RFC 896

Congestion Control in IP/TCP Internetworks 🎀

Network Working Group RFC 896, by John Nagle, Ford Aerospace and Communications Corporation, 6 January 1984 💖

okay bestie, the header says this one came from John Nagle at Ford Aerospace and Communications Corporation on 6 January 1984 📅. it doesn't list a category, but the memo says it's meant to stimulate thought and further discussion, and it does not specify any standards 🧠. it also doesn't say it obsoletes or updates anything, so it's a fresh start 🌸

---

Introduction ✨

okay so congestion control is a known problem in complex networks 🌐. the team found that the Department of Defense's Internet Protocol (IP), which is a pure datagram protocol, and Transmission Control Protocol (TCP), which is a transport layer protocol, get unusual congestion problems when they're used together 😭. the trouble comes from interactions between the transport and datagram layers. IP gateways are especially vulnerable to something they call "congestion collapse" 💀, especially when those gateways connect networks with very different bandwidth. the good news is they came up with solutions that actually prevent congestion collapse 🫶

now, why doesn't everyone notice this? because these protocols are mostly used on networks built on top of ARPANET IMP technology 🛰️. ARPANET IMP networks usually have uniform bandwidth and identical switching nodes, and they're built with a lot of spare capacity. that spare capacity, plus the IMP system's ability to throttle host transmissions, has been enough for most IP/TCP hosts and networks to handle congestion 🌈. but then the ARPANET split into two interconnected networks, and other networks with different properties started connecting to it. so relying on the friendly behavior of the IMP system isn't enough anymore if hosts want to communicate quickly and reliably 🏃‍♀️💨. better congestion handling is now mandatory for a network to work well under load 👑

Ford Aerospace and Communications Corporation, and its parent company Ford Motor Company, run the only private IP/TCP long-haul network that exists today 🚗. this network connects four facilities: one in Michigan, two in California, and one in England, and some of them have big local networks too 🏢. the net is cross-tied to the ARPANET but uses its own long-haul circuits. traffic between Ford facilities travels over private leased circuits, including a leased transatlantic satellite connection 🛰️. all switching nodes are pure IP datagram switches with no node-to-node flow control, and all hosts run software that was either written or heavily modified by Ford or Ford Aerospace 🛠️. link bandwidth on this network varies a lot, from 1200 to 10,000,000 bits per second 📶. they haven't been able to afford the luxury of spare long-haul bandwidth like the ARPANET has, so their long-haul links are heavily loaded during peak periods. as a result, transit times of several seconds are pretty common on their network ⏳😩

because of the pure datagram setup, heavy loading, and wide bandwidth variation, they had to solve problems that the ARPANET/MILNET community is only just starting to notice 🔍. their network is sensitive to suboptimal behavior by host TCP implementations, both on and off their own net. they spent a lot of effort looking at TCP behavior under different conditions, and they solved some very widespread TCP problems 🧩. this memo presents two problems and their solutions 🎯. many TCP implementations have these problems. if throughput through an ARPANET/MILNET gateway is worse than throughput across a single net for a given TCP implementation, there's a high chance that the implementation has one or both of these problems 🚨

---

Congestion collapse 💥

before we get into the two specific problems and their solutions, we need to talk about what happens when these problems aren't addressed 📝. in heavily loaded pure datagram networks with end-to-end retransmission, switching nodes get congested. the round-trip time through the net goes up, and the number of datagrams in transit inside the net also goes up 📈. this is normal behavior under load 🙂. as long as there's only one copy of each datagram in transit, congestion is still under control ✅. but once hosts start retransmitting datagrams that haven't been delivered yet, things can get seriously bad 😱

host TCP implementations are expected to retransmit packets several times, at increasing time intervals, until some upper limit on the retransmit interval is reached 🔁. normally, that's enough to prevent serious congestion problems 👍. even with better adaptive host retransmission algorithms, though, a sudden load on the net can make the round-trip time rise faster than the sending host's round-trip time measurements can be updated 🌊. this happens when a new bulk transfer, like a file transfer, starts filling a large window 📦. if the round-trip time goes past the maximum retransmission interval for any host, that host starts putting more and more copies of the same datagrams into the net 🙀. the network is now in serious trouble 🚑. eventually all the available buffers in the switching nodes get full, and packets have to be dropped 🗑️. the round-trip time for packets that do get delivered is now at its maximum ⏰. hosts are sending each packet several times, and eventually some copy of each packet arrives at its destination. this is congestion collapse 💀💜

