Reliable Data Transfer

Reliable Data Transfer

Remember that the Internet's network-layer service (IP service) is untrustworthy. IP does not guarantee datagram delivery, does not guarantee in-order delivery of datagrams, and does not guarantee the integrity of the data in the datagrams. With IP service, datagrams can overflow router buffers and never reach their destination, datagrams can arrive out of order, and bits in the datagram can get corrupted (flipped from 0 to 1 and vice versa). Because transport-layer segments are carried across the network by IP datagrams, transport-layer segments can suffer from these difficulties as well.

TCP makes a reliable data transfer service on top of IP's unreliable best-effort service. TCP's reliable data transfer service makes sure that the data stream that a process reads out of its TCP receive buffer is uncorrupted, without gaps, without duplication, and in sequence; that is, the byte stream is exactly the same byte stream that was sent by the end system on the other side of the connection. How TCP provides a reliable data transfer involves many of the principles that we studied in "Principles of Reliable Data Transfer".

In our previous development of reliable data transfer techniques, it was conceptually easiest to suppose that an individual timer is associated with each transmitted but not yet acknowledged segment. While this is great in theory, timer management can require substantial overhead. Thus, the recommended TCP timer management procedures use only a single retransmission timer, even if there are several transmitted but not yet acknowledged segments. The TCP protocol explained in this section follows this single-timer recommendation.

We will discuss how TCP provides reliable data transfer in two incremental steps. We first present a highly simplified description of a TCP sender that uses only timeouts to recover from lost segments; we then present a more complete description that uses duplicate acknowledgments in addition to timeouts. In the subsequent discussion, we assume that data is being sent in only one direction, from Host A to Host B, and that Host A is sending a large file.

Figure 1 presents a highly simplified description of a TCP sender. We see that there are three most important events related to data transmission and retransmission in the TCP sender, data received from application above; timer timeout; and ACK receipt. Upon the occurrence of the first most important event, TCP receives data from the application, encapsulates the data in a segment, and passes the segment to IP. Note that each segment contains a sequence number that is the byte-stream number of the first data byte in the segment, as explained in "TCP Segment Structure". Also note that if the timer is already not running for some other segment. TCP starts the timer when the segment is passed to IP. (It is helpful to think of the timer as being associated with the oldest unacknowledged segment.) The expiration interval for this timer is the TimeoutInterval, which is calculated from EstimatedRTT and DevRTT, as explained in "Round-Trip Time Estimation and Timeout".

Simplified TCP sender

The second most important event is the timeout. TCP responds to the timeout event by retransmitting the segment that caused the timeout. TCP then restarts the timer.

The third most important event that must be handled by the TCP sender is the arrival of an acknowledgment segment (ACK) from the receiver (more specifically, a segment containing a valid ACK field value). On the occurrence of this event, TCP compares the ACK value y with its variable SendBase. The TCP state variable SendBase is the sequence number of the oldest unacknowledged byte. (Therefore SendBase-1 is the sequence number of the last byte that is known to have been received correctly and in order at the receiver.) As mentioned earlier, TCP uses cumulative acknowledgments, so that y acknowledges the receipt of all bytes before byte number y. If y > SendBase, then the ACK is acknowledging one or more previously unacknowledged segments. Therefore the sender updates its SendBase variable; it also restarts the timer if there currently are any not-yet-acknowledged segments.

A Few Interesting Scenarios


We have just explained a highly simplified version of how TCP provides reliable data transfer. But even this highly simplified version has many subtleties. To get a good feeling for how this protocol works, let's now walk through a few simple scenarios, Figure 2 shows the first scenario, in which Host A sends one segment to Host B. Assume that this segment has sequence number 92 and includes 8 bytes of data. After sending this segment, Host A waits for a segment from B with acknowledgment number 100. Although the segment from A is received at B, the acknowledgment from B to A gets lost. In this case, the timeout event occurs, and Host A retransmits the same segment. Obviously, when Host B receives the retransmission, it observes from the sequence number that the segment includes data that has already been received. Thus, TCP in Host B will discard the bytes in the retransmitted segment.

Retransmission due to a lost acknowledgment
   
In a second scenario, shown in Figure 3, Host A sends two segments back to back. The first segment has sequence number 92 and 8 bytes of data, and the second segment has sequence number 100 and 20 bytes of data. Assume that both segments arrive intact at B, and B sends two separate acknowledgments for each of these segments. The first of these acknowledgements has acknowledgment number 100; the second has acknowledgment number 120. Assume now that neither of the acknowledgements arrives at Host A before the timeout. When the timeout event occurs, Host A resends the first segment with sequence number 92 and restarts the timer. As long as the ACK for the second segment arrives before the new timeout, the second segment will not be retransmitted.

In a third and final scenario, suppose Host A sends the two segments, exactly as in the second example. The acknowledgment of the first segment is lost in the network, but just before the timeout event, Host A receives an acknowledgment with acknowledgment number 120. Host A therefore knows that Host B has received everything up through byte 119; so Host A does not resend either of the two segments. This scenario is shown in Figure 4.

Segment 100 not retransmitted


A cumulative acknowledgment avoids retransmission of the first segment

Doubling the Timeout Interval


