TCP/IP: TCP Timeout and Retransmission

The original TCP specification [RFC0793] had TCP update a smoothed RTT estimator (called SRTT) using the following formula:

Given the estimator SRTT, which changes as the RTT changes, [RFC0793] recommended that the RTO be set to the following:

We shall call this assignment procedure the classic method. It generally results in the RTO being set either to 1s, or to about twice SRTT.

For relatively stable distributions of the RTT, this was adequate. However, when TCP was run over networks with highly variable RTT_s (e.g., early packet radio networks in this case), it did not perform so well.

In [J88], Jacobson detailed problems with the classic method further—basically, that the timer specified by [RFC0793] cannot keep up with wide fluctuations in the RTT (and in particular, it causes unnecessary retransmissions when the real RTT is much larger than expected).

To address this problem, the method used to assign the RTO was enhanced to accommodate a larger variability in the RTT.

The following equations that are applied to each RTT measurement M (called RTT_s earlier):

Here, the value srtt effectively replaces the earlier value of SRTT, and the value rttvar, which becomes an EWMA of the mean deviation, is used instead of β to help determine the RTO.

This is the basis for the way many TCP implementations compute their RTOs to this day, and because of its adoption as the basis for [RFC6298] we shall call it the standard method, although there are slight refinements in [RFC6298].

A SACK-capable receiver is allowed to generate SACKs if it has received the SACK-Permitted option during the TCP connection establishment.

Generally speaking, a receiver generates SACKs whenever there is any out-of-order data in its buffer. This can happen either:

The receiver places in the first SACK block the sequence number range contained in the segment it has most recently received.

A SACK-capable sender must be used that treats the SACK blocks appropriately and performs selective retransmission by sending only those segments missing at the receiver, a process also called selective repeat.

The SACK sender keeps track of any cumulative ACK information it receives (like any TCP sender), plus any SACK information it receives.

When a SACK-capable sender has the opportunity to perform a retransmission, usually because it has received a SACK or seen multiple duplicate ACKs, it has the choice of whether it sends new data or retransmits old data.

To understand how the use of SACK alters the sender and receiver behaviors, we repeat the preceding fast retransmit experiment, but this time the sender and receiver are using SACK.

With a non-SACK TCP, an ACK can indicate only the highest in-sequence segment back to the sender. With SACK, it can signal other (out-of-order) segments as well.

DSACK or D-SACK (stands for duplicate SACK [RFC2883]) is a rule, applied at the SACK receiver and interoperable with conventional SACK senders, that causes the first SACK block to indicate the sequence numbers of a duplicate segment that has arrived at the receiver, which is usually to determine when a retransmission was not necessary and to learn additional facts about the network.

The change to the SACK receiver is to allow a SACK block to be included even if it covers sequence numbers below (or equal to) the cumulative ACK Number field.

Exactly what a sender given DSACK information is supposed to do with it is not specified by [RFC2883].

The experimental Eifel Detection Algorithm [RFC3522] deals with the retransmission ambiguity problem using the TCP TSOPT to detect spurious retransmissions.

The Eifel Detection Algorithm is able to detect spurious behavior earlier than the approach using only DSACK because it relies on ACKs generated as a result of packets arriving before loss recovery is initiated.

DSACKs, conversely, are able to be sent only after a duplicate segment has arrived at the receiver and able to be acted upon only after the DSACK is returned to the sender.

Detecting spurious retransmissions early can offer advantages, because it allows the sender to avoid most of the go-back-N behavior.

The mechanics of the Eifel Detection Algorithm are simple. It requires the use of the TCP TSOPT.

The Eifel Detection Algorithm can be combined with DSACKs which can be beneficial when an entire window’s worth of ACKs are lost but both the original transmit and retransmission have arrived at the receiver.

Forward-RTO Recovery (F-RTO) [RFC5682] is a standard algorithm for detecting spurious retransmissions.

F-RTO makes a modification to the action TCP ordinarily takes after a timer-based retransmission.

F-RTO modifies the ordinary behavior of TCP by having TCP send new (so far unsent) data after the timeout-based retransmission when the first ACK arrives. It then inspects the second arriving ACK.

The Eifel Response Algorithm [RFC4015] is a standard set of operations to be executed by a TCP once a retransmission has been deemed spurious.

Because the response algorithm is logically decoupled from the Eifel Detection Algorithm, it can be used with any of the detection algorithms we just discussed.

The Eifel Response Algorithm was originally intended to operate for both timer-based and fast retransmit spurious retransmissions but is currently specified only for timer-based retransmissions.

Packet reordering can occur in an IP network because IP provides no guarantee that relative ordering between packets is maintained during delivery.

