SACK Blocks and the Retransmission Queue

A cumulative acknowledgement says one thing: everything below this number arrived. When a single segment is lost from the middle of a window, the receiver keeps sending the same number, and the sender learns only that the window has not advanced. It cannot tell whether one segment was lost or twenty, whether the loss was at the left edge or near the right, or whether the later segments are sitting in the receiver’s buffer waiting for the hole to be filled.

Recovering from that position with the retransmission timer alone costs one full timeout per loss episode. On a path with a 200 ms round trip, a single loss every few hundred segments would then dominate the connection’s total time. Selective acknowledgement exists to close that gap.

The option that carries ranges

SACK is a TCP option, negotiated in the handshake, that lets a receiver report up to four received ranges that lie above the cumulative acknowledgement. Each block is two 32-bit sequence numbers: the left edge and the right edge of a contiguous run of received bytes. The blocks are ordered so that the most recently received block comes first, which matters for the sender’s ability to infer which segment triggered the acknowledgement.

The option is limited by the TCP header’s 40-byte option space. Two bytes of kind and length plus eight bytes per block gives four blocks in 34 bytes, which is why four is the standard number. A receiver with more than four disjoint holes must choose which to report, and the choice is a policy: report the most recent blocks so the sender learns about fresh arrivals, and let older holes be inferred from the cumulative acknowledgement once they are filled. A sender that ignores this and assumes the report is complete will believe everything not listed is lost, and will retransmit data the receiver already holds.

A SACK block is redundant with the cumulative acknowledgement for the prefix, so the blocks always describe ranges strictly above it. This keeps the representation compact and makes the sender’s parsing uniform: everything below SND.UNA is acknowledged, everything inside a reported block is received, and everything else in the outstanding range is either in flight or lost.

The sender’s scoreboard

The sender maintains a record of which bytes in the outstanding range are known to have arrived. The natural structure is a list of disjoint intervals, and the operations on it are insertion of a new block, merging with adjacent intervals, and advancing the left edge when the cumulative acknowledgement moves.

/* Sender-side scoreboard: a small array of disjoint received ranges above SND.UNA. */
struct range { uint32_t lo, hi; };   /* half-open [lo, hi) */

struct scoreboard {
    struct range r[8];
    int n;
};

/* Returns 0 on success, -1 if the scoreboard is full and the block was dropped. */
static int insert_range(struct scoreboard *s, uint32_t lo, uint32_t hi)
{
    int i = 0;
    while (i < s->n && s->r[i].hi < lo) i++;          /* find first range not entirely below */

    /* Merge with any range that overlaps or touches [lo, hi). */
    while (i < s->n && s->r[i].lo <= hi) {
        if (s->r[i].lo < lo) lo = s->r[i].lo;
        if (s->r[i].hi > hi) hi = s->r[i].hi;
        for (int j = i; j + 1 < s->n; j++) s->r[j] = s->r[j + 1];
        s->n--;
    }
    if (s->n == (int)(sizeof s->r / sizeof s->r[0]))
        return -1;                                    /* caller falls back to cumulative ACKs */

    for (int j = s->n; j > i; j--) s->r[j] = s->r[j - 1];
    s->r[i] = (struct range){ lo, hi };
    s->n++;
    return 0;
}

The merging is the important part. Two SACK blocks that arrive in separate acknowledgements may describe adjacent ranges, and treating them as separate holes would cause a spurious retransmission of the boundary between them. Merging also collapses the scoreboard after a hole is filled, which keeps the structure small even when the receiver reports overlapping blocks.

The scoreboard is not the only record the sender keeps. It also needs to know which segments it has already retransmitted, so that a second report of the same hole does not cause a second copy. The two records are usually combined into a per-segment flag.

Inferring loss from a map

With a scoreboard, loss detection stops being a timer question and becomes a counting question. RFC 6675 defines a predicate over a sequence number and returns lost when either of two conditions holds: at least a threshold number of discontiguous SACKed sequences lie above it, or more than (threshold - 1) × SMSS bytes above it have been SACKed. The threshold is the same value used by the duplicate-acknowledgement rule, conventionally three, and the second condition is the byte-counting generalisation that makes the first one work when segments are not uniformly sized.

