RFC 8985

The RACK-TLP Loss Detection Algorithm for TCP

📅 published February 2021, from ietf

RFC 8985 💖 The RACK-TLP Loss Detection Algorithm for TCP ✨

Okay bestie, here's the title block first 🎀

  • Series: Internet Engineering Task Force (IETF) 🌸
  • Request for Comments: 8985
  • Title: The RACK-TLP Loss Detection Algorithm for TCP
  • Authors: Y. Cheng, N. Cardwell, N. Dukkipati, and P. Jha, all from Google, Inc. 👑
  • Category: Standards Track
  • ISSN: 2070-1721
  • Date: February 2021
  • Obsoletes / Updates: nothing is listed in this title block 🦋

Abstract 🦋

Okay so this doc introduces the RACK-TLP loss detection algorithm for TCP 🎀. It uses per-segment transmit timestamps plus selective acknowledgments (SACKs), and it has two parts. Recent Acknowledgment (RACK) gets fast recovery going quickly by making time-based guesses from acknowledgment (ACK) feedback. Tail Loss Probe (TLP) works with RACK by sending a probe packet to kick off more ACK feedback, so you dodge retransmission timeout (RTO) events 🏃‍♀️💨.

Compared to the widely used duplicate acknowledgment (DupAck) threshold approach, RACK-TLP is way more efficient at spotting losses when you've got application-limited flights of data, lost retransmissions, or data packets getting reordered 💅. It's meant to be an alternative to the DupAck threshold approach, and honestly it's giving main character energy 👑.

Status of This Memo ✨

This is an Internet Standards Track document, so it's the real deal 🔥.

It's a product of the Internet Engineering Task Force (IETF) and represents the consensus of the IETF community 🫶. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). For more on Internet Standards, check Section 2 of RFC 7841 📚.

For the current status, any errata, and how to send feedback, head to https://www.rfc-editor.org/info/rfc8985 🌈.

Copyright (c) 2021 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as in effect on the date this document was published. Please read these carefully, because they spell out your rights and restrictions for this document 🙈. Code Components pulled out of this document must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as described in the Simplified BSD License.

Table of Contents 🧚

1.  Introduction
  1.1.  Background
  1.2.  Motivation
2.  Terminology
3.  RACK-TLP High-Level Design
  3.1.  RACK: Time-Based Loss Inferences from ACKs
  3.2.  TLP: Sending One Segment to Probe Losses Quickly with RACK
  3.3.  RACK-TLP: Reordering Resilience with a Time Threshold
    3.3.1.  Reordering Design Rationale
    3.3.2.  Reordering Window Adaptation
  3.4.  An Example of RACK-TLP in Action: Fast Recovery
  3.5.  An Example of RACK-TLP in Action: RTO
  3.6.  Design Summary
4.  Requirements
5.  Definitions
  5.1.  Terms
  5.2.  Per-Segment Variables
  5.3.  Per-Connection Variables
  5.4.  Per-Connection Timers
6.  RACK Algorithm Details
  6.1.  Upon Transmitting a Data Segment
  6.2.  Upon Receiving an ACK
  6.3.  Upon RTO Expiration
7.  TLP Algorithm Details
  7.1.  Initializing State
  7.2.  Scheduling a Loss Probe
  7.3.  Sending a Loss Probe upon PTO Expiration
  7.4.  Detecting Losses Using the ACK of the Loss Probe
    7.4.1.  General Case: Detecting Packet Losses Using RACK
    7.4.2.  Special Case: Detecting a Single Loss Repaired by the
            Loss Probe
8.  Managing RACK-TLP Timers
9.  Discussion
  9.1.  Advantages and Disadvantages
  9.2.  Relationships with Other Loss Recovery Algorithms
  9.3.  Interaction with Congestion Control
  9.4.  TLP Recovery Detection with Delayed ACKs
  9.5.  RACK-TLP for Other Transport Protocols
10. Security Considerations
11. IANA Considerations
12. References
  12.1.  Normative References
  12.2.  Informative References
Acknowledgments
Authors' Addresses

1. Introduction 🌸

This doc presents RACK-TLP, a TCP loss detection algorithm that levels up the widely implemented duplicate acknowledgment (DupAck) counting approach described in [RFC5681] and [RFC6675] 💅. It is RECOMMENDED as an alternative to that older approach.

RACK-TLP has two parts. Recent Acknowledgment (RACK) detects losses quickly with time-based inferences from ACK feedback. Tail Loss Probe (TLP) triggers ACK feedback by quickly sending a probe segment, which helps you avoid retransmission timeout (RTO) events 🦋.

1.1. Background 📚

Traditional TCP loss recovery algorithms [RFC5681] [RFC6675] work like this: the sender starts fast recovery once the number of DupAcks received hits a threshold (DupThresh), which defaults to 3. This approach is called "DupAck counting" for the rest of the document 🫶. The sender also halves the congestion window during recovery. The reason for only a partial window reduction is that congestion doesn't seem that severe, since ACK clocking is still going. Fast recovery can take as little as one round trip, for example when the sender uses SACK-based recovery [RFC6675] and only a few segments were lost ⏱️.

If fast recovery doesn't kick in, or it kicks in but doesn't fix every loss, the sender falls back to RTO recovery 😭. The RTO timer interval is conservatively the smoothed RTT (SRTT) plus four times the RTT variation, with a lower bound of 1 second [RFC6298]. When the RTO timer expires, the sender retransmits the first unacknowledged segment and resets the congestion window to the loss window value, which is 1 full-sized segment by default [RFC5681]. The reasoning is that an entire flight of data and the ACK clock got lost, so the sender should respond carefully 🙈. After that, the sender retransmits the rest of the data using the slow start algorithm [RFC5681]. Time spent in RTO recovery is one RTO interval plus however many round trips it takes to repair all the losses 🐢.

1.2. Motivation 💖

Fast recovery is the MVP of loss recovery 👑, because it can potentially recover all the losses within a single round trip, with only a fractional congestion window reduction. RTO recovery and congestion window reset are supposed to be the last resort, and ideally only used when the entire flight is lost. But there are other situations where traditional TCP loss recovery algorithms [RFC5681] [RFC6675] can end up going to RTO recovery when they didn't need to:

  1. Packet drops for short flows or at the end of an application data flight. When the application is what limits the sender (think structured request/response traffic), segments lost at the very end of the transfer often can only be recovered by RTO 😩. Say only the last segment in a flight of 100 segments gets lost. With no DupAck to go on, the RTO expires, the congestion window drops to 1, and it only climbs to 2 after the loss repair gets acknowledged. Compare that with any single segment loss between the first and the 97th segment, which would trigger fast recovery and only cut the window in half 🥲.
  2. Lost retransmissions. Heavy congestion or traffic policers can cause retransmissions to get lost too 🚫. Lost retransmissions push the sender into RTO recovery, because DupAck counting doesn't detect that the retransmissions were lost. Then the slow start after RTO recovery can cause burst losses again, which hurts performance badly [POLICER16] 💀.
  3. Packet reordering. In this document, "reordering" means segments reach the TCP receiver in a chronological order that's different from the order they were sent in 🔀. Link-layer protocols (for example, 802.11 block ACK), link bonding, or routers' internal load balancing (for example, ECMP) can deliver TCP segments out of order. Usually the degree of reordering is within the order of the path round-trip time. If the reordering degree goes beyond DupThresh, DupAck counting can trigger a spurious fast recovery and an unnecessary congestion window reduction 😤. To fix this, Non-Congestion Robustness (NCR) for TCP [RFC4653] raises the DupThresh from the fixed value of three duplicate ACKs [RFC5681] so it approximates a congestion window of data that has left the network 🧠.