this condition is stable 🧱. once the saturation point has been reached, the network keeps running in a degraded state as long as the algorithm for picking which packets to drop is fair 🤷‍♀️. in this state, every packet is sent several times, and throughput drops to a tiny fraction of normal 📉. the team pushed their own network into this condition on purpose and watched it stay stuck there 🧪. it's also possible for the round-trip time to get so large that connections break because the hosts involved time out ⌛

congestion collapse and pathological congestion aren't normally seen in the ARPANET/MILNET system, because those networks have a lot of spare capacity 🌷. where connections don't pass through IP gateways, the IMP-to-host flow control mechanisms usually prevent congestion collapse. this works especially well because TCP implementations tend to be tuned for the time constants of the pure ARPANET case 🎀. however, apart from ICMP Source Quench messages, nothing fundamentally prevents congestion collapse when TCP runs over the ARPANET/MILNET and packets are being dropped at gateways 🙅‍♀️. it's also worth noting that a few badly behaved hosts can, all by themselves, congest the gateways and stop other hosts from passing traffic 😤. the team has seen this problem many times with certain hosts on the ARPANET, and they've talked privately with those hosts' administrators 🤫

adding more memory to the gateways won't fix the problem 🧠❌. the more memory you add, the longer round-trip times have to get before packets are dropped. so the onset of congestion collapse is delayed, but when collapse does happen, an even larger fraction of the packets in the net are duplicates, and throughput gets even worse 💔

---

The two problems 🧩

two key problems with the engineering of TCP implementations have been observed 👀. the team calls them the small-packet problem and the source-quench problem. the second one is being addressed by several implementors. the first one is generally believed (incorrectly) to be solved already 🙃. they found that once the small-packet problem is solved, the source-quench problem becomes much more manageable 💪. so they present the small-packet problem and their solution to it first 🥇

The small-packet problem 🔬

small packets come with a special problem 😬. when TCP is used to send single-character messages typed at a keyboard, the typical result is that 41 byte packets (one byte of data and 40 bytes of header) get sent for each byte of useful data 🤯. that's a 4000% overhead. it's annoying but tolerable on lightly loaded networks 😌. on heavily loaded networks, though, the congestion caused by this overhead can lead to lost datagrams and retransmissions, plus excessive propagation time from congestion in switching nodes and gateways 🚦. in practice, throughput can drop so low that TCP connections get aborted 💔

this classic problem is well known. it was first addressed in the Tymnet network in the late 1960s 🕰️. the solution used there was to limit the number of datagrams generated per unit time. the limit was enforced by delaying the transmission of small packets for a short time (200-500ms), in the hope that another character or two would show up to be added to the same packet before the timer ran out ⏱️. an extra feature for user-friendliness was to skip the time delay when a control character, such as a carriage return, was received 💅

this technique has been used in NCP Telnet, X.25 PADs, and TCP Telnet 📟. its advantage is that it's well understood and not too hard to implement 👍. its flaw is that it's really hard to pick a time limit that satisfies everyone 🙈. a time limit short enough to give highly responsive service over a 10M bits per second Ethernet will be too short to prevent congestion collapse on a heavily loaded net with a five second round-trip time 🚫. and the reverse is also true: a time limit long enough to handle the heavily loaded net will frustrate users on the Ethernet 😩

The solution to the small-packet problem 💡

clearly, an adaptive approach is desirable 🌟. you'd expect a proposal for an adaptive inter-packet time limit based on the round-trip delay observed by TCP. while such a mechanism could certainly be implemented, it's unnecessary 🙌. a simple and elegant solution has been found 🫧

the solution is to inhibit the sending of new TCP segments when new outgoing data arrives from the user, if any previously transmitted data on the connection remains unacknowledged 🛑. this inhibition is to be unconditional. no timers, tests for the size of data received, or other conditions are required. implementation typically takes one or two lines inside a TCP program 🤏

