Unit 3, Tutorial 9: TCP Congestion Control (Advanced)

Congestion occurs when the demand for network resources (bandwidth, buffers) exceeds the available capacity. This leads to:

TCP congestion control aims to avoid congestion by dynamically adjusting the sender’s sending rate based on network feedback (loss or ECN). It is an end‑to‑end mechanism, as the network does not explicitly tell the sender the available bandwidth (except via ECN).

📘 2. TCP Congestion Control Principles

TCP uses a congestion window (cwnd) that limits the amount of data the sender can have in flight. The effective window is min(cwnd, rwnd). The sender adjusts cwnd based on perceived congestion:

📘 3. Additive Increase / Multiplicative Decrease (AIMD)

AIMD ensures stability and fairness. It allows flows to share bandwidth equally over time because additive increase gives a concave growth, while multiplicative decrease quickly backs off.

📘 4. Slow Start

When a connection starts, or after a timeout, cwnd is set to 1 MSS (or a small initial value). The sender then doubles cwnd each RTT (exponential growth) until it reaches a threshold (ssthresh). This rapid growth allows TCP to quickly reach the available bandwidth.

Slow start is also used after a timeout. The threshold is set to half the cwnd at the time of loss.

📘 5. Congestion Avoidance

Once cwnd reaches ssthresh, TCP enters congestion avoidance, where cwnd increases linearly (by 1 MSS per RTT). This cautious growth probes for additional bandwidth without causing sudden overload. If a loss occurs, cwnd is reduced to half (multiplicative decrease), and ssthresh is set to that new value.

📘 6. Fast Retransmit and Fast Recovery (TCP Reno)

Fast retransmit: After receiving 3 duplicate ACKs, the sender retransmits the lost segment before the timeout, improving recovery time.

Fast recovery (Reno): After fast retransmit, the sender sets ssthresh = cwnd/2, cwnd = ssthresh + 3*MSS (to account for the three duplicate ACKs that indicate the receiver has already received some data), and then continues in congestion avoidance. This avoids the slow start after a fast retransmit.

This combination makes Reno more efficient than Tahoe, which after fast retransmit would set cwnd to 1 and go to slow start.

📘 7. TCP Tahoe vs. Reno

Reno achieves higher throughput because it does not waste time in slow start after a loss.

📘 8. Throughput Models and the Square‑Root Law

A well‑known result for TCP Reno (with fast retransmit/recovery) is the square‑root law:

where p is the packet loss probability. This formula shows that throughput is inversely proportional to the square root of the loss rate. It is derived from the sawtooth pattern of cwnd: cwnd oscillates between W (peak) and W/2, and losses occur on average every W packets.

📘 9. Fairness and Convergence

TCP is fair in the sense that multiple TCP connections sharing the same bottleneck will converge to equal bandwidth shares. This is a consequence of AIMD: additive increase causes all flows to grow linearly, while multiplicative decrease scales each flow proportionally. Over time, flows converge to fairness.

However, fairness is affected by RTT: flows with shorter RTTs increase cwnd faster and tend to get more bandwidth (the "RTT unfairness" problem). Various enhancements, like TCP Cubic, aim to improve fairness in high‑speed networks.

📘 10. Advanced Variants: TCP Cubic, BBR, and ECN

📝 Quiz

Test your understanding with these 35 questions. Answers are hidden below each.

What is the primary goal of TCP congestion control?

Answer
To prevent network congestion and ensure fair sharing of bandwidth among competing flows.
What does the acronym AIMD stand for?

Answer
Additive Increase, Multiplicative Decrease.
In AIMD, how does cwnd increase during congestion avoidance?

Answer
Linearly, by 1 MSS per RTT.
In AIMD, how does cwnd decrease when a loss is detected?

Answer
Multiplicatively, by halving (cwnd = cwnd/2).
What is the initial value of cwnd in slow start?

Answer
Typically 1 MSS (or 10 MSS in some implementations).
How does cwnd grow during slow start?

Answer
Exponentially, doubling each RTT.
What is the role of the ssthresh variable?

Answer
It is the slow start threshold; when cwnd reaches ssthresh, TCP switches from slow start to congestion avoidance.
How many duplicate ACKs trigger fast retransmit?

Answer
3 duplicate ACKs.
What does TCP Reno do after fast retransmit?

Answer
It sets ssthresh = cwnd/2, cwnd = ssthresh + 3*MSS, and enters congestion avoidance (fast recovery).
What does TCP Tahoe do after fast retransmit?

Answer
It sets ssthresh = cwnd/2, cwnd = 1, and enters slow start.
Which TCP variant has better performance under loss? Why?

