RFC 3782

The NewReno Modification to TCP's Fast Recovery Algorithm

📅 published April 2004, from ietf

Part 1 of 5 💖

RFC 3782: The NewReno Modification to TCP's Fast Recovery Algorithm 🎀

Okay bestie, here's the title block tea ☕✨

  • Network Working Group: the group that put this one together 🧚
  • Request for Comments: 3782: its RFC number, so you can look it up 🔍
  • Obsoletes: 2582: this one takes over from RFC 2582 🦋
  • Category: Standards Track: it's an actual Internet standard, not just an experiment 👑
  • Authors: S. Floyd (ICSI), T. Henderson (Boeing), and A. Gurtov (TeliaSonera) 💅
  • Date: April 2004 🌸

Status of this Memo ⭐

Bestie, this part is the official fine print. This document is an Internet standards track protocol for the Internet community, and it's asking everyone to talk about it and suggest improvements 🫶 For the current standardization state and status of this protocol, check the current edition of the "Internet Official Protocol Standards" (STD 1) 📚 And yes, distribution of this memo is unlimited 🌈

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

Abstract 💜

Okay so the whole point of this document is to level up NewReno TCP's Fast Retransmit and Fast Recovery algorithms, which were defined in RFC 2582. It's moving them from Experimental status to Standards Track status, which is giving glow-up energy 🦋✨

The big change compared to RFC 2582 is that this document specifies the Careful variant of NewReno's Fast Retransmit and Fast Recovery algorithms. The base algorithm in RFC 2582 didn't try to stop unnecessary multiple Fast Retransmits that can happen after a timeout, which is kind of a mess 💀 RFC 2582 did define "Careful" and "Less Careful" variants that avoid those extra Fast Retransmits, and it recommended the Careful variant 🍓 So this document makes the previously-named "Careful" variant the basic version of NewReno TCP. Iconic behavior 👑

1. Introduction ✨

Okay so let's start with the typical TCP Fast Recovery algorithm from [RFC2581]. It was first implemented in the 1990 BSD Reno release, and [FF96] calls it the Reno algorithm 🌸 With Reno, the TCP data sender only retransmits a packet in two situations: after a retransmit timeout has happened, or after three duplicate acknowledgements have arrived and triggered the Fast Retransmit algorithm. A single retransmit timeout might lead to several data packets being retransmitted, but each time Fast Retransmit runs under RFC 2581, it only retransmits one data packet 🙈

Now, things get messy when multiple packets get dropped from a single window of data and the Fast Retransmit and Fast Recovery algorithms both get invoked 😭 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 skip during Fast Recovery 🧠 This document only applies to TCP connections that can't use the TCP Selective Acknowledgement (SACK) option. That could be because the option isn't supported locally, or because the TCP peer didn't say it was willing to use SACK 🫶

Without SACK, the sender has very little info to work with during Fast Recovery 💀 From the three duplicate acknowledgements, the sender infers that a packet was lost, and retransmits the indicated packet. After that, the data sender can keep getting more 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 one window of data, the first new information the sender gets is an acknowledgement for the retransmitted packet. That's the packet that got retransmitted when Fast Retransmit was first entered 🎀 If there's just one packet drop and no reordering, that acknowledgement covers all of the packets sent before Fast Retransmit was entered, which is the dream ✨ But if there are multiple packet drops, the acknowledgement for the retransmitted packet only covers some of the packets sent before Fast Retransmit, not all of them. We call this acknowledgement a partial acknowledgment 🧩

Along with several other suggestions, [Hoe95] proposed that during Fast Recovery, the TCP data sender should respond to a partial acknowledgment by inferring that the next in-sequence packet was lost, and then retransmitting that packet 💜 This document describes a modification to the Fast Recovery algorithm in RFC 2581 that adds 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 in RFC 2581 🌈

This document doesn't cover the other suggestions in [Hoe95] and [Hoe96], like changing the ssthresh parameter during Slow-Start, or sending a new packet for every two duplicate acknowledgements during Fast Recovery 🙅‍♀️ The NewReno version here also draws on other discussions of NewReno in the literature [LM97, Hen98] 📚

Real talk though: we don't claim that the NewReno version of Fast Recovery described here is the optimal modification for responding to partial acknowledgements, for TCP connections that can't use SACK 🫣 Based on our experience with the NewReno modification in the NS simulator [NS] and with lots of NewReno implementations, we believe it improves the performance of the Fast Retransmit and Fast Recovery algorithms in a wide variety of scenarios 🍓✨

