Noesis
4.3.22Computer Networks

TCP congestion control — slow start, congestion avoidance, fast retransmit, CUBIC

2,374 words11 min readdifficulty · medium3 backlinks
🇮🇳 Yeh note Hinglish mein padho →

The two windows that limit a sender

WHAT we control: cwnd. WHY: rwnd protects the receiver's RAM; cwnd protects the network's queues — two different bottlenecks.

We measure cwnd in units of MSS (Maximum Segment Size) for clarity. Throughput ≈cwndRTT\approx \dfrac{\text{cwnd}}{\text{RTT}}, so bigger cwnd = faster — until loss.

1. Slow Start (SS) — find the ballpark fast

HOW it grows (derivation from first principles): We want to increase cwnd by 1 MSS for every ACK received.

  • Suppose cwnd = WW segments. In one RTT we send WW segments → receive WW ACKs.
  • Each ACK adds 1 → after one RTT, cwnd =W+W=2W= W + W = 2W.

So per-RTT: W→2WW \to 2W. After nn RTTs starting from 1: cwnd(n)=2 n MSS\text{cwnd}(n) = 2^{\,n} \text{ MSS}

2. Congestion Avoidance (CA) — tiptoe near the limit

HOW (derivation): We want +1 segment per RTT, but ACKs arrive throughout the RTT. With cwnd = WW segments, WW ACKs arrive per RTT, and we want their total effect to be +1 MSS: per ACK: cwnd+=MSS×MSScwnd\text{per ACK: } \text{cwnd} \mathrel{+}= \frac{\text{MSS} \times \text{MSS}}{\text{cwnd}} Summing over WW ACKs: W×MSS2W⋅MSS=MSSW \times \frac{\text{MSS}^2}{W\cdot\text{MSS}} = \text{MSS}. ✓ Exactly +1 per RTT.

So per-RTT: cwnd(t+RTT)=cwnd(t)+1 MSS\text{cwnd}(t+\text{RTT}) = \text{cwnd}(t) + 1\ \text{MSS}

This is the AI of AIMD (Additive Increase, Multiplicative Decrease).

3. Reacting to loss — two flavours

WHY halve (the MD in AIMD)? Cutting in half is a strong, multiplicative back-off that quickly relieves congestion and, combined with additive increase, gives a fair, stable sawtooth that converges (proven via the AIMD chart — fairness line).

4. Fast Retransmit — don't wait for the clock

This saves a full RTO (which can be hundreds of ms), keeping the pipe full.

Figure — TCP congestion control — slow start, congestion avoidance, fast retransmit, CUBIC

5. CUBIC — the modern default (Linux, since kernel 2.6.19)

Derivation of KK (WHY that cube root): After a loss, cwnd drops to β Wmax⁡\beta\,W_{\max}... wait — actually CUBIC drops by factor (1−β)(1-\beta), so new window =(1−β)Wmax⁡=(1-\beta)W_{\max}. We want the cubic curve to pass through the new window at t=0t=0 and reach Wmax⁡W_{\max} at t=Kt=K (its inflection plateau). Set Wcubic(0)=(1−β)Wmax⁡W_{\text{cubic}}(0)=(1-\beta)W_{\max}: C(0−K)3+Wmax⁡=(1−β)Wmax⁡C(0-K)^3 + W_{\max} = (1-\beta)W_{\max} −CK3=−βWmax⁡  ⇒  K=βWmax⁡C3-C K^3 = -\beta W_{\max} \;\Rightarrow\; K=\sqrt[3]{\frac{\beta W_{\max}}{C}}

Worked Examples

Common Mistakes

Recall Feynman: explain to a 12-year-old

Imagine pouring water into a thin pipe but you can't see the pipe. You start with a trickle, then double the flow each second to find how much it takes. The moment water splashes back (a packet got lost), you know you pushed too hard, so you cut the flow in half and then add just a tiny bit more each second, sneaking up on the perfect amount. If the splash was a tiny dribble (3 duplicate "I'm still missing one!" notes), you only halve. If the pipe went totally silent (timeout), you slam back to a trickle. CUBIC is a smarter version: it remembers the flow rate that caused the last splash, races back up to just below it, pauses to test it, then carefully pushes higher to see if the pipe got bigger.

Flashcards