at first glance, this solution seems to imply drastic changes to the behavior of TCP 😳. it isn't so. it all works out right in the end 💖. let's see why 🔍

when a user process writes to a TCP connection, TCP receives some data 📨. it may hold that data for future sending, or it may send a packet immediately. if it holds off sending now, it will typically send the data later, when an incoming packet arrives and changes the state of the system 🔄. the state can change in one of two ways. the incoming packet either acknowledges old data the distant host has received, or it announces the availability of buffer space in the distant host for new data (this last one is called "updating the window") 🪟. each time data arrives on a connection, TCP has to reexamine its current state and maybe send some packets out 🧐. so when we skip sending data on arrival from the user, we're really just deferring its transmission until the next message arrives from the distant host. a message must always arrive soon, unless the connection was previously idle or communications with the other end have been lost 📬. in the first case, the idle connection, our scheme will result in a packet being

sent whenever the user writes to the TCP connection, so we totally don't deadlock in the idle condition 💅. In the second case, where the far host has died, sending more data is pointless anyway 💀. ngl we didn't touch the normal TCP retransmission logic at all, so lost messages are still not a problem 🔁.

Okay so we tested this scheme under a bunch of different conditions and it works in every single case 🎀. The first one we wanted to fix was the character-oriented Telnet connection 🍓. Let's say the user is sending TCP a new character every 200ms, and the connection runs over an Ethernet with a round-trip time of 50ms, software processing included ✨. Without any mechanism to prevent small-packet congestion, one packet gets sent for each character, and the response is optimal 🦋. The overhead is 4000%, but on an Ethernet that's acceptable 🙈. The classic timer scheme, with a limit of 2 packets per second, causes two or three characters to be sent per packet. The response gets degraded even though on a high-bandwidth Ethernet that's unnecessary 😭. The overhead drops to 1500%, but on an Ethernet that's a bad tradeoff 💔. With our scheme, every character the user types finds TCP with an idle connection, so the character goes out right away, just like in the no-control case ⚡. The user sees no visible delay 🫶. So our scheme performs as well as the no-control scheme and gives better responsiveness than the timer scheme 👑.

The second case is the same Telnet test, but over a long-haul link with a 5-second round-trip time 🌈. Without any mechanism to prevent small-packet congestion, 25 new packets would be sent in 5 seconds.* The overhead here is 4000% 😱. With the classic timer scheme and the same limit of 2 packets per second, there would still be 10 packets outstanding and adding to congestion 🚧. Sending lots of packets won't improve the round-trip time, of course. In general it gets worse, because the packets fight for line time 🥲. The overhead drops to 1500% now. With our scheme, though, the first character from the user finds an idle TCP connection and gets sent immediately 🚀. The next 24 characters, arriving from the user at 200ms intervals, get held until a message comes back from the distant host ⏳. When the ACK for the first packet arrives at the end of 5 seconds, a single packet with the 24 queued characters goes out 📦. So our scheme cuts the overhead down to 320% with no penalty in response time 🙌. The response time usually gets better with our scheme because the packet overhead is smaller, here by a factor of 4.7 over the classic timer scheme 📉. Congestion drops by this same factor, and the round-trip delay falls sharply 🔥. For this case, our scheme has a striking advantage over either of the other approaches 😤.

* This problem is not seen in the pure ARPANET case, because the IMPs will block the host when the count of packets outstanding becomes excessive. But when a pure datagram local net (such as an Ethernet) or a pure datagram gateway (such as an ARPANET / MILNET gateway) is involved, it is possible to have large numbers of tiny packets outstanding 👀.

We use our scheme for all TCP connections, not just Telnet connections 💖. Let's see what happens for a file transfer data connection using our technique 📁. Again we'll look at the two extreme cases.

As before, we start with the Ethernet case 🌸. The user is now writing data to TCP in 512 byte blocks, as fast as TCP will accept them 🏃‍♀️. The user's first write starts things going. Our first datagram is 512+40 bytes, or 552 bytes long 📨. The user's second write doesn't cause a send, but it does cause the block to be buffered 🧺. Assume the user fills up TCP's outgoing buffer area before the first ACK comes back 🪣. Then, when the ACK comes in, all the queued data up to the window size gets sent 💨. From then on, the window stays full, because each ACK kicks off a sending cycle and the queued data goes out 🔁. So after a one-round-trip-time startup period, when only one block is sent, our scheme settles into a maximum-throughput condition 🏆. The startup delay is only 50ms on the Ethernet, so the startup transient is insignificant 🤏. All three schemes give equivalent performance in this case 🤝.

