RFC 2001

✨ RFC 2001: TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms 🎀

Okay bestie, the header says this one is by W. Stevens of NOAO 💅, it's on the Standards Track 🛤️, and it's dated January 1997 📅. The header doesn't list anything it obsoletes or updates 🤷‍♀️.

---

Status of This Memo 📣

This doc is an Internet standards track protocol for the Internet community, and it's literally asking for discussion and suggestions for improvements 💬. For where it stands in the standardization world, check the current edition of the "Internet Official Protocol Standards" (STD 1) 📚. Distribution of this memo is unlimited 🌈.

Abstract 🧠

Okay so modern TCP has four intertwined algorithms that were never fully documented as Internet standards 😭: slow start, congestion avoidance, fast retransmit, and fast recovery. [2] and [3] give some details on them, [4] has examples of them in action 🎬, and [5] has the source code for the 4.4BSD implementation 💻. RFC 1122 says a TCP must implement slow start and congestion avoidance (Section 4.2.2.15 of [1]), citing [2] as the reference 📖. Fast retransmit and fast recovery came along after RFC 1122 though 🍓. So the whole mission of this doc is to document all four for the Internet 🫶.

Acknowledgments 🙌

A lot of this memo is borrowed from "TCP/IP Illustrated, Volume 1: The Protocols" by W. Richard Stevens (Addison-Wesley, 1994) and "TCP/IP Illustrated, Volume 2: The Implementation" by Gary R. Wright and W. Richard Stevens (Addison-Wesley, 1995) 📕. It's used with the permission of Addison-Wesley 🦋. The four algorithms described here were developed by Van Jacobson 👑.

1. Slow Start 🐢

Old TCPs would start a connection by shoving multiple segments into the network all at once, up to the window size the receiver advertised 🙈. That's totally fine when both hosts are on the same LAN. But if there are routers and slower links in between, things can go sideways 😬. An intermediate router has to queue the packets, and it's possible for that router to run out of space. [2] shows how this naive approach can drastically reduce the throughput of a TCP connection 📉.

The fix is called slow start ✨. The big idea is that the rate at which new packets should be injected into the network is the rate at which the acknowledgments come back from the other end 🔁.

Slow start adds another window to the sender's TCP, called the congestion window, or "cwnd" 🪟. When a new connection is set up with a host on another network, cwnd starts at one segment. That's the segment size announced by the other end, or the default, which is typically 536 or 512 🍼. Each time an ACK arrives, cwnd goes up by one segment. The sender can transmit up to the minimum of cwnd and the advertised window. Cwnd is flow control imposed by the sender based on how congested the network looks to it 👀. The advertised window is flow control imposed by the receiver, tied to how much buffer space the receiver has for this connection 🧺.

The sender starts by sending one segment and waiting for its ACK 🐣. Once that ACK lands, cwnd goes from one to two, so two segments can go out. When both are acknowledged, cwnd jumps to four 📈. That's exponential growth, though it's not exactly exponential, because the receiver may delay its ACKs, typically sending one ACK for every two segments it gets 🤏.

At some point the capacity of the internet can be reached, and an intermediate router starts discarding packets 💥. That tells the sender its cwnd has gotten too large 🙃.

Early implementations only did slow start when the other end was on a different network. Current implementations always do slow start 🧠.

2. Congestion Avoidance 🌊

Congestion can happen when data arrives on a big pipe, like a fast LAN, and gets sent out a smaller pipe, like a slower WAN 🚰. It can also happen when multiple input streams hit a router whose output capacity is less than the sum of those inputs 🌪️. Congestion avoidance is a way to deal with lost packets 🫠, and it's described in [2].

The algorithm assumes that packet loss from damage is very small, much less than 1%. So when a packet is lost, that signals congestion somewhere between source and destination 🚨. There are two indications of packet loss: a timeout happens, or duplicate ACKs get received 👯.

Congestion avoidance and slow start are independent algorithms with different objectives 🎯. But when congestion happens, TCP must slow down its transmission rate of packets into the network, and then invoke slow start to get things going again 🔄. In practice, they're implemented together 🫶.

Congestion avoidance and slow start need two variables kept for each connection: the congestion window, cwnd, and the slow start threshold size, ssthresh. The combined algorithm works like this:

1. Initialization for a given connection sets cwnd to one segment and ssthresh to 65535 bytes 🎬.
2. The TCP output routine never sends more than the minimum of cwnd and the receiver's advertised window 🚧.
3. When congestion happens (signaled by a timeout or the reception of duplicate ACKs), one-half of the current window size is saved in ssthresh. The current window size here is the minimum of cwnd and the receiver's advertised window, but at least two segments 🫙. Also, if the congestion is signaled by a timeout, cwnd is set to one segment, which means slow start 🐢.
4. When new data is acknowledged by the other end, cwnd increases. How it increases depends on whether TCP is doing slow start or congestion avoidance 🎢.

If cwnd is less than or equal to ssthresh, TCP is in slow start. Otherwise TCP is doing congestion avoidance 🪄. Slow start keeps going until TCP is halfway to where it was when congestion happened. That's because it recorded half of the window size that caused the problem in step 2. Then congestion avoidance takes over 🫡.

