CS 176C:

Learning Objectives

• Bufferbloats
  • Why do we see bufferbloats, and why should we care?
• Active Queue Management (AQM)
  • Why do we need active queue management?
  • What is CoDel?
  • What is PIE?

Why do we see packet bursts?

• Initial congestion window

  • recall TCP slowstart

• Multiple short TCP connections per application

• Capacity mismatch

  • consider a router with
    • links: incoming 1 Gbps, outgoing 100 Mbps
    • average data rate is 100 Mbps

Buffers in the Network

• Pros
  • absorb traffic bursts \(\rightarrow\) efficient
• Cons:
  • increases latency \(\rightarrow\) unfair
  • messes up TCP's control loop
    • queuing delay is not a loss

Bufferbloat

• Large buffers \(\rightarrow\) Sawtooth behavior
• What is sawtooth behavior?
  • starts with partial buffer
  • fill buffer and increase congestion window
  • buffer full \(\rightarrow\) packet drop
  • back off
• What is bufferbloat?
  • large delays w/o improvements in throughput

Understanding Bufferbloats (1)

• Sender's window: 25 packets
• Pipe size (BDP): 20 packets
  • height \(\rightarrow\) B
  • weight \(\rightarrow\) D
• ingress/egress capacity ratio: 10

Understanding Bufferbloats (2)

• bottleneck spaces out the packets
• ack stream retains spacing
• After one RTT
  • packet-arrival rate \(=\) packet-departure rate (at buffer)

Understanding Bufferbloats (3)

Queue size vs. time

• Initially
  • Sending rate \(\downarrow\) \(\rightarrow\) Queue Size \(\downarrow\)
• After one RTT,
  • packet's arrival rate \(=\) departure rate
  • queue size = (window - BDP)

Solutions

• Fix TCP
  • use delay for congestion control
• Tune buffers/TCP
  • dynamically resize buffers
  • make window match pipe size
• Packet scheduling/shaping
  • recall previous class
• Active queue management
  • detect problem at buffers
  • send signals to sender

Active Queue Management

• Signal \(\rightarrow\) packet drops
• Detection
  • Random early detection (RED)
    • average queue length
  • Controlled delay (CoDel)
    • minimum sojourn time in an interval
  • Proportional integral enhanced (PIE)
    • queue delay

Random Early Detection (RED)

• Challenges
  • Is queue length a good indicator?
  • How to compute drop probability?

Controlled Delay (CoDel)

• Insight:
  • discriminates between bad and good queues
    • good queues: clear up in one RTT
    • bad queues: persist for long
• Detection:
  • Measures sojourn time
    • i.e., time spent by a packet in a queue
• Signal:
  • drops packet at dequeue
  • drops tail packet if buffer is full

CoDel Algorithm

Analysing CoDel (1)

• Pros:
  • Effective
    • directly control latency
  • Adaptive
    • adapts to dynamically changing link rates

Analysing CoDel (2)

• Cons
  • Configuring target delay, interval size, etc. is non-trivial
  • Head-drop complexity
  • Requires per-packet timestamp

Proportional Integral Enhanced (PIE)

• Insight
  • best of both worlds
    • easy to implement (RED)
    • directly control latency (CoDEL)
• Detection
  • dequeue rate
• Signal
  • drops packet at enqueue (tail)

PIE Algorithm (1)

PIE Algorithm (2)

• Drop probability (\(p\)) (every \(T_{update}\))
  • \(d_{curr} = Q/dr_{avg}\)
  • \(p=p+\alpha.(d_{cur}-d_{tgt})+\beta.(d_{cur}-d_{old})\)
  • \(d_{old} = d_{cur}\)
• Departure rate (at regular interval)
  • count \(+=\) pkt-size
  • T = now-start
  • \(dr_{curr}\) = \(\frac{count}{T}\)
  • \(dr_{avg}\) = \((1-\epsilon).dr_{avg}+ \epsilon.dr_{curr}\)

Analysing PIE

• Pros
  • Effective
    • directly control latency
  • Efficient
    • high link utilization
  • Simple
    • tail drop, no per-packet state
    • works for different topology, streams, etc.

Analysing PIE

• Cons
  • Tuning
    • tuning \(\alpha\), \(\beta\), \(T_{update}\), \(dr_{avg}\), etc. is non-trivial?

CoDel vs. PIE

VoIP/Gaming traffic

• CoDel~PIE << Bufferbloat
• PIE is easiest to implement (preferred)

DOCSIS-PIE

• Target delay
  • 10 ms (derived from extensive simulation study)
• Departure-rate estimation
  • Simple EWMA doesn't work
    • Request-grant mechanism
    • Competing traffic shaping
  • DOCSIS specifies a custom rate-estimation function

Summary:

• Bufferbloat
• Active queue management
  • CoDel
  • PIE
• Next class
  • Active Measurements
  • Measure Broadband America