The RACK-TLP Loss Detection Algorithm for TCP
Extracted elements (30)
RACK-TLP intentionally decouples loss detection from congestion control: RACK only detects losses and does not modify the congestion control algorithm. This separation allows congestion control (e.g., PRR) to govern when and how retransmissions occur independently of the loss detection mechanism.
RACK uses a time-based reordering window instead of a packet-distance threshold (DupAck counting) because reordering degree in time is typically bounded within one RTT — whether segments traverse parallel paths with similar delays or are repaired quickly by local link-layer retransmissions — whereas reordering in packet distance can vary up to the full flight size.
The initial RACK reordering window is min_RTT/4 because Linux TCP used the same factor in Early Retransmit [RFC5827] to delay retransmission in the presence of reordering, and operational experience showed this worked well. It is a deliberate adoption of an empirically validated constant.
The RACK reordering window persists for up to 16 loss recoveries before resetting to min_RTT/4. This bounds spurious fast recovery episodes caused by a temporarily inflated window to approximately once every 16 recoveries (less than 7%), balancing adaptation to sustained reordering against unnecessary sensitivity.
The TLP PTO is conservatively set to 2*SRTT rather than 1*SRTT because network and end-host delay variance can delay an ACK beyond one SRTT, and using exactly SRTT would risk spurious probes. 2*SRTT is the next integral multiple of SRTT that provides adequate headroom.
TLP preferentially retransmits the highest-sequence segment (not the lowest unacknowledged) to resolve the retransmission ambiguity problem: any SACK for that segment — whether for the original or the retransmission — equally implies that the N-1 preceding segments were likely lost, so the choice of which copy is irrelevant to RACK's inference.
RACK-TLP can be implemented in other transport protocols. The QUIC loss detection and congestion control draft (draft-ietf-quic-recovery) and the SPROUT algorithm both independently adopted reordering window approaches similar to RACK.
RACK-TLP is compatible with the standard RTO [RFC6298], RTO Restart [RFC7765], F-RTO [RFC5682], and Eifel [RFC3522] algorithms because RACK-TLP detects loss solely via ACK events and does not change the RTO timer calculation or detect spurious RTOs.
A segment marked as lost by RACK-TLP MUST NOT be retransmitted until congestion control deems it appropriate. The PRR algorithm [RFC6937] is RECOMMENDED for the congestion control actions triggered by RACK-TLP loss detections.
After a TLP retransmission, if the sender does not receive a DSACK or DupAck confirming that both the original and probe arrived, it MUST assume that the original segment, the TLP retransmission, or a corresponding ACK was lost, and SHOULD invoke a congestion control response equivalent to fast recovery.
After attempting to send a loss probe — regardless of whether one was actually sent — the sender MUST re-arm the RTO timer (not the PTO timer) if FlightSize is nonzero. This ensures RTO recovery remains the last resort if TLP fails.
For each data segment sent, the sender MUST store its most recent transmission time with a timestamp whose granularity is finer than 1/4 of the connection's minimum RTT. Microsecond resolution is suitable for intra-datacenter traffic; millisecond or finer for the Internet.
RACK DSACK-based reordering window adaptation is RECOMMENDED but not required. TLP requires RACK; TLP cannot operate independently.
The connection MUST use SACK options [RFC2018] and the sender MUST maintain a per-connection SACK scoreboard. These are hard prerequisites for RACK-TLP to function.
The default PTO interval is 2*SRTT. If no SRTT estimate is available, the PTO SHOULD be 1 second. When FlightSize is one segment, the sender MAY inflate the PTO by TLP.max_ack_delay. If the computed PTO would fire after the RTO, the sender schedules TLP at the RTO time instead.
The RACK reordering window MUST be bounded, and this bound SHOULD be SRTT. The window grows linearly each round trip a DSACK is received — (N+1)*min_RTT/4 — up to SRTT, and resets to min_RTT/4 after 16 DSACK-free loss recoveries.
The RACK reordering window SHOULD be set to zero when no reordering has been observed and either three segments have been SACKed since the last recovery or the sender is already in fast or RTO recovery. Otherwise it SHOULD start from min_RTT/4.
The SACK loss recovery algorithm [RFC6675] MUST NOT be used together with RACK-TLP because RFC 6675's NextSeg() does not handle lost retransmissions and does not specify the required additional congestion response for that case.
The sender SHOULD start or restart a TLP PTO timer after transmitting new data or upon receiving a cumulative ACK for new data, unless it is already in fast recovery, RTO recovery, or segments have been SACKed (RACK.segs_sacked != 0).
Upon PTO expiration, the sender MUST verify two conditions before sending a probe: (1) no prior TLP is still in flight (TLP.end_seq is None), and (2) an RTT sample has been obtained since the last probe or connection start. If either condition fails, the sender MUST skip the probe and MUST re-arm the RTO timer.
Per-connection RACK variables include RACK.reo_wnd (adaptive reordering window in time units), RACK.min_RTT (windowed minimum RTT), RACK.rtt (RTT of the most recently delivered non-spurious segment), RACK.reordering_seen, RACK.fack (highest forward-acknowledged sequence), RACK.dsack_round, RACK.reo_wnd_mult, and RACK.reo_wnd_persist.
Per-segment state includes Segment.xmit_ts (time of last transmission, with INFINITE_TS indicating not in flight), Segment.lost (marked for retransmission), and Segment.retransmitted (ever retransmitted). Clock granularity must be finer than 1/4 of min RTT.
RACK marks a segment as lost when RACK.xmit_ts >= Segment.xmit_ts AND (RACK.xmit_ts - Segment.xmit_ts + (now - RACK.ack_ts)) >= RACK.reo_wnd, which simplifies to: now >= Segment.xmit_ts + RACK.rtt + RACK.reo_wnd.
RACK.segment is the segment (among all selectively or cumulatively acknowledged segments) that was sent most recently, including retransmissions. Its transmission timestamp and highest sequence number are tracked in RACK.xmit_ts and RACK.end_seq, and the time it was acknowledged in RACK.ack_ts.
TLP state variables include TLP.is_retrans (whether the outstanding probe is a retransmission), TLP.end_seq (SND.NXT at probe send time, None when no probe is outstanding), and TLP.max_ack_delay (budget for delayed ACK accommodation).
RACK-TLP is not vulnerable to ACK-splitting attacks [SCWA99]: an attacker SACKing only one byte of an MSS-sized segment produces the same RACK.xmit_ts effect as SACKing the entire segment, because all bytes within the segment share the same transmission timestamp, so RACK.xmit_ts does not advance spuriously.
RACK-TLP's behavior depends on information in SACK options and therefore has security considerations similar to those in RFC 6675 Section 5. Attackers that can forge or manipulate SACK options may influence RACK's loss inferences.
The RACK reordering timer, TLP PTO timer, RTO timer, and Zero Window Probe timer are mutually exclusive. When arming a RACK reordering timer or TLP PTO, the sender SHOULD cancel any other pending timers. Implementations use a single timer with a state variable indicating which event fires next.
TLP state is reset (TLP.is_retrans = false, TLP.end_seq = None) when initiating a connection, fast recovery, or RTO recovery. TLP.end_seq is set to SND.NXT when a probe is sent and cleared to None when the probe is confirmed delivered, deemed lost, or superseded.
Upon RTO expiration, RACK marks the first outstanding segment (SEG.SEQ == SND.UNA) as lost unconditionally; all other unacknowledged segments are marked lost only if Segment.xmit_ts + RACK.rtt + RACK.reo_wnd <= now. This prevents spurious retransmissions of recently sent segments after a spurious RTO.