TCP Retransmission & Reliability

TCP Retransmission and Reliability

Consider a data transfer divided into numbered segments that the receiver must process in a defined order. The Internet Protocol (IP) delivers these segments using a best-effort model.

A segment can be lost, duplicated, or arrive after a segment sent later. IP does not notify the sender about every loss. The receiver therefore needs a mechanism that tracks sequence numbers, identifies missing data, and causes it to be sent again.

TCP orders the byte stream delivered to the application and uses acknowledgments and sequence numbers to detect gaps. If the connection remains active, TCP retransmission mechanisms can resend segments that the receiver has not acknowledged. They are not an unconditional delivery guarantee because the connection can fail. Their purpose is to detect probable loss and choose when to transmit the data again.

Detecting Loss: The Two Main Triggers for Retransmission

Before TCP can retransmit a lost segment, it first has to realize that the segment is missing. It does not receive explicit notifications from the network saying a packet was dropped. Instead, it must infer the loss based on the acknowledgments (or lack thereof) it receives from the other end. There are two primary signals that trigger this inference.

1. The Slow Path: Retransmission Timeout (RTO)

This is TCP's primary mechanism for detecting a possibly lost segment:

1. For outstanding data, the sender maintains one Retransmission Timer associated with the earliest unacknowledged segment.
2. The sender starts the timer when unacknowledged data exists and no retransmission timer is running, then waits for an ACK.
3. If an ACK covers the earliest data before the timer expires, the sender stops the timer when no data remains in flight, or restarts it for later outstanding data.
4. If the timer expires, the sender retransmits the earliest unacknowledged segment. It applies exponential backoff to the RTO because the cause can be loss, delay, or reordering.

An RTO expiration can indicate loss, substantial delay, reordering, or congestion. The sender retransmits the earliest unacknowledged data and reduces sending according to congestion control. RFC 6298 derives RTO from SRTT and RTTVAR, in simplified form $\text{RTO} = \text{SRTT} + \max(G, 4\times\text{RTTVAR})$. Before an RTT sample exists, the recommended initial RTO is 1 second, and G represents the clock granularity. After expiration the value is backed off, and samples made ambiguous by retransmission should not update RTT. Waiting for the timer can be slow, especially on high-latency networks.

2. The Fast Path: Duplicate Acknowledgments

TCP can also infer loss from a faster pattern of incoming ACKs. This mechanism acts before the RTO expires, but its result remains a heuristic.

TCP uses a cumulative acknowledgment scheme. An ACK with the number $N$ means the receiver has received all bytes up to $N-1$ and is now expecting byte $N$. If segments arrive out of order, the receiver cannot advance the acknowledgment number yet. Instead, it immediately sends another ACK with the unchanged value $N$. This repeated ACK is called a duplicate ACK.

If the sender receives three duplicate ACKs without an intervening ACK that advances the acknowledgment point, it may treat this as evidence of a missing segment and trigger fast retransmission. Later segments may have arrived out of order, but the pattern can also result from duplicated ACKs or reordering. An implementation can limit a false response by using SACK or other information. This trigger is faster than waiting for the full RTO to expire.

Fast Retransmit and Fast Recovery: TCP's Response

Detecting probable loss through three duplicate ACKs activates two related congestion-control algorithms: Fast Retransmit and Fast Recovery. The described variant comes from TCP Reno; current implementations can use other variants while retaining the idea of reacting quickly.

Fast Retransmit

The Fast Retransmit algorithm follows this rule:

Upon receiving the third duplicate ACK, do not wait for the Retransmission Timer to expire. Immediately retransmit the segment beginning at the unchanged acknowledgment point, which is inferred to be missing.

This retransmission can save one RTT of waiting for the RTO. It is called fast because it uses duplicate ACKs before the timer expires.

Fast Recovery

Fast Recovery specifies what to do after Fast Retransmit. Duplicate ACKs indicate that some segments reached the receiver, so the connection is still carrying data. They do not prove that the network is uncongested or that the inferred segment was lost.

Therefore, resetting the congestion window (cwnd) back to 1 MSS, as after an RTO, would reduce throughput more than this signal requires.

Instead, the Fast Recovery algorithm performs the following steps:

