TCP congestion control: cwnd, Slow Start, AIMD, Tahoe vs Reno

1. What is the difference between flow control and congestion control?
   Stuck? Peek at 4.3.4 TCP timeout estimation: EWMA, Jacobson’s algorithm & Karn’s rule

   • EWMA: Est_new = (1 − α)·Est_old + α·Sample = Est_old + (Sample − Est_old)·α (default α = 1/8).
   • Deviation & RTO: Dev_new = (1 − β)·Dev_old + β·|Sample − Est| (default β = 1/4); RTO = Est + 4·Dev.
   • Karn's rule: ignore RTT samples from retransmitted segments; double RTO on each timeout.

   Read lesson 4.3.4

2. If a sender knows both the receiver’s advertised window rwnd and its own congestion window cwnd, how much unacknowledged data can it have in flight?
   Stuck? Peek at 4.3.3 TCP flow control (rwnd), sequence wrap-around time & window scaling

   • Flow control: rwnd = RcvBuffer − (LastByteRcvd − LastByteRead); sender keeps BytesInFlight ≤ rwnd.
   • Zero window (`rwnd = 0`): sender runs Persist Timer and sends 1-byte Zero-Window Probes.
   • Wrap-around time: T_wrap = (2³² × 8) / B seconds (34.36 s at 1 Gbps).
   • Window scaling: True rwnd = HeaderWindow × 2ˢ (S ≤ 14, negotiated in SYN).

   Read lesson 4.3.3

3. Which is a milder sign of network congestion: a Retransmission Timeout (RTO) or receiving 3 Duplicate ACKs?
   Stuck? Peek at 1.2.2 Packet switching: store-and-forward, datagrams, statistical multiplexing

   • Packet switching: packets with headers; no reservation; full link rate while sending.
   • Store-and-forward: receive whole packet → buffer/queue → forward; full buffer → loss.
   • Datagram: each packet routed independently; may reorder; robust to failures.
   • Statistical multiplexing: share capacity on demand; P(exactly k of n) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.

   Read lesson 1.2.2

Suppose the receiver has a huge 10 MB buffer (rwnd = 10 MB), so flow control says "send at full blast!" If 1,000 senders immediately dump 10 MB into a bottleneck router with a 64 KB queue, almost every packet is dropped, everyone times out and retransmits, and throughput collapses to near zero (congestion collapse).

How does a TCP sender probe the network's unknown capacity without any router telling it the link rate? By maintaining a Congestion Window (cwnd) and running a brilliant state machine: Slow Start, Congestion Avoidance (AIMD), and Fast Retransmit / Fast Recovery (Tahoe vs Reno)!

Why is TCP's initial phase called "Slow Start" when it actually doubles cwnd every RTT (exponential growth: 1 → 2 → 4 → 8 → 16 MSS)?

Because before Slow Start was invented by Van Jacobson in 1988, a new TCP connection immediately dumped an entire rwnd worth of segments (e.g., 64 KB = 44 segments) into the network in RTT 1! Starting at 1 MSS was "slow" compared to dumping 44 segments at once — even though it probes upward exponentially!

Effective Window: W = min(cwnd, rwnd)

A TCP sender maintains two window limits simultaneously: the receiver's advertised window rwnd (flow control) and its own Congestion Window cwnd (congestion control), plus a threshold variable called the Slow Start Threshold (ssthresh):

Phase 1 & 2: Slow Start (Exponential) vs Congestion Avoidance (AIMD Linear)

A new connection starts with cwnd = 1 MSS and a high initial ssthresh:

Reaction to Loss: Timeout vs 3 Duplicate ACKs (TCP Tahoe vs TCP Reno)

When a segment is lost, TCP detects it in one of two ways: either the Retransmission Timeout (RTO) expires (severe congestion), or 3 Duplicate ACKs arrive before timeout (mild congestion — later segments are still reaching the receiver, triggering Fast Retransmit!). In both cases, TCP first cuts the threshold in half (Multiplicative Decrease):

Putting it together

• A TCP sender caps unacknowledged data in flight at W = min(cwnd, rwnd).
• Slow Start grows cwnd exponentially (+1 MSS per ACK, doubling per RTT) up to ssthresh; Congestion Avoidance grows cwnd linearly (+1 MSS per RTT).
• Any loss sets ssthresh = ⌊cwnd/2⌋; a timeout resets cwnd = 1 MSS in both Tahoe and Reno, whereas 3 duplicate ACKs reset cwnd = 1 MSS in Tahoe but cwnd = ssthresh in Reno.

