Principles of Reliable Transfer

How do you even ensure reliability in a packet switching network? TCP is a reliable data transfer protocol that is implemented on top of an unreliable IP end-to-end network layer. W ith a reliable channel, no transferred bits are corrupted or lost, and all are delivered in the order in which they were sent.

Let’s start with the perfectly reliable channel to lay the foundations For completely reliable underlying channel, with receiver able to receive data as fast as the sender happens to send, the sending and receiving side has only one state.

Over a non-lossy channel with bit errors

A realistic model of the underlying channel is one in which bits in a packet may be corrupted, such requires re-transmission based protocols called ARQ (automatic repeat request).

Three additional protocol capabilities in ARQ:

• Error detection: Need a mechanism to detect when bits errors have occurred, just like checksum
• Receiver feedback: ACK and NAK acknowledgement packets to tell sender that error has occurs
• Re-transmission: A packet that is sent in error at the receiver will be transmitted by the sender.

The sending side has two states, one waiting for data to be passed down the upper layer when rdt_send() occurs, the sender will create a packet containing the data to be sent, along with a packet checksum, after which enters waiting state where it cannot get more data from the upper layer; that is rdt_send() event cannot occur.

The receiver-side has a single state, on packet arrival, the receiver replies with either an ACK or NAK, depending on whether or not the received packet is corrupted.

Wait wait, what about acknowledgement packets getting corrupted? We have not accounted the possibility that the ACK or NAK packet itself could be corrupted, if an ACK or NAK is corrupted, the sender has no way of knowing whether or not the receiver has correctly received the last piece of transmitted data.

Three possibilities for handling corrupted ACKs or NAKs:

• Add enough checksum bits to allow the sender not only to detect, but also to recover from, bit errors, solves the immediate problem for a channel that can corrupt packets but not lose them.
• Sender simply re-sends the current data packet when it receives a garbled ACK or NAK packet, however introduces duplicate packets into the sender-to-receiver channel, fundamental difficult is that cannot know a prior whether an arriving packet contains new data or is a re-transmission.

How to deal with this duplication of packets? Simple solution and one adopted in almost all and TCP is to add a new field to the data and have the sender number its data packets by putting a sequence number into this field, the receiver then need only check this sequence number to determine whether or not the received packet is a re-transmission.

What should be the size of this sequence number? For the simple case of stop-and-wait protocol, a 1-bit sequence number will suffice, since it will allow the receiver to know whether the sender is re-sending the previous transmitted packet as the sender knows that a received ACK or NAK packet was generated in response to its most recently transmitted data packet, since we are currently assuming that the channel does not lose packets.

Over a lossy channel with bit errors

When underlying channel can lose packets, two additional concerns must now be addresses by the protocol, how to detect packet loss and what to do when packet loss occurs.

Sender to judiciously choose a time value and if an ACK is not received within this time, the packet is re-transmitted

What is the countdown timer value? The sender must clearly wait at least as a round-trip delay between the sender and receiver plus whatever amount of time is needed to process a packet at the receiver.

Pipelined data transfer

The stop-and-wait looks quite slow, any improvements? At the heart of this protocol performance is the fact that it is a stop-and-wait protocol, rather than operate in a stop-and-wait manner, the sender is allowed to send multiple packets without waiting for acknowledgement, following consequences:

1. The range of sequence numbers must be increased, since each in-transit packet (not counting re-transmissions) must have a unique sequence number and there may be multiple, in-transit unacknowledged packets.
2. The sender and receiver sides of the protocols may have to buffer more than one packet, minimally the sender will have to buffer packets that have been transmitted but not yet acknowledged.
3. The range of sequence numbers needed and the buffering requirements will depend on the manner in which a data transfer protocol responds to lost, corrupted, and overly delayed packets.

Go-back-N

Okay one simple one is just allowing multiple packets to stay in pipeline? The sender is allowed to transmit multiple packets when available without waiting for an acknowledgement, but is constrained to have no more than some maximum allowable number, N, of unacknowledged packets in the pipeline.

Sender’s view of sequence numbers

If we define $\text{base}$ to be the sequence number of the oldest acknowledged packet and $\text{nextseqnum}$ be the smallest unused sequence number i.e. the sequence number of the next packet to be sent then four intervals can be identified.

$[0,\text{base}-1]$ corresponds to packets that have already been transmitted and acknowledged. $[\text{base},\text{nextseqnum}-1]$ corresponds to packets that have been send but not yet acknowledged. $[\text{nextseqsum},\text{base}+N-1]$ can be used for packets that can be sent immediately should data arrive from the upper layer. $[\text{base}+N,...]$ cannot be used until an acknowledgment packet currently in the pipeline has been acknowledged.

The range of permissible sequence numbers for transmitted but not yet acknowledged packets can be viewed as a window of size $N$ over the range of sequence numbers.

As the protocol operates, this window slides forward over the sequence number space, for this reason $N$ is the window size.

Okay why limit the window size at all? Flow control is one of the reason to impose a limit on the sender.

In practice, a packet’s sequence number is carried in a fixed-length field in the packet header, if $k$ is the number of bits in the packet sequence number field, the range of sequence numbers is thus $[0,2^k-1]$