What does cwnd limit and who maintains it?
The amount of unACKed data the network can handle; maintained locally by the sender (never sent on the wire).
In slow start, how does cwnd change per ACK and per RTT?
+1 MSS per ACK ⇒ doubles per RTT (exponential): cwnd(n)=2^n.
In congestion avoidance, what is the per-ACK increment?
cwnd += MSS²/cwnd, summing to +1 MSS per RTT (linear, additive increase).
What does AIMD stand for and why is it stable/fair?
Additive Increase, Multiplicative Decrease; the sawtooth converges to fair, efficient sharing.
Reno reaction to a TIMEOUT?
ssthresh = cwnd/2; cwnd = 1 MSS; restart slow start.
Reno reaction to 3 DUPLICATE ACKs?
ssthresh = cwnd/2; cwnd ≈ ssthresh (halve); stay in congestion avoidance (Fast Recovery).
Why exactly THREE duplicate ACKs trigger fast retransmit?
1–2 dup ACKs may be packet reordering; 3 is strong evidence the segment is truly lost, so retransmit without waiting for RTO.
Write CUBIC's window function.
W(t) = C·(t−K)³ + W_max, t = time since last loss.
Derive K in CUBIC.
Require W(0)=(1−β)W_max ⇒ −C·K³ = −β·W_max ⇒ K = ∛(β·W_max / C).
Why is CUBIC's concave-then-convex shape clever?
Concave: grow fast then slow approaching old W_max (caution near danger); convex after K: accelerate to probe new bandwidth.
Why does CUBIC give better RTT fairness than Reno?
Its growth depends on real elapsed time since loss, not on RTT, so flows with different RTTs grow similarly.
Throughput in terms of cwnd?
≈ cwnd / RTT.

Connections

  • TCP Reliable Data Transfer — cumulative ACKs and retransmission timers (RTO) that this builds on.
  • Flow Control vs Congestion Control — rwnd vs cwnd, two distinct bottlenecks.
  • AIMD Fairness — geometric proof of convergence to the fairness line.
  • Queueing and Router Buffers — where the dropped packets actually happen (Bufferbloat).
  • BBR Congestion Control — model-based alternative to loss-based CUBIC.
  • Bandwidth Delay Product — why long fat networks motivated CUBIC.

Concept Map

solved by

controls

combines via min

combines via min

measured in

phase 1

grows

reaches ssthresh then

grows

is the AI of

timeout RTO

3 dup ACKs

triggers MD

Network congestion collapse

TCP congestion control

cwnd sender side

rwnd receiver window

Bytes in flight

MSS units

Slow Start

Exponential doubling per RTT

Congestion Avoidance

Linear plus 1 MSS per RTT

AIMD

Packet loss signal

Fast Retransmit

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Internet ek shared road hai jisme koi traffic police nahi hai. Agar har sender apni poori speed se data bhej de, to routers ki queue overflow ho jaayegi, packets drop honge, sab log retransmit karenge aur network collapse — yeh 1986 mein literally hua tha. Isliye har sender khud andaaza lagata hai ki network kitna le sakta hai, aur iska control hota hai cwnd (congestion window) se. Throughput basically cwnd/RTT hai.

Game simple hai: Slow Start mein chhote se shuru karo (1 MSS) aur har RTT mein double karo — naam "slow" hai par yeh sabse fast exponential growth hai. Jab cwnd ek ssthresh tak pahunch jaaye, switch karo Congestion Avoidance pe, jahan har RTT sirf +1 MSS badhta hai (tiptoe karke limit dhoondhna). Yeh poora pattern AIMD kehlata hai — additive increase, multiplicative decrease.

Loss do tarah ka hota hai. Timeout = network bilkul silent, bahut severe → cwnd ko 1 par patak do aur slow start dobara. 3 duplicate ACKs = halka signal, kyunki baaki packets aa rahe hai, sirf ek kho gaya → ssthresh aur cwnd ko aadha karo, CA mein hi raho. Teen dup ACK isliye, kyunki ek-do to reordering ho sakta hai, teen ka matlab pakka loss — to turant retransmit karo bina timer ka wait kiye; ise Fast Retransmit kehte hai.

CUBIC modern Linux default hai. Reno ka +1/RTT fast long-distance links pe bahut slow hai. CUBIC formula W(t)=C(t−K)3+WmaxW(t)=C(t-K)^3+W_{max} use karta hai, jahan tt last loss ke baad ka real time hai (RTT nahi) — isliye alag-alag RTT waale flows fair rehte hai. Curve pehle concave hota hai (purane WmaxW_{max} ke paas careful), phir convex (naya bandwidth khojne ke liye tezi se upar). Bas yahi pura khel hai — gently upar chalo, congestion sense karte hi zor se back off.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 3,137 wordsD2Visual walkthroughThe derivation in pictures · 2,404 wordsD3Worked examplesEvery scenario covered · 4,240 wordsD4ExercisesGraded, full solutions · 3,231 wordsD5Question bankConcept traps, quick reveals · 2,132 words

Test yourself — Computer Networks

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Control flow — if - else, switch, while, do-while, for, break, continue, gotoCoding · 5.1.6Power-delay productHardware · 3.2.13TCP — header, connection (3-way handshake, 4-way termination)Coding · 4.3.19TCP reliability — seq - ack numbers, retransmission, cumulative ACKCoding · 4.3.20TCP flow control — sliding window, receive bufferCoding · 4.3.21