Answer
Reno, because it avoids the slow start phase after a loss, keeping cwnd higher.
What is the square‑root law for TCP throughput?

Answer
Throughput ≈ 1.22 * MSS / (RTT * sqrt(p)), where p is loss probability.
What does the square‑root law imply about the impact of loss rate on throughput?

Answer
Throughput decreases rapidly with loss rate; halving the loss rate increases throughput by about 41% (since sqrt(1/2) ≈ 0.707, throughput becomes 1/0.707 ≈ 1.41).
What is the fairness property of TCP?

Answer
Multiple TCP flows sharing a bottleneck tend to converge to equal bandwidth shares.
Why is TCP considered fair?

Answer
Because of AIMD: additive increase allows all flows to grow, while multiplicative decrease scales back each flow proportionally.
What is the effect of a shorter RTT on TCP fairness?

Answer
Flows with shorter RTTs increase cwnd faster and tend to get more bandwidth, causing RTT unfairness.
What is TCP Cubic?

Answer
A congestion control algorithm that uses a cubic function for window growth, improving performance in high‑speed networks.
What is TCP BBR?

Answer
A congestion control algorithm that uses bottleneck bandwidth and RTT estimates to set the sending rate, rather than reacting to loss.
What is ECN?

Answer
Explicit Congestion Notification: routers mark packets to signal congestion without dropping them.
How does ECN help TCP?

Answer
It allows the sender to react to congestion earlier, reducing loss and improving performance.
What happens to cwnd on a timeout?

Answer
cwnd = 1 MSS, ssthresh = max(cwnd/2, 2*MSS), and slow start begins.
What happens to cwnd on a triple duplicate ACK in Reno?

Answer
ssthresh = cwnd/2, cwnd = ssthresh + 3*MSS.
What is the difference between slow start and congestion avoidance?

Answer
Slow start doubles cwnd each RTT; congestion avoidance increases cwnd linearly by 1 MSS per RTT.
Why is slow start called "slow" when it doubles cwnd?

Answer
It is slow compared to starting with a large window, but it quickly grows; it's "slow" to avoid initial congestion.
What is the purpose of the 3 duplicate ACK threshold?

Answer
It is a balance between detecting loss quickly and avoiding spurious retransmissions due to packet reordering.
Can TCP congestion control be disabled?

Answer
It can be disabled, but it is not recommended; it would allow a flow to send at any rate, causing unfairness and potential congestion collapse.
What is the "sawtooth" pattern of cwnd?

Answer
cwnd oscillates up linearly (congestion avoidance) and drops multiplicatively (on loss), forming a sawtooth wave.
How does TCP estimate RTT for the purpose of setting timeouts?

Answer
Using SampleRTT, EstimatedRTT, and DevRTT (exponential smoothing) to compute the timeout.
What is the relationship between window size and throughput?

Answer
Throughput = window / RTT, assuming the window is the limiting factor.
What is the effect of a large buffer at the bottleneck on TCP?

Answer
It can lead to bufferbloat: increased latency without a corresponding increase in throughput.
What is the purpose of the initial cwnd in modern TCP?

Answer
It is set to a larger value (e.g., 10 MSS) to reduce the latency of web transfers.
What is the difference between flow control and congestion control?

Answer
Flow control prevents receiver overload; congestion control prevents network overload.
What is the role of the ssthresh variable after a loss?

Answer
It is set to half the cwnd at the time of loss, marking the new threshold for slow start.
How does TCP Cubic differ from Reno in handling high bandwidth‑delay products?

Answer
Cubic uses a cubic function that grows more aggressively for large windows, allowing it to better utilize high‑speed links.
What is the impact of TCP’s congestion control on UDP traffic?

Answer
UDP does not have congestion control, so it can cause unfairness; networks often rate‑limit UDP to protect TCP.

🛠️ Exercises

Apply your knowledge with these 20 exercises. Solutions are provided below each.

Exercise 1: Slow Start Growth
Initially cwnd = 1 MSS, ssthresh = 16 MSS. How many RTTs does it take to reach ssthresh?

Solution
cwnd doubles each RTT: 1,2,4,8,16 → 5 RTTs to reach 16 (the 5th RTT sends 16).
Exercise 2: Congestion Avoidance Growth
After reaching ssthresh=16, how many RTTs to increase cwnd from 16 to 20?

Solution
In congestion avoidance, cwnd increases by 1 MSS per RTT, so from 16 to 20 takes 4 RTTs.
Exercise 3: Loss Handling (Timeout)
If cwnd = 100 MSS and a timeout occurs, what are new cwnd and ssthresh?

