WIXLIB

The New AQM Kids on the Block: AnExperimental Evaluation of CoDel and PIENaeem Khademi naeemk@ifi.uio.no David Ros dros@simula.no Michael Welzl michawe@ifi.uio.no 17th IEEE Global Internet Symposium – 2014Toronto, ON, CanadaN. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20141 / 21

OutlineOutlineAQMAQM mechanisms consideredCoDelPIEAREDExperimental SetupA Basic TestParameter SensitivityConclusions and Future WorkQ&AN. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20142 / 21

AQMActive Queue Management (AQM)IProblem: Standard loss-based TCP’s congestion control plusLarge unmanaged buffers in Internet routers, switches, devicedrivers,. (a.k.a Bufferbloat)ICause: Latency issues for interactive/multimedia applicationsISolution: AQM tries to signal the onset of congestion by(randomly?) dropping/marking packetsAQM GoalsIMaintain low average queue/latencyIAllow occasional packet burstsIBreak synchronization among TCP flowsN. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20143 / 21

AQM mechanisms consideredThe New AQM Kids on the Block.ITwo very recent proposals:II(FQ )CoDel (IETF 84)PIE (IETF 85) mandatory in DOCSIS 3.1 CMISome older AQMs dating back to early 90’s/00’s (*RED, REM,BLUE, CHOKe,.)ILittle academic literature available on CoDel and PIEIDesigned to be better than RED, just like CoDel and PIELiterature (bold peer-reviewed)Wired, simWired, real-lifeWireless (any)CoDel[NJ12][GRT 13][WP12][Whi13][GRT 13] XXPIE[Whi13]FQ CoDel[Whi13]XXX-NOTE: [WP12] and [Whi13] are on DOCSIS 3.0 while [GRT 13] has tests withLow-Priority congestion control.N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20144 / 21

AQM mechanisms consideredThe New AQM Kids on the Block (cont.)AQM Deployment StatusI(W)RED is available on plenty of HW but mostly "turned off"Mentioned Reasons for Lack of DeploymentIBad implementation (?)IHard to tune RED paramsISally Floyd’s ARED (2001 technical report, available in Linux)adaptively tunes RED params aiming for a certain target queuing with fixed BW maps to a "target delay"ITarget delay can be set in ARED, CoDel and PIEN. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20145 / 21

AQM mechanisms consideredCoDelThe New AQM Kids on the Block (cont.)CoDel – Controlling DelayITries to detect the standing queue by measuring minimum sojourndelay (delaymin ) over a fixed-duration interval (default 100 ms)IUses timestampingIIf delaymin target for at least one interval, enters dropping modeand a packet is dropped from the tail (deque)INext dropping time: Dropping interval decreases in inverseproportion to the square root of the number of drops since thedropping mode was enteredIExits dropping mode if delaymin targetINo drop when queue is less than 1 MTUN. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20146 / 21

AQM mechanisms consideredCoDelThe New AQM Kids on the Block (cont.)CoDel AssumptionsI100 ms is nominal RTT assumed typical on the Internet pathsIinterval 100 ms; assures protection of normal packet burstsIA small target standing queue (5% of nominal RTT) is tolerable forachieving better link utilizationN. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20147 / 21

AQM mechanisms consideredPIEThe New AQM Kids on the Block (cont.)PIE – Proportional Integral controller EnhancedILightweight as it uses delay estimation instead of timestampingIUses a Proportional Integral (PI) controller designIUses trend of latency (increasing or decreasing) over time todetermine the congestion levelIE[T ] as current estimated queuing delay during every tupdate , N ascurrent queue length and µ is the draining rateE[T ] N/µIRandomly drops on enque based on probability pp p α (E[T ] Ttarget ) β (E[T ] E[T ]old )N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20148 / 21

AQM mechanisms consideredAREDThe New AQM Kids on the Block (cont.)ARED – Adaptive REDITries to solve RED’s main problem of parameter tuning to keep theaverage queue length (N̄) around a desired target queuingItarget queuing (th max th min)/2IObserves N̄ to make RED more/less aggressiveIUpdates RED’s pmax adaptively (every 500 ms by default) using anAIMD policyIOnly useful in fixed-BW scenarios(target delay target queuing/BW )N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 20149 / 21

Experimental SetupExperimental SetupI Traffic: 60 sec (or 300 sec if RTT 500 ms) of TCP traffic by iperf, repeated for 10 runsI AQM iface: GSO TSO off, BQL 1514, txqueuelen 1000I TCP: Linux default with renoI Topology: Dumbbell with 4 sender-receiver pairsModelCPURAMEthernetEthernet driverOS kernelDell OptiPlex GX620Intel(R) Pentium(R) 4 CPU 3.00 GHz1 GB PC2-4200 (533 MHz)Broadcom NetXtreme BCM5751RTL-8139 (AQM interface)RTL8111/8168B (Dummynet router)tg38139too (AQM interface)r8168 (Dummynet router)Linux 3.8.2 (FC14)Linux 3.10.4 (AQM router) (FC16)N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.100 Mbps100 Mbps100 Mbps100 Mbps10 MbpsAQM100 MbpsDummynet router100 Mbps100 MbpsBottleneck router100 MbpsApril 28, 201410 / 21

Experimental SetupExperimental Setup (cont.)IAQM parameters used unless otherwise noted.CoDelinterval 100 mstarget 5 msAREDPIEparameters in [pie].PIE Parameter Default valuetupdate30 msTtarget20 msα0.125β1.25N. Khademi, D. Ros, M. Welzlparameters in [FGS01].ARED ParameterDefault valueinterval500 msαmin(0.01, pmax /4)β0.9th min0.5 targetth max1.5 targetThe New AQM Kids on the Block.April 28, 201411 / 21

