AdvancedComputer Networks · Lesson 11 of 15 · Updated ·
TCP Congestion Control — Slow Start, Congestion Avoidance, AIMD, Tahoe vs Reno with Numericals
In the last lesson the receiver told the sender how much it could accept. But between them sit routers shared by thousands of other connections. If everyone sends as fast as their receivers allow, router queues overflow, packets are dropped, senders resend, and the network gets even more crowded. This is called congestion, and in the worst case almost nothing useful gets through (congestion collapse).
TCP handles this with congestion control: each sender guesses how much the network can carry and adjusts the guess as it goes.
1. Flow control vs congestion control
| Flow control | Congestion control | |
|---|---|---|
| Protects | the receiver's buffer | the network (routers) |
| Who sets the limit | receiver, via the window field (rwnd) | sender, by its own estimate (cwnd) |
| Signal used | advertised window | lost packets (timeout, duplicate ACKs) |
The sender may have at most min(cwnd, rwnd) unacknowledged bytes in flight. In exam questions, cwnd is usually counted in MSS (maximum segment size — the largest data piece TCP puts in one segment, often about 1,460 bytes on Ethernet), and rwnd is assumed to be large.
2. Slow start
A new connection knows nothing about the path. It starts with a small window — classically cwnd = 1 MSS (modern systems start with up to 10) — and grows it quickly:
- For every ACK received, cwnd increases by 1 MSS.
- One round trip delivers cwnd ACKs, so cwnd doubles every RTT: 1, 2, 4, 8, 16…
The name is misleading — the growth is exponential. It is "slow" only compared with sending a full window at once.
Slow start continues until cwnd reaches the slow start threshold (ssthresh).
3. Congestion avoidance (additive increase)
Once cwnd ≥ ssthresh, TCP becomes careful: cwnd grows by 1 MSS per RTT (linear growth). It keeps probing for spare capacity, but gently.
If doubling would jump past ssthresh, the usual exam rule is to stop at ssthresh: with ssthresh = 10, the sequence is 1, 2, 4, 8, 10, 11, 12…
4. Reacting to loss (multiplicative decrease)
TCP treats a lost segment as a sign of congestion. There are two ways it finds out:
| Signal | What it suggests | Reaction |
|---|---|---|
| Timeout (no ACK at all) | serious congestion — nothing is getting through | ssthresh = cwnd / 2, cwnd = 1, slow start again |
| 3 duplicate ACKs | one segment was lost, but later ones are arriving | fast retransmit the missing segment; ssthresh = cwnd / 2 |
Why three duplicates? The receiver sends a duplicate ACK each time a segment arrives out of order. One or two duplicates can come from simple reordering; three in a row strongly suggest a real loss. Fast retransmit resends at once instead of waiting for the timer.
The two classic versions differ only in what happens after 3 duplicate ACKs:
- TCP Tahoe — treats every loss like a timeout: cwnd = 1, slow start.
- TCP Reno — fast recovery: cwnd = ssthresh (half the old window), then linear growth. (Textbooks describe extra temporary inflation by 3 MSS during recovery; most exam questions use the simple "cwnd = new ssthresh" rule.)
Both versions restart from cwnd = 1 after a timeout.
5. AIMD and the sawtooth
Put together, steady-state TCP follows AIMD — additive increase, multiplicative decrease: +1 MSS per RTT while things go well, halve on loss. Over time cwnd draws a sawtooth.
Why this shape? When several connections share a link, AIMD pushes them towards fair shares: everyone gains the same amount per RTT, but the bigger windows lose more when they are halved. Increasing fast and decreasing slowly would do the opposite and lead to collapse.
6. Solving cwnd questions step by step
Question. ssthresh = 16 MSS, cwnd starts at 1. A loss occurs in round trip 9. Find cwnd in each round trip for Tahoe and Reno.
Steps:
- RTT 1–5: slow start 1, 2, 4, 8, 16 (16 reaches ssthresh).
- RTT 6–9: congestion avoidance 17, 18, 19, 20.
- Loss at cwnd = 20 → new ssthresh = 10.
- Tahoe: 1, 2, 4, 8, 10, 11… Reno: 10, 11, 12…
The same rules in Python:
def cwnd_trace(rtts, ssthresh, loss_at=(), kind="Tahoe"):
cwnd, out = 1, []
for r in range(1, rtts + 1):
out.append(cwnd)
if r in loss_at:
ssthresh = max(cwnd // 2, 2)
cwnd = 1 if kind == "Tahoe" else ssthresh
continue
nxt = cwnd * 2 if cwnd < ssthresh else cwnd + 1
if cwnd < ssthresh < nxt: # do not jump past ssthresh
nxt = ssthresh
cwnd = nxt
return out
print("Tahoe:", cwnd_trace(15, 16, (9,), "Tahoe"))
print("Reno: ", cwnd_trace(15, 16, (9,), "Reno"))
Tahoe: [1, 2, 4, 8, 16, 17, 18, 19, 20, 1, 2, 4, 8, 10, 11]
Reno: [1, 2, 4, 8, 16, 17, 18, 19, 20, 10, 11, 12, 13, 14, 15]
Notice how much faster Reno gets back to a useful window. That is why fast recovery was added.
Quick throughput estimate. If cwnd is 20 MSS of 1,000 bytes and RTT is 100 ms, the sender moves about 20 × 1,000 bytes every 0.1 s = 200,000 bytes/s ≈ 1.6 Mbps, no matter how fast the link is. Throughput ≈ cwnd ÷ RTT.
7. Beyond Reno
Real operating systems use newer algorithms, but the ideas are the same:
- CUBIC — the default in Linux; grows cwnd using a cubic curve, which suits fast, long-distance links.
- BBR — from Google; estimates the bottleneck bandwidth and RTT instead of waiting for losses.
- ECN (Explicit Congestion Notification) — routers mark packets instead of dropping them, so senders slow down before any loss.
For interviews, explain Reno clearly and mention that modern stacks use CUBIC or BBR.
Common mistakes
- Thinking slow start is linear — it doubles every RTT.
- Halving cwnd on a timeout. A timeout sets cwnd to 1; it is ssthresh that becomes half.
- Letting slow start jump past ssthresh (8 → 16 when ssthresh is 10).
- Mixing up rwnd (set by the receiver) and cwnd (estimated by the sender).
- Saying UDP does congestion control — plain UDP does not; the application must do it if needed.
Quick recap
- Sender limit = min(cwnd, rwnd).
- Slow start: cwnd doubles each RTT until ssthresh.
- Congestion avoidance: +1 MSS per RTT.
- Timeout: ssthresh = cwnd/2, cwnd = 1. Three duplicate ACKs: fast retransmit; Tahoe cwnd = 1, Reno cwnd = ssthresh.
- AIMD gives the sawtooth and fairness between flows.
- Throughput ≈ cwnd ÷ RTT.