The Network layer for a protocol stack is responsible for getting a message from the source machine to the destination machine. However, there are often several programs running on the source machine and several programs running on the destination machine. The Transport layer for a protocol stack is responsible for getting the message to the right program on the destination machine. On the Internet there is one main protocol for the Network layer called IP (for Internet Protocol). However, on the Internet there are two alternative protocols for the Transport layer called TCP (Transmission Control Protocol) and UDP (User Datagram Protocol). TCP is used by many of the applications because it guarantees reliable delivery. Reliable delivery means that TCP ensures that all parts of a message will eventually reach the destination program on the destination machine undamaged. Unfortunately, in reality parts of a message sometimes will not reach the destination or will reach the destination corrupted (damaged). Thus, TCP has to have some means of detecting and recovering from lost or damaged message parts (the TCP message parts are officially called segments, but we will call them packets which is a more message-like name). This means of recovering from errors is called reliable data transfer.
Reliable Data Transfer Protocols: Stop-and-Wait
The applet illustrates the basic idea of how error control can be done at the transport layer. The protocol TCP uses is is based on the use of acknowledgements, timouts, and retransmission. These protocols retransmit a data packet if acknowledgements and timeouts indicate that the data packet may not have been successfully transmitted during the previous attempt. This same family of protocols is also used at other protocol layers such as the application layer and the link layer. The simplest such protocol is called Stop-and-Wait. In Stop-and-Wait the Sender sends one data packet. When the Receiver receives that data packet, the Receiver checks to see if the data packet has been corrupted. If the data packet has not been corrupted, then the Receiver sends an acknowledgement packet back to the Sender. When the Sender receives the acknowledgement, the Sender can then send the next data packet. Near the bottom of the applet's screen the combination of the radio button labeled Stop-and-Wait and the radio button labeled No Loss illustrates this case.
What happens in the Stop-and-Wait protocol if something goes wrong? One case is when the sender's packet is lost or corrupted. In this case the sender has to recognize that the data packet needs to be retransmitted. Notice that the receiver will not send an acknowledgment if the data packet has been lost or corrupted. Consequently, the sender can use a timeout period. The timeout period starts when the data packet is sent. If the sender does not receive an acknowledgment packet by when the timeout period expires, then when the timeout period expires, the sender retransmits the data packet. Near the bottom of the applet's screen the combination of the radio button labeled Stop-and-Wait and the radio button labeled Lost Data illustrates this case.
When this simulation executes, notice the timer in the top left of the applet screen. When the timer expires for a packet, the sender retransmits the packet. There is another approach to handling a lost or corrupted data packet in the Stop-and-Wait protocol that is not shown in the applet. In this approach the receiver sends a negative acknowledgment packet when the receiver receives a corrupted data packet. When the sender receives a negative acknowledgment packet, the sender knows to immediately retransmit the data packet. Notice that with negative acknowledgment packets, the sender still needs a timeout period to handle when the data packet is lost instead of corrupted.
The second way things can go wrong in Stop-and-Wait is when the sender's data packet reaches the receiver and is not corrupted, but the receiver's acknowledgment packet is lost or corrupted. In this case the sender waits until the timeout period for the data packet expires and retransmits the data packet. The receiver will then receive a second copy of the data packet. The receiver discards the second copy of the data packet and retransmits the acknowledgment packet. This may happen several times until finally the acknowledgment packet reaches the sender uncorrupted and the sender stops retransmitting the data packet. Near the bottom of the applet's screen the combination of the radio button labeled Stop-and-Wait and the radio button labeled Lost ACK illustrates this case.
Reliable Data Transfer Protocols: Pipelined (Selective Repeat)
Stop-and-Wait is called Stop-and-Wait since the sender has to wait until the acknowledgement for the one outstanding packet arrives or until the timeout for the one outstanding packe expires. In some cases, this means that the sender can be idle for a large fraction of the time. If the time it takes for a packet to reach the receiver is much longer than the time it takes for the sender to transmit a packet, then the sender will spend most of its time idle waiting for the acknowledgment. If the sender needs to send several packets, then the time until the last of the packets is sent might be quite long due to this waiting.
Pipelined reliable data transfer protocols address this problem. In a pipelined reliable data transfer protocol, the sender can start sending a second data packet before the sender receives the acknowledgment for the first data packet. Thus, if the sender needs to send several packets, then the time until the last of the packets is sent will be shorter with a pipelined protocol. Thus, a pipelined protocol can have better performance than the Stop-and-Wait protocol. It is possible to measure the extent to which a pipelined protocol has better performance that Stop-and-Wait. This is called measuring the utilization of the connection or link between the sender and the receiver. The textbook by Kurose and Ross (Subsection 3.4.2, pages 214-215) shows the difference in utilization between these two protocols for one realistic situation. Near the bottom of the applet's screen the combination of the radio button labeled Pipelined and the radio button labeled No loss illustrates how pipelining can improve network utilization. The sender can keep on sending packets even if the acknowledgements for the earlier packets have not yet returned. Thus, it takes less time to send a sequence of packets.. The applet assumes that the sender can send at most three packets at any one time and wants to send four packets.
Errors can occur when a pipelined protocol is used, just as they can occur when the stop-and-wait protocol is used. The same two cases exist. 1) a lost or corrupted data packet or 2) a lost or corrupted acknowledgment packet. There are two approaches to this problem. In one approach, called Go-Back-N, the sender retransmits all the data packets it had sent since the lost or corrupted data packet. In the second approach, called Selective Repeat, the sender just retransmits the lost or corrupted data packet. Selective Repeat causes fewer packets to be retransmitted, but requires more overhead on the part of the receiver.
The applet assumes the Selective Repeat approach is used. We discuss how the above error conditions are handled in the selective repeat version of the pipelined reliable data transfer protocol. Since the sender of the data packets may have several data packets simultaneously in transit, the acknowledgment packets have to differ from those of the stop-and-wait protocol. In the stop-and-wait protocol the acknowledgment packet contains the sequence number of the data packet received. In contrast, in selective repeat the receiver keeps track of the sequence number, N, of the last packet that it received successfully and such that the packets of all lower sequence numbers have been received successfully. The acknowledgment packet in selective repeat always contains the sequence number N + 1. Thus, if the receiver receives a data packet that is corrupted or out of sequence, then the receiver just resends an acknowledgement packet that contains the number N + 1. This continues until the data packet with sequence number N + 1 arrives uncorrupted at the receiver. These acknowledgment packets are called duplicate ACKs.
We now consider each of the error cases. If a data packet is lost, the the receiver does not send an acknowledgement packet since the receiver does not know that a data packet had been sent. If a data packet arrives corrupted or out of sequence, the the receiver resends a duplicate ack containing sequence number N + 1 as described above. In either of these cases, the timeout period for the lost or corrupted data packet expires and the sender retransmits the data packet.
If acknowledgment pack is lost or corrupted, then the timeout period for that data packet expires and the sender retransmits the data packet. The receiver discards the new copy of the data packet and sends a duplicate ack as described above. Both cases so far are just like Idle RQ.
As with the stop-and-wait protocol, the pipelined protocols could be extended by the receiver sending a negative acknowledgment when the receiver receives a corrupted data packet, but the sender of the data packet would still need a timeout period to handle the case of lost data packets.
The applet also illustrates the effects of changing the link
bandwidth, the packet size, and the one way delay.
Increasing the link bandwidth, for example, causes the time
from when the first bit leaves the sender to the time the
last bit leaves the sender to decrease.
This is shown by the rectangle of the packet becoming not as
tall, but instead wider (so the total area is constant).
Increasing the packet size, for example, causes the area
of the packet's rectangle to increase by the packet becoming
taller.
The one way delay is the propagation delay of a packet from
the sender to the receiver.
This propagation delay is determined by the link length and
the propagation speed of the media.
Increasing the one way delay is shown by making
the rectangle for the packet move more slowly towards the
receiver and by the timers advancing more slowly.
These visual aspects of the simulation reflect that it takes
a longer time for the packet to reach the receiver and for
the acknowledgement to reach the sender.
The timer speed needs to be slowed proportionally to the
slowing of the packet movement because otherwise timeouts
could occur inappropriately. For example, if a timer expires
in less time than it takes for a packet to reach the receiver
and the accompanying acknowledgement to reach the sender, then
every packet send will cause a timeout.
References
[1]J.F. Kurose and K.W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Second Edition, Addison Wesley, 2003.
Acknowledgements and Developer Information
Current Version Date: February 2004
Copyright notice (C) Mark A. Holliday. All rights reserved.