Slow start has cwnd begin at one segment and go up by one segment every time an ACK comes in. Like we said earlier, this opens the window exponentially: send one segment, then two, then four, and so on 🚀. Congestion avoidance says cwnd goes up by segsize*segsize/cwnd each time an ACK is received. Here segsize is the segment size, and cwnd is maintained in bytes 📏. That's linear growth, compared to slow start's exponential growth 🐌. The increase in cwnd should be at most one segment each round-trip time, no matter how many ACKs are received in that RTT. Slow start, on the other hand, increments cwnd by the number of ACKs received in a round-trip time 🔢.

Many implementations incorrectly add a small fraction of the segment size during congestion avoidance, typically the segment size divided by 8 🙅‍♀️. This is wrong, and it should not be emulated in future releases 🚫.

3. Fast Retransmit ⚡

Changes to the congestion avoidance algorithm were proposed in 1990 [3]. Before we get into the change, know that TCP may generate an immediate acknowledgment, which is a duplicate ACK, when an out-of-order segment arrives (Section 4.2.2.21 of [1], with a note that one reason for doing so was the experimental fast-retransmit algorithm) 🧩. This duplicate ACK should not be delayed 🏃‍♀️. Its purpose is to tell the other end that a segment came in out of order, and to say what sequence number it's expecting 🔢.

TCP can't tell whether a duplicate ACK comes from a lost segment or from just a reordering of segments. So it waits for a small number of duplicate ACKs to come in 🤔. The assumption is that if it's only reordering, there will be just one or two duplicate ACKs before the reordered segment gets processed, and that generates a new ACK 🔀. But if three or more duplicate ACKs arrive in a row, that's a strong indication that a segment was lost 😱. TCP then retransmits what appears to be the missing segment, without waiting for the retransmission timer to expire ⏰.

4. Fast Recovery 🚑

After fast retransmit sends what looks like the missing segment, congestion avoidance is performed, but slow start is not. This is the fast recovery algorithm 🫶. It's an improvement that allows high throughput under moderate congestion, especially with large windows 🏋️‍♀️.

Here's why slow start is skipped: receiving duplicate ACKs tells TCP more than just that a packet has been lost. The receiver can only generate a duplicate ACK when another segment arrives. So that segment has left the network and is sitting in the receiver's buffer 🧺. That means data is still flowing between the two ends, and TCP doesn't want to drop the flow abruptly by going into slow start 🙅‍♀️.

The fast retransmit and fast recovery algorithms are usually implemented together, like this:

1. When the third duplicate ACK in a row is received, set ssthresh to one-half the current congestion window, cwnd, but no less than two segments. Retransmit the missing segment. Then set cwnd to ssthresh plus 3 times the segment size. This inflates the congestion window by the number of segments that have left the network and which the other end has cached (3) 🎈.
2. Each time another duplicate ACK arrives, increment cwnd by the segment size. This inflates the congestion window for the additional segment that has left the network. Transmit a packet, if the new value of cwnd allows it 📦.
3. When the next ACK arrives that acknowledges new data, set cwnd to ssthresh (the value set in step 1). This ACK should be the acknowledgment of the retransmission from step 1, one round-trip time after the retransmission. Also, this ACK should acknowledge all the intermediate segments sent between the lost packet and the receipt of the first duplicate ACK 🧾. This step is congestion avoidance, since TCP is now down to one-half the rate it was at when the packet was lost 🐢.

The fast retransmit algorithm first appeared in the 4.3BSD Tahoe release, and it was followed by slow start 🏛️. The fast recovery algorithm appeared in the 4.3BSD Reno release 🌸.

5. Security Considerations 🔒

😱 Security considerations are not discussed in this memo. Not one word on them, so keep that in mind 🚨.

6. References 📚

[1] B. Braden, ed., "Requirements for Internet Hosts -- Communication Layers," RFC 1122, Oct. 1989.

[2] V. Jacobson, "Congestion Avoidance and Control," Computer Communication Review, vol. 18, no. 4, pp. 314-329, Aug. 1988. ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z.

[3] V. Jacobson, "Modified TCP Congestion Avoidance Algorithm," end2end-interest mailing list, April 30, 1990. ftp://ftp.isi.edu/end2end/end2end-interest-1990.mail.

[4] W. R. Stevens, "TCP/IP Illustrated, Volume 1: The Protocols", Addison-Wesley, 1994.

[5] G. R. Wright, W. R. Stevens, "TCP/IP Illustrated, Volume 2: The Implementation", Addison-Wesley, 1995.

Author's Address ✨

Okay bestie, this last bit is just the contact card for the author, W. Richard Stevens 🦋 He's the legend behind so much of the networking knowledge we're talking about, so here's how to reach him 💖

W. Richard Stevens
1202 E. Paseo del Zorro
Tucson, AZ  85718

Phone: 520-297-9416

EMail: rstevens@noao.edu
Home Page: http://www.noao.edu/~rstevens

And that's a wrap on RFC 2001! 🎀 Slow start, congestion avoidance, fast retransmit, and fast recovery all working together so the network doesn't get overwhelmed. Iconic 👑