RFC 2861

TCP Congestion Window Validation

📅 published June 2000, from ietf

Network Working Group, RFC 2861 🎀

  • RFC number and title: RFC 2861, TCP Congestion Window Validation
  • Authors: M. Handley, J. Padhye, and S. Floyd, all from ACIRI
  • Category: Experimental
  • Date: June 2000
  • Obsoletes and updates: the header doesn't list any RFCs this one obsoletes or updates

Status of this Memo 📋

This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited.

Copyright (C) The Internet Society (2000). All Rights Reserved.

Abstract ✨

okay so TCP's congestion window is basically the number of packets a TCP flow is allowed to have floating around in the network at any moment 🌊 but here's the tea: if the sender goes quiet for a long time, or is just application-limited (meaning the app isn't giving it enough data to fill the window), the congestion window can become invalid. it stops matching what's actually happening on the network, and that's giving stale 🙈

this doc proposes a simple tweak to TCP's congestion control: after a sufficiently long application-limited period, decay cwnd, and use ssthresh as a little memory of what cwnd used to be 🧠

there's another glow-up too. cwnd can also get inflated during application-limited periods (in slow-start or congestion avoidance) even though the old value was never fully used. so the proposal is that the sender should not increase cwnd while it's application-limited, since it hasn't actually used the current window 💅

the authors tested these ideas with simulations and with experiments from an implementation in FreeBSD 🧚

1. Conventions and Acronyms 📖

The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear in this document, are to be interpreted as described in [B97].

2. Introduction 🌸

okay let's start with the basics bestie 💖 TCP's congestion window controls how many packets a TCP flow can have in the network at any time. it's set using an Additive-Increase, Multiplicative-Decrease (AIMD) mechanism, which probes for available bandwidth and adapts when network conditions change 🦋 AIMD works really well when the sender always has data to send, which is typically the case for TCP doing bulk-data transfer.

telnet is a different vibe though. the sender often has little or no data, and the sending rate is set by how fast the user generates data 🥺 then the web showed up with dynamically-created data and HTTP 1.1 with persistent-connection TCP, and now the interaction between two states matters more than ever: application-limited periods (when the sender sends less than the congestion or receiver windows allow) and network-limited periods (when the sender is limited by the TCP window). we define a network-limited period as any period when the sender is sending a full window of data 🔥

long application-limited periods can invalidate the congestion window 😭 when the sender is network-limited, the value of the congestion window keeps getting "revalidated" by successfully sending a whole window of data without loss. an incoming stream of acknowledgements "clocks out" new data, which is concrete evidence of recent available bandwidth 🍓 but during application-limited periods, the estimate of capacity that cwnd represents can get steadily less accurate over time. in particular, capacity that used to belong to the network-limited connection might now be used by other traffic 👀

current TCP implementations are all over the place when it comes to starting up after an idle period ngl 💀 some slow-start after an idle period longer than the RTO estimate, as suggested in [RFC2581] and in the appendix of [VJ88], while others don't reduce their congestion window after an idle period at all. [RFC2581] recommends the following: "a TCP SHOULD set cwnd to no more than RW [the initial window] before beginning transmission if the TCP has not sent data in an interval exceeding the retransmission timeout." there's also a proposal for slow-start after idle in [HTH98]. and the idea of validating congestion information during idle periods has shown up outside of TCP and IP too, like the "Use-it or Lose-it" mechanisms for ATM networks [J96,J95] 🦋

so to fix the revalidation problem after an application-limited period, we propose a simple change to TCP's congestion control. decay cwnd after the transition from a sufficiently long application-limited period (at least one roundtrip time) to a network-limited period. specifically, after an idle period, the TCP sender should reduce its congestion window by half for every RTT that the flow has remained idle ✨

when cwnd gets reduced, ssthresh stays as "memory" of the recent congestion window 🧠 ssthresh is never decreased when cwnd is reduced after an application-limited period. before cwnd is reduced, ssthresh is set to the maximum of its current value and halfway between the old and new values of cwnd. this lets a TCP sender that's ramping its rate back up after an application-limited period slow-start quickly and recover most of the previous congestion window 🚀 to be more precise: if ssthresh is less than 3/4 cwnd when the congestion window is reduced after an application-limited period, then ssthresh is increased to 3/4 cwnd before the reduction of the congestion window 💅

the second problem is that cwnd can also be increased (in slow-start or congestion avoidance) during application-limited periods, when the old value might never have been fully used 🙈 as far as the authors know, every current TCP implementation increases the congestion window when an acknowledgement arrives, as long as the receiver's advertised window and the slow-start or congestion avoidance increase algorithm allow it, without checking whether the previous cwnd was actually used. so this document proposes that the window increase algorithm should not be invoked during application-limited periods [MSML99]. specifically, the TCP sender should not increase the congestion window when it has been application-limited (and therefore hasn't fully used the current congestion window). this keeps cwnd from growing arbitrarily large without evidence that the network can support it 🌈 from [MSML99, Section 5.2]: "This restriction assures that [cwnd] only grows as long as TCP actually succeeds in injecting enough data into the network to test the path."

