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

  • Pick an initial rate R → How to pick initial rate
  • 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
  • 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

  • Slow Start
  • Congestion Avoidance
  • 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

  • Slow Start
    • Rapidly increase our initial sending rate until we hit bottleneck
  • Congestion Avoidance
    • Adapting our sending rate to current network conditions
    • AIMD (Additive Increase, Multiplicative Decrease)
  • 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

  • Slow Start
  • Congestion Avoidance
  • 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

  • Slow Start
  • Congestion Avoidance
  • 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

  • Slow Start
  • Congestion Avoidance
  • 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