How does this work?

This looks like a programming language specification, explain in words please? The GBN sender must respond to three types of events:

1. Invocation from above When rdt_send() is called from above, the sender first checks to see if the window is full, if not a packet is created and sent, if full, the sender simply returns the data back to upper layer, an implicit indication that the window is full, in a real implementation, the sender would more likely have either buffered but not immediately sent this data, or would have a synchronization mechanism, that would allows the upper layer to call rdt_send() only when the window is not full.
2. Receipt of an ACK In our GBN protocol, an acknowledgment for a packet with seq number will be taken to be a cumulative acknowledgment, indicating that all packets with a sequence number up to and including $n$ have been correctly received at the receiver.
3. A timeout event If a timeout occurs, the sender re-sends all packets that have been previously sent but that have not yet been acknowledged, uses only one timer, which can be thought of as a timer for the oldest transmitted but not yet acknowledged packet, if an ACK is received but there are still additional transmitted but not yet acknowledged packets, the timer is restarted, if there are no outstanding, unacknowledged packets the timer is stopped

Receivers actions:

• If a packet with sequence number $n$ is received correctly and is in order that is, the data last delivered to the upper layer came from a packet with sequence number $n-1$, the receiver sends an ACK for packet $n$ and delivers the data portion of the data to the upper layer.
• In other cases, the packet is discarded, and re sends an ACK for the most recently received in order packet, is a replacement of negative acknowledgement.
• Since packets are delivered one at a time to the upper layer, if packet $k$ has been received and delivered, then all packets with a sequence number lower than $k$ have also been delivered.

Why to discard the out-of-order packets? Use of cumulative acknowledgement is a natural choice for GBN, seems wasteful, but advantage of this approach is the simplicity of receiver buffering - the receiver need not buffer any out of order packets, thus while the sender must maintain the upper and lower bounds of its window and the position of $\text{nextseqnum}$ within this window, the only piece of information the receiver need maintain is the sequence number of the next in order packet.

Selective Repeat (SR)

GBN has some shortcomings, I see? GBN allows sender to potentially fill the pipeline with packets, thus avoiding the channel utilization problems, but also suffers, when the window size and bandwidth delay product are both large, many packets can be in the pipeline, a single packet error can thus cause GBN to re-transmit a large number of packets.

Selective-repeat protocols avoid unnecessary re-transmissions by having the sender re-transmit only those packets that it suspects were received in error that is, were lost or corrupted at the receiver.

The SR receiver will acknowledge a correctly received packet whether or not it is in order, out of order packets are buffered until any missing packets (those with lower sequence numbers) are received, at which point a batch of packets can be delivered to the upper layer.

SR sender events and actions:

1. Data received from above When data is received from above, the SR sender checks the next available sequence number for the packet, if the sequence number is within the sender’s window, the data is packetized and sent; otherwise is either buffered or returned for later.
2. ACK received If an ACK is received, the SR sender marks that packet as having been received, provided it is in the window, if the packet’s sequence number is equal to $\text{send-base}$, the window base is moved forward to the unacknowledged packet with the smallest sequence number, if the window moves and there are un-transmitted packets with sequence numbers that now fall within the window, these packets are transmitted.
3. Timeout Timers are again used to protect against lost packets, however each packet must now have its own logical timer, since only a single packet will be transmitted on timeout, a single hardware timer can be used to mimic the operation of multiple logical timers.

SR receiver events and actions:

1. Packet with sequence number in $[\text{rcv-base},\text{rcv-base+N-1}]$ is correctly received, in this case the received packet falls within the receiver’s window and a selective ACK is returned to the sender, if the packet was not previously received, it is buffered, if this packet has a sequence number equal to the base of the receive window $\text{rcv-base}$ then this packet, and any previously buffered and consecutively numbered packets are delivered to the upper layer, and the receive window is then moved forward by the number of packets delivered to the upper layer.
2. Packets with sequence number in $[\text{rcv-base}-N,\text{rcv-base}-1]$ is correctly received, in this case, an ACK must be generated, even though this is a packet that the receiver has previously acknowledged.
3. Otherwise, the packet is ignored.

Wait does receiver really acknowledges the already received packets? The receiver re-acknowledges rather than ignores already received packets with certain sequence numbers below the current window base.

Is it the time to finally lose the FIFO assumption? We have assumed that packets cannot be reordered within the channel between the sender and receiver, generally a reasonable assumption when the sender and receiver are connected by a single physical wire, however, when the channel connecting two is a network, packet reordering can occur.

One manifestation of packet reordering is that old copies of a packet with a sequence or acknowledgement number of $x$ can appear, even though the sender’s not the receiver’s window contains $x$, with packet reordering, the channel can be though of as essentially buffering packets and spontaneously emitting these packets at any point in the future.

Because sequence numbers may be reused, some care must be taken to guard against such duplicate packets, the approach taken in practice is to ensure that a sequence number is not reused until the sender is sure that any previously sent packets with sequence number $x$ are no longer in the network, done by assuming that a packet cannot live in the network for longer than some fixed amount of time, a maximum packet lifetime of approximately three minutes is assumed in the TCP extensions for high-speed networks.