Duplicate Acknowledgements and How a Sender Distinguishes Loss from Reordering

A TCP receiver is required to acknowledge in order. When segment 1000 arrives but the segment starting at 500 is missing, the receiver cannot advance its acknowledgement number past 500, so it sends another ACK with the same number. The sender receives an ACK that acknowledges nothing new, and that duplicate is the only signal it gets. From the sender’s side, a duplicate ACK could mean the data after the hole arrived and the hole is lost, or it could mean the data after the hole arrived before the hole did and the hole is merely late. The two cases are indistinguishable from the acknowledgement number alone, and the algorithm’s response to each is opposite: retransmit, or wait.

Fast retransmit resolves the ambiguity with a count. A single duplicate ACK is normal under reordering. Several duplicates arriving in succession mean several segments after the hole have been delivered, which is evidence that the hole is not merely delayed by a small amount — if it were, it would have arrived interleaved with the others. Three duplicates is the threshold, and it is a heuristic chosen from observation of how much reordering real paths exhibit, not a value derived from any property of the network.

The mechanics of the third duplicate

The sender keeps SND.UNA, the first unacknowledged byte. On receiving an ACK:

• If the acknowledgement number advances past SND.UNA, new data was acknowledged. Reset the duplicate counter, and if a recovery episode is in progress, handle the partial acknowledgement.
• If the acknowledgement number equals SND.UNA and the advertised window is unchanged, increment the duplicate counter. The segment carries no new information about delivery, but it does carry evidence that something left the network.
• On the third duplicate, retransmit the segment at SND.UNA without waiting for the retransmission timer, and enter fast recovery.

The retransmission timer is the fallback, and it is expensive. A timeout collapses the congestion window to one segment, discards the ssthresh estimate, and restarts slow start. A fast retransmit halves the window and continues in congestion avoidance, which is far cheaper. The whole point of the duplicate-ACK mechanism is to convert a timeout into a fast retransmit as often as possible, and its efficiency depends entirely on how often three duplicates actually arrive.

The count of three is not arbitrary in one respect: each duplicate ACK proves that a segment left the network and was delivered. If the sender holds its window constant while duplicates arrive, it is receiving permission to send new data. Reno’s fast recovery exploits this by inflating the window by one segment per duplicate ACK, so the sender can keep transmitting during the recovery episode without going idle. That inflation is why fast recovery is sometimes described as “conserving” the window: the sender’s in-flight estimate stays at the pre-loss level minus one, which is the amount it believes the network can still hold.

The Reno fast recovery episode

The sequence for a single loss in a window is:

1. Third duplicate arrives. Set ssthresh = max(FlightSize / 2, 2*SMSS). Retransmit the lost segment. Set cwnd = ssthresh + 3*SMSS, the three segments being the ones that generated the duplicates and therefore left the network.
2. Each further duplicate increments cwnd by one segment and, if the window permits, sends new data.
3. When an ACK arrives that acknowledges the retransmitted segment, exit recovery: set cwnd = ssthresh and continue in congestion avoidance.

Step 3 is where the single-loss assumption lives. The acknowledgement that ends recovery covers the hole and everything contiguous after it. If a second segment was lost in the same window, the acknowledgement will stop short of it, and the sender that exits recovery at that point has thrown away the information that it is still in a loss episode. It will then wait for three more duplicates on the new hole, which may never arrive because the window has been reduced, and eventually time out.

NewReno fixes this with a partial acknowledgement rule. During recovery the sender remembers the highest sequence number sent at the time recovery began, the recovery point. An ACK that advances SND.UNA but does not reach the recovery point is a partial acknowledgement: it proves another segment was lost. The sender retransmits the segment at the new SND.UNA, deflates the window by the amount of newly acknowledged data, adds one segment back if the ACK covered at least a full segment, and stays in recovery. Only an ACK that reaches the recovery point ends the episode. This turns one recovery episode per lost segment into one episode per window, at the cost of one retransmission per round trip during recovery.

/* Partial-ACK handling inside NewReno recovery (RFC 6582). */
if (in_recovery) {
    if (before(ack, recover_point)) {
        uint32_t newly = ack - snd_una;
        /* Partial ACK: another hole. Retransmit it and keep recovering. */
        snd_una = ack;
        cwnd = cwnd > newly ? cwnd - newly : 0;   /* deflate by what was acked */
        if (newly >= smss)
            cwnd += smss;               /* one segment may have left the network */
        retransmit(snd_una);
    } else {
        /* Full ACK: the episode is over. */
        snd_una = ack;
        cwnd = ssthresh;
        in_recovery = 0;
    }
}

The retransmission per round trip is the cost. NewReno recovers from k losses in one window in about k round trips, which is better than the k separate episodes Reno would need but worse than the one round trip that selective acknowledgement makes possible.

