# CS 176C: Bufferbloats and AQM <!-- Put the link to this slide here so people can follow --> [Slides](https://hackmd.io/p/J_NQjC-NTc2ro4Cejdh5jQ) --- ## 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