RFC 2582

The NewReno Modification to TCP's Fast Recovery Algorithm

📅 published April 1999, from ietf

The NewReno Modification to TCP's Fast Recovery Algorithm ✨

Okay bestie, the title block is giving a lot: this is RFC 2582 from the Network Working Group, written by S. Floyd (ACIRI) and T. Henderson (U.C. Berkeley) in April 1999. It's filed as an Experimental category doc 🧪. The title block doesn't list any RFC that it obsoletes or updates, so nothing gets replaced or patched here 💅.

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 (1999). All Rights Reserved.

Abstract 💌

Okay so [RFC2001] is the one that lays out four intertwined TCP congestion control algorithms: Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery 🌸. Then [RFC2581] says it's totally fine to tweak these, including tweaks that use the TCP Selective Acknowledgement (SACK) option [MMFR96], and tweaks that respond to "partial acknowledgments" (ACKs which cover new data, but not all the data outstanding when loss was detected) when there's no SACK 🙈.

This doc describes one specific way to handle those partial acknowledgments, called NewReno. Janey Hoe was the first to propose this response, in [Hoe95] 🧚.

1. Introduction ✨

So the typical Fast Recovery from [RFC2581] (first shipped in the 1990 BSD Reno release, and called the Reno algorithm in [FF96]) has a pretty limited vibe 🥺. The TCP data sender only retransmits a packet after a retransmit timeout happens, or after three duplicate acknowledgements show up and kick off the Fast Retransmit algorithm. A single retransmit timeout might lead to several data packets getting retransmitted, but each Reno Fast Retransmit invocation only retransmits a single data packet.

Things get messy when multiple packets get dropped from a single window of data and Fast Retransmit and Fast Recovery both get invoked 😭. In that case, if the SACK option is available, the TCP sender has the info it needs to make smart choices about which packets to retransmit and which to leave alone during Fast Recovery 🧠. This document only applies to TCP connections that are unable to use the TCP Selective Acknowledgement (SACK) option.

Without SACK, the TCP sender has very little info to work with when making retransmission decisions during Fast Recovery 💀. From the three duplicate acknowledgements, the sender infers a packet loss and retransmits the indicated packet. After that, the data sender could keep getting duplicate acknowledgements, because the data receiver is acknowledging extra data packets that were already in flight when the sender entered Fast Retransmit.

When multiple packets are dropped from a single window of data, the first new information the sender gets is an acknowledgement for the retransmitted packet (the one retransmitted when Fast Retransmit was first entered) 👀. If only a single packet had been dropped, that acknowledgement would cover all the packets sent before Fast Retransmit was entered (assuming no reordering). But with multiple drops, the acknowledgement for the retransmitted packet only covers some of the packets sent before Fast Retransmit, not all of them. We call this packet a partial acknowledgment 🦋.

Along with several other suggestions, [Hoe95] proposed that during Fast Recovery, the TCP data sender respond to a partial acknowledgment by inferring that the indicated packet has been lost, and then retransmitting that packet 🔥. This document describes a modification to Fast Recovery in Reno TCP that bakes in a response to partial acknowledgements received during Fast Recovery. We call this modified algorithm NewReno, because it's a slight but significant variation of the basic Reno algorithm 👑. This document doesn't discuss the other suggestions in [Hoe95] and [Hoe96], like changing the ssthresh parameter during Slow-Start, or the idea of sending a new packet for every two duplicate acknowledgements during Fast Recovery 🙅‍♀️. The version of NewReno in this document also draws on other discussions of NewReno in the literature [LM97].

We do not claim that this NewReno version of Fast Recovery is an optimal modification for responding to partial acknowledgements, for TCPs that are unable to use SACK 🫶. Based on experience with the NewReno modification in the NS simulator [NS], we believe it improves the performance of the Fast Retransmit and Fast Recovery algorithms in a wide variety of scenarios 📈. We're simply documenting it for the benefit of the IETF community. We encourage the use of this modification to Fast Recovery, and we also encourage feedback about operational experiences with this or related modifications 🌈.

2. Definitions 📖

