idnits 2.17.1 draft-ietf-tcpm-rack-10.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document is more than 15 pages and seems to lack a Table of Contents. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There is 1 instance of too long lines in the document, the longest one being 2 characters in excess of 72. ** The abstract seems to contain references ([RFC2018], [RFC5681], [RFC6675]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (August 22, 2020) is 1342 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'RFC8174' is mentioned on line 69, but not defined == Missing Reference: 'RFC3522' is mentioned on line 1141, but not defined == Missing Reference: 'RACK-TCPM97' is mentioned on line 411, but not defined == Missing Reference: 'DMCG11' is mentioned on line 672, but not defined == Missing Reference: 'RFC3042' is mentioned on line 856, but not defined ** Obsolete normative reference: RFC 793 (Obsoleted by RFC 9293) -- No information found for draft-ietf-quic-recovery-latest - is the name correct? Summary: 4 errors (**), 0 flaws (~~), 6 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 TCP Maintenance Working Group Y. Cheng 3 Internet-Draft N. Cardwell 4 Intended status: Standards Track N. Dukkipati 5 Expires: February 23, 2021 P. Jha 6 Google, Inc 7 August 22, 2020 9 The RACK-TLP loss detection algorithm for TCP 10 draft-ietf-tcpm-rack-10 12 Abstract 14 This document presents the RACK-TLP loss detection algorithm for TCP. 15 RACK-TLP uses per-segment transmit timestamps and selective 16 acknowledgements (SACK) [RFC2018] and has two parts: RACK ("Recent 17 ACKnowledgment") starts fast recovery quickly using time-based 18 inferences derived from ACK feedback. TLP ("Tail Loss Probe") 19 leverages RACK and sends a probe packet to trigger ACK feedback to 20 avoid retransmission timeout (RTO) events. Compared to the widely 21 used DUPACK threshold approach, RACK-TLP detects losses more 22 efficiently when there are application-limited flights of data, lost 23 retransmissions, or data packet reordering events. It is intended to 24 be an alternative to the DUPACK threshold approach in 25 [RFC5681][RFC6675]. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on February 23, 2021. 44 Copyright Notice 46 Copyright (c) 2020 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (https://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 1. Terminology 61 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 62 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 63 "OPTIONAL" in this document are to be interpreted as described in BCP 64 14 [RFC2119] [RFC8174] when, and only when, they appear in all 65 capitals, as shown here. In this document, these words will appear 66 with that interpretation only when in UPPER CASE. Lower case uses of 67 these words are not to be interpreted as carrying [RFC2119] 68 significance. 70 2. Introduction 72 This document presents RACK-TLP, a TCP loss detection algorithm that 73 improves upon the widely implemented DUPACK counting approach in 74 [RFC5681][RFC6675], and that is RECOMMENDED to be used as an 75 alternative to that earlier approach. RACK-TLP has two parts: RACK 76 ("Recent ACKnowledgment") detects losses quickly using time-based 77 inferences derived from ACK feedback. TLP ("Tail Loss Probe") 78 triggers ACK feedback by quickly sending a probe segment, to avoid 79 retransmission timeout (RTO) events. 81 2.1. Background 83 In traditional TCP loss recovery algorithms [RFC5681][RFC6675], a 84 sender starts fast recovery when the number of DUPACKs received 85 exceeds a threshold (DupThresh) that defaults to 3 (this approach is 86 referred to as DUPACK-counting in the rest of the document). The 87 sender also halves the congestion window during the recovery. The 88 rationale behind the partial window reduction is that congestion does 89 not seem severe since ACK clocking is still maintained. The time 90 elapsed in fast recovery can be just one round-trip, e.g. if the 91 sender uses SACK-based recovery [RFC6675] and the number of lost 92 segments is small. 94 If fast recovery is not triggered, or triggers but fails to repair 95 all the losses, then the sender resorts to RTO recovery. The RTO 96 timer interval is conservatively the smoothed RTT (SRTT) plus four 97 times the RTT variation, and is lower bounded to 1 second [RFC6298]. 98 Upon RTO timer expiration, the sender retransmits the first 99 unacknowledged segment and resets the congestion window to the LOSS 100 WINDOW value (by default 1 full-size segment [RFC5681]). The 101 rationale behind the congestion window reset is that an entire flight 102 of data was lost, and the ACK clock was lost, so this deserves a 103 cautious response. The sender then retransmits the rest of the data 104 following the slow start algorithm [RFC5681]. The time elapsed in 105 RTO recovery is one RTO interval plus the number of round-trips 106 needed to repair all the losses. 108 2.2. Motivation 110 Fast Recovery is the preferred form of loss recovery because it can 111 potentially recover all losses in the time scale of a single round 112 trip, with only a fractional congestion window reduction. RTO 113 recovery and congestion window reset should ideally be the last 114 resort, only used when the entire flight is lost. However, in 115 addition to losing an entire flight of data, the following situations 116 can unnecessarily resort to RTO recovery with traditional TCP loss 117 recovery algorithms [RFC5681][RFC6675]: 119 1. Packet drops for short flows or at the end of an application data 120 flight. When the sender is limited by the application (e.g. 121 structured request/response traffic), segments lost at the end of 122 the application data transfer often can only be recovered by RTO. 123 Consider an example of losing only the last segment in a flight 124 of 100 segments. Lacking any DUPACK, the sender RTO expires and 125 reduces the congestion window to 1, and raises the congestion 126 window to just 2 after the loss repair is acknowledged. In 127 contrast, any single segment loss occurring between the first and 128 the 97th segment would result in fast recovery, which would only 129 cut the window in half. 131 1. Lost retransmissions. Heavy congestion or traffic policers can 132 cause retransmissions to be lost. Lost retransmissions cause a 133 resort to RTO recovery, since DUPACK-counting does not detect the 134 loss of the retransmissions. Then the slow start after RTO 135 recovery could cause burst losses again that severely degrades 136 performance [POLICER16]. 138 2. Packet reordering. Link-layer protocols (e.g., 802.11 block 139 ACK), link bonding, or routers' internal load-balancing (e.g., 140 ECMP) can deliver TCP segments out of order. The degree of such 141 reordering is usually within the order of the path round trip 142 time. If the reordering degree is beyond DupThresh, the DUPACK- 143 counting can cause a spurious fast recovery and unnecessary 144 congestion window reduction. To mitigate the issue, [RFC4653] 145 adjusts DupThresh to half of the inflight size to tolerate the 146 higher degree of reordering. However if more than half of the 147 inflight is lost, then the sender has to resort to RTO recovery. 149 3. RACK-TLP high-level design 151 RACK-TLP allows senders to recover losses more effectively in all 152 three scenarios described in the previous section. There are two 153 design principles behind RACK-TLP. The first principle is to detect 154 losses via ACK events as much as possible, to repair losses at round- 155 trip time-scales. The second principle is to gently probe the 156 network to solicit additional ACK feedback, to avoid RTO expiration 157 and subsequent congestion window reset. At a high level, the two 158 principles are implemented in RACK and TLP, respectively. 160 3.1. RACK: time-based loss inferences from ACKs 162 The rationale behind RACK is that if a segment is delivered out of 163 order, then the segments sent chronologically before that were either 164 lost or reordered. This concept is not fundamentally different from 165 [RFC5681][RFC6675][FACK]. RACK's key innovation is using per-segment 166 transmission timestamps and widely-deployed SACK [RFC2018] options to 167 conduct time-based inferences, instead of inferring losses by 168 counting ACKs or SACKed sequences. Time-based inferences are more 169 robust than DUPACK-counting approaches because they have no 170 dependence on flight size, and thus are effective for application- 171 limited traffic. 173 Conceptually, RACK puts a virtual timer for every data segment sent 174 (including retransmissions). Each timer expires dynamically based on 175 the latest RTT measurements plus an additional delay budget to 176 accommodate potential packet reordering (called the reordering 177 window). When a segment's timer expires, RACK marks the 178 corresponding segment lost for retransmission. 180 In reality, as an algorithm, RACK does not arm a timer for every 181 segment sent because it's not necessary. Instead the sender records 182 the most recent transmission time of every data segment sent, 183 including retransmissions. For each ACK received, the sender 184 calculates the latest RTT measurement (if eligible) and adjusts the 185 expiration time of every segment sent but not yet delivered. If a 186 segment has expired, RACK marks it lost. 188 Since the time-based logic of RACK applies equally to retransmissions 189 and original transmissions, it can detect lost retransmissions as 190 well. If a segment has been retransmitted but its most recent 191 (re)transmission timestamp has expired, then after a reordering 192 window it's marked lost. 194 3.2. TLP: sending one segment to probe losses quickly with RACK 196 RACK infers losses from ACK feedback; however, in some cases ACKs are 197 sparse, particularly when the inflight is small or when the losses 198 are high. In some challenging cases the last few segments in a 199 flight are lost. With [RFC5681] or [RFC6675] the sender's RTO would 200 expire and reset the congestion window, when in reality most of the 201 flight has been delivered. 203 Consider an example where a sender with a large congestion window 204 transmits 100 new data segments after an application write, and only 205 the last three segments are lost. Without RACK-TLP, the RTO expires, 206 the sender retransmits the first unacknowledged segment, and the 207 congestion window slow-starts from 1. After all the retransmits are 208 acknowledged the congestion window has been increased to 4. The 209 total delivery time for this application transfer is three RTTs plus 210 one RTO, a steep cost given that only a tiny fraction of the flight 211 was lost. If instead the losses had occurred three segments sooner 212 in the flight, then fast recovery would have recovered all losses 213 within one round-trip and would have avoided resetting the congestion 214 window. 216 Fast Recovery would be preferable in such scenarios; TLP is designed 217 to trigger the feedback RACK needed to enable that. After the last 218 (100th) segment was originally sent, TLP sends the next available 219 (new) segment or retransmits the last (highest-sequenced) segment in 220 two round-trips to probe the network, hence the name "Tail Loss 221 Probe". The successful delivery of the probe would solicit an ACK. 222 RACK uses this ACK to detect that the 98th and 99th segments were 223 lost, trigger fast recovery, and retransmit both successfully. The 224 total recovery time is four RTTs, and the congestion window is only 225 partially reduced instead of being fully reset. If the probe was 226 also lost then the sender would invoke RTO recovery resetting the 227 congestion window. 229 3.3. RACK-TLP: reordering resilience with a time threshold 231 3.3.1. Reordering design rationale 233 Upon receiving an ACK indicating an out-of-order data delivery, a 234 sender cannot tell immediately whether that out-of-order delivery was 235 a result of reordering or loss. It can only distinguish between the 236 two in hindsight if the missing sequence ranges are filled in later 237 without retransmission. Thus a loss detection algorithm needs to 238 budget some wait time -- a reordering window -- to try to 239 disambiguate packet reordering from packet loss. 241 The reordering window in the DUPACK-counting approach is implicitly 242 defined as the elapsed time to receive acknowledgements for 243 DupThresh-worth of out-of-order deliveries. This approach is 244 effective if the network reordering degree (in sequence distance) is 245 smaller than DupThresh and at least DupThresh segments after the loss 246 are acknowledged. For cases where the reordering degree is larger 247 than the default DupThresh of 3 packets, one alternative is to 248 dynamically adapt DupThresh based on the FlightSize (e.g., the sender 249 adjusts the DUPTRESH to half of the FlightSize). However, this does 250 not work well with the following two types of reordering: 252 1. Application-limited flights where the last non-full-sized segment 253 is delivered first and then the remaining full-sized segments in 254 the flight are delivered in order. This reordering pattern can 255 occur when segments traverse parallel forwarding paths. In such 256 scenarios the degree of reordering in packet distance is one 257 segment less than the flight size. 259 2. A flight of segments that are delivered partially out of order. 260 One cause for this pattern is wireless link-layer retransmissions 261 with an inadequate reordering buffer at the receiver. In such 262 scenarios, the wireless sender sends the data packets in order 263 initially, but some are lost and then recovered by link-layer 264 retransmissions; the wireless receiver delivers the TCP data 265 packets in the order they are received, due to the inadequate 266 reordering buffer. The random wireless transmission errors in 267 such scenarios cause the reordering degree, expressed in packet 268 distance, to have highly variable values up to the flight size. 270 In the above two cases the degree of reordering in packet distance is 271 highly variable, making DUPACK-counting approach ineffective 272 including dynamic adaptation variants like [RFC4653]. Instead the 273 degree of reordering in time difference in such cases is usually 274 within a single round-trip time. This is because the packets either 275 traverse slightly disjoint paths with similar propagation delays or 276 are repaired quickly by the local access technology. Hence, using a 277 time threshold instead of packet threshold strikes a middle ground, 278 allowing a bounded degree of reordering resilience while still 279 allowing fast recovery. This is the rationale behind the RACK-TLP 280 reordering resilience design. 282 Specifically, RACK-TLP introduces a new dynamic reordering window 283 parameter in time units, and the sender considers a data segment S 284 lost if both conditions are met: 286 1. Another data segment sent later than S has been delivered 287 2. S has not been delivered after the estimated round-trip time plus 288 the reordering window 290 Note that condition (1) implies at least one round-trip of time has 291 elapsed since S has been sent. 293 3.3.2. Reordering window adaptation 295 The RACK reordering window adapts to the measured duration of 296 reordering events, within reasonable and specific bounds to 297 disincentivize excessive reordering. More specifically, the sender 298 sets the reordering window as follows: 300 1. The reordering window SHOULD be set to zero if no reordering has 301 been observed on the connection so far, and either (a) three 302 segments have been delivered out of order since the last recovery 303 or (b) the sender is already in fast or RTO recovery. Otherwise, 304 the reordering window SHOULD start from a small fraction of the 305 round trip time, or zero if no round trip time estimate is 306 available. 308 2. The RACK reordering window SHOULD adaptively increase (using the 309 algorithm in "Step 4: Update RACK reordering window", below) if 310 the sender receives a Duplicate Selective Acknowledgement (DSACK) 311 option [RFC2883]. Receiving a DSACK suggests the sender made a 312 spurious retransmission, which may have been due to the 313 reordering window being too small. 315 3. The RACK reordering window MUST be bounded and this bound SHOULD 316 be SRTT. 318 Rules 2 and 3 are required to adapt to reordering caused by dynamics 319 such as the prolonged link-layer loss recovery episodes described 320 earlier. Each increase in the reordering window requires a new round 321 trip where the sender receives a DSACK; thus, depending on the extent 322 of reordering, it may take multiple round trips to fully adapt. 324 For short flows, the low initial reordering window helps recover 325 losses quickly, at the risk of spurious retransmissions. The 326 rationale is that spurious retransmissions for short flows are not 327 expected to produce excessive additional network traffic. For long 328 flows the design tolerates reordering within a round trip. This 329 handles reordering in small time scales (reordering within the round- 330 trip time of the shortest path). 332 However, the fact that the initial reordering window is low, and the 333 reordering window's adaptive growth is bounded, means that there will 334 continue to be a cost to reordering that disincentivizes excessive 335 reordering. 337 3.4. An Example of RACK-TLP in Action: fast recovery 339 The following example in figure 1 illustrates the RACK-TLP algorithm 340 in action: 342 Event TCP DATA SENDER TCP DATA RECEIVER 343 _____ ____________________________________________________________ 344 1. Send P0, P1, P2, P3 --> 345 [P1, P2, P3 dropped by network] 347 2. <-- Receive P0, ACK P0 349 3a. 2RTTs after (2), TLP timer fires 350 3b. TLP: retransmits P3 --> 352 4. <-- Receive P3, SACK P3 354 5a. Receive SACK for P3 355 5b. RACK: marks P1, P2 lost 356 5c. Retransmit P1, P2 --> 357 [P1 retransmission dropped by network] 359 6. <-- Receive P2, SACK P2 & P3 361 7a. RACK: marks P1 retransmission lost 362 7b. Retransmit P1 --> 364 8. <-- Receive P1, ACK P3 366 Figure 1. RACK-TLP protocol example 368 Figure 1, above, illustrates a sender sending four segments (P1, P2, 369 P3, P4) and losing the last three segments. After two round-trips, 370 TLP sends a loss probe, retransmitting the last segment, P3, to 371 solicit SACK feedback and restore the ACK clock (event 3). The 372 delivery of P3 enables RACK to infer (event 5b) that P1 and P2 were 373 likely lost, because they were sent before P3. The sender then 374 retransmits P1 and P2. Unfortunately, the retransmission of P1 is 375 lost again. However, the delivery of the retransmission of P2 allows 376 RACK to infer that the retransmission of P1 was likely lost (event 377 7a), and hence P1 should be retransmitted (event 7b). 379 3.5. An Example of RACK-TLP in Action: RTO 381 In addition to enhancing fast recovery, RACK improves the accuracy of 382 RTO recovery by reducing spurious retransmissions. 384 Without RACK, upon RTO timer expiration the sender marks all the 385 unacknowledged segments lost. This approach can lead to spurious 386 retransmissions. For example, consider a simple case where one 387 segment was sent with an RTO of 1 second, and then the application 388 writes more data, causing a second and third segment to be sent right 389 before the RTO of the first segment expires. Suppose only the first 390 segment is lost. Without RACK, upon RTO expiration the sender marks 391 all three segments as lost and retransmits the first segment. When 392 the sender receives the ACK that selectively acknowledges the second 393 segment, the sender spuriously retransmits the third segment. 395 With RACK, upon RTO timer expiration the only segment automatically 396 marked lost is the first segment (since it was sent an RTO ago); for 397 all the other segments RACK only marks the segment lost if at least 398 one round trip has elapsed since the segment was transmitted. 399 Consider the previous example scenario, this time with RACK. With 400 RACK, when the RTO expires the sender only marks the first segment as 401 lost, and retransmits that segment. The other two very recently sent 402 segments are not marked lost, because they were sent less than one 403 round trip ago and there were no ACKs providing evidence that they 404 were lost. When the sender receives the ACK that selectively 405 acknowledges the second segment, the sender would not retransmit the 406 third segment but rather would send any new segments (if allowed by 407 congestion window and receive window). 409 In the above example, if the sender were to send a large burst of 410 segments instead of two segments right before RTO, without RACK the 411 sender may spuriously retransmit almost the entire flight [RACK- 412 TCPM97]. Note that the Eifel protocol [RFC3522] cannot prevent this 413 issue because it can only detect spurious RTO episodes. In this 414 example the RTO itself was not spurious. 416 3.6. Design Summary 418 To summarize, RACK-TLP aims to adapt to small time-varying degrees of 419 reordering, quickly recover most losses within one to two round 420 trips, and avoid costly RTO recoveries. In the presence of 421 reordering, the adaptation algorithm can impose sometimes-needless 422 delays when it waits to disambiguate loss from reordering, but the 423 penalty for waiting is bounded to one round trip and such delays are 424 confined to flows long enough to have observed reordering. 426 4. Requirements 428 The reader is expected to be familiar with the definitions given in 429 the TCP congestion control [RFC5681] and selective acknowledgment 430 [RFC2018][RFC6675] RFCs. RACK-TLP has the following requirements: 432 1. The connection MUST use selective acknowledgment (SACK) options 433 [RFC2018], and the sender MUST keep SACK scoreboard information 434 on a per-connection basis ("SACK scoreboard" has the same meaning 435 here as in [RFC6675] section 3). 437 2. For each data segment sent, the sender MUST store its most recent 438 transmission time with a timestamp whose granularity that is 439 finer than 1/4 of the minimum RTT of the connection. At the time 440 of writing, microsecond resolution is suitable for intra- 441 datacenter traffic and millisecond granularity or finer is 442 suitable for the Internet. Note that RACK-TLP can be implemented 443 with TSO (TCP Segmentation Offload) support by having multiple 444 segments in a TSO aggregate share the same timestamp. 446 3. RACK DSACK-based reordering window adaptation is RECOMMENDED but 447 is not required. 449 4. TLP requires RACK. 451 5. Definitions 453 The reader is expected to be familiar with the variables of SND.UNA, 454 SND.NXT, SEG.ACK, and SEG.SEQ in [RFC793], SMSS, FlightSize in 455 [RFC5681], DupThresh in [RFC6675], RTO and SRTT in [RFC6298]. A 456 RACK-TLP implementation needs to store new per-segment and per- 457 connection state, described below. 459 5.1. Per-segment variables 461 Theses variables indicate the status of the most recent transmission 462 of a data segment: 464 "Segment.lost" is true if the most recent (re)transmission of the 465 segment has been marked lost and needs to be retransmitted. False 466 otherwise. 468 "Segment.retransmitted" is true if it was retransmitted in the most 469 recent transmission. False otherwise. 471 "Segment.xmit_ts" is the time of the last transmission of a data 472 segment, including retransmissions, if any, with a clock granularity 473 specified in the Requirements section. 475 "Segment.end_seq" is the next sequence number after the last sequence 476 number of the data segment. 478 5.2. Per-connection variables 480 "RACK.segment". Among all the segments that have been either 481 selectively or cumulatively acknowledged, RACK.segment is the one 482 that was sent most recently (including retransmissions). 484 "RACK.xmit_ts" is the latest transmission timestamp of RACK.segment. 486 "RACK.end_seq" is the Segment.end_seq of RACK.segment. 488 "RACK.ack_ts" is the time when the full sequence range of 489 RACK.segment was selectively or cumulatively acknowledged. 491 "RACK.segs_sacked" returns the total number of segments selectively 492 acknowledged in the SACK scoreboard. 494 "RACK.fack" is the highest selectively or cumulatively acknowledged 495 sequence (i.e. forward acknowledgement). 497 "RACK.min_RTT" is the estimated minimum round-trip time (RTT) of the 498 connection. 500 "RACK.rtt" is the RTT of the most recently delivered segment on the 501 connection (either cumulatively acknowledged or selectively 502 acknowledged) that was not marked invalid as a possible spurious 503 retransmission. 505 "RACK.reordering_seen" indicates whether the sender has detected data 506 segment reordering event(s). 508 "RACK.reo_wnd" is a reordering window computed in the unit of time 509 used for recording segment transmission times. It is used to defer 510 the moment at which RACK marks a segment lost. 512 "RACK.dsack" indicates if a DSACK option has been received since the 513 last RACK.reo_wnd change. 515 "RACK.reo_wnd_mult" is the multiplier applied to adjust RACK.reo_wnd. 517 "RACK.reo_wnd_persist" is the number of loss recoveries before 518 resetting RACK.reo_wnd. 520 "RACK.rtt_seq" is the SND.NXT when RACK.rtt is updated. 522 "TLP.is_retrans": a boolean indicating whether there is an 523 unacknowledged TLP retransmission. 525 "TLP.end_seq": the value of SND.NXT at the time of sending a TLP 526 retransmission. 528 "TLP.max_ack_delay": sender's maximum delayed ACK timer budget. 530 Per-connection timers 532 "RACK reordering timer": a timer that allows RACK to wait for 533 reordering to resolve, to try to disambiguate reordering from loss, 534 when some out-of-order segments are marked as SACKed. 536 "TLP PTO": a timer event indicating that an ACK is overdue and the 537 sender should transmit a TLP segment, to solicit SACK or ACK 538 feedback. 540 These timers augment the existing timers maintained by a sender, 541 including the RTO timer [RFC6298]. A RACK-TLP sender arms one of 542 these three timers -- RACK reordering timer, TLP PTO timer, or RTO 543 timer -- when it has unacknowledged segments in flight. The 544 implementation can simplify managing all three timers by multiplexing 545 a single timer among them with an additional variable to indicate the 546 event to invoke upon the next timer expiration. 548 6. RACK Algorithm Details 550 6.1. Upon transmitting a data segment 552 Upon transmitting a new segment or retransmitting an old segment, 553 record the time in Segment.xmit_ts and set Segment.lost to FALSE. 554 Upon retransmitting a segment, set Segment.retransmitted to TRUE. 556 RACK_transmit_data(Segment): 557 Segment.xmit_ts = Now() 558 Segment.lost = FALSE 560 RACK_retransmit_data(Segment): 561 Segment.retransmitted = TRUE 562 RACK_transmit_data(Segment) 564 6.2. Upon receiving an ACK 566 Step 1: Update RACK.min_RTT. 568 Use the RTT measurements obtained via [RFC6298] or [RFC7323] to 569 update the estimated minimum RTT in RACK.min_RTT. The sender SHOULD 570 track a windowed min-filtered estimate of recent RTT measurements 571 that can adapt when migrating to significantly longer paths, rather 572 than a simple global minimum of all RTT measurements. 574 Step 2: Update state for most recently sent segment that has been 575 delivered 577 In this step, RACK updates the states that track the most recently 578 sent segment that has been delivered: RACK.segment; RACK maintains 579 its latest transmission timestamp in RACK.xmit_ts and its highest 580 sequence number in RACK.end_seq. These two variables are used, in 581 later steps, to estimate if some segments not yet delivered were 582 likely lost. Given the information provided in an ACK, each segment 583 cumulatively ACKed or SACKed is marked as delivered in the 584 scoreboard. Since an ACK can also acknowledge retransmitted data 585 segments, and retransmissions can be spurious, the sender needs to 586 take care to avoid spurious inferences. For example, if the sender 587 were to use timing information from a spurious retransmission, the 588 RACK.rtt could be vastly underestimated. 590 To avoid spurious inferences, ignore a segment as invalid if any of 591 its sequence range has been retransmitted before and either of two 592 conditions is true: 594 1. The Timestamp Echo Reply field (TSecr) of the ACK's timestamp 595 option [RFC7323], if available, indicates the ACK was not 596 acknowledging the last retransmission of the segment. 598 2. The segment was last retransmitted less than RACK.min_rtt ago. 600 The second check is a heuristic when the TCP Timestamp option is not 601 available, or when the round trip time is less than the TCP Timestamp 602 clock granularity. 604 Among all the segments newly ACKed or SACKed by this ACK that pass 605 the checks above, update the RACK.rtt to be the RTT sample calculated 606 using this ACK. Furthermore, record the most recent Segment.xmit_ts 607 in RACK.xmit_ts if it is ahead of RACK.xmit_ts. If Segment.xmit_ts 608 equals RACK.xmit_ts (e.g. due to clock granularity limits) then 609 compare Segment.end_seq and RACK.end_seq to break the tie. 611 Step 2 may be summarized in pseudocode as: 613 RACK_sent_after(t1, seq1, t2, seq2): 614 If t1 > t2: 615 Return true 616 Else if t1 == t2 AND seq1 > seq2: 617 Return true 618 Else: 619 Return false 621 RACK_update(): 622 For each Segment newly acknowledged cumulatively or selectively: 623 rtt = Now() - Segment.xmit_ts 624 If Segment.retransmitted is TRUE: 625 If ACK.ts_option.echo_reply < Segment.xmit_ts: 626 Return 627 If rtt < RACK.min_rtt: 628 Return 630 RACK.rtt = rtt 631 If RACK_sent_after(Segment.xmit_ts, Segment.end_seq 632 RACK.xmit_ts, RACK.end_seq): 633 RACK.xmit_ts = Segment.xmit_ts 635 Step 3: Detect data segment reordering 637 To detect reordering, the sender looks for original data segments 638 being delivered out of order. To detect such cases, the sender 639 tracks the highest sequence selectively or cumulatively acknowledged 640 in the RACK.fack variable. The name "fack" stands for the most 641 "Forward ACK" (this term is adopted from [FACK]). If a never- 642 retransmitted segment that's below RACK.fack is (selectively or 643 cumulatively) acknowledged, it has been delivered out of order. The 644 sender sets RACK.reordering_seen to TRUE if such segment is 645 identified. 647 RACK_detect_reordering(): 648 For each Segment newly acknowledged cumulatively or selectively: 649 If Segment.end_seq > RACK.fack: 650 RACK.fack = Segment.end_seq 651 Else if Segment.end_seq < RACK.fack AND 652 Segment.retransmitted is FALSE: 653 RACK.reordering_seen = TRUE 655 Step 4: Update RACK reordering window 657 The RACK reordering window, RACK.reo_wnd, serves as an adaptive 658 allowance for settling time before marking a segment lost. This step 659 documents a detailed algorithm that follows the principles outlined 660 in the ``Reordering window adaptation'' section. 662 If the sender has not yet observed any reordering based on the 663 previous step, then RACK prioritizes quick loss recovery by using 664 setting RACK.reo_wnd to 0 when the number of SACKed segments exceeds 665 DupThresh, or during loss recovery. 667 Aside from those special conditions, RACK starts with a conservative 668 reordering window of RACK.min_RTT/4. This value was chosen because 669 Linux TCP used the same factor in its implementation to delay Early 670 Retransmit [RFC5827] to reduce spurious loss detections in the 671 presence of reordering, and experience showed this worked reasonably 672 well [DMCG11]. 674 However, the reordering detection in the previous step, Step 3, has a 675 self-reinforcing drawback when the reordering window is too small to 676 cope with the actual reordering. When that happens, RACK could 677 spuriously mark reordered segments lost, causing them to be 678 retransmitted. In turn, the retransmissions can prevent the 679 necessary conditions for Step 3 to detect reordering, since this 680 mechanism requires ACKs or SACKs for only segments that have never 681 been retransmitted. In some cases such scenarios can persist, 682 causing RACK to continue to spuriously mark segments lost without 683 realizing the reordering window is too small. 685 To avoid the issue above, RACK dynamically adapts to higher degrees 686 of reordering using DSACK options from the receiver. Receiving an 687 ACK with a DSACK option indicates a spurious retransmission, 688 suggesting that RACK.reo_wnd may be too small. The RACK.reo_wnd 689 increases linearly for every round trip in which the sender receives 690 some DSACK option, so that after N distinct round trips in which a 691 DSACK is received, the RACK.reo_wnd becomes (N+1) * min_RTT / 4, with 692 an upper-bound of SRTT. 694 If the reordering is temporary then a large adapted reordering window 695 would unnecessarily delay loss recovery later. Therefore, RACK 696 persists using the inflated RACK.reo_wnd for up to 16 loss 697 recoveries, after which it resets RACK.reo_wnd to its starting value, 698 min_RTT / 4. The downside of resetting the reordering window is the 699 risk of triggering spurious fast recovery episodes if the reordering 700 remains high. The rationale for this approach is to bound such 701 spurious recoveries to approximately once every 16 recoveries (less 702 than 7%). 704 To track the linear scaling factor for the adaptive reordering 705 window, RACK uses the variable RACK.reo_wnd_mult, which is 706 initialized to 1 and adapts with the following pseudocode, which 707 implements the above algorithm: 709 RACK_update_reo_wnd(): 711 /* DSACK-based reordering window adaptation */ 712 If RACK.dsack_round is not None AND 713 SND.UNA >= RACK.dsack_round: 714 RACK.dsack_round = None 715 /* Grow the reordering window per round that sees DSACK. 716 Reset the window after 16 DSACK-free recoveries */ 717 If RACK.dsack_round is None AND 718 any DSACK option is present on latest received ACK: 719 RACK.dsack_round = SND.NXT 720 RACK.reo_wnd_mult += 1 721 RACK.reo_wnd_persist = 16 722 Else if exiting Fast or RTO recovery: 723 RACK.reo_wnd_persist -= 1 724 If RACK.reo_wnd_persist <= 0: 725 RACK.reo_wnd_mult = 1 727 If RACK.reordering_seen is FALSE: 728 If in Fast or RTO recovery: 729 Return 0 730 Else if RACK.segs_sacked >= DupThresh: 731 Return 0 732 Return min(RACK.min_RTT / 4 * RACK.reo_wnd_mult, SRTT) 734 Step 5: Detect losses. 736 For each segment that has not been SACKed, RACK considers that 737 segment lost if another segment that was sent later has been 738 delivered, and the reordering window has passed. RACK considers the 739 reordering window to have passed if the RACK.segment was sent 740 sufficiently after the segment in question, or a sufficient time has 741 elapsed since the RACK.segment was S/ACKed, or some combination of 742 the two. More precisely, RACK marks a segment lost if: 744 RACK.xmit_ts >= Segment.xmit_ts 745 AND 746 (RACK.xmit_ts - Segment.xmit_ts) + (now - RACK.ack_ts) >= RACK.reo_wnd 748 Solving this second condition for "now", the moment at which a 749 segment is marked lost, yields: 751 now >= Segment.xmit_ts + RACK.reo_wnd + (RACK.ack_ts - RACK.xmit_ts) 753 Then (RACK.ack_ts - RACK.xmit_ts) is the round trip time of the most 754 recently (re)transmitted segment that's been delivered. When 755 segments are delivered in order, the most recently (re)transmitted 756 segment that's been delivered is also the most recently delivered, 757 hence RACK.rtt == RACK.ack_ts - RACK.xmit_ts. But if segments were 758 reordered, then the segment delivered most recently was sent before 759 the most recently (re)transmitted segment. Hence RACK.rtt > 760 (RACK.ack_ts - RACK.xmit_ts). 762 Since RACK.RTT >= (RACK.ack_ts - RACK.xmit_ts), the previous equation 763 reduces to saying that the sender can declare a segment lost when: 765 now >= Segment.xmit_ts + RACK.reo_wnd + RACK.rtt 767 In turn, that is equivalent to stating that a RACK sender should 768 declare a segment lost when: 770 Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - now <= 0 772 Note that if the value on the left hand side is positive, it 773 represents the remaining wait time before the segment is deemed lost. 774 But this risks a timeout (RTO) if no more ACKs come back (e.g., due 775 to losses or application-limited transmissions) to trigger the 776 marking. For timely loss detection, the sender is RECOMMENDED to 777 install a reordering timer. This timer expires at the earliest 778 moment when RACK would conclude that all the unacknowledged segments 779 within the reordering window were lost. 781 The following pseudocode implements the algorithm above. When an ACK 782 is received or the RACK reordering timer expires, call 783 RACK_detect_loss_and_arm_timer(). The algorithm breaks timestamp 784 ties by using the TCP sequence space, since high-speed networks often 785 have multiple segments with identical timestamps. 787 RACK_detect_loss(): 788 timeout = 0 789 RACK.reo_wnd = RACK_update_reo_wnd() 790 For each segment, Segment, not acknowledged yet: 791 If Segment.lost is TRUE AND Segment.retransmitted is FALSE: 792 Continue /* Segment lost but not yet retransmitted */ 794 If RACK_sent_after(RACK.xmit_ts, RACK.end_seq, 795 Segment.xmit_ts, Segment.end_seq): 796 remaining = Segment.xmit_ts + RACK.rtt + 797 RACK.reo_wnd - Now() 798 If remaining <= 0: 799 Segment.lost = TRUE 800 Else: 801 timeout = max(remaining, timeout) 802 Return timeout 804 RACK_detect_loss_and_arm_timer(): 805 timeout = RACK_detect_loss() 806 If timeout != 0 807 Arm the RACK timer to call 808 RACK_detect_loss_and_arm_timer() after timeout 810 As an optimization, an implementation can choose to check only 811 segments that have been sent before RACK.xmit_ts. This can be more 812 efficient than scanning the entire SACK scoreboard, especially when 813 there are many segments in flight. The implementation can use a 814 separate doubly-linked list ordered by Segment.xmit_ts and inserts a 815 segment at the tail of the list when it is (re)transmitted, and 816 removes a segment from the list when it is delivered or marked lost. 817 In Linux TCP this optimization improved CPU usage by orders of 818 magnitude during some fast recovery episodes on high-speed WAN 819 networks. 821 6.3. Upon RTO expiration 823 Upon RTO timer expiration, RACK marks the first outstanding segment 824 as lost (since it was sent an RTO ago); for all the other segments 825 RACK only marks the segment lost if the time elapsed since the 826 segment was transmitted is at least the sum of the recent RTT and the 827 reordering window. 829 RACK_mark_losses_on_RTO(): 830 For each segment, Segment, not acknowledged yet: 831 If SEG.SEQ == SND.UNA OR 832 Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - Now() <= 0: 833 Segment.lost = TRUE 835 7. TLP Algorithm Details 837 7.1. Initializing state 839 Reset TLP.is_retrans and TLP.end_seq when initiating a connection, 840 fast recovery, or RTO recovery. 842 TLP_init(): 843 TLP.end_seq = None 844 TLP.is_retrans = false 846 7.2. Scheduling a loss probe 848 The sender schedules a loss probe timeout (PTO) to transmit a segment 849 during the normal transmission process. The sender SHOULD start or 850 restart a loss probe PTO timer after transmitting new data (that was 851 not itself a loss probe) or upon receiving an ACK that cumulatively 852 acknowledges new data, unless it is already in fast recovery, RTO 853 recovery, or the sender has segments delivered out-of-order (i.e. 854 RACK.segs_sacked is not zero). These conditions are excluded because 855 they are addressed by similar mechanisms, like Limited Transmit 856 [RFC3042], the RACK reordering timer, and F-RTO [RFC5682]. 858 The sender calculates the PTO interval by taking into account a 859 number of factors. 861 First, the default PTO interval is 2*SRTT. By that time, it is 862 prudent to declare that an ACK is overdue, since under normal 863 circumstances, i.e. no losses, an ACK typically arrives in one SRTT. 864 Choosing PTO to be exactly an SRTT would risk causing spurious 865 probes, given that network and end-host delay variance can cause an 866 ACK to be delayed beyond SRTT. Hence the PTO is conservatively 867 chosen to be the next integral multiple of SRTT. 869 Second, when there is no SRTT estimate available, the PTO SHOULD be 1 870 second. This conservative value corresponds to the RTO value when no 871 SRTT is available, per [RFC6298]. 873 Third, when FlightSize is one segment, the sender MAY inflate PTO by 874 TLP.max_ack_delay to accommodate a potential delayed acknowledgment 875 and reduce the risk of spurious retransmissions. The actual value of 876 TLP.max_ack_delay is implementation-specific. 878 Finally, if the time at which an RTO would fire (here denoted 879 "TCP_RTO_expiration()") is sooner than the computed time for the PTO, 880 then the sender schedules a TLP to be sent at that RTO time. 882 Summarizing these considerations in pseudocode form, a sender SHOULD 883 use the following logic to select the duration of a PTO: 885 TLP_calc_PTO(): 886 If SRTT is available: 887 PTO = 2 * SRTT 888 If FlightSize is one segment: 889 PTO += TLP.max_ack_delay 890 Else: 891 PTO = 1 sec 893 If Now() + PTO > TCP_RTO_expiration(): 894 PTO = TCP_RTO_expiration() - Now() 896 7.3. Sending a loss probe upon PTO expiration 898 When the PTO timer expires, the sender SHOULD transmit a previously 899 unsent data segment, if the receive window allows, and increment the 900 FlightSize accordingly. Note that FlightSize could be one packet 901 greater than the congestion window temporarily until the next ACK 902 arrives. 904 If such a segment is not available, then the sender SHOULD retransmit 905 the highest-sequence segment sent so far and set TLP.is_retrans to 906 true. This segment is chosen to deal with the retransmission 907 ambiguity problem in TCP. Suppose a sender sends N segments, and 908 then retransmits the last segment (segment N) as a loss probe, and 909 then the sender receives a SACK for segment N. As long as the sender 910 waits for the RACK reordering window to expire, it doesn't matter if 911 that SACK was for the original transmission of segment N or the TLP 912 retransmission; in either case the arrival of the SACK for segment N 913 provides evidence that the N-1 segments preceding segment N were 914 likely lost. 916 In the case where there is only one original outstanding segment of 917 data (N=1), the same logic (trivially) applies: an ACK for a single 918 outstanding segment tells the sender the N-1=0 segments preceding 919 that segment were lost. Furthermore, whether there are N>1 or N=1 920 outstanding segments, there is a question about whether the original 921 last segment or its TLP retransmission were lost; the sender 922 estimates whether there was such a loss using TLP recovery detection 923 (see below). 925 The sender MUST follow the RACK transmission procedures in the ''Upon 926 Transmitting a Data Segment'' section (see above) upon sending either 927 a retransmission or new data loss probe. This is critical for 928 detecting losses using the ACK for the loss probe. Furthermore, 929 prior to sending a loss probe, the sender MUST check that there is no 930 other previous loss probe still in flight. This ensures that at any 931 given time the sender has at most one additional packet in flight 932 beyond the congestion window limit. This invariant is maintained 933 using the state variable TLP.end_seq, which indicates the latest 934 unacknowledged TLP loss probe's ending sequence. It is reset when 935 the loss probe has been acknowledged or is deemed lost or irrelevant. 936 After attempting to send a loss probe, regardless of whether a loss 937 probe was sent, the sender MUST re-arm the RTO timer, not the PTO 938 timer, if FlightSize is not zero. This ensures RTO recovery remains 939 the last resort if TLP fails. The following pseudo code summarizes 940 the operations. 942 TLP_send_probe(): 944 If TLP.end_seq is None: 945 TLP.is_retrans = false 946 Segment = send buffer segment starting at SND.NXT 947 If Segment exists and fits the peer receive window limit: 948 /* Transmit the lowest-sequence unsent Segment */ 949 Transmit Segment 950 RACK_transmit_data(Segment) 951 TLP.end_seq = SND.NXT 952 Increase FlightSize by Segment length 953 Else: 954 /* Retransmit the highest-sequence Segment sent */ 955 Segment = send buffer segment ending at SND.NXT 956 Transmit Segment 957 RACK_retransmit_data(Segment) 958 TLP.end_seq = SND.NXT 960 7.4. Detecting losses by the ACK of the loss probe 962 When there is packet loss in a flight ending with a loss probe, the 963 feedback solicited by a loss probe will reveal one of two scenarios, 964 depending on the pattern of losses. 966 7.4.1. General case: detecting packet losses using RACK 968 If the loss probe and the ACK that acknowledges the probe are 969 delivered successfully, RACK-TLP uses this ACK -- just as it would 970 with any other ACK -- to detect if any segments sent prior to the 971 probe were dropped. RACK would typically infer that any 972 unacknowledged data segments sent before the loss probe were lost, 973 since they were sent sufficiently far in the past (at least one PTO 974 has elapsed, plus one round-trip for the loss probe to be ACKed). 975 More specifically, RACK_detect_loss() (step 5) would mark those 976 earlier segments as lost. Then the sender would trigger a fast 977 recovery to recover those losses. 979 7.4.2. Special case: detecting a single loss repaired by the loss probe 981 If the TLP retransmission repairs all the lost in-flight sequence 982 ranges (i.e. only the last segment in the flight was lost), the ACK 983 for the loss probe appears to be a regular cumulative ACK, which 984 would not normally trigger the congestion control response to this 985 packet loss event. The following TLP recovery detection mechanism 986 examines ACKs to detect this special case to make congestion control 987 respond properly [RFC5681]. 989 After a TLP retransmission, the sender checks for this special case 990 of a single loss that is recovered by the loss probe itself. To 991 accomplish this, the sender checks for a duplicate ACK or DSACK 992 indicating that both the original segment and TLP retransmission 993 arrived at the receiver, meaning there was no loss. If the TLP 994 sender does not receive such an indication, then it MUST assume that 995 either the original data segment, the TLP retransmission, or a 996 corresponding ACK were lost, for congestion control purposes. 998 If the TLP retransmission is spurious, a receiver that uses DSACK 999 would return an ACK that covers TLP.end_seq with a DSACK option (Case 1000 1). If the receiver does not support DSACK, it would return a DUPACK 1001 without any SACK option (Case 2). If the sender receives an ACK 1002 matching either case, then the sender estimates that the receiver 1003 received both the original data segment and the TLP probe 1004 retransmission, and so the sender considers the TLP episode to be 1005 done, and records that fact by setting TLP.end_seq to None. 1007 Upon receiving an ACK that covers some sequence number after 1008 TLP.end_seq, the sender should have received any ACKs for the 1009 original segment and TLP probe retransmission segment. At that time, 1010 if the TLP.end_seq is still set, and thus indicates that the TLP 1011 probe retransmission remains unacknowledged, then the sender should 1012 presume that at least one of its data segments was lost. The sender 1013 then SHOULD invoke a congestion control response equivalent to a fast 1014 recovery. 1016 More precisely, on each ACK the sender executes the following: 1018 TLP_process_ack(ACK): 1019 If TLP.end_seq is not None AND ACK.seq >= TLP.end_seq: 1020 If not TLP.is_retrans: 1021 TLP.end_seq = None /* TLP of new data delivered */ 1022 Else if ACK has a DSACK option matching TLP.end_seq: 1023 TLP.end_seq = None /* Case 1, above */ 1024 Else If SEG.ACK > TLP.end_seq: 1025 TLP.end_seq = None /* Repaired the single loss */ 1026 (Invoke congestion control to react to 1027 the loss event the probe has repaired) 1028 Else If ACK is a DUPACK without any SACK option: 1029 TLP.end_seq = None /* Case 2, above */ 1031 8. Managing RACK-TLP timers 1033 The RACK reordering, the TLP PTO timer, the RTO and Zero window probe 1034 (ZWP) timer [RFC793] are mutually exclusive and used in different 1035 scenarios. When arming a RACK reordering timer or TLP PTO timer, the 1036 sender SHOULD cancel any other pending timer(s). An implementation 1037 is to have one timer with an additional state variable indicating the 1038 type of the timer. 1040 9. Discussion 1042 9.1. Advantages and disadvantages 1044 The biggest advantage of RACK-TLP is that every data segment, whether 1045 it is an original data transmission or a retransmission, can be used 1046 to detect losses of the segments sent chronologically prior to it. 1047 This enables RACK-TLP to use fast recovery in cases with application- 1048 limited flights of data, lost retransmissions, or data segment 1049 reordering events. Consider the following examples: 1051 1. Packet drops at the end of an application data flight: Consider a 1052 sender that transmits an application-limited flight of three data 1053 segments (P1, P2, P3), and P1 and P3 are lost. Suppose the 1054 transmission of each segment is at least RACK.reo_wnd after the 1055 transmission of the previous segment. RACK will mark P1 as lost 1056 when the SACK of P2 is received, and this will trigger the 1057 retransmission of P1 as R1. When R1 is cumulatively 1058 acknowledged, RACK will mark P3 as lost and the sender will 1059 retransmit P3 as R3. This example illustrates how RACK is able 1060 to repair certain drops at the tail of a transaction without an 1061 RTO recovery. Notice that neither the conventional duplicate ACK 1062 threshold [RFC5681], nor [RFC6675], nor the Forward 1063 Acknowledgment [FACK] algorithm can detect such losses, because 1064 of the required segment or sequence count. 1066 2. Lost retransmission: Consider a flight of three data segments 1067 (P1, P2, P3) that are sent; P1 and P2 are dropped. Suppose the 1068 transmission of each segment is at least RACK.reo_wnd after the 1069 transmission of the previous segment. When P3 is SACKed, RACK 1070 will mark P1 and P2 lost and they will be retransmitted as R1 and 1071 R2. Suppose R1 is lost again but R2 is SACKed; RACK will mark R1 1072 lost and trigger retransmission again. Again, neither the 1073 conventional three duplicate ACK threshold approach, nor 1074 [RFC6675], nor the Forward Acknowledgment [FACK] algorithm can 1075 detect such losses. And such a lost retransmission can happen 1076 when TCP is being rate-limited, particularly by token bucket 1077 policers with large bucket depth and low rate limit; in such 1078 cases retransmissions are often lost repeatedly because standard 1079 congestion control requires multiple round trips to reduce the 1080 rate below the policed rate. 1082 3. Packet reordering: Consider a simple reordering event where a 1083 flight of segments are sent as (P1, P2, P3). P1 and P2 carry a 1084 full payload of MSS octets, but P3 has only a 1-octet payload. 1085 Suppose the sender has detected reordering previously and thus 1086 RACK.reo_wnd is min_RTT/4. Now P3 is reordered and delivered 1087 first, before P1 and P2. As long as P1 and P2 are delivered 1088 within min_RTT/4, RACK will not consider P1 and P2 lost. But if 1089 P1 and P2 are delivered outside the reordering window, then RACK 1090 will still spuriously mark P1 and P2 lost. 1092 The examples above show that RACK-TLP is particularly useful when the 1093 sender is limited by the application, which can happen with 1094 interactive or request/response traffic. Similarly, RACK still works 1095 when the sender is limited by the receive window, which can happen 1096 with applications that use the receive window to throttle the sender. 1098 RACK-TLP works more efficiently with TCP Segmentation Offload (TSO) 1099 compared to DUPACK-counting. RACK always marks the entire TSO 1100 aggregate lost because the segments in the same TSO aggregate have 1101 the same transmission timestamp. By contrast, the algorithms based 1102 on sequence counting (e.g., [RFC6675][RFC5681]) may mark only a 1103 subset of segments in the TSO aggregate lost, forcing the stack to 1104 perform expensive fragmentation of the TSO aggregate, or to 1105 selectively tag individual segments lost in the scoreboard. 1107 The main drawback of RACK-TLP is the additional states required 1108 compared to DUPACK-counting. RACK requires the sender to record the 1109 transmission time of each segment sent at a clock granularity that is 1110 finer than 1/4 of the minimum RTT of the connection. TCP 1111 implementations that record this already for RTT estimation do not 1112 require any new per-packet state. But implementations that are not 1113 yet recording segment transmission times will need to add per-packet 1114 internal state (expected to be either 4 or 8 octets per segment or 1115 TSO aggregate) to track transmission times. In contrast, [RFC6675] 1116 loss detection approach does not require any per-packet state beyond 1117 the SACK scoreboard; this is particularly useful on ultra-low RTT 1118 networks where the RTT may be less than the sender TCP clock 1119 granularity (e.g. inside data-centers). Another disadvantage is the 1120 reordering timer may expire prematurely (like any other 1121 retransmission timer) to cause higher spurious retransmission 1122 especially if DSACK is not supported. 1124 9.2. Relationships with other loss recovery algorithms 1126 The primary motivation of RACK-TLP is to provide a general 1127 alternative to some of the standard loss recovery algorithms 1128 [RFC5681][RFC6675][RFC5827][RFC4653]. [RFC5827][RFC4653] dynamically 1129 adjusts the duplicate ACK threshold based on the current or previous 1130 flight sizes. RACK-TLP takes a different approach by using a time- 1131 based reordering window. RACK-TLP can be seen as an extended Early 1132 Retransmit [RFC5827] without a FlightSize limit but with an 1133 additional reordering window. [FACK] considers an original segment 1134 to be lost when its sequence range is sufficiently far below the 1135 highest SACKed sequence. In some sense RACK-TLP can be seen as a 1136 generalized form of FACK that operates in time space instead of 1137 sequence space, enabling it to better handle reordering, application- 1138 limited traffic, and lost retransmissions. 1140 RACK-TLP is compatible with the standard RTO [RFC6298], RTO-restart 1141 [RFC7765], F-RTO [RFC5682] and Eifel algorithms [RFC3522]. This is 1142 because RACK-TLP only detects loss by using ACK events. It neither 1143 changes the RTO timer calculation nor detects spurious RTO. 1145 9.3. Interaction with congestion control 1147 RACK-TLP intentionally decouples loss detection from congestion 1148 control. RACK-TLP only detects losses; it does not modify the 1149 congestion control algorithm [RFC5681][RFC6937]. A segment marked 1150 lost by RACK-TLP MUST NOT be retransmitted until congestion control 1151 deems this appropriate. 1153 The only exception -- the only way in which RACK-TLP modulates the 1154 congestion control algorithm -- is that one outstanding loss probe 1155 can be sent even if the congestion window is fully used. However, 1156 this temporary over-commit is accounted for and credited in the in- 1157 flight data tracked for congestion control, so that congestion 1158 control will erase the over-commit upon the next ACK. 1160 If packet losses happen after the reordering window has been 1161 increased by DSACK, RACK-TLP may take longer to detect losses than 1162 the pure DUPACK-counting approach. In this case TCP may continue to 1163 increase the congestion window upon receiving ACKs during this time, 1164 making the sender more aggressive. 1166 The following simple example compares how RACK-TLP and non-RACK-TLP 1167 loss detection interacts with congestion control: suppose a sender 1168 has a congestion window (cwnd) of 20 segments on a SACK-enabled 1169 connection. It sends 10 data segments and all of them are lost. 1171 Without RACK-TLP, the sender would time out, reset cwnd to 1, and 1172 retransmit the first segment. It would take four round trips (1 + 2 1173 + 4 + 3 = 10) to retransmit all the 10 lost segments using slow 1174 start. The recovery latency would be RTO + 4*RTT, with an ending 1175 cwnd of 4 segments due to congestion window validation. 1177 With RACK-TLP, a sender would send the TLP after 2*RTT and get a 1178 DUPACK, enabling RACK to detect the losses and trigger fast recovery. 1179 If the sender implements Proportional Rate Reduction [RFC6937] it 1180 would slow start to retransmit the remaining 9 lost segments since 1181 the number of segments in flight (0) is lower than the slow start 1182 threshold (10). The slow start would again take four round trips (1 1183 + 2 + 4 + 3 = 10) to retransmit all the lost segments. The recovery 1184 latency would be 2*RTT + 4*RTT, with an ending cwnd set to the slow 1185 start threshold of 10 segments. 1187 The difference in recovery latency (RTO + 4*RTT vs 6*RTT) can be 1188 significant if the RTT is much smaller than the minimum RTO (1 second 1189 in [RFC6298]) or if the RTT is large. The former case can happen in 1190 local area networks, data-center networks, or content distribution 1191 networks with deep deployments. The latter case can happen in 1192 developing regions with highly congested and/or high-latency 1193 networks. 1195 9.4. TLP recovery detection with delayed ACKs 1197 Delayed or stretched ACKs complicate the detection of repairs done by 1198 TLP, since with such ACKs the sender takes longer time to receive 1199 fewer ACKs than would normally be expected. To mitigate this 1200 complication, before sending a TLP loss probe retransmission, the 1201 sender should attempt to wait long enough that the receiver has sent 1202 any delayed ACKs that it is withholding. The sender algorithm 1203 described above features such a delay, in the form of 1204 TLP.max_ack_delay. Furthermore, if the receiver supports DSACK then 1205 in the case of a delayed ACK the sender's TLP recovery detection 1206 mechanism (see above) can use the DSACK information to infer that the 1207 original and TLP retransmission both arrived at the receiver. 1209 If there is ACK loss or a delayed ACK without a DSACK, then this 1210 algorithm is conservative, because the sender will reduce the 1211 congestion window when in fact there was no packet loss. In practice 1212 this is acceptable, and potentially even desirable: if there is 1213 reverse path congestion then reducing the congestion window can be 1214 prudent. 1216 9.5. RACK for other transport protocols 1218 RACK can be implemented in other transport protocols (e.g., [QUIC- 1219 LR]). The [Sprout] loss detection algorithm was also independently 1220 designed to use a 10ms reordering window to improve its loss 1221 detection. 1223 10. Security Considerations 1225 RACK-TLP algorithm behavior is based on information conveyed in SACK 1226 options, so it has security considerations similar to those described 1227 in the Security Considerations section of [RFC6675]. 1229 Additionally, RACK-TLP has a lower risk profile than [RFC6675] 1230 because it is not vulnerable to ACK-splitting attacks [SCWA99]: for 1231 an MSS-size segment sent, the receiver or the attacker might send MSS 1232 ACKs that SACK or acknowledge one additional byte per ACK. This 1233 would not fool RACK. In such a scenario, RACK.xmit_ts would not 1234 advance, because all the sequence ranges within the segment were 1235 transmitted at the same time, and thus carry the same transmission 1236 timestamp. In other words, SACKing only one byte of a segment or 1237 SACKing the segment in entirety have the same effect with RACK. 1239 11. IANA Considerations 1241 This document makes no request of IANA. 1243 Note to RFC Editor: this section may be removed on publication as an 1244 RFC. 1246 12. Acknowledgments 1248 The authors thank Matt Mathis for his insights in FACK and Michael 1249 Welzl for his per-packet timer idea that inspired this work. Eric 1250 Dumazet, Randy Stewart, Van Jacobson, Ian Swett, Rick Jones, Jana 1251 Iyengar, Hiren Panchasara, Praveen Balasubramanian, Yoshifumi 1252 Nishida, Bob Briscoe, Felix Weinrank, Michael Tuexen, Martin Duke, 1253 Ilpo Jarvinen, Theresa Enghardt, Mirja Kuehlewind, Gorry Fairhurst, 1254 and Yi Huang contributed to the draft or the implementations in 1255 Linux, FreeBSD, Windows, and QUIC. 1257 13. References 1259 13.1. Normative References 1261 [RFC2018] Mathis, M. and J. Mahdavi, "TCP Selective Acknowledgment 1262 Options", RFC 2018, October 1996. 1264 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1265 Requirement Levels", RFC 2119, March 1997. 1267 [RFC2883] Floyd, S., Mahdavi, J., Mathis, M., and M. Podolsky, "An 1268 Extension to the Selective Acknowledgement (SACK) Option 1269 for TCP", RFC 2883, July 2000. 1271 [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion 1272 Control", RFC 5681, September 2009. 1274 [RFC6298] Paxson, V., Allman, M., Chu, J., and M. Sargent, 1275 "Computing TCP's Retransmission Timer", RFC 6298, June 1276 2011. 1278 [RFC6675] Blanton, E., Allman, M., Wang, L., Jarvinen, I., Kojo, M., 1279 and Y. Nishida, "A Conservative Loss Recovery Algorithm 1280 Based on Selective Acknowledgment (SACK) for TCP", 1281 RFC 6675, August 2012. 1283 [RFC7323] Borman, D., Braden, B., Jacobson, V., and R. 1284 Scheffenegger, "TCP Extensions for High Performance", 1285 September 2014. 1287 [RFC793] Postel, J., "Transmission Control Protocol", September 1288 1981. 1290 13.2. Informative References 1292 [FACK] Mathis, M. and M. Jamshid, "Forward acknowledgement: 1293 refining TCP congestion control", ACM SIGCOMM Computer 1294 Communication Review, Volume 26, Issue 4, Oct. 1996. , 1295 1996. 1297 [POLICER16] 1298 Flach, T., Papageorge, P., Terzis, A., Pedrosa, L., Cheng, 1299 Y., Karim, T., Katz-Bassett, E., and R. Govindan, "An 1300 Analysis of Traffic Policing in the Web", ACM SIGCOMM , 1301 2016. 1303 [QUIC-LR] Iyengar, J. and I. Swett, "QUIC Loss Recovery And 1304 Congestion Control", draft-ietf-quic-recovery-latest (work 1305 in progress), March 2020. 1307 [RFC4653] Bhandarkar, S., Reddy, A., Allman, M., and E. Blanton, 1308 "Improving the Robustness of TCP to Non-Congestion 1309 Events", August 2006. 1311 [RFC5682] Sarolahti, P., Kojo, M., Yamamoto, K., and M. Hata, 1312 "Forward RTO-Recovery (F-RTO): An Algorithm for Detecting 1313 Spurious Retransmission Timeouts with TCP", RFC 5682, 1314 September 2009. 1316 [RFC5827] Allman, M., Ayesta, U., Wang, L., Blanton, J., and P. 1317 Hurtig, "Early Retransmit for TCP and Stream Control 1318 Transmission Protocol (SCTP)", RFC 5827, April 2010. 1320 [RFC6937] Mathis, M., Dukkipati, N., and Y. Cheng, "Proportional 1321 Rate Reduction for TCP", May 2013. 1323 [RFC7765] Hurtig, P., Brunstrom, A., Petlund, A., and M. Welzl, "TCP 1324 and SCTP RTO Restart", February 2016. 1326 [SCWA99] Savage, S., Cardwell, N., Wetherall, D., and T. Anderson, 1327 "TCP Congestion Control With a Misbehaving Receiver", ACM 1328 Computer Communication Review, 29(5) , 1999. 1330 [Sprout] Winstein, K., Sivaraman, A., and H. Balakrishnan, 1331 "Stochastic Forecasts Achieve High Throughput and Low 1332 Delay over Cellular Networks", USENIX Symposium on 1333 Networked Systems Design and Implementation (NSDI) , 2013. 1335 Authors' Addresses 1337 Yuchung Cheng 1338 Google, Inc 1340 Email: ycheng@google.com 1342 Neal Cardwell 1343 Google, Inc 1345 Email: ncardwell@google.com 1346 Nandita Dukkipati 1347 Google, Inc 1349 Email: nanditad@google.com 1351 Priyaranjan Jha 1352 Google, Inc 1354 Email: priyarjha@google.com