Tcp – Why is TCP Fast Retransmit able to detect “up to” 3 dropped packets

protocol-theorytcp

In section 6.3.3 (page 512) of the book Computer Networks: A Systems Approach, by Peterson & Davie, I found the following statement:

Given the current 64-KB maximum advertised window size, TCP’s fast retransmit mechanism is able to detect up to three dropped packets per window in practice.

My question is: why "up to" 3 dropped packets?

I think I may have sketched part of the argument, but I'm still not sure about it:

  • Assume a (max. ?) MSS of 1 kB
  • Assume one currently has min(congestion_wnd, advertised_wnd) = 64 kB
  • I'll think of window sizes in terms of packets, so I'll consider a packet to have size 1 kB, and thus a window size of 64 packets.

Say that a TCP sender is currently transmitting a window of size 64 packets, starting at sequence number p. Say that packet p + d is dropped. We can detect the dropped packet and re-transmit it if the sender has (at least) 4 more packets to send after packet p + d (i.e. +3 subsequent packets to generate 3 duplicate ACKs + 1 re-transmission). This leaves us with 64 – 4 = 60 'slots' on which we can have dropped packets.

The cost of a dropped packet is 5 packets, i.e. the 1 dropped packet + 3 subsequent packets to get 3 duplicate ACKs + 1 re-transmission. This gives us a credit of x = 60 / 5 = 12 packets to drop, which is larger than 3.

Where is my logic failing? I'm also doubtful about the validity of my assumptions regarding packet and MSS size in byte, but the statement seems to combine (mix up?) packets and byte sizes, which may contribute to the confusion.

Thanks!

Best Answer

Based on their understanding of the Fast Retransmit algorithm, I believe the authors are giving you their real-world idea of what to expect. Understand, this is the authors' idea. Even your argument is made with some assumptions which may, or may not, be congruent with the authors' assumptions. You could contact the authors for clarification. A simple search turns up a verified e-mail address for Larry Peterson at the University of Arizona.

RFC 2581, TCP Congestion Control:

3.2 Fast Retransmit/Fast Recovery

A TCP receiver SHOULD send an immediate duplicate ACK when an out- of-order segment arrives. The purpose of this ACK is to inform the sender that a segment was received out-of-order and which sequence number is expected. From the sender's perspective, duplicate ACKs can be caused by a number of network problems. First, they can be caused by dropped segments. In this case, all segments after the dropped segment will trigger duplicate ACKs. Second, duplicate ACKs can be caused by the re-ordering of data segments by the network (not a rare event along some network paths [Pax97]). Finally, duplicate ACKs can be caused by replication of ACK or data segments by the network. In addition, a TCP receiver SHOULD send an immediate ACK when the incoming segment fills in all or part of a gap in the sequence space. This will generate more timely information for a sender recovering from a loss through a retransmission timeout, a fast retransmit, or an experimental loss recovery algorithm, such as NewReno [FH98].

The TCP sender SHOULD use the "fast retransmit" algorithm to detect and repair loss, based on incoming duplicate ACKs. The fast retransmit algorithm uses the arrival of 3 duplicate ACKs (4 identical ACKs without the arrival of any other intervening packets) as an indication that a segment has been lost. After receiving 3 duplicate ACKs, TCP performs a retransmission of what appears to be the missing segment, without waiting for the retransmission timer to expire.

After the fast retransmit algorithm sends what appears to be the missing segment, the "fast recovery" algorithm governs the transmission of new data until a non-duplicate ACK arrives. The reason for not performing slow start is that the receipt of the duplicate ACKs not only indicates that a segment has been lost, but also that segments are most likely leaving the network (although a massive segment duplication by the network can invalidate this conclusion). In other words, since the receiver can only generate a duplicate ACK when a segment has arrived, that segment has left the network and is in the receiver's buffer, so we know it is no longer consuming network resources. Furthermore, since the ACK "clock" [Jac88] is preserved, the TCP sender can continue to transmit new segments (although transmission must continue using a reduced cwnd).

The fast retransmit and fast recovery algorithms are usually implemented together as follows.

  1. When the third duplicate ACK is received, set ssthresh to no more than the value given in equation 3.

  2. Retransmit the lost segment and set cwnd to ssthresh plus 3*SMSS. This artificially "inflates" the congestion window by the number of segments (three) that have left the network and which the receiver has buffered.

  3. For each additional duplicate ACK received, increment cwnd by SMSS. This artificially inflates the congestion window in order to reflect the additional segment that has left the network.

  4. Transmit a segment, if allowed by the new value of cwnd and the receiver's advertised window.

  5. When the next ACK arrives that acknowledges new data, set cwnd to ssthresh (the value set in step 1). This is termed "deflating" the window.

    This ACK should be the acknowledgment elicited by the retransmission from step 1, one RTT after the retransmission (though it may arrive sooner in the presence of significant out- of-order delivery of data segments at the receiver). Additionally, this ACK should acknowledge all the intermediate segments sent between the lost segment and the receipt of the third duplicate ACK, if none of these were lost.

Note: This algorithm is known to generally not recover very efficiently from multiple losses in a single flight of packets [FF96]. One proposed set of modifications to address this problem can be found in [FH98].

Related Topic