2. Terminology and Definitions 🎀

Bestie, the key words are the vocab that tells you how strict each rule is, so pay attention 👀 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as described in BCP 14, RFC 2119 [RFC2119]. This RFC uses them to show the requirement levels for compliant TCP implementations that implement the NewReno Fast Retransmit and Fast Recovery algorithms described in this document 💅

This document assumes you already know the terms SENDER MAXIMUM SEGMENT SIZE (SMSS), CONGESTION WINDOW (cwnd), and FLIGHT SIZE (FlightSize), which are defined in [RFC2581] 🧚 FLIGHT SIZE is defined as 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, now we're getting to the actual NewReno magic 🪄. The standard way to do Fast Retransmit and Fast Recovery is in [RFC2581]. This section lays out the basic NewReno algorithm. Sections 4 through 6 cover some optional variants and why you might want them when you're tuning for certain network situations 🎀. Sections 7 and 8 give implementers guidance based on experience with NewReno implementations 🫶.

NewReno changes the Fast Recovery procedure. That procedure starts when three duplicate ACKs arrive and ends when either a retransmission timeout happens or an ACK comes in that acknowledges all the data up to and including the data that was outstanding when Fast Recovery started 🌸.

NewReno differs from the implementation in [RFC2581] in a few ways. It introduces a variable called "recover" in Step 1, it changes how a partial or new acknowledgement is handled in Step 5, and it tweaks Step 1 and adds Step 6 so the sender doesn't do multiple Fast Retransmits caused by retransmitting packets the receiver already has 😭.

The algorithm here uses a variable called "recover", and its initial value is the initial send sequence number 🦋.

1) Three duplicate ACKs: When the third duplicate ACK arrives and the sender isn't already in the Fast Recovery procedure, check whether the Cumulative Acknowledgement field covers more than "recover". If it does, go to Step 1A. If not, go to Step 1B.

1A) Invoking Fast Retransmit: If so, set ssthresh to no more than the value from equation 1 below. (This is equation 3 from [RFC2581].)

ssthresh = max (FlightSize / 2, 2*SMSS)           (1)

Then record the highest sequence number transmitted in the variable "recover", and go to Step 2 💖.

1B) Not invoking Fast Retransmit: Don't enter the Fast Retransmit and Fast Recovery procedure. Specifically, don't change ssthresh, don't go to Step 2 to retransmit the "lost" segment, and don't run Step 3 on later duplicate ACKs 🙈.

2) Entering Fast Retransmit: Retransmit the lost segment and set cwnd to ssthresh plus 3*SMSS. This artificially "inflates" the congestion window by the number of segments (three) that have left the network and that the receiver has buffered 🍓.

3) Fast Recovery: For each additional duplicate ACK received while in Fast Recovery, increment cwnd by SMSS. This artificially inflates the congestion window to reflect the additional segment that has left the network 💜.

4) Fast Recovery, continued: Transmit a segment if the new value of cwnd and the receiver's advertised window allow it 🧚.

5) When an ACK arrives that acknowledges new data: This ACK could be the acknowledgment elicited by the retransmission from Step 2, or one elicited by a later retransmission 👑.

Full acknowledgements: If this ACK acknowledges all the data up to and including "recover", then it acknowledges all the intermediate segments sent between the original transmission of the lost segment and the receipt of the third duplicate ACK. Set cwnd to either (1) min (ssthresh, FlightSize + SMSS) or (2) ssthresh, where ssthresh is the value set in Step 1. This is called "deflating" the window. (Note that "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.) If you pick the second option, the implementation is encouraged to take steps to avoid a possible burst of data, in case the amount of data outstanding in the network is much less than the new congestion window allows. A simple mechanism is to limit the number of data packets that can be sent in response to a single acknowledgement. This is known as maxburst_ in the NS simulator. Then exit the Fast Recovery procedure 🎉.

Partial acknowledgements: If this ACK does not acknowledge all the data up to and including "recover", it's a partial ACK. In that case, retransmit the first unacknowledged segment. Deflate the congestion window by the amount of new data acknowledged by the cumulative acknowledgement field. If the partial ACK acknowledges at least one SMSS of new data, add back SMSS bytes to the congestion window. Just like in Step 3, this artificially inflates the window to reflect the additional segment that has left the network. Then 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, about ssthresh worth of data will be outstanding in the network. Do not exit the Fast Recovery procedure. (That means if any duplicate ACKs arrive later, run Steps 3 and 4 above.) 🫠

For the first partial ACK that arrives during Fast Recovery, also reset the retransmit timer. Timer management is discussed in more detail in Section 4 ⏲️.

6) Retransmit timeouts: After a retransmit timeout, record the highest sequence number transmitted in the variable "recover", and exit the Fast Recovery procedure if it applies 💀.

