Fast Retransmit

In the intricate dance of TCP communication, duplicate acknowledgments serve as one of the most elegant and powerful signaling mechanisms ever devised in protocol design. Unlike explicit error messages or timeout-based detection, duplicate ACKs represent an implicit signal—a pattern that emerges naturally from TCP's cumulative acknowledgment semantics when segments arrive out of order or are lost entirely.

Understanding duplicate ACKs is not merely academic; it is foundational to comprehending modern TCP's ability to achieve high throughput over networks with non-negligible loss rates. The fast retransmit mechanism, which we will explore throughout this module, relies entirely on the correct interpretation of duplicate ACKs. Before we can understand how TCP responds to these signals, we must first understand precisely what they are, how they are generated, and what information they encode.

To understand duplicate ACKs, we must first establish a rigorous understanding of TCP's acknowledgment semantics. TCP uses cumulative acknowledgments—a design choice with profound implications for both simplicity and loss detection.

The Cumulative ACK Principle:

When a TCP receiver sends an acknowledgment with acknowledgment number N, it is asserting:

"I have successfully received and buffered all bytes up to and including byte N-1. I am now expecting byte N."

This is fundamentally different from selective acknowledgments, where each received segment is acknowledged individually. Cumulative ACKs reduce overhead (one number covers many segments) but create ambiguity when segments arrive out of order or are lost.

Sequence Number Mechanics:

TCP numbers each byte of data with a 32-bit sequence number. When a sender transmits a segment containing bytes 1000-1499 (500 bytes of data), the segment carries:

• Sequence Number = 1000 (first byte in segment)
• Implicit: last byte is 1499

When the receiver successfully receives this segment (assuming all prior bytes were received), it responds with:

• Acknowledgment Number = 1500 (expecting byte 1500 next)

The acknowledgment number always points to the next expected byte, not the last received byte. This distinction matters when analyzing duplicate ACKs.

The Acknowledgment Invariant:

A properly functioning TCP receiver maintains the following invariant:

ACK_number = min(sequence_number_of_first_missing_byte,
                 sequence_number_of_next_byte_after_last_received)

In simpler terms: the ACK number is always the sequence number of the first "gap" in the received data stream. If there are no gaps (all data contiguous), it's simply the next expected byte. If there is a gap (a missing segment), the ACK number cannot advance past the gap until the missing data arrives.

This invariant is the foundation of why duplicate ACKs occur.

A duplicate acknowledgment is an acknowledgment that carries the same acknowledgment number as a previously sent acknowledgment. But this simple definition masks significant nuance.

Formal Definition (RFC 5681):

A duplicate ACK is an ACK that acknowledges the same segment of data as previously acknowledged. For this purpose, a segment is considered a duplicate ACK if:

1. The ACK does not change the receiver's advertised window
2. The ACK carries no data
3. The ACK carries no SYN or FIN flag
4. The ACK number equals a previously sent ACK number

Illustrative Scenario:

Consider the following transmission sequence:

1. Sender transmits segments with sequence numbers: 1000, 1500, 2000, 2500, 3000 (500 bytes each)
2. Segment 1500 (bytes 1500-1999) is lost in the network
3. Receiver gets segment 1000 → sends ACK 1500
4. Receiver gets segment 2000 → expected 1500, got 2000 → sends ACK 1500 (duplicate!)
5. Receiver gets segment 2500 → still expecting 1500 → sends ACK 1500 (duplicate!)
6. Receiver gets segment 3000 → still expecting 1500 → sends ACK 1500 (duplicate!)

The receiver cannot advance its ACK number past 1500 because bytes 1500-1999 are missing. Each subsequent out-of-order segment triggers another duplicate ACK.

The Counter-Intuitive Nature of Duplicate ACKs:

Duplicate ACKs represent a positive signal disguised as repetition. Each duplicate ACK tells the sender:

1. The receiver is alive — It's still processing incoming segments
2. Segments are arriving — The network path is working (at least partially)
3. There's a gap — Some earlier segment didn't arrive
4. Later segments did arrive — The gap is being "bookended"

This is significantly more information than a timeout provides. A timeout only tells you "something went wrong." Duplicate ACKs tell you what went wrong and prove the network is still functional.

Understanding when and why a receiver generates duplicate ACKs is critical for both implementing TCP correctly and debugging network issues. The receiver's behavior is governed by RFC 5681 and reflects a careful balance between responsiveness and efficiency.

Mandatory Behavior (RFC 5681, Section 3.2):

A TCP receiver SHOULD send an immediate duplicate ACK when an out-of-order segment arrives.

Note the RFC language: SHOULD, not MUST. This means implementations are strongly encouraged to send immediate duplicate ACKs but are not strictly required to do so. In practice, all modern TCP stacks follow this guidance.

The Immediacy Requirement:

Unlike normal ACKs, which may be delayed (typically up to 200ms or 2 segments) to reduce overhead, duplicate ACKs must be sent immediately. This immediacy is crucial because:

