§3.7.1Classic TCP Congestion Control

The window, and the rate

The answer to the first question is a variable. The sender keeps a congestion window congestion window Simple A sender-side limit on unacknowledged data, set by what the network seems able to take. Precise cwnd: a variable kept only at the sender, which together with rwnd bounds the unacknowledged data by LastByteSent − LastByteAcked ≤ min{cwnd, rwnd}. Roughly, the sender may send cwnd bytes per round-trip time, so its rate is about cwnd/RTT. Unlike rwnd it appears in no header — the network never states it, the sender infers it. introduced in ch. 3 — open in glossary , cwnd, and obeys

$LastByteSent - LastByteAcked \le \min\{cwnd, rwnd\}$

For this section, assume the receive buffer is large enough that rwnd never binds; section 3.5.5 covered the case where it does. Assume too that the sender always has data to send.

cwnd = 1 segment × 500 bytes = 500 bytes
one window may be outstanding per round trip
rate ≈ cwnd / RTT = 500 × 8 bits / 200 ms
                  = 20.0 kbps
this is where every TCP connection starts — one segment per round trip

How it knows, and what it does about it

A loss event loss event Simple Either a timeout or three duplicate ACKs — TCP’s two ways of concluding a segment was lost. Precise The trigger for TCP to reduce its congestion window: the occurrence of either a timeout or the receipt of three duplicate acknowledgements. It is not the same as "loss", which is the general word for a dropped packet. The distinction matters because TCP responds far more sharply to a timeout than to duplicate acknowledgements, which at least prove the network is still delivering something. introduced in ch. 3 — open in glossary is a timeout, or the receipt of three duplicate acknowledgements — the two signals section 3.5.4 built. When a router buffer overflows, a segment is dropped, and one of those two things eventually happens at the sender.

And when nothing is lost, acknowledgements keep arriving. TCP takes that as evidence that all is well and increases the congestion window.

Three principles follow, and the book states them as such:

1. A lost segment implies congestion, so the rate should be decreased.
2. An acknowledged segment implies the network is delivering, so the rate can be increased.
3. Bandwidth probing bandwidth probing Simple Speeding up until something breaks, backing off, and then speeding up again. Precise TCP’s strategy for finding a sending rate: increase in response to arriving acknowledgements until a loss event occurs, reduce, and begin increasing again to see whether conditions have changed. There is no signalling — acknowledgements and loss events are the only evidence — and every sender acts on local information alone, asynchronously from all the others. introduced in ch. 3 — open in glossary : increase in response to acknowledgements until a loss event, then back off, then start probing again.

Slow start

Every connection begins here. cwnd starts at 1 MSS (maximum segment size) maximum segment size The largest amount of application data TCP puts in one segment. Typically 1,460 bytes. It limits the data, not the whole segment (§3.5.1). introduced in ch. 3 , and increases by 1 MSS every time a transmitted segment is first acknowledged.

One segment, then two, then four: the rate doubles every round trip. The send rate starts slow and grows exponentially — which is a slightly awkward thing for something called slow start slow start Simple The opening phase, where the window doubles every round trip — anything but slow. Precise The state a TCP connection begins in. cwnd starts at a small value and grows by one MSS for every segment first acknowledged, which doubles the sending rate every round-trip time. It ends when cwnd reaches ssthresh, when a timeout occurs (cwnd returns to 1 MSS and slow start restarts), or when three duplicate acknowledgements arrive (TCP moves to fast recovery). The name refers to starting from 1 MSS, not to the growth rate. introduced in ch. 3 — open in glossary , and the book says so.

Figure 3.51 also gives the other half of the starting state, which the prose does not: a fresh connection begins with ssthresh = 64 KB. That is deliberately large — it means a first connection will normally keep doubling until something actually goes wrong, rather than stopping at a threshold no measurement has justified yet.

Congestion avoidance