This document assumes the reader already knows the terms MAXIMUM SEGMENT SIZE (MSS), CONGESTION WINDOW (cwnd), and FLIGHT SIZE (FlightSize) from [RFC2581] 🎀. FLIGHT SIZE is defined in [RFC2581] as follows:

   FLIGHT SIZE:
      The amount of data that has been sent but not yet acknowledged.

3. The Fast Retransmit and Fast Recovery algorithms in NewReno ✨

Okay bestie, so the standard way to do Fast Retransmit and Fast Recovery is in [RFC2581] 🎀. NewReno is basically a glow-up of that, and it only changes two things. It adds a variable called "recover" in step 1, and it changes how you respond to a partial or new ACK in step 5 💅. The whole thing is called the "Fast Recovery procedure." It kicks off when three duplicate ACKs come in, and it ends either when a retransmission timeout happens or when an ACK arrives that covers all the data up to and including the data that was outstanding when Fast Recovery started 🦋.

  1. When the third duplicate ACK comes in and the sender is not already in the Fast Recovery procedure, set ssthresh to no more than the value from equation 1 below. (That's equation 3 from [RFC2581] 🔥.)
ssthresh = max (FlightSize / 2, 2*MSS)           (1)

Then record the highest sequence number transmitted in the variable "recover" 👑.

  1. Retransmit the lost segment and set cwnd to ssthresh plus 3*MSS. This "inflates" the congestion window by the three segments that have left the network and that the receiver has buffered 🧚.
  2. For each extra duplicate ACK that arrives, increment cwnd by MSS. This inflates the window again to reflect the additional segment that has left the network 💜.
  3. Transmit a segment, if the new value of cwnd and the receiver's advertised window allow it 🌸.
  4. When an ACK arrives that acknowledges new data, this ACK could be the acknowledgment from the retransmission in step 2, or one from a later retransmission 🫶.

If this ACK acknowledges all the data up to and including "recover," then it's acknowledging all the intermediate segments sent between the original transmission of the lost segment and the third duplicate ACK. Set cwnd to either (1) min (ssthresh, FlightSize + MSS), or (2) ssthresh, where ssthresh is the value from step 1. This is called "deflating" the window 🍓. (Quick note: "FlightSize" in step 1 is the amount of data outstanding when Fast Recovery was entered, while "FlightSize" in step 5 is the amount outstanding when Fast Recovery is exited. Different moments, different numbers! 🙈) If you pick the second option, the implementation should take measures to avoid a possible burst of data, in case the amount of data outstanding in the network was much less than the new congestion window allows [HTH98]. Then exit the Fast Recovery procedure 🦋.

If this ACK does not acknowledge all the data up to and including "recover," then it's a partial ACK 🥺. In that case, retransmit the first unacknowledged segment. Deflate the congestion window by the amount of new data acknowledged, then add back one MSS, and send a new segment if the new value of cwnd permits it. This "partial window deflation" tries to make sure that, when Fast Recovery eventually ends, approximately ssthresh amount of data will be outstanding in the network ✨. Do not exit the Fast Recovery procedure. If any duplicate ACKs arrive afterward, run steps 3 and 4 again 💅.

For the first partial ACK that arrives during Fast Recovery, also reset the retransmit timer ⏰.

Note that in step 5, the congestion window gets deflated when a partial acknowledgement comes in. The window was probably inflated quite a bit by then 🎈. Depending on the original pattern of packet losses, the partial acknowledgement might cover nearly a whole window of data. If the congestion window wasn't deflated in that case, the data sender could end up sending nearly a whole window back-to-back, and that's a vibe nobody wants 😭.

There are a few possible variants of the simple partial-ACK response described above 💖. First, there's the question of when to reset the retransmit timer after a partial acknowledgement. Section 4 below covers that more.

There's also a related question about how many packets to retransmit after each partial acknowledgement. The algorithm above retransmits a single packet after each partial acknowledgement. That's the most conservative option, since it's the least likely to cause an unnecessary retransmission 🧸. A variant that recovers faster from a window with lots of drops would be to effectively Slow-Start, which needs less than N roundtrip times to recover from N losses [Hoe96]. With this slightly more aggressive response to partial acknowledgements, it would make sense to reset the retransmit timer after each retransmission. We haven't tried this variant in our simulator, so we won't discuss it further in this document 🤷‍♀️.

A third question is how to avoid multiple Fast Retransmits caused by retransmitting packets the receiver has already received. Section 5 below covers that 🌈. Avoiding multiple Fast Retransmits matters even more if you use the more aggressive responses to partial acknowledgements, because then the sender is more likely to retransmit packets the receiver already has 👑.

And one last thing 🫶. Without the SACK option, the data sender is working with limited information. You could spend forever figuring out which Fast Recovery variant is best for which scenario. If recovering from multiple dropped packets in a single window is the big concern, the best move is to use the SACK option 🔥.

4. Resetting the retransmit timer. ⏰

The algorithm in Section 3 resets the retransmit timer only after the first partial ACK. So if a lot of packets get dropped from one window of data, the TCP data sender's retransmit timer will eventually expire, and the sender will invoke Slow-Start 😩. (This is illustrated on page 12 of [F98].) We call this the Impatient variant of NewReno 🏃‍♀️.

On the other hand, the NewReno simulations in [FF96] show the algorithm above, except the retransmit timer is reset after every partial acknowledgement. We call this the Slow-but-Steady variant of NewReno 🐢. In this case, for a window with lots of packet drops, the TCP data sender retransmits at most one packet per roundtrip time. (You can see this in the New-Reno TCP simulation of Figure 5 in [FF96], and on page 11 of [F98].) 🌸

For TCP implementations where the Retransmission Timeout Value (RTO) is generally not much larger than the round-trip time (RTT), the Impatient variant can hit a retransmit timeout even when only a few packets are dropped 😬. For TCP implementations where the RTO is usually a lot bigger than the RTT, the Slow-but-Steady variant can stay in Fast Recovery for a long time when multiple packets have been dropped from one window of data 🥱. Neither variant is optimal. A better algorithm might recover faster from multiple packet drops and combine that with the Slow-but-Steady approach to resetting the retransmit timers 💡. Just know there's a limit to how well this can perform without the SACK option 💜.

5. Avoiding Multiple Fast Retransmits ✨

okay bestie so without the SACK option, a duplicate ACK is kinda like a ghost 👻 it doesn't tell you which data packet at the receiver set it off. so the sender literally can't tell the difference between a duplicate ACK caused by a lost or delayed packet and one caused by the sender resending a packet the receiver already has. 💀 this means multiple segment losses from one window of data can sometimes cause unnecessary multiple Fast Retransmits (and multiple congestion window reductions) [Flo94].

with Fast Retransmit and Fast Recovery in Reno or NewReno TCP, the multiple Fast Retransmit problems are pretty minor 🫶 (especially compared to Tahoe TCP, which doesn't do Fast Recovery at all). still, unnecessary Fast Retransmits can happen with Reno or NewReno, especially if a Retransmit Timeout happens during Fast Recovery. (this is shown for Reno on page 6 of [F98], and for NewReno on page 8 of [F98].) with NewReno, the data sender stays in Fast Recovery until either a Retransmit Timeout happens or all of the data that was outstanding when Fast Retransmit was entered has been acknowledged. so with NewReno, the multiple Fast Retransmit problem from a single window of data can only show up after a Retransmit Timeout 🍓

the following change to the algorithms in Section 3 gets rid of the multiple Fast Retransmit problem 🔥 (this change is called "bugfix" in [F98], and it's shown on pages 7 and 9). it uses a new variable called "send_high", whose initial value is the initial send sequence number. after each retransmit timeout, the highest sequence number transmitted so far gets recorded in "send_high".

if, after a retransmit timeout, the TCP data sender retransmits three consecutive packets that the data receiver already has, then the sender gets three duplicate ACKs that don't acknowledge "send_high". in this case those duplicate ACKs aren't a sign of a new congestion event 🙅‍♀️ they just mean the sender unnecessarily retransmitted at least three packets.

we also need to note that if the sender gets three duplicate ACKs that don't acknowledge "send_high", it doesn't know whether those duplicate ACKs came from a brand new packet drop or not. for a TCP that uses this bugfix for avoiding multiple fast retransmits, the sender does not infer a packet drop from duplicate ACKs in these situations. as always, the retransmit timer is the backup mechanism for inferring packet loss in this case ⏰

this change to Fast Retransmit replaces Step 1 in Section 3 with Step 1A below. it also adds Step 6 below:

  • 1A. when the third duplicate ACK is received and the sender is not already in the Fast Recovery procedure, check to see if those duplicate ACKs cover more than "send_high". if they do, set ssthresh to no more than the value given in equation 1, record the highest sequence number transmitted in the variable "recover", and go to Step 2. if the duplicate ACKs don't cover "send_high", then do nothing. that means: do not enter the Fast Retransmit and Fast Recovery procedure, do not change ssthresh, do not go to Step 2 to retransmit the "lost" segment, and do not execute Step 3 upon subsequent duplicate ACKs.
  • 2-5. these are the same as the steps in Section 3 above.
  • 6. after a retransmit timeout, record the highest sequence number transmitted in the variable "send_high", and exit the Fast Recovery procedure if applicable.

Step 1A, which checks whether the duplicate ACKs cover more than "send_high", is the Careful variant of this algorithm. another possible variant would be to require only that the three duplicate ACKs cover "send_high" before starting another Fast Retransmit. we call this the Less Careful variant of Fast Retransmit. 🧐

there are two separate scenarios where the TCP sender could get three duplicate ACKs that acknowledge "send_high" but not anything above it. in the first scenario, the data sender transmitted four packets with sequence numbers higher than "send_high", the first of those packets got dropped in the network, and the following three packets each triggered a duplicate ACK acknowledging "send_high". in the second scenario, the sender unnecessarily retransmitted three packets below "send_high", and those three packets triggered three duplicate ACKs acknowledging "send_high". without SACK, the TCP sender can't tell these two scenarios apart 😭

with the Careful variant of Fast Retransmit, the data sender has to wait for a retransmit timeout in the first scenario, but it doesn't make an unnecessary Fast Retransmit in the second scenario. with the Less Careful variant, the data sender does Fast Retransmit like it should in the first scenario, but it makes an unnecessary Fast Retransmit in the second scenario. the NS simulator implements the Less Careful variant of NewReno, while the TCP implementation in Sun's Solaris 7 implements the Careful variant. this document recommends the Careful variant given in Step 1A above. 💖

6. Implementation issues for the data receiver.

[RFC2001] specifies that "Out-of-order data segments SHOULD be acknowledged immediately, in order to trigger the fast retransmit algorithm." Neal Cardwell has noted [C98] that some data receivers don't send an immediate acknowledgement when they send a partial acknowledgment, and instead wait for their delayed acknowledgement timer to expire first 🙄 as [C98] points out, this seriously limits the potential benefit from NewReno, because it delays when the data sender gets the partial acknowledgement. our recommendation is that the data receiver sends an immediate acknowledgement for an out-of-order segment, even when that out-of-order segment fills a hole in the buffer. 🌸

7. Simulations 🎀

simulations with NewReno are shown with the validation test tcl/test/test-all-newreno in the NS simulator. the command ../../ns test-suite-newreno.tcl reno shows a simulation with Reno TCP, which illustrates the data sender's lack of response to a partial acknowledgement. in contrast, the command ../../ns test-suite-newreno.tcl newreno_B shows the same scenario using the NewReno algorithms described in this paper ✨

the tests ../../ns test-suite-newreno.tcl newreno1_B0 and ../../ns test-suite-newreno.tcl newreno1_B show the Slow-but-Steady and the Impatient variants of NewReno, respectively. 🦋

8. Conclusions 👑

okay so our recommendation is that TCP implementations include the NewReno modification to the Fast Recovery algorithm given in Section 3, along with the modification for avoiding multiple Fast Retransmits given in Section 5. the NewReno modification from Section 3 can matter even for TCP implementations that support the SACK option, because the SACK option can only be used for TCP connections when both TCP end-nodes support it. also, the NewReno modification given in Section 3 implements the Impatient variant of NewReno, not the Slow-but-Steady variant. 💅

while this document mentions several possible variations to the NewReno algorithm, we haven't explored all of them, so we can't make recommendations about some of them 🙈 our belief is that the differences between any two variants of NewReno are small compared to the differences between Reno and NewReno. basically, the important thing is to implement NewReno instead of Reno for a TCP connection without SACK. it matters less exactly which variant of NewReno you implement 🌈

9. Acknowledgements 🫶

many thanks to Anil Agarwal, Mark Allman, Vern Paxson, Kacheong Poon, and Bernie Volz for their detailed feedback on this document 💜

10. References 📚

  • [C98] Neal Cardwell, "delayed ACKs for retransmitted packets: ouch!". November 1998. Email to the tcpimpl mailing list, Message-ID Pine.LNX.4.02A.9811021421340.26785-100000@sake.cs.washington.edu, archived at http://tcp-impl.lerc.nasa.gov/tcp-impl.
  • [F98] Sally Floyd. Revisions to RFC 2001. Presentation to the TCPIMPL Working Group, August 1998. URLs ftp://ftp.ee.lbl.gov/talks/sf-tcpimpl-aug98.ps and ftp://ftp.ee.lbl.gov/talks/sf-tcpimpl-aug98.pdf.
  • [FF96] Kevin Fall and Sally Floyd. Simulation-based Comparisons of Tahoe, Reno and SACK TCP. Computer Communication Review, July 1996. URL ftp://ftp.ee.lbl.gov/papers/sacks.ps.Z.
  • [Flo94] S. Floyd, TCP and Successive Fast Retransmits. Technical report, October 1994. URL ftp://ftp.ee.lbl.gov/papers/fastretrans.ps.
  • [Hen98] Tom Henderson, Re: NewReno and the 2001 Revision. September 1998. Email to the tcpimpl mailing list, Message ID Pine.BSI.3.95.980923224136.26134A-100000@raptor.CS.Berkeley.EDU, archived at http://tcp-impl.lerc.nasa.gov/tcp-impl.
  • [Hoe95] J. Hoe, Startup Dynamics of TCP's Congestion Control and Avoidance Schemes. Master's Thesis, MIT, 1995. URL http://ana-www.lcs.mit.edu/anaweb/ps-papers/hoe-thesis.ps.
  • [Hoe96] J. Hoe, "Improving the Start-up Behavior of a Congestion Control Scheme for TCP", In ACM SIGCOMM, August 1996. URL http://www.acm.org/sigcomm/sigcomm96/program.html.
  • [HTH98] Hughes, A., Touch, J. and J. Heidemann, "Issues in TCP Slow-Start Restart After Idle", Work in Progress, March 1998.
  • [LM97] Dong Lin and Robert Morris, "Dynamics of Random Early Detection", SIGCOMM 97, September 1997. URL http://www.acm.org/sigcomm/sigcomm97/program.html.
  • [MMFR96] Mathis, M., Mahdavi, J., Floyd, S. and A. Romanow, "TCP Selective Acknowledgement Options", RFC 2018, October 1996.
  • [NS] The UCB/LBNL/VINT Network Simulator (NS). URL http://www-mash.cs.berkeley.edu/ns/.
  • [RFC2001] Stevens, W., "TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms", RFC 2001, January 1997.
  • [RFC2581] Stevens, W., Allman, M. and V. Paxson, "TCP Congestion Control", RFC 2581, April 1999.

11. Security Considerations 🔐

RFC 2581 discusses general security considerations concerning TCP congestion control. this document describes a specific algorithm that conforms with the congestion control requirements of RFC 2581, so those considerations apply to this algorithm too. there are no known additional security concerns for this specific algorithm. 🛡️

12. AUTHORS' ADDRESSES 💌

Sally Floyd 🌸 AT&T Center for Internet Research at ICSI (ACIRI)

Tom Henderson 🦋 University of California at Berkeley

Copyright (C) The Internet Society (1999). All Rights Reserved. 🌈

Okay so, this document and translations of it can be copied and handed out to others, and derivative works that comment on it, explain it, or help people implement it can be made, copied, published, and distributed, in whole or in part, without any restriction of any kind. The only catch is that the above copyright notice and this paragraph have to be included on all of those copies and derivative works. 🫶

However, this document itself may not be modified in any way, like removing the copyright notice or the references to the Internet Society or other Internet organizations. The one exception is when it's needed for developing Internet standards, in which case the copyright procedures in the Internet Standards process must be followed. Translating it into languages other than English is also allowed. 🌍

The limited permissions above are perpetual and will not be revoked by the Internet Society or its successors or assigns. Forever and ever, no cap. 💜

This document and the information in it 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. 💀

📦 where this page comes from