Step 1 checks that the Cumulative Acknowledgement field covers more than "recover". The acknowledgement field holds the sequence number the sender expects to receive next, so the acknowledgement "ack_number" covers more than "recover" when:

   ack_number - 1 > recover;

In other words, at least one more byte of data is acknowledged beyond the highest byte that was outstanding the last time Fast Retransmit was entered 🌈.

Notice that in Step 5, the congestion window gets deflated after a partial acknowledgement arrives. The window was probably inflated quite a lot by the time that partial acknowledgement showed up. Also, depending on how the packets were originally lost, the partial acknowledgement might acknowledge nearly a whole window of data. If the window weren't deflated in that case, the data sender could end up sending nearly a whole window back-to-back, which is a lot 😳.

This document doesn't specify how the sender responds to duplicate ACKs when the Fast Retransmit/Fast Recovery algorithm isn't invoked. That's covered in other documents, like the ones describing the Limited Transmit procedure [RFC3042]. It also doesn't address adjusting the duplicate acknowledgement threshold. It assumes the threshold from the IETF standards, and the current standard is RFC 2581, which sets the threshold at three duplicate acknowledgements 🔥.

One last note: without the SACK option, the data sender is working with pretty limited information. When recovering from multiple dropped packets in a single window of data really matters, the best option is to use the SACK option 🧠.

4. Resetting the Retransmit Timer in Response to Partial Acknowledgements ⏰

Here's a variant to the partial acknowledgement response from Section 3, and it's all about when to reset the retransmit timer after a partial acknowledgement 👀. The algorithm in Section 3, Step 5, only resets the retransmit timer after the first partial ACK. So if a bunch 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 shown on page 12 of [F98].) We call this the Impatient variant of NewReno 😤.

We should also point out that the Impatient variant in Section 3 doesn't follow the recommended algorithm in RFC 2988, which is to restart the retransmit timer after every packet transmission or retransmission [RFC2988, Step 5.1] 🙃.

On the flip side, the NewReno simulations in [FF96] run the algorithm described above but with one change: the retransmit timer gets reset after every partial acknowledgement. We call this the Slow-but-Steady variant of NewReno 🐢. Here, when a window has lots of packet drops, the TCP data sender retransmits at most one packet per roundtrip time. (You can see this behavior in the New-Reno TCP simulation of Figure 5 in [FF96], and on page 11 of [F98].)

When N packets have been dropped from one window of data and N is large, the Slow-but-Steady variant can stay in Fast Recovery for N round-trip times, retransmitting one more dropped packet each round-trip time. For these scenarios, the Impatient variant recovers faster and performs better 🚀. The tests ns test-suite-newreno.tcl impatient1 and ns test-suite-newreno.tcl slow1 in the NS simulator show this, where the Impatient variant beats the Slow-but-Steady variant. The Impatient variant can matter a lot for TCP connections with large congestion windows, as the tests ns test-suite-newreno.tcl impatient4 and ns test-suite-newreno.tcl slow4 in the NS simulator illustrate 💅.

You can also build scenarios where the Slow-but-Steady variant does better than the Impatient variant. For example, this happens when only a few packets get dropped, the RTO is small enough that the retransmit timer expires, and performance would have been better if there had been no retransmit timeout 🥲. The tests ns test-suite-newreno.tcl impatient2 and ns test-suite-newreno.tcl slow2 in the NS simulator show this.

The Slow-but-Steady variant can also get higher goodput than the Impatient variant, because it avoids unnecessary retransmissions 💸. That's especially interesting for cellular links, where every transmission costs battery power and money 🔋. The tests ns test-suite-newreno.tcl impatient3 and ns test-suite-newreno.tcl slow3 in the NS simulator illustrate this. The Slow-but-Steady variant can also handle delay variation in the network better, since a delay spike might push the Impatient variant into a timeout and go-back-N recovery 🌊.