• Adding +1 KB instead of +1 MSS when MSS = 2 KB! Always divide all byte/KB values by MSS at step 0, trace in MSS, and multiply back by MSS at the end!
• Forgetting to clamp at ssthresh when ssthresh is not a power of 2! If cwnd = 4 MSS and ssthresh = 6 MSS, the next RTT is min(8, 6) = 6 MSS, NOT 8 MSS!
• Confusing Timeout vs 3 Duplicate ACKs in TCP Reno! On a Timeout, even TCP Reno resets cwnd = 1 MSS! Only on 3 Duplicate ACKs does Reno set cwnd = ssthresh.

Work in MSS! Slow Start ×2 (clamped at ssthresh), CA +1 MSS; Loss sets ssthresh = cwnd/2; Timeout → 1 MSS, 3-Dup → 1 (Tahoe) or ssthresh (Reno)!

Let's lock in everything from Section 4.3 — TCP header, 3-way handshake, sequence/ACK numbering, wrap-around time, EWMA/Jacobson RTO, and Tahoe/Reno congestion control — in Lock-in L4.3!

1. NAT

   A TCP Reno connection with MSS = 1 KB starts at RTT 1 with cwnd = 1 KB and ssthresh = 8 KB. Assuming no losses, what is cwnd (in KB) during RTT 6?

   Write your answer before opening the key.

2. NAT

   In the previous question (cwnd = 10 KB during RTT 6, MSS = 1 KB), suppose 3 duplicate ACKs arrive at the end of RTT 6. Under TCP Reno, what is cwnd (in KB) during RTT 8 (assuming no further losses)?

   Write your answer before opening the key.

3. NAT

   If the connection in the previous question used TCP Tahoe instead of TCP Reno (3 duplicate ACKs at the end of RTT 6 when cwnd = 10 KB, MSS = 1 KB), what would cwnd (in KB) be during RTT 8?

   Write your answer before opening the key.

4. MCQ

   During Slow Start (cwnd < ssthresh), how much does a TCP sender increase cwnd upon receiving each individual ACK that acknowledges new data?

   1. By 1 MSS per individual ACK (which results in doubling cwnd every RTT).
   2. By 1 MSS per RTT.
   3. By MSS × (MSS / cwnd) per ACK.
   4. It keeps cwnd constant until ssthresh is reached.

• Effective window: W = min(cwnd, rwnd). Always trace in units of MSS!
• Slow Start (cwnd < ssthresh): +1 MSS per ACK → cwnd ← min(2·cwnd, ssthresh) per RTT.
• Congestion Avoidance (cwnd ≥ ssthresh): +1 MSS per RTT (AIMD linear growth).
• On Loss: ssthresh ← ⌊cwnd / 2⌋; Timeout → cwnd = 1 MSS; 3 Dup ACKs → cwnd = 1 MSS (Tahoe) or cwnd = ssthresh (Reno).

• cwnd (Congestion Window)
• effective window = min(cwnd, rwnd)
• ssthresh (Slow Start Threshold)
• Slow Start (exponential, +1 MSS per ACK)
• Congestion Avoidance (AIMD, +1 MSS per RTT)
• Fast Retransmit (3 duplicate ACKs)
• Fast Recovery (TCP Reno vs TCP Tahoe)

1. How does cwnd grow in Slow Start vs Congestion Avoidance?
   Reveal answer

   Slow Start (cwnd < ssthresh): +1 MSS per ACK → doubles every RTT (clamped at ssthresh). Congestion Avoidance (cwnd ≥ ssthresh): +1 MSS per RTT (linear).
2. How do TCP Tahoe and TCP Reno differ when 3 duplicate ACKs arrive at window cwnd?
   Reveal answer

   Both set ssthresh = ⌊cwnd / 2⌋. Tahoe resets cwnd = 1 MSS (Slow Start); Reno sets cwnd = ssthresh (Fast Recovery / Congestion Avoidance).
3. What do TCP Tahoe and TCP Reno do when a Retransmission Timeout (RTO) occurs?
   Reveal answer

   Both set ssthresh = ⌊cwnd / 2⌋ and reset cwnd = 1 MSS (entering Slow Start).

• Always convert KB to MSS first! Never apply +1 directly to KB when MSS ≠ 1 KB! In Congestion Avoidance, cwnd grows by +1 MSS per RTT (which is +2 KB if MSS = 2 KB!). Solve the entire trace in MSS, then multiply by MSS at the very last step! — avoiding the #1 GATE numerical trap in TCP congestion control.
• Slow Start RTT Count Formula: To grow from 1 MSS to ssthresh = S MSS takes ⌈log₂(S)⌉ RTT intervals (so S is reached in round 1 + ⌈log₂(S)⌉). — quickly jumping across Slow Start without listing every round.