1. Time sensitivity — Each duplicate ACK helps the sender detect loss faster; delays reduce the benefit
2. Counting accuracy — The sender counts duplicate ACKs; delayed ACKs could coalesce and reduce the count
3. RTT impact — The sender may be estimating RTT; delayed ACKs distort these estimates

The Linux kernel, for example, bypasses its delayed ACK mechanism entirely when generating duplicate ACKs, sending them immediately via tcp_send_ack().

One of TCP's fundamental challenges is distinguishing between packet reordering and packet loss. Both conditions generate duplicate ACKs, but the appropriate response differs dramatically:

• Reordering: The "missing" segment will arrive shortly; retransmitting wastes bandwidth
• Loss: The segment is gone; retransmission is essential for progress

This ambiguity is why TCP uses a threshold approach rather than reacting to a single duplicate ACK.

The Magic Number: Three Duplicate ACKs

TCP's fast retransmit algorithm uses three duplicate ACKs as the threshold for assuming loss. But why three? This isn't arbitrary; it reflects empirical analysis of network behavior:

Mathematical Justification:

Consider a network with reordering distance d—the maximum number of segments by which a packet may be delayed relative to others. If a segment is reordered by d positions:

• d out-of-order segments arrive before the delayed segment
• Each generates 1 duplicate ACK
• Total: d duplicate ACKs from reordering alone

Studies of real networks (including those by Paxson and others) found that d ≤ 2 covers the vast majority of reordering events. Setting the threshold at 3 provides a safety margin:

• 1 dup ACK: Almost certainly reordering
• 2 dup ACKs: Very likely reordering
• 3 dup ACKs: Probably loss (false positive rate acceptable)

The threshold is a tradeoff: too low causes spurious retransmissions; too high delays legitimate recovery.

To deeply understand duplicate ACKs, let's develop a formal model that relates the number of duplicate ACKs to network conditions and sender behavior.

Variables:

• W = Sender's congestion window (in segments)
• n = Number of segments in flight when loss occurs
• k = Position of lost segment (1st, 2nd, 3rd, etc.)
• D = Number of duplicate ACKs generated

Theorem: Duplicate ACK Count

For a single lost segment at position k in a flight of n segments:

D = n - k

Each segment after the lost segment triggers exactly one duplicate ACK (assuming no additional losses).

Proof:

Let the sender transmit segments with sequence numbers S₁, S₂, ..., Sₙ. Let segment Sₖ be lost.

1. Receiver gets S₁, S₂, ..., Sₖ₋₁ in order → ACKs advance normally
2. Receiver expects Sₖ but receives Sₖ₊₁ → Gap detected → Dup ACK #1
3. Receiver expects Sₖ but receives Sₖ₊₂ → Dup ACK #2
4. ...
5. Receiver expects Sₖ but receives Sₙ → Dup ACK #(n-k)

Total duplicate ACKs: n - k

Corollary:

The earliest segment in a flight that can generate 3 duplicate ACKs is segment n - 3 + 1 = n - 2 (the third-to-last segment). If the last or second-to-last segment is lost, fast retransmit cannot trigger—the sender must wait for timeout.

Extended Model: Multiple Losses

When multiple segments are lost (common during congestion events), the analysis becomes more complex:

Let segments at positions k₁ < k₂ < ... < kₘ be lost from a flight of n segments.

First Lost Segment:

• Generates k₂ - k₁ - 1 dup ACKs (from segments between first and second loss)
• Plus n - kₘ dup ACKs (from segments after last loss)
• Total for first loss: (k₂ - k₁ - 1) + (n - kₘ)

This quickly becomes insufficient for fast retransmit when losses are clustered together—a key limitation that selective acknowledgment (SACK) addresses.

Understanding duplicate ACKs conceptually is essential, but recognizing them in real packet captures is a critical skill for network debugging and performance tuning. Let's examine how duplicate ACKs appear in practice.

Wireshark Identification:

Wireshark automatically detects and labels duplicate ACKs using its TCP stream analysis. It tracks ACK numbers per stream and flags any ACK that matches a previously seen ACK number (with the additional RFC 5681 criteria).

Key Indicators in Packet Captures:

Distinguishing True Duplicates from Similar ACKs:

Not all repeated ACK numbers are duplicate ACKs in the RFC sense:

Wireshark's heuristics generally handle these cases correctly, but understanding the distinction is crucial for manual analysis.

Implementing correct duplicate ACK generation and handling requires attention to subtle details. Both receiver-side generation and sender-side counting have implementation pitfalls.

Receiver Implementation Requirements:

Sender Implementation Requirements:

Duplicate ACKs are far more than a curiosity of TCP behavior—they are the essential signaling mechanism that enables TCP to recover from loss without the catastrophic delays of timeout-based recovery. Let's consolidate our understanding:

What's Next:

With a thorough understanding of duplicate ACKs in place, we're ready to explore how TCP uses this signal. The next page covers the retransmission trigger—the precise algorithm by which TCP converts the observation of three duplicate ACKs into a fast retransmit action, bypassing the potentially lengthy retransmission timeout.