The internet network layer provides only best effort service with no guarantee that packets arrive at their destination. Also, since each packet is routed individually it is possible that packets are received out of order. For connection-oriented service provided by TCP, it is necessary to have a reliable data transfer (RDT) protocol to ensure delivery of all packets and to enable the receiver to deliver the packets in order to its application layer.
A simple alternating bit RDT protocol can be designed using some basic tools. This protocol is also known as a stop-and-wait protocol: after sending each packet the sender stops and waits for feedback from the receiver indicating that the packet has been received.
Stop-and-wait RDT protocols have poor performance in a long-distance connection. At best, the sender can only transmit one packet per round-trip time. For a 1000 mile connection this amounts to approximately 1 packet (about 1500 bytes) every 20 ms. That results in a pathetic 75 KB per second rate.
To improve transmission rates, a realistic RDT protocol must use pipelining. This allows the sender to have a large number of packets "in the pipeline". This phrase refers to packets that have been sent but whose receipt has not yet verified by the receiver.
The following tools are essential for any RDT protocol implemented on top of an unreliable network.
The data link and network layers have error detection for detecting bit errors in packets. However, error detection schemes can never detect all errors so it is helpful to have additional error detection in the transport layer to reduce the frequency of undetected errors.
Lower layer protocols with error detection usually have a simple policy for dealing with errors: discard the packet. A transport layer RDT protocol typically just does the same thing, letting its algorithm for dealing with missing packets deal with the problem. Since the lower layers may discard packets an RDT protocol must allow for the possibility that a receiver is not even aware of an attempted transmission.
Packets in the network layer are routed individually. This makes it possible that they are received in a different order than they are transmitted. Sequence numbering is essential for restoring the transmitted order.
Feedback involves information sent by the receiver back to the sender about reception of sent packets. This is essential for recovery of missing packets. The feedback takes the form of acknowledgments (ACKs) with one of three forms:
Most reliable data transfer protocols use only one of these types of acknowledgment. Negative acknowledgments are useful in human communication, but only because the acknowledgment is not lost, though it may be garbled. Since negative acknowledgment packets can be lost in the internet, they are not useful. They will not be considered in this presentation.
Cumulative acknowledgments allow acknowledgment of numerous packets at a time. They can be useful in pipelined protocols.
Packet loss in the network layer does not discriminate between data packets and acknowledgment packets. A sender in a reliable data transfer protocol needs to set a timer for transmitted packets. Generally the sender does one of two things:
If an acknowledgment arrives before the timer fires the sender stops the timer so that it will not fire.
The section on timers describes most of the sender policy involved in the alternating bit protocol. The only thing required to complete the protocol is handling of sequence numbers and the responsibilities of the receiver.
The alternating bit protocol uses a 1-bit sequence number. That is, the sequence number alternates between 0 and 1. The protocol only uses positive acknowledgments.
Both sender and receiver maintain state information about an expected sequence number.
The protocol is best described in terms of event handling by the receiver and sender for different kinds of events.
The receiver initially expects a packet with sequence number 0. The receiver has only two kinds of events to respond to.
The receiver has one state variable:
The receiver has two kinds of events to respond to.
Send an acknowledgment for the packet to the network layer and toggle the expected sequence number.
Forward the packet to the application layer.
Send an acknowledgment for the packet to the network layer. The sender must not have received the previous acknowledgment.
The sender begins with expected sequence number 0. It starts by accepting data coming in from the application layer. Then the sender has four types of events to respond to.
Stop accepting input from the application layer.
Save the packet in case it needs to be resent.
Send the packet to the network layer and start the timer.
Send the saved packet to the network layer and restart the timer.
Stop the timer so that it will not fire.
Toggle the expected sequence number.
Accept data from the application layer.
Ignore it. It is an acknowledgment of a resend due to a late acknowledgment.
Pipelining allows a sender to send out multiple packets without waiting for acknowledgment. But all packets that have been sent must be retained until they are acknowledged in case they need to be resent. To limit the number of packets that need to be retained, pipelined protocols need to set a bound on the number of packets in the pipeline (sent but not yet acknowledged). This bound imposes a "window" on the sequence numbers for packets in the pipeline.
Pipelined protocols can be distinguished based on how they use acknowledgments and timers. Two basic pipelined protocols, "Go back n" and "Selective Repeat" acknowledge individual packets, but differ in the number of timers that they use. The RDT protocol in TCP uses cumulative acknowledgments
The window size is the limit on the number of packets in the pipeline; that is, the number of packets that have been sent but not yet acknowledged. Protocols that use packet numbers as sequence numbers limit sequence numbers to a range twice the size of the window. If the window size is n then sequence numbers range from 0 to 2*n - 1.
Senders and receivers typically set up arrays for sent or received packets. The sequence number is used as an index into the array so the array size is twice the window size. Circular indexing is used for array access.
There are two tricky aspects to handling arrays with circular indexing:
Advancing the window start index can move it beyond the end of an array. If n is the window size then this can be corrected with the following C, C++, or Java code added after the advance:
ws = ws % (2 * n);
Testing if sequence number i is in the window breaks down into two cases depending on comparison between ws and n.
For ws ≤ n it can be seen from the diagram below that sequence number i is in the window when i ≥ ws AND i < ws + n. The window is shaded light green in the diagram.
For ws > n it can be seen from the diagram below that sequence number i is in the window when i ≥ ws OR i < ws - n. The window is shaded light green in the diagram. Note that it wraps around the end of the array in this case.
Basic pipelined protocols use individual acknowledgments. An acknowledgment with sequence number i only acknowledges receipt of the packet with sequence number i.
The pipelined protocol in TCP uses cumulative acknowledgments. An acknowledgment with sequence number i acknowledges receipt of all packets with sequence numbers up to and including i.
Pipelined protocols that use individual acknowledgments can either use a single timer or they can use a separate timer for each packet in the pipeline. With a single timer (go back n), the protocol does not know what packet the timer is firing for so it resends all unacknowledged packets. With a timer for each packet in the pipeline (selective repeat), the protocol can just resend the packet associated with the timer that fired.
Pipelined protocols that use cumulative acknowledgments just use a single timer, but still only resend a single packet. With cumulative acknowledgments the sender just resends the packet just beyond the most recent acknowledgment. When the receiver gets the resend it will send another acknowledgment to update the sender.
The receiver has one state variable:
The receiver has two kinds of events to respond to.
Save it and send an acknowledgment for the packet to the network layer.
Forward acknowledged packets at the beginning of the window to the application layer and advance windowStart past these packets.
Just send an acknowledgment for the packet to the network layer. The sender must not have received the previous acknowledgment.
The sequence number in an acknowledgment is always the same as the sequence number of the received packet that triggered the acknowledgment.
The sender has two state variables:
The sender has four kinds of events to respond to.
Advance the window to begin at the first unacknowledged packet.
Accept data from the application layer if the window has advanced.
Ignore it. It is an acknowledgment of a resend due to a late acknowledgment.
The go back n protocol uses individual acknowledgments. A go back n sender uses a single timer. When this timer fires the sender does not know which packet failed to be received so the sender resends all packets in the window.
Give the packet sequence number nextSequenceNumber and send it to the network layer. Save the packet in case it needs to be resent. Start or restart the timer.
Increment nextSequenceNumber and stop accepting input from the application layer if the window is full.
Send all unacknowledged saved packets in the window to the network layer and restart the timer.
Stop the timer so that it will not fire.
The selective repeat protocol, like the go back n protocol, uses individual acknowledgments. Unlike the go back n protocol, a selective repeat sender uses a timer for each packet in the pipeline. This makes it possible to be selective about handling timer firing. The selective repeat sender only resends the packet associated with the timer that fired.
Give the packet sequence number nextSequenceNumber and send it to the network layer. Save the packet in case it needs to be resent. Start timer nextSequenceNumber.
Increment nextSequenceNumber and stop accepting input from the application layer if the window is full.
Send saved packet i to the network layer and restart timer i.
Stop timer i so that it will not fire.
When cumulative acknowledgments are used the sequence number in the receiver acknowledgment always indicates the highest sequence number that has been received along with all with all of its predecessors.
The sender uses a single timer that is restarted either when a packet is sent and all of its predecessors have been acknowledged or when an acknowledgment arrives for a previously unacknowledged packet. There are some variations on this policy.
The sections in the menu show a tabular comparison of senders and receivers for the Alternating Bit, Go-Back-n, Selective Repeat, and Cumulative Acknowledgment reliable data transfer protocols.
The table entries are mostly the same. Changes are color coded with blue meaning simplifications for the Alternating Bit protocol and blue-violet meaning other changes.