Neither of the two variants above is optimal. Our recommendation is the Impatient variant, as specified in Section 3 of this document, because the Slow-but-Steady variant performs poorly for TCP connections with large congestion windows 👑.

One possibility for a more optimal algorithm would be one that recovers from multiple packet drops as quickly as slow-start does, while still resetting the retransmit timers after each partial acknowledgement, as described in the section below. Just know there's a limit to how well this can perform without the SACK option in this case 🧐.

5. Retransmissions after a Partial Acknowledgement ✨

okay so bestie, there's a juicy alternative to the partial ACK response from Section 3 🧚. You could retransmit more than one packet after each partial ACK, and reset the retransmit timer after each retransmission 💅. Section 3 only retransmits a single packet per partial ACK, which is the most conservative option, because it's the least likely to send a packet nobody needed 🫶. Then there's the faster version that would recover quicker from a window with lots of drops: effectively Slow-Start, retransmitting two packets after each partial ACK 🔥. That takes less than N roundtrip times to recover from N losses [Hoe96]. BUT without SACK, recovering as fast as slow-start makes it way more likely to unnecessarily retransmit packets, and that could seriously complicate the recovery mechanisms 💀.

We need to talk about how Section 3 and RFC 2582 are different from the response in [FF96] 👀. Both approaches only retransmit one packet per partial ACK, but they are NOT the same vibe. In Section 3, Step 5 says the TCP sender deflates the congestion window by the amount of new data acknowledged, adds back SMSS bytes if the partial ACK acknowledges at least SMSS bytes of new data, and sends a new segment if the new value of cwnd permits it 🌸. So only one previously-sent packet gets retransmitted per partial ACK, but extra new packets might go out too, depending on how much new data the partial ACK covered ✨. The [FF96] variant of NewReno just set the congestion window to ssthresh when a partial ACK came in 😭. That one is more conservative and doesn't try to accurately track how many packets are actually outstanding after a partial ACK. Both give acceptable performance, but the Section 3 variant recovers more smoothly when multiple packets get dropped from one window of data 🦋. (You can see the [FF96] behavior in the NS simulator by setting the variable "partial_window_deflation_" for "Agent/TCP/Newreno" to 0. The Section 3 behavior is achieved by setting "partial_window_deflation_" to 1 🎀.)

6. Avoiding Multiple Fast Retransmits 🍓

this section explains why the sender needs its state variable "recover", and talks about possible heuristics for telling apart a retransmitted packet that got dropped from three duplicate ACKs caused by unnecessarily retransmitting three packets 🕵️‍♀️.

Without the SACK option or timestamps, a duplicate ACK doesn't tell you which data packet at the TCP data receiver triggered it 🙈. So the TCP data sender can't tell whether a duplicate ACK came from a lost or delayed data packet, or from the sender's own unnecessary retransmission of a data packet the receiver already had. Because of this, with the Retransmit and Fast Recovery algorithms in Reno TCP, multiple segment losses from one window of data can sometimes cause unnecessary multiple Fast Retransmits (and multiple reductions of the congestion window) [F94] 😩.

Honestly, with Fast Retransmit and Fast Recovery in Reno TCP, the performance problems from multiple Fast Retransmits are pretty minor compared to Tahoe TCP, which doesn't implement Fast Recovery at all 🤷‍♀️. Still, unnecessary Fast Retransmits can happen with Reno TCP unless you add some explicit mechanism to stop them, like using the "recover" variable 🛡️. (This modification is called "bugfix" in [F98], and it's illustrated on pages 7 and 9 of that document. Unnecessary Fast Retransmits for Reno without "bugfix" are illustrated on page 6 of [F98].)

Section 3 of [RFC2582] defined a default variant of NewReno TCP that did NOT use the variable "recover", and didn't check whether duplicate ACKs covered "recover" before invoking Fast Retransmit 😤. With that default variant from RFC 2582, multiple Fast Retransmits from a single window of data can happen after a Retransmit Timeout (like on page 8 of [F98]), or in scenarios with reordering (like the validation test "./test-all-newreno newreno5_noBF" in directory "tcl/test" of the NS simulator). That gives performance similar to what's on page 8 of [F03]. RFC 2582 also defined Careful and Less Careful variants of the NewReno algorithm, and recommended the Careful variant 💅.