1. Multiplicative Decrease: The sender computes $\text{ssthresh} = \max(\text{FlightSize}/2, 2\times\text{SMSS})$, where FlightSize is data in flight and SMSS is the segment size. On the third duplicate ACK it retransmits the missing segment and sets $\text{cwnd} = \text{ssthresh} + 3\times\text{SMSS}$.
2. Temporary Inflation: For each further duplicate ACK, the sender temporarily increases $\text{cwnd}$ by SMSS. This allows new segments to be sent while the receiver confirms ranges already received.
3. Resume Congestion Avoidance: After an ACK acknowledges previously unacknowledged data from the recovery episode, the sender reduces $\text{cwnd}$ to $\text{ssthresh}$ and resumes linear growth in Congestion Avoidance.

Together, Fast Retransmit and Fast Recovery can repair a single missing segment without waiting for the RTO. The formula describes the classic RFC 5681 variant, and FlightSize means actual data in flight rather than the cwnd value itself. SMSS is the sender's segment size used by the congestion algorithm. The time depends on RTT, segment ordering, acknowledgments, and the congestion-control implementation.

The Limitation of Cumulative ACKs and The Solution: SACK

Fast Retransmit and Fast Recovery work well for a single loss, but they have limitations when multiple segments are lost from one transmitted data window.

The Multiple Packet Loss Problem

Consider a transfer of 10 segments. Segments 3 and 6 are lost, while the receiver gets segments 1, 2, 4, 5, 7, 8, 9, and 10. With cumulative acknowledgments, the receiver can report only that it is still waiting for segment 3.

The sender may receive three duplicate ACKs for segment 3 and perform Fast Retransmit. Only after segment 3 arrives again can the receiver acknowledge through segment 5 and indicate that it is waiting for segment 6. In this simplified Reno case, information about the second loss arrives after another RTT, so recovering two segments takes about two RTTs. The result depends on the duplicate-ACK threshold, window size, and whether the receiver buffers out-of-order data.

Selective Acknowledgment (SACK) for Multiple Losses

To reduce this delay, TCP was extended with Selective Acknowledgment (SACK). Both endpoints must negotiate SACK-Permitted in the initial SYN and SYN-ACK segments.

After negotiation, the receiver continues to send a cumulative ACK and can add SACK blocks to the TCP header options. Each block lists the starting and ending sequence numbers of a contiguous range of data that has been received successfully. The left edge is the first sequence number in the range, while the right edge is the sequence number after its end. The option itself does not retransmit data; the sender uses the blocks to select segments and retains the RTO timer as a safeguard.

How SACK Works in Practice

Let us revisit our example with SACK enabled. The sender ships segments 1-10. Segments 3 and 6 are lost.

1. The receiver gets segments 1 and 2. It sends a normal ACK with Acknowledgment Number for the start of segment 3.
2. The receiver gets segment 4 and detects that segment 3 is missing. It sends a duplicate ACK for the start of segment 3 and a SACK Option reporting the range corresponding to segment 4.
3. The receiver gets segment 5. It sends another duplicate ACK for segment 3 with a SACK option reporting the range 4-5.
4. The sender receives these duplicate ACKs. In classic Fast Retransmit, the third triggers retransmission of segment 3. The sender also processes SACK and knows that segments 4 and 5 arrived, so they do not need retransmission. It marks those ranges as selectively acknowledged in its data structures.
5. The receiver then gets segment 7. It sends another duplicate ACK for segment 3, with the SACK option reporting ranges 4-5 and 7.
6. From this information, the sender knows that segment 3 needs retransmission, while segments 4, 5, 7, and later segments arrived. Segment 6 is the remaining missing segment in this example. The sender can retransmit it without waiting for another RTT if its recovery algorithm permits.

SACK reports received ranges to the sender, which can identify multiple missing segments without waiting for a separate acknowledgment for each retransmission. The benefit depends on the window size, RTT, option-space limits, and congestion-control algorithm. SACK blocks consume header space, so their number depends on the available options area. If an ACK carrying a block is lost, range discovery can be delayed, so the RTO timer remains necessary. It remains useful on networks with frequent segment loss.