Finally, let's look at a file transfer over the 5-second round-trip time connection 🐢. Again, only one packet gets sent until the first ACK comes back. Then the window gets filled and kept full 🪟. Since the round-trip time is 5 seconds, only 512 bytes of data get transmitted in the first 5 seconds 😩. Assuming a 2K window, once the first ACK comes in, 2K of data gets sent, and a steady rate of 2K per 5 seconds is maintained after that 📊. This is the only case where our scheme is worse than the timer scheme, and the difference is only in the startup transient. The steady-state throughput is identical 🫠. The naive scheme and the timer scheme would both take 250 seconds to transmit a 100K byte file under the conditions above. Our scheme would take 254 seconds, a difference of 1.6% 🧮.

So for all the cases we examined, our scheme gives at least 98% of the performance of both other schemes, and it gives a dramatic improvement in Telnet performance over paths with long round-trip times 🚀✨. We use our scheme in the Ford Aerospace Software Engineering Network, and we can run screen editors over Ethernet and talk to distant TOPS-20 hosts with improved performance in both cases 🖥️💜.

---

Congestion control with ICMP 🚦

Okay, so now that we've solved the small-packet congestion problem, and with it the problem of excessive small-packet congestion inside our own network, we turned to general congestion control 🧠. Our own network is pure datagram with no node-to-node flow control. So the only mechanism available to us under the IP standard was the ICMP Source Quench message 📮. With careful handling, we find this is adequate to prevent serious congestion problems 👍. We do find it necessary to be careful about how our hosts and switching nodes behave regarding Source Quench messages ⚠️.

When to send an ICMP Source Quench 🫧

The present ICMP standard* says that an ICMP Source Quench message should be sent whenever a packet is dropped, and it may additionally be sent when a gateway finds itself becoming short of resources 📜. There's some ambiguity here, but clearly it is a violation of the standard to drop a packet without sending an ICMP message 🙅‍♀️.

Our basic assumption is that packets ought not to be dropped during normal network operation 🌷. So we want to throttle senders back before they overload switching nodes and gateways 🛑. All our switching nodes send ICMP Source Quench messages well before buffer space is exhausted. They don't wait until it's necessary to drop a message before sending one 💨. As we showed in our analysis of the small-packet problem, merely providing large amounts of buffering is not a solution 🙅‍♀️. In general, our experience is that Source Quench should be sent when about half the buffering space is exhausted 🌓. This isn't based on extensive experimentation, but it appears to be a reasonable engineering decision 🤓. One could argue for an adaptive scheme that adjusted the quench generation threshold based on recent experience. We haven't found that necessary as yet 🤷‍♀️.

There exist other gateway implementations that generate Source Quenches only after more than one packet has been discarded. We consider this approach undesirable, since any system for controlling congestion based on discarding packets is wasteful of bandwidth and may be susceptible to congestion collapse under heavy load 🗑️📉. Our understanding is that the decision to generate Source Quenches with great reluctance stems from a fear that acknowledge traffic will be quenched, and that this will result in connection failure 😨. As will be shown below, appropriate handling of Source Quench in host implementations eliminates this possibility 🙌.

What to do when an ICMP Source Quench is received 📬

We inform TCP, or any other protocol at that layer, when ICMP receives a Source Quench 📣. The basic action of our TCP implementations is to reduce the amount of data outstanding on connections to the host mentioned in the Source Quench 🫳. This control is applied by causing the sending TCP to behave as if the distant host's window size has been reduced 🪟. Our first implementation was simplistic but effective. Once a Source Quench has been received, our TCP behaves as if the window size is zero whenever the window isn't empty 🥹. This behavior continues until some number (at present 10) of ACKs have been received. At that time, TCP returns to normal operation* 🔄. David Mills of Linkabit Corporation has since implemented a similar but more elaborate throttle on the count of outstanding packets in his DCN systems 🛠️. The additional sophistication seems to produce a modest gain in throughput, but we have not made formal tests 🧪. Both implementations effectively prevent congestion collapse in switching nodes 💪.