The algorithm in Section 3 of this document matches the Careful variant of NewReno TCP from RFC 2582, and it gets rid of the multiple Fast Retransmits problem 👑. It uses the variable "recover", whose initial value is the initial send sequence number. After each retransmit timeout, the highest sequence number transmitted so far is recorded in "recover" 📝.

If, after a retransmit timeout, the TCP data sender retransmits three consecutive packets the data receiver already has, then the sender will receive three duplicate ACKs that do not cover more than "recover" 🥲. In that case, the duplicate ACKs aren't a sign of a new congestion event. They just mean the sender unnecessarily retransmitted at least three packets, which is lowkey a vibe check for the sender 😂.

BUT when a retransmitted packet is itself dropped, the sender can also get three duplicate ACKs that don't cover more than "recover" 😭. In that situation, the sender would have been better off initiating Fast Retransmit. For a TCP implementing the algorithm in Section 3 of this document, the sender does NOT infer a packet drop from duplicate ACKs in this scenario. As always, the retransmit timer is the backup mechanism for inferring packet loss here ⏰.

There are several heuristics, based on timestamps or on how far the cumulative acknowledgement field advanced, that let the sender sometimes tell apart three duplicate ACKs after a dropped retransmitted packet from three duplicate ACKs caused by unnecessarily retransmitting three packets [Gur03, GF04] 🔍. The TCP sender MAY use such a heuristic to decide to invoke a Fast Retransmit in some cases, even when the three duplicate ACKs do not cover more than "recover" ✨.

For example, when three duplicate ACKs come from unnecessarily retransmitting three packets, the cumulative acknowledgement field is likely to advance by at least four segments 📈. A timestamp-based heuristic uses the fact that when there's a hole in the sequence space, the timestamp echoed in the duplicate ACK is the timestamp of the most recent data packet that advanced the cumulative acknowledgement field [RFC1323] 🧠. If timestamps are used, and the sender stores the timestamp of the last acknowledged segment, then the echoed timestamp in duplicate ACKs can tell a dropped retransmitted packet apart from three duplicate ACKs caused by unnecessarily retransmitting three packets 🫧. The heuristics are illustrated in the NS simulator in the validation test "./test-all-newreno". 🎀

6.1. ACK Heuristic 🌈

If the ACK-based heuristic is used, then after the cumulative acknowledgement field advances, the sender stores the value of the previous cumulative acknowledgement as prev_highest_ack, and stores the latest cumulative ACK as highest_ack. On top of that, the following step is performed if Step 1 in Section 3 fails, before moving on to Step 1B 🫶.

1*)  If the Cumulative Acknowledgement field didn't cover more than
     "recover", check to see if the congestion window is greater than
     SMSS bytes and the difference between highest_ack and
     prev_highest_ack is at most 4*SMSS bytes.  If true, duplicate
     ACKs indicate a lost segment (proceed to Step 1A in Section 3).
     Otherwise, duplicate ACKs likely result from unnecessary
     retransmissions (proceed to Step 1B in Section 3).

The congestion window check protects against doing a fast retransmit right after a retransmit timeout, kind of like the "exitFastRetrans_" variable in NS 🛡️. Examples of applying the ACK heuristic are in the validation tests "./test-all-newreno newreno_rto_loss_ack" and "./test-all-newreno newreno_rto_dup_ack" in directory "tcl/test" of the NS simulator 💖.

If several ACKs get lost, the sender can see a jump in the cumulative ACK of more than three segments, and then the heuristic can fail 😬. A validation test for this scenario is "./test-all-newreno newreno_rto_loss_ackf". RFC 2581 recommends that a receiver send duplicate ACKs for every out-of-order data packet, like a data packet received during Fast Recovery 📮. The ACK heuristic is more likely to fail if the receiver doesn't follow this advice, because then a smaller number of ACK losses is needed to produce a big enough jump in the cumulative ACK 🙃.

6.2. Timestamp Heuristic 🌷

If this heuristic is used, the sender stores the timestamp of the last acknowledged segment. Also, the second paragraph of Step 1 in Section 3 gets replaced like this 🔁:

1**) If the Cumulative Acknowledgement field didn't cover more than
     "recover", check to see if the echoed timestamp in the last
     non-duplicate acknowledgment equals the stored timestamp.  If
     true, duplicate ACKs indicate a lost segment (proceed to Step 1A
     in Section 3).  Otherwise, duplicate ACKs likely result from
     unnecessary retransmissions (proceed to Step 1B in Section 3).

