TCP Fast Recovery

In the landscape of TCP congestion control, the Fast Recovery phase represents one of the most significant algorithmic innovations in the protocol's evolution. While Fast Retransmit (covered in Module 1) enables TCP to detect and respond to packet loss without waiting for expensive timeout events, it was the introduction of Fast Recovery that truly transformed TCP's ability to maintain high throughput in the face of transient network conditions.

To fully appreciate Fast Recovery's importance, we must first understand the problem it was designed to solve. Before its introduction, even when TCP could quickly detect loss through duplicate ACKs, the sender's response was devastatingly conservative: it would reset the congestion window (cwnd) to 1 MSS and restart slow start from scratch. This behavior, while safe, was deeply inefficient on networks where packet loss events were typically isolated incidents rather than indicators of severe congestion collapse.

Fast Recovery is a congestion control mechanism that allows TCP to maintain relatively high throughput during and after packet loss events by avoiding the costly return to slow start. Introduced as part of TCP Reno, Fast Recovery fundamentally changed how TCP responds to detected packet loss.

The Core Insight:

The key insight behind Fast Recovery is deceptively simple yet profoundly impactful: when duplicate ACKs arrive at the sender, they indicate that packets are still successfully reaching the receiver. Each duplicate ACK confirms that:

1. At least one packet has left the network (arrived at receiver)
2. The network path is still functioning
3. Only specific packets appear to be lost, not the entire pipe

This observation leads to a critical realization: if data is still flowing through the network, perhaps severe congestion window reduction isn't necessary. Instead of assuming catastrophic congestion and restarting from scratch, TCP can reduce its sending rate more moderately and continue transmitting.

Understanding Fast Recovery requires viewing TCP's congestion control as a state machine with well-defined transitions. The Fast Recovery phase is one such state, entered under specific conditions and exited when recovery completes or fails.

State Machine Overview:

TCP congestion control operates in one of several states:

• Slow Start: Initial exponential growth phase
• Congestion Avoidance: Linear growth after reaching threshold
• Fast Recovery: Loss recovery without slow start penalty

The transitions between these states are triggered by specific events: acknowledgments, timeouts, and duplicate ACKs.

Entry Conditions for Fast Recovery:

TCP enters the Fast Recovery phase when the following conditions are met:

1. Three Duplicate ACKs Received: The sender receives three acknowledgments for the same sequence number (four identical ACKs total including the original).

2. Fast Retransmit Triggered: Immediately upon receiving the third duplicate ACK, TCP performs Fast Retransmit of the presumed lost segment.

3. Threshold Adjustment: Before entering Fast Recovery, TCP sets the slow start threshold (ssthresh) to half of the current flight size.

4. Window Inflation: The congestion window is set to ssthresh plus 3×MSS (accounting for the three duplicate ACKs already received).

Once TCP enters the Fast Recovery phase, its behavior changes significantly from normal congestion avoidance. The primary goal during this phase is to maintain the 'ACK clock' - the self-clocking mechanism that paces TCP transmission based on acknowledgment arrival.

ACK Clock Preservation:

The ACK clock is TCP's natural pacing mechanism. When packets arrive at the receiver, they trigger ACKs that travel back to the sender. These incoming ACKs permit the sender to transmit new data. This creates a self-regulating feedback loop that naturally adapts to network conditions.

During Fast Recovery, maintaining this clock is critical. Each duplicate ACK, while not acknowledging new data, does indicate that one segment has left the network and been received. This information is used to 'inflate' the congestion window temporarily.

The Window Inflation Rationale:

Window inflation during Fast Recovery may seem counterintuitive at first. Why increase cwnd when we've just detected a loss? The answer lies in understanding what the congestion window actually represents.

The cwnd limits the number of bytes that can be outstanding (unacknowledged) in the network. When a duplicate ACK arrives, it signals that a previously transmitted packet has reached the receiver and is now buffered there (otherwise, no ACK would be generated). This packet has effectively 'left the network' from the sender's perspective.

By incrementing cwnd, TCP compensates for this reduction in outstanding bytes, allowing new data to be transmitted. The total bytes in the network (flight size) remains roughly constant while recovery proceeds.

Fast Recovery is a transient phase - TCP must eventually exit it. There are two possible exit paths, each with dramatically different implications for subsequent behavior.

Exit Condition 1: Successful Recovery (New ACK)

The desired exit from Fast Recovery occurs when TCP receives an ACK that acknowledges new data - specifically, data at or beyond the sequence number that was retransmitted. This 'new ACK' indicates that:

1. The retransmitted segment has been successfully received
2. All segments up to that point have been delivered
3. The network has recovered from whatever condition caused the loss

Upon receiving a new ACK, TCP performs 'window deflation' and transitions to Congestion Avoidance.

Exit Condition 2: Recovery Failure (Timeout)

If Fast Recovery fails - meaning the retransmitted segment is also lost, or multiple segments need retransmission - the sender will eventually experience a retransmission timeout (RTO). This timeout triggers the most conservative response:

1. ssthresh reduction: Set to half of the current flight size (may already be set from Fast Recovery entry)
2. cwnd reset: Congestion window drops to 1 MSS
3. Slow Start restart: TCP returns to the slow start phase and must exponentially grow cwnd from scratch

This represents a significant performance penalty and highlights why Fast Recovery's success is crucial for maintaining throughput.

Understanding the difference between Fast Recovery and Slow Start is essential for appreciating why Fast Recovery was such a significant advancement. Both phases involve managing the congestion window, but their philosophies and impacts are fundamentally different.

Slow Start's Approach:

