draft-ietf-tcpm-rack-08.txt   draft-ietf-tcpm-rack-09.txt 
TCP Maintenance Working Group Y. Cheng TCP Maintenance Working Group Y. Cheng
Internet-Draft N. Cardwell Internet-Draft N. Cardwell
Intended status: Standards Track N. Dukkipati Intended status: Standards Track N. Dukkipati
Expires: September 10, 2020 P. Jha Expires: January 14, 2021 P. Jha
Google, Inc Google, Inc
March 9, 2020 July 13, 2020
RACK: a time-based fast loss detection algorithm for TCP RACK-TLP: a time-based efficient loss detection for TCP
draft-ietf-tcpm-rack-08 draft-ietf-tcpm-rack-09
Abstract Abstract
This document presents a new TCP loss detection algorithm called RACK This document presents the RACK-TLP loss detection algorithm for TCP.
("Recent ACKnowledgment"). RACK uses the notion of time, instead of RACK-TLP uses per-segment transmit timestamp and selective
packet or sequence counts, to detect losses, for modern TCP acknowledgement (SACK) [RFC2018] and has two parts: RACK ("Recent
implementations that can support per-packet timestamps and the ACKnowledgment") starts fast recovery quickly using time-based
selective acknowledgment (SACK) option. It is intended to be an inferences derived from ACK feedback. TLP ("Tail Loss Probe")
alternative to the DUPACK threshold approach [RFC6675], as well as leverages RACK and sends a probe packet to trigger ACK feedback to
other nonstandard approaches such as FACK [FACK]. avoid the retransmission timeout (RTO) events. Compared to the
widely used DUPACK threshold approach, RACK-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 in
[RFC5681][RFC6675].
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 10, 2020. This Internet-Draft will expire on January 14, 2021.
Copyright Notice Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents
1. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1. Background . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . 4
3. RACK-TLP high-level design . . . . . . . . . . . . . . . . . 5
3.1. RACK: time-based loss inferences from ACKs . . . . . . . 5
3.2. TLP: sending one segment to probe losses quickly with
RACK . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3. RACK-TLP: reordering resilience with a time threshold . . 6
3.3.1. Reordering design rationale . . . . . . . . . . . . . 6
3.3.2. Reordering window adaptation . . . . . . . . . . . . 8
3.4. An Example of RACK-TLP in Action: fast recovery . . . . . 9
3.5. An Example of RACK-TLP in Action: RTO . . . . . . . . . . 9
3.6. Design Summary . . . . . . . . . . . . . . . . . . . . . 10
4. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1. Per-packet variables . . . . . . . . . . . . . . . . . . 11
5.2. Per-connection variables . . . . . . . . . . . . . . . . 12
6. RACK Algorithm Details . . . . . . . . . . . . . . . . . . . 13
6.1. Upon transmitting a data segment . . . . . . . . . . . . 13
6.2. Upon receiving an ACK . . . . . . . . . . . . . . . . . . 13
6.3. Upon RTO expiration . . . . . . . . . . . . . . . . . . . 19
7. TLP Algorithm Details . . . . . . . . . . . . . . . . . . . . 20
7.1. Initializing state . . . . . . . . . . . . . . . . . . . 20
7.2. Scheduling a loss probe . . . . . . . . . . . . . . . . . 20
7.3. Sending a loss probe upon PTO expiration . . . . . . . . 21
7.4. Detecting losses by the ACK of the loss probe . . . . . . 22
7.4.1. General case: detecting packet losses using RACK . . 22
7.4.2. Special case: detecting a single loss repaired by the
loss probe . . . . . . . . . . . . . . . . . . . . . 23
8. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.1. Advantages and disadvantages . . . . . . . . . . . . . . 24
8.2. Relationships with other loss recovery algorithms . . . . 26
8.3. Interaction with congestion control . . . . . . . . . . . 26
8.4. TLP recovery detection with delayed ACKs . . . . . . . . 27
8.5. RACK for other transport protocols . . . . . . . . . . . 28
9. Security Considerations . . . . . . . . . . . . . . . . . . . 28
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 28
12.1. Normative References . . . . . . . . . . . . . . . . . . 28
12.2. Informative References . . . . . . . . . . . . . . . . . 29
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30
1. Terminology 1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP "OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. In this document, these words will appear capitals, as shown here. In this document, these words will appear
with that interpretation only when in UPPER CASE. Lower case uses of with that interpretation only when in UPPER CASE. Lower case uses of
these words are not to be interpreted as carrying [RFC2119] these words are not to be interpreted as carrying [RFC2119]
significance. significance.
2. Introduction 2. Introduction
This document presents a new loss detection algorithm called RACK This document presents RACK-TLP, a TCP loss detection algorithm that
("Recent ACKnowledgment"). RACK uses the notion of time instead of improves upon the widely implemented DUPACK counting approach in
the conventional packet or sequence counting approaches for detecting [RFC5681][RFC6675], and that is RECOMMENDED to be used as an
losses. RACK deems a packet lost if it has not been delivered and alternative to that earlier approach. RACK-TLP has two parts: RACK
some packet sent sufficiently later has been delivered. It does this ("Recent ACKnowledgment") detects losses quickly using time-based
by recording packet transmission times and inferring losses using inferences derived from ACK feedback. TLP ("Tail Loss Probe")
cumulative acknowledgments or selective acknowledgment (SACK) TCP triggers ACK feedback by quickly sending a probe segment, to avoid
options. retransmission timeout (RTO) events.
In recent years we have been observing several increasingly common 2.1. Background
loss and reordering patterns in the Internet:
1. Slow recovery due to lost retransmissions. Traffic policers In traditional TCP loss recovery algorithms [RFC5681][RFC6675], a
[POLICER16] and burst losses often cause retransmissions to be sender starts fast recovery when the number of DUPACKs received
lost again. This severely increases latency because the lost exceeds a threshold (DupThresh) that defaults to 3 (this approach is
retransmissions can only be recovered by retransmission timeouts referred to as DUPACK-counting in the rest of the document). The
(RTOs). sender also halves the congestion window during the recovery. The
rationale behind the partial window reduction is that congestion does
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 recovery [RFC6675] and the number of lost
segments is small.
2. Tail drops. Structured request-response traffic turns more If fast recovery is not triggered, or triggers but fails to repair
losses into tail drops. In such cases, TCP is application- all the losses, then the sender resorts to RTO recovery. The RTO
limited, so it cannot send new data to probe losses and has to timer interval is conservatively the smoothed RTT (SRTT) plus four
rely on retransmission timeouts (RTOs). 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
WINDOW 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 retransmits the rest of the data
following the slow start algorithm [RFC5681]. The time elapsed in
RTO recovery is one RTO interval plus the number of round-trips
needed to repair all the losses.
3. Reordering. Link-layer protocols (e.g., 802.11 block ACK), link 2.2. Motivation
bonding, or routers' internal load-balancing can deliver TCP
packets out of order. The degree of such reordering is usually
within the order of the path round trip time.
Despite TCP stacks (e.g. Linux) that implement many of the standard Fast Recovery is the preferred form of loss recovery because it can
and proposed loss detection algorithms potentially recover all losses in the time scale of a single round
trip, with only a fractional congestion window reduction. RTO
recovery and congestion window reset should ideally be the last
resort, only used when the entire flight is lost. However, in
addition to losing an entire flight of data, the following situations
can unnecessarily resort to RTO recovery with traditional TCP loss
recovery algorithms [RFC5681][RFC6675]:
[RFC4653][RFC5827][RFC5681][RFC6675][RFC7765][FACK][THIN-STREAM], 1. Packet drops for short flows or at the end of an application data
we've found that together they do not perform well. The main reason flight. When the sender is limited by the application (e.g.
is that many of them are based on the classic rule of counting structured request/response traffic), segments lost at the end of
duplicate acknowledgments [RFC5681]. They can either detect loss the application data transfer often can only be recovered by RTO.
quickly or accurately, but not both, especially when the sender is Consider an example of losing only the last segment in a flight
application-limited or under reordering that is unpredictable. And of 100 segments. Lacking any DUPACK, the sender RTO expires and
under these conditions none of them can detect lost retransmissions reduces the congestion window to 1, and raises the congestion
well. 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.
Also, these algorithms, including RFCs, rarely address the 1. Lost retransmissions. Heavy congestion or traffic policers can
interactions with other algorithms. For example, FACK may consider a cause retransmissions to be lost again. Lost retransmissions
packet is lost while RFC6675 may not. Implementing N algorithms cause a resort to RTO recovery, since DUPACK-counting does not
while dealing with N^2 interactions is a daunting task and error- detect the loss of the retransmissions. Then the slow start
prone. after RTO recovery could cause burst losses again that severely
degrades performance [POLICER16].
The goal of RACK is to solve all the problems above by replacing many 2. Packet reordering. Link-layer protocols (e.g., 802.11 block
of the loss detection algorithms above with one more effective ACK), link bonding, or routers' internal load-balancing (e.g.,
algorithm to handle loss and reordering. ECMP) can deliver 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 DupThresh, the DUPACK-
counting can cause a spurious fast recovery and unnecessary
congestion window reduction. To mitigate the issue, [RFC4653]
adjusts DupThresh to half of the inflight size to tolerate higher
degree of reordering. However if more than half of the inflight
is lost, then the sender has to resort to RTO recovery.
3. Overview 3. RACK-TLP high-level design
The main idea behind RACK is that if a packet has been delivered out RACK-TLP allows senders to recover losses more effectively in all
of order, then the packets sent chronologically before that were three scenarios described in the previous section. There are two
either lost or reordered. This concept is not fundamentally design principles behind RACK-TLP. The first principle is to detect
different from [RFC5681][RFC6675][FACK]. But the key innovation in losses via ACK events as much as possible, to repair losses at round-
RACK is to use a per-packet transmission timestamp and widely trip time-scales. The second principle is to gently probe the
deployed SACK options to conduct time-based inferences instead of network to solicit additional ACK feedback, to avoid RTO expiration
inferring losses with packet or sequence counting approaches. and subsequent congestion window reset. At a high level, the two
principles are implemented in RACK and TLP, respectively.
Using a threshold for counting duplicate acknowledgments (i.e., 3.1. RACK: time-based loss inferences from ACKs
DupThresh) alone is no longer reliable because of today's prevalent
reordering patterns. A common type of reordering is that the last
"runt" packet of a window's worth of packet bursts gets delivered
first, then the rest arrive shortly after in order. To handle this
effectively, a sender would need to constantly adjust the DupThresh
to the burst size; but this would risk increasing the frequency of
RTOs on real losses.
Today's prevalent lost retransmissions also cause problems with The rationale behind RACK is that if a segment is delivered out of
packet-counting approaches [RFC5681][RFC6675][FACK], since those order, then the segments sent chronologically before that were either
approaches depend on reasoning in sequence number space. lost or reordered. This concept is not fundamentally different from
Retransmissions break the direct correspondence between ordering in [RFC5681][RFC6675][FACK]. RACK's key innovation is using per-segment
sequence space and ordering in time. So when retransmissions are transmission timestamps and widely-deployed SACK options to conduct
lost, sequence-based approaches are often unable to infer and quickly time-based inferences, instead of inferring losses by counting ACKs
repair losses that can be deduced with time-based approaches. or SACKed sequences. Time-based inferences are more robust than
DUPACK-counting approaches because they have no dependence on flight
size, and thus are effective for application-limited traffic.
Instead of counting packets, RACK uses the most recently delivered Conceptually, RACK puts a virtual timer for every data segment sent
packet's transmission time to judge if some packets sent previous to (including retransmissions). Each timer expires dynamically based on
that time have "expired" by passing a certain reordering settling the latest RTT measurements plus an additional delay budget to
window. On each ACK, RACK marks any already-expired packets lost, accommodate potential packet reordering (called the reordering
and for any packets that have not yet expired it waits until the window). When a segment's timer expires, RACK marks the
reordering window passes and then marks those lost as well. In corresponding segment lost for retransmission.
either case, RACK can repair the loss without waiting for a (long)
RTO. RACK can be applied to both fast recovery and timeout recovery,
and can detect losses on both originally transmitted and
retransmitted packets, making it a great all-weather loss detection
mechanism.
4. Design Rationale for Reordering Tolerance 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 transmission time of every data segment sent,
including retransmissions. For each 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 lost.
The reordering behavior of networks can evolve (over years) in Since the time-based logic of RACK applies equally to retransmissions
response to the behavior of transport protocols and applications, as and original transmissions, it can detect lost retransmissions as
well as the needs of network designers and operators. From a network well. If a segment has been retransmitted but its most recent
or link designer's viewpoint, parallelization (eg. link bonding) is (re)transmission timestamp has expired, then after a reordering
the easiest way to get a network to go faster. Therefore their main window it's marked lost.
constraint on speed is reordering, and there is pressure to relax
that constraint. If RACK becomes widely deployed, the underlying
networks may introduce more reordering for higher throughput. But
this may result in excessive reordering that hurts end to end
performance:
1. End host packet processing: extreme reordering on high-speed 3.2. TLP: sending one segment to probe losses quickly with RACK
networks would incur high CPU cost by greatly reducing the
effectiveness of aggregation mechanisms, such as large receive
offload (LRO) and generic receive offload (GRO), and
significantly increasing the number of ACKs.
2. Congestion control: TCP congestion control implicitly assumes the RACK infers losses from ACK feedback; however, in some cases ACKs are
feedback from ACKs are from the same bottleneck. Therefore it sparse, particularly when the inflight is small or when the losses
cannot handle well scenarios where packets are traversing largely are high. In some challenging cases the last few segments in a
disjoint paths. flight are lost. With [RFC5681] or [RFC6675] the sender's RTO would
expire and reset the congestion window, when in reality most of the
flight has been delivered.
3. Loss recovery: Having an excessively large reordering window to Consider an example where a sender with a large congestion window
accommodate widely different latencies from different paths would transmits 100 new data segments after an application write, and only
increase the latency of loss recovery. 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. 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 instead the losses had occurred three segments sooner
in the flight, then fast recovery would have recovered all losses
within one round-trip and would have avoided resetting the congestion
window.
An end-to-end transport protocol cannot tell immediately whether a Fast Recovery would be preferable in such scenarios; TLP is designed
hole is reordering or loss. It can only distinguish between the two to trigger the feedback RACK needed to enable that. After the last
in hindsight if the hole in the sequence space gets filled later (100th) segment was originally sent, TLP sends the next available
without a retransmission. How long the sender waits for such (new) segment or retransmits the last (highest-sequenced) segment in
potential reordering events to settle is determined by the current two round-trips to probe the network, hence the name "Tail Loss
reordering window. 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, 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 RTO recovery resetting the
congestion window.
Given these considerations, a core design philosophy of RACK is to 3.3. RACK-TLP: reordering resilience with a time threshold
adapt to the measured duration of reordering events, within
reasonable and specific bounds. To accomplish this RACK places the
following mandates on the reordering window:
1. The initial RACK reordering window SHOULD be set to a small 3.3.1. Reordering design rationale
fraction of the round-trip time.
2. If no reordering has been observed, then RACK SHOULD honor the Upon receiving an ACK indicating an out-of-order data delivery, a
classic 3-DUPACK rule for initiating fast recovery. One simple sender cannot tell immediately whether that out-of-order delivery was
way to implement this is to temporarily override the reorder a result of reordering or loss. It can only distinguish between the
window to 0. two in hindsight if the missing sequence ranges are filled in later
without retransmission. Thus a loss detection algorithm needs to
budget some wait time -- a reordering window -- to try to
disambiguate packet reordering from packet loss.
3. The RACK reordering window SHOULD leverage Duplicate Selective The reordering window in the DUPACK-counting approach is implicitly
Acknowledgement (DSACK) information [RFC3708] to adaptively defined as the elapsed time to receive acknowledgements for
estimate the duration of reordering events. DupThresh-worth of out-of-order deliveries. This approach is
effective if the network reordering degree (in sequence distance) is
smaller than DupThresh and at least DupThresh segments after the loss
are acknowledged. For cases where the reordering degree is larger
than the default DupThresh of 3 packets, one alternative is to
dynamically adapt DupThresh based on the FlightSize (e.g. adjusts
DUPTRESH to half of the FlightSize). However, this does not work
well with the following two types of reordering:
4. The RACK reordering window MUST be bounded and this bound SHOULD 1. Application-limited flights where the last non-full-sized segment
be one round trip. is delivered first and then the remaining full-sized segments in
the flight are delivered in order. This reordering pattern can
occur when segments traverse parallel forwarding paths. In such
scenarios the degree of reordering in packet distance is one
segment less than the flight size.
As a flow starts, either condition 1 or condition 2 or both would 2. A flight of segments that are delivered partially out of order.
trigger RACK to start the recovery process quickly. The low initial One cause for this pattern is wireless link-layer retransmissions
reordering window and use of the 3-DUPACK rule are key to achieving with an inadequate reordering buffer at the receiver. In such
low-latency loss recovery for short flows by risking spurious scenarios, the wireless sender sends the data packets in order
retransmissions to recover losses quickly. This rationale is that initially, but some are lost and then recovered by link-layer
retransmissions; the wireless receiver delivers the TCP data
packets in the order they are received, due to the inadequate
reordering buffer. The random wireless transmission errors in
such scenarios cause the reordering degree, expressed in packet
distance, to have highly variable values up to the flight size.
In the above two cases the degree of reordering in packet distance is
highly variable, making DUPACK-counting approach ineffective
including dynamic adaptation variants like [RFC4653]. Instead the
degree of reordering in time difference in such cases is usually
within a single round-trip time. This is because the packets either
traverse slightly disjoint paths with similar propagation delays or
are repaired quickly by the local access technology. Hence, using a
time threshold instead of packet threshold strikes a middle ground,
allowing a bounded degree of reordering resilience while still
allowing fast recovery. This is the rationale behind the RACK-TLP
reordering resilience design.
Specifically, RACK-TLP introduces a new dynamic reordering window
parameter in time units, and the sender considers a data segment S
lost if both conditions are met:
1. Another data segment sent later than S has been delivered
2. S has not been delivered after the estimated round-trip time plus
the reordering window
Note that condition (1) implies at least one round-trip of time has
elapsed since S has been sent.
3.3.2. Reordering window adaptation
The RACK reordering window adapts to the measured duration of
reordering events, within reasonable and specific bounds in order to
disincentivize excessive reordering. More specifically:
1. If the sender has not observed any reordering since the
connection was established, then the RACK reordering window
SHOULD be zero in either of the following cases:
1. After learning that three segments have been delivered out of
order (e.g. receiving 3 DUPACKs per [RFC5681]); in turn, this
will cause the RACK loss detection logic to trigger fast
recovery.
2. During fast recovery or RTO recovery.
1. If the sender has observed some reordering since the connection
was established, then the RACK reordering window SHOULD be set to
a small fraction of the round-trip time, or zero if no round-trip
time estimate is available.
2. The RACK reordering window MUST be bounded and this bound SHOULD
be SRTT.
3. The RACK reordering window SHOULD leverage that to adaptively
estimate the duration of reordering events, if the receiver uses
Duplicate Selective Acknowledgement (DSACK) [RFC2883].
For short flows, the low initial reordering window is key to recover
quickly by risking spurious retransmissions. The rationale is that
spurious retransmissions for short flows are not expected to produce spurious retransmissions for short flows are not expected to produce
excessive network traffic. excessive network traffic additionally. For long flows the design
tolerates reordering within a round trip. This handles reordering
caused by path divergence in small time scales (reordering within the
round-trip time of the shortest path).
For long flows the design tolerates reordering within a round trip. However, the fact that the initial reordering window is low, and the
This handles reordering caused by path divergence in small time reordering window's adaptive growth is bounded, means that there will
scales (reordering within the round-trip time of the shortest path), continue to be a cost to reordering to disincentivize excessive
which should tolerate much of the reordering from link bonding, network reordering over highly disjoint paths. For such networks
multipath routing, or link-layer out-of-order delivery. It also there are good alternative solutions, such as MPTCP.
relaxes ordering constraints to allow sending flights of TCP packets
on different paths dynamically for better load-balancing (e.g.
flowlets).
However, the fact that the initial RACK reordering window is low, and 3.4. An Example of RACK-TLP in Action: fast recovery
the RACK reordering window's adaptive growth is bounded, means that
there will continue to be a cost to reordering and a limit to RACK's
adaptation to reordering. This maintains a disincentive for network
designers and operators to introduce needless or excessive
reordering, particularly because they have to allow for low round
trip time paths. This means RACK will not encourage networks to
perform inconsiderate fine-grained packet-spraying over highly
disjoint paths with very different characteristics. There are good
alternative solutions, such as MPTCP, for such networks.
To conclude, the RACK algorithm aims to adapt to small degrees of The following example in figure 1 illustrates the RACK-TLP algorithm
in action:
Event TCP DATA SENDER TCP DATA RECEIVER
_____ ____________________________________________________________
1. Send P0, P1, P2, P3 -->
[P1, P2, P3 dropped by network]
2. <-- Receive P0, ACK P0
3a. 2RTTs after (2), TLP timer fires
3b. TLP: retransmits P3 -->
4. <-- Receive P3, SACK P3
5a. Receive SACK for P3
5b. RACK: marks P1, P2 lost
5c. Retransmit P1, P2 -->
[P1 retransmission dropped by network]
6. <-- Receive P2, SACK P2 & P3
7a. RACK: marks P1 retransmission lost
7b. Retransmit P1 -->
8. <-- Receive P1, ACK P3
Figure 1.
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 probe, 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 P1 and P2 were
likely lost, because they were sent before P3. The sender then
retransmits P1 and P2. Unfortunately, the retransmission of P1 is
lost again. However, the delivery of the retransmission of P2 allows
RACK to infer that the retransmission of P1 was likely lost (event
7a), and hence P1 should be retransmitted (event 7b).
3.5. An Example of RACK-TLP in Action: RTO
In addition to enhancing fast recovery, RACK improves the accuracy of
RTO recovery by reducing spurious retransmissions.
Without RACK, upon RTO timer expiration the sender marks all the
unacknowledged segments lost. This approach can lead to spurious
retransmissions. For example, consider a simple case where one
segment was sent with an RTO of 1 second, and then the application
writes more data, causing a second and third segment to be sent right
before the RTO of the first segment expires. Suppose only the first
segment is lost. Without RACK, upon RTO expiration the sender marks
all three segments as lost and retransmits the first segment. When
the sender receives the ACK that selectively acknowledges the second
segment, the sender spuriously retransmits the third segment.
With RACK, upon RTO timer expiration the only segment automatically
marked lost is the first segment (since it was sent an RTO ago); for
all the other segments 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 segment as
lost, and retransmits that segment. The other two very recently sent
segments are not marked lost, because they were sent less than one
round trip ago and there were no ACKs providing evidence that they
were lost. When the sender receives the ACK that selectively
acknowledges the second segment, the sender would not retransmit the
third segment but rather would send any new segments (if allowed by
congestion window and receive window).
In the above example, if the sender were to send a large burst of
segments instead of two segments right before RTO, without RACK the
sender may spuriously retransmit almost the entire flight [RACK-
TCPM97]. Note that the Eifel protocol [RFC3522] cannot prevent this
issue because it can only detect spurious RTO episodes. In this
example the RTO itself was not spurious.
3.6. Design Summary
To summarize, RACK-TLP aims to adapt to small time-varying degrees of
reordering, quickly recover most losses within one to two round reordering, quickly recover most losses within one to two round
trips, and avoid costly retransmission timeouts (RTOs). In the trips, and avoid costly RTO recoveries. In the presence of
presence of reordering, the adaptation algorithm can impose reordering, the adaptation algorithm can impose sometimes-needless
sometimes-needless delays when it waits to disambiguate loss from delays when it waits to disambiguate loss from reordering, but the
reordering, but the penalty for waiting is bounded to one round trip penalty for waiting is bounded to one round trip and such delays are
and such delays are confined to longer-running flows. confined to flows long enough to have observed reordering.
5. Requirements 4. Requirements
The reader is expected to be familiar with the definitions given in The reader is expected to be familiar with the definitions given in
the TCP congestion control [RFC5681] and selective acknowledgment the TCP congestion control [RFC5681] and selective acknowledgment
[RFC2018] RFCs. Familiarity with the conservative SACK-based [RFC2018][RFC6675] RFCs. RACK-TLP has the following requirements:
recovery for TCP [RFC6675] is not expected but helps.
RACK has three requirements:
1. The connection MUST use selective acknowledgment (SACK) options 1. The connection MUST use selective acknowledgment (SACK) options
[RFC2018]. [RFC2018], and the sender keeps a SACK scoreboard information on
a per-connection basis ([RFC6675] section 3).
2. For each packet sent, the sender MUST store its most recent 2. For each data segment sent, the sender MUST store its most recent
transmission time with (at least) millisecond granularity. For transmission time with a timestamp whose granularity that is
round-trip times lower than a millisecond (e.g., intra-datacenter finer than 1/4 of the minimum RTT of the connection. At the time
communications) microsecond granularity would significantly help of writing, microsecond resolution is suitable for intra-
the detection latency but is not required. datacenter traffic and millisecond granularity or finer is
suitable for the Internet. Note that RACK-TLP can be implemented
with TSO (TCP Segmentation Offload) support by having multiple
segments in a TSO aggregate share the same timestamp.
3. For each packet sent, the sender MUST remember whether the packet 3. RACK DSACK-based reordering window adaptation is RECOMMENDED but
has been retransmitted or not. is not required.
We assume that requirement 1 implies the sender keeps a SACK 4. TLP requires RACK.
scoreboard, which is a data structure to store selective
acknowledgment information on a per-connection basis ([RFC6675]
section 3). For the ease of explaining the algorithm, we use a
pseudo-scoreboard that manages the data in sequence number ranges.
But the specifics of the data structure are left to the implementor.
RACK does not need any change on the receiver. 5. Definitions
6. Definitions The reader is expected to be familiar with the variables of SND.UNA,
SND.NXT, SEG.ACK, and SEG.SEQ in [RFC793], SMSS, FlightSize in
[RFC5681], DupThresh in [RFC6675], RTO and SRTT in [RFC6298]. A
RACK-TLP implementation needs to store new per-packet and per-
connection state, described below.
The reader is expected to be familiar with the definitions given in 5.1. Per-packet variables
[RFC793], including SND.UNA, SND.NXT, SEG.ACK, and SEG.SEQ.
6.1. Definitions of variables Theses variables indicate the status of the most recent transmission
of a data segment:
A sender implementing RACK needs to store these new RACK variables: "Segment.lost" is true if the most recent (re)transmission of the
segment has been marked lost and needs to be retransmitted. False
otherwise.
"Packet.xmit_ts" is the time of the last transmission of a data "Segment.retransmitted" is true if it was retransmitted in the most
packet, including retransmissions, if any. The sender needs to recent transmission. False otherwise.
record the transmission time for each packet sent and not yet
acknowledged. The time MUST be stored at millisecond granularity or
finer.
"RACK.packet". Among all the packets that have been either "Segment.xmit_ts" is the time of the last transmission of a data
selectively or cumulatively acknowledged, RACK.packet is the one that segment, including retransmissions, if any, with a clock granularity
was sent most recently including retransmissions. specified in the Requirements section.
"RACK.xmit_ts" is the latest transmission timestamp of RACK.packet. "Segment.end_seq" is the next sequence number after the last sequence
number of the data segment.
"RACK.end_seq" is the ending TCP sequence number of RACK.packet. 5.2. Per-connection variables
"RACK.rtt" is the RTT of the most recently delivered packet on the "RACK.segment". Among all the segments that have been either
connection (either cumulatively acknowledged or selectively selectively or cumulatively acknowledged, RACK.segment is the one
acknowledged) that was not marked invalid as a possible spurious that was sent most recently (including retransmissions).
retransmission.
"RACK.rtt_seq" is the SND.NXT when RACK.rtt is updated. "RACK.xmit_ts" is the latest transmission timestamp of RACK.segment.
"RACK.reo_wnd" is a reordering window computed in the unit of time "RACK.end_seq" is the Segment.end_seq of RACK.segment.
used for recording packet transmission times. It is used to defer
the moment at which RACK marks a packet lost.
"RACK.dupthresh" is a constant specifying the number of duplicate "RACK.ack_ts" is the time when the full sequence range of
acknowledgments, or selectively acknowledged segments, that can RACK.segment was selectively or cumulatively acknowledged.
(under certain conditions) trigger fast recovery, similar to
[RFC6675]. As in [RFC5681] and [RFC6675], this threshold is defined "RACK.segs_sacked" returns the total number of segments selectively
to be 3. acknowledged in the SACK scoreboard.
"RACK.fack" is the highest selectively or cumulatively acknowledged
sequence (i.e. forward acknowledgement).
"RACK.min_RTT" is the estimated minimum round-trip time (RTT) of the "RACK.min_RTT" is the estimated minimum round-trip time (RTT) of the
connection. connection.
"RACK.ack_ts" is the time when all the sequences in RACK.packet were "RACK.rtt" is the RTT of the most recently delivered segment on the
selectively or cumulatively acknowledged. connection (either cumulatively acknowledged or selectively
acknowledged) that was not marked invalid as a possible spurious
retransmission.
"RACK.reo_wnd_incr" is the multiplier applied to adjust RACK.reo_wnd "RACK.reordering_seen" indicates whether the sender has detected data
segment reordering event(s).
"RACK.reo_wnd" is a reordering window computed in the unit of time
used for recording segment transmission times. It is used to defer
the moment at which RACK marks a segment lost.
"RACK.dsack" indicates if a DSACK option has been received since the
last RACK.reo_wnd change.
"RACK.reo_wnd_mult" is the multiplier applied to adjust RACK.reo_wnd.
"RACK.reo_wnd_persist" is the number of loss recoveries before "RACK.reo_wnd_persist" is the number of loss recoveries before
resetting RACK.reo_wnd resetting RACK.reo_wnd
"RACK.dsack" indicates if a DSACK option has been received since last "RACK.rtt_seq" is the SND.NXT when RACK.rtt is updated.
RACK.reo_wnd change
"RACK.pkts_sacked" returns the total number of packets selectively "TLP.is_retrans": a boolean indicating whether there is an
acknowledged in the SACK scoreboard. unacknowledged TLP retransmission.
"RACK.reord" indicates the connection has detected packet reordering "TLP.end_seq": the value of SND.NXT at the time of sending a TLP
event(s) retransmission.
"RACK.fack" is the highest selectively or cumulatively acknowledged
sequence
Note that the Packet.xmit_ts variable is per packet in flight. The "TLP.max_ack_delay": sender's maximum delayed ACK timer budget.
RACK.xmit_ts, RACK.end_seq, RACK.rtt, RACK.reo_wnd, and RACK.min_RTT
variables are kept in the per-connection TCP control block.
RACK.packet and RACK.ack_ts are used as local variables in the
algorithm.
7. Algorithm Details Per-connection timers
7.1. Transmitting a data packet "RACK reordering timer": a timer that allows RACK to wait for
reordering to resolve, to try to disambiguate reordering from loss,
when some out-of-order segments are marked as SACKed.
Upon transmitting a new packet or retransmitting an old packet, "TLP PTO": a timer event indicating that an ACK is overdue and the
record the time in Packet.xmit_ts. RACK does not care if the sender should transmit a TLP segment, to solicit SACK or ACK
retransmission is triggered by an ACK, new application data, an RTO, feedback.
or any other means.
7.2. Upon receiving an ACK These timers augment the existing timers maintained by a sender,
including the 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 segments in flight. The
implementation can simplify 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 expiration.
6. RACK Algorithm Details
6.1. Upon transmitting a data segment
Upon transmitting a new segment or retransmitting an old segment,
record the time in Segment.xmit_ts and set Segment.lost to FALSE.
Upon retransmitting a segment, set Segment.retransmitted to TRUE.
RACK_transmit_data(Segment):
Segment.xmit_ts = Now()
Segment.lost = FALSE
RACK_retransmit_data(Segment):
Segment.retransmitted = TRUE
RACK_transmit_data(Segment)
6.2. Upon receiving an ACK
Step 1: Update RACK.min_RTT. Step 1: Update RACK.min_RTT.
Use the RTT measurements obtained via [RFC6298] or [RFC7323] to Use the RTT measurements obtained via [RFC6298] or [RFC7323] to
update the estimated minimum RTT in RACK.min_RTT. The sender can update the estimated minimum RTT in RACK.min_RTT. The sender SHOULD
track a simple global minimum of all RTT measurements from the track a simple global minimum of all RTT measurements from the
connection, or a windowed min-filtered value of recent RTT connection, or a windowed min-filtered estimate of recent RTT
measurements. This document does not specify an exact approach. measurements.
Step 2: Update RACK stats
Given the information provided in an ACK, each packet cumulatively Step 2: Update state for most recently sent segment that has been
ACKed or SACKed is marked as delivered in the scoreboard. Among all delivered
the packets newly ACKed or SACKed in the connection, record the most
recent Packet.xmit_ts in RACK.xmit_ts if it is ahead of RACK.xmit_ts.
Sometimes the timestamps of RACK.Packet and Packet could carry the
same transmit timestamps due to clock granularity or segmentation
offloading (i.e. the two packets were handed to the NIC as a single
unit). In that case the sequence numbers of RACK.end_seq and
Packet.end_seq are compared to break the tie.
Since an ACK can also acknowledge retransmitted data packets, and In this step, RACK updates its states that tracks the most recently
retransmissions can be spurious, the sender must take care to avoid sent segment that has been delivered: RACK.segment; RACK maintains
spurious inferences. For example, if the sender were to use timing its latest transmission timestamp in RACK.xmit_ts and its highest
information from a spurious retransmission, the RACK.rtt could be sequence number in RACK.end_seq. These two variables are used, in
vastly underestimated. later steps, to estimate if some segments not yet delivered 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 be spurious, the sender needs to
take care to avoid spurious inferences. For example, if the sender
were to use timing information from a spurious retransmission, the
RACK.rtt could be vastly underestimated.
To avoid spurious inferences, ignore a packet as invalid if any of To avoid spurious inferences, ignore a segment as invalid if any of
its TCP sequences have been retransmitted before and either of two its sequence range has been retransmitted before and either of two
conditions is true: conditions is true:
1. The Timestamp Echo Reply field (TSecr) of the ACK's timestamp 1. The Timestamp Echo Reply field (TSecr) of the ACK's timestamp
option [RFC7323], if available, indicates the ACK was not option [RFC7323], if available, indicates the ACK was not
acknowledging the last retransmission of the packet. acknowledging the last retransmission of the segment.
2. The packet was last retransmitted less than RACK.min_rtt ago. 2. The segment was last retransmitted less than RACK.min_rtt ago.
If the ACK is not ignored as invalid, update the RACK.rtt to be the The second check is a heuristic when the TCP Timestamp option is not
RTT sample calculated using this ACK, and continue. If this ACK or available, or when the round trip time is less than the TCP Timestamp
SACK was for the most recently sent packet, then record the clock granularity.
RACK.xmit_ts timestamp and RACK.end_seq sequence implied by this ACK.
Otherwise exit here and omit the following steps.
Notice that the second condition above is a heuristic. This Among all the segments newly ACKed or SACKed by this ACK that pass
heuristic would fail to update RACK stats if a data packet is the checks above, update the RACK.rtt to be the RTT sample calculated
spuriously retransmitted because of a recent minimum RTT decrease using this ACK. Furthermore, record the most recent Segment.xmit_ts
(e.g. path change). For example, in cases with a TCP connection in RACK.xmit_ts if it is ahead of RACK.xmit_ts. If Segment.xmit_ts
without TCP timestamps, and where the first M packets in a flight of equals RACK.xmit_ts (e.g. due to clock granularity limits) then
data packets travel an old (longer) original path, and the remaining compare Segment.end_seq and RACK.end_seq to break the tie.
N packets in that flight travel a new (shorter) path and arrive out
of order and elicit SACKs, then those SACKs for the N packets can
initiate a spurious retransmission of the first M packets. In such
scenarios, the sender would not be able to update its RACK.min_rtt
using the (ambiguous) RTT samples from retransmissions, so during
recovery all RTT samples may be less than RACK.min_rtt, and thus meet
the second condition. In such cases RACK may not detect losses from
ACK events and the recovery would then resort to the (slower) TLP or
RTO timer-based recovery. However, such events should be rare and
the connection would pick up the new minimum RTT when the recovery
ends, so the sender can avoid repeated similar failures.
Step 2 may be summarized in pseudocode as: Step 2 may be summarized in pseudocode as:
RACK_sent_after(t1, seq1, t2, seq2): RACK_sent_after(t1, seq1, t2, seq2):
If t1 > t2: If t1 > t2:
Return true Return true
Else if t1 == t2 AND seq1 > seq2: Else if t1 == t2 AND seq1 > seq2:
Return true Return true
Else: Else:
Return false Return false
RACK_update(): RACK_update():
For each Packet newly acknowledged cumulatively or selectively: For each Segment newly acknowledged cumulatively or selectively:
rtt = Now() - Packet.xmit_ts rtt = Now() - Segment.xmit_ts
If Packet.retransmitted is TRUE: If Segment.retransmitted is TRUE:
If ACK.ts_option.echo_reply < Packet.xmit_ts: If ACK.ts_option.echo_reply < Segment.xmit_ts:
Return Return
If rtt < RACK.min_rtt: If rtt < RACK.min_rtt:
Return Return
RACK.rtt = rtt RACK.rtt = rtt
If RACK_sent_after(Packet.xmit_ts, Packet.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 = Packet.xmit_ts RACK.xmit_ts = Segment.xmit_ts
Step 3: Detect packet reordering Step 3: Detect data segment reordering
To detect reordering, the sender looks for original data packets To detect reordering, the sender looks for original data segments
being delivered out of order in sequence space. The sender tracks being delivered out of order. To detect such cases, the sender
the highest sequence selectively or cumulatively acknowledged in the tracks the highest sequence selectively or cumulatively acknowledged
RACK.fack variable. The name fack stands for the most forward ACK in the RACK.fack variable. The name "fack" stands for the most
originated from the [FACK] draft. If the ACK selectively or "Forward ACK" (this term is adopted from [FACK]). If a never-
cumulatively acknowledges an unacknowledged and also never retransmitted segment that's below RACK.fack is (selectively or
retransmitted sequence below RACK.fack, then the corresponding packet cumulatively) acknowledged, it has been delivered out of order. The
has been reordered and RACK.reord is set to TRUE. sender sets RACK.reordering_seen to TRUE if such segment is
identified.
The heuristic above only detects reordering if the re-ordered packet RACK_detect_reordering():
has not yet been retransmitted. This is a major drawback because if For each Segment newly acknowledged cumulatively or selectively:
RACK has a low reordering window and the network is reordering If Segment.end_seq > RACK.fack:
packets, RACK may falsely retransmit frequently. Consequently RACK RACK.fack = Segment.end_seq
may fail to detect reordering to increase the reordering window, Else if Segment.end_seq < RACK.fack AND
because the reordered packets were already (falsely) retransmitted. Segment.retransmitted is FALSE:
RACK.reordering_seen = TRUE
DSACK [RFC3708] can help mitigate this issue. The false Step 4: Update RACK reordering window
retransmission would solicit DSACK option in the ACK. Therefore if
the ACK has a DSACK option covering some sequence that were both
acknowledged and retransmitted, this implies the original packet was
reordered but RACK retransmitted the packet too quickly and should
set RACK.reord to TRUE.
RACK_detect_reordering(): The RACK reordering window, RACK.reo_wnd, serves as an adaptive
For each Packet newly acknowledged cumulatively or selectively: allowance for settling time before marking a segment lost. This step
If Packet.end_seq > RACK.fack: documents a detailed algorithm that follows the principles outlined
RACK.fack = Packet.end_seq in the ``RACK reordering window adaptation'' section.
Else if Packet.end_seq < RACK.fack AND
Packet.retransmitted is FALSE:
RACK.reord = TRUE
For each Packet covered by the DSACK option: If the sender has not yet observed any reordering based on the
If Packet.retransmitted is TRUE: previous step, then RACK prioritizes quick loss recovery by using
RACK.reord = TRUE setting RACK.reo_wnd to 0 when the number of SACKed segments exceeds
DupThresh, or during loss recovery.
Step 4: Update RACK reordering window Aside from those special conditions, RACK starts with a conservative
reordering window of RACK.min_RTT/4. This value was chosen because
Linux TCP used the same factor in its implementation to delay Early
Retransmit [RFC5827] to reduce spurious loss detections in the
presence of reordering, and experience showed this worked reasonably
well [DMCG11].
To handle the prevalent small degree of reordering, RACK.reo_wnd However, the reordering detection in the previous step, Step 3, has a
serves as an allowance for settling time before marking a packet self-reinforcing drawback when the reordering window is too small to
lost. This section documents a detailed algorithm following the cope with the actual reordering. When that happens, RACK could
design rationale section. RACK starts initially with a conservative spuriously mark reordered segments lost, causing them to be
window of min_RTT/4. If no reordering has been observed, RACK uses retransmitted. In turn, the retransmissions can prevent the
RACK.reo_wnd of 0 during loss recovery, in order to retransmit necessary conditions for Step 3 to detect reordering, since this
quickly, or when the number of DUPACKs exceeds the classic DUPACK mechanism requires ACKs or SACKs for only segments that have never
threshold. The subtle difference between this approach and the been retransmitted. In some cases such scenarios can persist,
conventional one [RFC5681][RFC6675] is discussed later in the section causing RACK to continue to spuriously mark segments lost without
"RACK and TLP Discussion". realizing the reordering window is too small.
Further, RACK MAY use DSACK [RFC3708] to adapt the reordering window, To avoid the issue above, RACK dynamically adapts to higher degrees
to higher degrees of reordering, if DSACK is supported. Receiving an of reordering using DSACK options from the receiver. Receiving an
ACK with a DSACK indicates a spurious retransmission, which in turn ACK with a DSACK option indicates a spurious retransmission,
suggests that the RACK reordering window, RACK.reo_wnd, is likely too suggesting that RACK.reo_wnd may be too small. The RACK.reo_wnd
small. The sender MAY increase the RACK.reo_wnd window linearly for increases linearly for every round trip in which the sender receives
every round trip in which the sender receives a DSACK, so that after some DSACK option, so that after N distinct round trips in which a
N distinct round trips in which a DSACK is received, the RACK.reo_wnd DSACK is received, the RACK.reo_wnd becomes (N+1) * min_RTT / 4, with
becomes (N+1) * min_RTT / 4, with an upper-bound of SRTT. The an upper-bound of SRTT.
inflated RACK.reo_wnd would persist for 16 loss recoveries and after
which it resets to its starting value, min_RTT / 4.
The following pseudocode implements the above algorithm. Note that If the reordering is temporary then a large adapted reordering window
extensions that require additional TCP features (e.g. DSACK) would would unnecessarily delay loss recovery later. Therefore, RACK
work if the feature functions simply return false. persists the inflated RACK.reo_wnd for only 16 loss recoveries, after
which it resets RACK.reo_wnd to its starting value, min_RTT / 4. The
downside of resetting the reordering window is the risk of triggering
spurious fast recovery episodes if the reordering remains high. The
rationale for this approach is to bound such spurious recoveries to
approximately once every 16 recoveries (less than 7%).
RACK_update_reo_wnd(): To track the linear scaling factor for the adaptive reordering
RACK.min_RTT = TCP_min_RTT() window, RACK uses the variable RACK.reo_wnd_mult, which is
If DSACK option is present: initialized to 1 and adapts with the following pseudocode, which
RACK.dsack = true implements the above algorithm:
If SND.UNA < RACK.rtt_seq: RACK_update_reo_wnd():
RACK.dsack = false /* React to DSACK once per round trip */
If RACK.dsack: /* DSACK-based reordering window adaptation */
RACK.reo_wnd_incr += 1 If RACK.dsack_round is not None AND
RACK.dsack = false SND.UNA >= RACK.dsack_round:
RACK.rtt_seq = SND.NXT RACK.dsack_round = None
RACK.reo_wnd_persist = 16 /* Keep window for 16 recoveries */ /* Grow the reordering window per round that sees DSACK.
Else if exiting loss recovery: Reset the window after 16 DSACK-free recoveries */
If RACK.dsack_round is None AND
any DSACK option is present on latest received ACK:
RACK.dsack_round = SND.NXT
RACK.reo_wnd_mult += 1
RACK.reo_wnd_persist = 16
Else if exiting Fast or RTO recovery:
RACK.reo_wnd_persist -= 1 RACK.reo_wnd_persist -= 1
If RACK.reo_wnd_persist <= 0: If RACK.reo_wnd_persist <= 0:
RACK.reo_wnd_incr = 1 RACK.reo_wnd_mult = 1
If RACK.reord is FALSE: If RACK.reordering_seen is FALSE:
If in loss recovery: /* If in fast or timeout recovery */ If in Fast or RTO recovery:
RACK.reo_wnd = 0 Return 0
Return Else if RACK.segs_sacked >= DupThresh:
Else if RACK.pkts_sacked >= RACK.dupthresh: Return 0
RACK.reo_wnd = 0 Return min(RACK.min_RTT / 4 * RACK.reo_wnd_mult, SRTT)
return
RACK.reo_wnd = RACK.min_RTT / 4 * RACK.reo_wnd_incr
RACK.reo_wnd = min(RACK.reo_wnd, SRTT)
Step 5: Detect losses. Step 5: Detect losses.
For each packet that has not been SACKed, if RACK.xmit_ts is after For each segment that has not been SACKed, RACK considers that
Packet.xmit_ts + RACK.reo_wnd, then mark the packet (or its segment lost if another segment that was sent later has been
corresponding sequence range) lost in the scoreboard. The rationale delivered, and the reordering window has passed. RACK considers the
is that if another packet that was sent later has been delivered, and reordering window to have passed if the RACK.segment was sent
the reordering window or "reordering settling time" has already sufficiently after the segment in question, or a sufficient time has
passed, then the packet was likely lost. elapsed since the RACK.segment was S/ACKed, or some combination of
the two. More precisely, RACK marks a segment lost if:
If another packet that was sent later has been delivered, but the
reordering window has not passed, then it is not yet safe to deem the
unacked packet lost. Using the basic algorithm above, the sender
would wait for the next ACK to further advance RACK.xmit_ts; but this
risks a timeout (RTO) if no more ACKs come back (e.g, due to losses
or application limit). For timely loss detection, the sender MAY
install a "reordering settling" timer set to fire at the earliest
moment at which it is safe to conclude that some packet is lost. The
earliest moment is the time it takes to expire the reordering window
of the earliest unacked packet in flight.
This timer expiration value can be derived as follows. As a starting
point, we consider that the reordering window has passed if the
RACK.packet was sent sufficiently after the packet in question, or a
sufficient time has elapsed since the RACK.packet was S/ACKed, or
some combination of the two. More precisely, RACK marks a packet as
lost if the reordering window for a packet has elapsed through the
sum of:
1. delta in transmit time between a packet and the RACK.packet
2. delta in time between RACK.ack_ts and now
So we mark a packet as lost if:
RACK.xmit_ts >= Packet.xmit_ts RACK.xmit_ts >= Segment.xmit_ts
AND AND
(RACK.xmit_ts - Packet.xmit_ts) + (now - RACK.ack_ts) >= RACK.reo_wnd (RACK.xmit_ts - Segment.xmit_ts) + (now - RACK.ack_ts) >= RACK.reo_wnd
If we solve this second condition for "now", the moment at which we
can declare a packet lost, then we get:
now >= Packet.xmit_ts + RACK.reo_wnd + (RACK.ack_ts - RACK.xmit_ts) Solving this second condition for "now", the moment at which a
segment is marked lost, yields:
Then (RACK.ack_ts - RACK.xmit_ts) is the RTT of the packet the sender now >= Segment.xmit_ts + RACK.reo_wnd + (RACK.ack_ts - RACK.xmit_ts)
used to set RACK.xmit_ts: the round trip time of the most recently
(re)transmitted packet that's been delivered. To be more robust to
reordering, RACK uses a more conservative RTT value to decide if an
unacknowledged packet should be considered lost, RACK.rtt: the round
trip time of the most recently delivered packet on the connection
that was not marked invalid as a possible spurious retransmission.
When packets are delivered in order, the most recently Then (RACK.ack_ts - RACK.xmit_ts) is the round trip time of the most
(re)transmitted packet that's been delivered is also the most recently (re)transmitted segment that's been delivered. When
recently delivered, hence RACK.rtt == RACK.ack_ts - RACK.xmit_ts. segments are delivered in order, the most recently (re)transmitted
But if packets were reordered, then the packet delivered most segment that's been delivered is also the most recently delivered,
recently was sent before the most recently (re)transmitted packet. hence RACK.rtt == RACK.ack_ts - RACK.xmit_ts. But if segments were
Hence RACK.rtt > (RACK.ack_ts - RACK.xmit_ts). reordered, then the segment delivered most recently was sent before
the most recently (re)transmitted segment. Hence RACK.rtt >
(RACK.ack_ts - RACK.xmit_ts).
Since RACK.RTT >= (RACK.ack_ts - RACK.xmit_ts), the previous equation Since RACK.RTT >= (RACK.ack_ts - RACK.xmit_ts), the previous equation
reduces to saying that the sender can declare a packet lost when: reduces to saying that the sender can declare a segment lost when:
now >= Packet.xmit_ts + RACK.reo_wnd + RACK.rtt now >= Segment.xmit_ts + RACK.reo_wnd + RACK.rtt
In turn, that is equivalent to stating that a RACK sender should In turn, that is equivalent to stating that a RACK sender should
declare a packet lost when: declare a segment lost when:
Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - now <= 0
Note that if the value on the left hand side is positive, it
represents the remaining wait time before the segment is deemed lost.
But this risks a timeout (RTO) if no more ACKs come back (e.g, due to
losses or application-limited transmissions) to trigger the marking.
For timely loss detection, the sender is RECOMMENDED to install a
reordering timer. This timer expires at the earliest moment when
RACK would conclude that all the unacknowledged segments within the
reordering window were lost.
Packet.xmit_ts + RACK.rtt + RACK.reo_wnd - now <= 0
The following pseudocode implements the algorithm above. When an ACK The following pseudocode implements the algorithm above. When an ACK
is received or the RACK timer expires, call RACK_detect_loss(). The is received or the RACK reordering timer expires, call
algorithm includes an additional optimization to break timestamp ties RACK_detect_loss_and_arm_timer(). The algorithm breaks timestamp
by using the TCP sequence space. The optimization is particularly ties by using the TCP sequence space, since high-speed networks often
useful to detect losses in a timely manner with TCP Segmentation have multiple segments with identical timestamps.
Offload, where multiple packets in one TCP Segmentation Offload (TSO)
blob have identical timestamps.
RACK_detect_loss(): RACK_detect_loss():
timeout = 0 timeout = 0
RACK.reo_wnd = RACK_update_reo_wnd()
For each packet, Packet, not acknowledged yet: For each segment, Segment, not acknowledged yet:
If Packet.lost is TRUE AND Packet.retransmitted is FALSE: If Segment.lost is TRUE AND Segment.retransmitted is FALSE:
Continue /* Packet lost but not yet retransmitted */ Continue /* Segment lost but not yet retransmitted */
If RACK_sent_after(RACK.xmit_ts, RACK.end_seq, If RACK_sent_after(RACK.xmit_ts, RACK.end_seq,
Packet.xmit_ts, Packet.end_seq): Segment.xmit_ts, Segment.end_seq):
remaining = Packet.xmit_ts + RACK.rtt + remaining = Segment.xmit_ts + RACK.rtt +
RACK.reo_wnd - Now() RACK.reo_wnd - Now()
If remaining <= 0: If remaining <= 0:
Packet.lost = TRUE Segment.lost = TRUE
Else: Else:
timeout = max(remaining, timeout) timeout = max(remaining, timeout)
Return timeout
RACK_detect_loss_and_arm_timer():
timeout = RACK_detect_loss()
If timeout != 0 If timeout != 0
Arm a timer to call RACK_detect_loss() after timeout Arm the RACK timer to call
RACK_detect_loss_and_arm_timer() after timeout
Implementation optimization: looping through packets in the SACK
scoreboard above could be very costly on large-BDP networks since the
inflight could be very large. If the implementation can organize the
scoreboard data structures to have packets sorted by the last
(re)transmission time, then the loop can start on the least recently
sent packet and abort on the first packet sent after RACK.time_ts.
This can be implemented by using a seperate doubly-linked list sorted
in time order. The implementation inserts the packet at the tail of
the list when it is (re)transmitted, and removes a packet from the
list when it is delivered or marked lost. We RECOMMEND such an
optimization because it enables implementations to support high-BDP
networks. This optimization is implemented in Linux and sees orders
of magnitude improvement in CPU usage on high-speed WAN networks.
7.3. Tail Loss Probe: fast recovery for tail losses
This section describes a supplemental algorithm, Tail Loss Probe
(TLP), which leverages RACK to further reduce RTO recoveries. TLP
triggers fast recovery to quickly repair tail losses that can
otherwise be recovered only via RTOs. After an original data
transmission, TLP sends a probe data segment within one to two RTTs.
The probe data segment can either be new, previously unsent data, or
a retransmission of previously sent data just below SND.NXT. In
either case the goal is to elicit more feedback from the receiver, in
the form of an ACK (potentially with SACK blocks), to allow RACK to
trigger fast recovery instead of an RTO.
An RTO occurs when the first unacknowledged sequence number is not
acknowledged after a conservative period of time has elapsed
[RFC6298]. Common causes of RTOs include:
1. The entire flight of data is lost.
2. Tail losses of data segments at the end of an application
transaction.
3. Tail losses of ACKs at the end of an application transaction.
4. Lost retransmits, which can halt fast recovery based on [RFC6675]
if the ACK stream completely dries up. For example, consider a
window of three data packets (P1, P2, P3) that are sent; P1 and
P2 are dropped. On receipt of a SACK for P3, RACK marks P1 and
P2 as lost and retransmits them as R1 and R2. Suppose R1 and R2
are lost as well, so there are no more returning ACKs to detect
R1 and R2 as lost. Recovery stalls.
5. An unexpectedly long round-trip time (RTT). This can cause ACKs
to arrive after the RTO timer expires. The F-RTO algorithm
[RFC5682] is designed to detect such spurious retransmission
timeouts and at least partially undo the consequences of such
events, but F-RTO cannot be used in many situations.
7.4. Tail Loss Probe: An Example
Following is an example of TLP. All events listed are at a TCP
sender.
1. Sender transmits segments 1-10: 1, 2, 3, ..., 8, 9, 10. There is
no more new data to transmit. A TLP is scheduled to be sent 2
RTTs after the transmission of the 10th segment.
2. Sender receives acknowledgements (ACKs) for segments 1-5;
segments 6-10 are lost and no ACKs are received. The sender
reschedules its TLP at a time relative to the last received ACK,
which is the ACK for segment 5 in this case. The sender sets the
time for the TLP using the calculation described in step (2) of
the algorithm.
3. When the TLP timer fires, sender retransmits segment 10.
4. After an RTT, a SACK for packet 10 arrives. The ACK also carries
SACK holes for segments 6, 7, 8 and 9. This triggers RACK-based
loss recovery.
5. The connection enters fast recovery and retransmits the remaining
lost segments.
7.5. Tail Loss Probe Algorithm Details
We define the terminology used in specifying the TLP algorithm:
FlightSize: amount of outstanding data in the network, as defined in
[RFC5681].
RTO: The transport's retransmission timeout (RTO) is based on
measured round-trip times (RTT) between the sender and receiver, as
specified in [RFC6298] for TCP. PTO: Probe timeout (PTO) is a timer
event indicating that an ACK is overdue and the sender should try to
transmit a TLP. Its value is constrained to be smaller than or equal
to an RTO.
SRTT: smoothed round-trip time, computed as specified in [RFC6298]. As an optimization, an implementation can choose to check only
TLPRxtOut: a boolean indicating whether there is an unacknowledged segments that have been sent before RACK.xmit_ts. This can be more
TLP retransmission. efficient than scanning the entire SACK scoreboard, especially when
there are many segments in flight. The implementation can use a
separate doubly-linked list ordered by Segment.xmit_ts and inserts a
segment at the tail of the list when it is (re)transmitted, and
removes a segment from the list when it is delivered or marked lost.
In Linux TCP this optimization improved CPU usage by orders of
magnitude during some fast recovery episodes on high-speed WAN
networks.
TLPHighRxt: the value of SND.NXT at the time of sending a TLP 6.3. Upon RTO expiration
retransmission.
WCDelAckT: maximum delayed ACK timer value. Upon RTO timer expiration, RACK marks the first outstanding segment
as lost (since it was sent an RTO ago); for all the other segments
RACK only marks the segment lost if the time elapsed since the
segment was transmitted is at least the sum of the recent RTT and the
reordering window.
The TLP algorithm has three phases, which we discuss in turn. RACK_mark_losses_on_RTO():
For each segment, Segment, not acknowledged yet:
If SEG.SEQ == SND.UNA OR
Segment.xmit_ts + RACK.rtt + RACK.reo_wnd - Now() <= 0:
Segment.lost = TRUE
7.5.1. Phase 1: Scheduling a loss probe 7. TLP Algorithm Details
Step 1: Check conditions for scheduling a PTO. 7.1. Initializing state
A sender should check to see if it should schedule a PTO in the Reset TLP.is_retrans and TLP.end_seq when initiating a connection,
following situations: fast recovery, or RTO recovery.
1. After transmitting new data that was not itself a TLP probe TLP.is_retrans = false
2. Upon receiving an ACK that cumulatively acknowledges data 7.2. Scheduling a loss probe
A sender should schedule a PTO only if all of the following The sender schedules a loss probe timeout (PTO) to transmit a segment
conditions are met: during the normal transmission process. The sender SHOULD start or
restart a loss probe PTO timer after transmitting new data (that was
not itself a loss probe) or upon receiving an ACK that cumulatively
acknowledges new data, unless it is already in fast recovery, RTO
recovery, or the sender has segments delivered out-of-order (i.e.
RACK.segs_sacked is not zero). These conditions are excluded because
they are addressed by similar mechanisms, like Limited Transmit
[RFC3042], the RACK reordering timer, and F-RTO [RFC5682]. Further,
prior to scheduling a PTO the sender SHOULD cancel any pending PTO,
RTO, RACK reordering timer, or zero window probe (ZWP) timer
[RFC793].
1. The connection supports SACK [RFC2018] The sender calculates the PTO interval by taking into account a
2. The connection has no SACKed sequences in the SACK scoreboard number of factors.
3. The connection is not in loss recovery First, the default PTO interval is 2*SRTT. By that time, it is
prudent to declare that an ACK is overdue, since under normal
circumstances, i.e. no losses, an ACK typically arrives in one SRTT.
Choosing PTO to be exactly an SRTT would risk causing spurious
probes, given that network and end-host delay variance can cause an
ACK to be delayed beyond SRTT. Hence the PTO is conservatively
chosen to be the next integral multiple of SRTT.
If a PTO can be scheduled according to these conditions, the sender Second, when there is no SRTT estimate available, the PTO SHOULD be 1
should schedule a PTO. If there was a previously scheduled PTO or second. This conservative value corresponds to the RTO value when no
RTO pending, then that pending PTO or RTO should first be cancelled, SRTT is available, per [RFC6298].
and then the new PTO should be scheduled.
If a PTO cannot be scheduled according to these conditions, then the Third, when FlightSize is one segment, the sender MAY inflate PTO by
sender MUST arm the RTO timer if there is unacknowledged data in TLP.max_ack_delay to accommodate a potential delayed acknowledgment
flight. and reduce the risk of spurious retransmissions. The actual value of
TLP.max_ack_delay is implementation-specific.
Step 2: Select the duration of the PTO. Finally, if the time at which an RTO would fire (here denoted
"TCP_RTO_expiration()") is sooner than the computed time for the PTO,
then the sender schedules a TLP to be sent at that RTO time.
A sender SHOULD use the following logic to select the duration of a Summarizing these considerations in pseudocode form, a sender SHOULD
PTO: use the following logic to select the duration of a PTO:
TLP_timeout(): TLP_calc_PTO():
If SRTT is available: If SRTT is available:
PTO = 2 * SRTT PTO = 2 * SRTT
If FlightSize = 1: If FlightSize is one segment:
PTO += WCDelAckT PTO += TLP.max_ack_delay
Else: Else:
PTO = 1 sec PTO = 1 sec
If Now() + PTO > TCP_RTO_expire(): If Now() + PTO > TCP_RTO_expiration():
PTO = TCP_RTO_expire() - Now() PTO = TCP_RTO_expiration() - Now()
Aiming for a PTO value of 2*SRTT allows a sender to wait long enough
to know that an ACK is overdue. Under normal circumstances, i.e. no
losses, an ACK typically arrives in one SRTT. But choosing PTO to be
exactly an SRTT is likely to generate spurious probes given that
network delay variance and even end-system timings can easily push an
ACK to be above an SRTT. We chose PTO to be the next integral
multiple of SRTT.
WCDelAckT stands for worst case delayed ACK timer. When FlightSize
is 1, PTO is inflated by WCDelAckT time to compensate for a potential
long delayed ACK timer at the receiver. The RECOMMENDED value for
WCDelAckT is 200ms.
Finally, if the time at which an RTO would fire (here denoted
"TCP_RTO_expire") is sooner than the computed time for the PTO, then
a probe is scheduled to be sent at that earlier time.
7.5.2. Phase 2: Sending a loss probe
When the PTO fires, transmit a probe data segment:
TLP_send_probe(): 7.3. Sending a loss probe upon PTO expiration
If an unsent segment exists AND
the receive window allows new data to be sent:
Transmit the lowest-sequence unsent segment of up to SMSS
Increment FlightSize by the size of the newly-sent segment
Else if TLPRxtOut is not set: When the PTO timer expires, the sender SHOULD transmit a previously
Retransmit the highest-sequence segment sent so far unsent data segment, if the receive window allows, and increment the
TLPRxtOut = true FlightSize accordingly. Note that FlightSize could be one packet
TLPHighRxt = SND.NXT greater than the congestion window temporarily until the next ACK
The cwnd remains unchanged arrives.
When the loss probe is a retransmission, the sender uses the highest- If such a segment is not available, then the sender SHOULD retransmit
sequence segment sent so far. This is in order to deal with the the highest-sequence segment sent so far and set TLP.is_retrans to
true. This segment is chosen in order to deal with the
retransmission ambiguity problem in TCP. Suppose a sender sends N retransmission ambiguity problem in TCP. Suppose a sender sends N
segments, and then retransmits the last segment (segment N) as a loss 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 probe, and then the sender receives a SACK for segment N. As long as
the sender waits for any required RACK reordering settling timer to the sender waits for the RACK reordering window expire, it doesn't
then expire, it doesn't matter if that SACK was for the original matter if that SACK was for the original transmission of segment N or
transmission of segment N or the TLP retransmission; in either case the TLP retransmission; in either case the arrival of the SACK for
the arrival of the SACK for segment N provides evidence that the N-1 segment N provides evidence that the N-1 segments preceding segment N
segments preceding segment N were likely lost. In the case where were likely lost.
there is only one original outstanding segment of data (N=1), the
same logic (trivially) applies: an ACK for a single outstanding
segment tells the sender the N-1=0 segments preceding that segment
were lost. Furthermore, whether there are N>1 or N=1 outstanding
segments, there is a question about whether the original last segment
or its TLP retransmission were lost; the sender estimates this using
TLP recovery detection (see below).
Note that whether or not a probe was sent in TLP_send_probe(), the
sender MUST arm the RTO timer, not the PTO timer, at the end of
TLP_send_probe() if FlightSize is not zero. This ensures that the
sender does not send repeated, back-to-back TLP probes. Checking
TLPRxtOut prior to sending the loss probe is also critical to avoid
TLP loops if an application writes periodically at an interval less
than PTO.
7.5.3. Phase 3: ACK processing
On each incoming ACK, the sender should check the conditions in Step
1 of Phase 1 to see if it should schedule (or reschedule) the loss
probe timer.
7.6. TLP recovery detection
If the only loss in an outstanding window of data was the last
segment, then a TLP loss probe retransmission of that data segment
might repair the loss. TLP recovery detection examines ACKs to
detect when the probe might have repaired a loss, and thus allows
congestion control to properly reduce the congestion window (cwnd)
[RFC5681].
Consider a TLP retransmission episode where a sender retransmits a
tail packet in a flight. The TLP retransmission episode ends when
the sender receives an ACK with a SEG.ACK above the SND.NXT at the
time the episode started (i.e. TLPHighRxt). During the TLP
retransmission episode the sender checks for a duplicate ACK or
D-SACK indicating that both the original segment and TLP
retransmission arrived at the receiver, meaning there was no loss
that needed repairing. If the TLP sender does not receive such an
indication before the end of the TLP retransmission episode, then it
MUST estimate that either the original data segment or the TLP
retransmission were lost, and congestion control MUST react
appropriately to that loss as it would any other loss.
Since a significant fraction of the hosts that support SACK do not
support duplicate selective acknowledgments (D-SACKs) [RFC2883] the
TLP algorithm for detecting such lost segments relies only on basic
SACK support [RFC2018].
7.6.1. Initializing and resetting state
When a connection is created, or suffers a retransmission timeout, or
enters fast recovery, it executes the following:
TLPRxtOut = false
7.6.2. Recording loss probe states
Senders MUST only send a TLP loss probe retransmission if TLPRxtOut
is false. This ensures that at any given time a connection has at
most one outstanding TLP retransmission. This allows the sender to
use the algorithm described in this section to estimate whether any
data segments were lost.
Note that this condition only restricts TLP loss probes that are
retransmissions. There may be an arbitrary number of outstanding
unacknowledged TLP loss probes that consist of new, previously-unsent
data, since the retransmission timeout and fast recovery algorithms
are sufficient to detect losses of such probe segments.
Upon sending a TLP probe that is a retransmission, the sender sets
TLPRxtOut to true and TLPHighRxt to SND.NXT.
7.6.3. Detecting recoveries accomplished by loss probes
Step 1: Track ACKs indicating receipt of original and retransmitted
segments
A sender considers both the original segment and TLP probe
retransmission segment as acknowledged if either 1 or 2 are true:
1. This is a duplicate acknowledgment (as defined in [RFC5681],
section 2), and all of the following conditions are met:
1. TLPRxtOut is true 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 tells the sender the N-1=0 segments preceding
that segment were lost. Furthermore, whether there are N>1 or N=1
outstanding segments, there is a question about whether the original
last segment or its TLP retransmission were lost; the sender
estimates whether there was such a loss using TLP recovery detection
(see below).
2. SEG.ACK == TLPHighRxt The sender MUST follow the RACK transmission procedures in the ''Upon
Transmitting 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. Furthermore,
prior to sending a loss probe, the sender MUST check that 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 invariant 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 loss probe has been acknowledged or is deemed lost or irrelevant.
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 following pseudo code summarizes
the operations.
3. SEG.ACK == SND.UNA TLP_send_probe():
4. the segment contains no SACK blocks for sequence ranges above If TLP.end_seq is None:
TLPHighRxt TLP.is_retrans = false
Segment = send buffer segment starting at SND.NXT
If Segment exists and fits the peer receive window limit:
/* Transmit the lowest-sequence unsent Segment */
Transmit Segment
RACK_transmit_data(Segment)
TLP.end_seq = SND.NXT
Increase FlightSize by Segment length
Else:
/* Retransmit the highest-sequence Segment sent */
Segment = send buffer segment ending at SND.NXT
Transmit Segment
RACK_retransmit_data(Segment)
TLP.end_seq = SND.NXT
TLP.is_retrans = true
5. the segment contains no data 7.4. Detecting losses by the ACK of the loss probe
6. the segment is not a window update 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 pattern of losses.
2. This is an ACK acknowledging a sequence number at or above 7.4.1. General case: detecting packet losses using RACK
TLPHighRxt and it contains a D-SACK; i.e. all of the following
conditions are met:
1. TLPRxtOut is true If the loss probe and the ACK that acknowledges the probe are
delivered 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 typically infer 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_detect_loss() (step 5) would mark those
earlier segments as lost. Then the sender would trigger a fast
recovery to recover those losses.
2. SEG.ACK >= TLPHighRxt 7.4.2. Special case: detecting a single loss repaired by the loss probe
3. the ACK contains a D-SACK block 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 appears to be a regular cumulative ACK, which
would not normally trigger the congestion control response to this
packet loss event. The following TLP recovery detection mechanism
examines ACKs to detect this special case to make congestion control
respond properly [RFC5681].
If either of the conditions is met, then the sender estimates that After a TLP retransmission, the sender checks for this special case
the receiver received both the original data segment and the TLP of a single loss that is recovered by the loss probe itself. To
probe retransmission, and so the sender considers the TLP episode to accomplish this, the sender checks for a duplicate ACK or DSACK
be done, and records that fact by setting TLPRxtOut to false. indicating that both the original segment and TLP retransmission
arrived at the receiver, meaning there was no loss. If the TLP
sender does not receive such an indication, then it SHOULD assume
that either the original data segment or the TLP retransmission were
lost, for congestion control purposes.
Step 2: Mark the end of a TLP retransmission episode and detect If the TLP retransmission is spurious, a receiver that uses DSACK
losses would return an 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). 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
retransmission, and so the sender considers the TLP episode to be
done, and records that fact by setting TLP.end_seq to None.
If the sender receives a cumulative ACK for data beyond the TLP loss Upon receiving an ACK that covers some sequence number after
probe retransmission then, in the absence of reordering on the return TLP.end_seq, the sender should have received any ACKs for the
path of ACKs, it should have received any ACKs for the original original segment and TLP probe retransmission segment. At that time,
segment and TLP probe retransmission segment. At that time, if the if the TLP.end_seq is still set, and thus indicates that the TLP
TLPRxtOut flag is still true and thus indicates that the TLP probe probe retransmission remains unacknowledged, then the sender should
retransmission remains unacknowledged, then the sender should presume presume that at least one of its data segments was lost. The sender
that at least one of its data segments was lost, so it SHOULD invoke then SHOULD invoke a congestion control response equivalent to a fast
a congestion control response equivalent to fast recovery. recovery.
More precisely, on each ACK the sender executes the following: More precisely, on each ACK the sender executes the following:
if (TLPRxtOut and SEG.ACK >= TLPHighRxt) { TLP_process_ack(ACK):
TLPRxtOut = false If TLP.end_seq is not None AND ACK.seq >= TLP.end_seq:
EnterRecovery() If not TLP.is_retrans:
ExitRecovery() TLP.end_seq = None /* TLP of new data delivered */
} Else if ACK has a DSACK option matching TLP.end_seq:
TLP.end_seq = None /* Case 1, above */
8. RACK and TLP Discussion Else If SEG.ACK > TLP.end_seq:
TLP.end_seq = None /* Repaired the single loss */
(Invoke congestion control to react on
the loss event the probe has repaired)
Else If ACK is a DUPACK without any SACK option:
TLP.end_seq = None /* Case 2, above */
8.1. Advantages 8. Discussion
The biggest advantage of RACK is that every data packet, whether it 8.1. Advantages and disadvantages
is an original data transmission or a retransmission, can be used to
detect losses of the packets sent chronologically prior to it.
Example: TAIL DROP. Consider a sender that transmits a window of The biggest advantage of RACK-TLP is that every data segment, whether
three data packets (P1, P2, P3), and P1 and P3 are lost. Suppose the it is an original data transmission or a retransmission, can be used
transmission of each packet is at least RACK.reo_wnd (1 millisecond to detect losses of the segments sent chronologically prior to it.
by default) after the transmission of the previous packet. RACK will This enables RACK-TLP to use fast recovery in cases with application-
mark P1 as lost when the SACK of P2 is received, and this will limited flights of data, lost retransmissions, or data segment
trigger the retransmission of P1 as R1. When R1 is cumulatively reordering events. Consider the following examples:
acknowledged, RACK will mark P3 as lost and the sender will
retransmit P3 as R3. This example illustrates how RACK is able to
repair certain drops at the tail of a transaction without any timer.
Notice that neither the conventional duplicate ACK threshold
[RFC5681], nor [RFC6675], nor the Forward Acknowledgment [FACK]
algorithm can detect such losses, because of the required packet or
sequence count.
Example: LOST RETRANSMIT. Consider a window of three data packets 1. Packet drops at the end of an application data flight: Consider a
(P1, P2, P3) that are sent; P1 and P2 are dropped. Suppose the sender that transmits an application-limited flight of three data
transmission of each packet is at least RACK.reo_wnd (1 millisecond segments (P1, P2, P3), and P1 and P3 are lost. Suppose the
by default) after the transmission of the previous packet. When P3 transmission of each segment is at least RACK.reo_wnd after the
is SACKed, RACK will mark P1 and P2 lost and they will be transmission of the previous segment. RACK will mark P1 as lost
retransmitted as R1 and R2. Suppose R1 is lost again but R2 is when the SACK of P2 is received, and this will trigger the
SACKed; RACK will mark R1 lost for retransmission again. Again, retransmission of P1 as R1. When R1 is cumulatively
neither the conventional three duplicate ACK threshold approach, nor acknowledged, RACK will mark P3 as lost and the sender will
[RFC6675], nor the Forward Acknowledgment [FACK] algorithm can detect retransmit P3 as R3. This example illustrates how RACK is able
such losses. And such a lost retransmission is very common when TCP to repair certain drops at the tail of a transaction without an
is being rate-limited, particularly by token bucket policers with RTO recovery. Notice that neither the conventional duplicate ACK
large bucket depth and low rate limit. Retransmissions are often threshold [RFC5681], nor [RFC6675], nor the Forward
lost repeatedly because standard congestion control requires multiple Acknowledgment [FACK] algorithm can detect such losses, because
round trips to reduce the rate below the policed rate. of the required segment or sequence count.
Example: SMALL DEGREE OF REORDERING. Consider a common reordering 2. Lost retransmission: Consider a flight of three data segments
event: a window of packets are sent as (P1, P2, P3). P1 and P2 carry (P1, P2, P3) that are sent; P1 and P2 are dropped. Suppose the
a full payload of MSS octets, but P3 has only a 1-octet payload. transmission of each segment is at least RACK.reo_wnd after the
Suppose the sender has detected reordering previously and thus transmission of the previous segment. When P3 is SACKed, RACK
RACK.reo_wnd is min_RTT/4. Now P3 is reordered and delivered first, will mark P1 and P2 lost and they will be retransmitted as R1 and
before P1 and P2. As long as P1 and P2 are delivered within R2. Suppose R1 is lost again but R2 is SACKed; RACK will mark R1
min_RTT/4, RACK will not consider P1 and P2 lost. But if P1 and P2 lost and trigger retransmission again. Again, neither the
are delivered outside the reordering window, then RACK will still conventional three duplicate ACK threshold approach, nor
falsely mark P1 and P2 lost. We discuss how to reduce false [RFC6675], nor the Forward Acknowledgment [FACK] algorithm can
positives in the end of this section. detect such losses. And such a lost retransmission can happen
when TCP is being rate-limited, particularly by token bucket
policers with large bucket depth and low rate limit; in such
cases retransmissions are often lost repeatedly because standard
congestion control requires multiple round trips to reduce the
rate below the policed rate.
The examples above show that RACK is particularly useful when the 3. Packet reordering: Consider a simple reordering event where a
sender is limited by the application, which is common for flight of segments are sent as (P1, P2, P3). P1 and P2 carry a
interactive, request/response traffic. Similarly, RACK still works full payload of MSS octets, but P3 has only a 1-octet payload.
when the sender is limited by the receive window, which is common for Suppose the sender has detected reordering previously and thus
applications that use the receive window to throttle the sender. RACK.reo_wnd is min_RTT/4. Now P3 is reordered and delivered
first, before P1 and P2. As long as P1 and P2 are delivered
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 lost.
For some implementations (e.g., Linux), RACK works quite efficiently The examples above show that RACK-TLP is particularly useful when the
with TCP Segmentation Offload (TSO). RACK always marks the entire sender is limited by the application, which can happen with
TSO blob lost because the packets in the same TSO blob have the same interactive or request/response traffic. Similarly, RACK still works
transmission timestamp. By contrast, the algorithms based on when the sender is limited by the receive window, which can happen
sequence counting (e.g., [RFC6675][RFC5681]) may mark only a subset with applications that use the receive window to throttle the sender.
of packets in the TSO blob lost, forcing the stack to perform
expensive fragmentation of the TSO blob, or to selectively tag
individual packets lost in the scoreboard.
8.2. Disadvantages 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 contrast, 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
perform expensive fragmentation of the TSO aggregate, or to
selectively tag individual segments lost in the scoreboard.
RACK requires the sender to record the transmission time of each The main drawback of RACK-TLP is the additional states required
packet sent at a clock granularity of one millisecond or finer. TCP compared 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 minimum RTT of the connection. TCP
implementations that record this already for RTT estimation do not implementations that record this already for RTT estimation do not
require any new per-packet state. But implementations that are not require any new per-packet state. But implementations that are not
yet recording packet transmission times will need to add per-packet yet recording segment transmission times will need to add per-packet
internal state (commonly either 4 or 8 octets per packet or TSO blob) internal state (expected to be either 4 or 8 octets per segment or
to track transmission times. In contrast, the conventional [RFC6675] TSO aggregate) to track transmission times. In contrast, [RFC6675]
loss detection approach does not require any per-packet state beyond loss detection approach does not require any per-packet state beyond
the SACK scoreboard. This is particularly useful on ultra-low RTT the SACK scoreboard; this is particularly useful on ultra-low RTT
networks where the RTT is far less than the sender TCP clock networks where the RTT may be less than the sender TCP clock
granularity (e.g. inside data-centers). granularity (e.g. inside data-centers).
RACK can easily and optionally support the conventional approach in 8.2. Relationships with other loss recovery algorithms
[RFC6675][RFC5681] by resetting the reordering window to zero when
the threshold is met. Note that this approach differs slightly from
[RFC6675] which considers a packet lost when at least DupThresh
higher-sequence packets are SACKed. RACK's approach considers a
packet lost when at least one higher sequence packet is SACKed and
the total number of SACKed packets is at least DupThresh. For
example, suppose a connection sends 10 packets, and packets 3, 5, 7
are SACKed. [RFC6675] considers packets 1 and 2 lost. RACK
considers packets 1, 2, 4, 6 lost.
8.3. Adjusting the reordering window
When the sender detects packet reordering, RACK uses a reordering
window of min_rtt / 4. It uses the minimum RTT to accommodate
reordering introduced by packets traversing slightly different paths
(e.g., router-based parallelism schemes) or out-of-order deliveries
in the lower link layer (e.g., wireless links using link-layer
retransmission). RACK uses a quarter of minimum RTT because Linux
TCP used the same factor in its implementation to delay Early
Retransmit [RFC5827] to reduce spurious loss detections in the
presence of reordering, and experience shows that this seems to work
reasonably well. We have evaluated using the smoothed RTT (SRTT from
[RFC6298] RTT estimation) or the most recently measured RTT
(RACK.rtt) using an experiment similar to that in the Performance
Evaluation section. They do not make any significant difference in
terms of total recovery latency.
8.4. Relationships with other loss recovery algorithms
The primary motivation of RACK is to ultimately provide a simple and
general replacement for some of the standard loss recovery algorithms
[RFC5681][RFC6675][RFC5827][RFC4653], as well as some nonstandard
ones [FACK][THIN-STREAM]. While RACK can be a supplemental loss
detection mechanism on top of these algorithms, this is not
necessary, because RACK implicitly subsumes most of them.
[RFC5827][RFC4653][THIN-STREAM] dynamically adjusts the duplicate ACK
threshold based on the current or previous flight sizes. RACK takes
a different approach, by using only one ACK event and a reordering
window. RACK can be seen as an extended Early Retransmit [RFC5827]
without a FlightSize limit but with an additional reordering window.
[FACK] considers an original packet to be lost when its sequence
range is sufficiently far below the highest SACKed sequence. In some
sense RACK can be seen as a generalized form of FACK that operates in
time space instead of sequence space, enabling it to better handle
reordering, application-limited traffic, and lost retransmissions.
Since the 3 duplicate ACK threshold for triggering fast recovery
[RFC5681] has been widely deployed and usually works well in the
absence of reordering, RACK uses this signal to trigger fast recovery
if a connection has not observed reordering.
RACK is compatible with and does not interfere with the standard RTO
[RFC6298], RTO-restart [RFC7765], F-RTO [RFC5682] and Eifel
algorithms [RFC3522]. This is because RACK only detects loss by
using ACK events. It neither changes the RTO timer calculation nor
detects spurious timeouts.
Furthermore, RACK naturally works well with Tail Loss Probe [TLP] The primary motivation of RACK-TLP is to provide a general
because a tail loss probe solicits either an ACK or SACK, which can alternative to some of the standard loss recovery algorithms
be used by RACK to detect more losses. RACK can be used to relax [RFC5681][RFC6675][RFC5827][RFC4653]. [RFC5827][RFC4653] dynamically
TLP's requirement for using FACK and retransmitting the the highest- adjusts the duplicate ACK threshold based on the current or previous
sequenced packet, because RACK is agnostic to packet sequence flight sizes. RACK-TLP takes a different approach by using a time-
numbers, and uses transmission time instead. Thus TLP could be based reordering window. RACK-TLP can be seen as an extended Early
modified to retransmit the first unacknowledged packet, which could Retransmit [RFC5827] without a FlightSize limit but with an
improve application latency. additional reordering window. [FACK] considers an original segment
to be lost when its sequence range is 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
sequence space, enabling it to better handle reordering, application-
limited traffic, and lost retransmissions.
8.5. Interaction with congestion control 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 nor detects spurious RTO.
RACK intentionally decouples loss detection from congestion control. 8.3. Interaction with congestion control
RACK only detects losses; it does not modify the congestion control
algorithm [RFC5681][RFC6937]. A packet marked lost by RACK SHOULD
NOT be retransmitted until congestion control deems this appropriate.
RACK is applicable for both fast recovery and recovery after a RACK-TLP intentionally decouples loss detection from congestion
retransmission timeout (RTO) in [RFC5681]. RACK applies equally to control. RACK-TLP only detects losses; it does not modify the
fast recovery and RTO recovery because RACK is purely based on the congestion control algorithm [RFC5681][RFC6937]. A segment marked
transmission time order of packets. When a packet retransmitted by lost by RACK-TLP MUST not be retransmitted until congestion control
RTO is acknowledged, RACK will mark any unacked packet sent deems this appropriate.
sufficiently prior to the RTO as lost, because at least one RTT has
elapsed since these packets were sent.
RACK may detect losses faster or slower than the conventional The only exception -- the only way in which RACK-TLP modulates the
duplicate ACK threshold approach does. RACK can detect losses faster congestion control algorithm -- is that one outstanding loss probe
by not requiring three DUPACKs, so congestion control may reduce the can be sent even if the congestion window is full. However, this
congestion window earlier. When the network path has both reordering temporary over-commit is accounted for and credited in the in-flight
and losses, RACK detects losses slower by waiting for the reordering data tracked for congestion control, so that congestion control will
window to expire. TCP may continue to increase the congestion window erase the over-commit upon the next ACK.
upon receiving ACKs during this time, making the sender more
aggressive. Certain congestion control algorithms can benefit from
accounting for this increase in the congestion window during the
reordering window.
8.5.1. Example: interactions with congestion control If packet losses happen after the reordering window has been
increased by DSACK, 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 during this time,
making the sender more aggressive.
The following simple example compares how RACK and non-RACK loss The following simple example compares how RACK-TLP and non-RACK-TLP
detection interacts with congestion control: suppose a TCP sender has loss detection interacts with congestion control: suppose a sender
a congestion window (cwnd) of 20 packets on a SACK-enabled has a congestion window (cwnd) of 20 segments on a SACK-enabled
connection. It sends 10 data packets and all of them are lost. connection. It sends 10 data segments and all of them are lost.
Without RACK, the sender would time out, reset cwnd to 1, and Without RACK-TLP, the sender would time out, reset cwnd to 1, and
retransmit the first packet. It would take four round trips (1 + 2 + retransmit the first segment. It would take four round trips (1 + 2
4 + 3 = 10) to retransmit all the 10 lost packets using slow start. + 4 + 3 = 10) to retransmit all the 10 lost segments using slow
The recovery latency would be RTO + 4*RTT, with an ending cwnd of 4 start. The recovery latency would be RTO + 4*RTT, with an ending
packets due to congestion window validation. cwnd of 4 segments due to congestion window validation.
With RACK, a sender would send the TLP after 2*RTT and get a DUPACK. With RACK-TLP, a sender would send the TLP after 2*RTT and get a
DUPACK, enabling RACK to detect the losses and trigger fast recovery.
If the sender implements Proportional Rate Reduction [RFC6937] it If the sender implements Proportional Rate Reduction [RFC6937] it
would slow start to retransmit the remaining 9 lost packets since the would slow start to retransmit the remaining 9 lost segments since
number of packets in flight (0) is lower than the slow start the number of segments in flight (0) is lower than the slow start
threshold (10). The slow start would again take four round trips (1 threshold (10). The slow start would again take four round trips (1
+ 2 + 4 + 3 = 10). The recovery latency would be 2*RTT + 4*RTT, with + 2 + 4 + 3 = 10) to retransmit all the lost segments. The recovery
an ending cwnd set to the slow start threshold of 10 packets. latency would be 2*RTT + 4*RTT, with an ending cwnd set to the slow
start threshold of 10 segments.
In both cases, the sender after the recovery would be in congestion The difference in recovery latency (RTO + 4*RTT vs 6*RTT) can be
avoidance. The difference in recovery latency (RTO + 4*RTT vs 6*RTT) significant if the RTT is much smaller than the minimum RTO (1 second
can be significant if the RTT is much smaller than the minimum RTO (1 in [RFC6298]) or if the RTT is large. The former case can happen in
second in RFC6298) or if the RTT is large. The former case is common local area networks, data-center networks, or content distribution
in local area networks, data-center networks, or content distribution networks with deep deployments. The latter case can happen in
networks with deep deployments. The latter case is more common in
developing regions with highly congested and/or high-latency developing regions with highly congested and/or high-latency
networks. networks.
8.6. TLP recovery detection with delayed ACKs 8.4. TLP recovery detection with delayed ACKs
Delayed ACKs complicate the detection of repairs done by TLP, since Delayed ACKs complicate the detection of repairs done by TLP, since
with a delayed ACK the sender receives one fewer ACK than would with a delayed ACK the sender receives one fewer ACK than would
normally be expected. To mitigate this complication, before sending normally be expected. To mitigate this complication, before sending
a TLP loss probe retransmission, the sender should attempt to wait a TLP loss probe retransmission, the sender should attempt to wait
long enough that the receiver has sent any delayed ACKs that it is long enough that the receiver has sent any delayed ACKs that it is
withholding. The sender algorithm described above features such a withholding. The sender algorithm described above features such a
delay, in the form of WCDelAckT. Furthermore, if the receiver delay, in the form of TLP.max_ack_delay. Furthermore, if the
supports duplicate selective acknowledgments (D-SACKs) [RFC2883] then receiver supports DSACK then in the case of a delayed ACK the
in the case of a delayed ACK the sender's TLP recovery detection sender's TLP recovery detection mechanism (see above) can use the
algorithm (see above) can use the D-SACK information to infer that DSACK information to infer that the original and TLP retransmission
the original and TLP retransmission both arrived at the receiver. both arrived at the receiver.
If there is ACK loss or a delayed ACK without a D-SACK, then this
algorithm is conservative, because the sender will reduce cwnd 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 cwnd can be prudent.
8.7. RACK for other transport protocols 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 window can be
prudent.
RACK can be implemented in other transport protocols. The algorithm 8.5. RACK for other transport protocols
can be simplified by skipping step 3 if the protocol can support a
unique transmission or packet identifier (e.g. TCP timestamp options
[RFC7323]). For example, the QUIC protocol implements RACK [QUIC- RACK can be implemented in other transport protocols (e.g., [QUIC-
LR]. The [Sprout] loss detection algorithm was also independently LR]). The [Sprout] loss detection algorithm was also independently
designed to use a 10ms reordering window to improve its loss designed to use a 10ms reordering window to improve its loss
detection. detection.
9. Experiments and Performance Evaluations 9. Security Considerations
RACK and TLP have been deployed at Google, for both connections to
users in the Internet and internally. We conducted a performance
evaluation experiment for RACK and TLP on a small set of Google Web
servers in Western Europe that serve mostly European and some African
countries. The experiment lasted three days in March 2017. The
servers were divided evenly into four groups of roughly 5.3 million
flows each:
Group 1 (control): RACK off, TLP off, RFC 6675 on
Group 2: RACK on, TLP off, RFC 6675 on
Group 3: RACK on, TLP on, RFC 6675 on
Group 4: RACK on, TLP on, RFC 6675 off
All groups used Linux with CUBIC congestion control, an initial
congestion window of 10 packets, and the fq/pacing qdisc. In terms
of specific recovery features, all groups enabled RFC5682 (F-RTO) but
disabled FACK because it is not an IETF RFC. FACK was excluded
because the goal of this setup is to compare RACK and TLP to RFC-
based loss recoveries. Since TLP depends on either FACK or RACK, we
could not run another group that enables TLP only (with both RACK and
FACK disabled). Group 4 is to test whether RACK plus TLP can
completely replace the DupThresh-based [RFC6675].
The servers sit behind a load balancer that distributes the
connections evenly across the four groups.
Each group handles a similar number of connections and sends and
receives similar amounts of data. We compare total time spent in
loss recovery across groups. The recovery time is measured from when
the recovery and retransmission starts, until the remote host has
acknowledged the highest sequence (SND.NXT) at the time the recovery
started. Therefore the recovery includes both fast recoveries and
timeout recoveries.
Our data shows that Group 2 recovery latency is only 0.3% lower than
the Group 1 recovery latency. But Group 3 recovery latency is 25%
lower than Group 1 due to a 40% reduction in RTO-triggered
recoveries! Therefore it is important to implement both TLP and RACK
for performance. Group 4's total recovery latency is 0.02% lower
than Group 3's, indicating that RACK plus TLP can successfully
replace RFC6675 as a standalone recovery mechanism.
We want to emphasize that the current experiment is limited in terms
of network coverage. The connectivity in Western Europe is fairly
good, therefore loss recovery is not a major performance bottleneck.
We plan to expand our experiments to regions with worse connectivity,
in particular on networks with strong traffic policing.
10. Security Considerations
RACK does not change the risk profile for TCP. RACK-TLP algorithm behavior is based on information conveyed in SACK
options, so it has security considerations similar to those described
in the Security Considerations section of [RFC6675].
An interesting scenario is ACK-splitting attacks [SCWA99]: for an Additionally, RACK-TLP has a lower risk profile than [RFC6675]
MSS-size packet sent, the receiver or the attacker might send MSS 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 additional byte per ACK. This ACKs that SACK or acknowledge one additional byte per ACK. This
would not fool RACK. RACK.xmit_ts would not advance because all the would not fool RACK. In such a scenario, RACK.xmit_ts would not
sequences of the packet are transmitted at the same time (carry the advance, because all the sequence ranges within the segment were
same transmission timestamp). In other words, SACKing only one byte transmitted at the same time, and thus carry the same transmission
of a packet or SACKing the packet in entirety have the same effect on timestamp. In other words, SACKing only one byte of a segment or
RACK. SACKing the segment in entirety have the same effect with RACK.
11. IANA Considerations 10. IANA Considerations
This document makes no request of IANA. This document makes no request of IANA.
Note to RFC Editor: this section may be removed on publication as an Note to RFC Editor: this section may be removed on publication as an
RFC. RFC.
12. Acknowledgments 11. Acknowledgments
The authors thank Matt Mathis for his insights in FACK and Michael The authors thank Matt Mathis for his insights in FACK and Michael
Welzl for his per-packet timer idea that inspired this work. Eric Welzl for his per-packet timer idea that inspired this work. Eric
Dumazet, Randy Stewart, Van Jacobson, Ian Swett, Rick Jones, Jana Dumazet, Randy Stewart, Van Jacobson, Ian Swett, Rick Jones, Jana
Iyengar, Hiren Panchasara, Praveen Balasubramanian, Yoshifumi Iyengar, Hiren Panchasara, Praveen Balasubramanian, Yoshifumi
Nishida, Bob Briscoe, Felix Weinrank, Michael Tuexen, Martin Duke, Nishida, Bob Briscoe, Felix Weinrank, Michael Tuexen, Martin Duke,
and Ilpo Jarvinen contributed to the draft or the implementations in Ilpo Jarvinen, Theresa Enghardt, Mirja Kuehlewind, Gorry Fairhurst,
Linux, FreeBSD, Windows and QUIC. and Yi Huang contributed to the draft or the implementations in
Linux, FreeBSD, Windows, and QUIC.
13. References 12. References
13.1. Normative References 12.1. Normative References
[RFC2018] Mathis, M. and J. Mahdavi, "TCP Selective Acknowledgment [RFC2018] Mathis, M. and J. Mahdavi, "TCP Selective Acknowledgment
Options", RFC 2018, October 1996. Options", RFC 2018, October 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997. Requirement Levels", RFC 2119, March 1997.
[RFC2883] Floyd, S., Mahdavi, J., Mathis, M., and M. Podolsky, "An [RFC2883] Floyd, S., Mahdavi, J., Mathis, M., and M. Podolsky, "An
Extension to the Selective Acknowledgement (SACK) Option Extension to the Selective Acknowledgement (SACK) Option
for TCP", RFC 2883, July 2000. for TCP", RFC 2883, July 2000.
skipping to change at page 28, line 47 skipping to change at page 29, line 47
[RFC6937] Mathis, M., Dukkipati, N., and Y. Cheng, "Proportional [RFC6937] Mathis, M., Dukkipati, N., and Y. Cheng, "Proportional
Rate Reduction for TCP", May 2013. Rate Reduction for TCP", May 2013.
[RFC7323] Borman, D., Braden, B., Jacobson, V., and R. [RFC7323] Borman, D., Braden, B., Jacobson, V., and R.
Scheffenegger, "TCP Extensions for High Performance", Scheffenegger, "TCP Extensions for High Performance",
September 2014. September 2014.
[RFC793] Postel, J., "Transmission Control Protocol", September [RFC793] Postel, J., "Transmission Control Protocol", September
1981. 1981.
13.2. Informative References 12.2. Informative References
[DMCG11] Dukkipati, N., Mathis, M., Cheng, Y., and M. Ghobadi,
"Proportional Rate Reduction for TCP", May 2013.
[FACK] Mathis, M. and M. Jamshid, "Forward acknowledgement: [FACK] Mathis, M. and M. Jamshid, "Forward acknowledgement:
refining TCP congestion control", ACM SIGCOMM Computer refining TCP congestion control", ACM SIGCOMM Computer
Communication Review, Volume 26, Issue 4, Oct. 1996. , Communication Review, Volume 26, Issue 4, Oct. 1996. ,
1996. 1996.
[POLICER16] [POLICER16]
Flach, T., Papageorge, P., Terzis, A., Pedrosa, L., Cheng, Flach, T., Papageorge, P., Terzis, A., Pedrosa, L., Cheng,
Y., Karim, T., Katz-Bassett, E., and R. Govindan, "An Y., Karim, T., Katz-Bassett, E., and R. Govindan, "An
Analysis of Traffic Policing in the Web", ACM SIGCOMM , Analysis of Traffic Policing in the Web", ACM SIGCOMM ,
2016. 2016.
[QUIC-LR] Iyengar, J. and I. Swett, "QUIC Loss Recovery And [QUIC-LR] Iyengar, J. and I. Swett, "QUIC Loss Recovery And
Congestion Control", draft-ietf-quic-recovery-latest (work Congestion Control", draft-ietf-quic-recovery-latest (work
in progress), March 2020. in progress), March 2020.
[RACK-TCPM97]
Cheng, Y., "RACK: a time-based fast loss recovery", IETF97
TCPM meeting , 2016.
[RFC7765] Hurtig, P., Brunstrom, A., Petlund, A., and M. Welzl, "TCP [RFC7765] Hurtig, P., Brunstrom, A., Petlund, A., and M. Welzl, "TCP
and SCTP RTO Restart", February 2016. and SCTP RTO Restart", February 2016.
[SCWA99] Savage, S., Cardwell, N., Wetherall, D., and T. Anderson, [SCWA99] Savage, S., Cardwell, N., Wetherall, D., and T. Anderson,
"TCP Congestion Control With a Misbehaving Receiver", ACM "TCP Congestion Control With a Misbehaving Receiver", ACM
Computer Communication Review, 29(5) , 1999. Computer Communication Review, 29(5) , 1999.
[Sprout] Winstein, K., Sivaraman, A., and H. Balakrishnan, [Sprout] Winstein, K., Sivaraman, A., and H. Balakrishnan,
"Stochastic Forecasts Achieve High Throughput and Low "Stochastic Forecasts Achieve High Throughput and Low
Delay over Cellular Networks", USENIX Symposium on Delay over Cellular Networks", USENIX Symposium on
Networked Systems Design and Implementation (NSDI) , 2013. Networked Systems Design and Implementation (NSDI) , 2013.
[THIN-STREAM]
Petlund, A., Evensen, K., Griwodz, C., and P. Halvorsen,
"TCP enhancements for interactive thin-stream
applications", NOSSDAV , 2008.
[TLP] Dukkipati, N., Cardwell, N., Cheng, Y., and M. Mathis, [TLP] Dukkipati, N., Cardwell, N., Cheng, Y., and M. Mathis,
"Tail Loss Probe (TLP): An Algorithm for Fast Recovery of "Tail Loss Probe (TLP): An Algorithm for Fast Recovery of
Tail Drops", draft-dukkipati-tcpm-tcp-loss-probe-01 (work Tail Drops", draft-dukkipati-tcpm-tcp-loss-probe-01 (work
in progress), August 2013. in progress), August 2013.
Authors' Addresses Authors' Addresses
Yuchung Cheng Yuchung Cheng
Google, Inc Google, Inc
 End of changes. 188 change blocks. 
971 lines changed or deleted 999 lines changed or added

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