1 of 41

Discussion 7

1

CS 168, Summer 2025 @ UC Berkeley

Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao, Iuniana Oprescu

Congestion Control 📈

2 of 41

Logistics

  • Project 3A: Transport
    • Deadline: Tuesday, July 29th
  • Project 3B: Transport
    • Deadline: Tuesday, August 5th
  • Midterm on July 22nd, 7-9pm (put it in your calendar)!
    • You can bring two 8.5” x 11” cheat sheets, each two-sided (4 sides total)
    • Scope TBD

​

3 of 41

TCP Circa 1986

  • What happens when router buffers fill up?
    • Packets get dropped
  • Then what happens at the sender?
    • Increased RTT, timeouts, retransmits
      • →More packets in the network!!
      • … So more retransmits!
  • Eventually, useful throughput approaches zero
  • This is the congestion collapse of 1986!

4 of 41

Congestion Control

5 of 41

Goal of Congestion Control

  • Limit the # of packets in flight
    • Utilize our fair share of bandwidth…
    • But don’t overload the network
  • Adapt to the right bandwidth
  • Be fair
    • Links are shared among many hosts

6 of 41

A naïve solution

  • Overwhelmed? Tell the sender to slow down!
    • Both routers & receiver
  • “Source Quench”
    • signals the originating device to reduce the amount of traffic it is sending
  • Problems?
    • If the link is already overwhelmed, these extra messages may be dropped too! (or add more traffic)

7 of 41

A host-based solution sketch

  1. Pick an initial rate R
  2. Try sending at rate R for some period of time
    • If congestion: reduce R
    • Else: increase R
  3. Repeat step 2

8 of 41

A host-based solution sketch

  1. Pick an initial rate R → How to pick initial rate
  2. Try sending at rate R for some period of time → How to detect congestion
    • If congestion: reduce R → How much to increase/decrease
    • Else: increase R
  3. Repeat step 2

9 of 41

TCP: loss-based feedback

Idea: drop implies congestion

  • 3 dupACK: minor congestion (ACKs get through)
  • Timeout: major congestion (nothing gets through)

​

TCP’s response depends on the kind of loss.

10 of 41

Congestion Control: Windows

  • Receive Window (RWND)
    • What rate at which the receiver can process packets
  • Congestion Window (CWND)
    • What rate at which the network can process packets
  • Sending rate
    • Smaller of the two
  • In this class, we assume CWND << RWND
    • Network will determine our sending rate

11 of 41

TCP Sawtooth

Time

CWND

Slow Start

3 Dup ACKs

3 Dup ACKs

Timeout

Congestion Avoidance/

Fast Recovery

12 of 41

Utilization

  • The TCP sawtooth alternates between:
    • Over-utilizing bandwidth (causing drops)
    • Under-utilizing bandwidth
  • Smart choices around buffering can result in higher utilization by absorbing the increase in window size

13 of 41

Three States

  1. Slow Start
  2. Congestion Avoidance
  3. Fast Recovery

Time

CWND

Slow Start

3 Dup ACKs

3 Dup ACKs

Timeout

Congestion Avoidance/

Fast Recovery

14 of 41

The Big Picture

slow �start

congestion �avoidance

fast �recovery

cwnd > ssthresh

timeout

dupACK=3

timeout

dupACK=3

new ACK

dupACK

new ACK

timeout

new ACK

dupACK

dupACK

15 of 41

Implementation

  • State at sender
    • CWND
      • Max sending rate without congesting network (assuming CWND << RWND)
    • Ssthresh (slow-start threshold)
      • Threshold CWND for exiting slow start
    • dupACKcount
      • Count of contiguous duplicate ACKs received
    • Timer

16 of 41

Congestion Control Mechanics

  1. Slow Start
    • Rapidly increase our initial sending rate until we hit bottleneck
  2. Congestion Avoidance
    • Adapting our sending rate to current network conditions
    • AIMD (Additive Increase, Multiplicative Decrease)
  3. Fast Recovery
    • Optimizing recovery from isolated loss
    • Detected through Duplicate ACKs

17 of 41

Implementation

  • Events at sender
    • ACK (new data)
    • dupACK (duplicate ACK for old data)
    • Timeout

​

  • … receiver just receives packets and sends ACKs

​

18 of 41

Three States

  1. Slow Start
  2. Congestion Avoidance
  3. Fast Recovery

Time

CWND

Slow Start

3 Dup ACKs

3 Dup ACKs

Timeout

Congestion Avoidance/

Fast Recovery

19 of 41

Slow Start

  • Value of CWND starts at (small constant) * MSS
  • For each packet that is acknowledged, increase the CWND by 1
    • Effectively doubles CWND every RTT!

​

  • Window goes from 1 → 2 → 4 → …

​

20 of 41

Slow Start – Intuition

  • Instead of blasting packets based on the receive window
  • Build up initial transmission rate slowly
  • Back off when we’ve exceeded the capacity
  • It’s exponential growth, but still a slow start

21 of 41

Slow Start – When does it end?

  • 2 Ways
    1. If CWND > ssthresh
      • Enter congestion avoidance
    2. If we get 3 duplicate ACKs
      • Enter Fast Recovery

​

  • If timeout:
    • Restart slow start, ssthresh = cwnd/2, CWND = 1

​

22 of 41

Slow Start

Slow Start

Timeout

  • ssthresh = cwnd / 2
  • cwnd = 1
  • dupAckCount = 0

DupACK

- DupAckCount++

New ACK

  • cwnd = cwnd + 1
  • dupAckCount = 0

dupAckCount == 3

Move to Fast Recovery

  • ssthresh = cwnd / 2
  • cwnd = ssthresh + 3
  • Retransmit missing packet

cwnd > ssthresh

Move to Congestion Avoidance

23 of 41

Three States

  1. Slow Start
  2. Congestion Avoidance
  3. Fast Recovery

Time

CWND

Slow Start

3 Dup ACKs

3 Dup ACKs

Timeout

Congestion Avoidance/

Fast Recovery

24 of 41

Congestion Avoidance – Intuition

  • In the steady state
  • Constantly probe for more bandwidth
  • When we’ve exceeded – back off aggressively

25 of 41

Congestion Avoidance

  • Growth is more conservative than slow start
  • After each new ACK, increase CWND by 1 / CWND
    • After one RTT, CWND will have increased by ~1
  • When does it stop?
    1. Timeout → back to slow start
    2. 3 duplicate ACKS → Fast recovery

26 of 41

Congestion Avoidance

Congestion Avoidance

DupACK

-DupAckCount++

New ACK

  • cwnd = cwnd + 1/cwnd
  • dupAckCount = 0

Timeout

Move to Slow Start

  • ssthresh = cwnd / 2
  • cwnd = 1

- dupAckCount = 0

dupACKCount == 3

Move to Fast Recovery

  • ssthresh = cwnd / 2
  • cwnd = ssthresh + 3
  • Retransmit missing packet

​

​

27 of 41

Three States

  1. Slow Start
  2. Congestion Avoidance
  3. Fast Recovery

Time

CWND

Slow Start

3 Dup ACKs

3 Dup ACKs

Timeout

Congestion Avoidance/

Fast Recovery

28 of 41

Fast Recovery – Intuition

  • A single lost packet
    • May just be a fluke
  • Resetting CWND may be too aggressive
  • Instead just retransmit that single packet
    • And continue as if nothing happened

​

29 of 41

Fast Recovery

  • Every duplicate ACK increases the window by 1

​

  • When does it stop?
    1. Timeout → back to Slow Start
    2. New ACK → back to Congestion Avoidance

30 of 41

Fast Recovery

Fast Recovery

Timeout

Move to Slow Start

- ssthresh = cwnd / 2

- cwnd = 1

- dupAckCount = 0

New ACK

Move to Congestion Avoidance

  • cwnd = ssthresh
  • dupAckCount = 0

DupACK

- cwnd = cwnd + 1

31 of 41

Big Ideas

  • Fundamental concepts:
    • Slow Start
    • AIMD
  • Hack
    • Fast Recovery
  • ​
  • Lesson
    • Sometimes, BAND-AIDs scale remarkably well!

32 of 41

Worksheet

  • True/False
  • Impact of Fast Recovery
  • AIMD Throughput

33 of 41

Question 1: True/False

34 of 41

Worksheet

  • True/False
  • Impact of Fast Recovery
  • AIMD Throughput

35 of 41

Question 2: Impact of Fast Recovery

36 of 41

Question 2: Impact of Fast Recovery

37 of 41

Worksheet

  • True/False
  • Impact of Fast Recovery
  • AIMD Throughput

38 of 41

Question 3: AIMD Throughput

39 of 41

Question 3: AIMD Throughput

40 of 41

Question 3: AIMD Throughput

41 of 41

Questions?

Feedback Form: https://tinyurl.com/cs168-su25-disc-feedback