On entry, cwnd is roughly half its value when congestion was last encountered — so congestion could be just around the corner. TCP therefore stops doubling and increases cwnd by a single MSS per round trip.

The usual implementation increases cwnd by MSS × (MSS/cwnd) on each new acknowledgement. With MSS 1,460 bytes and cwnd 14,600 bytes there are ten segments in flight, so each acknowledgement adds a tenth of an MSS. Once all ten are acknowledged, cwnd has grown by exactly one MSS.

Congestion avoidance congestion avoidance Simple The careful phase: one more segment per round trip instead of twice as many. Precise The state TCP enters when cwnd reaches ssthresh. Instead of doubling every round-trip time, cwnd grows by a single MSS per round-trip time, usually implemented as cwnd += MSS·(MSS/cwnd) on each new acknowledgement. A timeout sends TCP back to slow start with cwnd = 1 MSS; three duplicate acknowledgements halve cwnd and move it to fast recovery. introduced in ch. 3 — open in glossary ends the same two ways: a timeout, treated exactly as in slow start; or three duplicate acknowledgements, treated very differently.

Fast recovery

In fast recovery fast recovery Simple After three duplicate ACKs, carrying on from half the window instead of starting over. Precise The state entered on three duplicate acknowledgements. ssthresh is set to half of cwnd, cwnd becomes ssthresh + 3·MSS, and cwnd grows by one MSS for each further duplicate acknowledgement. When the missing segment is finally acknowledged, TCP deflates cwnd and enters congestion avoidance. Recommended but not required [RFC 5681]; it is what distinguishes Reno from Tahoe. introduced in ch. 3 — open in glossary , cwnd is increased by 1 MSS for every further duplicate acknowledgement for the missing segment. Each one is evidence that another segment has left the network, so there is room to send another.

When an acknowledgement finally arrives for the missing segment, TCP deflates cwnd and enters congestion avoidance. If a timeout occurs instead, it goes to slow start with cwnd = 1 MSS, like everything else that times out.

Fast recovery is recommended but not required [RFC 5681] — and that optional status is the whole difference between two famous versions of TCP.

Tahoe and Reno

TCP Tahoe tcp tahoe Simple An early TCP that always dropped back to one segment after any loss. Precise The earlier version of TCP, which unconditionally set cwnd to 1 MSS and re-entered slow start after either a timeout or three duplicate acknowledgements. It has no fast recovery, so a single lost segment costs the whole pipe. introduced in ch. 3 — open in glossary , the earlier version, unconditionally cut cwnd to 1 MSS and entered slow start after either kind of loss event. TCP Reno tcp reno Simple The classic TCP: like Tahoe, but with fast recovery added. Precise The version of TCP that added fast recovery, so that a loss detected by three duplicate acknowledgements halves the congestion window instead of collapsing it to 1 MSS. Timeouts still send it back to slow start. It is the "classic" TCP of RFC 5681 and the baseline against which CUBIC, Vegas and BBR are compared. introduced in ch. 3 — open in glossary added fast recovery.

The whole machine

Retrospective — the saw tooth

Step back from the details. Ignore the slow start at the beginning of a connection, and assume losses are signalled by triple duplicate acknowledgements rather than timeouts. What is left is:

• linear increase of cwnd by 1 MSS per round trip, and
• halving of cwnd on a loss event.

That is additive-increase, multiplicative-decrease additive-increase multiplicative-decrease Simple Grow by one segment each round trip; halve on loss. This makes the sawtooth. Precise AIMD: the shape of TCP congestion control once the initial slow start is ignored and losses are assumed to be signalled by duplicate acknowledgements. cwnd rises linearly by 1 MSS per round-trip time and is halved on each loss event, producing the familiar saw-tooth. Later analysis showed this simple rule acts as a distributed asynchronous optimisation algorithm [Kelly 1998]. introduced in ch. 3 — open in glossary — AIMD.

Check yourself