Why the network asks senders to slow down

In October 1986, data between the Lawrence Berkeley Laboratory and UC Berkeley, two sites 400 yards apart, slowed from 32 kilobits per second to 40 bits per second. Van Jacobson and Michael Karels call it a “factor-of-thousand drop”. It was the first of a series of what they call congestion collapses - a phrase they credit to John Nagle - and their fix changed only the computers at the two ends, not the network.

The problem no one can solve for you

A sender on the internet cannot know how fast it should go. The right rate depends on the slowest link on the path, and on how many strangers are sharing it at that moment. The network does not keep track of either. Jacobson and Karels put it plainly: the network announces, by dropping a packet, when demand is too high, but “says nothing if a connection is using less than its fair share (since the network is stateless, it cannot know this).” So, they conclude, “a connection has to increase its bandwidth utilization to find out the current limit.” A sender that stops probing wastes whatever room other users free up. In their example you share a path with one other user, each of you using half, and she leaves: “50% of the bandwidth will be wasted unless your window size is increased.”

Why it matters

At the time, the authors note, it was common for internet gateways to drop 10% of the packets arriving at them. Their paper describes changes to the TCP code in 4.3BSD Berkeley Unix, and they start from one principle. A connection that is running steadily should not put a new packet into the network until an old packet leaves. The paper calls this the conservation of packets. Its trace figures show the difference. Four conversations shared a 25 kilobyte-per-second link. Without congestion avoidance, 4,000 of 11,000 packets sent were retransmissions. With it, 89 of 8,281 were, which the paper rounds to 1%.

The window, and three rules for it

TCP limits a sender with a window: the number of packets it may have in flight, sent but not yet acknowledged. The paper adds a second limit, the congestion window, cwnd, counted here in packets (real TCP counts bytes). Each acknowledgement that comes back frees a slot, so the returning acks set the pace of sending. The paper says the sender “uses acks as a ‘clock’”.

Slow-start. When starting, or restarting after a loss, set cwnd to one packet, then add one packet for every ack of new data. Each round trip returns one ack per packet, so the window doubles every round trip. Reaching a window of W packets takes about R log₂ W, where R is the round-trip time. For a window of 8 that is 3 round trips (our arithmetic). Despite the name, the paper notes, it “isn't that slow”.

Treat a loss as congestion. Packets are lost either to damage or to a full queue at a router somewhere on the path. Damage is rare, well under 1% on most paths, so it is, in their word, probable that a lost packet means congestion rather than damage. The sender notices a loss when its retransmission timer runs out, a signal the paper notes is delivered “by all existing networks, without special modification”.

Back off fast, climb slowly. Under congestion a queue grows exponentially, so senders must “throttle back at least as quickly as the queues are growing”: on a loss, multiply the window by a factor below one. The paper uses one half. With no congestion, add a small constant, one packet per round trip, done in code by adding 1/cwnd per ack. They borrowed this additive increase, multiplicative decrease from Jain, Ramakrishnan and Chiu (“We copied Jain’s scheme”). Increasing by a multiple instead “will oscillate wildly”, because it is “easy to drive the net into saturation but hard for the net to recover”.

What the paper actually does on a loss

Its Appendix B combines the rules with a second variable, ssthresh. On a timeout, half the current window is stored in ssthresh, and cwnd is set to one packet. The sender slow-starts back up to ssthresh, then climbs by one packet per round trip to probe for more bandwidth. So the window falls to one packet, not to half. The familiar zig-zag, where the window is halved and keeps climbing from there, is the later Reno behaviour. The paper lists “fast retransmit” only as an algorithm to be described in a coming RFC.

Why half? If the path was shared by one connection and now it is shared by two, “the bandwidth available to you has been reduced by half.” The authors are frank that the one-packet increase has less justification than the halving, and is “almost certainly too large.” On the Arpanet, windows settled at 8 to 12 packets.

In short

The network tells a sender only that it has gone too far, never that it could go faster. So every sender must creep upward until a packet is lost, then retreat sharply and start creeping again. In this paper, the retreat is a drop to one packet and a fast climb back to half the old window.