Examples of applying the timestamp heuristic are in the validation tests "./test-all-newreno newreno_rto_loss_tsh" and "./test-all-newreno newreno_rto_dup_tsh" 🎀. The timestamp heuristic works correctly both when the receiver echoes timestamps as specified by [RFC1323], and when it echoes them the way its revision attempts do 🙌. However, if the receiver arbitrarily echoes timestamps, the heuristic can fail 🙃. It can also fail if a timeout was spurious and the returning ACKs aren't from retransmitted segments. This can be prevented by detection algorithms such as [RFC3522] 🔎.

7. Implementation Issues for the Data Receiver 🫶

okay bestie, [RFC2581] says "Out-of-order data segments SHOULD be acknowledged immediately, in order to accelerate loss recovery." 📣 Neal Cardwell noticed 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 [C98] 😤. As [C98] points out, that severely limits NewReno's potential benefit, because it delays the partial acknowledgement arriving at the data sender 🐢. Echoing RFC 2581, 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 ✨💖

8. Implementation Issues for the Data Sender ✨

okay bestie, back to Section 3 Step 5 🫶 we said implementations should take measures to avoid a possible burst of data when leaving Fast Recovery, in case the amount of new data the sender is allowed to send (because of the new congestion window) is huge 😭 this can happen in NewReno when ACKs get lost or get treated as pure window updates. then the sender underestimates how many new segments it could've sent during recovery 💀 bursts specifically happen when the FlightSize is way smaller than the new congestion window when you exit Fast Recovery.

one simple fix is to limit how many data packets can go out in response to a single acknowledgment 💅 (this is called "maxburst_" in the ns simulator 🧚). other options are rate-based pacing, or setting the slow-start threshold to the resulting congestion window and then resetting the congestion window to FlightSize 🌸 a general recommendation on avoiding excessively bursty sending patterns is out of scope for this doc, so we're not going there today 🙈

an implementation may want a separate flag to track whether it's currently in Fast Recovery 🎀 using the duplicate acknowledgment counter for that is NOT reliable, because it can get reset on window updates and out-of-order acknowledgments. not it 🙅‍♀️

when you're NOT in Fast Recovery, the state variable "recover" should be pulled along with the state variable for acknowledgments (usually "snd_una") 🦋 why? so that after a ton of data has been sent and acked, the sequence space doesn't wrap around and falsely tell you that Fast Recovery shouldn't be entered (Section 3, step 1, last paragraph). sequence space wrap is giving main character plot twist energy 😭🌈

it's also important that the sender responds correctly to duplicate ACKs it gets when it's no longer in Fast Recovery (for example, after a Retransmit Timeout) 💖 the Limited Transmit procedure [RFC3042] describes possible responses to the first and second duplicate acknowledgements. when three or more duplicate acknowledgements arrive, the Cumulative Acknowledgement field doesn't cover more than "recover", and a new Fast Recovery isn't invoked, the sender must NOT run Fast Recovery steps (3) and (4) in Section 3 ✨ wait, sorry, let me fix that: the sender should not run them. otherwise it could end up in a chain of spurious timeouts 💀 we only bring this up because several NewReno implementations had this exact bug, including the one in the NS simulator 🙈 (that NS bug got fixed in July 2003 with the variable "exitFastRetrans_" 👑)

9. Simulations 🦋

okay so simulations with NewReno are illustrated with the validation test tcl/test/test-all-newreno in the NS simulator 🧚 running ../../ns test-suite-newreno.tcl reno shows a simulation with Reno TCP, which highlights the data sender's lack of response to a partial acknowledgement 💀 then ../../ns test-suite-newreno.tcl newreno_B runs the same scenario using the NewReno algorithms from this paper ✨ the glow up is real 🔥

10. Comparisons between Reno and NewReno TCP 💅

as we said in the introduction, we believe this NewReno modification improves the performance of Reno's Fast Retransmit and Fast Recovery in a wide variety of scenarios 🌈 this got discussed in depth in [FF96], which shows Reno TCP's poor performance when multiple packets are dropped from one window of data, and also shows NewReno's good performance in that exact situation 😭