This can be beneficial (to IP at least), because IP can choose another path for traffic (e.g., that is faster) without having to worry about the consequences that doing so may cause traffic freshly injected into the network to pass ahead of older traffic, resulting in the order of packet arrivals at the receiver not matching the order of transmission at the sender.

There are other reasons packet reordering may occur. For example, some high-performance routers employ multiple parallel data paths within the hardware [BPS99], and different processing delays among packets can lead to a departure order that does not match the arrival order.

Reordering may take place in the forward path or the reverse path of a TCP connection (or in some cases both). The reordering of data segments has a somewhat different effect on TCP as does reordering of ACK packets.

Recall that because of asymmetric routing, it is frequently the case that ACKs travel along different network links (and through different routers) from data packets on the forward path.

When traffic is reordered, TCP can be affected in several ways.

Because a TCP receiver is supposed to immediately ACK any out-of-sequence data it receives in order to help induce fast retransmit to be triggered on packet loss, any packet that is reordered within the network causes a receiver to produce a duplicate ACK.

If fast retransmit were to be invoked whenever any duplicate ACK is received at the sender, a large number of unnecessary retransmissions would occur on network paths where a small amount of reordering is common.

To handle this situation, fast retransmit is triggered only after the duplicate threshold (dupthresh) has been reached.

The problem of distinguishing loss from reordering is not trivial. Dealing with it involves trying to decide when a sender has waited long enough to try to fill apparent holes at the receiver.

Fortunately, severe reordering on the Internet is not common [J03], so setting dupthresh to a relatively small number (such as the default of 3) handles most circumstances. That said, there are a number of research projects that modify TCP to handle more severe reordering [LLY07]. Some of these adjust dupthresh dynamically, as does the Linux TCP implementation.

Although rare, the IP protocol may deliver a single packet more than one time. This can happen, for example, when a link-layer network protocol performs a retransmission and creates two copies of the same packet.

The effect of packet 3 being duplicated is to produce a series of duplicate ACKs from the receiver. This is enough to trigger a spurious fast retransmit, as the non-SACK sender may mistakenly believe that packets 5 and 6 have arrived earlier. With SACK (and DSACK, in particular) this is more easily diagnosed at the sender.

With DSACK, each of the duplicate ACKs for A3 contains DSACK information that segment 3 has already been received. Furthermore, none of them contains an indication of any out-of-order data, meaning the arriving packets (or their ACKs) must have been duplicates. TCP can often suppress spurious retransmissions in such cases.

tc controls the transmit queues of your kernel. Normally when applications on your computer generate data to send, the data is passed to your kernel (via TCP and IP) for transmission on the network interface. The packets are transmitted in a first-in-first-out (FIFO) order.

tc allows you to change the queuing mechanisms (e.g. giving priority to specific type of packets), as well as emulate links by delaying and dropping packets.

Here we will use tc to drop packets. Because tc controls the transmit queues, we use it on a source computer (normally tc doesn’t impact on what is received by your computer, but there are exceptions).

netem is a special type of queuing discipline used for emulating networks. The above command tells the Linux kernel to drop on average 25% of the packets in the transmit queue. You can use different values of loss (e.g. 10%).

When using tc you can show the current queue disciplines using:

To show that it works, lets run an PING test. On computer node-1 (the computer where tc is NOT used) run:

To delete the above queue discipline use the delete command instead of replace:

iptables allows you to create rules that specify how packets coming into your computer and going out of your computer are treated (and for routers, also forwarded by the router). The rules for packets coming in are in the INPUT chain, packets going out are OUTPUT, and packets forwarded are in the FORWARD chain. We will only use the INPUT chain.

The rules can filter packets based on common packet identifiers (IP addresses, ports, protocol numbers) as well as other matching criteria. We will use a special statistic matching module. For each packet that matches the filter, some action is applied (e.g. DROP the packet, ACCEPT the packet, or some more complex operation).

On computer node-1 (the destination), to view the current set of rules:

There are no rules in either of the three chains. Note that the default policy (if a packet does not match any rule) is to ACCEPT packets.

Now to add a rule to the INPUT chain to drop 25% of incoming packets on computer node-1:

To demonstrate the packet dropping, run another PING test on the source node-0:

Returning to computer node-1, to delete a rule you can use the -D option:

(or you can refer to rules by number, e.g. iptables -D INPUT 1 to delete rule 1 from the INPUT chain).

Alternatively we can specify to drop every n packets, starting from packet p. And we can combine with the standard filtering mechanisms of firewalls to only drop packets belong to a particular source/destination pair or application.

This rule should drop packet 3, 7, 11, …​ for only one of the connections (with destination port 6666).

Here is the output of an iperf3 test at the source node-0. There are 25% packets dropped by the destination (receiver).