Contents (hide)
1 Automatic Repeat-reQuest
2 Stop & Wait
3 Go Back N
4 Selective Repeat

Reliable Data Transfer Protocols: TCP

Objectives

We review briefly the general methods that can be used to build a reliable data transfer protocol on top of an unreliable protocol. For example, TCP provides reliability on top of IP which is unreliable.

A reliable protocol can provide assurances about:
• Data consistency: the data that is received is the same as the data that is sent. For example, if I send "ABC", you receive "ABC" and not "ABD".
• Ordering: data is received in the same order as it is sent. For example, if I send "ABC", you receive "ABC" and not "ACB".
• No loss: all the data that is sent is received. For example, if I send "ABC", you receive "ABC" and not "AC".

Reliable protocols can be obtained by combining the following tools:
• Acknowledgments: the sender waits to receive a message from the receiver indicating that the message sent has been received
• Timeouts and Retries: if the sender does not receive acknowledgment within a certain time delay, it assumes that the message it sent got lost, and it retries by sending the same message again. Timeouts and retries require the usage of buffers (unacknowledged messages must be kept in memory in case they need to be re-sent).
• Checksums: add a one-way function signature to the packets sent. For example, when sending a packet of 32-bit words, add a one-word 32-bit signature which is computed as the 32-bit binary sum of all the sent words. The receiver receives the data and the checksum. It recomputes the checksum on its side. If the computed checksum matches the received checksum, then we assume the data was properly received. Else, we assume the data got corrupted, and send a negative acknowledgment. Checksums are a special case of redundancy check.
• Sequence numbers: since packets can arrive in a different order than the order in which they were sent, the receiver must be able to re-order the packets. This is obtained by numbering the packets when sending them. The receiver must buffer packets it receives out of order until the preceding packets are received.

Various algorithms have been developed that combine these principles in different ways.

# Automatic Repeat-reQuest

Automatic Repeat Request (ARQ) is the general family of protocols which rely on sending an acknowledgment packet to confirm that data was properly received. Stop and Wait, Go-back-N and selective repeat are 3 variations of this general approach.

# Stop & Wait

Stop and Wait is the simplest form of ARQ. In this method, the sender sends 1 packet, then waits for the acknowledgment.

The sender behaves as follows:
Send packet / Remember ID of sent packet.
Start timer
If timeout: resend packet.
If receive acknowledgment of another packet: ignore it (compare ID of packet).
If receive positive Acknowledgment: move to next packet.
If receive negative Acknowledgment: resend packet, restart timer.


Read packet.
Compute checksum.
If computed checksum == received checksum, send positive Acknowledgment
else send negative acknowledgment
Store ID of last received packet.


Note that the same packet can be sent more than once (because of timeouts or negative acks), and as a result received more than once. Similarly, the ack packet can be sent more than once and received more than once by the sender. Therefore, there must be specific code to handle these cases. This is solved in Stop and Wait by adding a sequence number to the packets. In the case of stop and wait, the sequence number can be a single bit, which is flipped each time the sender moves to the next packets.

Stop and Wait is inefficient, because one must wait for a full round-trip (send a packet, wait for an ack packet) between each packet.

# Go Back N

Go back N is an improved, more efficient form of ARQ compared to Stop and Wait. In this method, the sender can go ahead and send up to N packets without waiting to receive acknowledgments. In this case, the sequence number must be a number between 0 and n-1.

The receiver remembers the sequence number of the next packet it expects to receive. When it receives the right packet, it sends this number with every ACK it sends. The receiver will ignore any packet that does not have the exact sequence number it expects – whether that packet is a "past" duplicate of a packet it has already ACK'ed, or whether that packet is a "future" packet past the lost packet it is waiting for.

Once the sender has sent all of the packets in its window, it will detect that all of the packets since the first lost packet are outstanding, and will go back to the sequence number of the last ACK it received from the receiver and fill its window starting with that packet and continue the process over again.

The sending window size must be no more than the number of sequence numbers (if they are numbered from zero to n-1) to verify transmission in cases of any packet (any data or ACK packet) being dropped.

Figure taken from – Computer Networking: A Top Down Approach Featuring the Internet. Jim Kurose, Keith Ross.

# Selective Repeat

Selective Repeat is the most effective method of ARQ. It avoids the limitation of Go-back-N that re-sends the whole N packets in case a single packet was lost.