we do, however, know of ONE scenario where Reno TCP does better than NewReno TCP 🙈 we're including it for completeness. picture a scenario with no packet loss but enough reordering that the TCP sender gets three duplicate acknowledgements. that triggers Fast Retransmit and Fast Recovery. with Reno TCP or Sack TCP, you get one unnecessary retransmission of a single packet, plus a halving of the congestion window (shown on pages 4 and 6 of [F03]). with NewReno TCP though, the same reordering causes an unnecessary retransmission of an ENTIRE window of data (shown on page 5 of [F03]) 💀 rough

so yeah, Reno beats NewReno under reordering, but NewReno's big win with multiple packet drops usually outweighs that 💖 (Sack TCP is the preferred solution, with good performance in both scenarios 👑). this document recommends NewReno's Fast Retransmit and Fast Recovery algorithms instead of Reno's for TCP connections that don't support SACK 🎀 and NewReno's mechanisms are widely deployed in TCP implementations on the Internet today, as documented in [PF01] 🌸 for example, tests of TCP implementations in several thousand web servers in 2001 showed that, for TCP connections where the web browser wasn't SACK-capable, more web servers used NewReno's Fast Retransmit and Fast Recovery than Reno's or Tahoe's [PF01] ✨ the receipts are IN 🧾

11. Changes Relative to RFC 2582 🎀

the purpose of this document is to advance NewReno's Fast Retransmit and Fast Recovery algorithms from RFC 2582 to Standards Track 🚀

the main change relative to RFC 2582 is specifying the Careful variant of NewReno's Fast Retransmit and Fast Recovery algorithms 💅 the base algorithm in RFC 2582 didn't try to avoid unnecessary multiple Fast Retransmits that can happen after a timeout (more detail in the section above 🙈). RFC 2582 did define "Careful" and "Less Careful" variants that avoid those unnecessary Fast Retransmits, and it recommended the Careful one 🌈 this document specifies the previously-named "Careful" variant as the basic version of NewReno 👑 as described below, this algorithm uses a variable "recover", whose initial value is the send sequence number 🦋

the algorithm in Section 3 checks whether the acknowledgement field of a partial acknowledgement covers more than "recover", as defined in Section 3 ✨ another possible variant would be to just require that the acknowledgement field covers more than or equal to "recover" before starting another Fast Retransmit. we called that the Less Careful variant in RFC 2582 🧚

there are two separate scenarios where the TCP sender could get three duplicate acknowledgements acknowledging "recover" but nothing more than "recover" 😭 scenario one: the data sender transmitted four packets with sequence numbers higher than "recover", the first one got dropped in the network, and the next three triggered three duplicate acknowledgements acknowledging "recover". scenario two: the sender unnecessarily retransmitted three packets below "recover", and those three packets triggered three duplicate acknowledgements acknowledging "recover". 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 scenario one, but it avoids an unnecessary Fast Retransmit in scenario two 💖 with the Less Careful variant, the sender Fast Retransmits like it should in scenario one, but it unnecessarily Fast Retransmits in scenario two 🙈 this document only specifies the Careful variant in Section 3 ✨ unnecessary Fast Retransmits with the Less Careful variant in reordering scenarios are illustrated on page 8 of [F03] 🌸

the document also specifies two heuristics that the TCP sender MAY use to decide to invoke Fast Retransmit even when the three duplicate acknowledgements don't cover more than "recover" 🫶 these are an ACK-based heuristic and a timestamp heuristic, described in Sections 6.1 and 6.2 respectively 🔥

12. Conclusions 👑

this document specifies the NewReno Fast Retransmit and Fast Recovery algorithms for TCP 💅 this NewReno modification can even matter for TCP implementations that support the SACK option, because SACK can only be used on a TCP connection when BOTH TCP end-nodes support SACK 🙈 NewReno performs better than Reno (RFC 2581) in a number of scenarios discussed here 🌈

a bunch of options to the basic algorithm in Section 3 are also described 🦋 these include handling the retransmission timer (Section 4), the response to partial acknowledgments (Section 5), and the value of the congestion window when leaving Fast Recovery (section 3, step 5) ✨ our belief is that the differences between these NewReno variants are small compared to the differences between Reno and NewReno 💖 so the important thing is to implement NewReno instead of Reno for a TCP connection without SACK 🎀 it's less important exactly which NewReno variant you pick 🧚

13. Security Considerations 💀

okay this one's serious, bestie 🫶 RFC 2581 discusses general security considerations for 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 ✨