Solution
ssthresh = 50 MSS, cwnd = 1 MSS.
Exercise 4: Loss Handling (Triple Duplicate ACK)
If cwnd = 100 MSS and 3 duplicate ACKs are received, what are new cwnd and ssthresh for Reno?

Solution
ssthresh = 50 MSS, cwnd = 50 + 3 = 53 MSS (then congestion avoidance).
Exercise 5: Throughput Calculation
Given MSS = 1460 bytes, RTT = 100 ms, loss rate p = 0.001. Calculate the approximate throughput using the square‑root law.

Solution
Throughput ≈ 1.22 * 1460 / (0.1 * sqrt(0.001)) = 1781.2 / (0.1 * 0.03162) = 1781.2 / 0.003162 ≈ 563,000 bytes/s ≈ 4.5 Mbps.
Exercise 6: Fairness Convergence
Two TCP flows share a 10 Mbps bottleneck. Both have the same RTT. What will their throughput converge to?

Solution
They will converge to approximately 5 Mbps each.
Exercise 7: RTT Unfairness
Flow A has RTT = 50 ms, Flow B has RTT = 100 ms, both share the same bottleneck. Which flow gets more bandwidth?

Solution
Flow A (shorter RTT) will get more bandwidth because it increases cwnd faster.
Exercise 8: Slow Start Initial Window
If initial cwnd = 10 MSS, how long to reach ssthresh = 64 MSS?

Solution
Doubling: 10,20,40,80 → 4 RTTs to reach 80, but it reaches 64 after 3 RTTs (10→20→40→80). Actually at the 3rd RTT it sends 80, so it has reached 64 by then.
Exercise 9: TCP Reno vs Tahoe Comparison
After a triple duplicate ACK, Tahoe sets cwnd=1; Reno sets cwnd=ssthresh+3. Which recovers faster? Why?

Solution
Reno recovers faster because it avoids slow start.
Exercise 10: ECN Benefit
Explain how ECN can reduce the number of retransmissions.

Solution
ECN allows the sender to reduce its rate before packets are dropped, avoiding the need for retransmission.
Exercise 11: Cubic Growth
In TCP Cubic, the window growth is cubic. Why is this better than linear for high‑speed networks?

Solution
Cubic grows faster for large windows, enabling better utilization of high bandwidth‑delay product links while still being fair.
Exercise 12: BBR Operation
How does BBR estimate the available bandwidth?

Solution
It monitors the rate of incoming ACKs to estimate the bottleneck bandwidth and measures the RTT to set the pacing rate.
Exercise 13: Sawtooth Pattern
Sketch the sawtooth pattern of cwnd for TCP Reno over time, indicating slow start, congestion avoidance, and losses.

Solution
A diagram showing exponential growth, then linear growth, then sudden drop, then linear growth again.
Exercise 14: Loss Rate Impact
If the loss rate doubles, by what factor does the throughput decrease according to the square‑root law?

Solution
Throughput ∝ 1/sqrt(p). If p doubles, throughput becomes 1/sqrt(2) ≈ 0.707 times the original (about 30% decrease).
Exercise 15: Bufferbloat
How does a large router buffer affect TCP performance?

Solution
It can increase latency (bufferbloat) but may improve throughput by reducing losses. However, it can cause unfairness and slow reaction.
Exercise 16: ssthresh Update
If cwnd = 200 MSS at the time of loss, what is ssthresh after the loss?

Solution
ssthresh = 100 MSS (assuming no other constraints).
Exercise 17: Timeout vs Fast Retransmit
Which recovers faster from a single packet loss: timeout or fast retransmit? Why?

Solution
Fast retransmit recovers faster because it does not wait for the timer to expire (which is typically much longer than RTT).
Exercise 18: Initial Window
What is the benefit of setting initial cwnd to 10 MSS instead of 1?

Solution
It reduces the latency for short flows (e.g., web pages) by avoiding the slow start ramp‑up.
Exercise 19: Fairness with Different RTTs
If Flow A has RTT 10 ms and Flow B has RTT 100 ms, how much more bandwidth might A get?

Solution
Approximately proportional to 1/RTT (since cwnd grows faster per unit time). A may get about 10 times more bandwidth, though other factors limit it.
Exercise 20: ECN and Loss
With ECN, how does the sender react to congestion?

Solution
The sender reduces its cwnd (similar to a loss event) but without retransmission, using the ECN‑Echo flag.

📚 Homework

These advanced problems require synthesis, research, and quantitative analysis. Sample answers are provided below.

Problem 1: Derive the Square‑Root Law
Derive the square‑root law for TCP Reno throughput. Show the steps, assuming the sawtooth pattern and that losses occur when cwnd reaches its maximum W.