Experimental SetupExperimental Setup (cont.)IRTT is measured on per-packet basis using Synthetic PacketPairs (SPP) tool [spp]IIGives a very precise distribution of perceived RTT on the pathGoodput is measured per 5-sec intervalsIlong-term throughput/goodput does not reflect AQM performanceover time (e.g. bursts of packet drops are not desired)N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201412 / 21

A Basic TestA Basic oodput (Mbps)RTT (ms)Single TCP Flow (RTTbase 100 ms)111555 10 10 10 20 20 20 30 30 30Target Delay Del(a) Per-packet RTT555 10 10 10 20 20 20 30 30 30Target Delay (ms)PIEARED(b) GoodputPer-packet RTT and goodput. Bottom and top of whisker-box plots show 10th and 90thpercentiles respectively.N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201413 / 21

A Basic TestA Basic Test (cont.)CoDel vs. RED from K. Nichols, “Controlling QueueDelay” [NJ12]IA similar trend canbe observed betweenCoDel and RED in adifferent test in[NJ12]FTP traffic mix w/ and w/o web-browsing and CBRapplications and RTTs from 10 500 ms.N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201414 / 21

Parameter SensitivityParameter Sensitivity (cont.)1115CoDel55 10 10 10 20 20 20 30 30 30Target Delay (ms)PIEARED(c) 100RTT 00RTT (ms)RTT (ms)Target Delay111CoDel555 10 10 10 20 20 20 30 30 30Target Delay (ms)PIEARED(d) 1101001115CoDel55 10 10 10 20 20 20 30 30 30Target Delay (ms)PIEARED(e) HeavyPer-packet RTT. Light, moderate and heavy congestion scenarios (4 senders andRTTbase 100 ms).Light, moderate and heavy congestion correspond to 4, 16 and 64 concurrent TCP flowsrespectively.N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201415 / 21

Parameter SensitivityParameter Sensitivity (cont.)Goodput (Mbps)Target Delay109.598.518.518155CoDel5 10 10 10 20 20 20 30 30 30Target Delay (ms)PIEARED7.5(g) Moderate76.565.5111CoDel555 10 10 10 20 20 20 30 30 30Target Delay (ms)PIE(f) LightGoodput (Mbps)Goodput (Mbps)9109.5109.598.5111AREDCoDel555 10 10 10 20 20 20 30 30 30Target Delay (ms)PIEARED(h) HeavyGoodput. Light, Moderate and Heavy congestion scenarios (4 senders and RTTbase 100 ms).N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201416 / 21

Parameter SensitivityParameter Sensitivity (cont.)CoDel’s Dropping Mode Interval – Target Delay 5 ms180170Goodput (Mbps)RTT 303030Interval (ms)Moderate1001001005303030Interval (ms)Moderate100100100Heavy(j) GoodputHeavy(i) Per-packet RTT4 senders, RTTbase 100 ms.N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201417 / 21

Parameter SensitivityParameter Sensitivity 00Goodput (Mbps)RTT (ms)PIE’s t update Interval – Target Delay 5 ms109.598.5855Light55Light5303030Interval (ms)Moderate1001001005303030Interval (ms)Moderate100100100Heavy(l) GoodputHeavy(k) Per-packet RTT4 senders, RTTbase 100 ms.N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201418 / 21

Conclusions and Future WorkConclusionsIARED: Only performed worse than CoDel or PIE with smallnumber of flowsICoDel: Dropping mode interval can be reduced to lower the delaywithout degrading the goodput muchIPIE (as implemented in Linux): Long distribution tail for lowtarget delaysFuture WorkIMore realistic traffic types (here, only bulk TCP traffic) includingbursty trafficISimulations for environment parameters that cannot be producedwith our testbedN. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201419 / 21

Q&ABibliography[FGS01]Sally Floyd, Ramakrishna Gummadi, and Scott Shenker.Adaptive RED: An Algorithm for Increasing the Robustness of RED’s Active Queue Management.Technical report, 2001.[GRT 13] Y. Gong, D. Rossi, C. Testa, S. Valenti, and D. Taht.Fighting the Bufferbloat: On the Coexistence of AQM and Low Priority Congestion Control.2013.[NJ12]Kathleen Nichols and Van Jacobson.Controlling Queue Delay.Queue, 10(5):20:20–20:34, May 2012.[pie]PIE Linux code (Cisco).ftp://ftpeng.cisco.com/pie/linux code/.[spp]Synthetic Packet eg White.A Simulation Study of CoDel, SFQ-CoDel and PIE in DOCSIS 3.0 Networks.Technical Report, CableLabs, April 2013.[WP12]Greg White and Joey Padden.Preliminary Study of CoDel AQM in a DOCSIS Network.Technical Report, CableLabs, November 2012.N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201420 / 21

Q&AQ&AMore on experimental results: N. Khademi, D. Ros, and M. Welzl,“The New AQM Kids on the Block: Much Ado About Nothing?”,Technical Report 434, Department of Informatics, University of Oslo,23 October 2013, available at http://urn.nb.no/URN:NBN:no-38868N. Khademi, D. Ros, M. WelzlThe New AQM Kids on the Block.April 28, 201421 / 21

AQM mechanisms considered The New AQM Kids on the Block. I Two very recent proposals: I (FQ_)CoDel(IETF84) I PIE(IETF85) mandatory in DOCSIS3.1 CM I Some older AQMs dating back to early 90's/00's (*RED, REM, BLUE, CHOKe,.) I Designed to be better than RED, just like CoDel and PIE I Little academic literature available on CoDel and PIE Literature (bold peer-reviewed)