A Conservative Selective Acknowledgment (SACK)-based Loss Recovery Algorithm for TCP
obsoleted by
- rfc-6675 — A Conservative Loss Recovery Algorithm Based on Selective Acknowledgment (SACK) for TCP
Extracted elements (21)
Implementers MAY optionally re-arm the RTO timer on each retransmission sent during recovery (rather than only on cumulative ACK advancement per RFC 2988). This prevents premature RTO expiry during long recovery phases that keep the ACK clock active, at the cost of a more conservative timer.
Rule 3 of NextSeg() is included as a 'last resort' to sustain the ACK clock when no definitely-lost or unsent data is available. The authors expect it to trigger rarely; they leave the decision to use it to implementors because it risks underestimating Pipe when both copies of a retransmitted segment leave the network.
The Pipe variable enables a fundamentally different congestion window management from standard RFC 2581: rather than counting packets in flight by ACK arrival, it estimates in-network bytes using SACK state, allowing the sender to inject new data into gaps during recovery without over-filling the network.
Scoreboard information for sequence numbers above the new HighACK SHOULD NOT be cleared when exiting loss recovery on a cumulative ACK beyond RecoveryPoint, preserving SACK state for potential subsequent recovery events.
The first and second duplicate ACKs (before DupThresh is reached) may be used to trigger Limited Transmit (RFC 3042) transmission of previously unsent segments; this is compatible with and complementary to the SACK recovery algorithm.
During recovery, if cwnd - pipe >= 1 SMSS the sender SHOULD transmit one or more segments by querying NextSeg(); each sent segment increments pipe and updates HighRxt or HighData as appropriate; step C repeats until cwnd - pipe < 1 SMSS or NextSeg() fails.
NextSeg() MUST return the smallest unSACKed sequence S2 that is above HighRxt, below the highest SACK-covered octet, and for which IsLost(S2) is true (rule 1); if none exists, MUST return the next unsent data if the window allows (rule 2); MUST indicate failure if neither rule applies.
Rule 3 of NextSeg() MAY return a segment meeting rules (1.a) and (1.b) but not (1.c) as a 'last resort' retransmission to sustain the ACK clock and avoid RTO, but this is left to implementor discretion.
SACKed data MUST NOT be removed from TCP's retransmission buffer until the data is cumulatively acknowledged, because SACK information is advisory and a receiver may renege.
Scoreboard's Update() SHOULD continue to be applied to arriving ACKs during slow-start after RTO, so that all available receiver information is used even though prior SACK state was expunged.
SetPipe() MUST traverse sequence space from HighACK to HighData and set Pipe to the estimated number of octets in transit: incrementing for each un-SACKed octet not determined lost, and again for each octet at or below HighRxt (retransmitted octets are thus counted twice).
Upon an RTO during loss recovery, RecoveryPoint MUST be set to HighData and its new value preserved; the current loss recovery algorithm MUST be terminated; a new recovery phase MUST NOT be initiated until HighACK >= new RecoveryPoint.
Upon an RTO, the sender SHOULD expunge SACK information (per RFC 2018) since the receiver may have reneged, but SHOULD still use SACK information that arrives during the subsequent slow-start recovery phase to guide retransmissions.
Upon receipt of any ACK containing SACK information, the scoreboard MUST be updated via Update().
When a TCP sender receives the DupThresh-th duplicate ACK and no prior loss event has occurred (or HighACK is beyond RecoveryPoint), loss recovery SHOULD be initiated: set RecoveryPoint = HighData, reduce ssthresh = cwnd = FlightSize/2, retransmit HighACK+1, run SetPipe(), and proceed to step C.
DupThresh holds the number of duplicate ACKs required to trigger retransmission; per RFC 2581 this is 3. Implementers should consult RFC 2581 updates for the current value or method.
Four sender-side variables track recovery state: HighACK (highest cumulatively ACKed byte), HighData (highest sequence number transmitted), HighRxt (highest sequence number retransmitted during current recovery), and Pipe (estimate of bytes outstanding in the network).
IsLost(SeqNum) returns true when either DupThresh discontiguous SACKed sequences have arrived above SeqNum, or (DupThresh * SMSS) bytes with sequence numbers greater than SeqNum have been SACKed; otherwise false.
The scoreboard is a per-connection data structure that stores incoming SACK information, tracking which octets have been cumulatively ACKed or SACKed. It exposes Update(), IsLost(), SetPipe(), and NextSeg() operations.
The SACK-based algorithm is more robust than pure duplicate-ACK counting against attackers forging duplicate ACKs to force cwnd reduction: SACK provides an additional check on ACK legitimacy, though it is not fool-proof.
Loss recovery phase: entered on DupThresh duplicate ACKs (if HighACK <= RecoveryPoint check passes); terminated when a cumulative ACK arrives for a sequence number greater than RecoveryPoint. During recovery, each ACK triggers Update(), SetPipe(), and conditional retransmission via NextSeg() when cwnd - pipe >= 1 SMSS.