RFC 6937
Proportional Rate Reduction for TCP
Proportional Rate Reduction for TCP 🎀
RFC 6937 · Category: Experimental · ISSN 2070-1721 · May 2013 ✨
Authors: M. Mathis, N. Dukkipati, and Y. Cheng, all from Google, Inc. 💅
The header doesn't list any RFCs this one obsoletes or updates. 🦋
Abstract 🌸
Okay so this doc introduces an experimental Proportional Rate Reduction (PRR) algorithm 🔥 that's meant to be a glow-up for the Fast Recovery and Rate-Halving algorithms, which are already everywhere. These algorithms decide how much data TCP is allowed to send while it's recovering from loss. PRR cuts down on the extra window adjustments, so by the end of recovery the actual window size lands as close as possible to the ssthresh set by the congestion control algorithm. It's giving precision 💖
Status of This Memo 📝
This document is not an Internet Standards Track specification. It's published so people can look at it, try implementing it experimentally, and evaluate it. 🧪
It does define an Experimental Protocol for the Internet community. It's a product of the Internet Engineering Task Force (IETF) and reflects the consensus of the IETF community. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). Not every IESG-approved doc is a candidate for any level of Internet Standard, so check Section 2 of RFC 5741 for the details. 🫶
For the current status, any errata, and how to send feedback, go to http://www.rfc-editor.org/info/rfc6937. 🌈
Copyright Notice ©️
Copyright (c) 2013 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, which you can find at http://trustee.ietf.org/license-info. Those provisions are the ones in effect on the date this document was published. Please read them carefully, because they spell out your rights and restrictions for this document. Any Code Components pulled out of this document must include the Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as described in the Simplified BSD License. 💅
Table of Contents 🗂️
1. Introduction ....................................................2
2. Definitions .....................................................5
3. Algorithms ......................................................6
3.1. Examples ...................................................6
4. Properties ......................................................9
5. Measurements ...................................................11
6. Conclusion and Recommendations .................................12
7. Acknowledgements ...............................................13
8. Security Considerations ........................................13
9. References .....................................................13
9.1. Normative References ......................................13
9.2. Informative References ....................................14
Appendix A. Strong Packet Conservation Bound ......................151. Introduction 🌷
Okay, so this doc describes an experimental algorithm, PRR, that makes the amount of data TCP sends during loss recovery way more accurate. ✨
Standard congestion control [RFC5681] says TCP (and other protocols) have to shrink their congestion window (cwnd) when losses happen. Fast Recovery, which is described in that same document, is the reference algorithm for doing this. Its whole goal is to keep TCP's self-clock alive by using the ACKs that come back during recovery to clock more data into the network. The catch is that Fast Recovery usually adjusts the window by waiting for half a round-trip time (RTT) worth of ACKs before it sends anything. It's kind of fragile, because it can't make up for the implicit window reduction that the losses themselves already caused. 😭
RFC 6675 [RFC6675] makes Fast Recovery with Selective Acknowledgement (SACK) [RFC2018] way more accurate by computing "pipe", which is the sender's estimate of how many bytes are still outstanding in the network. With RFC 6675, Fast Recovery sends data as needed on each ACK so that pipe never drops below ssthresh, the window size set by the congestion control algorithm. This protects Fast Recovery from timeouts in lots of heavy-loss cases, though not if the entire second half of the window of data or ACKs gets lost. Still, one ACK carrying a SACK option that implies a big chunk of missing data can cause a step discontinuity in the pipe estimator, and that can make Fast Retransmit send a burst of data. Yikes 💀
Rate-Halving sends data on alternate ACKs during recovery, so that after 1 RTT the window has been halved. It's implemented in Linux even though it was only informally published [RHweb], including an uncompleted document [RHID]. It also doesn't adequately make up for the implicit window reduction caused by the losses, and it assumes a net 50% window reduction. That was totally standard when it was written, but it's not a great fit for modern congestion control algorithms like CUBIC [CUBIC], which reduce the window by less than 50%. As a result, Rate-Halving often lets the window fall further than it needs to, which hurts performance and raises the risk of timeouts if more losses show up. 🙈
PRR avoids these excess window adjustments, so that at the end of recovery the actual window size is as close as possible to ssthresh, the window size set by the congestion control algorithm. It's patterned after Rate-Halving, but it uses the fraction that matches the target window the congestion control algorithm picked. During PRR, one of two extra Reduction Bound algorithms limits the total window reduction from every mechanism, including transient application stalls and the losses themselves. 🦋
Two slightly different Reduction Bound algorithms are described: Conservative Reduction Bound (CRB), which is strictly packet conserving, and 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. In real networks, though, it doesn't perform as well as the algorithms in RFC 6675, which turn out to be more aggressive in a lot of cases. SSRB is the compromise: it lets TCP send 1 additional segment per ACK compared to CRB in some situations. It's less aggressive than RFC 6675 (it sends fewer segments or takes longer to send them), yet it still outperforms it, thanks to the lower chance of more losses during recovery. 🔥
The Strong Packet Conservation Bound that PRR and both Reduction Bounds are based on 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. PRR and the Reduction Bound algorithms lean on this self-clock as much as possible, and they're only slightly affected by how accurate other estimators, like pipe [RFC6675] and cwnd, happen to be. That's what gives them their precision when events make the other estimators uncertain. 💖
The original packet conservation principle [Jacobson88] treated packets that are presumed lost (for example, packets marked as candidates for retransmission) as having already left the network. That idea shows up in the pipe estimator defined in RFC 6675 and used here. It's different from the Strong Packet Conservation Bound in Appendix A, though, which is defined only on the basis of data arriving at the receiver. 🧠
The algorithms were evaluated in a large-scale measurement study presented in a companion paper [IMC11] and summarized in Section 5. That study was based on RFC 3517 [RFC3517], which has since been superseded by RFC 6675. Because the two specs differ slightly, and because the authors were very meticulous about their RFC 3517 implementation, they aren't comfortable saying outright that the measurement results apply to RFC 6675. They do believe it's the case, though. So they chose to be pedantic and describe the results relative to RFC 3517, which is what they were actually based on. General discussions of the algorithms and their properties have been updated to refer to RFC 6675. 🤓
For authentic network traffic, PRR-SSRB outperforms both RFC 3517 and Linux Rate-Halving, even though it's less aggressive than RFC 3517. The authors believe these results apply to RFC 6675 as well. 👑
The algorithms are described as modifications to "TCP Congestion Control" in RFC 5681 [RFC5681], using concepts drawn from the pipe algorithm [RFC6675]. They're most accurate and easiest to implement with SACK [RFC2018], but they don't require SACK. 🌸
2. Definitions 📚
These terms, parameters, and state variables are used exactly as they're defined in earlier documents:
- RFC 793:
snd.una(send unacknowledged) - RFC 5681: duplicate ACK,
FlightSize, Sender Maximum Segment Size (SMSS) - RFC 6675: covered (as in "covered sequence numbers")
- 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
Then there are a few extra variables we define ourselves, bestie:
SACKd: the total number of bytes the scoreboard says have been delivered to the receiver. You can compute it by scanning the scoreboard and counting the total bytes covered by all SACK blocks. If SACK isn't in use,SACKdisn't defined.DeliveredData: the total number of bytes the current ACK says have been delivered to the receiver. When you're not in recovery,DeliveredDatais the change insnd.una. With SACK,DeliveredDatacan be computed precisely as the change insnd.unaplus the (signed) change inSACKd. In recovery without SACK,DeliveredDatais estimated to be 1SMSSon each duplicate acknowledgement. On a later partial or full ACK, it's estimated to be the change insnd.una, minus 1SMSSfor each preceding duplicate ACK.
DeliveredData is robust, which is honestly iconic 🙌 For TCP using SACK, DeliveredData can be computed precisely anywhere in the network just by inspecting the returning ACKs. If ACKs go missing, later ACKs will just show a larger DeliveredData. And for any TCP (with or without SACK), the sum of DeliveredData has to match the forward progress over the same time interval. ✨
We introduce a local variable called sndcnt, which says exactly how many bytes should be sent in response to each ACK. Quick note: deciding which data to send (like retransmitting missing data or sending more new data) is out of scope for this document. That's a different conversation, bestie 💅
3. Algorithms ✨
okay bestie, this is the part where PRR actually gets cooking 🍳 At the start of recovery you set up your PRR state. The algorithm is written so it works with a modern congestion control algorithm, CongCtrlAlg(), which might set ssthresh to something other than FlightSize/2 👀
ssthresh = CongCtrlAlg() // Target cwnd after recovery
prr_delivered = 0 // Total bytes delivered during recovery
prr_out = 0 // Total bytes sent during recovery
RecoverFS = snd.nxt-snd.una // FlightSize at the start of recoveryThen, on every ACK during recovery, you work out how much data got delivered, add that to prr_delivered, and compute pipe with the RFC 6675 pipe algorithm. If pipe is bigger than ssthresh, you use Proportional Rate Reduction to spread the window reduction out 💅 If it isn't, you use one of two versions of the Reduction Bound (PRR-CRB or PRR-SSRB) to catch up, but only as far as the limit lets you. Here's the whole vibe in one block:
On every ACK during recovery compute:
DeliveredData = change_in(snd.una) + change_in(SACKd)
prr_delivered += DeliveredData
pipe = (RFC 6675 pipe algorithm)
if (pipe > ssthresh) {
// Proportional Rate Reduction
sndcnt = CEIL(prr_delivered * ssthresh / RecoverFS) - prr_out
} else {
// Two versions of the Reduction Bound
if (conservative) { // PRR-CRB
limit = prr_delivered - prr_out
} else { // PRR-SSRB
limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS
}
// Attempt to catch up, as permitted by limit
sndcnt = MIN(ssthresh - pipe, limit)
}
On any data transmission or retransmission:
prr_out += (data sent) // strictly less than or equal to sndcntEvery time you send data or retransmit, you add it to prr_out, and that amount has to be strictly less than or equal to sndcnt 🫶
3.1. Examples
okay now the fun part, the examples 🦋 We show how these algorithms behave in two scenarios: TCP taking a single loss, or a burst of 15 consecutive losses. In every case we're assuming bulk data (no application pauses), standard Additive Increase Multiplicative Decrease (AIMD) congestion control, and cwnd = FlightSize = pipe = 20 segments. That means ssthresh gets set to 10 at the start of recovery. We also assume standard Fast Retransmit and Limited Transmit [RFC3042], so TCP sends 2 new segments followed by 1 retransmit in response to the first 3 duplicate ACKs after the losses. iconic behaviour 🌸
Each diagram below shows the per-ACK response during the first round trip for the different recovery algorithms, when the zeroth segment is lost. The top line is the transmitted segment number that triggered the ACKs, with an X for the lost segment. "cwnd" and "pipe" show the values of these algorithms after each returning ACK processes. "Sent" tells you how much 'N'ew or 'R'etransmitted data would be sent. Heads up: the algorithms that decide which data to send are out of scope for this document 🙈
When there's a single loss, PRR with either Reduction Bound algorithm behaves the same way. We show "RB", a flag that tells you which Reduction Bound subexpression ended up determining the value of sndcnt. With minimal losses, "limit" (for both algorithms) will always be bigger than ssthresh - pipe, so sndcnt will be ssthresh - pipe, which is marked with "s" in the "RB" row ✨
RFC 6675
ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
cwnd: 20 20 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
pipe: 19 19 18 18 17 16 15 14 13 12 11 10 10 10 10 10 10 10 10
sent: N N R N N N N N N N N
Rate-Halving (Linux)
ack# X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
cwnd: 20 20 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11
pipe: 19 19 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 11 10
sent: N N R 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
pipe: 19 19 18 18 18 17 17 16 16 15 15 14 14 13 13 12 12 11 10
sent: N N R N N N N N N N N
RB: s s
Cwnd is not shown because PRR does not use it.
Key for RB
s: sndcnt = ssthresh - pipe // from ssthresh
b: sndcnt = prr_delivered - prr_out + SMSS // from banked
d: sndcnt = DeliveredData + SMSS // from DeliveredData
(Sometimes, more than one applies.)All 3 algorithms send the same total amount of data, which is the main takeaway here 🍓 RFC 6675 gets a "half window of silence", while Rate-Halving and PRR spread the voluntary window reduction across an entire RTT. Rude to RFC 6675, honestly, but it's valid 😭
Next up, same starting conditions, except now the first 15 packets (0-14) are lost. During the rest of that lossy RTT, only 5 ACKs make it back to the sender. We'll look at each algorithm one at a time 🧚
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 11 11 11
pipe: 19 19 4 10 10
sent: N N 7R R R
Rate-Halving (Linux)
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
pipe: 19 19 4 4 4
sent: N N R R R
PRR-CRB
ack# X X X X X X X X X X X X X X X 15 16 17 18 19
pipe: 19 19 4 4 4
sent: N N R R R
RB: b b b
PRR-SSRB
ack# X X X X X X X X X X X X X X X 15 16 17 18 19
pipe: 19 19 4 5 6
sent: N N 2R 2R 2R
RB: bd d dIn this specific situation, RFC 6675 is more aggressive. Once Fast Retransmit fires (on the ACK for segment 17), TCP immediately retransmits enough data to bring pipe up to cwnd. Our measurement data (see Section 5) shows RFC 6675 significantly outperforms Rate-Halving, PRR-CRB, and some other similarly conservative algorithms we tested. It turns out it's pretty common for the actual losses to exceed the window reduction the congestion control algorithm decided on 📉
The Linux implementation of Rate-Halving includes an early version of the Conservative Reduction Bound [RHweb]. In this situation, the 5 ACKs each trigger exactly 1 transmission (2 new data, 3 old data), and cwnd gets set to 5. At a window size of 5, it takes 3 round trips to retransmit all 15 lost segments 😩 Rate-Halving doesn't raise the window at all during recovery, so once recovery finally completes, TCP slow starts cwnd from 5 up to 10. So TCP runs at half the window the congestion control picked for more than 3 RTTs, which means more elapsed time and more exposure to timeouts if there are extra losses. not it 💀
PRR-CRB implements a Conservative Reduction Bound. Since the total losses push pipe below ssthresh, data is sent so 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. That's what the RB:b tagging in the figure shows. In this case, PRR-CRB runs into exactly the same problems as Rate-Halving: the extra window reduction makes it take excessively long to recover the losses, and that exposes it to additional timeouts 😵💫
PRR-SSRB increases the window by exactly 1 segment per ACK until pipe rises to ssthresh during recovery. It does this by setting limit to one greater than the data reported as delivered to the receiver on that ACK. That's slow start during recovery, marked with RB:d in the figure 🚀 Increasing the window during recovery might look ill advised, but remember this is actually less aggressive than what RFC 5681 permits. RFC 5681 sends the same quantity of additional data as a single burst in response to the ACK that triggered Fast Retransmit, so PRR-SSRB is the gentler option 🫶
For less extreme events, where the total losses are smaller than the difference between FlightSize and ssthresh, PRR-CRB and PRR-SSRB have identical behaviours. Literally the same energy 💖
4. Properties ✨
okay bestie, these are the properties that PRR-CRB and PRR-SSRB both have, except where I note otherwise 💅🎀
PRR keeps TCP's ACK clocking going across most recovery events, including burst losses 🦋 RFC 6675 can send big unclocked bursts after burst losses, and that's not it 😭
Normally PRR spreads voluntary window reductions out evenly across a full RTT 🌸 This can generally make Internet traffic less bursty, so it's kinda like a soft form of pacing 🫶 Hypothetically, any pacing makes it more likely that different flows get interleaved, which means fewer chances for ACK compression and other stuff that makes traffic burstier 🧚 But these effects have not been quantified yet.
If there are minimal losses, PRR converges to exactly the target window that the congestion control algorithm picked 🎯 As TCP gets close to the end of recovery, prr_delivered approaches RecoverFS, and sndcnt gets computed so that prr_out approaches ssthresh ✨
Implicit window reductions from multiple isolated losses during recovery make later voluntary reductions get skipped 🙈 For small numbers of losses, the window size ends at exactly the window the congestion control algorithm chose 💖
For burst losses, earlier voluntary window reductions can get undone by sending extra segments in response to ACKs that arrive later during recovery 🔄 As long as some voluntary window reductions are not undone, the final value for pipe will be the same as ssthresh, which is the target cwnd value the congestion control algorithm chose 👑
PRR with either Reduction Bound makes application stalls better 🙌 That's when the sending application doesn't queue data for transmission fast enough, or when the receiver stops advancing rwnd (receiver window). If there's an application stall early during recovery, prr_out falls behind the sum of the transmissions permitted by sndcnt 😬 Those missed chances to send because of stalls get treated like banked voluntary window reductions. Specifically, they make prr_delivered - prr_out significantly positive 📈 If the application catches up while TCP is still in recovery, TCP sends a partial window burst to catch up to exactly where it would have been if the application had never stalled 🏃♀️ This burst might look hard on the network, but it's exactly what happens every time there's a partial RTT application stall while not in recovery. We made the partial RTT stall behavior uniform in all states 💅 Changing this behavior is out of scope for this document.
PRR with Reduction Bound is also less sensitive to errors in the pipe estimator 🧠 While in recovery, pipe is basically an estimator, using incomplete info to guess whether un-SACKed segments are actually lost or just out of order in the network 🤔 Under some conditions pipe can be really off. For example, pipe is underestimated when a burst of reordered data is prematurely assumed to be lost and marked for retransmission 😵 If transmissions are regulated directly by pipe like they are with RFC 6675, a step discontinuity in the pipe estimator causes a burst of data that can't be taken back once the pipe estimator gets corrected a few ACKs later 💀 For PRR, pipe only decides which algorithm, PRR or the Reduction Bound, gets used to compute sndcnt from DeliveredData ✨ While pipe is underestimated, the algorithms differ by at most 1 segment per ACK. Once pipe 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 this Strong Packet Conservation Bound is the most aggressive algorithm that doesn't lead to additional forced losses in some environments 👑 It has the property that if there's a standing queue at a bottleneck with no cross traffic, the queue stays at exactly constant length for the whole recovery, except for +1/-1 fluctuation from 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 bunch of reasons, our measurements summarized in Section 5 show it's less aggressive and doesn't perform as well as RFC 6675, which permits bursts of data when there are bursts of losses 😤 PRR-SSRB is a compromise that lets TCP send 1 extra segment per ACK compared to the Packet Conserving Bound 🫶 From the perspective of a strict Packet Conserving Bound, PRR-SSRB does open the window during recovery. But it's significantly less aggressive than RFC 6675 when there are burst losses 🌸
5. Measurements
Okay so in a companion IMC11 paper [IMC11], we describe some measurements comparing the different strategies for reducing the window during recovery 📊 The experiments ran on servers carrying Google production traffic, and here's the brief version 🙌
The various window reduction algorithms and extensive instrumentation were all implemented in Linux 2.6 🐧 We used the uniform set of algorithms in the base Linux implementation, including CUBIC [CUBIC], Limited Transmit [RFC3042], threshold transmit (Section 3.1 in [FACK]) (this algorithm wasn't in RFC 3517, but a similar one got added to RFC 6675), and lost retransmission detection algorithms 🎀 We confirmed that the behaviors of Rate-Halving (the Linux default), RFC 3517, and PRR were authentic to their respective specifications, and that performance and features were comparable to the kernels in production use ✅ All the different window reduction algorithms were present in a common kernel and could be selected with a sysctl, so we had an absolutely uniform baseline for comparing them 🧚
Our experiments also included an extra algorithm, PRR with an unlimited bound (PRR-UB), which sends ssthresh-pipe bursts when pipe falls below ssthresh 💥 This behavior parallels RFC 3517.
An important detail of this configuration is that CUBIC only reduces the window by 30%, instead of the 50% reduction used by traditional congestion control algorithms 🫣 This makes RFC 3517 and PRR-UB more likely to send a burst right when Fast Retransmit gets triggered, because pipe is likely already below ssthresh 😬 Exactly this condition was observed for 32% of the recovery events: pipe fell below ssthresh before Fast Retransmit was triggered, so the various PRR algorithms started in the Reduction Bound phase, and RFC 3517 sent bursts of segments with the Fast Retransmit 💀
In the companion paper, we observe that PRR-SSRB spends the least time in recovery of all the algorithms tested, mostly because it experiences fewer timeouts once it's already in recovery 🏆
RFC 3517 experiences 29% more detected lost retransmissions and 2.6% more timeouts (presumably due to undetected lost retransmissions) than PRR-SSRB 📉 These results are representative of PRR-UB and other algorithms that send bursts when pipe falls below ssthresh 🌪️
Rate-Halving experiences 5% more timeouts and significantly smaller final cwnd values at the end of recovery 😭 The smaller cwnd sometimes makes the recovery itself take extra round trips 🐌 These results are representative of PRR-CRB and other algorithms that implement strict packet conservation during recovery 🫠
6. Conclusion and Recommendations
Although the Strong Packet Conservation Bound used in PRR-CRB is very appealing for a bunch of reasons, our measurements show it's less aggressive and doesn't perform as well as RFC 3517 (and by implication RFC 6675), which permits bursts of data when there are bursts of losses 🥺 RFC 3517 and RFC 6675 are conservative in the original sense of Van Jacobson's packet conservation principle, which assumed that presumed lost segments have actually left the network 🧠 PRR-CRB makes no such assumption. Instead it follows a Strong Packet Conservation Bound, in which only packets that have actually arrived at the receiver are considered to have left the network 📦 PRR-SSRB is a compromise that lets TCP send 1 extra segment per ACK relative to the Strong Packet Conservation Bound, to partially make up for excess losses 🫶
From the perspective of the Strong Packet Conservation Bound, PRR-SSRB does open the window during recovery. However, it's significantly less aggressive than RFC 3517 (and RFC 6675) when there are burst losses 🌸 Even so, it often outperforms RFC 3517 (and presumably RFC 6675) because it avoids some of the self-inflicted losses caused by bursts 💅✨
At this point, we see no reason not to test and deploy PRR-SSRB on a large scale 🚀 Implementers worried about any potential impact of raising the window during recovery may want to optionally support PRR-CRB (which is actually simpler to implement) for comparison studies 🔍 There's also one minor detail of PRR that can be improved by replacing pipe with total_pipe, as defined by Laminar TCP [Laminar] 🧚
One final comment about terminology: we expect common usage to drop "Slow Start Reduction Bound" from the algorithm name 🏷️ This document needed to be pedantic about having distinct names for PRR and every variant of the Reduction Bound. However, we don't anticipate any future exploration of the alternative Reduction Bounds 🙈
7. Acknowledgements
This document is based in part on previous incomplete work by Matt Mathis, Jeff Semke, and Jamshid Mahdavi [RHID], and it was influenced by several discussions with John Heffner 🫶
Monia Ghobadi and Sivasankar Radhakrishnan helped analyze the experiments 🙌
Ilpo Jarvinen reviewed the code 💻
Mark Allman improved the document through his insightful review 👑
8. Security Considerations
PRR does not change the risk profile for TCP 🛡️
Implementers that change PRR from counting bytes to counting segments have to be cautious about the effects of ACK splitting attacks [Savage99] ⚠️ In these, the receiver acknowledges partial segments to confuse the sender's congestion accounting 😱
Heads up: ACK splitting attacks can confuse the sender's congestion accounting, so if you switch PRR from bytes to segments, be careful 🚨
9. References
9.1. Normative References
[RFC0793] Postel, J., "Transmission Control Protocol", STD 7,
RFC 793, September 1981.
[RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP
Selective Acknowledgment Options", RFC 2018, October
1996.
[RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion
Control", RFC 5681, September 2009.
[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, August 2012.9.2. Informative References ✨
okay bestie, here are all the informative refs, the extra reading list for people who wanna go deeper 📚💖
- [RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing TCP's Loss Recovery Using Limited Transmit", RFC 3042, January 2001. This one is all about helping TCP recover from losses with Limited Transmit 🦋
- [RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A Conservative Selective Acknowledgment (SACK)-based Loss Recovery Algorithm for TCP", RFC 3517, April 2003. The SACK-based recovery algorithm, so iconic 👑
- [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. The paper that started it all for PRR 🎀
- [FACK] Mathis, M. and J. Mahdavi, "Forward Acknowledgment: Refining TCP Congestion Control", ACM SIGCOMM SIGCOMM96, August 1996. FACK, the OG forward ACK vibes 🌸
- [RHID] Mathis, M., Semke, J., and J. Mahdavi, "The Rate-Halving Algorithm for TCP Congestion Control", Work in Progress, August 1999. A draft, but a cute one 🧚
- [RHweb] Mathis, M. and J. Mahdavi, "TCP Rate-Halving with Bounding Parameters", Web publication, December 1997, <http://www.psc.edu/networking/papers/FACKnotes/current/>. The web notes, lowkey a hidden gem 💜
- [CUBIC] Rhee, I. and L. Xu, "CUBIC: A new TCP-friendly high-speed TCP variant", PFLDnet 2005, February 2005. CUBIC is giving high-speed, TCP-friendly energy 🚀
- [Jacobson88] Jacobson, V., "Congestion Avoidance and Control", SIGCOMM Comput. Commun. Rev. 18(4), August 1988. The legendary Jacobson paper, no cap 🫶
- [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. Ngl this one is about receivers that don't play fair 💀
- [Laminar] Mathis, M., "Laminar TCP and the case for refactoring TCP congestion control", Work in Progress, July 2012. A work-in-progress idea about refactoring congestion control 🌈
Appendix A. Strong Packet Conservation Bound ✨
okay so PRR-CRB is based on a conservative, philosophically pure, and aesthetically appealing Strong Packet Conservation Bound 💅 it's inspired by Van Jacobson's packet conservation principle [Jacobson88], but it treats segments that are missing and presumed lost differently 🦋 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 🔥 the presumed losses do get included in the pipe calculation, but they don't change the outcome of PRR-CRB once pipe has fallen below ssthresh 🫶
we claim this Strong Packet Conservation Bound is the most aggressive algorithm that doesn't lead to additional forced losses in some environments 👑 it has this really cute property: if there's a standing queue at a bottleneck carrying no other traffic, the queue stays exactly constant length for the entire recovery, except for +1/-1 fluctuation from differences in packet arrival and exit times 🌸 any less aggressive algorithm makes a declining queue at the bottleneck 📉 any more aggressive algorithm makes an increasing queue, or extra losses if it's a full drop tail queue 💀
we demonstrate this with a little thought experiment 🧚
imagine a network path with 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 that 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 the data arriving at the bottleneck queue will exactly replace the data that was served at the head of the queue, so the queue has a constant length 🍓 if the queue is drop tail and full, it stays exactly full 🔥 losses or reordering on the ACK path only cause wider fluctuations in the queue size, but don't raise its peak size, 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 (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 it doesn't 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 Google, Inc. 1600 Amphitheatre Parkway Mountain View, California 94043 USA
EMail: mattmathis@google.com
Nandita Dukkipati Google, Inc. 1600 Amphitheatre Parkway Mountain View, California 94043 USA
EMail: nanditad@google.com
Yuchung Cheng Google, Inc. 1600 Amphitheatre Parkway Mountain View, California 94043 USA
EMail: ycheng@google.com
📦 where this page comes from
- ietf: rfc6937 2013-05
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms