1
CS 168, Spring 2026 @ UC Berkeley
Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao
Congestion Control, Part 2
Lecture 13 (Transport 4)
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Recall: Congestion Control Problem Statement
Congestion control: Ensuring senders send at an optimal rate. That is, a rate that:
Challenging problem since a host’s optimal sending rate depends on several factors:
No end host has a global view of the network
Recall: Possible Approaches
Congestion Control Protocols
Pricing
Reservations
Dynamic Adjustment
Router-assisted
Host-based
Host-Based Dynamic Adjustment: Algorithm Sketch
Every host independently runs the same algorithm:
Components of a solution:
Host-Based Dynamic Adjustment: Algorithm Sketch
Every host independently runs the same algorithm:
Components of a solution:
Host-Based Dynamic Adjustment: Algorithm Sketch
Every host independently runs the same algorithm:
Components of a solution:
Implementing Congestion Control with Event-driven Updates
Lecture 15, CS 168, Spring 2026
Congestion Control Implementation
TCP Throughput Model
Congestion Control Issues
Router-Assisted Congestion Control
Host-Based Dynamic Adjustment: Algorithm Sketch
Every host independently runs the same algorithm:
How long is "some period of time"?
???
Event-Driven Updates
Instead of updating after "some period of time," CWND updates are event-driven.
Sender adjusts CWND each time something interesting happens in TCP.
Event-Driven Updates
Three interesting events that sender reacts to:
Event-Driven Updates
How to react to these events:
Event-Driven Slow Start
Conceptual slow start: Double CWND after each RTT.
Event-driven slow start: Increase CWND by 1 after each ack.
Intuition:
t = 0 RTTs: CWND = 1 Send 1 packet
t = 1 RTT: get 1 ack CWND = 2 Send 2 packets
t = 2 RTTs: get 2 acks CWND = 4 Send 4 packets
t = 3 RTTs: get 4 acks CWND = 8 Send 8 packets
t = 4 RTTs: get 8 acks CWND = 16 Send 16 packets
Event-Driven Slow Start
Conceptual slow start: Double CWND after each RTT.
Event-driven slow start: Increase CWND by 1 after each ack.
Intuition:
Event-Driven Slow Start
Sender
Recipient
CWND = 1
CWND = 2
CWND = 3
CWND = 4
CWND = 5
CWND = 6
CWND = 7
CWND = 8
First RTT
Second RTT
Third RTT
Fourth RTT
Event-Driven AIMD Adjustments: Additive Increase
Conceptual AIMD increase: Add 1 to CWND after each RTT.
Event-driven AIMD increase: Increase CWND by 1/CWND after each ack.
Intuition:
Implementation:
1
CWND
MSS
CWND
(1/CWND in packets) fraction rewritten in bytes by multiplying top and bottom by packet size: (MSS/CWND in bytes)
Total increase after each RTT should be MSS bytes, not 1 packet.
Note: Technically, increase on each ack is different, but approximation is close enough.
First update: 3.00 + (1/3.00) = 3.33
Second update: 3.33 + (1/3.33) = 3.63
Third update: 3.63 + (1/3.63) = 3.93 ≈ 4
Event-Driven AIMD Adjustments: Multiplicative Decrease
So far, we’ve looked at increasing the CWND.
Conceptual AIMD decrease: Divide CWND in half when loss detected.
Event-driven AIMD decrease: Divide CWND in half when 3 duplicate acks detected.
CWND should never decrease below 1 packet (MSS bytes).
Event-Driven Adjustments: Timeout
When a packet is lost from timeout, abandon current rate and restart from slow-start.
Implementation: When timeout occurs:
Event-Driven Slow Start: SSTHRESH
Denotes the boundary between slow start and congestion avoidance.
Why do we need it?
Event-Driven Updates: SSTHRESH
SSTHRESH helps us remember a likely safe rate.
Loss
Loss
Timeout
Slow Start
AIMD
Loss
SSTHRESH
SSTHRESH
Slow Start
AIMD
Loss
Summary: TCP Congestion Control
Detecting congestion:
Discovering an initial rate:
Adapting rate to congestion:
Fast Recovery
Lecture 15, CS 168, Spring 2026
Congestion Control Implementation
TCP Throughput Model
Congestion Control Issues
Router-Assisted Congestion Control
Fast Recovery
Problem: Additive increases are too slow to recover from isolated loss.
This last feature is an optimization to improve performance.
Fast Recovery: Setting the Stage
Consider sending 10 packets.
The first one (101) is dropped.
Acks for 102–110 all say ack(101) because packet 101 is still missing.
After the third duplicate ack(101), we resend 101.
Eventually, ack for the re-sent 101 says ack(111) because packets 102–110 were all received earlier.
What does CWND look like during this process?
✗
101
102
103
104
105
106
107
108
109
110
ack(101) from 102
ack(101) from 103
ack(101) from 104
ack(101) from 105
ack(101) from 106
ack(101) from 107
ack(101) from 108
ack(101) from 109
ack(101) from 110
ack(111) from 101
Resend 101
Quick recap: TCP Sliding Window
The window is a range of W contiguous bytes, starting at the first unacked byte.
The window slides right if and only if its leftmost bytes are acked.
...
3
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
...
...
1
2
Sent and acked
4
5
6
7
Not sent yet
Window
W bytes
First unacked byte
Fast Recovery: Windows Without Fast Recovery
...
101
102
103
104
105
106
107
108
109
110
111
112
113
After sending 10 packets: CWND = 10. 101–110 can be in flight.
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
After ack(101) from 102: Can't send anything new.
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
After ack(101) from 103: Can't send anything new.
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
After ack(101) from 104: Can't send anything new.
114
115
...
3 duplicate acks detected. CWND = 5.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 105: Can't send anything new.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Note: We're marking acked packets in green for convenience, but the sender cannot deduce from duplicate acks that these exact packets were received.
Fast Recovery: Windows Without Fast Recovery
Problem: After we decreased CWND, we had to wait a long time before sending again.
After ack(101) from 107: Can't send anything new.
After ack(101) from 108: Can't send anything new.
After ack(101) from 109: Can't send anything new.
After ack(101) from 110: Can't send anything new.
After ack(111) from resent 101:�Window slides to first unacked packet (111).
Sender is now able to send 111–115.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 106: Can't send anything new.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Fast Recovery: Windows Without Fast Recovery
Problem: In the entire blue area, after CWND decreased, the sender isn't sending anything.
✗
101
102
103
104
105
106
107
108
109
110
ack(101) from 102
ack(101) from 103
ack(101) from 104
ack(101) from 105
ack(101) from 106
ack(101) from 107
ack(101) from 108
ack(101) from 109
ack(101) from 110
ack(111) from 101
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
CWND = 10. 101–110 can be in flight.
114
115
...
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Resend 101
CWND = 5. 101–105 can be in flight.
Fast Recovery: Windows Without Fast Recovery
Secondary problem: Sender is forced to send a large burst at once, and so has to wait a full RTT for ack(112) to arrive before sending 116+.
ack(101) from 102
ack(101) from 103
ack(101) from 104
ack(101) from 105
ack(101) from 106
ack(101) from 107
ack(101) from 108
ack(101) from 109
ack(101) from 110
111
112
113
114
115
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Resend 101
CWND = 5. 101–105 can be in flight.
ack(111) from 101
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
CWND = 5. 111–115 can be in flight.
The Fast Recovery Problem
The problem, restated again:
The secondary problem, restated again:
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
CWND = 10. 101–110 can be in flight.
114
115
...
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
CWND = 5. 101–105 can be in flight.
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
CWND = 5. 111–115 can be in flight.
The Fast Recovery Problem
The sender can deduce from the duplicate acks that fewer packets are in flight:
The Fast Recovery Problem
The sender can deduce from the duplicate acks that fewer packets are in flight.
Key idea:
Reminder: We had seen this in action before!
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# duplicate acks = 6
Assumptions:
Fast Recovery: Windows with Fast Recovery
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
3 duplicate acks detected. CWND = 5.
Extend window to account for the 3 acks: CWND = 5 + 3 = 8.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 105: Extend window to CWND = 9.
Can't send anything new.
After ack(101) from 104: Can't send anything new.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 103: Can't send anything new.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 102: Can't send anything new.
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After sending 10 packets: CWND = 10.�101–110 can be in flight.
Fast Recovery: Windows with Fast Recovery
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 110: Extend window to C = 14.
We can send 114!
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(111) from resent 101: Back to normal. C = 5.
We can send 115.
After ack(101) from 109: Extend window to C = 13.
We can send 113!
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 108: Extend window to C = 12.
We can send 112!
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 107: Extend window to C = 11.
We can send 111!
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
After ack(101) from 106: Extend window to C = 10.
Can't send anything new.
Fast Recovery: Windows with Fast Recovery
Remember: The sender does not know exactly which packets were acked.
The sender does know how many packets were acked.
The artificially extended window ensures that the total number of packets in flight is still 5 (the new CWND).
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
...
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Fast Recovery: Windows Without Fast Recovery
The sender is now still sending in the blue area!
✗
101
102
103
104
105
106
107
108
109
110
ack(101) from 102
ack(101) from 103
ack(101) from 104
ack(101) from 105
ack(101) from 106
ack(101) from 107
ack(101) from 108
ack(101) from 109
ack(101) from 110
ack(111) from 101
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
CWND = 10. 101–110 can be in flight.
114
115
...
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Resend 101
CWND = 14. 101–114 can be in flight.
Fast Recovery: Windows Without Fast Recovery
Because we sent 111–114 during the blue area, when the new ack(111) arrives, we only have to send 115.�Also, ack(112) will arrive sooner so we can keep sending.
ack(101) from 102
ack(101) from 103
ack(101) from 104
ack(101) from 105
ack(101) from 106
ack(101) from 107
ack(101) from 108
ack(101) from 109
ack(101) from 110
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
Resend 101
CWND = 5. 101–105 can be in flight.
ack(111) from 101
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
CWND = 5. 111–115 can be in flight.
Fast Recovery: Implementation
Conceptually: When a duplicate ack arrives, artificially extend the window to let the sender send one more packet.
Implementation:
State Machine and Variants
Lecture 15, CS 168, Spring 2026
Congestion Control Implementation
TCP Throughput Model
Congestion Control Issues
Router-Assisted Congestion Control
Putting It All Together: TCP with Congestion Control
The sender maintains 5 values:
The recipient maintains a buffer of out-of-order packets.
The sender responds to 3 events:
The recipient responds to receiving a packet: Reply with an ack and a RWND value.
Putting It All Together: TCP with Congestion Control
Events at sender: new ack, duplicate ack, timeout.
When we receive an ack for new data (not previously acked):
Putting It All Together: TCP with Congestion Control
Events at sender: new ack, duplicate ack, timeout.
When we receive a duplicate ack:
If dupACKcount = 3: Do fast retransmit.
If dupACKcount > 3: Do fast recovery.
Putting It All Together: TCP with Congestion Control
Events at sender: new ack, duplicate ack, timeout.
When the timer expires:
TCP Congestion Control State Machine
Congestion Avoidance
Fast Recovery
Slow Start
Timeout
Dup ack
New ack
Dup ack x3
Dup ack x3
Timeout
New ack
Dup ack
New ack
Dup ack
CWND > SSTHRESH
Timeout
TCP Congestion Control Variants
TCP Tahoe:
TCP Reno:
TCP New Reno:
TCP-SACK:
Unless otherwise specified, we're using this one.
Interoperability Between TCP Congestion Control Variants
How can all these variants co-exist? Don't we need a single, uniform standard?
What happens if I use Reno, you use Tahoe, and we try to communicate?
What happens if I use Tahoe, and you use SACK?
TCP Throughput Model
Lecture 15, CS 168, Spring 2026
Congestion Control Implementation
TCP Throughput Model
Congestion Control Issues
Router-Assisted Congestion Control
Our Goal: The TCP Throughput Equation
Given a path through the network, what TCP throughput can we expect?
We'll derive a simple model that expressed TCP throughput in terms of path properties:
TCP Throughput Equation: Simplifying Assumptions
Simplifying assumptions:
We'll assume a single, non-changing path through the network:
TCP Throughput in Terms of Window Size
From our assumptions: We lose a packet when CWND reaches Wmax.
Window size changing over time:
TCP Throughput in Terms of Window Size
Window size changing over time:
Average window size is 3/4 × Wmax.
Wmax
0.5 × Wmax
Average: 3/4 × Wmax
Time
Window Size
TCP Throughput in Terms of Window Size
Unit conversion:
Computing throughput:
Throughput = Wmax ×
Next step: Express Wmax in terms of p, the loss rate.
3
4
MSS
RTT
Relating Window and Loss Rate
Next step: Express Wmax in terms of p, the loss rate.
Loss
Loss
Loss
Wmax
0.5 × Wmax
Average: 3/4 × Wmax
(0.5 × Wmax) RTTs
Time between losses
Time
Window Size
Relating Window and Loss Rate
How many packets are sent in (0.5 × Wmax) RTTs?
Loss
Loss
Loss
Wmax / RTT
(0.5 × Wmax) / RTT
Average: (3/4 × Wmax) / RTT
Width = (0.5 × Wmax) RTT
Height = (3/4 × Wmax) / RTT
Time
Rate
Relating Window and Loss Rate
Next step: Express Wmax in terms of p, the loss rate.
Loss rate = p =
Loss
Loss
Loss
Time
Rate
Wmax / RTT
(0.5 × Wmax) / RTT
Average: (3/4 × Wmax) / RTT
Width = (0.5 × Wmax) RTT
Height = (3/4 × Wmax) / RTT
8
3Wmax2
Relating Window and Loss Rate
Loss rate = p =
Do some algebra to isolate Wmax in terms of p:
8
3Wmax2
Relating Window and Loss Rate
Do some more algebra to plug this into our original throughput equation:
The TCP Throughput Equation
Throughput =
This tells us that:
Consequences of Equation (1/2): Flows with Different RTTs
Throughput =
TCP is inherently unfair when flows have different RTTs.
From the equation: A–B gets twice as much bandwidth as X–Y.
A
X
B
Y
100 ms
200 ms
R1
R2
Consequences of Equation (2/2): Rate-Based Congestion Control
Throughput =
TCP throughput is choppy: Rate oscillates between W/2 and W.
Some applications (e.g. video streaming) would prefer sending at a steady rate.
Solution: Equation-based congestion control.
Using the equation ensures fairness: We don't use more bandwidth than TCP would.
Look up RFC 5348 for spec.
Congestion Control Issues
Lecture 15, CS 168, Spring 2026
Congestion Control Implementation
TCP Throughput Model
Congestion Control Issues
Router-Assisted Congestion Control
Congestion Control Issues
We'll look at 5 issues (and potential solutions):
Issues (1/5): Confusing Corruption and Congestion
TCP detects congestion by checking for loss.
From the equation: Higher loss = lower throughput.
Issues (2/5): Short Connections
Most real-life TCP connections are really short.
Many connections stay in slow-start the whole time.
Not enough packets to trigger duplicate acks.
Partial fix: Start with a higher initial CWND.
Look up RFC 5348 for experiments on this.
Sender
Recipient
Recall slow start: Start with CWND = 1, double every RTT.
It took ≈2 RTTs to send 3 packets.
Issues (3/5): Router Queues Get Filled Up
TCP deliberately overshoots capacity until packets get dropped.
Result: Delays are large for everybody.
The problem is even worse if routers keep really long queues.
Issues (3/5): Router Queues Get Filled Up
Possible solution: Google's BBR algorithm (2016).
Congestion Control Protocols
Pricing
Reservations
Dynamic Adjustment
Router-assisted
Host-based
Loss-based
Delay-based
BBR is here.
TCP is here.
Issues (4/5): Cheating
Nobody is enforcing that users follow the TCP congestion control algorithm.
Cheating strategy: Change the algorithm.
Cheating strategy: Open lots of connections.
Issues (4/5): Cheating
Applying graphical model to a cheating host:
Suppose current allocation is (X, Y).
If both increase additively: (X + 2a, Y + a).
Notice: Slope of this line is now 1/2, not 1.
1
1
Fairness Line:
X = 2Y
Efficiency Line:
X + Y = 1
(X, Y)
(X+2a, Y+a)
AIMD (Additive Increase, Multiplicative Decrease) Adjustments on Graph
Increase: +2 (X), +1(Y) Decrease: ÷2
Because X is cheating, AIMD converges toward a "fairness" line where X has twice as much bandwidth as Y.
1
1
Efficiency Line:
X + Y = 1
Fairness Line:
X = 2Y
Issues (4/5): Cheating
Why hasn't the Internet suffered another congestion collapse? Some theories:
How much cheating occurs in practice?
| |
Google’s Network Congestion Algorithm Isn’t Fair, Researchers Say | |
Karl Bode | October 31, 2019 |
Issues (5/5): Congestion Control and Reliability are Intertwined
Mechanisms for congestion control and reliability are tightly coupled.
This complicates evolution.
Sometimes we only want one, but not the other.
Router-Assisted Congestion Control
Lecture 15, CS 168, Spring 2026
Congestion Control Implementation
TCP Throughput Model
Congestion Control Issues
Router-Assisted Congestion Control
Router-Assisted Congestion Control
Many of our issues could be fixed with some help from routers!
Two ways routers can help:
Enforcing Fairness
How can routers ensure each flow gets its fair share?
What does fair mean exactly?
Round-Robin (Equal Packet Size)
For now, assume all packets are the same size.
Suppose we have three connections:
Suppose we only have capacity to send 10 packets.
Round-robin service: Take turns sending packets from each queue.
A1
A2
A3
A4
A5
A6
A7
A8
B1
B2
B3
B4
B5
B6
C1
C2
A5
A6
A7
A8
B5
B6
A1
A2
A3
A4
B1
B2
B3
B4
C1
C2
Round-Robin (Equal Packet Size)
With round-robin service and capacity 10:
Property: If you don't get your full demand, nobody gets more than you.
Max-Min Fairness (Equal Packet Size)
Instead of round-robin, we could mathematically solve max-min fairness.
Resource allocation problem:
Intuitive solution:
Round-Robin (Unequal Packet Size)
How do we deal with packets of different sizes?
We won’t cover fair queueing in detail this class, but if you’re interested please refer to the paper below.
Analysis and Simulation of a Fair Queueing Algorithm | ||
Alan Demers, Srinivasan Keshav, Scott Shenker | 1990 | |
Note: Fair Queuing Does Not Solve Congestion
Fair queuing does not eliminate congestion.
Fair queuing can manage congestion.
R1
A
X
R2
B
Y
5
1
1
1
0.1
Router-Assisted Congestion Control
Two ways routers can help:
Router-Assisted Rate Adaptation
Why not just let routers tell the end hosts what rate they should use?
Possible design:
Now, the sender doesn't need to dynamically adjust to find a good rate.
Router-Assisted Congestion Detection
Explicit Congestion Notification (ECN) bit: Single bit in the IP packet header.
Used in some, but not all routers.