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

WHAT: cwnd doubles every RTT. Phase: Slow Start. Growth type: exponential (factor 2 per RTT). WHY it doubles: let $W$ = the current value of cwnd measured in segments. In one RTT the sender emits $W$ segments and (no loss) gets $W$ ACKs back; each ACK adds $+1$, so $W\to W+W=2W$. This is the steep left (magenta) edge of the sawtooth in Figure s01 and the curving ramp in Figure s02.

cwnd is never on the wire — it is a local variable the sender keeps to protect the network's queues. rwnd is advertised in every ACK to protect the receiver's buffer. See Flow Control vs Congestion Control.

Mild. Later packets are still arriving (that's what generates the duplicates), so only one segment is lost. Mechanism: Fast Retransmit (resend immediately), followed by Fast Recovery (halve, stay in CA).

WHY doubling: let $W$ = the current cwnd in segments. In slow start every ACK adds $+1$, and one RTT with cwnd $=W$ brings back $W$ ACKs, so $W\to 2W$ each RTT (see Problem 1.1). We apply that rule until cwnd reaches the ssthresh border line ($16$): $1\to 2\to 4\to 8\to 16$ At RTT4 cwnd reaches $16=$ ssthresh ⇒ switch to CA. So the SS sequence is $\{1,2,4,8,16\}$ over RTT0…RTT4, then CA continues $17,18,\dots$ On Figure s01 this is the exponential ramp meeting the dashed ssthresh line; on Figure s02 it is the curving magenta ramp.

Timeout rule:

• $\text{ssthresh}=24/2=12$
• $\text{cwnd}=1$ MSS
• Next phase: Slow Start (double $1\to 2\to 4\to 8$, then reach $12$ and enter CA).

Fast Recovery rule:

• $\text{ssthresh}=24/2=12$
• $\text{cwnd}=\text{ssthresh}=12$ MSS
• Next phase: Congestion Avoidance (linear $+1$ MSS per RTT).

Compare: same ssthresh ($12$) as the timeout case, but cwnd falls only to $12$ (not $1$), and we skip slow start. WHY: milder signal ⇒ milder reaction — this is the whole point of matching reaction to severity (AIMD Fairness).

(a) After a CUBIC loss the window drops by factor $(1-\beta )$: $W_{\text{new}}=(1-\beta )W_{\max }=0.7\times 64=44.8\text{MSS}.$ (A real kernel floors this to $44$ MSS; we keep $44.8$ to show the rule.) (b) $K=\sqrt[3]{\frac{\beta W_{\max }}{C}}=\sqrt[3]{\frac{0.3\times 64}{0.4}}=\sqrt[3]{48}\approx 3.634\text{s}.$ Check: at $t=K$ (recall $t$ = seconds since loss), $W_{\text{cubic}}=C(0{)}^3+W_{\max }=64$ ✓ (it climbs back exactly to the old peak).

WHAT: CA adds $+1$ MSS per RTT.

• Flow A: $1000/20=50$ RTTs ⇒ $+50$ MSS.
• Flow B: $1000/100=10$ RTTs ⇒ $+10$ MSS.

Analysis: the short-RTT flow A grabs bandwidth $5\times$ faster — this is RTT unfairness. Reno's growth is tied to RTT, so low-RTT flows dominate. CUBIC's fix: $W(t)=C(t-K{)}^3+W_{\max }$ depends on wall-clock seconds since loss (that $t$ again), not RTTs, so two flows with different RTTs climb at comparable real-time rates ⇒ better RTT fairness.

TCP ACKs are cumulative: "I have everything up to byte X." If segment 5 is lost but 6,7,8 arrive, the receiver re-ACKs "I still want 5" each time.

• 1 or 2 duplicates can happen from harmless packet reordering (segment 5 just took a slower path and hasn't arrived yet).
• 3 duplicates is strong statistical evidence segment 5 is truly lost, not merely late.

So "3" is a noise threshold trading off false alarms (retransmitting a reordered-but-fine packet) against waiting too long. Retransmitting on the 3rd saves a whole RTO. See TCP Reliable Data Transfer.

WHAT: CA adds $+1$/RTT, so refilling $5000$ MSS needs $10000-5000=5000$ RTTs. Time: $5000\times 0.1\text{s}=500\text{s}\approx 8.3$ minutes — the pipe sits half-empty for minutes. Why CUBIC: its convex exploration phase ($t>K$) accelerates upward instead of crawling $+1$/RTT, refilling huge windows in seconds, not minutes.

Slow start (cwnd $<$ ssthresh $=8$), doubling:

• RTT0: $1$, RTT1: $2$, RTT2: $4$, RTT3: $8$.

At RTT3 cwnd $=8=$ ssthresh ⇒ enter CA. So at start of RTT4 cwnd $=8+1=9$. Now the 3-dup-ACK loss hits at cwnd $=9$:

• $\text{ssthresh}=9/2=4.5$ (a real kernel floors this to $4$; we keep $4.5$ to show the rule).
• $\text{cwnd}=\text{ssthresh}=4.5$, stay in CA.

Post-recovery CA, $+1$ MSS per RTT:

• RTT5: $4.5+1=5.5$
• RTT6: $5.5+1=6.5$

Full trace, cwnd at start of RTT0 … RTT7 (eight values): $\text{RTT0}=1,\text{RTT1}=2,\text{RTT2}=4,\text{RTT3}=8,\text{RTT4}=9,\text{RTT5}=4.5,\text{RTT6}=5.5,\text{RTT7}=6.5$ $\boxed{1,2,4,8,9,4.5,5.5,6.5}$ ssthresh after loss $=4.5$. WHY each step: exponential while below ssthresh, linear at/above it, halve-and-stay-CA on the mild dup-ACK loss — exactly the sawtooth of Figure s01.

Timeout at cwnd $=9$:

• $\text{ssthresh}=9/2=4.5$
• $\text{cwnd}=1$, go to slow start.

Slow start doubles until cwnd reaches ssthresh $=4.5$, then switch to CA:

• RTT4: cwnd $=1$ (right after timeout)
• RTT5: $2$
• RTT6: $4$
• RTT7: $4.5$ (reached ssthresh ⇒ CA)
• RTT8: $5.5$ (CA, $+1$)
• RTT9: $6.5$

Compare with 4.1: identical ssthresh ($4.5$), but the timeout forces cwnd all the way to $1$ and a fresh slow-start climb — a far deeper cut for the more severe signal. (Integer-flooring kernels would use ssthresh $=4$; the shape is unchanged.)

Target rate $R=240\times 10^6$ bits/s $=3.0\times 10^7$ bytes/s (÷8). Bytes per RTT we must have in flight $=R\times \text{RTT}=3.0\times 10^7\times 0.05=1.5\times 10^6$ bytes. In MSS: $\frac{1.5\times 10^6}{1500}=1000$ MSS. Meaning: this is exactly the bandwidth-delay product in segments — the window needed to keep the pipe full.

Setup: let $W$ = cwnd measured in MSS. In one RTT the sender emits $W$ segments and (no loss) receives $W$ ACKs. Per ACK increment (in bytes): $\frac{{\text{MSS}}^2}{\text{cwnd}}=\frac{{\text{MSS}}^2}{W\cdot \text{MSS}}=\frac{\text{MSS}}{W}$. Sum over the $W$ ACKs in one RTT: ${\sum }_{i=1}^W\frac{\text{MSS}}{W}=W\cdot \frac{\text{MSS}}{W}=\text{MSS}.$ So cwnd grows by exactly $+1$ MSS per RTT — the Additive Increase of AIMD. $■$

Requirement 1 (at the peak): $W_{\text{cubic}}(K)=C(K-K{)}^3+W_{\max }=W_{\max }$ ✓ automatically — $K$ is where the curve tops out. Requirement 2 (at loss, $t=0$): the window just after loss is $(1-\beta )W_{\max }$. Set: $C(0-K{)}^3+W_{\max }=(1-\beta )W_{\max }.$ $-C{K}^3=(1-\beta )W_{\max }-W_{\max }=-\beta W_{\max }.$ $C{K}^3=\beta W_{\max }\Rightarrow K=\sqrt[3]{\frac{\beta W_{\max }}{C}}.■$ Meaning: $K$ is the real-time delay (in seconds) before CUBIC re-tests its old ceiling — the "memory" of where it broke.

$W_{\text{cubic}}(t)=0.4(t-4.217{)}^3+100$ (here $t$ = seconds since the last loss).

• $t=0$: $0.4(-4.217{)}^3+100=0.4(-74.99)+100=-29.996+100=70.0$ ← equals $(1-\beta )\cdot 100$ ✓.
• $t=2$: $0.4(-2.217{)}^3+100=0.4(-10.897)+100=-4.359+100=95.64$.
• $t=K\approx 4.217$: $0.4(0)+100=100.0$ ← the plateau at $W_{\max }$.
• $t=6$: $0.4(1.783{)}^3+100=0.4(5.667)+100=2.267+100=102.27$.

What to observe in Figure s03: the magenta part of the curve ($t<K$) is concave — it shoots up out of $70$ then bends over and eases toward the dashed $W_{\max }=100$ line: TCP is cautious as it re-approaches the value that broke it. The curve just kisses the plateau at $t=K$ (the violet dot). The orange part ($t>K$) is convex — it curls upward and accelerates past $100$: now TCP probes for brand-new bandwidth. The four square markers are exactly the values you computed $(0,70),(2,95.64),(K,100),(6,102.27)$ — check each sits on the curve.

From $K=\sqrt[3]{\beta W_{\max }/C}$: increasing $C$ decreases $K$ (C is in the denominator). So to reach the peak faster, increase $C$. Halving $K$: $K\propto C^{-1/3}$, so $K_{\text{new}}=\frac{1}{2}{K}_{\text{old}}$ requires ${\left(\frac{C_{\text{new}}}{C_{\text{old}}}\right)}^{-1/3}=\frac{1}{2}\Rightarrow \frac{C_{\text{new}}}{C_{\text{old}}}=2^3=8.$ $C_{\text{new}}=8\times 0.4=3.2.$ Check: $K_{\text{new}}=\sqrt[3]{0.3\cdot 100/3.2}=\sqrt[3]{9.375}\approx 2.108=\frac{1}{2}(4.217)$ ✓. Trade-off caveat: larger $C$ is more aggressive ⇒ risks unfairness to gentler flows and can starve alternatives like BBR Congestion Control; production CUBIC keeps $C=0.4$ for a reason.

Which loss signal restarts slow start from cwnd = 1? ::: Timeout (RTO) — the severe signal. Which loss signal halves cwnd and stays in CA? ::: Three duplicate ACKs (Fast Recovery). What is ssthresh? ::: The border cwnd value separating slow start (below) from congestion avoidance (at/above); reset to cwnd/2 on every loss. What does RTT mean? ::: Round-trip time — one there-and-back of a segment plus its ACK; our natural clock tick. Is CUBIC's $t$ measured in RTTs or seconds? ::: Wall-clock seconds since the last loss. What is $K$ physically? ::: Time (in seconds) to climb back to the previous peak $W_{\max }$. Why increase $C$ by $8\times$ to halve $K$? ::: Because $K\propto C^{-1/3}$ (cube-root dependence).