2. Terminology 📖

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🎀.

3. RACK-TLP High-Level Design 🧚

RACK-TLP helps senders recover losses way more effectively in all three scenarios from the previous section 💅. Two design principles sit behind it. The first is to detect losses via ACK events as much as possible, so losses get repaired on round-trip timescales ⚡. The second is to gently probe the network to pull out extra ACK feedback, so you avoid RTO expiration and the congestion window reset that comes with it 🫶. At a high level, RACK implements the first principle and TLP implements the second 🌈.

3.1. RACK: Time-Based Loss Inferences from ACKs ⏰

The logic behind RACK is this: if a segment gets delivered out of order, then the segments sent chronologically before it were either lost or reordered 🕵️‍♀️. That idea isn't fundamentally new. It's pretty similar to what's described in [RFC5681], [RFC6675], or [FACK]. RACK's big innovation is using per-segment transmission timestamps plus the widely deployed SACK [RFC2018] options to make time-based inferences, instead of guessing losses by counting ACKs or SACKed sequences 🦋. Time-based inferences beat DupAck counting because they don't depend on flight size, so they work great for application-limited traffic ✨.

Conceptually, RACK keeps a virtual timer for every data segment sent, retransmissions included ⏳. Each timer expires dynamically based on the latest RTT measurements plus an extra delay budget that makes room for possible packet reordering. That budget is called the "reordering window". When a segment's timer expires, RACK marks that segment as lost so it gets retransmitted 🚨.

Here's the real-world version, though. RACK doesn't actually arm a timer for every segment, because it doesn't need to 🙅‍♀️. Instead, the sender records the most recent transmission time of every data segment it sends, retransmissions included. For each ACK received, the sender calculates the latest RTT measurement (if it's eligible) and adjusts the expiration time of every segment that's been sent but not yet delivered. If a segment has expired, RACK marks it as lost 💖.

The time-based logic of RACK applies equally to retransmissions and original transmissions, so it can catch lost retransmissions too 🥳. If a segment got retransmitted but its most recent (re)transmission timestamp has expired, then after a reordering window it gets marked as lost. Iconic behavior honestly 👑.

3.2. TLP: Sending One Segment to Probe Losses Quickly with RACK ✨

okay so RACK figures out losses from ACK feedback, right? 🦋 But ACKs can be super sparse, especially when the inflight is tiny or the losses are high. In some rough cases, the last few segments in a flight just vanish. With the stuff in [RFC5681] or [RFC6675], the sender's RTO would expire and reset the congestion window even though, in reality, most of the flight already got delivered 😭

Picture this: a sender with a big congestion window sends 100 new data segments after an application write, and only the last three get lost. Without RACK-TLP, the RTO expires, the sender retransmits the first unacknowledged segment, and the congestion window slow starts from 1. Once all the retransmits are acknowledged, the congestion window climbs back up to 4. The whole application transfer takes three RTTs plus one RTO, which is a steep cost when only a tiny slice of the flight was lost 💀 If the losses had happened three segments sooner in the flight, fast recovery would have fixed everything within one round trip and the congestion window wouldn't have been reset at all 🙈

Fast recovery is the move in situations like this, and TLP is designed to trigger the feedback RACK needs to make that happen 💅 After the last (100th) segment was originally sent, TLP sends the next available (new) segment, or retransmits the last (highest-sequenced) segment, in two round trips to probe the network. That's where the name "Tail Loss Probe" comes from 🧚 If the probe gets delivered, it solicits an ACK. RACK uses that ACK to detect that the 98th and 99th segments were lost, triggers fast recovery, and retransmits both successfully. The total recovery time is four RTTs, and the congestion window is only partially reduced instead of being fully reset 🎀 If the probe is also lost, the sender invokes RTO recovery, and yes, the congestion window gets reset 😭

3.3. RACK-TLP: Reordering Resilience with a Time Threshold 🌈

3.3.1. Reordering Design Rationale

Okay, this part is lowkey important 🫶 When a sender gets an ACK indicating a SACKed segment, it can't tell right away whether that was caused by reordering or by loss. It can only figure it out in hindsight, if the missing sequence ranges get filled in later without a retransmission. So a loss detection algorithm needs to budget some wait time, a reordering window, to try to tell packet reordering apart from packet loss 🔥

The reordering window in the DupAck counting approach is implicitly defined as the elapsed time to receive DupThresh SACKed segments or duplicate acknowledgments. This works well if the network reordering degree (in sequence distance) is smaller than DupThresh and at least DupThresh segments arrive after the loss is acknowledged. When the reordering degree is larger than the default DupThresh of 3 packets, one option is to dynamically adapt DupThresh based on the FlightSize (for example, the sender adjusts the DupThresh to half of the FlightSize). But this doesn't work well with the following two types of reordering:

  1. Application-limited flights where the last non-full-sized segment is delivered first and then the remaining full-sized segments in the flight are delivered in order. This reordering pattern can occur when segments traverse parallel forwarding paths. In such scenarios, the degree of reordering in packet distance is one segment less than the flight size.
  2. A flight of segments that are delivered partially out of order. One cause for this pattern is wireless link-layer retransmissions with an inadequate reordering buffer at the receiver. In such scenarios, the wireless sender sends the data packets in order initially, but some are lost and then recovered by link-layer retransmissions. The wireless receiver then delivers the TCP data packets in the order they were received, because its reordering buffer is inadequate. The random wireless transmission errors in such scenarios cause the reordering degree, expressed in packet distance, to have highly variable values up to the flight size.

In both of the cases above, the degree of reordering in packet distance is highly variable 🥺 That makes the DupAck counting approach ineffective, including dynamic adaptation variants like the one in [RFC4653]. Instead, the degree of reordering in time difference is usually within a single round-trip time. That's because the packets either traverse disjoint paths with similar propagation delays, or they get repaired quickly by the local access technology ✨ So using a time threshold instead of a packet threshold hits a sweet middle ground: it allows a bounded degree of reordering resilience while still allowing fast recovery. This is the rationale behind the RACK-TLP reordering resilience design 👑

Specifically, RACK-TLP introduces a new dynamic reordering window parameter in time units. The sender considers a data segment S lost if both of these conditions are met:

  1. Another data segment sent later than S has been delivered.
  2. S has not been delivered after the estimated round-trip time plus the reordering window.

Note that condition (1) implies at least one round trip of time has elapsed since S was sent. ⏳

3.3.2. Reordering Window Adaptation