Sample Answer
Let W be the peak cwnd in packets. The sawtooth goes from W/2 to W, then drops to W/2. The average cwnd = 3W/4. The time between losses is W * RTT (since each RTT sends W/2 packets? Actually, we need to derive carefully: each cycle sends about (W/2 + W)/2 * (W/2) packets? The standard derivation: throughput ≈ (1.22 * MSS) / (RTT * sqrt(p)).
Problem 2: AIMD Stability Analysis
Prove that AIMD leads to stable and fair bandwidth allocation for two flows sharing a bottleneck.

Sample Answer
Use the differential equation model: dx/dt = α/x? Actually, the classic proof shows that the ratio of throughputs converges to 1 because additive increase adds equal increments, while multiplicative decrease scales both by the same factor. Thus the difference decreases over time.
Problem 3: TCP Cubic vs. Reno Fairness
Compare the fairness of Cubic and Reno when flows with different RTTs share the same bottleneck. Why is Cubic more fair?

Sample Answer
Cubic uses a cubic function that is less aggressive for small windows and more aggressive for large ones, reducing the RTT bias.
Problem 4: ECN and TCP Performance
Explain how ECN improves TCP performance in terms of latency and throughput. Provide a scenario.

Sample Answer
ECN avoids packet drops, so it reduces retransmissions and latency. In a scenario with bursty traffic, ECN allows the sender to react before queue overflow.
Problem 5: Bufferbloat Mitigation
Discuss strategies to mitigate bufferbloat in TCP networks (e.g., CoDel, PIE, or active queue management).

Sample Answer
Active Queue Management (AQM) like CoDel drops or marks packets based on queue delay, keeping buffers small while maintaining utilization.
Problem 6: TCP Initial Window Impact
Analyze the effect of increasing the initial cwnd from 1 to 10 on web page load times. What are the trade‑offs?

Sample Answer
It reduces latency for short flows, but may cause transient congestion if many connections start simultaneously.
Problem 7: Fairness with UDP
Explain why UDP flows can starve TCP flows in a shared bottleneck. How can this be addressed?

Sample Answer
UDP lacks congestion control and can send at a constant high rate, pushing TCP to back off. Solutions include rate limiting UDP or using per‑flow fairness mechanisms.
Problem 8: TCP BBR vs. Reno
Compare the operating principles of BBR and Reno. In which scenarios does BBR outperform Reno?

Sample Answer
BBR uses bandwidth and RTT estimates; Reno uses loss. BBR performs better in high‑speed networks with lossy links, while Reno may be more conservative.
Problem 9: Loss Rate Measurement
How can a TCP connection estimate the loss rate p? What are the challenges?

Sample Answer
By counting losses over a window of time. Challenges include distinguishing congestion loss from transmission errors, and varying loss rates.
Problem 10: Congestion Window Dynamics
Write a simulation (pseudocode) of the TCP Reno cwnd update loop, including slow start, congestion avoidance, fast retransmit, and fast recovery.

Sample Answer
Pseudocode with variables cwnd, ssthresh, dupACKcount, timer, etc., handling events.
Problem 11: Impact of Packet Reordering
How does packet reordering affect TCP congestion control? How can it cause spurious fast retransmits?

Sample Answer
Reordering can generate duplicate ACKs, leading to unnecessary fast retransmits. TCP may use timestamps or delay ACKs to mitigate.
Problem 12: TCP CUBIC Window Growth
Derive the cubic window growth function and explain how it achieves both fast ramp‑up and fairness.

Sample Answer
cwnd = C * (t - K)^3 + Wmax, where Wmax is the window at the last loss, and K is the time to reach Wmax. It grows faster for larger windows.
Problem 13: ECN and Congestion Window
How does an ECN‑capable sender reduce its cwnd when it receives an ECN‑Echo? Is it the same as a loss?

Sample Answer
It reduces cwnd by half (like a loss) but does not retransmit (unless required). It is similar to a congestion indication.
Problem 14: Throughput with Loss and Timeouts
Modify the square‑root law to include timeouts. How do timeouts reduce throughput?

Sample Answer
Timeouts cause larger idle periods, reducing throughput. A more complex formula includes the probability of timeout.
Problem 15: Fairness in High‑Speed Networks
Discuss the fairness challenges of TCP in high‑speed, long‑distance networks (e.g., 10 Gbps, 100 ms RTT). How do algorithms like Cubic address them?

Sample Answer
In high BDP networks, Reno may take a long time to increase cwnd, limiting throughput. Cubic's aggressive growth fills the pipe faster while maintaining fairness.

📡 Tutorial 9: TCP Congestion Control (Advanced)

Table of Contents

🎯 Learning Objectives

🔍 Overview

📘 1. The Congestion Problem