Proportional Rate Reduction for TCP
draft-ietf-tcpm-prr-rfc6937bis-13
| Document | Type | Active Internet-Draft (tcpm WG) | |
|---|---|---|---|
| Authors | Matt Mathis , Nandita Dukkipati , Yuchung Cheng , Neal Cardwell | ||
| Last updated | 2025-04-15 (Latest revision 2024-11-09) | ||
| Replaces | draft-mathis-tcpm-rfc6937bis | ||
| RFC stream | Internet Engineering Task Force (IETF) | ||
| Intended RFC status | Proposed Standard | ||
| Formats | |||
| Additional resources | Mailing list discussion | ||
| Stream | WG state | Submitted to IESG for Publication | |
| Associated WG milestone |
|
||
| Document shepherd | Yoshifumi Nishida | ||
| Shepherd write-up | Show Last changed 2025-04-04 | ||
| IESG | IESG state | AD Evaluation::Revised I-D Needed | |
| Action Holders | |||
| Consensus boilerplate | Yes | ||
| Telechat date | (None) | ||
| Responsible AD | Gorry Fairhurst | ||
| Send notices to | nsd.ietf@gmail.com |
draft-ietf-tcpm-prr-rfc6937bis-13
TCP Maintenance Working Group M. Mathis
Internet-Draft
Obsoletes: 6937 (if approved) N. Dukkipati
Intended status: Standards Track Y. Cheng
Expires: 13 May 2025 N. Cardwell
Google, Inc.
9 November 2024
Proportional Rate Reduction for TCP
draft-ietf-tcpm-prr-rfc6937bis-13
Abstract
This document updates the experimental Proportional Rate Reduction
(PRR) algorithm, described RFC 6937, to standards track. PRR
provides logic to regulate the amount of data sent by TCP or other
transport protocols during fast recovery. PRR accurately regulates
the actual flight size through recovery such that at the end of
recovery it will be as close as possible to the slow start threshold
(ssthresh), as determined by the congestion control algorithm.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 13 May 2025.
Copyright Notice
Copyright (c) 2024 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
Mathis, et al. Expires 13 May 2025 [Page 1]
Internet-Draft Proportional Rate Reduction November 2024
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Document and WG Information . . . . . . . . . . . . . . . 3
2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Changes From RFC 6937 . . . . . . . . . . . . . . . . . . . . 7
4. Relationships to other standards . . . . . . . . . . . . . . 9
5. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 9
6. Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 11
7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8. Properties . . . . . . . . . . . . . . . . . . . . . . . . . 15
9. Adapting PRR to other transport protocols . . . . . . . . . . 17
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 17
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
12. Security Considerations . . . . . . . . . . . . . . . . . . . 17
13. Normative References . . . . . . . . . . . . . . . . . . . . 18
14. Informative References . . . . . . . . . . . . . . . . . . . 18
Appendix A. Strong Packet Conservation Bound . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 21
1. Introduction
This document updates the Proportional Rate Reduction (PRR) algorithm
described in [RFC6937] from experimental to standards track. PRR
smoothly regulates the amount of data sent during fast recovery, such
that at the end of recovery the flight size will be as close as
possible to the slow start threshold (ssthresh), as determined by the
congestion control algorithm. PRR has been deployed in at least
three major TCP implementations covering the vast majority of today's
web traffic.
This document specifies several main changes from RFC 6937. First,
it introduces a new heuristic that replaces a manual configuration
parameter that determined how conservative PRR was when the volume of
in-flight data was less than ssthresh. Second, the algorithm
specifies behavior for non-SACK connections. Third, the algorithm
ensures a smooth sending process even when the sender has experienced
high reordering and starts loss recovery after a large amount of
sequence space has been SACKed. Finally, this document also includes
additional discussion about the integration of PRR with congestion
control and lost detection algorithms.
Mathis, et al. Expires 13 May 2025 [Page 2]
Internet-Draft Proportional Rate Reduction November 2024
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
1.1. Document and WG Information
Formatted: 2024-11-09 20:55:47+00:00
Please send all comments, questions and feedback to tcpm@ietf.org
About revision 00:
The introduction above was drawn from draft-mathis-tcpm-rfc6937bis-
00. All of the text below was copied verbatim from RFC 6937, to
facilitate comparison between RFC 6937 and this document as it
evolves.
About revision 01:
* Recast the RFC 6937 introduction as background
* Made "Changes From RFC 6937" an explicit section
* Made Relationships to other standards more explicit
* Added a generalized safeACK heuristic
* Provided hints for non TCP implementations
* Added language about detecting ACK splitting, but have no advice
on actions (yet)
About revision 02:
* Companion RACK loss detection RECOMMENDED
* Non-SACK accounting in the pseudo code
* cwnd computation in the pseudo code
* Force fast retransmit at the beginning of fast recovery
* Remove deprecated Rate-Halving text
* Fixed bugs in the example traces
About revision 03 and 04:
Mathis, et al. Expires 13 May 2025 [Page 3]
Internet-Draft Proportional Rate Reduction November 2024
* Clarify when and how sndcnt becomes 0
* Improve algorithm to smooth the sending rate under higher
reordering cases
About revision 05:
* Revert the RecoverFS text and pseudocode to match the behavior in
draft revision 03 and more closely match Linux TCP PRR
About revision 06:
* Update RecoverFS to be initialized as: RecoverFS = pipe.
About revision 07:
* Restored the revision 04 prose description for the rationale for
initializing RecoverFS as: RecoverFS = pipe.
* Added reference to [Hoe96Startup] in acknowledgements
About revision 08:
* Inserted missing reference to [RFC9293]
* Recategorized "voluntary window reductions" as a phrase introduced
by PRR
About revision 09:
* Document the setting of cwnd = ssthresh when the sender completes
a PRR episode, based on Linux TCP PRR experience and the mailing
list discussion in the TCPM mailing list thread: "draft-ietf-tcpm-
prr-rfc6937bis-03: set cwnd to ssthresh exiting fast recovery?".
Mention the potential for bursts as a result of setting cwnd =
ssthresh. Say that pacing is RECOMMENDED to deal with this.
* Revised RecoverFS initialization to handle fast recoveries with
mixes of real and spurious loss detection events (due to
reordering), and incorporate consideration for a potentially large
volume of data that is SACKed before fast recovery starts.
* Fixed bugs in the definition of DeliveredData (reverted to
definition from RFC 6937).
* Clarified PRR triggers initialization based on start of congestion
control reduction, not loss recovery, since congestion control may
reduce ssthresh for each round trip with new losses in recovery.
Mathis, et al. Expires 13 May 2025 [Page 4]
Internet-Draft Proportional Rate Reduction November 2024
* Fixed bugs in PRR examples.
About revision 10:
* Minor typo fixes and wordsmithing.
About revision 11:
* Based on comments at the TCPM session at IETF 120, clarified the
scope of congestion control algorithms for which PRR can be used,
and clarified that it can be used for Reno or CUBIC.
About revision 12:
* Added "About revision 11" and "About revision 12" sections.
* Added a clarification about the applicability to CUBIC in the
algorithm section.
About revision 13:
* Switch from using the RFC 6675 "pipe" concept to an "inflight"
concept that is independent of loss detection algorithm, and thus
is usable with RACK-TLP loss detection [RFC8985]
2. Background
Congestion control algorithms like Reno [RFC5681] and CUBIC [RFC9438]
require that TCP (and other protocols) reduce their congestion window
(cwnd) in response to losses. Fast recovery is the reference
algorithm for making this adjustment using feedback from
acknowledgements. Its stated goal is to recover TCP's self clock by
relying on returning ACKs during recovery to clock more data into the
network. Without PRR, fast recovery typically adjusts the window by
waiting for a large fraction of a round-trip time (one half round-
trip time of ACKs for Reno [RFC5681], or 30% of a round-trip time for
CUBIC [RFC9438]) to pass before sending any data.
Mathis, et al. Expires 13 May 2025 [Page 5]
Internet-Draft Proportional Rate Reduction November 2024
[RFC6675] makes fast recovery with Selective Acknowledgement (SACK)
[RFC2018] more accurate by computing "pipe", a sender side estimate
of the number of bytes still outstanding in the network. With
[RFC6675], fast recovery is implemented by sending data as necessary
on each ACK to allow pipe to rise to match ssthresh, the window size
as determined by the congestion control algorithm. This protects
fast recovery from timeouts in many cases where there are heavy
losses, although not if the entire second half of the window of data
or ACKs are lost. However, a single ACK carrying a SACK option that
implies a large quantity of missing data can cause a step
discontinuity in the pipe estimator, which can cause Fast Retransmit
to send a burst of data.
PRR avoids these excess window adjustments such that at the end of
recovery the actual window size will be as close as possible to
ssthresh, the window size as determined by the congestion control
algorithm. It uses the fraction that is appropriate for the target
window chosen by the congestion control algorithm. During PRR, one
of two additional Reduction Bound algorithms limits the total window
reduction due to all mechanisms, including transient application
stalls and the losses themselves.
We describe two slightly different Reduction Bound algorithms:
Conservative Reduction Bound (CRB), which is strictly packet
conserving; and a Slow Start Reduction Bound (SSRB), which is more
aggressive than CRB by, at most, 1 segment per ACK. PRR-CRB meets
the Strong Packet Conservation Bound described in Appendix A;
however, in real networks it does not perform as well as the
algorithms described in [RFC6675], which prove to be more aggressive
in a significant number of cases. SSRB offers a compromise by
allowing TCP to send 1 additional segment per ACK relative to CRB in
some situations. Although SSRB is less aggressive than [RFC6675]
(transmitting fewer segments or taking more time to transmit them),
it outperforms due to the lower probability of additional losses
during recovery.
The Strong Packet Conservation Bound on which PRR and both Reduction
Bounds are based is patterned after Van Jacobson's packet
conservation principle: segments delivered to the receiver are used
as the clock to trigger sending the same number of segments back into
the network. As much as possible, PRR and the Reduction Bound
algorithms rely on this self clock process, and are only slightly
affected by the accuracy of other estimators, such as the estimate of
the volume of in-flight data. This is what gives the algorithms
their precision in the presence of events that cause uncertainty in
other estimators.
Mathis, et al. Expires 13 May 2025 [Page 6]
Internet-Draft Proportional Rate Reduction November 2024
The original definition of the packet conservation principle
[Jacobson88] treated packets that are presumed to be lost (e.g.,
marked as candidates for retransmission) as having left the network.
This idea is reflected in the estimator for in-flight data used by
PRR, but it is distinct from the Strong Packet Conservation Bound as
described in Appendix A, which is defined solely on the basis of data
arriving at the receiver.
3. Changes From RFC 6937
The largest change since [RFC6937] is the introduction of a new
heuristic that uses good recovery progress (for TCP, when the latest
ACK advances snd.una and does not indicate that a prior fast
retransmit has been lost) to select the Reduction Bound. [RFC6937]
left the choice of Reduction Bound to the discretion of the
implementer but recommended to use SSRB by default. For all of the
environments explored in earlier PRR research, the new heuristic is
consistent with the old recommendation.
The paper "An Internet-Wide Analysis of Traffic Policing"
[Flach2016policing] uncovered a crucial situation not previously
explored, where both Reduction Bounds perform very poorly, but for
different reasons. Under many configurations, token bucket traffic
policers can suddenly start discarding a large fraction of the
traffic when tokens are depleted, without any warning to the end
systems. The transport congestion control has no opportunity to
measure the token rate, and sets ssthresh based on the previously
observed path performance. This value for ssthresh may cause a data
rate that is substantially larger than the token replenishment rate,
causing high loss. Under these conditions, both reduction bounds
perform very poorly. PRR-CRB is too timid, sometimes causing very
long recovery times at smaller than necessary windows, and PRR-SSRB
is too aggressive, often causing many retransmissions to be lost for
multiple rounds. Both cases lead to prolonged recovery, decimating
application latency and/or goodput.
Investigating these environments led to the development of a
"safeACK" heuristic to dynamically switch between Reduction Bounds:
by default conservatively use PRR-CRB and only switch to PRR-SSRB
when ACKs indicate the recovery is making good progress (snd.una is
advancing without detecting any new losses). The SafeACK heuristic
was experimented with in Google's CDN [Flach2016policing] and
implemented in Linux since 2015.
This SafeACK heuristic is only invoked where losses, application-
limited behavior, or other events cause the current estimate of in-
flight data to fall below ssthresh. The high loss rates that make
the heuristic essential are only common in the presence of heavy
Mathis, et al. Expires 13 May 2025 [Page 7]
Internet-Draft Proportional Rate Reduction November 2024
losses such as traffic policers [Flach2016policing]. In these
environments the heuristic serves to salvage a bad situation and any
reasonable implementation of the heuristic performs far better than
either bound by itself.
Another PRR algorithm change improves the sending process when the
sender enters recovery after a large portion of sequence space has
been SACKed. This scenario could happen when the sender has
previously detected reordering, for example, by using [RFC8985]. In
the previous version of PRR, RecoverFS did not properly account for
sequence ranges SACKed before entering fast recovery, which caused
PRR to send too slow initially. With the change, PRR initializes
RecoverFS to "inflight", the data sender's best estimate of the
number of bytes outstanding in the network, for SACK connections.
Yet another change is to force a fast retransmit upon the first ACK
that triggers the recovery. Previously, PRR may not allow a fast
retransmit (i.e. sndcnt is 0) on the first ACK in fast recovery,
depending on the loss situation. Forcing a fast retransmit is
important to maintain the ACK clock and avoid potential RTO events.
The forced fast retransmit only happens once during the entire
recovery and still follows the packet conservation principles in PRR.
This heuristic has been implemented since the first widely deployed
TCP PRR implementation in 2011.
A final change: upon exiting recovery, a data sender SHOULD set cwnd
to ssthresh. This is important for robust performance. Without
setting cwnd to ssthresh at the end of recovery, with application-
limited sender behavior and some loss patterns cwnd could end fast
recovery well below ssthresh, leading to bad performance. The
performance could, in some cases, be worse than [RFC6675] recovery,
which simply sets cwnd = ssthresh at the start of recovery. This
behavior of setting cwnd to ssthresh at the end of recovery has been
implemented since the first widely deployed TCP PRR implementation in
2011, and is similar to [RFC6675], which specifies setting cwnd to
ssthresh at the start of recovery.
Since [RFC6937] was written, PRR has also been adapted to perform
multiplicative window reduction for non-loss based congestion control
algorithms, such as for [RFC3168] style ECN. This can be done by
using some parts of the loss recovery state machine (in particular
the RecoveryPoint from [RFC6675]) to invoke the PRR ACK processing
for exactly one round trip worth of ACKs. However, note that using
PRR for for cwnd reductions for [RFC3168] ECN has been observed, with
some ECN AQMs, to cause an excess cwnd reduction during ECN-triggered
congestion episodes, as noted in [VCC].
Mathis, et al. Expires 13 May 2025 [Page 8]
Internet-Draft Proportional Rate Reduction November 2024
For [RFC6937] we published a companion paper [IMC11] in which we
evaluated [RFC3517] and various experimental PRR versions in a large
scale measurement study. Today, the legacy algorithms used in that
study have already faded from code bases, making such comparisons
impossible without recreating historical algorithms. Readers
interested in the measurement study should review section 5 of RFC
6937 and the IMC paper [IMC11].
4. Relationships to other standards
PRR MAY be used in conjunction with any congestion control algorithm
that intends to make a multiplicative decrease in its sending rate
over approximately the time scale of one round trip time, as long as
the current volume of in-flight data is limited by a congestion
window (cwnd) and the target volume of in-flight data during that
reduction is a fixed value given by ssthresh. In particular, PRR is
applicable to both Reno [RFC5681] and CUBIC [RFC9438] congestion
control. PRR is described as a modification to "A Conservative Loss
Recovery Algorithm Based on Selective Acknowledgment (SACK) for TCP"
[RFC6675]. It is most accurate with SACK [RFC2018] but does not
require SACK.
The SafeACK heuristic came about as a result of robust Lost
Retransmission Detection under development in an early precursor to
[RFC8985]. Without Lost Retransmission Detection, policers that
cause very high loss rates are at very high risk of causing
retransmission timeouts because Reno [RFC5681], CUBIC [RFC9438], and
[RFC6675] can send retransmissions significantly above the policed
rate. It is RECOMMENDED that PRR is implemented together with RACK-
TLP loss recovery [RFC8985].
5. Definitions
The following terms, parameters, and state variables are used as they
are defined in earlier documents:
[RFC9293]: snd.una (send unacknowledged).
[RFC5681]: duplicate ACK, FlightSize, Sender Maximum Segment Size
(SMSS).
[RFC6675]: covered (as in "covered sequence numbers").
PRR defines additional variables and terms:
DeliveredData: The total number of bytes that the current ACK
indicates have been delivered to the receiver. When there are no
SACKed sequence ranges in the scoreboard before or after the ACK,
Mathis, et al. Expires 13 May 2025 [Page 9]
Internet-Draft Proportional Rate Reduction November 2024
DeliveredData is the change in snd.una. With SACK, DeliveredData can
be computed precisely as the change in snd.una, plus the (signed)
change in SACKed. In recovery without SACK, DeliveredData is
estimated to be 1 SMSS on receiving a duplicate acknowledgement, and
on a subsequent partial or full ACK DeliveredData is the change in
snd.una, minus 1 SMSS for each preceding duplicate ACK. Note that
without SACK, a poorly-behaved receiver that returns extraneous
DUPACKs (as described in [Savage99]) could attempt to artificially
inflate DeliveredData. As a mitigation, if not using SACK then PRR
disallows incrementing DeliveredData when the total bytes delivered
in a PRR episode would exceed the estimated data outstanding upon
entering recovery (RecoverFS).
inflight: The data sender's best estimate of the number of bytes
outstanding in the network. To calculate inflight, connections with
SACK enabled and using [RFC6675] loss detection MAY use the "pipe"
algorithm as specified in [RFC6675]. SACK-enabled connections using
RACK-TLP loss detection [RFC8985] or other loss detection algorithms
MUST calculate inflight by starting with SND.NXT - SND.UNA,
subtracting out bytes SACKed in the scoreboard, subtracting out bytes
marked lost in the scoreboard, and adding bytes in the scoreboard
that have been retransmitted since they were last marked lost. For
non-SACK-enabled connections, instead of subtracting out bytes SACKed
in the SACK scoreboard, senders MUST subtract out: min(RecoverFS, 1
SMSS for each preceding duplicate ACK in the fast recovery episode);
the min() with RecoverFS is to protect against misbehaving receivers
[Savage99].
RecoverFS: The "recovery flight size", the number of bytes the sender
estimates are in flight in the network upon entering fast recovery.
PRR uses RecoverFS to compute a smooth sending rate. Upon entering
fast recovery, PRR initializes RecoverFS to "inflight". RecoverFS
remains constant during a given fast recovery episode.
safeACK: A local boolean variable indicating that the current ACK
reported good progress. SafeACK is true only when the ACK has
cumulatively acknowledged new data and the ACK does not indicate
further losses. For example, an ACK triggering RFC6675 "last resort"
retransmission (Section 4, NextSeg() condition 4) may indicate
further losses. Both conditions indicate the recovery is making good
progress and can send more aggressively.
sndcnt: A local variable indicating exactly how many bytes should be
sent in response to each ACK. Note that the decision of which data
to send (e.g., retransmit missing data or send more new data) is out
of scope for this document.
Mathis, et al. Expires 13 May 2025 [Page 10]
Internet-Draft Proportional Rate Reduction November 2024
Voluntary window reductions: choosing not to send data in response to
some ACKs, for the purpose of reducing the sending window size and
data rate.
6. Algorithm
At the beginning of a congestion control response episode initiated
by the congestion control algorithm, a TCP data sender using PRR MUST
initialize the PRR state.
The timing of the start of a congestion control response episode is
entirely up to the congestion control algorithm, and (for example)
could correspond to the start of a fast recovery episode, or a once-
per-round-trip reduction when lost retransmits or lost original
transmissions are detected after fast recovery is already in
progress.
The PRR initialization allows a modern congestion control algorithm,
CongCtrlAlg(), that might set ssthresh to something other than
FlightSize/2 (including, e.g., CUBIC [RFC9438]):
ssthresh = CongCtrlAlg() // Target flight size in recovery
prr_delivered = 0 // Total bytes delivered in recovery
prr_out = 0 // Total bytes sent in recovery
RecoverFS = snd.nxt - snd.una
// Bytes SACKed before entering recovery will not be
// marked as delivered during recovery:
RecoverFS -= (bytes SACKed in scoreboard) - (bytes newly SACKed)
// Include the (rare) case of cumulatively ACKed bytes:
RecoverFS += (bytes newly cumulatively acknowledged)
Mathis, et al. Expires 13 May 2025 [Page 11]
Internet-Draft Proportional Rate Reduction November 2024
On every ACK starting or during fast recovery,
excluding the ACK that concludes a PRR episode:
if (DeliveredData is 0)
Return
prr_delivered += DeliveredData
inflight = (estimated volume of in-flight data)
safeACK = (snd.una advances and no further loss indicated)
if (inflight > ssthresh) {
// Proportional Rate Reduction
sndcnt = CEIL(prr_delivered * ssthresh / RecoverFS) - prr_out
} else {
// PRR-CRB by default
sndcnt = MAX(prr_delivered - prr_out, DeliveredData)
if (safeACK) {
// PRR-SSRB when recovery is in good progress
sndcnt += MSS
}
// Attempt to catch up, as permitted
sndcnt = MIN(ssthresh - inflight, sndcnt)
}
if (prr_out is 0 AND sndcnt is 0) {
// Force a fast retransmit upon entering recovery
sndcnt = MSS
}
cwnd = inflight + sndcnt
On any data transmission or retransmission:
prr_out += (data sent)
A PRR episode ends upon either completing fast recovery, or before
initiating a new PRR episode due to a new congestion control response
episode.
On the completion of a PRR episode:
cwnd = ssthresh
Note that this step that sets cwnd to ssthresh can potentially, in
some scenarios, allow a burst of back-to-back segments into the
network. As with common scenarios that could allow bursts, such as
restarting from idle, it is RECOMMENDED that implementations use
pacing to reduce the burstiness of traffic.
Mathis, et al. Expires 13 May 2025 [Page 12]
Internet-Draft Proportional Rate Reduction November 2024
7. Examples
We illustrate these algorithms by showing their different behaviors
for two scenarios: TCP experiencing either a single loss or a burst
of 15 consecutive losses. In all cases we assume bulk data (no
application pauses), Reno congestion control [RFC5681], and cwnd =
FlightSize = inflight = 20 segments, so ssthresh will be set to 10 at
the beginning of recovery. We also assume standard Fast Retransmit
and Limited Transmit [RFC3042], so TCP will send 2 new segments
followed by 1 retransmit in response to the first 3 duplicate ACKs
following the losses.
Each of the diagrams below shows the per ACK response to the first
round trip for the various recovery algorithms when the zeroth
segment is lost. The top line indicates the transmitted segment
number triggering the ACKs, with an X for the lost segment. "cwnd"
and "infl" indicate the values of cwnd and inflight, respectively,
for these algorithms after processing each returning ACK but before
further (re)transmission. "Sent" indicates how much 'N'ew or
'R'etransmitted data would be sent. Note that the algorithms for
deciding which data to send are out of scope of this document.
RFC 6675
ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
cwnd: 20 20 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
infl: 19 19 18 18 17 16 15 14 13 12 11 10 9 9 9 9 9 9 9 9 9 9
sent: N N R N N N N N N N N N N
PRR
ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
cwnd: 20 20 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 10 10 10
infl: 19 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 10 10 9 9
sent: N N R N N N N N N N N N N
Figure 1
In this first example, ACK#1 through ACK#19 contain SACKs for the
original flight of data, ACK#20 and ACK#21 carry SACKs for the
limited transmits triggered by the first and second SACKed segments,
and ACK#22 carries the full cumulative ACK covering all data up
through the limited transmits. ACK#22 completes the fast recovery
episode, and thus completes the PRR episode.
Mathis, et al. Expires 13 May 2025 [Page 13]
Internet-Draft Proportional Rate Reduction November 2024
Note that both algorithms send the same total amount of data. RFC
6675 experiences a "half window of silence" while PRR spreads the
voluntary window reduction across an entire RTT.
Next, we consider the same initial conditions when the first 15
packets (0-14) are lost. During the remainder of the lossy round
trip, only 5 ACKs are returned to the sender. We examine each of
these algorithms in succession.
RFC 6675
ack# X X X X X X X X X X X X X X X 15 16 17 18 19
cwnd: 20 20 10 10 10
infl: 19 19 4 9 9
sent: N N 6R R R
PRR
ack# X X X X X X X X X X X X X X X 15 16 17 18 19
cwnd: 20 20 5 5 5
infl: 19 19 4 4 4
sent: N N R R R
Figure 2
In this specific situation, RFC 6675 is more aggressive because once
Fast Retransmit is triggered (on the ACK for segment 17), TCP
immediately retransmits sufficient data to bring inflight up to cwnd.
Our earlier measurements [RFC 6937 section 6] indicates that RFC 6675
significantly outperforms PRR, and some other similarly conservative
algorithms that we tested, showing that it is significantly common
for the actual losses to exceed the window reduction determined by
the congestion control algorithm.
Under such heavy losses, PRR uses the PRR-CRB to follow the packet
conservation principle. Since the total losses bring inflight below
ssthresh, data is sent such that the total data transmitted, prr_out,
follows the total data delivered to the receiver as reported by
returning ACKs. Transmission is controlled by the sending limit,
which is set to prr_delivered - prr_out. PRR-CRB conservative window
reduction causes it to take excessively long to recover the losses
and exposes it to additional timeouts.
While not shown in the figure above, once the fast retransmits sent
upon ACK#17 deliver and solicit further ACKs that increment the
snd.una, PRR enters PRR-SSRB and increases the window by exactly 1
segment per ACK until inflight rises to ssthresh during recovery. On
Mathis, et al. Expires 13 May 2025 [Page 14]
Internet-Draft Proportional Rate Reduction November 2024
heavy losses when cwnd is large, PRR-SSRB recovers the losses
exponentially faster than PRR-CRB. Although increasing the window
during recovery seems to be ill advised, it is important to remember
that this is actually less aggressive than permitted by [RFC6675],
which sends the same quantity of additional data as a single burst in
response to the ACK that triggered Fast Retransmit.
For less severe loss events, where the total losses are smaller than
the difference between FlightSize and ssthresh, PRR-CRB and PRR-SSRB
are not invoked since PRR stays in the proportional rate reduction
mode.
8. Properties
The following properties are common to both PRR-CRB and PRR-SSRB,
except as noted:
PRR maintains TCP's ACK clocking across most recovery events,
including burst losses. RFC 6675 can send large unclocked bursts
following burst losses.
Normally, PRR will spread voluntary window reductions out evenly
across a full RTT. This has the potential to generally reduce the
burstiness of Internet traffic, and could be considered to be a type
of soft pacing. Hypothetically, any pacing increases the probability
that different flows are interleaved, reducing the opportunity for
ACK compression and other phenomena that increase traffic burstiness.
However, these effects have not been quantified.
If there are minimal losses, PRR will converge to exactly the target
window chosen by the congestion control algorithm. Note that as TCP
approaches the end of recovery, prr_delivered will approach RecoverFS
and sndcnt will be computed such that prr_out approaches ssthresh.
Implicit window reductions, due to multiple isolated losses during
recovery, cause later voluntary reductions to be skipped. For small
numbers of losses, the window size ends at exactly the window chosen
by the congestion control algorithm.
For burst losses, earlier voluntary window reductions can be undone
by sending extra segments in response to ACKs arriving later during
recovery. Note that as long as some voluntary window reductions are
not undone, and there is no application stall, the final value for
inflight will be the same as ssthresh, the target cwnd value chosen
by the congestion control algorithm.
Mathis, et al. Expires 13 May 2025 [Page 15]
Internet-Draft Proportional Rate Reduction November 2024
PRR with either Reduction Bound improves the situation when there are
application stalls, e.g., when the sending application does not queue
data for transmission quickly enough or the receiver stops advancing
rwnd (receiver window). When there is an application stall early
during recovery, prr_out will fall behind the sum of transmissions
allowed by sndcnt. The missed opportunities to send due to stalls
are treated like banked voluntary window reductions; specifically,
they cause prr_delivered - prr_out to be significantly positive. If
the application catches up while TCP is still in recovery, TCP will
send a partial window burst to catch up to exactly where it would
have been had the application never stalled. Although this burst
might be viewed as being hard on the network, this is exactly what
happens every time there is a partial RTT application stall while not
in recovery. We have made partial RTT stall behavior uniform in all
states. Changing this behavior is out of scope for this document.
PRR with Reduction Bound is less sensitive to errors in the inflight
estimator. While in recovery, inflight is intrinsically an
estimator, using incomplete information to estimate if un-SACKed
segments are actually lost or merely out of order in the network.
Under some conditions, inflight can have significant errors; for
example, inflight is underestimated when a burst of reordered data is
prematurely assumed to be lost and marked for retransmission. If the
transmissions are regulated directly by inflight as they are with RFC
6675, a step discontinuity in the inflight estimator causes a burst
of data, which cannot be retracted once the inflight estimator is
corrected a few ACKs later. For PRR dynamics, inflight merely
determines which algorithm, PRR or the Reduction Bound, is used to
compute sndcnt from DeliveredData. While inflight is underestimated,
the algorithms are different by at most 1 segment per ACK. Once
inflight is updated, they converge to the same final window at the
end of recovery.
Under all conditions and sequences of events during recovery, PRR-CRB
strictly bounds the data transmitted to be equal to or less than the
amount of data delivered to the receiver. We claim that this Strong
Packet Conservation Bound is the most aggressive algorithm that does
not lead to additional forced losses in some environments. It has
the property that if there is a standing queue at a bottleneck with
no cross traffic, the queue will maintain exactly constant length for
the duration of the recovery, except for +1/-1 fluctuation due to
differences in packet arrival and exit times. See Appendix A for a
detailed discussion of this property.
Although the Strong Packet Conservation Bound is very appealing for a
number of reasons, our earlier measurements [RFC 6937 section 6]
demonstrate that it is less aggressive and does not perform as well
as RFC 6675, which permits bursts of data when there are bursts of
Mathis, et al. Expires 13 May 2025 [Page 16]
Internet-Draft Proportional Rate Reduction November 2024
losses. PRR-SSRB is a compromise that permits TCP to send 1 extra
segment per ACK as compared to the Packet Conserving Bound when the
ACK indicates the recovery is in good progress without further
losses. From the perspective of a strict Packet Conserving Bound,
PRR-SSRB does indeed open the window during recovery; however, it is
significantly less aggressive than [RFC6675] in the presence of burst
losses. The [RFC6675] "half window of silence" may temporarily
reduce queue pressure when congestion control does not reduce the
congestion window entering recovery to avoid further losses. The
goal of PRR is to minimize the opportunities to lose the self clock
by accurately controlling flightsize to the target set by the
congestion control. It is the congestion control's responsibility to
avoid a full queue, not PRR.
9. Adapting PRR to other transport protocols
The main PRR algorithm and reductions bounds can be adapted to any
transport that can support RFC 6675. In one major implementation
(Linux TCP), PRR has been the default fast recovery algorithm for its
default and supported congestion control modules.
The safeACK heuristic can be generalized as any ACK of a
retransmission that does not cause some other segment to be marked
for retransmission. That is, PRR_SSRB is safe on any ACK that
reduces the total number of pending and outstanding retransmissions.
10. Acknowledgements
This document is based in part on previous work by Janey C. Hoe (see
section 3.2, "Recovery from Multiple Packet Losses", of
[Hoe96Startup]) and Matt Mathis, Jeff Semke, and Jamshid Mahdavi
[RHID], and influenced by several discussions with John Heffner.
Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the
experiments. Ilpo Jarvinen reviewed the initial implementation.
Mark Allman, Richard Scheffenegger, Markku Kojo, and Mirja Kuehlewind
improved the document through their insightful reviews and
suggestions.
11. IANA Considerations
This memo includes no request to IANA.
12. Security Considerations
PRR does not change the risk profile for TCP.
Mathis, et al. Expires 13 May 2025 [Page 17]
Internet-Draft Proportional Rate Reduction November 2024
Implementers that change PRR from counting bytes to segments have to
be cautious about the effects of ACK splitting attacks [Savage99],
where the receiver acknowledges partial segments for the purpose of
confusing the sender's congestion accounting.
13. Normative References
[RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP
Selective Acknowledgment Options", RFC 2018,
DOI 10.17487/RFC2018, October 1996,
<https://www.rfc-editor.org/info/rfc2018>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion
Control", RFC 5681, DOI 10.17487/RFC5681, September 2009,
<https://www.rfc-editor.org/info/rfc5681>.
[RFC6675] Blanton, E., Allman, M., Wang, L., Jarvinen, I., Kojo, M.,
and Y. Nishida, "A Conservative Loss Recovery Algorithm
Based on Selective Acknowledgment (SACK) for TCP",
RFC 6675, DOI 10.17487/RFC6675, August 2012,
<https://www.rfc-editor.org/info/rfc6675>.
[RFC8985] Cheng, Y., Cardwell, N., Dukkipati, N., and P. Jha, "The
RACK-TLP Loss Detection Algorithm for TCP", RFC 8985,
DOI 10.17487/RFC8985, February 2021,
<https://www.rfc-editor.org/info/rfc8985>.
[RFC9293] Eddy, W., Ed., "Transmission Control Protocol (TCP)",
STD 7, RFC 9293, DOI 10.17487/RFC9293, August 2022,
<https://www.rfc-editor.org/info/rfc9293>.
[RFC9438] Xu, L., Ha, S., Rhee, I., Goel, V., and L. Eggert, Ed.,
"CUBIC for Fast and Long-Distance Networks", RFC 9438,
DOI 10.17487/RFC9438, August 2023,
<https://www.rfc-editor.org/info/rfc9438>.
14. Informative References
[Flach2016policing]
Flach, T., Papageorge, P., Terzis, A., Pedrosa, L., Cheng,
Y., Al Karim, T., Katz-Bassett, E., and R. Govindan, "An
Internet-Wide Analysis of Traffic Policing", ACM
SIGCOMM SIGCOMM2016, August 2016.
Mathis, et al. Expires 13 May 2025 [Page 18]
Internet-Draft Proportional Rate Reduction November 2024
[Hoe96Startup]
Hoe, J., "Improving the start-up behavior of a congestion
control scheme for TCP", ACM SIGCOMM SIGCOMM1996, August
1996.
[IMC11] Dukkipati, N., Mathis, M., Cheng, Y., and M. Ghobadi,
"Proportional Rate Reduction for TCP", Proceedings of the
11th ACM SIGCOMM Conference on Internet Measurement
2011, Berlin, Germany, November 2011.
[Jacobson88]
Jacobson, V., "Congestion Avoidance and Control", SIGCOMM
Comput. Commun. Rev. 18(4), August 1988.
[RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing
TCP's Loss Recovery Using Limited Transmit", RFC 3042,
DOI 10.17487/RFC3042, January 2001,
<https://www.rfc-editor.org/info/rfc3042>.
[RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
of Explicit Congestion Notification (ECN) to IP",
RFC 3168, DOI 10.17487/RFC3168, September 2001,
<https://www.rfc-editor.org/info/rfc3168>.
[RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A
Conservative Selective Acknowledgment (SACK)-based Loss
Recovery Algorithm for TCP", RFC 3517,
DOI 10.17487/RFC3517, April 2003,
<https://www.rfc-editor.org/info/rfc3517>.
[RFC6937] Mathis, M., Dukkipati, N., and Y. Cheng, "Proportional
Rate Reduction for TCP", RFC 6937, DOI 10.17487/RFC6937,
May 2013, <https://www.rfc-editor.org/info/rfc6937>.
[RHID] Mathis, M., Semke, J., and J. Mahdavi, "The Rate-Halving
Algorithm for TCP Congestion Control", Work in Progress,
August 1999, <https://datatracker.ietf.org/doc/html/draft-
mathis-tcp-ratehalving>.
[Savage99] Savage, S., Cardwell, N., Wetherall, D., and T. Anderson,
"TCP congestion control with a misbehaving receiver",
SIGCOMM Comput. Commun. Rev. 29(5), October 1999.
[VCC] Cronkite-Ratcliff, B., Bergman, A., Vargaftik, S., Ravi,
M., McKeown, N., Abraham, I., and I. Keslassy,
"Virtualized Congestion Control (Extended Version)",
August 2016, <http://www.ee.technion.ac.il/~isaac/p/
sigcomm16_vcc_extended.pdf>.
Mathis, et al. Expires 13 May 2025 [Page 19]
Internet-Draft Proportional Rate Reduction November 2024
Appendix A. Strong Packet Conservation Bound
PRR-CRB is based on a conservative, philosophically pure, and
aesthetically appealing Strong Packet Conservation Bound, described
here. Although inspired by the packet conservation principle
[Jacobson88], it differs in how it treats segments that are missing
and presumed lost. Under all conditions and sequences of events
during recovery, PRR-CRB strictly bounds the data transmitted to be
equal to or less than the amount of data delivered to the receiver.
Note that the effects of presumed losses are included in the inflight
calculation, but do not affect the outcome of PRR-CRB, once inflight
has fallen below ssthresh.
We claim that this Strong Packet Conservation Bound is the most
aggressive algorithm that does not lead to additional forced losses
in some environments. It has the property that if there is a
standing queue at a bottleneck that is carrying no other traffic, the
queue will maintain exactly constant length for the entire duration
of the recovery, except for +1/-1 fluctuation due to differences in
packet arrival and exit times. Any less aggressive algorithm will
result in a declining queue at the bottleneck. Any more aggressive
algorithm will result in an increasing queue or additional losses if
it is a full drop tail queue.
We demonstrate this property with a little thought experiment:
Imagine a network path that has insignificant delays in both
directions, except for the processing time and queue at a single
bottleneck in the forward path. By insignificant delay, we mean when
a packet is "served" at the head of the bottleneck queue, the
following events happen in much less than one bottleneck packet time:
the packet arrives at the receiver; the receiver sends an ACK that
arrives at the sender; the sender processes the ACK and sends some
data; the data is queued at the bottleneck.
If sndcnt is set to DeliveredData and nothing else is inhibiting
sending data, then clearly the data arriving at the bottleneck queue
will exactly replace the data that was served at the head of the
queue, so the queue will have a constant length. If queue is drop
tail and full, then the queue will stay exactly full. Losses or
reordering on the ACK path only cause wider fluctuations in the queue
size, but do not raise its peak size, independent of whether the data
is in order or out of order (including loss recovery from an earlier
RTT). Any more aggressive algorithm that sends additional data will
overflow the drop tail queue and cause loss. Any less aggressive
algorithm will under-fill the queue. Therefore, setting sndcnt to
DeliveredData is the most aggressive algorithm that does not cause
forced losses in this simple network. Relaxing the assumptions
Mathis, et al. Expires 13 May 2025 [Page 20]
Internet-Draft Proportional Rate Reduction November 2024
(e.g., making delays more authentic and adding more flows, delayed
ACKs, etc.) is likely to increase the fine grained fluctuations in
queue size but does not change its basic behavior.
Note that the congestion control algorithm implements a broader
notion of optimal that includes appropriately sharing the network.
Typical congestion control algorithms are likely to reduce the data
sent relative to the Packet Conserving Bound implemented by PRR,
bringing TCP's actual window down to ssthresh.
Authors' Addresses
Matt Mathis
Email: ietf@mattmathis.net
Nandita Dukkipati
Google, Inc.
Email: nanditad@google.com
Yuchung Cheng
Google, Inc.
Email: ycheng@google.com
Neal Cardwell
Google, Inc.
Email: ncardwell@google.com
Mathis, et al. Expires 13 May 2025 [Page 21]