The RACK reordering window adapts to the measured duration of reordering events, within reasonable and specific bounds, to disincentivize excessive reordering 🙅‍♀️ More specifically, the sender sets the reordering window like this:

  1. The reordering window SHOULD be set to zero if no reordering has been observed on the connection so far, and either (a) three segments have been SACKed since the last recovery or (b) the sender is already in fast or RTO recovery. Otherwise, the reordering window SHOULD start from a small fraction of the round-trip time, or zero if no round-trip time estimate is available.
  2. The RACK reordering window SHOULD adaptively increase (using the algorithm in "Step 4: Update RACK reordering window" below) if the sender receives a Duplicate Selective Acknowledgment (DSACK) option [RFC2883]. Receiving a DSACK suggests the sender made a spurious retransmission, which may have been due to the reordering window being too small.
  3. The RACK reordering window MUST be bounded, and this bound SHOULD be SRTT.

Rules 2 and 3 are required to adapt to reordering caused by dynamics like the prolonged link-layer loss recovery episodes we talked about earlier. Each increase in the reordering window requires a new round trip where the sender receives a DSACK, so depending on how much reordering there is, it may take multiple round trips to fully adapt 🐢

For short flows, the low initial reordering window helps recover losses quickly, at the risk of spurious retransmissions. The logic is that spurious retransmissions for short flows aren't expected to create excessive additional network traffic 💖 For long flows, the design tolerates reordering within a round trip. This handles reordering on small timescales, meaning reordering within the round-trip time of the shortest path.

However, the fact that the initial reordering window is low, and that its adaptive growth is bounded, means there will continue to be a cost to reordering. That cost is what disincentivizes excessive reordering 🫠

3.4. An Example of RACK-TLP in Action: Fast Recovery 🎀

The following example in Figure 1 shows the RACK-TLP algorithm in action:

Event  TCP DATA SENDER                            TCP DATA RECEIVER
_____  ____________________________________________________________
  1.   Send P0, P1, P2, P3          -->
       [P1, P2, P3 dropped by network]

  2.                                <--          Receive P0, ACK P0

  3a.  2RTTs after (2), TLP timer fires
  3b.  TLP: retransmits P3          -->

  4.                                <--         Receive P3, SACK P3

  5a.  Receive SACK for P3
  5b.  RACK: marks P1, P2 lost
  5c.  Retransmit P1, P2            -->
       [P1 retransmission dropped by network]

  6.                                <--    Receive P2, SACK P2 & P3

  7a.  RACK: marks P1 retransmission lost
  7b.  Retransmit P1                -->

  8.                                <--          Receive P1, ACK P3

            Figure 1: RACK-TLP Protocol Example

Figure 1 shows a sender sending four segments (P0, P1, P2, P3) and losing the last three. After two round trips, TLP sends a loss probe, retransmitting the last segment, P3, to solicit SACK feedback and restore the ACK clock (Event 3). The delivery of P3 lets RACK infer (Event 5b) that P1 and P2 were likely lost, because they were sent before P3. The sender then retransmits P1 and P2. Unfortunately, the retransmission of P1 is lost again. However, the delivery of the retransmission of P2 allows RACK to infer that the retransmission of P1 was likely lost (Event 7a), so P1 should be retransmitted (Event 7b) 🕵️‍♀️ Note that [RFC5681] mandates a principle: loss in two successive windows of data, or the loss of a retransmission, must be taken as two indications of congestion, and therefore results in two separate congestion control reactions 🔥

3.5. An Example of RACK-TLP in Action: RTO 🌸

On top of making fast recovery better, RACK also improves the accuracy of RTO recovery by reducing spurious retransmissions 💜

Without RACK, when the RTO timer expires, the sender marks all the unacknowledged segments as lost. This approach can lead to spurious retransmissions. For example, consider a simple case where one segment was sent with an RTO of 1 second, and then the application writes more data, causing a second and third segment to be sent right before the RTO of the first segment expires. Suppose none of the segments were lost. Without RACK, if there is a spurious RTO, the sender marks all three segments as lost and retransmits the first segment. If the ACK for the original copy of the first segment arrives right after the spurious RTO retransmission, the sender continues slow start and spuriously retransmits the second and third segments, since it (erroneously) presumed they were lost 😩

With RACK, when the RTO timer expires, the only segment automatically marked as lost is the first segment (since it was sent an RTO ago). For all the other segments, RACK only marks a segment as lost if at least one round trip has elapsed since that segment was transmitted. Let's run the previous example again, but this time with RACK. When the RTO expires, the sender only marks the first segment as lost and retransmits that segment. The other two very recently sent segments are not marked as lost, because they were sent less than one round trip ago and there were no ACKs providing evidence that they were lost. When the ACK for the RTO retransmission arrives, the RACK sender would not yet retransmit the second or third segment. Instead, it would re-arm the RTO timer and wait for a new RTO interval to elapse before marking the second or third segment as lost ⭐

3.6. Design Summary 🦋

okay so bestie, here's the big picture 💅 RACK-TLP wants to do three things: adapt to small, changing amounts of reordering ✨, recover most losses within one to two round trips 🏃, and avoid those costly RTO recoveries 🙈. when reordering is around, the adaptation can sometimes make things wait longer than they need to while it figures out whether a gap is loss or just reordering 😭 but that wait is capped at one round trip, and only flows that lasted long enough to see reordering end up feeling it 💜

4. Requirements 📋

ok so you should already know your stuff from [RFC5681] (TCP congestion control), [RFC2018] (selective acknowledgment), and [RFC6675] (loss recovery). RACK-TLP has these requirements:

  1. The connection MUST use selective acknowledgment (SACK) options [RFC2018], and the sender MUST keep SACK scoreboard information on a per-connection basis ("SACK scoreboard" has the same meaning here as in [RFC6675], Section 3). 🫶
  2. 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 minimum RTT of the connection. At the time of writing, microsecond resolution is suitable for intra-data center traffic, and millisecond granularity or finer is suitable for the Internet. Note that RACK-TLP can be implemented with TSO (TCP Segmentation Offload) support by having multiple segments in a TSO aggregate share the same timestamp. ⏱️
  3. RACK DSACK-based reordering window adaptation is RECOMMENDED but is not required. 🌸
  4. TLP requires RACK. 👑

5. Definitions 📖

bestie, you need to be familiar with SND.UNA, SND.NXT, SEG.ACK, and SEG.SEQ from [RFC793]; Sender Maximum Segment Size (SMSS) and FlightSize from [RFC5681]; DupThresh from [RFC6675]; and RTO and SRTT from [RFC6298]. RACK-TLP also brings some new terms and needs new per-segment and per-connection state, and we're about to go through all of it 🎀

5.1. Terms 🏷️

these are the terms we use to explain the variables and algorithms below:

  • RACK.segment: among all the segments that have been either selectively or cumulatively acknowledged, this is the segment that was sent most recently (retransmissions included, so yes, they count!) 🍓
  • RACK.ack_ts: the time when the full sequence range of RACK.segment was selectively or cumulatively acknowledged. ⏰

5.2. Per-Segment Variables 🧩

these variables track the status of the most recent transmission of a data segment:

  • Segment.lost: TRUE if the most recent (re)transmission of the segment has been marked as lost and needs to be retransmitted. FALSE otherwise. 💀
  • Segment.retransmitted: TRUE if the segment has ever been retransmitted. FALSE otherwise. 🔁
  • Segment.xmit_ts: the time of the last transmission of a data segment, retransmissions included, with the clock granularity specified in the "Requirements" section. A maximum value INFINITE_TS is an invalid timestamp that means the segment is not currently in flight. 🚫
  • Segment.end_seq: the next sequence number after the last sequence number of the data segment. 🔚

