TCP Congestion Control

Flow control stops a sender from overrunning its receiver. It does nothing for the routers in between: if many senders together offer more traffic than a link can carry, router queues fill, packets are dropped, senders retransmit, and the network can spend its capacity on retransmissions (congestion collapse). TCP therefore keeps a second window, the congestion window cwnd, and permits at most $\max(0,\min(\text{cwnd},\text{rwnd})-\text{FlightSize})$ new bytes. Already-sent data may temporarily exceed a reduced window.

In the classic loss-based Tahoe/Reno model used here, without ECN, TCP infers congestion from loss rather than explicit network congestion notifications. The loss indications considered here are a retransmission timeout or three duplicate ACKs. It probes for capacity by growing cwnd and backs off sharply on loss: exponential growth in slow start, linear growth in congestion avoidance (additive increase), and a cut on loss (multiplicative decrease). TCP Tahoe and TCP Reno differ in what they do after three duplicate ACKs.

Start with a small window (the examples here start at 1 MSS; RFC 5681 allows an initial window of 2 to 4 segments depending on MSS). For each ACK of new data, cwnd grows by 1 MSS. Since a window of $w$ segments returns $w$ ACKs in one RTT, cwnd doubles every RTT: 1, 2, 4, 8, ... The name is historical; the growth is exponential.

Once cwnd $\ge$ ssthresh, cwnd grows by about 1 MSS per RTT (per ACK by $\text{MSS} \times \text{MSS} / \text{cwnd}$): linear growth.

FlightSize is the amount of outstanding data, which in the per-RTT model equals the current cwnd.

Fast retransmit. Three duplicate ACKs (four ACKs with the same number) mean later segments are arriving, so one segment is probably lost but the path still works: retransmit it at once, without waiting for the timer.

Fast recovery (Reno). After fast retransmit, set cwnd = ssthresh + 3 MSS (the three segments that left the network), add 1 MSS for each further duplicate ACK, and when the ACK for new data arrives, set cwnd = ssthresh and continue in congestion avoidance. A timeout is treated as more serious than three duplicate ACKs, because nothing is getting through.

The tables use the following conventions; a question that states others overrides them.

Initial cwnd = 1, ssthresh = 16. Three duplicate ACKs occur in round 9 and a timeout in round 13.

After round 9 both set ssthresh = 10; Tahoe restarts at 1, Reno continues from 10. At the timeout in round 13 the two have different windows (8 and 13), so they get different thresholds, 4 and $\lfloor 13/2 \rfloor = 6$, and then both restart at 1.

Slow-start time. From cwnd = 1, reaching $w$ (a power of 2 not above ssthresh) takes $\lg w$ rounds, and sending $n$ segments in slow start takes $\lceil \lg (n + 1) \rceil$ rounds, since after $k$ rounds $2^k - 1$ segments have gone.

Recovering after a timeout. Assume the pre-loss flight fills cwnd $W$, in MSS units. Set $\text{ssthresh}=\max(W/2,2)$ and cwnd = 1. For powers of two $W\ge4$, slow start takes $\lg(W/2)$ growth rounds to reach the threshold, followed by $W/2$ congestion-avoidance rounds to reach $W$. For $W=32$: 4 + 16 = 20 rounds. For $W=1$ the old window is already reached (0 growth rounds); for $W=2$, one slow-start growth round suffices. Otherwise use the stated round-by-round recurrence and minimum threshold, not this restricted closed form.

AIMD sawtooth. If a Reno flow loses one packet each time its window reaches $W$, the window cycles linearly between $W/2$ and $W$, so its average is $\tfrac34 W$ and its throughput about $0.75\,W \cdot \text{MSS} / \text{RTT}$.

Why AIMD. Additive increase and multiplicative decrease move competing flows towards an equal share: each decrease halves the difference between two flows' windows, while each increase leaves it unchanged.

A file of 63 segments, cwnd starting at 1, ssthresh 64, no loss: rounds carry 1, 2, 4, 8, 16, 32 segments; $1 + 2 + 4 + 8 + 16 + 32 = 63$, so 6 RTTs. A 64-segment file needs a seventh round for its last segment.

MSS = 1 KB. A timeout occurs at cwnd = 32 KB. ssthresh = 16 KB, cwnd = 1 KB; slow start gives 1, 2, 4, 8, 16 (4 RTTs to reach 16), then 17, ..., 32 (16 RTTs). cwnd is 32 KB again 20 RTTs after the timeout.

Reno with cwnd = 13 MSS gets three duplicate ACKs. ssthresh = $\lfloor 13/2 \rfloor = 6$ MSS and, after fast recovery, cwnd = 6. Under RFC 5681 in bytes, with MSS 1460 and FlightSize $13 \times 1460 = 18{,}980$ bytes, ssthresh = 9490 bytes = 6.5 MSS; problems in MSS units round down unless they say otherwise.

Reno, cwnd = 20 MSS, three duplicate ACKs. ssthresh = 10; cwnd = 10 + 3 = 13 while the retransmission is outstanding; two more duplicate ACKs inflate it to 15; the ACK for new data sets cwnd = 10. The per-round tables show only the final 10.

cwnd starts at 1 MSS, ssthresh = 12 MSS, rwnd = 14 MSS, no loss; each round the sender sends $\min(\text{cwnd}, \text{rwnd})$ segments.

Slow start stops at 12 (convention 2), congestion avoidance adds 1, and from round 7 the receiver's window of 14 is the limit. After 7 rounds 54 segments have gone, so a 100-segment file needs 11 rounds ($54 + 4 \times 14 = 110 \ge 100$). If a problem lets slow start overshoot (8 doubles to 16, then +1 per round), the rounds send 1, 2, 4, 8, 14, 14, and so on: 29 segments after 5 rounds and again 11 rounds for 100 segments, but the per-round values differ, so the convention must be stated.

Reno leaves fast recovery on the first new ACK; if several segments of one window were lost, that ACK is only a partial ACK and Reno may need a timeout. NewReno (RFC 6582) stays in fast recovery until all data outstanding at the time of the loss is acknowledged, retransmitting one lost segment per partial ACK.

Common misconceptions.