* ARPANET RFC 792 is the present standard. We are advised by the Defense Communications Agency that the description of ICMP in MIL-STD-1777 is incomplete and will be deleted from future revisions of that standard 📝.

Source Quench thus has the effect of limiting the connection to a limited number (perhaps one) of outstanding messages 🎯. So communication can continue, just at a reduced rate. That's exactly the effect we want 💅.

This scheme has the important property that Source Quench doesn't inhibit the sending of acknowledges or retransmissions 🫶. Implementations of Source Quench entirely within the IP layer are usually unsuccessful, because IP lacks enough information to throttle a connection properly 😵‍💫. Holding back acknowledges tends to produce retransmissions and therefore unnecessary traffic 🔁. Holding back retransmissions may cause a connection to be lost through a retransmission timeout 💀. Our scheme keeps connections alive under severe overload, just at reduced bandwidth per connection 🦋.

Other protocols at the same layer as TCP should also be responsive to Source Quench 🌈. In each case, we would suggest that new traffic should be throttled, but acknowledges should be treated normally 📨. The only serious problem comes from the User Datagram Protocol, which isn't normally a major traffic generator 🙃. We haven't implemented any throttling in these protocols as yet. All of them are passed Source Quench messages by ICMP, but they ignore them 🙈.

Self-defense for gateways 🛡️

As we have shown, gateways are vulnerable to host mismanagement of congestion 🥺. Host misbehavior, through excessive traffic generation, can prevent not only the host's own traffic from getting through, but can also interfere with other unrelated traffic 😤. The problem can be dealt with at the host level. But since one malfunctioning host can interfere with others, future gateways should be capable of defending themselves against this kind of behavior by obnoxious or malicious hosts 👿🛡️. We offer some basic self-defense techniques 🔥.

On one occasion in late 1983, a TCP bug in an ARPANET host caused the host to frantically generate retransmissions of the same datagram as fast as the ARPANET would accept them 😱. The gateway* that connected our net with the ARPANET was saturated, and little

* This follows the control engineering dictum "Never bother with proportional control unless bang-bang doesn't work".

useful traffic could get through 💅, because the gateway had more bandwidth to the ARPANET than to our net 🌸 The gateway busily sent ICMP Source Quench messages 📨, but the malfunctioning host just ignored them 🙄. This went on for several hours, until the malfunctioning host finally crashed 💀. The whole time, our network was effectively disconnected from the ARPANET 😭

When a gateway has to discard a packet, it gets to pick which one goes at its own discretion 🧚 The classic moves are to toss the most recently received packet, or the packet at the end of the longest outgoing queue. We think a more practical move is to discard the latest packet from whichever host has the most packets currently queued up inside the gateway 🎀 This strategy should tend to balance throughput among the hosts using the gateway ⚖️ We haven't actually tried it yet, but it seems like a reasonable starting point for gateway self-protection 🛡️✨

Another strategy is to discard a newly arrived packet if that packet duplicates one already sitting in the queue 🍓 The computational load for this check isn't a problem if hashing techniques are used 🧮 It won't protect you from malicious hosts 🙅‍♀️, but it does give some protection against TCP implementations with poor retransmission control 🔁 Gateways sitting between fast local networks and slower long-haul networks may find this check valuable 💜, especially if the local hosts are tuned to work well with the local network 🦋

Ideally, the gateway should detect malfunctioning hosts and squelch them 🤫 but detection like that is hard in a pure datagram system 😩 Still, failing to respond to an ICMP Source Quench message should be regarded as grounds for a gateway to take action and disconnect a host 🚪 Detecting that failure is non-trivial, but it's a worthwhile area for further research 🔬🌈

---

Conclusion ✨

The congestion control problems associated with pure datagram networks are difficult 😤, but effective solutions exist 👑 If IP / TCP networks are going to be operated under heavy load, TCP implementations must address several key issues in ways that are at least as effective as the ones described here 💖 No pressure, bestie 🫶💅