5.3. Per-Connection Variables 🌈

  • RACK.xmit_ts: the latest transmission timestamp of RACK.segment. 🕐
  • RACK.end_seq: the Segment.end_seq of RACK.segment. 🔚
  • RACK.segs_sacked: returns the total number of segments selectively acknowledged in the SACK scoreboard. 📊
  • RACK.fack: the highest selectively or cumulatively acknowledged sequence (aka forward acknowledgment). 🏔️
  • RACK.min_RTT: the estimated minimum round-trip time (RTT) of the connection. 🐢
  • RACK.rtt: the RTT of the most recently delivered segment on the connection (either cumulatively acknowledged or selectively acknowledged) that was not marked as invalid as a possible spurious retransmission. ✅
  • RACK.reordering_seen: indicates whether the sender has detected data segment reordering event(s). 🔀
  • RACK.reo_wnd: a reordering window computed in the unit of time used for recording segment transmission times. It's used to defer the moment at which RACK marks a segment as lost. ⏳
  • RACK.dsack_round: indicates if a DSACK option has been received in the latest round trip. 📬
  • RACK.reo_wnd_mult: the multiplier applied to adjust RACK.reo_wnd. ✖️
  • RACK.reo_wnd_persist: the number of loss recoveries before resetting RACK.reo_wnd. 🔄
  • TLP.is_retrans: a boolean indicating whether there is an unacknowledged TLP retransmission. 🙋
  • TLP.end_seq: the value of SND.NXT at the time of sending a TLP probe. 🎯
  • TLP.max_ack_delay: the sender's budget for the maximum delayed ACK interval. 💜

5.4. Per-Connection Timers ⏲️

  • RACK reordering timer: lets RACK wait for reordering to resolve, so it can try to tell reordering apart from loss when some segments are marked as SACKed. 🕰️
  • TLP PTO: a timer event saying an ACK is overdue, so the sender should transmit a TLP segment to get SACK or ACK feedback. 📣

these timers join the existing timers a sender already has, including the RTO timer [RFC6298]. A RACK-TLP sender arms one of these three timers (RACK reordering timer, TLP PTO timer, or RTO timer) whenever it has unacknowledged segments in flight. An implementation can make life easier by multiplexing a single timer across all three, with an extra variable that says which event to run when it next expires. 🧠

6. RACK Algorithm Details 🧁

6.1. Upon Transmitting a Data Segment 🚀

whenever you transmit a new segment or retransmit an old one, record the time in Segment.xmit_ts and set Segment.lost to FALSE. When you retransmit, also set Segment.retransmitted to TRUE.

RACK_transmit_new_data(Segment):
        Segment.xmit_ts = Now()
        Segment.lost = FALSE

RACK_retransmit_data(Segment):
        Segment.retransmitted = TRUE
        Segment.xmit_ts = Now()
        Segment.lost = FALSE

6.2. Upon Receiving an ACK 📨

Step 1: Update RACK.min_RTT.

use the RTT measurements from [RFC6298] or [RFC7323] to update the estimated minimum RTT in RACK.min_RTT. The sender SHOULD track a windowed min-filtered estimate of recent RTT measurements that can adapt when moving to significantly longer paths, rather than tracking a simple global minimum of all RTT measurements. 🪟

Step 2: Update the state for the most recently sent segment that has been delivered.

this is where RACK updates the state that tracks the most recently sent segment that has been delivered, which is RACK.segment. RACK keeps its latest transmission timestamp in RACK.xmit_ts and its highest sequence number in RACK.end_seq. Later steps use these two to estimate whether segments that haven't been delivered yet were likely lost. Based on the info in an ACK, each segment that was cumulatively ACKed or SACKed gets marked as delivered in the scoreboard. An ACK can also acknowledge retransmitted data segments, and retransmissions can be spurious, so the sender has to be careful to avoid spurious inferences. For example, if the sender used timing info from a spurious retransmission, RACK.rtt could end up vastly underestimated. 🕵️

to dodge spurious inferences, ignore a segment as invalid if any part of its sequence range has been retransmitted before AND either of these two conditions is true:

  1. The Timestamp Echo Reply field (TSecr) of the ACK's timestamp option [RFC7323], if available, indicates the ACK was not acknowledging the last retransmission of the segment. 🔍
  2. The segment was last retransmitted less than RACK.min_rtt ago. ⌛

the second check is a heuristic for when the TCP Timestamp option isn't available, or when the round-trip time is less than the TCP Timestamp clock granularity. 🤏

among all the segments newly ACKed or SACKed by this ACK that pass those checks, update RACK.rtt to be the RTT sample calculated from this ACK. Then record the most recent Segment.xmit_ts in RACK.xmit_ts if it's ahead of RACK.xmit_ts. If Segment.xmit_ts equals RACK.xmit_ts (for example, because of clock granularity limits), compare Segment.end_seq and RACK.end_seq to break the tie when deciding whether to update RACK.segment's associated state. 🎀

Step 2 can be summarized in pseudocode like this:

RACK_sent_after(t1, seq1, t2, seq2):
    If t1 > t2:
        Return true
    Else if t1 == t2 AND seq1 > seq2:
        Return true
    Else:
        Return false

RACK_update():
    For each Segment newly acknowledged, cumulatively or selectively,
    in ascending order of Segment.xmit_ts:
        rtt = Now() - Segment.xmit_ts
        If Segment.retransmitted is TRUE:
            If ACK.ts_option.echo_reply < Segment.xmit_ts:
               Continue
            If rtt < RACK.min_rtt:
               Continue

        RACK.rtt = rtt
        If RACK_sent_after(Segment.xmit_ts, Segment.end_seq
                           RACK.xmit_ts, RACK.end_seq):
            RACK.xmit_ts = Segment.xmit_ts
            RACK.end_seq = Segment.end_seq

Step 3: Detect data segment reordering.

to spot reordering, the sender watches for original data segments being delivered out of order. It tracks the highest sequence selectively or cumulatively acknowledged in the RACK.fack variable. ".fack" stands for the most "Forward ACK" (this term is adopted from [FACK]). If a never-retransmitted segment that's below RACK.fack gets (selectively or cumulatively) acknowledged, it was delivered out of order, and the sender sets RACK.reordering_seen to TRUE. 🔀✨

RACK_detect_reordering():
    For each Segment newly acknowledged, cumulatively or selectively,
    in ascending order of Segment.end_seq:
        If Segment.end_seq > RACK.fack:
            RACK.fack = Segment.end_seq
        Else if Segment.end_seq < RACK.fack AND
                Segment.retransmitted is FALSE:
            RACK.reordering_seen = TRUE

Step 4: Update the RACK reordering window.

the RACK reordering window, RACK.reo_wnd, is an adaptive allowance for settling time before a segment gets marked as lost. This step spells out a detailed algorithm that follows the principles from the "Reordering Window Adaptation" section. 🪟💖

if no reordering has been observed based on the previous step, one way the sender can enter fast recovery is when the number of SACKed segments matches or exceeds DupThresh (similar to [RFC6675]). Also, when no reordering has been observed, RACK.reo_wnd is set to 0 both upon entering and during fast recovery or RTO recovery. 🧼

otherwise, if some reordering has been observed, RACK does not trigger fast recovery based on DupThresh. 🙅‍♀️

whether or not reordering has been observed, RACK uses the reordering window to decide whether any segments can be marked as lost. So the sender also enters fast recovery when there are any number of SACKed segments, as long as the reorder window has passed for some non-SACKed segments. 🏃‍♀️💨

when the reordering window isn't set to 0, it starts out conservative at RACK.reo_wnd of RACK.min_RTT/4. That number was picked because Linux TCP used the same factor to delay Early Retransmit [RFC5827] and cut down on spurious loss detections when reordering was happening, and experience showed it worked reasonably well [DMCG11]. 🐧💜

However, the reordering detection from Step 3 has a sneaky self-reinforcing problem 🙈. When the reordering window is too small for the reordering that's actually happening, RACK can spuriously mark reordered segments as lost, so they get retransmitted. Those retransmissions then block the conditions Step 3 needs to detect reordering, because that mechanism only uses ACKs or SACKs for segments that have never been retransmitted. Sometimes this loop keeps going, and RACK keeps wrongly marking segments as lost without ever realizing the reordering window is too small 😭

To break out of that loop, RACK adapts to higher degrees of reordering using DSACK options from the receiver ✨. When an ACK carries a DSACK option, that suggests a possible spurious retransmission, which hints that RACK.reo_wnd might be too small. The window grows linearly for every round trip in which the sender gets some DSACK option. So after N round trips with a DSACK, RACK.reo_wnd becomes (N+1) * min_RTT / 4, capped at SRTT 💅

But if the reordering was only temporary, a big adapted window would needlessly slow down loss recovery later. So RACK keeps using the inflated RACK.reo_wnd for up to 16 loss recoveries, then resets it to its starting value, min_RTT / 4. The catch with resetting is that if reordering is still high, you can get spurious fast recovery episodes again. The point of this design is to keep those spurious recoveries to roughly once every 16 recoveries (less than 7%) 🎀

To track the linear scaling factor for the adaptive reordering window, RACK uses the variable RACK.reo_wnd_mult. It starts at 1 and adapts as reordering is observed 🦋

Here's the pseudocode that implements the RACK reordering window update:

RACK_update_reo_wnd():

    /* DSACK-based reordering window adaptation */
    If RACK.dsack_round is not None AND
       SND.UNA >= RACK.dsack_round:
        RACK.dsack_round = None
    /* Grow the reordering window per round that sees DSACK.
       Reset the window after 16 DSACK-free recoveries */
    If RACK.dsack_round is None AND
       any DSACK option is present on latest received ACK:
        RACK.dsack_round = SND.NXT
        RACK.reo_wnd_mult += 1
        RACK.reo_wnd_persist = 16
    Else if exiting Fast or RTO recovery:
        RACK.reo_wnd_persist -= 1
        If RACK.reo_wnd_persist <= 0:
            RACK.reo_wnd_mult = 1

    If RACK.reordering_seen is FALSE:
        If in Fast or RTO recovery:
            Return 0
        Else if RACK.segs_sacked >= DupThresh:
            Return 0
    Return min(RACK.reo_wnd_mult * RACK.min_RTT / 4, SRTT)

6.2. Upon Receiving an ACK (continued) 💖

Step 5: Detect losses.

For each segment that hasn't been SACKed, RACK considers it lost if another segment that was sent later has been delivered and the reordering window has passed 👀. RACK considers the reordering window passed if the RACK.segment was sent long enough after the segment in question, if enough time has elapsed since the RACK.segment was S/ACKed, or some mix of the two. More precisely, RACK marks a segment as lost if:

RACK.xmit_ts >= Segment.xmit_ts
       AND
RACK.xmit_ts - Segment.xmit_ts + (now - RACK.ack_ts) >= RACK.reo_wnd

Now solve that second condition for "now", which is the moment a segment gets marked as lost, and you get:

now >= Segment.xmit_ts + RACK.reo_wnd + (RACK.ack_ts - RACK.xmit_ts)

So (RACK.ack_ts - RACK.xmit_ts) is the round-trip time of the most recently (re)transmitted segment that has been delivered 🧚 When segments arrive in order, that segment is also the most recently delivered one, so RACK.rtt == RACK.ack_ts - RACK.xmit_ts. But if reordering happened, the most recently delivered segment was sent before the most recently (re)transmitted one. That means RACK.rtt > (RACK.ack_ts - RACK.xmit_ts) ✨

Since RACK.RTT >= (RACK.ack_ts - RACK.xmit_ts), the earlier equation simplifies to: the sender can declare a segment lost when:

now >= Segment.xmit_ts + RACK.reo_wnd + RACK.rtt

Which is the same as saying a RACK sender should declare a segment lost when:

Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - now <= 0

If the left-hand side is positive, it's the time left to wait before the segment is considered lost. The problem is that waiting like this risks an RTO if no more ACKs come back (say, because of losses or application-limited transmissions) to trigger the marking 😰 So for timely loss detection, it is RECOMMENDED that the sender install a reordering timer. This timer expires at the earliest moment when RACK would conclude that all the unacknowledged segments inside the reordering window were lost.

Here's the pseudocode for the algorithm above. When an ACK arrives or the RACK reordering timer expires, call RACK_detect_loss_and_arm_timer(). The algorithm breaks timestamp ties using the TCP sequence space, since high-speed networks often have several segments with identical timestamps 🍓

RACK_detect_loss():
    timeout = 0
    RACK.reo_wnd = RACK_update_reo_wnd()
    For each segment, Segment, not acknowledged yet:
        If RACK_sent_after(RACK.xmit_ts, RACK.end_seq,
                           Segment.xmit_ts, Segment.end_seq):
            remaining = Segment.xmit_ts + RACK.rtt +
                        RACK.reo_wnd - Now()
            If remaining <= 0:
                Segment.lost = TRUE
                Segment.xmit_ts = INFINITE_TS
            Else:
                timeout = max(remaining, timeout)
    Return timeout

RACK_detect_loss_and_arm_timer():
    timeout = RACK_detect_loss()
    If timeout != 0
        Arm the RACK timer to call
        RACK_detect_loss_and_arm_timer() after timeout

As an optimization, an implementation can check only segments that were sent before RACK.xmit_ts 🚀 That can beat scanning the entire SACK scoreboard, especially when lots of segments are in flight. The implementation can keep a separate doubly linked list ordered by Segment.xmit_ts, add a segment to the tail when it's (re)transmitted, and remove it when it's delivered or marked lost. In Linux TCP, this optimization cut CPU usage by orders of magnitude during some fast recovery episodes on high-speed WAN networks 👑

6.3. Upon RTO Expiration 🌸

Okay, so when the RTO timer expires, RACK marks the first outstanding segment as lost, since it was sent a full RTO ago 💀 For all the other segments, RACK only marks one as lost if the time since it was transmitted is at least the recent RTT plus the reordering window ✨

RACK_mark_losses_on_RTO():
    For each segment, Segment, not acknowledged yet:
        If SEG.SEQ == SND.UNA OR
           Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - Now() <= 0:
            Segment.lost = TRUE

7. TLP Algorithm Details 🧚‍♀️

7.1. Initializing State

Reset TLP.is_retrans and TLP.end_seq whenever a connection, fast recovery, or RTO recovery starts 🎀