What selective acknowledgement changes

A SACK option reports the blocks the receiver holds above the cumulative acknowledgement, as a sequence of left and right edges. RFC 2018 defines the option, and the sender can then know exactly which segments are missing rather than inferring one hole at a time.

With SACK the sender maintains a scoreboard: the set of segments it believes are still outstanding. Each SACK block marks a range as delivered. The retransmission decision becomes a search for the lowest unacknowledged segment, and the recovery episode retransmits every hole the scoreboard shows rather than one per round trip. RFC 6675 specifies a conservative algorithm that avoids marking segments lost on insufficient evidence, using a notion of how many bytes are known to have left the network.

The gain is largest exactly where Reno fails worst: a window that loses many segments at once, which happens when a burst overflows a buffer or when a link drops a run of packets. With Reno or NewReno that event costs several round trips and a full window reduction for each partial ACK; with SACK it costs one round trip of retransmissions and one window reduction.

SACK also changes what “three duplicates” means. A SACK-enabled receiver reports each new block, so the sender sees which ranges above the hole have arrived rather than only that something has, and it can retransmit every hole the scoreboard shows without waiting for three further duplicate ACKs for each one. The three-duplicate threshold remains as a floor because the sender still cannot distinguish a single reordered segment from a loss on the first duplicate alone.

The option is limited to 40 bytes of TCP header space, of which the option kind and length consume two, leaving room for four blocks under the common encoding. A receiver with more holes than blocks reports the most recent ones, so the sender’s scoreboard is always partial. That limit is why implementations must handle “the scoreboard says nothing is missing but the cumulative acknowledgement has not advanced” as a real state, resolved by the retransmission timer.

Reordering is not loss

Every duplicate-ACK heuristic is a bet that reordering is rarer than loss. The bet is usually good on the public internet and bad on paths with parallelism. A router that load-balances across equal-cost links, a wireless link that retransmits at layer two, or a receiver that delivers from multiple queues can reorder segments by more than three positions routinely.

When reordering exceeds the threshold, the sender retransmits a segment that was merely late. The retransmission is wasted capacity, and worse, it triggers a window halving for a loss that did not happen. On a path with persistent reordering, this produces a steady state in which the congestion window is halved by phantom losses faster than additive increase can restore it, and throughput settles at a fraction of capacity.

The standard remedy is to make the threshold adaptive. If the sender tracks how much reordering it has observed, it can require more duplicates before declaring a loss. Linux keeps a per-connection reordering estimate and raises it when a retransmission turns out to have been unnecessary, bounded by a configurable maximum, so a path that reorders persistently is eventually granted a larger threshold. The cost is latency on genuine losses, since a higher threshold delays the retransmission by that many segments’ worth of time.

The deeper problem is that no threshold resolves the ambiguity, it only moves the error rate. A sender that waits for k duplicates misses losses that produce fewer than k segments after the hole, which happens whenever the window is small or the loss is near the end of the window. A sender that acts on one duplicate retransmits spuriously under mild reordering. The three-duplicate value is a compromise that misclassifies in both directions, and the mechanisms that improve on it — timestamp-based RTT measurement, SACK-based detection, and the receiver-side duplicate suppression that some stacks perform — all work by gathering evidence other than the count.

The interaction with the control law

Fast recovery is a recovery mechanism, but it is entangled with congestion control in a way that is easy to miss. The window inflation during recovery assumes that each duplicate ACK corresponds to a segment that left the network. If the duplicates are caused by reordering rather than loss, the segments did leave, so the inflation is still correct. If they are caused by a receiver that acknowledges spuriously, the sender’s in-flight estimate becomes wrong and it oversends.

The halving itself is where the loss signal enters the control loop. A fast retransmit is a multiplicative decrease triggered by a duplicate-ACK count rather than by a timer, and the distinction between the two triggers determines whether the sender halves or collapses. That is the subject of the sawtooth, and it explains why the fraction of losses detected by duplicate ACKs rather than timeouts is the single largest determinant of a loss-based sender’s throughput on a given path.

The recovery point also has a subtle interaction with the window. NewReno’s recovery point is the highest sequence number sent when recovery began, and the sender must not send beyond it during recovery without adjusting. An implementation that forgets this can send data that the recovery episode’s partial-ACK logic then misinterprets, producing either a spurious retransmission or a premature exit from recovery. The rule is that the recovery point is fixed at entry and not updated, which is what makes “has the ACK reached the recovery point” a well-defined test.

Finally, the mechanisms here all assume that the sender’s window is the binding constraint. On a path where the receiver’s advertised window is smaller, the sender is flow-limited rather than congestion-limited, and fast recovery’s window arithmetic has no effect on the rate. The recovery still runs and still retransmits, but the rate does not change, which makes the loss appear free and can mask a persistent problem in the path.