one somewhat separate problem with keeping a big congestion window after an application-limited period: the sender might suddenly get a large amount of data after a quiet period and immediately send a full congestion window of back-to-back packets 😱 this burst problem can be handled with rate-based pacing (RBP, [VH97]) or with a maximum burst size control [FF96]. but the authors contend that even with mechanisms that limit back-to-back sending or pace packets out over a roundtrip time, an old congestion window that hasn't been fully used for some time can't be trusted as an indication of the bandwidth currently available for that flow 🥹 they also contend that the mechanisms for pacing out packets allowed by the congestion window are largely orthogonal to the algorithms that determine the appropriate size of the congestion window 🎀

3. Description ✨

okay so this is the main event bestie 💅 When a TCP sender has enough data to fill the network capacity for its flow, cwnd and ssthresh get set to values that fit the network conditions right now. But when the sender stops sending, the flow stops checking on the network, so the cwnd value can go stale and become inaccurate 😭 The authors think the correct, conservative move here is to cut the congestion window in half for every RTT the flow stays inactive. Why half? It's a very conservative number, based on how fast multiplicative decrease would have shrunk the window if there had been loss. Iconic restraint 🫶

Another situation is that the sender keeps sending but becomes application-limited instead of network-limited. So it offers less data to the network than the congestion window would allow. The flow is still sampling the network here, but it isn't sending enough traffic to be sure there's still room in the network for a full congestion window. For this case, the authors think the correct conservative behavior is for the sender to track the maximum amount of congestion window it actually used during each RTT, and then decay the congestion window each RTT to the midpoint between the current cwnd value and that maximum value used. Main character energy 👑

Before the congestion window gets reduced, ssthresh is set to the maximum of its current value and 3/4 cwnd. If the sender then has more data to send than the decayed cwnd allows, the TCP will slow-start (perform exponential increase) at least halfway back up to the old value of cwnd 🦋

Now, why "3/4 cwnd"? Because 3/4 cwnd is a conservative estimate of the recent average value of the congestion window, and TCP should safely be able to slow-start at least up to that point ✨ For a TCP in steady state that keeps reducing its congestion window each time it hits some maximum value maxwin, the average congestion window has been 3/4 maxwin. So on average, when the connection becomes application-limited, cwnd will be 3/4 maxwin, and in that case cwnd itself represents the average value of the congestion window. But if the connection happens to become application-limited when cwnd equals maxwin, then the average value of the congestion window is given by 3/4 cwnd 🧚

There's also an alternate option. You could set ssthresh to the maximum of its current value and the old value of cwnd, which would let TCP slow-start all the way back up to the old value of cwnd. The document says further experimentation can be used to evaluate these two options for setting ssthresh 🤔

For the separate issue of increasing the congestion window in response to an acknowledgement, the authors believe the correct behavior is for the sender to increase the congestion window only if the window was full when the acknowledgment arrived. No growing cwnd when nothing was actually using it 🙈

The authors call this set of changes TCP Congestion Window Validation (CWV), because they're all about making sure the congestion window is always a valid reflection of the current network state as probed by the connection 💖

3.1. The basic algorithm for reducing the congestion window

okay this part is the heart of CWV 🌸 A key issue is figuring out how to apply the rule of reducing the congestion window once for every roundtrip time that the flow is application-limited. The trick is that the RTT isn't always known precisely, so the document uses TCP's retransmission timer (RTO) as a reasonable upper bound on the roundtrip time. That means cwnd gets reduced roughly once per RTO ⏰

Here's how this basic algorithm could be implemented in TCP. When TCP sends a new packet, it checks whether more than RTO seconds have elapsed since the previous packet was sent. If RTO has elapsed, ssthresh is set to the maximum of 3/4 cwnd and the current value of ssthresh. Then the congestion window is halved for every RTO that elapsed since the previous packet was sent. On top of that, T_prev is set to the current time, and W_used is reset to zero. T_prev is used to figure out the elapsed time since the sender was last network-limited or last reduced cwnd after an idle period. When the sender is application-limited, W_used holds the maximum congestion window actually used since the sender was last network-limited 💅

The mechanism for figuring out how many RTOs fit in the most recent idle period could also work with a timer that expires every RTO after the last packet was sent, instead of checking on every packet. Which one is more efficient to build depends on the constraints of different operating systems, so the choice is up to the implementer 🫶

After TCP sends a packet, it also checks whether that packet filled the congestion window. If it did, the sender is network-limited, so it sets T_prev to the current TCP clock time and sets W_used to zero ✨