The threshold is a judgement about reordering, not about loss. A path that reorders a segment now and then produces one or two out-of-order arrivals, and the rule ignores them. A path that has lost a segment produces a growing set of received segments above the hole, and the third arrival is taken as sufficient evidence that the hole is a loss and not a delay.

Two refinements matter in practice.

The first is the distinction between a loss and a reordering. If the hole is filled shortly after the three segments above it arrive, the “loss” was actually a delayed segment, and the retransmission was spurious. The sender cannot know this in advance. It can only detect it after the fact, when the cumulative acknowledgement jumps past the hole without the retransmission having been needed. The timestamp option, discussed in Timestamps, RTTM, and Protection Against Wrapped Sequences, allows that detection to be reliable rather than heuristic.

The second is the interaction with the congestion window. A SACK-driven recovery can retransmit several segments in one round trip, which is a much more aggressive response than the one-segment-per- round-trip behaviour of the original fast retransmit. RFC 6675 constrains the number of segments that may be outstanding during recovery, and the constraint is expressed in terms of the pipe estimate: the sender’s estimate of how many octets are actually in the network. The procedure walks the sequence space from the highest cumulatively acknowledged byte to the highest byte sent, adding one for each octet that is neither SACKed nor considered lost, and one again for each octet already retransmitted.

The pipe estimate and why it is not the window

During recovery the sender’s notion of “how much can I send” is not the congestion window. The congestion window has already been reduced in response to the loss, but the network still contains the segments that were sent before the reduction. Sending up to the reduced window immediately would double-count the outstanding data.

The pipe estimate resolves this by counting what is actually in flight:

pipe = (SND.NXT - SND.UNA) - SACKed - lost_not_retransmitted + retransmitted

The first term is the outstanding range; the second removes what the receiver reports as received, which stays in the retransmission buffer but is no longer in the network; the third removes holes already judged lost and not yet resent, which are likewise not in flight; and the fourth counts a retransmitted octet again, because a second copy is now travelling. The sender may transmit while pipe < cwnd. This is the mechanism that lets a sender with many holes retransmit several segments in one round trip without exceeding what the network can absorb.

The estimate is approximate, and its errors have consequences. If it undercounts, the sender transmits more than the network can hold and the loss rate rises. If it overcounts, the sender stalls while capacity is idle. It drifts low when an acknowledgement covers a retransmitted octet whose original transmission may still be in the network: the octet is deducted once although two copies may still be travelling. It drifts high when a retransmission is itself lost, because the sender counts it as in flight until the retransmission timer fires or a later SACK shows the hole is still open.

Where SACK does not help

SACK is a receiver-side report, and its usefulness depends on the sender having enough outstanding data to create a map worth reporting. On a connection with a small window, a single loss consumes a large fraction of the outstanding range, and the threshold of three discontiguous SACKed sequences may never be reached. The recovery then falls back to the retransmission timer, and the benefit of the option is nil. This is why SACK is most valuable on long-fat paths, where the window is large and losses are sparse.

The option also requires both sides to support it. A receiver that does not negotiate SACK reports only cumulative acknowledgements, and the sender must use the duplicate-acknowledgement heuristic. The heuristic works, but it cannot distinguish one loss from many, and a sender that retransmits only the segment at the left edge will take one round trip per loss to recover.

Finally, SACK reports received ranges, not lost ones. A sender that infers loss from the absence of a report is making a probabilistic judgement, and the judgement is wrong whenever the network reorders more than the threshold. Paths that reorder systematically, in some multipath and some wireless environments, need the threshold raised or the detection moved to a timestamp-based method, because the default threshold will treat ordinary reordering as loss and reduce the sending rate for no reason. Multipath transports face this problem in a sharper form, since their paths have different delays by construction, as described in Multipath TCP and the Data-Level Sequence Space.