rfc8985xml2.original.xml   rfc8985.xml 
<?xml version="1.0" ?> <?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE rfc SYSTEM 'rfc2629.dtd' [
]>
<rfc ipr="trust200902" category="std" docName="draft-ietf-tcpm-rack-15">
<?rfc toc="yes"?>
<front>
<title abbrev="RACK">The RACK-TLP loss detection algorithm for TCP</title>
<author fullname="Yuchung Cheng" initials="Y." surname="Cheng">
<organization>Google, Inc</organization>
<address>
<email> ycheng@google.com </email>
</address>
</author>
<author fullname="Neal Cardwell" initials="N." surname="Cardwell">
<organization>Google, Inc</organization>
<address>
<email> ncardwell@google.com </email>
</address>
</author>
<author fullname="Nandita Dukkipati" initials="N." surname="Dukkipati">
<organization>Google, Inc</organization>
<address>
<email> nanditad@google.com </email>
</address>
</author>
<author fullname="Priyaranjan Jha" initials="P." surname="Jha">
<organization>Google, Inc</organization>
<address>
<email> priyarjha@google.com </email>
</address>
</author>
<date month="December" year="2020"/>
<area>Transport</area>
<workgroup> TCP Maintenance Working Group </workgroup>
<keyword>TCP</keyword>
<keyword>Loss Recovery</keyword>
<keyword>Reordering</keyword>
<abstract><t>
This document presents the RACK-TLP loss detection algorithm for TCP. RACK-TLP u
ses per-segment transmit timestamps and selective acknowledgements (SACK) and ha
s two parts: RACK ("Recent ACKnowledgment") starts fast recovery quickly using t
ime-based inferences derived from ACK feedback. TLP ("Tail Loss Probe") leverage
s RACK and sends a probe packet to trigger ACK feedback to avoid retransmission
timeout (RTO) events. Compared to the widely used DUPACK threshold approach, RAC
K-TLP detects losses more efficiently when there are application-limited flights
of data, lost retransmissions, or data packet reordering events. It is intended
to be an alternative to the DUPACK threshold approach.
</t></abstract>
</front>
<middle>
<section title="Terminology" anchor="terminology">
<t>The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD",
"SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this d
ocument are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, a
nd only when, they appear in all capitals, as shown here.</t>
</section>
<section title="Introduction" anchor="introduction">
<t>This document presents RACK-TLP, a TCP loss detection algorithm that improves
upon the widely implemented duplicate acknowledgment (DUPACK) counting approach
in [RFC5681] [RFC6675], and that is RECOMMENDED to be used as an alternative to
that earlier approach. RACK-TLP has two parts: RACK ("Recent ACKnowledgment") d
etects losses quickly using time-based inferences derived from ACK feedback. TLP
(“Tail Loss Probe”) triggers ACK feedback by quickly sending a probe segment,
to avoid retransmission timeout (RTO) events.</t>
<section title="Background" anchor="background">
<t>In traditional TCP loss recovery algorithms [RFC5681] [RFC6675], a sender sta
rts fast recovery when the number of DUPACKs received reaches a threshold (DupTh
resh) that defaults to 3 (this approach is referred to as DUPACK-counting in the
rest of the document). The sender also halves the congestion window during the
recovery. The rationale behind the partial window reduction is that congestion d
oes not seem severe since ACK clocking is still maintained. The time elapsed in
fast recovery can be just one round-trip, e.g. if the sender uses SACK-based rec
overy [RFC6675] and the number of lost segments is small.</t>
<t>If fast recovery is not triggered, or triggers but fails to repair all the lo
sses, then the sender resorts to RTO recovery. The RTO timer interval is conserv
atively the smoothed RTT (SRTT) plus four times the RTT variation, and is lower
bounded to 1 second [RFC6298]. Upon RTO timer expiration, the sender retransmits
the first unacknowledged segment and resets the congestion window to the LOSS W
INDOW value (by default 1 full-size segment [RFC5681]). The rationale behind the
congestion window reset is that an entire flight of data was lost, and the ACK
clock was lost, so this deserves a cautious response. The sender then retransmit
s the rest of the data following the slow start algorithm [RFC5681]. The time el
apsed in RTO recovery is one RTO interval plus the number of round-trips needed
to repair all the losses.</t>
</section>
<section title="Motivation" anchor="motivation">
<t>Fast Recovery is the preferred form of loss recovery because it can potential
ly recover all losses in the time scale of a single round trip, with only a frac
tional congestion window reduction. RTO recovery and congestion window reset sho
uld ideally be the last resort, only used when the entire flight is lost. Howeve
r, in addition to losing an entire flight of data, the following situations can
unnecessarily resort to RTO recovery with traditional TCP loss recovery algorith
ms [RFC5681] [RFC6675]:</t>
<t><list style="numbers">
<t>Packet drops for short flows or at the end of an application data flight. Whe
n the sender is limited by the application (e.g. structured request/response tra
ffic), segments lost at the end of the application data transfer often can only
be recovered by RTO.Consider an example of losing only the last segment in a fli
ght of 100 segments. Lacking any DUPACK, the sender RTO expires and reduces the
congestion window to 1, and raises the congestion window to just 2 after the los
s repair is acknowledged. In contrast, any single segment loss occurring between
the first and the 97th segment would result in fast recovery, which would only
cut the window in half.</t>
<t>Lost retransmissions. Heavy congestion or traffic policers can cause retransm
issions to be lost. Lost retransmissions cause a resort to RTO recovery, since D
UPACK-counting does not detect the loss of the retransmissions. Then the slow st
art after RTO recovery could cause burst losses again that severely degrades per
formance [POLICER16].</t>
<t>Packet reordering. In this document, "reordering" refers to the events where
segments are delivered at the TCP receiver in a chronological order different fr
om their chronological transmission order. Link-layer protocols (e.g., 802.11 bl
ock ACK), link bonding, or routers' internal load-balancing (e.g., ECMP) can del
iver TCP segments out of order. The degree of such reordering is usually within
the order of the path round trip time.If the reordering degree is beyond DupThre
sh, DUPACK-counting can cause a spurious fast recovery and unnecessary congestio
n window reduction. To mitigate the issue, TCP-NCR [RFC4653] increases the DupTh
resh from the current fixed value of three duplicate ACKs [RFC5681] to approxima
tely a congestion window of data having left the network.</t>
</list></t>
</section>
</section>
<section title="RACK-TLP high-level design" anchor="rack-tlp-high-level-design">
<t>RACK-TLP allows senders to recover losses more effectively in all three scena
rios described in the previous section. There are two design principles behind R
ACK-TLP. The first principle is to detect losses via ACK events as much as possi
ble, to repair losses at round-trip time-scales. The second principle is to gent
ly probe the network to solicit additional ACK feedback, to avoid RTO expiration
and subsequent congestion window reset. At a high level, the two principles are
implemented in RACK and TLP, respectively.</t>
<section title="RACK: time-based loss inferences from ACKs" anchor="rack-time-ba
sed-loss-inferences-from-acks">
<t>The rationale behind RACK is that if a segment is delivered out of order, the
n the segments sent chronologically before that were either lost or reordered. T
his concept is not fundamentally different from [RFC5681] [RFC6675] [FACK]. RACK
’s key innovation is using per-segment transmission timestamps and widely-deploy
ed SACK [RFC2018] options to conduct time-based inferences, instead of inferring
losses by counting ACKs or SACKed sequences. Time-based inferences are more rob
ust than DUPACK-counting approaches because they have no dependence on flight si
ze, and thus are effective for application-limited traffic.</t>
<t>Conceptually, RACK keeps a virtual timer for every data segment sent (includi
ng retransmissions). Each timer expires dynamically based on the latest RTT meas
urements plus an additional delay budget to accommodate potential packet reorder
ing (called the reordering window). When a segment’s timer expires, RACK marks t
he corresponding segment lost for retransmission.</t>
<t>In reality, as an algorithm, RACK does not arm a timer for every segment sent
because it’s not necessary. Instead the sender records the most recent transmis
sion time of every data segment sent, including retransmissions. For each ACK re
ceived, the sender calculates the latest RTT measurement (if eligible) and adjus
ts the expiration time of every segment sent but not yet delivered. If a segment
has expired, RACK marks it lost.</t>
<t>Since the time-based logic of RACK applies equally to retransmissions and ori
ginal transmissions, it can detect lost retransmissions as well. If a segment ha
s been retransmitted but its most recent (re)transmission timestamp has expired,
then after a reordering window it’s marked lost.</t>
</section>
<section title="TLP: sending one segment to probe losses quickly with RACK" anch
or="tlp-sending-one-segment-to-probe-losses-quickly-with-rack">
<t>RACK infers losses from ACK feedback; however, in some cases ACKs are sparse,
particularly when the inflight is small or when the losses are high. In some ch
allenging cases the last few segments in a flight are lost. With [RFC5681] or [R
FC6675] the sender’s RTO would expire and reset the congestion window, when in r
eality most of the flight has been delivered.</t>
<t>Consider an example where a sender with a large congestion window transmits 1
00 new data segments after an application write, and only the last three segment
s are lost. Without RACK-TLP, the RTO expires, the sender retransmits the first
unacknowledged segment, and the congestion window slow-starts from 1. After all
the retransmits are acknowledged the congestion window has been increased to 4.
The total delivery time for this application transfer is three RTTs plus one RTO
, a steep cost given that only a tiny fraction of the flight was lost. If instea
d the losses had occurred three segments sooner in the flight, then fast recover
y would have recovered all losses within one round-trip and would have avoided r
esetting the congestion window.</t>
<t>Fast Recovery would be preferable in such scenarios; TLP is designed to trigg
er the feedback RACK needed to enable that. After the last (100th) segment was o
riginally sent, TLP sends the next available (new) segment or retransmits the la
st (highest-sequenced) segment in two round-trips to probe the network, hence th
e name “Tail Loss Probe”. The successful delivery of the probe would solicit an
ACK. RACK uses this ACK to detect that the 98th and 99th segments were lost, tri
gger fast recovery, and retransmit 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 was also lost then the sender would invoke RTO recove
ry resetting the congestion window.</t>
</section>
<section title="RACK-TLP: reordering resilience with a time threshold" anchor="r
ack-tlp-reordering-resilience-with-a-time-threshold">
<section title="Reordering design rationale" anchor="reordering-design-rationale
">
<t>Upon receiving an ACK indicating an out-of-order data delivery, a sender cann
ot tell immediately whether that out-of-order delivery was a result of reorderin
g or loss. It can only distinguish between the two in hindsight if the missing s
equence ranges are filled in later without retransmission. Thus a loss detection
algorithm needs to budget some wait time -- a reordering window -- to try to di
sambiguate packet reordering from packet loss.</t>
<t>The reordering window in the DUPACK-counting approach is implicitly defined a
s the elapsed time to receive acknowledgements for DupThresh-worth of out-of-ord
er deliveries. This approach is effective if the network reordering degree (in s
equence distance) is smaller than DupThresh and at least DupThresh segments afte
r the loss are acknowledged. For cases where the reordering degree is larger tha
n the default DupThresh of 3 packets, one alternative is to dynamically adapt Du
pThresh based on the FlightSize (e.g., the sender adjusts the DUPTHRESH to half
of the FlightSize). However, this does not work well with the following two type
s of reordering:</t>
<t><list style="numbers">
<t>Application-limited flights where the last non-full-sized segment is delivere
d first and then the remaining full-sized segments in the flight are delivered i
n order. This reordering pattern can occur when segments traverse parallel forwa
rding paths. In such scenarios the degree of reordering in packet distance is on
e segment less than the flight size.</t>
<t>A flight of segments that are delivered partially out of order. One cause for
this pattern is wireless link-layer retransmissions with an inadequate reorderi
ng 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 delivers the TCP data packets in the orde
r they are received, due to the inadequate reordering buffer. The random wireles
s transmission errors in such scenarios cause the reordering degree, expressed i
n packet distance, to have highly variable values up to the flight size.</t>
</list></t>
<t>In the above two cases the degree of reordering in packet distance is highly
variable. This makes the DUPACK-counting approach ineffective including dynamic
adaptation variants like [RFC4653]. Instead the degree of reordering in time dif
ference in such cases is usually within a single round-trip time. This is becaus
e the packets either traverse slightly disjoint paths with similar propagation d
elays or are repaired quickly by the local access technology. Hence, using a tim
e threshold instead of packet threshold strikes a middle ground, allowing a boun
ded degree of reordering resilience while still allowing fast recovery. This is
the rationale behind the RACK-TLP reordering resilience design.</t>
<t>Specifically, RACK-TLP introduces a new dynamic reordering window parameter i
n time units, and the sender considers a data segment S lost if both conditions
are met:</t>
<t><list style="numbers">
<t>Another data segment sent later than S has been delivered</t>
<t>S has not been delivered after the estimated round-trip time plus the reorder
ing window</t>
</list></t>
<t>Note that condition (1) implies at least one round-trip of time has elapsed s
ince S has been sent.</t>
</section>
<section title="Reordering window adaptation" anchor="reordering-window-adaptati
on">
<t>The RACK reordering window adapts to the measured duration of reordering even
ts, within reasonable and specific bounds to disincentivize excessive reordering
. More specifically, the sender sets the reordering window as follows:</t>
<t><list style="numbers">
<t>The reordering window SHOULD be set to zero if no reordering has been observ
ed on the connection so far, and either (a) three segments have been delivered o
ut of order 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.</t>
<t>The RACK reordering window SHOULD adaptively increase (using the algorithm in
"Step 4: Update RACK reordering window", below) if the sender receives a Duplic
ate Selective Acknowledgement (DSACK) option [RFC2883]. Receiving a DSACK sugges
ts the sender made a spurious retransmission, which may have been due to the reo
rdering window being too small.</t>
<t>The RACK reordering window MUST be bounded and this bound SHOULD be SRTT.</t>
</list></t>
<t>Rules 2 and 3 are required to adapt to reordering caused by dynamics such as
the prolonged link-layer loss recovery episodes described earlier. Each increase
in the reordering window requires a new round trip where the sender receives a
DSACK; thus, depending on the extent of reordering, it may take multiple round t
rips to fully adapt.</t>
<t>For short flows, the low initial reordering window helps recover losses quick
ly, at the risk of spurious retransmissions. The rationale is that spurious retr
ansmissions for short flows are not expected to produce excessive additional net
work traffic. For long flows the design tolerates reordering within a round trip
. This handles reordering in small time scales (reordering within the round-trip
time of the shortest path).</t>
<t>However, the fact that the initial reordering window is low, and the reorderi
ng window's adaptive growth is bounded, means that there will continue to be a c
ost to reordering that disincentivizes excessive reordering.</t>
</section>
</section>
<section title="An Example of RACK-TLP in Action: fast recovery" anchor="an-exam
ple-of-rack-tlp-in-action-fast-recovery">
<t>The following example in figure 1 illustrates the RACK-TLP algorithm in actio
n:</t>
<figure><artwork>
Event TCP DATA SENDER TCP DATA RECEIVER
_____ ____________________________________________________________
1. Send P0, P1, P2, P3 --&gt;
[P1, P2, P3 dropped by network]
2. &lt;-- Receive P0, ACK P0
3a. 2RTTs after (2), TLP timer fires
3b. TLP: retransmits P3 --&gt;
4. &lt;-- Receive P3, SACK P3
5a. Receive SACK for P3
5b. RACK: marks P1, P2 lost
5c. Retransmit P1, P2 --&gt;
[P1 retransmission dropped by network]
6. &lt;-- Receive P2, SACK P2 &amp; P3
7a. RACK: marks P1 retransmission lost
7b. Retransmit P1 --&gt;
8. &lt;-- Receive P1, ACK P3
Figure 1. RACK-TLP protocol example
</artwork></figure>
<t>Figure 1, above, illustrates a sender sending four segments (P1, P2, P3, P4)
and losing the last three segments. After two round-trips, TLP sends a loss prob
e, retransmitting the last segment, P3, to solicit SACK feedback and restore the
ACK clock (event 3). The delivery of P3 enables RACK to infer (event 5b) that P
1 and P2 were likely lost, because they were sent before P3. The sender then ret
ransmits P1 and P2. Unfortunately, the retransmission of P1 is lost again. Howev
er, the delivery of the retransmission of P2 allows RACK to infer that the retra
nsmission of P1 was likely lost (event 7a), and hence P1 should be retransmitted
(event 7b). Note that [RFC5681] mandates a principle that loss in two successiv
e windows of data, or the loss of a retransmission, must be taken as two indicat
ions of congestion and therefore result in two separate congestion control react
ions.</t>
</section>
<section title="An Example of RACK-TLP in Action: RTO" anchor="an-example-of-rac
k-tlp-in-action-rto">
<t>In addition to enhancing fast recovery, RACK improves the accuracy of RTO rec
overy by reducing spurious retransmissions.</t>
<t>Without RACK, upon RTO timer expiration the sender marks all the unacknowledg
ed segments lost. This approach can lead to spurious retransmissions. For exam
ple, 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 then the sender m
arks all three segments as lost and retransmits the first segment. If the ACK fo
r the original copy of the first segment arrives right after the spurious RTO re
transmission, then the sender continues slow start and spuriously retransmits th
e second and third segments, since it (erroneously) presumed they are lost.</t
>
<t>With RACK, upon RTO timer expiration the only segment automatically marked lo
st is the first segment (since it was sent an RTO ago); for all the other segmen
ts RACK only marks the segment lost if at least one round trip has elapsed since
the segment was transmitted. Consider the previous example scenario, this time
with RACK. With RACK, when the RTO expires the sender only marks the first segm
ent as lost, and retransmits that segment. The other two very recently sent seg
ments are not marked lost, because they were sent less than one round trip ago a
nd there were no ACKs providing evidence that they were lost. Upon receiving the
ACK for the RTO retransmission the RACK sender would not yet retransmit the sec
ond or third segment. but rather would rearm the RTO timer and wait for a new RT
O interval to elapse before marking the second or third segments as lost.</t>
</section>
<section title="Design Summary" anchor="design-summary">
<t>To summarize, RACK-TLP aims to adapt to small time-varying degrees of reorder
ing, quickly recover most losses within one to two round trips, and avoid costly
RTO recoveries. In the presence of reordering, the adaptation algorithm can imp
ose sometimes-needless delays when it waits to disambiguate loss from reordering
, but the penalty for waiting is bounded to one round trip and such delays are c
onfined to flows long enough to have observed reordering.</t>
</section>
</section>
<section title="Requirements" anchor="requirements">
<t>The reader is expected to be familiar with the definitions given in the TCP c
ongestion control [RFC5681] and selective acknowledgment [RFC2018] and loss reco
very [RFC6675] RFCs. RACK-TLP has the following requirements:</t>
<t><list style="numbers">
<t>The connection MUST use selective acknowledgment (SACK) options [RFC2018], an
d the sender MUST keep SACK scoreboard information on a per-connection basis ("S
ACK scoreboard" has the same meaning here as in [RFC6675] section 3).</t>
<t>For each data segment sent, the sender MUST store its most recent transmissio
n time with a timestamp whose granularity is finer than 1/4 of the minimum RTT o
f the connection. At the time of writing, microsecond resolution is suitable for
intra-datacenter traffic and millisecond granularity or finer is suitable for t
he Internet.Note that RACK-TLP can be implemented with TSO (TCP Segmentation Off
load) support by having multiple segments in a TSO aggregate share the same time
stamp.</t>
<t>RACK DSACK-based reordering window adaptation is RECOMMENDED but is not requi
red.</t>
<t>TLP requires RACK.</t>
</list></t>
</section>
<section title="Definitions" anchor="definitions">
<t>The reader is expected to be familiar with the variables SND.UNA, SND.NXT, SE
G.ACK, and SEG.SEQ in [RFC793], SMSS, FlightSize in [RFC5681], DupThresh in [RFC
6675], RTO and SRTT in [RFC6298]. A RACK-TLP implementation uses several new ter
ms and needs to store new per-segment and per-connection state, described below.
</t>
<section title="Terms" anchor="terms">
<t>These terms are used to explain variables and algorithms below:</t>
<t> “RACK.segment”. Among all the segments that have been either selectiv
ely or cumulatively acknowledged, the term RACK.segment denotes the segment that
was sent most recently (including retransmissions).</t>
<t> “RACK.ack_ts” denotes the time when the full sequence range of RACK.s
egment was selectively or cumulatively acknowledged.</t>
</section>
<section title="Per-segment variables" anchor="per-segment-variables">
<t>Theses variables indicate the status of the most recent transmission of a dat
a segment:</t>
<t> “Segment.lost” is true if the most recent (re)transmission of the seg
ment has been marked lost and needs to be retransmitted. False otherwise.</t>
<t> “Segment.retransmitted” is true if the segment has ever been retransm
itted. False otherwise.</t>
<t> “Segment.xmit_ts” is the time of the last transmission of a data segm
ent, including retransmissions, if any, with a clock granularity specified in th
e Requirements section. A maximum value INFINITE_TS indicates an invalid timesta
mp that represents that the Segment is not currently in flight.</t>
<t> “Segment.end_seq” is the next sequence number after the last sequence
number of the data segment.</t>
</section>
<section title="Per-connection variables" anchor="per-connection-variables">
<t> “RACK.xmit_ts” is the latest transmission timestamp of RACK.segment.<
/t>
<t> “RACK.end_seq” is the Segment.end_seq of RACK.segment.</t>
<t> “RACK.segs_sacked” returns the total number of segments selectively a
cknowledged in the SACK scoreboard.</t>
<t> “RACK.fack” is the highest selectively or cumulatively acknowledged s
equence (i.e. forward acknowledgement).</t>
<t> “RACK.min_RTT” is the estimated minimum round-trip time (RTT) of the
connection. </t>
<t> “RACK.rtt” is the RTT of the most recently delivered segment on the c
onnection (either cumulatively acknowledged or selectively acknowledged) that wa
s not marked invalid as a possible spurious retransmission.</t>
<t> “RACK.reordering_seen” indicates whether the sender has detected data
segment reordering event(s).</t>
<t> “RACK.reo_wnd” is a reordering window computed in the unit of time us ed for recording segment transmission times. It is used to defer the moment at w hich RACK marks a segment lost.</t> <!DOCTYPE rfc SYSTEM "rfc2629-xhtml.ent">
<t> “RACK.dsack_round” indicates if a DSACK option has been received in t <rfc xmlns:xi="http://www.w3.org/2001/XInclude" ipr="trust200902" docName="draf
he lastest round trip.</t> t-ietf-tcpm-rack-15"
number="8985" obsoletes="" updates="" submissionType="IETF" category="std" cons
ensus="true"
xml:lang="en" tocInclude="true" symRefs="true" sortRefs="true" version="3">
<t> “RACK.reo_wnd_mult” is the multiplier applied to adjust RACK.reo_wnd. <front>
</t> <title abbrev="RACK">The RACK-TLP Loss Detection Algorithm for TCP</title>
<seriesInfo name="RFC" value="8985"/>
<author fullname="Yuchung Cheng" initials="Y." surname="Cheng">
<organization>Google, Inc.</organization>
<address>
<email> ycheng@google.com </email>
</address>
</author>
<author fullname="Neal Cardwell" initials="N." surname="Cardwell">
<organization>Google, Inc.</organization>
<address>
<email> ncardwell@google.com </email>
</address>
</author>
<author fullname="Nandita Dukkipati" initials="N." surname="Dukkipati">
<organization>Google, Inc.</organization>
<address>
<email> nanditad@google.com </email>
</address>
</author>
<author fullname="Priyaranjan Jha" initials="P." surname="Jha">
<organization>Google, Inc.</organization>
<address>
<email> priyarjha@google.com </email>
</address>
</author>
<date month="February" year="2021"/>
<area>Transport</area>
<workgroup> TCP Maintenance Working Group </workgroup>
<keyword>TCP</keyword>
<keyword>Loss Recovery</keyword>
<keyword>Reordering</keyword>
<abstract>
<t>
This document presents the RACK-TLP loss detection algorithm for TCP. RACK-TLP u
ses per-segment transmit timestamps and selective acknowledgments (SACKs) and ha
s two parts. Recent Acknowledgment (RACK) starts fast recovery quickly using tim
e-based inferences derived from acknowledgment (ACK) feedback, and Tail Loss Pro
be (TLP) leverages RACK and sends a probe packet to trigger ACK feedback to avoi
d retransmission timeout (RTO) events. Compared to the widely used duplicate ack
nowledgment (DupAck) threshold approach, RACK-TLP detects losses more efficientl
y when there are application-limited flights of data, lost retransmissions, or d
ata packet reordering events. It is intended to be an alternative to the DupAck
threshold approach.
</t>
</abstract>
</front>
<middle>
<section anchor="introduction" numbered="true" toc="default">
<name>Introduction</name>
<t> “RACK.reo_wnd_persist” is the number of loss recoveries before resett <t>This document presents RACK-TLP, a TCP loss detection algorithm that i
ing RACK.reo_wnd.</t> mproves upon the widely implemented duplicate acknowledgment (DupAck) counting a
pproach described in <xref target="RFC5681" format="default"/> and <xref target=
"RFC6675" format="default"/>; it is <bcp14>RECOMMENDED</bcp14> as an alternative
to that earlier approach. RACK-TLP has two parts. Recent Acknowledgment (RACK)
detects losses quickly using time-based inferences derived from ACK feedback. Ta
il Loss Probe (TLP) triggers ACK feedback by quickly sending a probe segment to
avoid retransmission timeout (RTO) events.</t>
<section anchor="background" numbered="true" toc="default">
<name>Background</name>
<t>In traditional TCP loss recovery algorithms <xref target="RFC5681" fo
rmat="default"/> <xref target="RFC6675" format="default"/>, a sender starts fast
recovery when the number of DupAcks received reaches a threshold (DupThresh) th
at defaults to 3 (this approach is referred to as "DupAck counting" in the rest
of the document). The sender also halves the congestion window during the recove
ry. The rationale behind the partial window reduction is that congestion does no
t seem severe since ACK clocking is still maintained. The time elapsed in fast r
ecovery can be just one round trip, e.g., if the sender uses SACK-based recovery
<xref target="RFC6675" format="default"/> and the number of lost segments is sm
all.</t>
<t>If fast recovery is not triggered or is triggered but fails to repair
all the losses, then the sender resorts to RTO recovery. The RTO timer interval
is conservatively the smoothed RTT (SRTT) plus four times the RTT variation, an
d is lower bounded to 1 second <xref target="RFC6298" format="default"/>. Upon R
TO timer expiration, the sender retransmits the first unacknowledged segment and
resets the congestion window to the loss window value (by default, 1 full-sized
segment <xref target="RFC5681" format="default"/>). The rationale behind the co
ngestion window reset is that an entire flight of data and the ACK clock were lo
st, so this deserves a cautious response. The sender then retransmits the rest o
f the data following the slow start algorithm <xref target="RFC5681" format="def
ault"/>. The time elapsed in RTO recovery is one RTO interval plus the number of
round trips needed to repair all the losses.</t>
</section>
<section anchor="motivation" numbered="true" toc="default">
<name>Motivation</name>
<t>Fast recovery is the preferred form of loss recovery because it can p
otentially recover all losses in the timescale of a single round trip, with only
a fractional congestion window reduction. RTO recovery and congestion window re
set should ideally be the last resort and should ideally be used only when the e
ntire flight is lost. However, in addition to losing an entire flight of data, t
he following situations can unnecessarily resort to RTO recovery with traditiona
l TCP loss recovery algorithms <xref target="RFC5681" format="default"/> <xref t
arget="RFC6675" format="default"/>:
</t>
<ol spacing="normal" type="1"><li>Packet drops for short flows or at the
end of an application data flight. When the sender is limited by the applicatio
n (e.g., structured request/response traffic), segments lost at the end of the a
pplication data transfer often can only be recovered by RTO. Consider an example
where only the last segment in a flight of 100 segments is lost. Lacking any Du
pAck, the sender RTO expires, reduces the congestion window to 1, and raises the
congestion window to just 2 after the loss repair is acknowledged. In contrast,
any single segment loss occurring between the first and the 97th segment would
result in fast recovery, which would only cut the window in half.
</li>
<li>Lost retransmissions. Heavy congestion or traffic policers can cau
se retransmissions to be lost. Lost retransmissions cause a resort to RTO recove
ry since DupAck counting does not detect the loss of the retransmissions. Then t
he slow start after RTO recovery could cause burst losses again, which severely
degrades performance <xref target="POLICER16" format="default"/>.
</li>
<li>Packet reordering. In this document, "reordering" refers to the ev
ents where segments are delivered at the TCP receiver in a chronological order d
ifferent from their chronological transmission order. Link-layer protocols (e.g.
, 802.11 block ACK), link bonding, or routers' internal load balancing (e.g., EC
MP) can deliver TCP segments out of order. The degree of such reordering is usua
lly within the order of the path round-trip time.
<t> “TLP.is_retrans”: a boolean indicating whether there is an unacknowl If the reordering degree is beyond DupThresh, DupAck counting can cause a spuri
edged TLP retransmission.</t> ous fast recovery and unnecessary congestion window reduction. To mitigate the i
ssue, Non-Congestion Robustness (NCR) for TCP <xref target="RFC4653" format="def
ault"/> increases the DupThresh from the current fixed value of three duplicate
ACKs <xref target="RFC5681" format="default"/> to approximate a congestion windo
w of data having left the network.</li>
</ol>
</section>
</section>
<section anchor="terminology" numbered="true" toc="default">
<name>Terminology</name>
<t>
The key words "<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>", "<bcp14>REQ
UIRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL
NOT</bcp14>", "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>", "<bcp14
>RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>",
"<bcp14>MAY</bcp14>", and "<bcp14>OPTIONAL</bcp14>" in this document are to
be interpreted as
described in BCP&nbsp;14 <xref target="RFC2119"/> <xref target="RFC8174"/>
when, and only when, they appear in all capitals, as shown here.
</t>
</section>
<t> “TLP.end_seq”: the value of SND.NXT at the time of sending a TLP retr <section anchor="rack-tlp-high-level-design" numbered="true" toc="default">
ansmission.</t> <name>RACK-TLP High-Level Design</name>
<t>RACK-TLP allows senders to recover losses more effectively in all thre
e scenarios described in the <xref target="motivation" format="none"> previous</
xref> section. There are two design principles behind RACK-TLP. The first princi
ple is to detect losses via ACK events as much as possible, to repair losses at
round-trip timescales. The second principle is to gently probe the network to so
licit additional ACK feedback, to avoid RTO expiration and subsequent congestion
window reset. At a high level, the two principles are implemented in RACK and T
LP, respectively.</t>
<section anchor="rack-time-based-loss-inferences-from-acks" numbered="tru
e" toc="default">
<name>RACK: Time-Based Loss Inferences from ACKs</name>
<t>
The rationale behind RACK is that if a segment is delivered out of order, then
the segments sent chronologically before that were either lost or reordered. Thi
s concept is not fundamentally different from those described in <xref target="R
FC5681" format="default"/>, <xref target="RFC6675" format="default"/>, or <xref
target="FACK" format="default"/>. RACK's key innovation is using per-segment tra
nsmission timestamps and widely deployed SACK <xref target="RFC2018" format="def
ault"/> options to conduct time-based inferences instead of inferring losses by
counting ACKs or SACKed sequences. Time-based inferences are more robust than Du
pAck counting approaches because they do not depend on flight size and thus are
effective for application-limited traffic.
</t>
<t>Conceptually, RACK keeps a virtual timer for every data segment sent
(including retransmissions). Each timer expires dynamically based on the latest
RTT measurements plus an additional delay budget to accommodate potential packet
reordering (called the
"reordering window"). When a segment's timer expires, RACK marks the correspond
ing segment as lost for retransmission.</t>
<t>In reality, as an algorithm, RACK does not arm a timer for every segm
ent sent because it's not necessary. Instead, the sender records the most recent
transmission time of every data segment sent, including retransmissions. For ea
ch ACK received, the sender calculates the latest RTT measurement (if eligible)
and adjusts the expiration time of every segment sent but not yet delivered. If
a segment has expired, RACK marks it as lost.
</t>
<t>Since the time-based logic of RACK applies equally to retransmissions
and original transmissions,
it can detect lost retransmissions as well. If a segment has been retransmitted
but its most recent (re)transmission timestamp has expired, then, after a reord
ering window, it's marked as lost.</t>
</section>
<section anchor="tlp-sending-one-segment-to-probe-losses-quickly-with-rac
k" numbered="true" toc="default">
<name>TLP: Sending One Segment to Probe Losses Quickly with RACK</name>
<t>RACK infers losses from ACK feedback; however, in some cases, ACKs ar
e sparse, particularly when the inflight is small or when the losses are high. I
n some challenging cases, the last few segments in a flight are lost. With the o
perations described in <xref target="RFC5681" format="default"/> or <xref target
="RFC6675" format="default"/>, the sender's RTO would expire and reset the conge
stion window when, in reality, most of the flight has been delivered.</t>
<t>Consider an example where a sender with a large congestion window tra
nsmits 100 new data segments after an application write and only the last three
segments are lost. Without RACK-TLP, the RTO expires, the sender retransmits the
first unacknowledged segment, and the congestion window slow starts from 1. Aft
er all the retransmits are acknowledged, the congestion window is increased to 4
. The total delivery time for this application transfer is three RTTs plus one R
TO, a steep cost given that only a tiny fraction of the flight was lost. If inst
ead the losses had occurred three segments sooner in the flight, then fast recov
ery would have recovered all losses within one round trip and would have avoided
resetting the congestion window.
</t>
<t>Fast recovery would be preferable in such scenarios; TLP is designed
to trigger the feedback RACK needed to enable that. After the last (100th) segme
nt was originally sent, TLP sends the next available (new) segment or retransmit
s the last (highest-sequenced) segment in two round trips to probe the network,
hence the name "Tail Loss Probe". The successful delivery of the probe would sol
icit an ACK. RACK uses this ACK to detect that the 98th and 99th segments were l
ost, trigger fast recovery, and retransmit 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 was also lost, then the sender would invoke R
TO recovery, resetting the congestion window.</t>
</section>
<section anchor="rack-tlp-reordering-resilience-with-a-time-threshold" nu
mbered="true" toc="default">
<name>RACK-TLP: Reordering Resilience with a Time Threshold</name>
<section anchor="reordering-design-rationale" numbered="true" toc="defau
lt">
<name>Reordering Design Rationale</name>
<t>Upon receiving an ACK indicating a SACKed segment, a sender cannot
tell immediately whether that was a result of reordering or loss. It can only di
stinguish between the two in hindsight if the missing sequence ranges are filled
in later without retransmission. Thus, a loss detection algorithm needs to budg
et some wait time -- a reordering window -- to try to disambiguate packet reorde
ring from packet loss.
</t>
<t>The reordering window in the DupAck counting approach is implicitly
defined as the elapsed time to receive DupThresh SACKed segments or duplicate a
cknowledgments. This approach is effective if the network reordering degree (in
sequence distance) is smaller than DupThresh and at least DupThresh segments aft
er the loss is acknowledged. For cases where the reordering degree is larger tha
n the default DupThresh of 3 packets, one alternative is to dynamically adapt Du
pThresh based on the FlightSize (e.g., the sender adjusts the DupThresh to half
of the FlightSize). However, this does not work well with the following two type
s of reordering:</t>
<ol spacing="normal" type="1"><li>Application-limited flights where th
e last non-full-sized segment is delivered first and then the remaining full-siz
ed segments in the flight are delivered in order. This reordering pattern can oc
cur when segments traverse parallel forwarding paths. In such scenarios, the deg
ree of reordering in packet distance is one segment less than the flight size.
</li>
<li>A flight of segments that are delivered partially out of order.
One cause for this pattern is wireless link-layer retransmissions with an inadeq
uate reordering buffer at the receiver. In such scenarios, the wireless sender s
ends the data packets in order initially, but some are lost and then recovered b
y link-layer retransmissions; the wireless receiver delivers the TCP data packet
s in the order they are received due to the inadequate reordering buffer. The ra
ndom wireless transmission errors in such scenarios cause the reordering degree,
expressed in packet distance, to have highly variable values up to the flight s
ize.</li>
</ol>
<t>In the above two cases, the degree of reordering in packet distance
is highly variable. This makes the DupAck counting approach ineffective, includ
ing dynamic adaptation variants as in <xref target="RFC4653" format="default"/>.
Instead, the degree of reordering in time difference in such cases is usually w
ithin a single round-trip time.
This is because the packets either traverse disjoint paths with similar propagat
ion delays or are repaired quickly by the local access technology. Hence, using
a time threshold instead of a packet threshold strikes a middle ground, allowing
a bounded degree of reordering resilience while still allowing fast recovery. T
his is the rationale behind the RACK-TLP reordering resilience design.</t>
<t>Specifically, RACK-TLP introduces a new dynamic reordering window p
arameter in time units, and the sender considers a data segment S lost if both o
f these conditions are met:</t>
<ol spacing="normal" type="1"><li>Another data segment sent later than
S has been delivered.</li>
<li>S has not been delivered after the estimated round-trip time plu
s the reordering window.</li>
</ol>
<t>
Note that condition (1) implies at least one round trip of time has elapsed sin
ce S has been sent.</t>
</section>
<section anchor="reordering-window-adaptation" numbered="true" toc="defa
ult">
<name>Reordering Window Adaptation</name>
<t>The RACK reordering window adapts to the measured duration of reord
ering events within reasonable and specific bounds to disincentivize excessive r
eordering. More specifically, the sender sets the reordering window as follows:<
/t>
<ol spacing="normal" type="1"><li anchor="rule1">The reordering window
<bcp14>SHOULD</bcp14> 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 las
t recovery or (b) the sender is already in fast or RTO recovery. Otherwise, the
reordering window <bcp14>SHOULD</bcp14> start from a small fraction of the round
-trip time or zero if no round-trip time estimate is available.
</li>
<li anchor="rule2">The RACK reordering window <bcp14>SHOULD</bcp14>
adaptively increase (using the <xref target="step4alg" format="none">algorithm</
xref> in <xref target="step4" format="none">"Step 4: Update RACK reordering wind
ow"</xref> below) if the sender receives a Duplicate Selective Acknowledgment (D
SACK) option <xref target="RFC2883" format="default"/>. Receiving a DSACK sugges
ts the sender made a spurious retransmission, which may have been due to the reo
rdering window being too small.</li>
<li anchor="rule3">The RACK reordering window <bcp14>MUST</bcp14> be
bounded, and this bound <bcp14>SHOULD</bcp14> be SRTT.</li>
</ol>
<t>Rules <xref target="rule2" format="none">2</xref> and <xref target=
"rule3" format="none">3</xref> are required to adapt to reordering caused by dyn
amics such as the prolonged link-layer loss recovery episodes described earlier.
Each increase in the reordering window requires a new round trip where the send
er receives a DSACK; thus, depending on the extent of reordering, it may take mu
ltiple round trips to fully adapt.</t>
<t>For short flows, the low initial reordering window helps recover lo
sses quickly, at the risk of spurious retransmissions. The rationale is that spu
rious retransmissions for short flows are not expected to produce excessive addi
tional network traffic. For long flows, the design tolerates reordering within a
round trip. This handles reordering in small timescales (reordering within the
round-trip time of the shortest path).</t>
<t>However, the fact that the initial reordering window is low and the
reordering window's adaptive growth is bounded means that there will continue t
o be a cost to reordering that disincentivizes excessive reordering.</t>
</section>
</section>
<section anchor="an-example-of-rack-tlp-in-action-fast-recovery" numbered
="true" toc="default">
<name>An Example of RACK-TLP in Action: Fast Recovery</name>
<t>The following example in <xref target="fig1"/> illustrates the RACK-T
LP algorithm in action:</t>
<figure anchor="fig1">
<name>RACK-TLP Protocol Example</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
Event TCP DATA SENDER TCP DATA RECEIVER
_____ ____________________________________________________________
1. Send P0, P1, P2, P3 -->
[P1, P2, P3 dropped by network]
<t> “TLP.max_ack_delay”: sender's maximum delayed ACK timer budget.</t> 2. <-- Receive P0, ACK P0
</section> 3a. 2RTTs after (2), TLP timer fires
<section title="Per-connection timers" anchor="per-connection-timers"> 3b. TLP: retransmits P3 -->
<t>“RACK reordering timer”: a timer that allows RACK to wait for reordering to r esolve, to try to disambiguate reordering from loss, when some out-of-order segm ents are marked as SACKed.</t> 4. <-- Receive P3, SACK P3
<t>“TLP PTO”: a timer event indicating that an ACK is overdue and the sender sho 5a. Receive SACK for P3
uld transmit a TLP segment, to solicit SACK or ACK feedback. </t> 5b. RACK: marks P1, P2 lost
5c. Retransmit P1, P2 -->
[P1 retransmission dropped by network]
<t>These timers augment the existing timers maintained by a sender, including th e RTO timer [RFC6298]. A RACK-TLP sender arms one of these three timers -- RACK reordering timer, TLP PTO timer, or RTO timer -- when it has unacknowledged segm ents in flight. The implementation can simplify managing all three timers by mul tiplexing a single timer among them with an additional variable to indicate the event to invoke upon the next timer expiration.</t> 6. <-- Receive P2, SACK P2 & P3
</section> 7a. RACK: marks P1 retransmission lost
</section> 7b. Retransmit P1 -->
<section title="RACK Algorithm Details" anchor="rack-algorithm-details">
<section title="Upon transmitting a data segment" anchor="upon-transmitting-a-da 8. <-- Receive P1, ACK P3
ta-segment"> ]]></artwork>
</figure>
<t anchor="fig1desc"><xref target="fig1"/> illustrates a sender sending
four segments (P0, P1, P2, P3) and losing the last three segments. After two rou
nd trips, TLP sends a loss probe, retransmitting the last segment, P3, to solici
t SACK feedback and restore the ACK clock (Event 3). The delivery of P3 enables
RACK to 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 retransmiss
ion of P1 is lost again. However, the delivery of the retransmission of P2 allow
s RACK to infer that the retransmission of P1 was likely lost (Event 7a); hence,
P1 should be retransmitted (Event 7b). Note that <xref target="RFC5681" format=
"default"/> mandates a principle that 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.</t>
</section>
<section anchor="an-example-of-rack-tlp-in-action-rto" numbered="true" to
c="default">
<name>An Example of RACK-TLP in Action: RTO</name>
<t>In addition to enhancing fast recovery, RACK improves the accuracy of
RTO recovery by reducing spurious retransmissions.</t>
<t>Without RACK, upon RTO timer expiration, the sender marks all the una
cknowledged segments as lost. This approach can lead to spurious retransmission
s. For example, consider a simple case where one segment was sent with an RTO o
f 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, then
the sender marks all three segments as lost and retransmits the first segment. I
f the ACK for the original copy of the first segment arrives right after the spu
rious RTO retransmission, then the sender continues slow start and spuriously re
transmits the second and third segments since it (erroneously) presumed they are
lost.</t>
<t>With RACK, upon RTO timer expiration, 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 the segment as lost if at least one round trip h
as elapsed since the segment was transmitted. Consider the previous example scen
ario, but this time with RACK. With RACK, when the RTO expires, the sender only
marks the first segment as lost and retransmits that segment. The other two ve
ry recently sent segments are not marked as lost because they were sent less tha
n one round trip ago and there were no ACKs providing evidence that they were lo
st. Upon receiving the ACK for the RTO retransmission, the RACK sender would not
yet retransmit the second or third segment, but rather would re-arm the RTO tim
er and wait for a new RTO interval to elapse before marking the second or third
segment as lost.</t>
</section>
<section anchor="design-summary" numbered="true" toc="default">
<name>Design Summary</name>
<t>To summarize, RACK-TLP aims to adapt to small time-varying degrees of
reordering, quickly recover most losses within one to two round trips, and avoi
d costly RTO recoveries. In the presence of reordering, the adaptation algorithm
can impose sometimes needless delays when it waits to disambiguate loss from re
ordering, but the penalty for waiting is bounded to one round trip, and such del
ays are confined to flows long enough to have observed reordering.</t>
</section>
</section>
<section anchor="requirements" numbered="true" toc="default">
<name>Requirements</name>
<t>The reader is expected to be familiar with the definitions given in th
e TCP congestion control <xref target="RFC5681" format="default"/>, selective ac
knowledgment <xref target="RFC2018" format="default"/>, and loss recovery <xref
target="RFC6675" format="default"/> RFCs. RACK-TLP has the following requirement
s:
</t>
<ol spacing="normal" type="1"><li>The connection <bcp14>MUST</bcp14> use
selective acknowledgment (SACK) options <xref target="RFC2018" format="default"/
>, and the sender <bcp14>MUST</bcp14> keep SACK scoreboard information on a per-
connection basis ("SACK scoreboard" has the same meaning here as in <xref target
="RFC6675" sectionFormat="comma" section="3"/>).</li>
<li>For each data segment sent, the sender <bcp14>MUST</bcp14> 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 re
solution is suitable for intra-data center traffic, and millisecond granularity
or finer is suitable for the Internet.
<t>Upon transmitting a new segment or retransmitting an old segment, record the Note that RACK-TLP can be implemented with TSO (TCP Segmentation Offload) suppo
time in Segment.xmit_ts and set Segment.lost to FALSE. Upon retransmitting a seg rt by having multiple segments in a TSO aggregate share the same timestamp.</li>
ment, set Segment.retransmitted to TRUE. </t> <li>RACK DSACK-based reordering window adaptation is <bcp14>RECOMMENDED<
/bcp14> but is not required.
</li>
<li>TLP requires RACK.</li>
</ol>
</section>
<section anchor="definitions" numbered="true" toc="default">
<name>Definitions</name>
<t>The reader is expected to be familiar with the variables SND.UNA, SND.
NXT, SEG.ACK, and SEG.SEQ in <xref target="RFC0793" format="default"/>; Sender M
aximum Segment Size (SMSS) and FlightSize in <xref target="RFC5681" format="defa
ult"/>; DupThresh in <xref target="RFC6675" format="default"/>; and RTO and SRTT
in <xref target="RFC6298" format="default"/>. A RACK-TLP implementation uses se
veral new terms and needs to store new per-segment and per-connection state, des
cribed below.</t>
<section anchor="terms" numbered="true" toc="default">
<name>Terms</name>
<t>These terms are used to explain the variables and algorithms below:
</t>
<dl newline="true">
<dt>RACK.segment</dt><dd>Among all the segments that have been either se
lectively or cumulatively acknowledged, the term "RACK.segment" denotes the segm
ent that was sent most recently (including retransmissions).</dd>
<dt>RACK.ack_ts</dt><dd>Denotes the time when the full sequence range of
RACK.segment was selectively or cumulatively acknowledged.</dd></dl>
</section>
<section anchor="per-segment-variables" numbered="true" toc="default">
<name>Per-Segment Variables</name>
<t>These variables indicate the status of the most recent transmission o
f a data segment:</t>
<dl newline="true">
<dt>Segment.lost</dt><dd>True if the most recent (re)transmission of the
segment has been marked as lost and needs to be retransmitted. False otherwise.
</dd>
<dt>Segment.retransmitted</dt><dd>True if the segment has ever been retr
ansmitted. False otherwise.
</dd>
<dt>Segment.xmit_ts</dt><dd>The time of the last transmission of a data
segment, including retransmissions, if any, with a clock granularity specified i
n the <xref target="requirements" format="none">"Requirements"</xref> section. A
maximum value INFINITE_TS indicates an invalid timestamp that represents that t
he segment is not currently in flight.</dd>
<dt>Segment.end_seq</dt><dd>The next sequence number after the last sequ
ence number of the data segment.</dd></dl>
</section>
<section anchor="per-connection-variables" numbered="true" toc="default">
<name>Per-Connection Variables</name>
<dl newline="true">
<dt>RACK.xmit_ts</dt><dd>The latest transmission timestamp of RACK.segment.
</dd>
<dt>RACK.end_seq</dt><dd>The Segment.end_seq of RACK.segment.</dd>
<dt>RACK.segs_sacked</dt><dd>Returns the total number of segments select
ively acknowledged in the SACK scoreboard.
</dd>
<dt>RACK.fack</dt><dd>The highest selectively or cumulatively acknowledg
ed sequence (i.e., forward acknowledgment).</dd>
<dt>RACK.min_RTT</dt><dd>The estimated minimum round-trip time (RTT) of
the connection.</dd>
<dt>RACK.rtt</dt><dd>The RTT of the most recently delivered segment on t
he connection (either cumulatively acknowledged or selectively acknowledged) tha
t was not marked as invalid as a possible spurious retransmission.
</dd>
<dt>RACK.reordering_seen</dt><dd>Indicates whether the sender has detect
ed data segment reordering event(s).</dd>
<dt>RACK.reo_wnd</dt><dd>A reordering window computed in the unit of tim
e used for recording segment transmission times. It is used to defer the moment
at which RACK marks a segment as lost.</dd>
<dt>RACK.dsack_round</dt><dd>Indicates if a DSACK option has been receiv
ed in the latest round trip.</dd>
<dt>RACK.reo_wnd_mult</dt><dd>The multiplier applied to adjust RACK.reo_
wnd.</dd>
<dt>RACK.reo_wnd_persist</dt><dd>The number of loss recoveries before re
setting RACK.reo_wnd.</dd>
<dt>
TLP.is_retrans</dt><dd>A boolean indicating whether there is an unackno
wledged TLP retransmission.</dd>
<dt>TLP.end_seq</dt><dd>The value of SND.NXT at the time of sending a TL
P probe.</dd>
<dt>
TLP.max_ack_delay:</dt><dd>The sender's budget for the maximum delayed A
CK interval.</dd></dl>
</section>
<section anchor="per-connection-timers" numbered="true" toc="default">
<name>Per-Connection Timers</name>
<dl newline="true">
<dt>RACK reordering timer</dt><dd>A timer that allows RACK to wait for r
eordering to resolve in order to try to disambiguate reordering from loss when s
ome segments are marked as SACKed.
</dd>
<dt>TLP PTO</dt><dd>A timer event indicating that an ACK is overdue and
the sender should transmit a TLP segment to solicit SACK or ACK feedback. </dd><
/dl>
<t>These timers augment the existing timers maintained by a sender, incl
uding the RTO timer <xref target="RFC6298" format="default"/>. A RACK-TLP sender
arms one of these three timers -- RACK reordering timer, TLP PTO timer, or RTO
timer -- when it has unacknowledged segments in flight. The implementation can s
implify managing all three timers by multiplexing a single timer among them with
an additional variable to indicate the event to invoke upon the next timer expi
ration.</t>
</section>
</section>
<section anchor="rack-algorithm-details" numbered="true" toc="default">
<name>RACK Algorithm Details</name>
<section anchor="upon-transmitting-a-data-segment" numbered="true" toc="de
fault">
<name>Upon Transmitting a Data Segment</name>
<t>Upon transmitting a new segment or retransmitting an old segment, rec
ord the time in Segment.xmit_ts and set Segment.lost to FALSE. Upon retransmitti
ng a segment, set Segment.retransmitted to TRUE. </t>
<figure><artwork> <sourcecode name="" type="pseudocode"><![CDATA[
RACK_transmit_new_data(Segment): RACK_transmit_new_data(Segment):
Segment.xmit_ts = Now() Segment.xmit_ts = Now()
Segment.lost = FALSE Segment.lost = FALSE
RACK_retransmit_data(Segment): Segment.retransmitted = TRUE Segment.xmit_ts =
Now()
Segment.lost = FALSE
</artwork></figure>
</section>
<section title="Upon receiving an ACK" anchor="upon-receiving-an-ack">
<t>Step 1: Update RACK.min_RTT.</t>
<t>Use the RTT measurements obtained via [RFC6298] or [RFC7323] to update the es
timated minimum RTT in RACK.min_RTT. The sender SHOULD track a windowed min-filt
ered estimate of recent RTT measurements that can adapt when migrating to signif
icantly longer paths, rather than a simple global minimum of all RTT measurement
s.</t>
<t>Step 2: Update state for most recently sent segment that has been delivered</
t>
<t>In this step, RACK updates the states that track the most recently sent segme
nt that has been delivered: RACK.segment; RACK maintains its latest transmission
timestamp in RACK.xmit_ts and its highest sequence number in RACK.end_seq. Thes
e two variables are used, in later steps, to estimate if some segments not yet d
elivered were likely lost.Given the information provided in an ACK, each segment
cumulatively ACKed or SACKed is marked as delivered in the scoreboard. Since an
ACK can also acknowledge retransmitted data segments, and retransmissions can b
e spurious, the sender needs to take care to avoid spurious inferences. For exam
ple, if the sender were to use timing information from a spurious retransmission
, the RACK.rtt could be vastly underestimated.</t>
<t>To avoid spurious inferences, ignore a segment as invalid if any of its seque
nce range has been retransmitted before and either of two conditions is true:</t
>
<t><list style="numbers">
<t>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.</t>
<t>The segment was last retransmitted less than RACK.min_rtt ago. </t>
</list></t>
<t>The second check is a heuristic when the TCP Timestamp option is not availabl
e, or when the round trip time is less than the TCP Timestamp clock granularity.
</t>
<t>Among all the segments newly ACKed or SACKed by this ACK that pass the checks
above, update the RACK.rtt to be the RTT sample calculated using this ACK. Furt
hermore, record the most recent Segment.xmit_ts in RACK.xmit_ts if it is ahead o
f RACK.xmit_ts. If Segment.xmit_ts equals RACK.xmit_ts (e.g. due to clock granul
arity limits) then compare Segment.end_seq and RACK.end_seq to break the tie whe
n deciding whether to update the RACK.segment’s associated state.</t>
<t>Step 2 may be summarized in pseudocode as:</t> RACK_retransmit_data(Segment):
Segment.retransmitted = TRUE
Segment.xmit_ts = Now()
Segment.lost = FALSE
]]></sourcecode>
</section>
<section anchor="upon-receiving-an-ack" numbered="true" toc="default">
<name>Upon Receiving an ACK</name>
<t anchor="step1">Step 1: Update RACK.min_RTT.</t>
<t>Use the RTT measurements obtained via <xref target="RFC6298" format="
default"/> or <xref target="RFC7323" format="default"/> to update the estimated
minimum RTT in RACK.min_RTT. The sender <bcp14>SHOULD</bcp14> track a windowed m
in-filtered estimate of recent RTT measurements that can adapt when migrating to
significantly longer paths rather than tracking a simple global minimum of all
RTT measurements.</t>
<t anchor="step2">
Step 2: Update the state for the most recently sent segment that has been delive
red.</t>
<t>In this step, RACK updates the state that tracks the most recently se
nt segment that has been delivered: RACK.segment. RACK maintains its latest tran
smission timestamp in RACK.xmit_ts and its highest sequence number in RACK.end_s
eq. These two variables are used in later steps to estimate if some segments not
yet delivered were likely lost.
<figure><artwork> Given the information provided in an ACK, each segment cumulatively ACKed or SAC
Ked is marked as delivered in the scoreboard. Because an ACK can also acknowledg
e retransmitted data segments and because retransmissions can be spurious, the s
ender needs to take care to avoid spurious inferences. For example, if the sende
r were to use timing information from a spurious retransmission, the RACK.rtt co
uld be vastly underestimated.</t>
<t>To avoid spurious inferences, ignore a segment as invalid if any of i
ts sequence range has been retransmitted before and if either of two conditions
is true:</t>
<ol spacing="normal" type="1"><li>The Timestamp Echo Reply field (TSecr)
of the ACK's timestamp option <xref target="RFC7323" format="default"/>, if ava
ilable, indicates the ACK was not acknowledging the last retransmission of the s
egment.</li>
<li>The segment was last retransmitted less than RACK.min_rtt ago. </l
i>
</ol>
<t>
The second check is a heuristic when the TCP Timestamp option is not available o
r when the round-trip time is less than the TCP Timestamp clock granularity.
</t>
<t>Among all the segments newly ACKed or SACKed by this ACK that pass th
e checks above, update the RACK.rtt to be the RTT sample calculated using this A
CK. Furthermore, record the most recent Segment.xmit_ts in RACK.xmit_ts if it is
ahead of RACK.xmit_ts. If Segment.xmit_ts equals RACK.xmit_ts (e.g., due to clo
ck granularity limits), then compare Segment.end_seq and RACK.end_seq to break t
he tie when deciding whether to update the RACK.segment's associated state.</t>
<t>Step 2 may be summarized in pseudocode as:</t>
<sourcecode name="" type="pseudocode"><![CDATA[
RACK_sent_after(t1, seq1, t2, seq2): RACK_sent_after(t1, seq1, t2, seq2):
If t1 &gt; t2: If t1 > t2:
Return true Return true
Else if t1 == t2 AND seq1 &gt; seq2: Else if t1 == t2 AND seq1 > seq2:
Return true Return true
Else: Else:
Return false Return false
RACK_update(): RACK_update():
For each Segment newly acknowledged, cumulatively or selectively, in asce For each Segment newly acknowledged, cumulatively or selectively,
nding order of Segment.xmit_ts: in ascending order of Segment.xmit_ts:
rtt = Now() - Segment.xmit_ts rtt = Now() - Segment.xmit_ts
If Segment.retransmitted is TRUE: If Segment.retransmitted is TRUE:
If ACK.ts_option.echo_reply &lt; Segment.xmit_ts: If ACK.ts_option.echo_reply < Segment.xmit_ts:
Continue Continue
If rtt &lt; RACK.min_rtt: If rtt < RACK.min_rtt:
Continue Continue
RACK.rtt = rtt RACK.rtt = rtt
If RACK_sent_after(Segment.xmit_ts, Segment.end_seq If RACK_sent_after(Segment.xmit_ts, Segment.end_seq
RACK.xmit_ts, RACK.end_seq): RACK.xmit_ts, RACK.end_seq):
RACK.xmit_ts = Segment.xmit_ts RACK.xmit_ts = Segment.xmit_ts
RACK.end_seq = Segment.end_seq RACK.end_seq = Segment.end_seq
</artwork></figure> ]]></sourcecode>
<t anchor="step3">Step 3: Detect data segment reordering.</t>
<t>Step 3: Detect data segment reordering</t> <t>To detect reordering, the sender looks for original data segments bei
ng delivered out of order. To detect such cases, the sender tracks the highest s
<t>To detect reordering, the sender looks for original data segments being deliv equence selectively or cumulatively acknowledged in the RACK.fack variable. ".fa
ered out of order. To detect such cases, the sender tracks the highest sequence ck" stands for the most "Forward ACK" (this term is adopted from <xref target="F
selectively or cumulatively acknowledged in the RACK.fack variable. The name "fa ACK" format="default"/>). If a never-retransmitted segment that's below RACK.fac
ck" stands for the most "Forward ACK" (this term is adopted from [FACK]). If a n k is (selectively or cumulatively) acknowledged, it has been delivered out of or
ever-retransmitted segment that’s below RACK.fack is (selectively or cumulativel der. The sender sets RACK.reordering_seen to TRUE if such a segment is identifie
y) acknowledged, it has been delivered out of order. The sender sets RACK.reorde d.</t>
ring_seen to TRUE if such segment is identified.</t> <sourcecode name="" type="pseudocode"><![CDATA[
<figure><artwork>
RACK_detect_reordering(): RACK_detect_reordering():
For each Segment newly acknowledged, cumulatively or selectively, in asce For each Segment newly acknowledged, cumulatively or selectively,
nding order of Segment.end_seq: in ascending order of Segment.end_seq:
If Segment.end_seq &gt; RACK.fack: If Segment.end_seq > RACK.fack:
RACK.fack = Segment.end_seq RACK.fack = Segment.end_seq
Else if Segment.end_seq &lt; RACK.fack AND Else if Segment.end_seq < RACK.fack AND
Segment.retransmitted is FALSE: Segment.retransmitted is FALSE:
RACK.reordering_seen = TRUE RACK.reordering_seen = TRUE
</artwork></figure> ]]></sourcecode>
<t anchor="step4">Step 4: Update the RACK reordering window.</t>
<t>Step 4: Update RACK reordering window</t> <t>The RACK reordering window, RACK.reo_wnd, serves as an adaptive allow
ance for settling time before marking a segment as lost. This step documents a d
<t>The RACK reordering window, RACK.reo_wnd, serves as an adaptive allowance for etailed algorithm that follows the principles outlined in the <xref target="reor
settling time before marking a segment lost. This step documents a detailed alg dering-window-adaptation" format="none">"Reordering Window Adaptation"</xref> se
orithm that follows the principles outlined in the ``Reordering window adaptatio ction.</t>
n’’ section.</t> <t>If no reordering has been observed based on the <xref target="step3"
format="none">previous step</xref>, then one way the sender can enter fast recov
<t>If no reordering has been observed, based on the previous step, then one way ery is when the number of SACKed segments matches or exceeds DupThresh (similar
the sender can enter Fast Recovery is when the number of SACKed segments matches to <xref target="RFC6675"/>). Furthermore, when no reordering has been observed,
or exceeds DupThresh (similar to RFC6675). Furthermore, when no reordering has the RACK.reo_wnd is set to 0 both upon entering and during fast recovery or RTO
been observed the RACK.reo_wnd is set to 0 both upon entering and during Fast Re recovery.</t>
covery or RTO recovery.</t> <t>Otherwise, if some reordering has been observed, then RACK does not t
rigger fast recovery based on DupThresh.</t>
<t>Otherwise, if some reordering has been observed, then RACK does not trigger F <t>Whether or not reordering has been observed, RACK uses the reordering
ast Recovery based on DupThresh.</t> window to assess whether any segments can be marked as lost. As a consequence,
the sender also enters fast recovery when there are any number of SACKed segment
<t>Whether or not reordering has been observed, RACK uses the reordering window s, as long as the reorder window has passed for some non-SACKed segments.</t>
to assess whether any segments can be marked lost. As a consequence, the sender <t>When the reordering window is not set to 0, it starts with a conserva
also enters Fast Recovery when there are any number of SACKed segments as long a tive RACK.reo_wnd of RACK.min_RTT/4. This value was chosen because Linux TCP use
s the reorder window has passed for some non-SACKed segments.</t> d the same factor in its implementation to delay Early Retransmit <xref target="
RFC5827" format="default"/> to reduce spurious loss detections in the presence o
<t>When the reordering window is not set to 0, it starts with a conservative RAC f reordering, and experience showed this worked reasonably well <xref target="DM
K.reo_wnd of RACK.min_RTT/4. This value was chosen because Linux TCP used the sa CG11" format="default"/>. </t>
me factor in its implementation to delay Early Retransmit [RFC5827] to reduce sp <t>However, the reordering detection in the previous step, <xref target=
urious loss detections in the presence of reordering, and experience showed this "step3" format="none">Step 3</xref>, has a self-reinforcing drawback when the re
worked reasonably well [DMCG11]. </t> ordering window is too small to cope with the actual reordering. When that happe
ns, RACK could spuriously mark reordered segments as lost, causing them to be re
<t>However, the reordering detection in the previous step, Step 3, has a self-re transmitted. In turn, the retransmissions can prevent the necessary conditions f
inforcing drawback when the reordering window is too small to cope with the actu or <xref target="step3" format="none">Step 3</xref> to detect reordering since t
al reordering. When that happens, RACK could spuriously mark reordered segments his mechanism requires ACKs or SACKs only for segments that have never been retr
lost, causing them to be retransmitted. In turn, the retransmissions can prevent ansmitted. In some cases, such scenarios can persist, causing RACK to continue t
the necessary conditions for Step 3 to detect reordering, since this mechanism o spuriously mark segments as lost without realizing the reordering window is to
requires ACKs or SACKs for only segments that have never been retransmitted. In o small.
some cases such scenarios can persist, causing RACK to continue to spuriously ma </t>
rk segments lost without realizing the reordering window is too small.</t> <t>To avoid the issue above, RACK dynamically adapts to higher degrees o
f reordering using DSACK options from the receiver. Receiving an ACK with a DSAC
<t>To avoid the issue above, RACK dynamically adapts to higher degrees of reorde K option indicates a possible spurious retransmission, suggesting that RACK.reo_
ring using DSACK options from the receiver. Receiving an ACK with a DSACK option wnd may be too small. The RACK.reo_wnd increases linearly for every round trip i
indicates a possible spurious retransmission, suggesting that RACK.reo_wnd may n which the sender receives some DSACK option so that after N round trips in whi
be too small. The RACK.reo_wnd increases linearly for every round trip in which ch a DSACK is received, the RACK.reo_wnd becomes (N+1) * min_RTT / 4, with an up
the sender receives some DSACK option, so that after N round trips in which a DS per-bound of SRTT.</t>
ACK is received, the RACK.reo_wnd becomes (N+1) * min_RTT / 4, with an upper-bou <t>If the reordering is temporary, then a large adapted reordering windo
nd of SRTT.</t> w would unnecessarily delay loss recovery later. Therefore, RACK persists using
the inflated RACK.reo_wnd for up to 16 loss recoveries, after which it resets RA
<t>If the reordering is temporary then a large adapted reordering window would u CK.reo_wnd to its starting value, min_RTT / 4. The downside of resetting the reo
nnecessarily delay loss recovery later. Therefore, RACK persists using the infla rdering window is the risk of triggering spurious fast recovery episodes if the
ted RACK.reo_wnd for up to 16 loss recoveries, after which it resets RACK.reo_wn reordering remains high. The rationale for this approach is to bound such spurio
d to its starting value, min_RTT / 4. The downside of resetting the reordering w us recoveries to approximately once every 16 recoveries (less than 7%).
indow is the risk of triggering spurious fast recovery episodes if the reorderin </t>
g remains high. The rationale for this approach is to bound such spurious recove <t>To track the linear scaling factor for the adaptive reordering window
ries to approximately once every 16 recoveries (less than 7%). </t> , RACK uses the variable RACK.reo_wnd_mult, which is initialized to 1 and adapts
with the observed reordering.</t>
<t>To track the linear scaling factor for the adaptive reordering window, RACK u <t>The following pseudocode implements the above algorithm for updating
ses the variable RACK.reo_wnd_mult, which is initialized to 1 and adapts with ob the RACK reordering window:</t>
served reordering.</t> <sourcecode anchor="step4alg" name="" type="pseudocode"><![CDATA[
<t>The following pseudocode implements the above algorithm for updating the RACK
reordering window:</t>
<figure><artwork>
RACK_update_reo_wnd(): RACK_update_reo_wnd():
/* DSACK-based reordering window adaptation */ /* DSACK-based reordering window adaptation */
If RACK.dsack_round is not None AND If RACK.dsack_round is not None AND
SND.UNA &gt;= RACK.dsack_round: SND.UNA >= RACK.dsack_round:
RACK.dsack_round = None RACK.dsack_round = None
/* Grow the reordering window per round that sees DSACK. /* Grow the reordering window per round that sees DSACK.
Reset the window after 16 DSACK-free recoveries */ Reset the window after 16 DSACK-free recoveries */
If RACK.dsack_round is None AND If RACK.dsack_round is None AND
any DSACK option is present on latest received ACK: RACK.dsack_rou any DSACK option is present on latest received ACK:
nd = SND.NXT RACK.dsack_round = SND.NXT
RACK.reo_wnd_mult += 1 RACK.reo_wnd_mult += 1
RACK.reo_wnd_persist = 16 RACK.reo_wnd_persist = 16
Else if exiting Fast or RTO recovery: Else if exiting Fast or RTO recovery:
RACK.reo_wnd_persist -= 1 RACK.reo_wnd_persist -= 1
If RACK.reo_wnd_persist &lt;= 0: If RACK.reo_wnd_persist <= 0:
RACK.reo_wnd_mult = 1 RACK.reo_wnd_mult = 1
If RACK.reordering_seen is FALSE: If RACK.reordering_seen is FALSE:
If in Fast or RTO recovery: If in Fast or RTO recovery:
Return 0 Return 0
Else if RACK.segs_sacked &gt;= DupThresh: Else if RACK.segs_sacked >= DupThresh:
Return 0 Return 0
Return min(RACK.reo_wnd_mult * RACK.min_RTT / 4, SRTT) Return min(RACK.reo_wnd_mult * RACK.min_RTT / 4, SRTT)
</artwork></figure> ]]></sourcecode>
<t anchor="step5">Step 5: Detect losses.</t>
<t>Step 5: Detect losses.</t> <t>For each segment that has not been SACKed, RACK considers that segmen
t lost if another segment that was sent later has been delivered and the reorder
<t>For each segment that has not been SACKed, RACK considers that segment lost i ing window has passed. RACK considers the reordering window to have passed if th
f another segment that was sent later has been delivered, and the reordering win e RACK.segment was sent a sufficient time after the segment in question, if a su
dow has passed. RACK considers the reordering window to have passed if the RACK. fficient time has elapsed since the RACK.segment was S/ACKed, or some combinatio
segment was sent sufficiently after the segment in question, or a sufficient tim n of the two. More precisely, RACK marks a segment as lost if:</t>
e has elapsed since the RACK.segment was S/ACKed, or some combination of the two <sourcecode name="" type="pseudocode"><![CDATA[
. More precisely, RACK marks a segment lost if:</t> RACK.xmit_ts >= Segment.xmit_ts
AND
<figure><artwork> RACK.xmit_ts - Segment.xmit_ts + (now - RACK.ack_ts) >= RACK.reo_wnd
RACK.xmit_ts &gt;= Segment.xmit_ts ]]></sourcecode>
AND <t>Solving this second condition for "now", the moment at which a segmen
RACK.xmit_ts - Segment.xmit_ts + (now - RACK.ack_ts) &gt;= RACK.reo_wnd t is marked as lost, yields:</t>
</artwork></figure> <sourcecode name="" type="pseudocode"><![CDATA[
now >= Segment.xmit_ts + RACK.reo_wnd + (RACK.ack_ts - RACK.xmit_ts)
<t>Solving this second condition for "now", the moment at which a segment is mar ]]></sourcecode>
ked lost, yields:</t> <t>Then (RACK.ack_ts - RACK.xmit_ts) is the round-trip time of the most
recently (re)transmitted segment that's been delivered. When segments are delive
<figure><artwork> red in order, the most recently (re)transmitted segment that's been delivered is
now &gt;= Segment.xmit_ts + RACK.reo_wnd + (RACK.ack_ts - RACK.xmit_ts) also the most recently delivered; hence, RACK.rtt == RACK.ack_ts - RACK.xmit_ts
</artwork></figure> . But if segments were reordered, then the segment delivered most recently was s
ent before the most recently (re)transmitted segment. Hence, RACK.rtt &gt; (RACK
<t>Then (RACK.ack_ts - RACK.xmit_ts) is the round trip time of the most recently .ack_ts - RACK.xmit_ts). </t>
(re)transmitted segment that's been delivered. When segments are delivered in o <t>Since RACK.RTT &gt;= (RACK.ack_ts - RACK.xmit_ts), the previous equat
rder, the most recently (re)transmitted segment that's been delivered is also th ion reduces to saying that the sender can declare a segment lost when:</t>
e most recently delivered, hence RACK.rtt == RACK.ack_ts - RACK.xmit_ts. But if <sourcecode name="" type="pseudocode"><![CDATA[
segments were reordered, then the segment delivered most recently was sent befor now >= Segment.xmit_ts + RACK.reo_wnd + RACK.rtt
e the most recently (re)transmitted segment. Hence RACK.rtt &gt; (RACK.ack_ts - ]]></sourcecode>
RACK.xmit_ts). </t> <t>In turn, that is equivalent to stating that a RACK sender should decl
are a segment lost when:</t>
<t>Since RACK.RTT &gt;= (RACK.ack_ts - RACK.xmit_ts), the previous equation redu <sourcecode name="" type="pseudocode"><![CDATA[
ces to saying that the sender can declare a segment lost when:</t> Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - now <= 0
]]></sourcecode>
<figure><artwork> <t>Note that if the value on the left-hand side is positive, it represen
now &gt;= Segment.xmit_ts + RACK.reo_wnd + RACK.rtt ts the remaining wait time before the segment is deemed lost. But this risks a t
</artwork></figure> imeout (RTO) if no more ACKs come back (e.g., due to losses or application-limit
ed transmissions) to trigger the marking. For timely loss detection, it is <bcp1
<t>In turn, that is equivalent to stating that a RACK sender should declare a se 4>RECOMMENDED</bcp14> that the sender install a reordering timer. This timer exp
gment lost when:</t> ires at the earliest moment when RACK would conclude that all the unacknowledged
segments within the reordering window were lost.</t>
<figure><artwork> <t>The following pseudocode implements the algorithm above. When an ACK
Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - now &lt;= 0 is received or the RACK reordering timer expires, call RACK_detect_loss_and_arm_
</artwork></figure> timer(). The algorithm breaks timestamp ties by using the TCP sequence space sin
ce high-speed networks often have multiple segments with identical timestamps. <
<t>Note that if the value on the left hand side is positive, it represents the r /t>
emaining wait time before the segment is deemed lost. But this risks a timeout ( <sourcecode name="" type="pseudocode"><![CDATA[
RTO) if no more ACKs come back (e.g., due to losses or application-limited trans
missions) to trigger the marking. For timely loss detection, the sender is RECOM
MENDED to install a reordering timer. This timer expires at the earliest moment
when RACK would conclude that all the unacknowledged segments within the reorder
ing window were lost.</t>
<t>The following pseudocode implements the algorithm above. When an ACK is recei
ved or the RACK reordering timer expires, call RACK_detect_loss_and_arm_timer().
The algorithm breaks timestamp ties by using the TCP sequence space, since high
-speed networks often have multiple segments with identical timestamps. </t>
<figure><artwork>
RACK_detect_loss(): RACK_detect_loss():
timeout = 0 timeout = 0
RACK.reo_wnd = RACK_update_reo_wnd() RACK.reo_wnd = RACK_update_reo_wnd()
For each segment, Segment, not acknowledged yet: For each segment, Segment, not acknowledged yet:
If RACK_sent_after(RACK.xmit_ts, RACK.end_seq, If RACK_sent_after(RACK.xmit_ts, RACK.end_seq,
Segment.xmit_ts, Segment.end_seq): Segment.xmit_ts, Segment.end_seq):
remaining = Segment.xmit_ts + RACK.rtt + remaining = Segment.xmit_ts + RACK.rtt +
RACK.reo_wnd - Now() RACK.reo_wnd - Now()
If remaining &lt;= 0: If remaining <= 0:
Segment.lost = TRUE Segment.xmit_ts = INFINITE_TS Segment.lost = TRUE
Segment.xmit_ts = INFINITE_TS
Else: Else:
timeout = max(remaining, timeout) timeout = max(remaining, timeout)
Return timeout Return timeout
RACK_detect_loss_and_arm_timer(): RACK_detect_loss_and_arm_timer():
timeout = RACK_detect_loss() timeout = RACK_detect_loss()
If timeout != 0 If timeout != 0
Arm the RACK timer to call RACK_detect_loss_and_arm_timer() afte Arm the RACK timer to call
r timeout RACK_detect_loss_and_arm_timer() after timeout
</artwork></figure> ]]></sourcecode>
<t>As an optimization, an implementation can choose to check only segmen
<t>As an optimization, an implementation can choose to check only segments that ts that have been sent before RACK.xmit_ts. This can be more efficient than scan
have been sent before RACK.xmit_ts. This can be more efficient than scanning the ning the entire SACK scoreboard, especially when there are many segments in flig
entire SACK scoreboard, especially when there are many segments in flight. The ht. The implementation can use a separate doubly linked list ordered by Segment.
implementation can use a separate doubly-linked list ordered by Segment.xmit_ts xmit_ts, insert a segment at the tail of the list when it is (re)transmitted, an
and inserts a segment at the tail of the list when it is (re)transmitted, and re d remove a segment from the list when it is delivered or marked as lost. In Linu
moves a segment from the list when it is delivered or marked lost. In Linux TCP x TCP, this optimization improved CPU usage by orders of magnitude during some f
this optimization improved CPU usage by orders of magnitude during some fast rec ast recovery episodes on high-speed WAN networks.</t>
overy episodes on high-speed WAN networks.</t> </section>
<section anchor="upon-rto-expiration" numbered="true" toc="default">
</section> <name>Upon RTO Expiration</name>
<section title="Upon RTO expiration" anchor="upon-rto-expiration"> <t>Upon RTO timer expiration, RACK marks the first outstanding segment a
s lost (since it was sent an RTO ago); for all the other segments, RACK only mar
<t>Upon RTO timer expiration, RACK marks the first outstanding segment as lost ( ks the segment as lost if the time elapsed since the segment was transmitted is
since it was sent an RTO ago); for all the other segments RACK only marks the se at least the sum of the recent RTT and the reordering window.</t>
gment lost if the time elapsed since the segment was transmitted is at least the <sourcecode name="" type="pseudocode"><![CDATA[
sum of the recent RTT and the reordering window.</t>
<figure><artwork>
RACK_mark_losses_on_RTO(): RACK_mark_losses_on_RTO():
For each segment, Segment, not acknowledged yet: For each segment, Segment, not acknowledged yet:
If SEG.SEQ == SND.UNA OR Segment.xmit_ts + RACK.rtt + RACK.reo If SEG.SEQ == SND.UNA OR
_wnd - Now() &lt;= 0: Segment.lost = TRUE Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - Now() <= 0:
</artwork></figure> Segment.lost = TRUE
]]></sourcecode>
</section> </section>
</section> </section>
<section title="TLP Algorithm Details" anchor="tlp-algorithm-details"> <section anchor="tlp-algorithm-details" numbered="true" toc="default">
<name>TLP Algorithm Details</name>
<section title="Initializing state" anchor="initializing-state"> <section anchor="initializing-state" numbered="true" toc="default">
<name>Initializing State</name>
<t>Reset TLP.is_retrans and TLP.end_seq when initiating a connection, fast recov <t>Reset TLP.is_retrans and TLP.end_seq when initiating a connection, fa
ery, or RTO recovery.</t> st recovery, or RTO recovery.</t>
<sourcecode name="" type="pseudocode"><![CDATA[
<figure><artwork>
TLP_init(): TLP_init():
TLP.end_seq = None TLP.end_seq = None
TLP.is_retrans = false TLP.is_retrans = false
</artwork></figure> ]]></sourcecode>
</section>
</section> <section anchor="scheduling-a-loss-probe" numbered="true" toc="default">
<section title="Scheduling a loss probe" anchor="scheduling-a-loss-probe"> <name>Scheduling a Loss Probe</name>
<t>
<t>The sender schedules a loss probe timeout (PTO) to transmit a segment during The sender schedules a loss probe timeout (PTO) to transmit a segment during the
the normal transmission process. The sender SHOULD start or restart a loss probe normal transmission process. The sender <bcp14>SHOULD</bcp14> start or restart
PTO timer after transmitting new data (that was not itself a loss probe) or upo a loss probe PTO timer after transmitting new data (that was not itself a loss p
n receiving an ACK that cumulatively acknowledges new data, unless it is already robe) or upon receiving an ACK that cumulatively acknowledges new data unless it
in fast recovery, RTO recovery, or the sender has segments delivered out-of-ord is already in fast recovery, RTO recovery, or segments have been SACKed (i.e.,
er (i.e. RACK.segs_sacked is not zero). These conditions are excluded because th RACK.segs_sacked is not zero). These conditions are excluded because they are ad
ey are addressed by similar mechanisms, like Limited Transmit [RFC3042], the RAC dressed by similar mechanisms, like Limited Transmit <xref target="RFC3042" form
K reordering timer, and F-RTO [RFC5682].</t> at="default"/>, the RACK reordering timer, and Forward RTO-Recovery (F-RTO) <xre
f target="RFC5682" format="default"/>.</t>
<t>The sender calculates the PTO interval by taking into account a number of fac <t>The sender calculates the PTO interval by taking into account a numbe
tors.</t> r of factors.</t>
<t>First, the default PTO interval is 2*SRTT. By that time, it is pruden
<t>First, the default PTO interval is 2*SRTT. By that time, it is prudent to dec t to declare that an ACK is overdue since under normal circumstances, i.e., no l
lare that an ACK is overdue, since under normal circumstances, i.e. no losses, a osses, an ACK typically arrives in one SRTT. Choosing the PTO to be exactly an
n ACK typically arrives in one SRTT. Choosing PTO to be exactly an SRTT would r SRTT would risk causing spurious probes given that network and end-host delay va
isk causing spurious probes, given that network and end-host delay variance can riance can cause an ACK to be delayed beyond the SRTT. Hence, the PTO is conserv
cause an ACK to be delayed beyond SRTT. Hence the PTO is conservatively chosen t atively chosen to be the next integral multiple of SRTT.</t>
o be the next integral multiple of SRTT.</t> <t>Second, when there is no SRTT estimate available, the PTO <bcp14>SHOU
LD</bcp14> be 1 second. This conservative value corresponds to the RTO value whe
<t>Second, when there is no SRTT estimate available, the PTO SHOULD be 1 second. n no SRTT is available, per <xref target="RFC6298" format="default"/>.</t>
This conservative value corresponds to the RTO value when no SRTT is available, <t>Third, when the FlightSize is one segment, the sender <bcp14>MAY</bcp
per [RFC6298].</t> 14> inflate the PTO by TLP.max_ack_delay to accommodate a potentially delayed ac
knowledgment and reduce the risk of spurious retransmissions. The actual value o
<t>Third, when FlightSize is one segment, the sender MAY inflate PTO by TLP.max_ f TLP.max_ack_delay is implementation specific. </t>
ack_delay to accommodate a potential delayed acknowledgment and reduce the risk <t>Finally, if the time at which an RTO would fire (here denoted as "TCP
of spurious retransmissions. The actual value of TLP.max_ack_delay is implementa _RTO_expiration()") is sooner than the computed time for the PTO, then the sende
tion-specific. </t> r schedules a TLP to be sent at that RTO time.</t>
<t>Summarizing these considerations in pseudocode form, a sender <bcp14>
<t>Finally, if the time at which an RTO would fire (here denoted "TCP_RTO_expira SHOULD</bcp14> use the following logic to select the duration of a PTO:</t>
tion()") is sooner than the computed time for the PTO, then the sender schedules <sourcecode name="" type="pseudocode"><![CDATA[
a TLP to be sent at that RTO time.</t> TLP_calc_PTO():
If SRTT is available:
<t>Summarizing these considerations in pseudocode form, a sender SHOULD use the PTO = 2 * SRTT
following logic to select the duration of a PTO:</t> If FlightSize is one segment:
PTO += TLP.max_ack_delay
<figure><artwork> Else:
TLP_calc_PTO(): If SRTT is available: PTO = 2 * SRTT If FlightS PTO = 1 sec
ize is one segment: PTO += TLP.max_ack_delay Else: PTO = 1 s
ec If Now() + PTO &gt; TCP_RTO_expiration(): PTO = TCP_RTO_expiration(
) - Now()
</artwork></figure>
</section>
<section title="Sending a loss probe upon PTO expiration" anchor="sending-a-loss
-probe-upon-pto-expiration">
<t>When the PTO timer expires, the sender MUST check whether both of the followi
ng conditions are met before sending a loss probe:</t>
<t><list style="numbers">
<t>First, there is no other previous loss probe still in flight. This ensures th
at at any given time the sender has at most one additional packet in flight beyo
nd the congestion window limit. This invariant is maintained using the state var
iable TLP.end_seq, which indicates the latest unacknowledged TLP loss probe’s en
ding sequence. It is reset when the loss probe has been acknowledged or is deeme
d lost or irrelevant.</t>
<t>Second, the sender has obtained an RTT measurement since the last loss probe
was transmitted, or, if the sender has not yet sent a loss probe on this connect
ion, since the start of the connection. This condition ensures that loss probe r
etransmissions do not prevent taking the RTT samples necessary to adapt SRTT to
an increase in path RTT.</t>
</list></t>
<t>If either one of these two conditions is not met, then the sender MUST skip s
ending a loss probe, and MUST proceed to re-armin the RTO timer, as specified at
the end of this section.</t>
<t>If both conditions are met, then the sender SHOULD transmit a previously unse
nt data segment, if one exists and the receive window allows, and increment the
FlightSize accordingly. Note that FlightSize could be one packet greater than th
e congestion window temporarily until the next ACK arrives.</t>
<t>If such an unsent segment is not available, then the sender SHOULD retransmit
the highest-sequence segment sent so far and set TLP.is_retrans to true. This s
egment is chosen to deal with the retransmission ambiguity problem in TCP. Suppo
se a sender sends N segments, and then retransmits the last segment (segment N)
as a loss probe, and then the sender receives a SACK for segment N. As long as t
he sender waits for the RACK reordering window to expire, it doesn't matter if t
hat SACK was for the original transmission of segment N or the TLP retransmissio
n; in either case the arrival of the SACK for segment N provides evidence that t
he N-1 segments preceding segment N were likely lost.</t>
<t>In the case where there is only one original outstanding segment of data (N=1
), the same logic (trivially) applies: an ACK for a single outstanding segment t
ells the sender the N-1=0 segments preceding that segment were lost. Furthermore
, whether there are N&gt;1 or N=1 outstanding segments, there is a question abou
t whether the original last segment or its TLP retransmission were lost; the sen
der estimates whether there was such a loss using TLP recovery detection (see be
low). </t>
<t>The sender MUST follow the RACK transmission procedures in the '’Upon Transmi
tting a Data Segment’’ section (see above) upon sending either a retransmission
or new data loss probe. This is critical for detecting losses using the ACK for
the loss probe.</t>
<t>After attempting to send a loss probe, regardless of whether a loss probe was
sent, the sender MUST re-arm the RTO timer, not the PTO timer, if FlightSize is
not zero. This ensures RTO recovery remains the last resort if TLP fails. The f
ollowing pseudo code summarizes the operations.</t>
<figure><artwork> If Now() + PTO > TCP_RTO_expiration():
PTO = TCP_RTO_expiration() - Now()
]]></sourcecode>
</section>
<section anchor="sending-a-loss-probe-upon-pto-expiration" numbered="true"
toc="default">
<name>Sending a Loss Probe upon PTO Expiration</name>
<t>
When the PTO timer expires, the sender <bcp14>MUST</bcp14> check whether both of
the following conditions are met before sending a loss probe:</t>
<ol spacing="normal" type="1"><li>First, there is no other previous loss
probe still in flight. This ensures that, at any given time, the sender has at
most one additional packet in flight beyond the congestion window limit. This in
variant is maintained using the state variable TLP.end_seq, which indicates the
latest unacknowledged TLP loss probe's ending sequence. It is reset when the los
s probe has been acknowledged or is deemed lost or irrelevant.</li>
<li>Second, the sender has obtained an RTT measurement since the last
loss probe transmission or the start of the connection, whichever was later. Thi
s condition ensures that loss probe retransmissions do not prevent taking the RT
T samples necessary to adapt SRTT to an increase in path RTT.</li>
</ol>
<t>If either one of these two conditions is not met, then the sender <bc
p14>MUST</bcp14> skip sending a loss probe and <bcp14>MUST</bcp14> proceed to re
-arm the RTO timer, as specified at the end of this section.</t>
<t>If both conditions are met, then the sender <bcp14>SHOULD</bcp14> tra
nsmit a previously unsent data segment, if one exists and the receive window all
ows, and increment the FlightSize accordingly. Note that the FlightSize could be
one packet greater than the congestion window temporarily until the next ACK ar
rives.</t>
<t>If such an unsent segment is not available, then the sender <bcp14>SH
OULD</bcp14> retransmit the highest-sequence segment sent so far and set TLP.is_
retrans to true. This segment is chosen to deal with the retransmission ambiguit
y problem in TCP. Suppose a sender sends N segments and then retransmits the las
t segment (segment N) as a loss probe, after which the sender receives a SACK fo
r segment N. As long as the sender waits for the RACK reordering window to expir
e, it doesn't matter if that SACK was for the original transmission of segment N
or the TLP retransmission; in either case, the arrival of the SACK for segment
N provides evidence that the N-1 segments preceding segment N were likely lost.<
/t>
<t>In a case where there is only one original outstanding segment of dat
a (N=1), the same logic (trivially) applies: an ACK for a single outstanding seg
ment tells the sender that the N-1=0 segments preceding that segment were lost.
Furthermore, whether there are N&gt;1 or N=1 outstanding segments, there is a qu
estion about whether the original last segment or its TLP retransmission were lo
st; the sender estimates whether there was such a loss using TLP recovery detect
ion (see below). </t>
<t>The sender <bcp14>MUST</bcp14> follow the RACK transmission procedure
s in the <xref target="upon-transmitting-a-data-segment" format="none">"Upon Tra
nsmitting a Data Segment"</xref> section upon sending either a retransmission or
a new data loss probe. This is critical for detecting losses using the ACK for
the loss probe.</t>
<t>
After attempting to send a loss probe, regardless of whether a loss probe was se
nt, the sender <bcp14>MUST</bcp14> re-arm the RTO timer, not the PTO timer, if t
he FlightSize is not zero. This ensures RTO recovery remains the last resort if
TLP fails. The following pseudocode summarizes the operations.</t>
<sourcecode name="" type="pseudocode"><![CDATA[
TLP_send_probe(): TLP_send_probe():
If TLP.end_seq is None and
If TLP.end_seq is None and
Sender has taken a new RTT sample since last probe or Sender has taken a new RTT sample since last probe or
the start of connection: the start of connection:
TLP.is_retrans = false Segment = send buffer segment starting at TLP.is_retrans = false
SND.NXT Segment = send buffer segment starting at SND.NXT
If Segment exists and fits the peer receive window limit: If Segment exists and fits the peer receive window limit:
/* Transmit the lowest-sequence unsent Segment */ /* Transmit the lowest-sequence unsent Segment */
Transmit Segment Transmit Segment
RACK_transmit_data(Segment) RACK_transmit_data(Segment)
TLP.end_seq = SND.NXT TLP.end_seq = SND.NXT
Increase FlightSize by Segment length Increase FlightSize by Segment length
Else: Else:
/* Retransmit the highest-sequence Segment sent */ Segment /* Retransmit the highest-sequence Segment sent */
= send buffer segment ending at SND.NXT Segment = send buffer segment ending at SND.NXT
Transmit Segment Transmit Segment
RACK_retransmit_data(Segment) RACK_retransmit_data(Segment)
TLP.end_seq = SND.NXT TLP.end_seq = SND.NXT
</artwork></figure> TLP.is_retrans = true
</section>
<section title="Detecting losses using the ACK of the loss probe" anchor="detect
ing-losses-using-the-ack-of-the-loss-probe">
<t>When there is packet loss in a flight ending with a loss probe, the feedback
solicited by a loss probe will reveal one of two scenarios, depending on the pat
tern of losses.</t>
<section title="General case: detecting packet losses using RACK " anchor="gener
al-case-detecting-packet-losses-using-rack-">
<t>If the loss probe and the ACK that acknowledges the probe are delivered succe
ssfully, RACK-TLP uses this ACK -- just as it would with any other ACK -- to det
ect if any segments sent prior to the probe were dropped. RACK would typically i
nfer that any unacknowledged data segments sent before the loss probe were lost,
since they were sent sufficiently far in the past (at least one PTO has elapsed
, plus one round-trip for the loss probe to be ACKed). More specifically, RACK_d
etect_loss() (step 5) would mark those earlier segments as lost. Then the sender
would trigger a fast recovery to recover those losses.</t>
</section>
<section title="Special case: detecting a single loss repaired by the loss probe
" anchor="special-case-detecting-a-single-loss-repaired-by-the-loss-probe">
<t>If the TLP retransmission repairs all the lost in-flight sequence ranges (i.e
. only the last segment in the flight was lost), the ACK for the loss probe appe
ars to be a regular cumulative ACK, which would not normally trigger the congest
ion control response to this packet loss event. The following TLP recovery detec
tion mechanism examines ACKs to detect this special case to make congestion cont
rol respond properly [RFC5681].</t>
<t>After a TLP retransmission, the sender checks for this special case of a sing
le loss that is recovered by the loss probe itself. To accomplish this, the send
er checks for a duplicate ACK or DSACK indicating that both the original segment
and TLP retransmission arrived at the receiver, meaning there was no loss. If t
he TLP sender does not receive such an indication, then it MUST assume that eith
er the original data segment, the TLP retransmission, or a corresponding ACK wer
e lost, for congestion control purposes.</t>
<t>If the TLP retransmission is spurious, a receiver that uses DSACK would retur
n an ACK that covers TLP.end_seq with a DSACK option (Case 1). If the receiver d
oes not support DSACK, it would return a DUPACK without any SACK option (Case 2)
. If the sender receives an ACK matching either case, then the sender estimates
that the receiver received both the original data segment and the TLP probe retr
ansmission, and so the sender considers the TLP episode to be done, and records
that fact by setting TLP.end_seq to None.</t>
<t>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 TLP probe ret
ransmission segment. At that time, if the TLP.end_seq is still set, and thus ind
icates that the TLP probe retransmission remains unacknowledged, then 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.</t>
<t>More precisely, on each ACK the sender executes the following:</t>
<figure><artwork> If FlightSize is not zero:
Rearm RTO timer to fire at timeout = now + RTO
]]></sourcecode>
</section>
<section anchor="detecting-losses-using-the-ack-of-the-loss-probe" numbere
d="true" toc="default">
<name>Detecting Losses Using the ACK of the Loss Probe</name>
<t>When there is packet loss in a flight ending with a loss probe, the f
eedback solicited by a loss probe will reveal one of two scenarios, depending on
the pattern of losses.</t>
<section anchor="general-case-detecting-packet-losses-using-rack-" numbe
red="true" toc="default">
<name>General Case: Detecting Packet Losses Using RACK</name>
<t>If the loss probe and the ACK that acknowledges the probe are deliv
ered successfully, RACK-TLP uses this ACK -- just as it would with any other ACK
-- to detect if any segments sent prior to the probe were dropped. RACK would t
ypically infer that any unacknowledged data segments sent before the loss probe
were lost, since they were sent sufficiently far in the past (where at least one
PTO has elapsed, plus one round trip for the loss probe to be ACKed). More spec
ifically, RACK_detect_loss() (<xref target="step5" format="none">Step 5</xref>)
would mark those earlier segments as lost. Then the sender would trigger a fast
recovery to recover those losses.</t>
</section>
<section anchor="special-case-detecting-a-single-loss-repaired-by-the-lo
ss-probe" numbered="true" toc="default">
<name>Special Case: Detecting a Single Loss Repaired by the Loss Probe
</name>
<t>If the TLP retransmission repairs all the lost in-flight sequence r
anges (i.e., only the last segment in the flight was lost), the ACK for the loss
probe appears to be a regular cumulative ACK, which would not normally trigger
the congestion control response to this packet loss event. The following TLP rec
overy detection mechanism examines ACKs to detect this special case to make cong
estion control respond properly <xref target="RFC5681" format="default"/>.</t>
<t>After a TLP retransmission, the sender checks for this special case
of a single loss that is recovered by the loss probe itself. To accomplish this
, the sender checks for a duplicate ACK or DSACK indicating that both the origin
al segment and TLP retransmission arrived at the receiver, which means there was
no loss. If the TLP sender does not receive such an indication, then it <bcp14>
MUST</bcp14> assume that the original data segment, the TLP retransmission, or a
corresponding ACK was lost for congestion control purposes.</t>
<t>
If the TLP retransmission is spurious, a receiver that uses DSACK would return a
n ACK that covers TLP.end_seq with a DSACK option (Case 1). If the receiver does
not support DSACK, it would return a DupAck without any SACK option (Case 2). I
f the sender receives an ACK matching either case, then the sender estimates tha
t the receiver received both the original data segment and the TLP probe retrans
mission. The sender considers the TLP episode to be done and records that fact b
y setting TLP.end_seq to None.
</t>
<t>Upon receiving an ACK that covers some sequence number after TLP.en
d_seq, the sender should have received any ACKs for the original segment and TLP
probe retransmission segment. At that time, if the TLP.end_seq is still set and
thus indicates that the TLP probe retransmission remains unacknowledged, then t
he sender should presume that at least one of its data segments was lost. The se
nder then <bcp14>SHOULD</bcp14> invoke a congestion control response equivalent
to a fast recovery.</t>
<t>More precisely, on each ACK, the sender executes the following:</t>
<sourcecode name="" type="pseudocode"><![CDATA[
TLP_process_ack(ACK): TLP_process_ack(ACK):
If TLP.end_seq is not None AND ACK's ack. number &gt;= TLP.end_seq: If TLP.end_seq is not None AND ACK's ack. number >= TLP.end_seq:
If not TLP.is_retrans: If not TLP.is_retrans:
TLP.end_seq = None /* TLP of new data delivered */ Else if TLP.end_seq = None /* TLP of new data delivered */
ACK has a DSACK option matching TLP.end_seq: Else if ACK has a DSACK option matching TLP.end_seq:
TLP.end_seq = None /* Case 1, above */ TLP.end_seq = None /* Case 1, above */
Else If ACK's ack. number &gt; TLP.end_seq: Else If ACK's ack. number > TLP.end_seq:
TLP.end_seq = None /* Repaired the single loss */ TLP.end_seq = None /* Repaired the single loss */
(Invoke congestion control to react to the loss event th (Invoke congestion control to react to
e probe has repaired) the loss event the probe has repaired)
Else If ACK is a DUPACK without any SACK option: Else If ACK is a DupAck without any SACK option:
TLP.end_seq = None /* Case 2, above */ TLP.end_seq = None /* Case 2, above */
</artwork></figure> ]]></sourcecode>
</section>
</section> </section>
</section> </section>
</section> <section anchor="managing-rack-tlp-timers" numbered="true" toc="default">
<section title="Managing RACK-TLP timers" anchor="managing-rack-tlp-timers"> <name>Managing RACK-TLP Timers</name>
<t>The RACK reordering timer, the TLP PTO timer, the RTO, and Zero Window
<t>The RACK reordering timer, the TLP PTO timer, the RTO, and Zero Window Probe Probe (ZWP) timer <xref target="RFC0793" format="default"/> are mutually exclusi
(ZWP) timer [RFC793] are mutually exclusive and used in different scenarios. Whe ve and are used in different scenarios. When arming a RACK reordering timer or T
n arming a RACK reordering timer or TLP PTO timer, the sender SHOULD cancel any LP PTO timer, the sender <bcp14>SHOULD</bcp14> cancel any other pending timers.
other pending timer(s). An implementation is expected to have one timer with an An implementation is expected to have one timer with an additional state variabl
additional state variable indicating the type of the timer.</t> e indicating the type of the timer.</t>
</section>
</section> <section anchor="discussion" numbered="true" toc="default">
<section title="Discussion" anchor="discussion"> <name>Discussion</name>
<section anchor="advantages-and-disadvantages" numbered="true" toc="defaul
<section title="Advantages and disadvantages" anchor="advantages-and-disadvantag t">
es"> <name>Advantages and Disadvantages</name>
<t>The biggest advantage of RACK-TLP is that every data segment, whether
<t>The biggest advantage of RACK-TLP is that every data segment, whether it is a it is an original data transmission or a retransmission, can be used to detect
n original data transmission or a retransmission, can be used to detect losses o losses of the segments sent chronologically prior to it. This enables RACK-TLP t
f the segments sent chronologically prior to it. This enables RACK-TLP to use fa o use fast recovery in cases with application-limited flights of data, lost retr
st recovery in cases with application-limited flights of data, lost retransmissi ansmissions, or data segment reordering events. Consider the following examples:
ons, or data segment reordering events. Consider the following examples:</t> </t>
<t><list style="numbers">
<t>Packet drops at the end of an application data flight: Consider a sender that
transmits an application-limited flight of three data segments (P1, P2, P3), an
d P1 and P3 are lost. Suppose the transmission of each segment is at least RACK.
reo_wnd after the transmission of the previous segment. RACK will mark P1 as los
t when the SACK of P2 is received, and this will trigger the retransmission of P
1 as R1. When R1 is cumulatively acknowledged, RACK will mark P3 as lost and the
sender will retransmit P3 as R3. This example illustrates how RACK is able to r
epair certain drops at the tail of a transaction without an RTO recovery. Notice
that neither the conventional duplicate ACK threshold [RFC5681], nor [RFC6675],
nor the Forward Acknowledgment [FACK] algorithm can detect such losses, becaus
e of the required segment or sequence count.</t>
<t>Lost retransmission: Consider a flight of three data segments (P1, P2, P3) th
at are sent; P1 and P2 are dropped. Suppose the transmission of each segment is
at least RACK.reo_wnd after the transmission of the previous segment. When P3 is
SACKed, RACK will mark P1 and P2 lost and they will be retransmitted as R1 and
R2. Suppose R1 is lost again but R2 is SACKed; RACK will mark R1 lost and trigge
r retransmission again. Again, neither the conventional three duplicate ACK thr
eshold approach, nor [RFC6675], nor the Forward Acknowledgment [FACK] algorithm
can detect such losses. And such a lost retransmission can happen when TCP is be
ing rate-limited, particularly by token bucket policers with large bucket depth
and low rate limit; in such cases retransmissions are often lost repeatedly beca
use standard congestion control requires multiple round trips to reduce the rate
below the policed rate.</t>
<t>Packet reordering: Consider a simple reordering event where a flight of segm
ents are sent as (P1, P2, P3). P1 and P2 carry a full payload of MSS octets, but
P3 has only a 1-octet payload. Suppose the sender has detected reordering previ
ously and thus RACK.reo_wnd is min_RTT/4. Now P3 is reordered and delivered firs
t, before P1 and P2. As long as P1 and P2 are delivered within min_RTT/4, RACK w
ill not consider P1 and P2 lost. But if P1 and P2 are delivered outside the reor
dering window, then RACK will still spuriously mark P1 and P2 lost.</t>
</list></t>
<t>The examples above show that RACK-TLP is particularly useful when the sender
is limited by the application, which can happen with interactive or request/resp
onse traffic. Similarly, RACK still works when the sender is limited by the rece
ive window, which can happen with applications that use the receive window to th
rottle the sender.</t>
<t>RACK-TLP works more efficiently with TCP Segmentation Offload (TSO) compared
to DUPACK-counting. RACK always marks the entire TSO aggregate lost because the
segments in the same TSO aggregate have the same transmission timestamp. By cont
rast, the algorithms based on sequence counting (e.g., [RFC6675] [RFC5681]) may
mark only a subset of segments in the TSO aggregate lost, forcing the stack to p
erform expensive fragmentation of the TSO aggregate, or to selectively tag indiv
idual segments lost in the scoreboard.</t>
<t>The main drawback of RACK-TLP is the additional states required compared to D
UPACK-counting. RACK requires the sender to record the transmission time of each
segment sent at a clock granularity that is finer than 1/4 of the minimum RTT o
f the connection. TCP implementations that record this already for RTT estimatio
n do not require any new per-packet state. But implementations that are not yet
recording segment transmission times will need to add per-packet internal state
(expected to be either 4 or 8 octets per segment or TSO aggregate) to track tran
smission times. In contrast, [RFC6675] loss detection approach does not require
any per-packet state beyond the SACK scoreboard; this is particularly useful on
ultra-low RTT networks where the RTT may be less than the sender TCP clock granu
larity (e.g. inside data-centers). Another disadvantage is the reordering timer
may expire prematurely (like any other retransmission timer) to cause higher spu
rious retransmission especially if DSACK is not supported.</t>
</section>
<section title="Relationships with other loss recovery algorithms" anchor="relat
ionships-with-other-loss-recovery-algorithms">
<t>The primary motivation of RACK-TLP is to provide a general alternative to som
e of the standard loss recovery algorithms [RFC5681] [RFC6675] [RFC5827] [RFC465
3]. In particular, [RFC6675] is not designed to handle lost retransmissions, so
its NextSeg() does not work for lost retransmissions and it does not specify the
corresponding required additional congestion response. Therefore, [RFC6675] MUS
T NOT be used with RACK-TLP; instead, a modified recovery algorithm that careful
ly addresses such a case is needed.</t>
<t>[RFC5827] [RFC4653] dynamically adjusts the duplicate ACK threshold based on
the current or previous flight sizes. RACK-TLP takes a different approach by usi
ng a time-based reordering window. RACK-TLP can be seen as an extended Early Ret
ransmit [RFC5827] without a FlightSize limit but with an additional reordering w
indow. [FACK] considers an original segment to be lost when its sequence range i
s sufficiently far below the highest SACKed sequence. In some sense RACK-TLP can
be seen as a generalized form of FACK that operates in time space instead of se
quence space, enabling it to better handle reordering, application-limited traff
ic, and lost retransmissions.</t>
<t>RACK-TLP is compatible with the standard RTO [RFC6298], RTO-restart [RFC7765]
, F-RTO [RFC5682] and Eifel algorithms [RFC3522]. This is because RACK-TLP only
detects loss by using ACK events. It neither changes the RTO timer calculation n
or detects spurious RTO. RACK-TLP slightly changes the behavior of [RFC6298] by
preceding the RTO with a TLP and reducing potential spurious retransmissions aft
er RTO.</t>
</section>
<section title="Interaction with congestion control" anchor="interaction-with-co
ngestion-control">
<t>RACK-TLP intentionally decouples loss detection from congestion control. RACK
-TLP only detects losses; it does not modify the congestion control algorithm [R
FC5681] [RFC6937]. A segment marked lost by RACK-TLP MUST NOT be retransmitted u
ntil congestion control deems this appropriate. As mentioned in the caption for
Figure 1, [RFC5681] mandates a principle that loss in two successive windows of
data, or the loss of a retransmission, must be taken as two indications of conge
stion and therefore trigger two separate reactions. [RFC6937] is RECOMMENDED for
the specific congestion control actions taken upon the losses detected by RACK-
TLP. In the absence of PRR, when RACK-TLP detects a lost retransmission the cong
estion control MUST trigger an additional congestion response per the aforementi
oned principle in [RFC5681]. If multiple original transmissions or retransmissio
ns were lost in a window, the congestion control specified in [RFC5681] only rea
cts once per window. The congestion control implementer is advised to carefully
consider this subtle situation introduced by RACK-TLP.</t>
<t>The only exception -- the only way in which 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 over-commit is account
ed for and credited in the in-flight data tracked for congestion control, so tha
t congestion control will erase the over-commit upon the next ACK. </t>
<t>If packet losses happen after reordering has been observed, RACK-TLP may take
longer to detect losses than the pure DUPACK-counting approach. In this case TC
P may continue to increase the congestion window upon receiving ACKs during this
time, making the sender more aggressive.</t>
<t>The following simple example compares how RACK-TLP and non-RACK-TLP loss dete
ction interacts with congestion control: suppose a sender has a congestion windo
w (cwnd) of 20 segments on a SACK-enabled connection. It sends 10 data segments
and all of them are lost.</t>
<t>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 retran
smit all the 10 lost segments using slow start. The recovery latency would be RT
O + 4*RTT, with an ending cwnd of 4 segments due to congestion window validation
.</t>
<t>With RACK-TLP, a sender would send the TLP after 2*RTT and get a DUPACK, enab
ling RACK to detect the losses and trigger fast recovery. If the sender implemen
ts Proportional Rate Reduction [RFC6937] it would slow start to retransmit the r
emaining 9 lost segments since the number of segments in flight (0) is lower tha
n the slow start threshold (10). The slow start would again take four round trip
s (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.</t>
<t>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 th
e RTT is large. The former case can happen in local area networks, data-center n
etworks, or content distribution networks with deep deployments. The latter case
can happen in developing regions with highly congested and/or high-latency netw
orks.</t>
</section>
<section title="TLP recovery detection with delayed ACKs" anchor="tlp-recovery-d
etection-with-delayed-acks">
<t>Delayed or stretched ACKs complicate the detection of repairs done by TLP, si
nce with such ACKs the sender takes a longer time to receive fewer ACKs than wou
ld normally be expected. To mitigate this complication, before sending a TLP los
s probe retransmission, the sender should attempt to wait long enough that the r
eceiver has sent any delayed ACKs that it is withholding. The sender algorithm d
escribed above features such a delay, in the form of TLP.max_ack_delay. Furtherm
ore, 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 the original and TLP retransmission both arrived at the receiver.</t
>
<t>If there is ACK loss or a delayed ACK without a DSACK, then 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: if there is reverse path congestion then reducing the congestion win
dow can be prudent.</t>
</section>
<section title="RACK-TLP for other transport protocols" anchor="rack-tlp-for-oth
er-transport-protocols">
<t>RACK-TLP can be implemented in other transport protocols (e.g., [QUIC-LR]). T
he [Sprout] loss detection algorithm was also independently designed to use a 10
ms reordering window to improve its loss detection similar to RACK.</t>
</section>
</section>
<section title="Security Considerations" anchor="security-considerations">
<t>RACK-TLP algorithm behavior is based on information conveyed in SACK options,
so it has security considerations similar to those described in the Security Co
nsiderations section of [RFC6675]. </t>
<t>Additionally, RACK-TLP has a lower risk profile than [RFC6675] because it is
not vulnerable to ACK-splitting attacks [SCWA99]: for an MSS-size segment sent,
the receiver or the attacker might send MSS ACKs that SACK or acknowledge one ad
ditional byte per ACK. This would not fool RACK. In such a scenario, RACK.xmit_t
s would not advance, because all the sequence ranges within the segment were tra
nsmitted at the same time, and thus carry the same transmission timestamp. In ot
her words, SACKing only one byte of a segment or SACKing the segment in entirety
have the same effect with RACK.</t>
</section>
<section title="IANA Considerations" anchor="iana-considerations">
<t>This document makes no request of IANA.</t>
<t>Note to RFC Editor: this section may be removed on publication as an RFC.</t>
</section>
<section title="Acknowledgments" anchor="acknowledgments">
<t>The authors thank Matt Mathis for his insights in FACK and Michael Welzl for
his per-packet timer idea that inspired this work. Eric Dumazet, Randy Stewart,
Van Jacobson, Ian Swett, Rick Jones, Jana Iyengar, Hiren Panchasara, Praveen Bal
asubramanian, Yoshifumi Nishida, Bob Briscoe, Felix Weinrank, Michael Tuexen, Ma
rtin Duke, Ilpo Jarvinen, Theresa Enghardt, Mirja Kuehlewind, Gorry Fairhurst, M
arkku Kojo, and Yi Huang contributed to this document or the implementations in
Linux, FreeBSD, Windows, and QUIC.</t>
</section>
</middle>
<back>
<references title="Normative References">
<reference anchor='RFC793'><front><title>Transmission Control Protocol</title><a
uthor initials='J.' surname='Postel' fullname='Jon Postel'></author><date year='
1981' month='September' /></front></reference>
<reference anchor='RFC2018'>
<front>
<title>TCP Selective Acknowledgment Options</title>
<author initials='M.' surname='Mathis' fullname='M. Mathis'>
<organization /></author>
<author initials='J.' surname='Mahdavi' fullname='J. Mahdavi'>
<organization /></author>
<date year='1996' month='October' />
</front>
<seriesInfo name='RFC' value='2018' />
<format type='TXT' target='http://www.rfc-editor.org/rfc/rfc2018.txt' />
</reference>
<reference anchor='RFC2119'>
<front>
<title>Key words for use in RFCs to Indicate Requirement Levels</title>
<author initials='S.' surname='Bradner' fullname='S. Bradner'>
<organization /></author>
<date year='1997' month='March' />
</front>
<seriesInfo name='RFC' value='2119' />
<format type='TXT' target='http://www.rfc-editor.org/rfc/rfc2119.txt' />
</reference>
<reference anchor='RFC2883'>
<front>
<title>An Extension to the Selective Acknowledgement (SACK) Option for TCP</titl
e>
<author initials='S.' surname='Floyd' fullname='S. Floyd'>
<organization /></author>
<author initials='J.' surname='Mahdavi' fullname='J. Mahdavi'>
<organization /></author>
<author initials='M.' surname='Mathis' fullname='M. Mathis'>
<organization /></author>
<author initials='M.' surname='Podolsky' fullname='M. Podolsky'>
<organization /></author>
<date year='2000' month='July' />
<abstract>
<t>This note defines an extension of the Selective Acknowledgement (SACK) Option
[RFC2018] for TCP. RFC 2018 specified the use of the SACK option for acknowled
ging out-of-sequence data not covered by TCP's cumulative acknowledgement field.
This note extends RFC 2018 by specifying the use of the SACK option for acknow
ledging duplicate packets. This note suggests that when duplicate packets are re
ceived, the first block of the SACK option field can be used to report the seque
nce numbers of the packet that triggered the acknowledgement. This extension to
the SACK option allows the TCP sender to infer the order of packets received at
the receiver, allowing the sender to infer when it has unnecessarily retransmit
ted a packet. A TCP sender could then use this information for more robust oper
ation in an environment of reordered packets [BPS99], ACK loss, packet replicati
on, and/or early retransmit timeouts.
</t></abstract></front>
<seriesInfo name='RFC' value='2883' />
<format type='TXT' target='http://www.rfc-editor.org/rfc/rfc2883.txt' />
</reference>
<reference anchor='RFC5681'>
<front>
<title>TCP Congestion Control</title>
<author initials='M.' surname='Allman' fullname='M. Allman'>
<organization /></author>
<author initials='V.' surname='Paxson' fullname='V. Paxson'>
<organization /></author>
<author initials='E.' surname='Blanton' fullname='E. Blanton'>
<organization /></author>
<date year='2009' month='September' />
<abstract>
<t>This document defines TCP's four intertwined congestion control algorithms: s
low start, congestion avoidance, fast retransmit, and fast recovery. In additio
n, the document specifies how TCP should begin transmission after a relatively l
ong idle period, as well as discussing various acknowledgment generation methods
. This document obsoletes RFC 2581. [STANDARDS-TRACK]</t></abstract></front>
<seriesInfo name='RFC' value='5681' />
<format type='TXT' octets='44339' target='http://www.rfc-editor.org/rfc/rfc5681.
txt' />
</reference>
<reference anchor='RFC6298'>
<front>
<title>Computing TCP's Retransmission Timer</title>
<author initials='V.' surname='Paxson' fullname='V. Paxson'>
<organization /></author>
<author initials='M.' surname='Allman' fullname='M. Allman'>
<organization /></author>
<author initials='J.' surname='Chu' fullname='J. Chu'>
<organization /></author>
<author initials='M.' surname='Sargent' fullname='M. Sargent'>
<organization /></author>
<date year='2011' month='June' />
<abstract>
<t>This document defines the standard algorithm that Transmission Control Protoc
ol (TCP) senders are required to use to compute and manage their retransmission
timer. It expands on the discussion in Section 4.2.3.1 of RFC 1122 and upgrades
the requirement of supporting the algorithm from a SHOULD to a MUST. This docu
ment obsoletes RFC 2988.
</t></abstract></front>
<seriesInfo name='RFC' value='6298' />
<format type='TXT' target='http://www.rfc-editor.org/rfc/rfc6298.txt' />
</reference>
<reference anchor='RFC6675'>
<front>
<title>A Conservative Loss Recovery Algorithm Based on Selective Acknowledgment
(SACK) for TCP
</title>
<author initials='E.' surname='Blanton' fullname='E. Blanton'>
<organization /></author>
<author initials='M.' surname='Allman' fullname='M. Allman'>
<organization /></author>
<author initials='L.' surname='Wang' fullname='L. Wang'>
<organization /></author>
<author initials='I.' surname='Jarvinen' fullname='I. Jarvinen'>
<organization /></author>
<author initials='M.' surname='Kojo' fullname='M. Kojo'>
<organization /></author>
<author initials='Y.' surname='Nishida' fullname='Y. Nishida'>
<organization /></author>
<date year='2012' month='August' />
<abstract>
<t>This document presents a conservative loss recovery algorithm for TCP that is
based on the use of the selective acknowledgment (SACK) TCP option. The algori
thm presented in this document conforms to the spirit of the current congestion
control specification (RFC 2581), but allows TCP senders to recover more effecti
vely when multiple segments are lost from a single flight of data. [STANDARDS-TR
ACK]</t></abstract></front>
<seriesInfo name='RFC' value='6675' />
<format type='TXT' octets='27855' target='http://www.rfc-editor.org/rfc/rfc6675.
txt' />
</reference>
<reference anchor='RFC7323'><front><title>TCP Extensions for High Performance</t
itle><author initials='D.' surname='Borman' fullname='David Borman'></author><au
thor initials='B.' surname='Braden' fullname='Bob Braden'></author><author initi
als='V.' surname='Jacobson' fullname='Van Jacobson'></author><author initials='R
.' surname='Scheffenegger' fullname='Richard Scheffenegger'></author><date year=
'2014' month='September' /></front></reference>
<reference anchor='RFC8174'><front><title>Ambiguity of Uppercase vs Lowercase in
RFC 2119 Key Words</title><author initials='B.' surname='Leiba' fullname='B. Le
iba'></author><date year='2017' month='May' /></front></reference>
</references>
<references title="Informative References"> <ol spacing="normal" type="1"><li>Packet drops at the end of an applicat ion data flight: Consider a sender that transmits an application-limited flight of three data segments (P1, P2, P3), and P1 and P3 are lost. Suppose the transmi ssion of each segment is at least RACK.reo_wnd after the transmission of the pre vious segment. RACK will mark P1 as lost when the SACK of P2 is received, and th is will trigger the retransmission of P1 as R1. When R1 is cumulatively acknowle dged, RACK will mark P3 as lost, and the sender will retransmit P3 as R3. This e xample illustrates how RACK is able to repair certain drops at the tail of a tra nsaction without an RTO recovery. Notice that neither the conventional duplicate ACK threshold <xref target="RFC5681" format="default"/>, nor the loss recovery algorithm <xref target="RFC6675" format="default"/>, nor the Forward Acknowledgm ent <xref target="FACK" format="default"/> algorithm can detect such losses beca use of the required segment or sequence count.</li>
<reference anchor='FACK'> <li>Lost retransmission: Consider a flight of three data segments (P1,
<front> P2, P3) that are sent; P1 and P2 are dropped. Suppose the transmission of each
<title>Forward acknowledgement: refining TCP congestion control</title> segment is at least RACK.reo_wnd after the transmission of the previous segment.
<author initials='M' surname='Mathis' fullname='Matt Mathis'> When P3 is SACKed, RACK will mark P1 and P2 as lost, and they will be retransmi
<organization /></author> tted as R1 and R2. Suppose R1 is lost again but R2 is SACKed; RACK will mark R1
<author initials='M' surname='Jamshid' fullname='Jamshid Mahdavi'> as lost and trigger retransmission again. Again, neither the conventional three
<organization /></author> -duplicate ACK threshold approach, nor the loss recovery algorithm <xref target=
<date year='1996' /> "RFC6675" format="default"/>, nor the Forward Acknowledgment <xref target="FACK"
</front> format="default"/> algorithm can detect such losses. And such a lost retransmis
<seriesInfo name='ACM SIGCOMM Computer Communication Review, Volume 26, Issue 4, sion can happen when TCP is being rate-limited, particularly by token bucket pol
Oct. 1996.' value=''/> icers with a large bucket depth and low rate limit; in such cases, retransmissio
</reference> ns are often lost repeatedly because standard congestion control requires multip
le round trips to reduce the rate below the policed rate.</li>
<li>Packet reordering: Consider a simple reordering event where a fli
ght of segments are sent as (P1, P2, P3). P1 and P2 carry a full payload of Maxi
mum Sender Size (MSS) octets, but P3 has only a 1-octet payload. Suppose the sen
der has detected reordering previously and thus RACK.reo_wnd is min_RTT/4. Now P
3 is reordered and delivered first, before P1 and P2. As long as P1 and P2 are d
elivered within min_RTT/4, RACK will not consider P1 and P2 lost. But if P1 and
P2 are delivered outside the reordering window, then RACK will still spuriously
mark P1 and P2 as lost.
</li>
</ol>
<t>The examples above show that RACK-TLP is particularly useful when the
sender is limited by the application, which can happen with interactive or requ
est/response traffic. Similarly, RACK still works when the sender is limited by
the receive window, which can happen with applications that use the receive wind
ow to throttle the sender.</t>
<t>RACK-TLP works more efficiently with TCP Segmentation Offload (TSO) c
ompared to DupAck counting. RACK always marks the entire TSO aggregate as lost b
ecause the segments in the same TSO aggregate have the same transmission timesta
mp. By contrast, the algorithms based on sequence counting (e.g., <xref target="
RFC6675" format="default"/>, <xref target="RFC5681" format="default"/>) may mark
only a subset of segments in the TSO aggregate as lost, forcing the stack to pe
rform expensive fragmentation of the TSO aggregate or to selectively tag individ
ual segments as lost in the scoreboard.</t>
<t>The main drawback of RACK-TLP is the additional state required compar
ed to DupAck counting. RACK requires the sender to record the transmission time
of each segment sent at a clock granularity that is finer than 1/4 of the minimu
m RTT of the connection. TCP implementations that already record this for RTT es
timation do not require any new per-packet state. But implementations that are n
ot yet recording segment transmission times will need to add per-packet internal
state (expected to be either 4 or 8 octets per segment or TSO aggregate) to tra
ck transmission times. In contrast, the loss detection approach described in <xr
ef target="RFC6675" format="default"/> does not require any per-packet state bey
ond the SACK scoreboard; this is particularly useful on ultra-low RTT networks w
here the RTT may be less than the sender TCP clock granularity (e.g., inside dat
a centers). Another disadvantage is that the reordering timer may expire prematu
rely (like any other retransmission timer) and cause higher spurious retransmiss
ions, especially if DSACK is not supported.</t>
</section>
<section anchor="relationships-with-other-loss-recovery-algorithms" number
ed="true" toc="default">
<name>Relationships with Other Loss Recovery Algorithms</name>
<t>The primary motivation of RACK-TLP is to provide a general alternativ
e to some of the standard loss recovery algorithms <xref target="RFC5681" format
="default"/> <xref target="RFC6675" format="default"/> <xref target="RFC5827" fo
rmat="default"/> <xref target="RFC4653" format="default"/>. In particular, the S
ACK loss recovery algorithm for TCP <xref target="RFC6675" format="default"/> is
not designed to handle lost retransmissions, so its NextSeg() does not work for
lost retransmissions, and it does not specify the corresponding required additi
onal congestion response. Therefore, the algorithm <xref target="RFC6675" format
="default"/> <bcp14>MUST NOT</bcp14> be used with RACK-TLP; instead, a modified
recovery algorithm that carefully addresses such a case is needed.</t>
<reference anchor='RFC3042'> <t>The Early Retransmit mechanism <xref target="RFC5827" format="default
<front> "/> and NCR for TCP <xref target="RFC4653" format="default"/> dynamically adjust
<title>Enhancing TCP's Loss Recovery Using Limited Transmit</title> the duplicate ACK threshold based on the current or previous flight sizes. RACK
<author initials='M.' surname='Allman'> -TLP takes a different approach by using a time-based reordering window. RACK-TL
<organization /></author> P can be seen as an extended Early Retransmit <xref target="RFC5827" format="def
<author initials='H.' surname='Balakrishnan'> ault"/> without a FlightSize limit but with an additional reordering window. <xr
<organization /></author> ef target="FACK" format="default"/> considers an original segment to be lost whe
<author initials='S.' surname='Floyd'> n its sequence range is sufficiently far below the highest SACKed sequence. In s
<organization /></author> ome sense, RACK-TLP can be seen as a generalized form of FACK that operates in t
<date year='2001' month='January' /> ime space instead of sequence space, enabling it to better handle reordering, ap
</front> plication-limited traffic, and lost retransmissions.</t>
</reference> <t>RACK-TLP is compatible with the standard RTO <xref target="RFC6298" f
ormat="default"/>, RTO Restart <xref target="RFC7765" format="default"/>, F-RTO
<xref target="RFC5682" format="default"/>, and Eifel algorithms <xref target="RF
C3522" format="default"/>. This is because RACK-TLP only detects loss by using A
CK events. It neither changes the RTO timer calculation nor detects spurious RTO
s. RACK-TLP slightly changes the behavior of <xref target="RFC6298" format="defa
ult"/> by preceding the RTO with a TLP and reducing potential spurious retransmi
ssions after RTO.</t>
</section>
<section anchor="interaction-with-congestion-control" numbered="true" toc=
"default">
<name>Interaction with Congestion Control</name>
<t>RACK-TLP intentionally decouples loss detection from congestion contr
ol. RACK-TLP only detects losses; it does not modify the congestion control algo
rithm <xref target="RFC5681" format="default"/> <xref target="RFC6937" format="d
efault"/>. A segment marked as lost by RACK-TLP <bcp14>MUST NOT</bcp14> be retra
nsmitted until congestion control deems this appropriate. As mentioned in the pa
ragraph following <xref target="fig1"/> (<xref target="fig1desc"/>), <xref targe
t="RFC5681" format="default"/> mandates a principle that 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 Ra
te Reduction (PRR) algorithm <xref target="RFC6937" format="default"/> is <bcp14
>RECOMMENDED</bcp14> for the specific congestion control actions taken upon the
losses detected by RACK-TLP.
<reference anchor='RFC3522'><front> In the absence of PRR <xref target="RFC6937"/>, when RACK-TLP detects a lost ret
<title>The Eifel Detection Algorithm for TCP</title> ransmission, the congestion control <bcp14>MUST</bcp14> trigger an additional co
<author initials='R.' surname='Ludwig'></author> ngestion response per the aforementioned principle in <xref target="RFC5681" for
<author initials='M.' surname='Meyer'></author> mat="default"/>. If multiple original transmissions or retransmissions were lost
<date year='2003' month='April'/> in a window, the congestion control specified in <xref target="RFC5681" format=
</front> "default"/> only reacts once per window. The congestion control implementer is a
</reference> dvised to carefully consider this subtle situation introduced by RACK-TLP.</t>
<t>The only exception -- the only way in which RACK-TLP modulates the co
ngestion control algorithm -- is that one outstanding loss probe can be sent eve
n 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 that congestion control will erase the overcommit upon the next ACK. </t>
<t>If packet losses happen after reordering has been observed, RACK-TLP
may take longer to detect losses than the pure DupAck counting approach. In this
case, TCP may continue to increase the congestion window upon receiving ACKs du
ring this time, making the sender more aggressive.</t>
<t>
The following simple example compares how RACK-TLP and non-RACK-TLP loss detecti
on interact with congestion control: suppose a sender has a congestion window (c
wnd) of 20 segments on a SACK-enabled connection. It sends 10 data segments, and
all of them are lost.</t>
<t>Without RACK-TLP, the sender would time out, reset cwnd to 1, and ret
ransmit the first segment. It would take four round trips (1 + 2 + 4 + 3 = 10) t
o retransmit all the 10 lost segments using slow start. The recovery latency wou
ld be RTO + 4*RTT, with an ending cwnd of 4 segments due to congestion window va
lidation.</t>
<t>With RACK-TLP, a sender would send the TLP after 2*RTT and get a DupA
ck, enabling RACK to detect the losses and trigger fast recovery. If the sender
implements Proportional Rate Reduction <xref target="RFC6937" format="default"/>
, it would slow start to retransmit the remaining 9 lost segments since the numb
er of segments in flight (0) is lower than the slow start threshold (10). The sl
ow start would again take four round trips (1 + 2 + 4 + 3 = 10) to retransmit al
l 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.</t>
<t>The difference in recovery latency (RTO + 4*RTT vs 6*RTT) can be sign
ificant if the RTT is much smaller than the minimum RTO (1 second in <xref targe
t="RFC6298" format="default"/>) or if the RTT is large. The former case can happ
en in local area networks, data center networks, or content distribution network
s with deep deployments. The latter case can happen in developing regions with h
ighly congested and/or high-latency networks.</t>
</section>
<section anchor="tlp-recovery-detection-with-delayed-acks" numbered="true"
toc="default">
<name>TLP Recovery Detection with Delayed ACKs</name>
<t>Delayed or stretched ACKs complicate the detection of repairs done by
TLP since, with such ACKs, the sender takes a longer time to receive fewer ACKs
than would normally be expected. To mitigate this complication, before sending
a TLP loss probe retransmission, the sender should attempt to wait long enough t
hat the receiver has sent any delayed ACKs that it is withholding. The sender al
gorithm 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 inf
ormation to infer that the original and TLP retransmission both arrived at the r
eceiver.</t>
<t>If there is ACK loss or a delayed ACK without a DSACK, then this algo
rithm is conservative because the sender will reduce the congestion window when,
in fact, there was no packet loss. In practice, this is acceptable and potenti
ally even desirable: if there is reverse path congestion, then reducing the cong
estion window can be prudent.</t>
</section>
<section anchor="rack-tlp-for-other-transport-protocols" numbered="true" t
oc="default">
<name>RACK-TLP for Other Transport Protocols</name>
<t>RACK-TLP can be implemented in other transport protocols (e.g., <xref
target="I-D.ietf-quic-recovery" format="default"/>). The <xref target="SPROUT"
format="default"/> loss detection algorithm was also independently designed to u
se a 10 ms reordering window to improve its loss detection similar to RACK.</t>
</section>
</section>
<section anchor="security-considerations" numbered="true" toc="default">
<name>Security Considerations</name>
<t>RACK-TLP algorithm behavior is based on information conveyed in SACK op
tions, so it has security considerations similar to those described in the Secur
ity Considerations section of <xref target="RFC6675" format="default"/>. </t>
<t>Additionally, RACK-TLP has a lower risk profile than the loss recovery
algorithm <xref target="RFC6675" format="default"/> because it is not vulnerable
to ACK-splitting attacks <xref target="SCWA99" format="default"/>: for an MSS-s
ized segment sent, the receiver or the attacker might send MSS ACKs that selecti
vely or cumulatively acknowledge one additional byte per ACK. This would not foo
l RACK. In such a scenario, RACK.xmit_ts would not advance because all the seque
nce ranges within the segment were transmitted at the same time and thus carry t
he same transmission timestamp. In other words, SACKing only one byte of a segme
nt or SACKing the segment in entirety have the same effect with RACK.</t>
</section>
<section anchor="iana-considerations" numbered="true" toc="default">
<name>IANA Considerations</name>
<t>This document has no IANA actions.</t>
</section>
</middle>
<back>
<reference anchor='RFC4653'><front> <displayreference target="I-D.ietf-quic-recovery" to="QUIC-LR"/>
<title>Improving the Robustness of TCP to Non-Congestion Events</title> <displayreference target="RFC0793" to="RFC793"/>
<author initials='S.' surname='Bhandarkar'></author>
<author initials='A. L. N.' surname='Reddy'></author>
<author initials='M.' surname='Allman'></author>
<author initials='E.' surname='Blanton'></author>
<date year='2006' month='August'/>
</front>
</reference>
<reference anchor='RFC5682'> <references>
<front> <name>References</name>
<title>Forward RTO-Recovery (F-RTO): An Algorithm for Detecting Spurious Retrans <references>
mission Timeouts with TCP</title> <name>Normative References</name>
<author initials='P.' surname='Sarolahti' fullname='P. Sarolahti'>
<organization /></author>
<author initials='M.' surname='Kojo' fullname='M. Kojo'>
<organization /></author>
<author initials='K.' surname='Yamamoto' fullname='K. Yamamoto'>
<organization /></author>
<author initials='M.' surname='Hata' fullname='M. Hata'>
<organization /></author>
<date year='2009' month='September' />
<abstract>
<t>The purpose of this document is to move the F-RTO (Forward RTO-Recovery) func
tionality for TCP in RFC 4138 from Experimental to Standards Track status. The F
-RTO support for Stream Control Transmission Protocol (SCTP) in RFC 4138 remains
with Experimental status. See Appendix B for the differences between this docum
ent and RFC 4138.&lt;/t>&lt;t> Spurious retransmission timeouts cause suboptimal
TCP performance because they often result in unnecessary retransmission of the
last window of data. This document describes the F-RTO detection algorithm for d
etecting spurious TCP retransmission timeouts. F-RTO is a TCP sender-only algori
thm that does not require any TCP options to operate. After retransmitting the f
irst unacknowledged segment triggered by a timeout, the F-RTO algorithm of the T
CP sender monitors the incoming acknowledgments to determine whether the timeout
was spurious. It then decides whether to send new segments or retransmit unackn
owledged segments. The algorithm effectively helps to avoid additional unnecessa
ry retransmissions and thereby improves TCP performance in the case of a spuriou
s timeout. [STANDARDS-TRACK]</t></abstract></front>
<seriesInfo name='RFC' value='5682' />
<format type='TXT' octets='47337' target='http://www.rfc-editor.org/rfc/rfc5682.
txt' />
</reference>
<reference anchor='RFC5827'> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<front> FC.0793.xml"/>
<title>Early Retransmit for TCP and Stream Control Transmission Protocol (SCTP)< <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
/title> FC.2018.xml"/>
<author initials='M.' surname='Allman' fullname='M. Allman'> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<organization /></author> FC.2119.xml"/>
<author initials='U.' surname='Ayesta' fullname='U. Ayesta'> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<organization /></author> FC.2883.xml"/>
<author initials='L.' surname='Wang' fullname='L. Wang'> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<organization /></author> FC.5681.xml"/>
<author initials='J.' surname='Blanton' fullname='J. Blanton'> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<organization /></author> FC.6298.xml"/>
<author initials='P.' surname='Hurtig' fullname='P. Hurtig'> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<organization /></author> FC.6675.xml"/>
<date year='2010' month='April' /> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<abstract> FC.7323.xml"/>
<t>This document proposes a new mechanism for TCP and Stream Control Transmissio <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
n Protocol (SCTP) that can be used to recover lost segments when a connection's FC.8174.xml"/>
congestion window is small. The "Early Retransmit" mechanism allows the transpo
rt to reduce, in certain special circumstances, the number of duplicate acknowle
dgments required to trigger a fast retransmission. This allows the transport to
use fast retransmit to recover segment losses that would otherwise require a le
ngthy retransmission timeout.
</t></abstract></front>
<seriesInfo name='RFC' value='5827' /> </references>
<format type='TXT' target='http://www.rfc-editor.org/rfc/rfc5827.txt' /> <references>
</reference> <name>Informative References</name>
<reference anchor='RFC6937'><front> <reference anchor="FACK">
<title>Proportional Rate Reduction for TCP</title> <front>
<author initials='M.' surname='Mathis' fullname='Matt Mathis'></author> <title>Forward acknowledgement: refining TCP congestion control</tit
<author initials='N.' surname='Dukkipati' fullname='Nandita Dukkipati'></author> le>
<author initials='Y.' surname='Cheng' fullname='Yuchung Cheng'></author> <author initials="M." surname="Mathis" fullname="Matt Mathis">
<date year='2013' month='May' /> <organization/>
</front></reference> </author>
<author initials="J." surname="Mahdavi" fullname="Jamshid Mahdavi">
<organization/>
</author>
<date year="1996" month="August"/>
</front>
<seriesInfo name="ACM SIGCOMM Computer Communication Review" value="Vo
lume 26, Issue 4"/>
<seriesInfo name="DOI" value="10.1145/248157.248181"/>
</reference>
<reference anchor='RFC7765'><front> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RF
<title>TCP and SCTP RTO Restart</title> C.3042.xml"/>
<author initials='P.' surname='Hurtig'></author> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RF
<author initials='A.' surname='Brunstrom'></author> C.3522.xml"/>
<author initials='A.' surname='Petlund'></author> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RF
<author initials='M.' surname='Welzl'></author> C.4653.xml"/>
<date year='2016' month='February'/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
</front> FC.5682.xml"/>
</reference> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.5827.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.6937.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.7765.xml"/>
<reference anchor='DMCG11'> <reference anchor="DMCG11">
<front> <front>
<title>Proportional Rate Reduction for TCP <title>Proportional Rate Reduction for TCP
</title> </title>
<author initials='N' surname='Dukkipati'></author> <author initials="N." surname="Dukkipati" fullname="Nandita Dukkipat
<author initials='M' surname='Matthis'></author> i"/>
<author initials='Y' surname='Cheng'></author> <author initials="M." surname="Matthis" fullname="Matt Mathis"/>
<author initials='M' surname='Ghobadi'></author> <author initials="Y." surname="Cheng" fullname="Yuchung Cheng"/>
<date year='2011' /> <author initials="M." surname="Ghobadi" fullname="Monia Ghobadi"/>
</front> <date month="November" year="2011"/>
<seriesInfo name='ACM SIGCOMM Conference on Internet Measurement' value=''/> </front>
</reference> <seriesInfo name="Proceedings of the 2011 ACM SIGCOMM Conference on In
ternet Measurement Conference" value="pp. 155-170"/>
<seriesInfo name="DOI" value="10.1145/2068816.2068832"/>
</reference>
<reference anchor='QUIC-LR'><front> <xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D
<title>QUIC Loss Detection and Congestion Control .ietf-quic-recovery.xml"/>
</title>
<author initials='J.' surname='Iyengar'></author>
<author initials='I.' surname='Swett'></author>
<date year='2020' month='Octobor'/>
</front>
<seriesInfo name='Internet-Draft' value='draft-ietf-quic-recovery' />
</reference>
<reference anchor='Sprout'><front> <reference anchor="SPROUT">
<title>Stochastic Forecasts Achieve High Throughput and Low Delay over Cellular <front>
Networks <title>Stochastic Forecasts Achieve High Throughput and Low Delay over Ce
llular Networks
</title> </title>
<author initials='K.' surname='Winstein'></author> <author initials="K." surname="Winstein" fullname="Keith Winstein"/>
<author initials='A.' surname='Sivaraman'></author> <author initials="A." surname="Sivaraman" fullname="Anirudh Sivarama
<author initials='H.' surname='Balakrishnan'></author> n"/>
<date year='2013'/> <author initials="H." surname="Balakrishnan" fullname="Hari Balakris
</front> hnan"/>
<seriesInfo name='USENIX Symposium on Networked Systems Design and Implementatio <date year="2013"/>
n (NSDI)' value=''/> </front>
</reference> <refcontent>10th USENIX Symposium on Networked Systems Design and Impl
ementation (NSDI '13)"</refcontent>
<reference anchor='SCWA99'>
<front>
<title>TCP Congestion Control With a Misbehaving Receiver</title>
<author initials='S' surname='Savage' fullname='S. Savage'>
<organization /></author>
<author initials='N' surname='Cardwell' fullname='N. Cardwell'>
<organization /></author>
<author initials='D' surname='Wetherall' fullname='D. Wetherall'>
<organization /></author>
<author initials='T' surname='Anderson' fullname='T. Anderson'>
<organization /></author>
<date year='1999' />
</front>
<seriesInfo name='ACM Computer Communication Review, 29(5)' value=''/>
</reference> </reference>
<reference anchor='POLICER16'> <reference anchor="SCWA99">
<front> <front>
<title>An Analysis of Traffic Policing in the Web <title>TCP congestion control with a misbehaving receiver</title>
</title> <author initials="S." surname="Savage" fullname="Stefan Savage">
<author initials='T' surname='Flach' fullname='T. Flach'><organization /></autho <organization/>
r> </author>
<author initials='P' surname='Papageorge' fullname='P. Papageorge'><organization <author initials="N." surname="Cardwell" fullname="Neal Cardwell">
/></author> <organization/>
<author initials='A' surname='Terzis' fullname='A. Terzis'><organization /></aut </author>
hor> <author initials="D." surname="Wetherall" fullname="David Wetherall"
<author initials='L' surname='Pedrosa' fullname='L. Pedrosa'><organization /></a >
uthor> <organization/>
<author initials='Y' surname='Cheng' fullname='Y. Cheng'><organization /></autho </author>
r> <author initials="T." surname="Anderson" fullname="Tom Anderson">
<author initials='T' surname='Karim' fullname='T. Karim'><organization /></autho <organization/>
r> </author>
<author initials='E' surname='Katz-Bassett' fullname='E. Katz-Bassett'><organiza <date year="1999" month="October"/>
tion /></author> </front>
<author initials='R' surname='Govindan' fullname='R. Govindan'><organization />< <seriesInfo name="ACM Computer Communication Review" value="29(5)"/>
/author> <seriesInfo name="DOI" value="10.1145/505696.505704"/>
<date year='2016' /> </reference>
</front>
<seriesInfo name='ACM SIGCOMM' value=''/>
</reference>
</references> <reference anchor="POLICER16">
</back> <front>
<title>An Internet-Wide Analysis of Traffic Policing</title>
<author initials="T." surname="Flach" fullname="Tobias Flach">
<organization/>
</author>
<author initials="P." surname="Papageorge" fullname="Pavlos Papageor
ge">
<organization/>
</author>
<author initials="A." surname="Terzis" fullname="Andreas Terzis">
<organization/>
</author>
<author initials="L." surname="Pedrosa" fullname="Luis Pedrosa">
<organization/>
</author>
<author initials="Y." surname="Cheng" fullname="Yuchung Cheng">
<organization/>
</author>
<author initials="T." surname="Karim" fullname="Tayeb Karim">
<organization/>
</author>
<author initials="E." surname="Katz-Bassett" fullname="Ethan Katz-Ba
ssett">
<organization/>
</author>
<author initials="R." surname="Govindan" fullname="Ramesh Govindan">
<organization/>
</author>
<date year="2016" month="August"/>
</front>
<seriesInfo name="DOI" value="10.1145/2934872.2934873"/>
<refcontent>Proceedings of the 2016 ACM SIGCOMM Conference pp. 468-482<
/refcontent>
</reference>
</references>
</references>
<section anchor="acknowledgments" numbered="false" toc="default">
<name>Acknowledgments</name>
<t>The authors thank <contact fullname="Matt Mathis"/> for his insights in
FACK and <contact fullname="Michael Welzl"/> for his per-packet timer idea that
inspired this work. <contact fullname="Eric Dumazet"/>, <contact fullname="Rand
y Stewart"/>, <contact fullname="Van Jacobson"/>, <contact fullname="Ian Swett"/
>, <contact fullname="Rick Jones"/>, <contact fullname="Jana Iyengar"/>, <contac
t fullname="Hiren Panchasara"/>, <contact fullname="Praveen Balasubramanian"/>,
<contact fullname="Yoshifumi Nishida"/>, <contact fullname="Bob Briscoe"/>, <con
tact fullname="Felix Weinrank"/>, <contact fullname="Michael Tüxen"/>, <contact
fullname="Martin Duke"/>, <contact fullname="Ilpo Jarvinen"/>, <contact fullname
="Theresa Enghardt"/>, <contact fullname="Mirja Kühlewind"/>, <contact fullname=
"Gorry Fairhurst"/>, <contact fullname="Markku Kojo"/>, and <contact fullname="Y
i Huang"/> contributed to this document or the implementations in Linux, FreeBSD
, Windows, and QUIC.</t>
</section>
</back>
</rfc> </rfc>
 End of changes. 66 change blocks. 
1534 lines changed or deleted 1296 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/