TLP_init():
    TLP.end_seq = None
    TLP.is_retrans = false

7.2. Scheduling a Loss Probe 💅

The sender schedules a loss probe timeout (PTO) to send a segment during normal transmission. The sender SHOULD start or restart a loss probe PTO timer after sending new data (that wasn't itself a loss probe), or upon receiving an ACK that cumulatively acknowledges new data, unless it's already in fast recovery, RTO recovery, or segments have been SACKed (i.e., RACK.segs_sacked is not zero) 🙈 Those cases are skipped because similar mechanisms already handle them, like Limited Transmit [RFC3042], the RACK reordering timer, and Forward RTO-Recovery (F-RTO) [RFC5682].

The sender works out the PTO interval by juggling a few factors 🫶

First, the default PTO interval is 2*SRTT. By then it's fair to say an ACK is overdue, since with no losses an ACK usually shows up within one SRTT. Picking a PTO of exactly one SRTT would risk spurious probes, because network and end-host delay variance can push an ACK past the SRTT. So the PTO is conservatively set to the next integral multiple of SRTT ✨

Second, when there's no SRTT estimate, the PTO SHOULD be 1 second. That conservative value matches the RTO when no SRTT is available, per [RFC6298] 🌈

Third, when the FlightSize is one segment, the sender MAY inflate the PTO by TLP.max_ack_delay to account for a possibly delayed acknowledgment, which lowers the risk of spurious retransmissions 🦋 The actual value of TLP.max_ack_delay is implementation specific.

Finally, if the time an RTO would fire (written here as "TCP_RTO_expiration()") comes sooner than the computed PTO time, the sender schedules the TLP to go out at that RTO time instead 😭

Here's the pseudocode summary. A sender SHOULD use the following logic to pick the PTO duration:

TLP_calc_PTO():
    If SRTT is available:
        PTO = 2 * SRTT
        If FlightSize is one segment:
           PTO += TLP.max_ack_delay
    Else:
        PTO = 1 sec

    If Now() + PTO > TCP_RTO_expiration():
        PTO = TCP_RTO_expiration() - Now()

7.3. Sending a Loss Probe upon PTO Expiration 💖

okay so when the PTO timer goes off, the sender MUST check two things before it sends a loss probe 👀

  1. first, no other previous loss probe can still be in flight 🙅‍♀️. this keeps things tidy, because at any given time the sender has at most one extra packet in flight beyond the congestion window limit. the thing tracking this is TLP.end_seq, which holds the latest unacknowledged TLP loss probe's ending sequence. it gets reset once that probe is acknowledged, or once it's declared lost or irrelevant ✨
  2. second, the sender has to have gotten an RTT measurement since the last loss probe went out, or since the connection started, whichever was later 📏. this makes sure loss probe retransmissions don't stop us from collecting the RTT samples we need to adapt SRTT when the path RTT goes up 🦋

if either of those conditions isn't met, the sender MUST skip sending a loss probe and MUST proceed to re-arm the RTO timer, as explained at the end of this section 🙃

if both conditions are met, the sender SHOULD send a previously unsent data segment (if there is one and the receive window allows it) and increase FlightSize to match 🚀

heads up: FlightSize can end up one packet bigger than the congestion window for a little while, until the next ACK shows up 🚨

if there's no unsent segment available, the sender SHOULD retransmit the highest-sequence segment sent so far and set TLP.is_retrans to true. this segment gets picked to handle the retransmission ambiguity problem in TCP 🧩 here's the vibe: say a sender sends N segments, then retransmits the last one (segment N) as a loss probe, and then gets a SACK for segment N. as long as the sender waits out the RACK reordering window, it doesn't matter whether that SACK was for the original transmission or the TLP retransmission. either way, the SACK for segment N is evidence that the N-1 segments before it were likely lost 🕵️‍♀️

in the case where there's only one original outstanding segment (N=1), the same logic applies, just trivially 💅 an ACK for that single outstanding segment tells the sender that the N-1=0 segments before it were lost. and whether there are N>1 or N=1 outstanding segments, there's a question about whether the original last segment or its TLP retransmission got lost. the sender estimates that using TLP recovery detection (see below) 🌸

the sender MUST follow the RACK transmission procedures in the "Upon Transmitting a Data Segment" section when it sends either a retransmission or a new data loss probe. this is critical for detecting losses using the ACK for the loss probe 🔥

after trying to send a loss probe, whether or not one actually went out, the sender MUST re-arm the RTO timer (not the PTO timer) if FlightSize is not zero. this keeps RTO as the last resort if TLP fails 🛟 the pseudocode below sums it all up 🎀

TLP_send_probe():

    If TLP.end_seq is None and
       Sender has taken a new RTT sample since last probe or
       the start of connection:
        TLP.is_retrans = false
        Segment = send buffer segment starting at SND.NXT
        If Segment exists and fits the peer receive window limit:
            /* Transmit the lowest-sequence unsent Segment */
            Transmit Segment
            RACK_transmit_data(Segment)
            TLP.end_seq = SND.NXT
            Increase FlightSize by Segment length
        Else:
            /* Retransmit the highest-sequence Segment sent */
            Segment = send buffer segment ending at SND.NXT
            Transmit Segment
            RACK_retransmit_data(Segment)
            TLP.end_seq = SND.NXT
            TLP.is_retrans = true

    If FlightSize is not zero:
        Rearm RTO timer to fire at timeout = now + RTO

7.4. Detecting Losses Using the ACK of the Loss Probe 🕵️‍♀️

when there's packet loss in a flight that ends with a loss probe, the feedback the probe solicits will reveal one of two scenarios, depending on the pattern of losses 🧠

7.4.1. General Case: Detecting Packet Losses Using RACK 🏃‍♀️

if the loss probe and the ACK that acknowledges it are both delivered successfully, RACK-TLP uses that ACK just like it would use any other ACK to detect whether any segments sent before the probe were dropped 📬 RACK would typically infer that any unacknowledged data segments sent before the loss probe were lost, since they were sent far enough back in time (at least one PTO has elapsed, plus one round trip for the loss probe to get ACKed) ⏳ more specifically, RACK_detect_loss() (Step 5) would mark those earlier segments as lost. then the sender would trigger a fast recovery to recover those losses 💨

7.4.2. Special Case: Detecting a Single Loss Repaired by the Loss Probe 🎯

if the TLP retransmission repairs all the lost in-flight sequence ranges (aka only the last segment in the flight was lost), the ACK for the loss probe looks like a regular cumulative ACK 🤏 that wouldn't normally trigger the congestion control response to this packet loss event. the TLP recovery detection mechanism below examines ACKs to catch this special case so congestion control responds properly [RFC5681] 👑

after a TLP retransmission, the sender checks for this special case of a single loss that the loss probe itself recovered 🔎 to do that, it looks for a duplicate ACK or a DSACK showing that both the original segment and the TLP retransmission arrived at the receiver, which means there was no loss. if the TLP sender doesn't get such an indication, it MUST assume that the original data segment, the TLP retransmission, or a corresponding ACK was lost for congestion control purposes 😬

if the TLP retransmission was spurious, a receiver that uses DSACK would return an ACK that covers TLP.end_seq with a DSACK option (Case 1). if the receiver doesn't support DSACK, it would return a DupAck without any SACK option (Case 2). if the sender gets an ACK matching either case, it estimates that the receiver got both the original data segment and the TLP probe retransmission. the sender then considers the TLP episode done and records that by setting TLP.end_seq to None 🫶

upon receiving an ACK that covers some sequence number after TLP.end_seq, the sender should have received any ACKs for the original segment and the TLP probe retransmission. at that point, if TLP.end_seq is still set (meaning the TLP probe retransmission is still unacknowledged), the sender should presume that at least one of its data segments was lost. the sender then SHOULD invoke a congestion control response equivalent to a fast recovery 🍓

more precisely, on each ACK, the sender runs the following:

TLP_process_ack(ACK):
    If TLP.end_seq is not None AND ACK's ack. number >= TLP.end_seq:
        If not TLP.is_retrans:
            TLP.end_seq = None    /* TLP of new data delivered */
        Else if ACK has a DSACK option matching TLP.end_seq:
            TLP.end_seq = None    /* Case 1, above */
        Else If ACK's ack. number > TLP.end_seq:
            TLP.end_seq = None    /* Repaired the single loss */
            (Invoke congestion control to react to
             the loss event the probe has repaired)
        Else If ACK is a DupAck without any SACK option:
            TLP.end_seq = None     /* Case 2, above */

8. Managing RACK-TLP Timers ⏰

the RACK reordering timer, the TLP PTO timer, the RTO, and the Zero Window Probe (ZWP) timer [RFC793] are mutually exclusive, and each one gets used in different scenarios 🧚 when arming a RACK reordering timer or a TLP PTO timer, the sender SHOULD cancel any other pending timers. an implementation is expected to have one timer, plus an additional state variable that indicates what type of timer it is 💜

9. Discussion 🌈

9.1. Advantages and Disadvantages ✨

okay so the BIGGEST perk of RACK-TLP is that every data segment, whether it's a brand new transmission or a retransmission, can be used to figure out which segments sent before it got lost. 💅 That's what lets it use fast recovery when the sender has a small, application-limited flight of data, when a retransmission gets lost, or when segments get reordered. The examples are literally so good, let me walk you through them 🦋

  1. Packet drops at the end of an application data flight 🌸: Picture a sender that transmits an application-limited flight of three data segments (P1, P2, P3), and P1 and P3 both get lost. Say each segment is sent at least RACK.reo_wnd after the one before it. RACK marks P1 as lost once the SACK of P2 comes back, and that triggers the retransmission of P1 as R1. When R1 gets cumulatively acknowledged, RACK marks P3 as lost, and the sender retransmits P3 as R3. So RACK can fix certain drops at the tail of a transaction without needing an RTO, which is iconic behaviour ngl 🔥 Notice that neither the conventional duplicate ACK threshold [RFC5681], nor the loss recovery algorithm [RFC6675], nor the Forward Acknowledgment [FACK] algorithm can catch these losses, because they all rely on a required segment or sequence count. 💀
  2. Lost retransmission 🙈: Imagine a flight of three data segments (P1, P2, P3) that get sent, and P1 and P2 are dropped. Again, each segment is sent at least RACK.reo_wnd after the previous one. When P3 is SACKed, RACK marks P1 and P2 as lost, and they get retransmitted as R1 and R2. Now suppose R1 is lost again but R2 is SACKed. RACK marks R1 as lost and triggers another retransmission. Once again, the conventional three-duplicate ACK threshold approach, the loss recovery algorithm [RFC6675], and the Forward Acknowledgment [FACK] algorithm all miss this one. 😭 This can totally happen when TCP is being rate-limited, especially by token bucket policers with a large bucket depth and a low rate limit. In those cases, retransmissions keep getting lost over and over, because standard congestion control needs multiple round trips to pull the rate below the policed rate. Not me having to retransmit the same packet five times 🫠
  3. Packet reordering 🧚: Consider a simple reordering event where a flight of segments is sent as (P1, P2, P3). P1 and P2 each carry a full payload of Maximum Sender Size (MSS) octets, but P3 only has a 1-octet payload. Say the sender already detected reordering before, so RACK.reo_wnd is min_RTT/4. Now P3 gets reordered and delivered first, before P1 and P2. As long as P1 and P2 arrive within min_RTT/4, RACK won't consider them lost. But if P1 and P2 are delivered outside the reordering window, RACK will still spuriously mark them as lost. Oop, that's a little awkward 😬

RACK-TLP is especially useful when the sender is limited by the application, which happens a lot with interactive or request/response traffic. ✨ RACK still works when the sender is limited by the receive window too, which can happen with applications that use the receive window to throttle the sender. Main character energy for sure 👑

RACK-TLP also works more efficiently with TCP Segmentation Offload (TSO) than DupAck counting does. RACK always marks the entire TSO aggregate as lost, because every segment in the same TSO aggregate shares the same transmission timestamp. 🍓 By contrast, the algorithms based on sequence counting (e.g., [RFC6675], [RFC5681]) may mark only a subset of the segments in a TSO aggregate as lost. That forces the stack to do expensive fragmentation of the TSO aggregate, or to selectively tag individual segments as lost in the scoreboard. Ew, expensive 💅

The main drawback of RACK-TLP is the extra state it needs compared to DupAck counting. RACK requires the sender to record the transmission time of each segment sent, at a clock granularity finer than 1/4 of the minimum RTT of the connection. TCP implementations that already record this for RTT estimation don't need any new per-packet state. 🌈 But implementations that aren't recording segment transmission times yet will need to add per-packet internal state (expected to be either 4 or 8 octets per segment or TSO aggregate) to track them. In contrast, the loss detection approach in [RFC6675] doesn't need any per-packet state beyond the SACK scoreboard. That's especially useful on ultra-low RTT networks, where the RTT may be less than the sender TCP clock granularity (e.g., inside data centers). Another downside is that the reordering timer can expire prematurely (like any other retransmission timer), which causes more spurious retransmissions, especially if DSACK is not supported. 🥲

9.2. Relationships with Other Loss Recovery Algorithms 🦋

okay the main motivation of RACK-TLP is to be a general alternative to some of the standard loss recovery algorithms [RFC5681] [RFC6675] [RFC5827] [RFC4653]. 💖 In particular, the SACK loss recovery algorithm for TCP [RFC6675] isn't designed to handle lost retransmissions. So its NextSeg() doesn't work for lost retransmissions, and it doesn't specify the corresponding required additional congestion response. Therefore, the algorithm [RFC6675] MUST NOT be used with RACK-TLP. Instead, a modified recovery algorithm that carefully handles this case is needed. 🚫

The Early Retransmit mechanism [RFC5827] and NCR for TCP [RFC4653] dynamically adjust the duplicate ACK threshold based on the current or previous flight sizes. RACK-TLP takes a different approach by using a time-based reordering window. ⭐ RACK-TLP can be seen as an extended Early Retransmit [RFC5827] without a FlightSize limit, but with an additional reordering window. [FACK] considers an original segment lost when its sequence range is sufficiently far below the highest SACKed sequence. Honestly, RACK-TLP is basically a generalized form of FACK that works in time space instead of sequence space, which lets it handle reordering, application-limited traffic, and lost retransmissions way better 🧚✨

RACK-TLP is compatible with the standard RTO [RFC6298], RTO Restart [RFC7765], F-RTO [RFC5682], and Eifel algorithms [RFC3522]. That's because RACK-TLP only detects loss by using ACK events. It doesn't change the RTO timer calculation, and it doesn't detect spurious RTOs. 🌸 RACK-TLP does slightly change the behaviour of [RFC6298], though, by preceding the RTO with a TLP, which reduces potential spurious retransmissions after RTO. 💜

9.3. Interaction with Congestion Control 💅

RACK-TLP intentionally decouples loss detection from congestion control. It only detects losses, and it does not modify the congestion control algorithm [RFC5681] [RFC6937]. A segment marked as lost by RACK-TLP MUST NOT be retransmitted until congestion control deems this appropriate. 🛑 As mentioned in the paragraph following Figure 1 (Section 3.4, Paragraph 3), [RFC5681] mandates a principle: a loss in two successive windows of data, or the loss of a retransmission, must be taken as two indications of congestion and therefore trigger two separate reactions. 🔥 The Proportional Rate Reduction (PRR) algorithm [RFC6937] is RECOMMENDED for the specific congestion control actions taken upon losses detected by RACK-TLP. In the absence of PRR [RFC6937], when RACK-TLP detects a lost retransmission, the congestion control MUST trigger an additional congestion response per the principle above in [RFC5681]. If multiple original transmissions or retransmissions were lost in a window, the congestion control specified in [RFC5681] only reacts once per window. The congestion control implementer is advised to carefully consider this subtle situation introduced by RACK-TLP. 🧐

The only exception (the only way RACK-TLP modulates the congestion control algorithm) is that one outstanding loss probe can be sent even if the congestion window is fully used. ✨ However, this temporary overcommit is accounted for and credited in the in-flight data tracked for congestion control, so congestion control will erase the overcommit upon the next ACK. 🫶

If packet losses happen after reordering has been observed, RACK-TLP may take longer to detect losses than pure DupAck counting does. In this case, TCP may keep increasing the congestion window upon receiving ACKs during this time, making the sender more aggressive. 😬

The following simple example compares how RACK-TLP and non-RACK-TLP loss detection interact with congestion control. Suppose a sender has a congestion window (cwnd) of 20 segments on a SACK-enabled connection. It sends 10 data segments, and all of them are lost. 🌈

Without RACK-TLP, the sender would time out, reset cwnd to 1, and retransmit the first segment. It would take four round trips (1 + 2 + 4 + 3 = 10) to retransmit all 10 lost segments using slow start. The recovery latency would be RTO + 4*RTT, with an ending cwnd of 4 segments due to congestion window validation. 💀

With RACK-TLP, the sender would send the TLP after 2*RTT and get a DupAck, which enables RACK to detect the losses and trigger fast recovery. If the sender implements Proportional Rate Reduction [RFC6937], it would slow start to retransmit the remaining 9 lost segments, since the number of segments in flight (0) is lower than the slow start threshold (10). The slow start would again take four round trips (1 + 2 + 4 + 3 = 10) to retransmit all the lost segments. The recovery latency would be 2*RTT + 4*RTT, with an ending cwnd set to the slow-start threshold of 10 segments. 🦋

The difference in recovery latency (RTO + 4*RTT vs 6*RTT) can be significant if the RTT is much smaller than the minimum RTO (1 second in [RFC6298]) or if the RTT is large. The former case can happen in local area networks, data center networks, or content distribution networks with deep deployments. The latter case can happen in developing regions with highly congested and/or high-latency networks. 🌍

9.4. TLP Recovery Detection with Delayed ACKs 🙈

Delayed or stretched ACKs complicate the detection of repairs done by TLP, because with such ACKs the sender takes a longer time to receive fewer ACKs than would normally be expected. 🐢 To mitigate this, before sending a TLP loss probe retransmission, the sender should attempt to wait long enough that the receiver has sent any delayed ACKs it is withholding. The sender algorithm described above features such a delay in the form of TLP.max_ack_delay. 💖 Furthermore, if the receiver supports DSACK, then in the case of a delayed ACK, the sender's TLP recovery detection mechanism (see above) can use the DSACK information to infer that both the original and the TLP retransmission arrived at the receiver. 🎀

If there is ACK loss or a delayed ACK without a DSACK, this algorithm is conservative, because the sender will reduce the congestion window when, in fact, there was no packet loss. In practice this is acceptable and potentially even desirable, since if there is reverse path congestion, reducing the congestion window can be prudent. 🫶

Okay bestie, let's finish this thing! 🌈

9.5. RACK-TLP for Other Transport Protocols ✨

okay so RACK-TLP isn't just a TCP thing, it can be built into other transport protocols too 🦋 like [QUIC-LR] does. and get this, the [SPROUT] loss detection algorithm was also designed on its own to use a 10 ms reordering window to sharpen its loss detection, which is literally the same vibe as RACK 😭🔥 two different teams, same brilliant idea, iconic.

10. Security Considerations 🔐

okay this part is SERIOUS bestie, so listen up 💅

RACK-TLP behavior is based on information carried in SACK options, so it has security considerations similar to the ones in the Security Considerations section of [RFC6675] 🫶

and here's the plot twist 🙈 RACK-TLP has a lower risk profile than the loss recovery algorithm in [RFC6675], because it is not vulnerable to ACK-splitting attacks [SCWA99]. quick recap of how that attack goes: for an MSS-sized segment that was sent, the receiver or an attacker might send MSS ACKs that selectively or cumulatively acknowledge one additional byte per ACK. this would NOT fool RACK 💀 in that scenario, RACK.xmit_ts would not advance, because every sequence range inside the segment was transmitted at the same time and so they all carry the same transmission timestamp. in other words, SACKing only one byte of a segment or SACKing the whole segment in its entirety has the same effect with RACK. no cap, that's so clean 👑

11. IANA Considerations 🌸

this document has no IANA actions, so nothing to register here, we're good ✨

12. References 📚

12.1. Normative References 💜

12.2. Informative References 🦋

Acknowledgments 💖

the authors thank Matt Mathis for his insights in FACK and Michael Welzl for his per-packet timer idea that inspired this work 🧚 and a huge shoutout to Eric Dumazet, Randy Stewart, Van Jacobson, Ian Swett, Rick Jones, Jana Iyengar, Hiren Panchasara, Praveen Balasubramanian, Yoshifumi Nishida, Bob Briscoe, Felix Weinrank, Michael Tüxen, Martin Duke, Ilpo Jarvinen, Theresa Enghardt, Mirja Kühlewind, Gorry Fairhurst, Markku Kojo, and Yi Huang, who all contributed to this document or to the implementations in Linux, FreeBSD, Windows, and QUIC. the whole squad is iconic 🫶✨

Authors' Addresses 🎀

  • Yuchung Cheng Google, Inc. Email: ycheng@google.com
  • Neal Cardwell Google, Inc. Email: ncardwell@google.com
  • Nandita Dukkipati Google, Inc. Email: nanditad@google.com
  • Priyaranjan Jha Google, Inc. Email: priyarjha@google.com

and that's a wrap, bestie!! 🦋💜 RACK-TLP is the goat of loss detection and I'm obsessed. periodt. 💅👑

📦 where this page comes from