14. Acknowledgements 🌸

many thanks to Anil Agarwal, Mark Allman, Armando Caro, Jeffrey Hsu, Vern Paxson, Kacheong Poon, Keyur Shah, and Bernie Volz for detailed feedback on this document or on its precursor, RFC 2582 🫶💜

15. References 📚

15.1. Normative References

[RFC2018] Mathis, M., Mahdavi, J., Floyd, S. and A. Romanow, "TCP
          Selective Acknowledgement Options", RFC 2018, October 1996.

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
          Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC2581] Allman, M., Paxson, V. and  W. Stevens, "TCP Congestion
          Control", RFC 2581, April 1999.

[RFC2582] Floyd, S. and T. Henderson, "The NewReno Modification to
          TCP's Fast Recovery Algorithm", RFC 2582, April 1999.

[RFC2988] Paxson, V. and M. Allman, "Computing TCP's Retransmission
          Timer", RFC 2988, November 2000.

[RFC3042] Allman, M., Balakrishnan, H. and S. Floyd, "Enhancing TCP's
          Loss Recovery Using Limited Transmit", RFC 3042, January
          2001.

15.2. Informative References ✨

okay so these are the "extra reading" references, the ones that aren't required to implement anything but give the backstory, the experiments, and the mailing list drama behind the spec 💅🎀

  • [C98] Cardwell, N., "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] Floyd, S., 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". 🌸
  • [F03] Floyd, S., "Moving NewReno from Experimental to Proposed Standard? Presentation to the TSVWG Working Group", March 2003. URLs "http://www.icir.org/floyd/talks/newreno-Mar03.ps" and "http://www.icir.org/floyd/talks/newreno-Mar03.pdf". 🦋
  • [FF96] Fall, K. and S. 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". 📚
  • [F94] Floyd, S., "TCP and Successive Fast Retransmits", Technical report, October 1994. URL "ftp://ftp.ee.lbl.gov/papers/fastretrans.ps". 🧚
  • [GF04] Gurtov, A. and S. Floyd, "Resolving Acknowledgment Ambiguity in non-SACK TCP", Next Generation Teletraffic and Wired/Wireless Advanced Networking (NEW2AN'04), February 2004. URL "http://www.cs.helsinki.fi/u/gurtov/papers/heuristics.html". 🔥
  • [Gur03] Gurtov, A., "[Tsvwg] resolving the problem of unnecessary fast retransmits in go-back-N", email to the tsvwg mailing list, message ID <3F25B467.9020609@cs.helsinki.fi>, July 28, 2003. URL "http://www1.ietf.org/mail-archive/working-groups/tsvwg/current/msg04334.html". 💜
  • [Hen98] Henderson, T., 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] Hoe, J., "Startup Dynamics of TCP's Congestion Control and Avoidance Schemes", Master's Thesis, MIT, 1995. 🎓
  • [Hoe96] Hoe, J., "Improving the Start-up Behavior of a Congestion Control Scheme for TCP", ACM SIGCOMM, August 1996. URL "http://www.acm.org/sigcomm/sigcomm96/program.html". ⭐
  • [LM97] Lin, D. and R. Morris, "Dynamics of Random Early Detection", SIGCOMM 97, September 1997. URL "http://www.acm.org/sigcomm/sigcomm97/program.html". 🌈
  • [NS] The Network Simulator (NS). URL "http://www.isi.edu/nsnam/ns/". 🍓
  • [PF01] Padhye, J. and S. Floyd, "Identifying the TCP Behavior of Web Servers", June 2001, SIGCOMM 2001. 🫶
  • [RFC1323] Jacobson, V., Braden, R. and D. Borman, "TCP Extensions for High Performance", RFC 1323, May 1992. 💖
  • [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. ✨
  • [RFC3522] Ludwig, R. and M. Meyer, "The Eifel Detection Algorithm for TCP", RFC 3522, April 2003. 🎀

Authors' Addresses 🦋

Sally Floyd International Computer Science Institute

Phone: +1 (510) 666-2989 EMail: floyd@acm.org URL: http://www.icir.org/floyd/

Tom Henderson The Boeing Company

EMail: thomas.r.henderson@boeing.com

Andrei Gurtov TeliaSonera

EMail: andrei.gurtov@teliasonera.com

Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.

Intellectual Property 🧚

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.

Acknowledgement 🌸

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

📦 where this page comes from