When TCP sends a packet that does not fill the congestion window, and the TCP send queue is empty, the sender is application-limited. In that case, it checks whether the amount of unacknowledged data is greater than W_used. If so, W_used is set to the amount of unacknowledged data. TCP also checks whether the elapsed time since T_prev is greater than RTO. If it is, then TCP hasn't just reduced its congestion window following an idle period. It has been application-limited rather than network-limited for at least one entire RTO interval, but for less than two RTO intervals. So TCP sets ssthresh to the maximum of 3/4 cwnd and the current value of ssthresh, and reduces its congestion window to (cwnd+W_used)/2. Then W_used is set to zero and T_prev is set to the current time, so a further reduction won't happen until at least another RTO period has passed. Net result: during an application-limited period, CWV reduces the congestion window once per RTO 🦋

3.2. Pseudo-code for reducing the congestion window

okay bestie, here's the pseudo-code, copied exactly so you can see the whole flow 🎀

Initially:
    T_last = tcpnow, T_prev = tcpnow, W_used = 0

After sending a data segment:
    If tcpnow - T_last >= RTO
        (The sender has been idle.)
        ssthresh =  max(ssthresh, 3*cwnd/4)
        For i=1  To (tcpnow - T_last)/RTO
            win =  min(cwnd, receiver's declared max window)
            cwnd =  max(win/2, MSS)
        T_prev = tcpnow
        W_used = 0

    T_last = tcpnow

    If window is full
        T_prev = tcpnow
        W_used = 0
    Else
        If no more data is available to send
            W_used =  max(W_used, amount of unacknowledged data)
            If tcpnow - T_prev >= RTO
                (The sender has been application-limited.)
                ssthresh =  max(ssthresh, 3*cwnd/4)
                win =  min(cwnd, receiver's declared max window)
                cwnd = (win + W_used)/2
                T_prev = tcpnow
                W_used = 0

4. Simulations ✨

the CWV proposal has been implemented as an option in the network simulator NS [NS] 🖥️ The simulations in the CWV validation test suite can be run with the command "./test-all-tcp" in the directory "tcl/test". They show CWV reducing the congestion window after a period where the TCP connection was application-limited, and limiting the increase in the congestion window when a transfer is application-limited. As the simulations show, using ssthresh to keep connection history is a critical part of the Congestion Window Validation algorithm 👑 [HPF99] goes into these simulations in more detail, so go check it out 🌈

5. Experiments 🧪

we implemented the CWV mechanism in the TCP implementation in FreeBSD 3.2 💖 [HPF99] also discusses these experiments in more detail.

The first experiment looks at how Congestion Window Validation limits cwnd increases during application-limited periods. It used a real ssh connection through a modem link emulated with Dummynet [Dummynet]. The link speed is 30Kb/s, and the link has five packet buffers available. Most modem banks have more buffering than this today, but the more buffer-limited situation sometimes happens with older modems 🙈 In the first half of the transfer, the user is typing away over the connection. About halfway through, the user lists a moderately large file, which causes a big burst of traffic to be sent.

For the unmodified TCP, every returning ACK during the first part of the transfer makes cwnd go up. So the big burst of data arriving from the application to the transport layer gets sent as lots of back-to-back packets, most of which get lost and then retransmitted 😭

For the modified TCP with Congestion Window Validation, the congestion window doesn't increase when the window isn't full, and it has been decreased during application-limited periods to be closer to what the user actually used. The burst of traffic is now constrained by the congestion window, which gives a better-behaved flow with minimal loss. The end result is that the transfer happens approximately 30% faster than the transfer without CWV, because it avoids retransmission timeouts 🚀

The second experiment uses a real ssh connection over a real dialup ppp connection, where the modem bank has much more buffering. For the unmodified TCP, the initial burst from the large file doesn't cause loss, but it does make the RTT go up to approximately 5 seconds, where the connection becomes bounded by the receiver's window 💀

For the modified TCP with Congestion Window Validation, the flow is much better behaved and doesn't produce a big burst of traffic. In this case, the linear increase for cwnd causes a slow increase in the RTT as the buffer slowly fills 🌸

For the second experiment, both the modified and the unmodified TCP finish delivering the data at precisely the same time. That's because the link is fully utilized in both cases, since the modem buffer is larger than the receiver window. Clearly a modem buffer this size is undesirable, because of its effect on the RTT of competing flows. But it's necessary with current TCP implementations that produce bursts similar to those shown in the top graph 🙃

6. Conclusions 🎀

okay so this document has presented several TCP algorithms for Congestion Window Validation. They're meant to be used after an idle period or a period where the sender was application-limited, and before an increase of the congestion window 💅 The goal is for TCP's congestion window to reflect the connection's recent knowledge about the state of the network path, while still keeping some memory (i.e., in ssthresh) about the earlier state of the path ✨ The authors believe these modifications will benefit both the network and the TCP flows themselves, by preventing unnecessary packet drops caused by a TCP sender that hasn't updated its information (or lacks information) about current network conditions 🫶 Future work will document and investigate the benefits these algorithms provide, using both simulations and experiments. Additional future work will describe a more complex version of the CWV algorithm for TCP implementations where the sender doesn't have an accurate estimate of the TCP roundtrip time 🦋

7. References ✨

okay bestie, here's the reading list 📚 every single one is real, so I kept the titles and links exactly as they are 🫶

  • [FF96] Fall, K., and Floyd, S., Simulation-based Comparisons of Tahoe, Reno, and SACK TCP, Computer Communication Review, V. 26 N. 3, July 1996, pp. 5-21. URL "http://www.aciri.org/floyd/papers.html".
  • [HPF99] Mark Handley, Jitendra Padhye, Sally Floyd, TCP Congestion Window Validation, UMass CMPSCI Technical Report 99-77, September 1999. URL "ftp://www-net.cs.umass.edu/pub/Handley99-tcpq-tr-99-77.ps.gz".
  • [HTH98] Amy Hughes, Joe Touch, John Heidemann, "Issues in TCP Slow-Start Restart After Idle", Work in Progress.
  • [J88] Jacobson, V., Congestion Avoidance and Control, Originally from Proceedings of SIGCOMM '88 (Palo Alto, CA, Aug. 1988), and revised in 1992. URL "http://www-nrg.ee.lbl.gov/nrg-papers.html".
  • [JKBFL96] Raj Jain, Shiv Kalyanaraman, Rohit Goyal, Sonia Fahmy, and Fang Lu, Comments on "Use-it or Lose-it", ATM Forum Document Number: ATM Forum/96-0178, URL "http://www.netlab.ohio-state.edu/~jain/atmf/af_rl5b2.htm".
  • [JKGFL95] R. Jain, S. Kalyanaraman, R. Goyal, S. Fahmy, and F. Lu, A Fix for Source End System Rule 5, AF-TM 95-1660, December 1995, URL "http://www.netlab.ohio-state.edu/~jain/atmf/af_rl52.htm".
  • [MSML99] Matt Mathis, Jeff Semke, Jamshid Mahdavi, and Kevin Lahey, The Rate-Halving Algorithm for TCP Congestion Control, June 1999. URL "http://www.psc.edu/networking/ftp/papers/draft-ratehalving.txt".
  • [NS] NS, the UCB/LBNL/VINT Network Simulator. URL "http://www-mash.cs.berkeley.edu/ns/".
  • [RFC2581] Allman, M., Paxson, V. and W. Stevens, TCP Congestion Control, RFC 2581, April 1999.
  • [VH97] Vikram Visweswaraiah and John Heidemann. Improving Restart of Idle TCP Connections, Technical Report 97-661, University of Southern California, November, 1997.
  • [Dummynet] Luigi Rizzo, "Dummynet and Forward Error Correction", Freenix 98, June 1998, New Orleans. URL "http://info.iet.unipi.it/~luigi/ip_dummynet/".

8. Security Considerations 🔥

okay this part is serious, so listen up 👀 the general security stuff for TCP congestion control is covered in RFC 2581. this doc describes one piece of those congestion control procedures, which means everything RFC 2581 says applies to this algorithm too 🛡️ and honestly? there are no known extra security concerns for this specific algorithm 💅

9. Authors' Addresses 🎀

The people who wrote this are:

  • Mark Handley AT&T Center for Internet Research at ICSI (ACIRI) Phone: +1 510 666 2946 EMail: mjh@aciri.org URL: http://www.aciri.org/mjh/
  • Jitendra Padhye AT&T Center for Internet Research at ICSI (ACIRI) Phone: +1 510 666 2887 EMail: padhye@aciri.org URL: http://www-net.cs.umass.edu/~jitu/
  • Sally Floyd AT&T Center for Internet Research at ICSI (ACIRI) Phone: +1 510 666 2989 EMail: floyd@aciri.org URL: http://www.aciri.org/floyd/

Copyright (C) The Internet Society (2000). All Rights Reserved.

okay, the legal bit, but make it cute 🧚 you can copy and share this document, and you can even make derivative works that comment on it or help people implement it, as long as the copyright notice and this paragraph stay on every copy 🫶 the document itself can't be changed in any way, like removing the copyright notice or the references to the Internet Society or other Internet organizations. the exceptions are developing Internet standards (which follows the Internet Standards process copyright procedures) or translating it into languages other than English. these permissions are perpetual and the Internet Society (or its successors or assigns) won't take them back ✨

and the disclaimer, which is serious: this document is provided on an "AS IS" basis, and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 💀

Acknowledgement 🌸

Funding for the RFC Editor function is currently provided by the Internet Society. 🫶💖

📦 where this page comes from