Flow Control and Congestion

In October 1986, the link between Lawrence Berkeley Laboratory and the University of California at Berkeley, two sites 400 yards apart, fell from 32 kilobits a second to 40 bits a second. Nothing had broken. Every sender was retransmitting into full queues, and the network spent its capacity carrying copies that would be dropped again. Sending faster had made everyone slower, by a factor of almost a thousand.

A sliding window says how much a sender may have in flight, but not how large that window should be. Two things limit it, and they are different in kind. The receiver's buffer is a limit the receiver knows and can state. The network's queues are a limit nobody states, which the sender has to discover by probing. Keeping the two apart leads to additive increase and multiplicative decrease, the rule that has kept the second one from collapsing since 1988.

Flow Control: The Receiver's Limit

A receiver has a buffer of fixed size, and a slow consumer drains it slowly. With every acknowledgement the receiver advertises how much room it has left, and the sender never has more unacknowledged data in flight than that. When Lantern falls behind applying feed messages, its advertised room shrinks toward zero, and every branch slows down to match instead of overrunning it.

The same idea runs through every bounded queue in software, under the name backpressure. A producer that finds a bounded queue full has to wait or give up, so the slow stage sets the pace of the fast one. The ring buffer in Chapter 5 is one such queue when its policy for a full buffer is to make the writer wait.

Congestion: The Network's Limit

Between sender and receiver sit routers whose queues are shared with everyone else's traffic. When packets arrive at a router faster than its outgoing link can send them, the queue grows, and when the queue is full the router drops. No router tells a sender what rate the path can carry. The sender has to infer it, from loss or from delay that rises as queues fill.

That inference is the hard part. A sender that sees no loss cannot tell whether the path has room to spare or is one packet from overflowing. The only way to find the limit is to go slightly over it, see the loss and back off.

Congestion Collapse

The 1986 collapse was a failure of that feedback. Senders answered loss by resending sooner and harder, and every resend arrived at a queue that was already full. The network filled with retransmissions of packets that would be dropped again, so useful throughput fell toward zero while every link stayed busy.

Van Jacobson and Michael Karels described the fix in "Congestion Avoidance and Control", presented in 1988. Senders were made to treat loss as a signal of congestion and to back off, and a new connection was made to start slowly and grow. The internet has run on that behaviour ever since.

AIMD

The rule is additive increase, multiplicative decrease. While things go well, the sender adds a small, fixed amount to its window every round trip. On a loss, it halves the window. The result is the sawtooth below: a slow climb toward what the path can carry, a sharp drop when it overflows and another climb.

The simulation in the figure starts with slow start, which doubles the window every round trip so that a new connection finds its rate in a few round trips instead of minutes. It overshoots the path's capacity of 40 packets at round trip 6 and loses. From then on the window grows by one packet per round trip and halves at each loss, at round trips 16 and 38, hovering around the capacity line.

The deeper reason for this particular pair came from Dah-Ming Chiu and Raj Jain in 1989. Two senders sharing a link both add the same amount when they increase, which keeps the gap between them the same, and both halve when they decrease, which halves the gap. Every cycle shrinks the difference, so the senders converge on equal shares whatever their starting point. Additive decrease would keep the gap, and multiplicative increase would widen it.

The figure plots the two senders' rates against each other. The pair starts with flow A at ten times flow B's rate. Each increase moves it diagonally up toward the full-link line, and each halving moves it straight toward the origin, which shrinks the gap. After a few cycles the path is running along the equal-shares diagonal.

Queues That Are Too Big

A buffer that never drops hides congestion as delay. A home router with seconds of buffering keeps a large upload flowing at full speed while every video call on the same line lags by a second, because each call's packets wait behind the upload's. Jim Gettys named this bufferbloat around 2010. Loss-based senders fill any buffer they are given, since they increase until something drops, so a bigger buffer only makes the delay longer.

Newer congestion control algorithms therefore watch delay as well as loss. Google's BBR, published in 2016, estimates the path's bandwidth and round trip directly and tries to keep queues short. The algorithms themselves, and how to choose between them, belong to Networking Deep Dive's topic on congestion control.

Congestion Control in Application Code

A client that retries every failure immediately is a sender without congestion control. When a dependency slows down, its retries multiply the load at the worst moment, and a thousand clients doing the same keep the dependency down long after the original problem is gone. Exponential backoff with random jitter, the practice Backend Deep Dive teaches in "Retries, Backoff and Jitter", is AIMD's cousin in application code.

An unbounded in-memory queue in a service is bufferbloat in software. Under sustained overload it grows, every request waits longer, and eventually the process runs out of memory. A bounded queue that rejects work when full is flow control, and backoff on failure is congestion control. Both replace a slow, invisible failure with a fast, visible "no".