Slow Start begins with an extremely conservative assumption: we know nothing about the network's capacity. Starting from cwnd = 1 MSS (or a small initial value), the sender doubles cwnd for each RTT. While 'slow' is a misnomer (it's actually exponential growth), the starting point is so low that reaching full capacity can take many RTTs.

Fast Recovery's Approach:

Fast Recovery assumes the network was recently working at a known capacity (the cwnd before loss detection) and that isolated losses don't indicate complete congestion collapse. It halves the rate (ssthresh = cwnd/2) but maintains transmission during recovery, then immediately resumes from that halfway point in Congestion Avoidance.

Quantifying the Difference:

Consider a TCP connection that was operating with cwnd = 64 MSS before detecting a loss:

With Slow Start (Tahoe-style response):

• cwnd drops to 1 MSS
• After 1 RTT: cwnd = 2 MSS
• After 2 RTTs: cwnd = 4 MSS
• After 3 RTTs: cwnd = 8 MSS
• After 6 RTTs: cwnd = 64 MSS (back to original)
• Total recovery: 6+ RTTs

With Fast Recovery (Reno-style response):

• ssthresh = 32 MSS, cwnd = 35 MSS (32 + 3)
• Recovery completes in ~1 RTT (upon new ACK)
• cwnd deflates to 32 MSS
• Connection continues at ~50% of original rate immediately

For a network with 100ms RTT, Slow Start recovery costs 600+ ms. Fast Recovery costs approximately 100ms. This difference is significant for user-perceived performance and overall throughput.

One of Fast Recovery's most elegant aspects is how it leverages TCP's self-clocking mechanism to maintain flow during the recovery process. This self-clocking, also known as 'ACK-clocking,' is fundamental to understanding why Fast Recovery works.

The Self-Clocking Principle:

TCP's transmission rate is naturally regulated by the acknowledgment stream. When a packet arrives at the receiver, an ACK is generated and sent back. Only when an ACK arrives at the sender can new data be transmitted (within cwnd limits). This creates a natural feedback loop:

1. Packets leave sender at rate limited by cwnd
2. Packets traverse network with inherent delay
3. Packets arrive at receiver, triggering ACKs
4. ACKs traverse network back to sender
5. ACKs permit new data transmission

This cycle creates a steady-state where the transmission rate automatically matches the network's capacity - the 'ACK clock' paces the sender.

Why Self-Clocking Matters During Fast Recovery:

When packet loss occurs, the self-clocking mechanism is at risk of breaking down. Without incoming ACKs, the sender cannot transmit new data. The network pipeline begins to drain, and if not carefully managed, the connection could stall.

Fast Recovery preserves the clock through window inflation:

1. Duplicate ACKs as Clock Ticks: Each duplicate ACK indicates a packet reached the receiver. Even though it doesn't acknowledge new data, it represents a 'clock tick' - proof that the path is functioning.

2. Window Inflation Permits Transmission: By increasing cwnd with each duplicate ACK, Fast Recovery creates room to send new data. This new data will generate future ACKs, keeping the clock running.

3. Recovery Point Tracking: TCP tracks the highest sequence number sent when recovery began. Only ACKs beyond this point indicate full recovery.

4. Continuous Flow: Throughout recovery, data continues flowing in both directions - retransmissions, new data (if cwnd permits), duplicate ACKs, and eventually new ACKs.

A critical concept in Fast Recovery is the recovery point - the sequence number that marks the boundary between the 'lost segment region' and segments transmitted during recovery. Understanding this boundary is essential for correct recovery behavior.

Defining the Recovery Point:

When TCP enters Fast Recovery, it records the highest sequence number that has been transmitted:

recovery_point = SND.NXT - 1

This recovery point serves as a threshold. Only when TCP receives an ACK acknowledging data at or beyond this point can it conclude that recovery is complete. This ensures that:

1. All segments outstanding when loss was detected have been acknowledged
2. The retransmitted segment has been received
3. The receiver has successfully reconstructed the stream up to the recovery point

The Partial ACK Problem:

A partial ACK occurs when the receiver acknowledges some new data but not all data up to the recovery point. This typically indicates that multiple segments were lost in the same window of data.

Consider this scenario:

• Sender has transmitted segments 1-10
• Segments 3 and 7 are lost
• Receiver gets 1, 2, then 4-6, 8-10
• Duplicate ACKs trigger Fast Recovery
• Sender retransmits segment 3
• Receiver gets segment 3, sends ACK for sequence up to segment 6
• This is a partial ACK (expected ACK was for segment 10)

In TCP Reno, partial ACKs cause the sender to exit Fast Recovery, deflate cwnd, then immediately detect another loss and re-enter Fast Recovery. This inefficiency was addressed in later TCP variants.

Improved Partial ACK Handling (NewReno Preview):

TCP NewReno introduced improved partial ACK handling that stays in Fast Recovery when receiving partial ACKs:

1. Immediately retransmit the next unacknowledged segment
2. Deflate cwnd by the amount of data acknowledged
3. Add back 1 MSS (for the segment that left the network)
4. Remain in Fast Recovery until a full ACK is received

This approach prevents multiple ssthresh halvings and provides more efficient recovery from multiple losses. We'll explore this in detail in the Reno implementation page.

The Fast Recovery phase represents a fundamental advancement in TCP congestion control, enabling networks to maintain high utilization even in the presence of transient packet loss. Let's consolidate the key concepts covered:

What's Next:

With the Fast Recovery phase mechanism understood, we'll explore how TCP responds to congestion signals during and after recovery. The next page examines the congestion response strategies that determine how aggressively TCP reduces its sending rate.