We now discuss a few changes that most TCP implementations employ. The first concerns the length of the timeout interval after a timer expiration. In this modification, whenever the timeout event occurs, TCP retransmits the not-yet-acknowledged segment with the smallest sequence number, as explained above. But each time TCP retransmits, it sets the next timeout interval to twice the previous value, rather than deriving it from the last EstimatedRTT and DevRTT (as explained in "Round-Trip Time Estimation and Timeout"). For instance, assume Timeout Interval associated with the oldest not yet acknowledged segment is .75 sec when the timer first expires. TCP will then retransmit this segment and set the new expiration time to 1.5 sec. If the timer expires again 1.5 sec later, TCP will again retransmit this segment, now setting the expiration time to 3.0 sec. Thus the intervals grow exponentially after each retransmission. On the other hand whenever the timer is started after either of the two other events (that is, data received from application above, and ACK received), the TimeoutInterval is derived from the most recent values of EstimatedRTT and DevRTT.

This modification provides a limited form of congestion control. (More comprehensive forms of TCP congestion control will be studied in "TCP Congestion Control") The timer expiration is most likely caused by congestion in the network, that is, too many packets arriving at one (or more) router queues in the path between the source and destination, causing packets to be dropped and/or long queuing delays. In times of congestion, if the sources continue to retransmit packets persistently, the congestion may get worse. Instead, TCP acts more politely, with each sender retransmitting after longer and longer intervals. We will see that a similar idea is used by Ethernet when we study "CSMA/CD".

Fast Retransmit


One of the troubles with timeout-triggered retransmissions is that the timeout period can be relatively long. When a segment is lost, this long timeout period forces the sender to delay resending the lost packet, thereby increasing the end-to-end delay. Fortunately, the sender can often detect packet loss well before the timeout event takes place by noting so-called duplicate ACKs. A duplicate ACK is an ACK that reacknowledges a segment for which the sender has already received an earlier acknowledgment. To understand the sender's response to a duplicate ACK, we must look at why the receiver sends a duplicate ACK in the first place. Table 1 summarizes the TCP receivers ACK generation policy. When a TCP receiver receives a segment with a sequence number that is larger than the next expected, in-order sequence number, it detects a gap in the data stream that is, a missing segment. This gap could be the result of lost or reordered segments within the network.

TCP ACK Generation Recommendation

Since TCP does not use negative acknowledgments, the receiver cannot send an explicit negative acknowledgment back to the sender. Instead, it simply reacknowledges (that is, generates a duplicate ACK for) the last in-order byte of data it has received. (Note that Table 1 allows for the case that the receiver does not discard out-of-order segments.)

Because a sender often sends a large number of segments back to back, if one segment is lost, there will likely be many back-to-back duplicate ACKs. If the TCP sender receives three duplicate ACKs for the same data, it takes this as an indication that the segment following the segment that has been ACKed three times has been lost. In the case that three duplicate ACKs are received, the TCP sender performs a fast retransmit, retransmitting the missing segment before that segment's timer expires. This is shown in Figure 5, where the second segment is lost, then retransmitted before its timer expires. For TCP with fast retransmit. the following code snippet replaces the ACK received event in Figure 1:



We noted earlier that many subtle issues arise when a timeout/retransmit mechanism is implemented in an actual protocol such as TCP. The procedures above, which have evolved as a result of more than 15 years of experience with TCP timers, should convince you that this is indeed the case.

Go-Back-N or Selective Repeat?


We close our study of TCP's error-recovery mechanism by looking at the following question: Is TCP a GBN or an SR protocol? Remember that TCP acknowledgments are cumulative and correctly received but out-of-order segments are not individually ACKed by the receiver.

Fast retransmit - retransmitting the missing segment before the segments timer expires

Consequently, as shown in Figure 1 (see also "Go-Back-N (GBN) Figure 2"), the TCP sender need only maintain the smallest sequence number of a transmitted but unacknowledged byte (SendBase) and the sequence number of the next byte to be sent (NextSeqNum). In this sense, TCP looks a lot like a GBN-style protocol. But there are some striking differences between TCP and Go-Back-N. Many TCP implementations will buffer correctly received but out-of-order segments.  Consider also what happens when the sender sends a sequence of segments 1,2, , N, and all of the segments arrive in order without error at the receiver. Further suppose that the acknowledgment for packet n < N gets lost, but the remaining N 1 acknowledgments arrive at the sender before their respective timeouts. In this instance, GBN would retransmit not only packet n, but also all of the following packets n + 1, n + 2, ., N. TCP, however, would retransmit at most one segment, namely, segment n. Furthermore, TCP would not even retransmit segment n if the acknowledgment for segment n + 1 arrived before the timeout for segment n.

A proposed modification to TCP, the so-called selective acknowledgment, allows a TCP receiver to acknowledge out-of-order segments selectively rather than just cumulatively acknowledging the last correctly received, in-order segment. When combined with selective retransmission - skipping the retransmission of segments that have already been selectively acknowledged by the receiver - TCP looks a lot like our generic SR protocol. In this way, TCPs error-recovery mechanism is perhaps best categorized as a hybrid of GBN and SR protocols.


Tags

datagram, router, end system, selective acknowledgment, tcp receiver

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.