{"id":83,"date":"2018-12-20T11:50:19","date_gmt":"2018-12-20T11:50:19","guid":{"rendered":"https:\/\/hhk3.kau.se\/fid\/?page_id=83"},"modified":"2020-08-29T22:33:35","modified_gmt":"2020-08-29T21:33:35","slug":"aqm","status":"publish","type":"page","link":"https:\/\/hhk3.kau.se\/latency\/modules\/aqm\/","title":{"rendered":"Active queue management"},"content":{"rendered":"<p>We have seen in the previous part of the course that there are many sources of delay. One of the most important is queueing delay as it can be very large in magnitude. In this part we take a closer look at queueing delay and the bufferbloat phenomenon and how active queue management (AQM) and fairness queueing can help mitigate the problem.<\/p>\n<h3>Course lecture: A closer look at bufferbloat<\/h3>\n<p><iframe loading=\"lazy\" title=\"A closer look at Bufferbloat\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/47keG2yR06s?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>If you did not read the\u00a0paper on\u00a0bufferbloat by Jim Gettys and Kathleen Nichols as part of getting aquainted to the sources of delay on the Internet, do so now: J. Gettys and K. Nichols, <a href=\"https:\/\/queue.acm.org\/detail.cfm?id=2071893\">Bufferbloat: Dark Buffers in the Internet<\/a>, ACM Queue, nov. 2011, vol . 9, no. 11.<\/p>\n<h3>Course lecture: Active queue management<\/h3>\n<p><iframe loading=\"lazy\" title=\"Active Queue Management\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/C5mDeJL3szU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h3><\/h3>\n<h3>Practical Exercise<\/h3>\n<p>The purpose of this exercise is to experience hands-on how different queueing algorithms affects queueing delay and reduce buffer bloat. The goal is to quantify how packet delay is affected by concurrent bulk flows that increase buffer occupancy, and how different algorithms can be used to mitigate this behavior.<\/p>\n<p>The experiment environment consists of the network emulator \u2019mininet\u2019, running in a Linux virtual machine in VirtualBox. This provides a consistent and reproducible network setup to ensure that you will experience the expected effect of the settings.<\/p>\n<p>VirtualBox to run the virtual machine is available (without cost) at <a href=\"https:\/\/www.virtualbox.org\/\">https:\/\/www.virtualbox.org\/<\/a><br \/>\nThe virtual machine is available at\u00a0 <a href=\"https:\/\/kau.box.com\/v\/latency-vm\">https:\/\/kau.box.com\/v\/latency-vm<\/a><br \/>\nThe experiment code is available at <a href=\"https:\/\/git.cse.kau.se\/courses\/dvad60\/blob\/master\/latency\">https:\/\/git.cse.kau.se\/courses\/dvad60\/blob\/master\/latency<\/a><\/p>\n<p>The instructions to perform the exercise is documented in <a href=\"https:\/\/git.cse.kau.se\/courses\/dvad60\/blob\/master\/latency\/README.txt\">https:\/\/git.cse.kau.se\/courses\/dvad60\/blob\/master\/latency\/README.txt<\/a><\/p>\n<p>There is a presentation\u00a0slideset at <a href=\"https:\/\/git.cse.kau.se\/courses\/dvad60\/blob\/master\/latency\/dvad61-latency-exercise.pptx\">https:\/\/git.cse.kau.se\/courses\/dvad60\/blob\/master\/latency\/dvad61-latency-exercise.pptx<\/a>\u00a0and you can also follow along in the video recording below:<\/p>\n<p><iframe loading=\"lazy\" title=\"Active queue management: latency exercise\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/nZJSieVnWRE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h3>Related readings<\/h3>\n<p>As part of the revival of AQM to address the bufferbloat problem, two new key\u00a0algorithms have beed developed and also standardized by the <a href=\"https:\/\/datatracker.ietf.org\/group\/aqm\/about\/\">IETF AQM working group<\/a>, Codel and PIE. Below you find the papers that introduce these algorithms as well as their standards documents (RFCs). The papers should give you the needed understanding of the principles of the algorithms, you can\u00a0read the detailed performance evaluations\u00a0depending on your preferences. You can also check the standards documents if you like.<\/p>\n<ul>\n<li>K. Nichols and V. Jacobson, &#8220;<a href=\"https:\/\/queue.acm.org\/detail.cfm?id=2209336\">Controlling Queue Delay&#8221;,\u00a0ACM Queue<\/a>, Vol. 10 No. 5, May 2012. <em>(Mandatory for credit bearing course)<\/em><\/li>\n<li>Rong Pan et al. &#8220;<a href=\"https:\/\/ieeexplore.ieee.org\/document\/6602305\">PIE: A lightweight control scheme to address the bufferbloat problem<\/a>&#8220;. 14th IEEE International Conference on High Performance Switching and Routing (HPSR), 2013. (See <a href=\"https:\/\/hhk3.kau.se\/latency\/about-the-course-2\/how-to-find-articles-and-literature\/\">Article access page<\/a> for information on how to access this article.) <em>(Mandatory for credit bearing course)<\/em><\/li>\n<li>K. Nichols, V. Jacobson, A. McGregor, Ed., J. Iyengar, Ed., &#8220;<a href=\"https:\/\/tools.ietf.org\/html\/rfc8289\">Controlled Delay Active Queue Management<\/a>&#8220;. RFC 8289. January 2018.<\/li>\n<li>R. Pan, P. Natarajan, F. Baker, G. White.&#8221;<a href=\"https:\/\/tools.ietf.org\/html\/rfc8033\">Proportional Integral Controller Enhanced (PIE): A Lightweight Control Scheme to Address the Bufferbloat Problem<\/a>&#8220;. RFC 8033. February 2017.<\/li>\n<\/ul>\n<p>While Codel and PIE are relatively recent algorithms, AQM is an old concept. The key initial work in this area is the RED algorithm described\u00a0in a paper by Sally Floyd and Van Jacobson, &#8220;<a href=\"http:\/\/www.icir.org\/floyd\/papers\/early.twocolumn.pdf\">Random early detection gateways for congestion avoidance<\/a>&#8220;, in 1993.<\/p>\n<p>AQM algorithms can help manage queues and reduce bufferbloat, but are\u00a0ineffective\u00a0if you have non-responsive flows. Some form of fairness queueing can be used to alleviate this problem and reduce the effect of bursty traffic. The FQ-Codel algorithm combines Flow queueing and Codel and is described in RFC 8290:<\/p>\n<ul>\n<li>T. H\u00f8iland-J\u00f8rgensen et al., <a href=\"https:\/\/tools.ietf.org\/html\/rfc8290\">The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm<\/a>, RFC 8290, January 2018. <em>(Mandatory for credit bearing course)<\/em><\/li>\n<\/ul>\n<p>For an illustration of how the different AQMs and queueing algorithms behave you can check the evaluations in the paper below:<\/p>\n<ul>\n<li>T. H\u00f8iland-J\u00f8rgensen, P. Hurtig and A. Brunstrom. <a href=\"https:\/\/doi.org\/10.1016\/j.comnet.2015.07.014\">The Good, the Bad and the WiFi: Modern AQMs in a residential setting<\/a>,\u00a0Computer Networks, October 2015.<\/li>\n<\/ul>\n<p>The WiFi experiments in the above paper illustrate the importance of ensuring that the queue management algorithm actually runs in the right place to control the queue. Lower layers of the operating system networking stack can have queues of their own, as can device drivers and hardware. A solution for WiFi was introduced into Linux as described in the paper below:<\/p>\n<ul>\n<li>T. H\u00f8iland-J\u00f8rgensen et al., <a href=\"https:\/\/www.usenix.org\/system\/files\/conference\/atc17\/atc17-hoiland-jorgensen.pdf\">Ending the Anomaly: Achieving Low Latency and Airtime Fairness in WiFi<\/a>, USENIX ATC,\u00a0July 2017.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>We have seen in the previous part of the course that there are many sources of delay. One of the most important is queueing delay as it can be very large in magnitude. In this part we take a closer look at queueing delay and the bufferbloat phenomenon and how active queue management (AQM) and [&hellip;]<\/p>\n","protected":false},"author":120,"featured_media":0,"parent":77,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-83","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/pages\/83","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/users\/120"}],"replies":[{"embeddable":true,"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/comments?post=83"}],"version-history":[{"count":23,"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/pages\/83\/revisions"}],"predecessor-version":[{"id":282,"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/pages\/83\/revisions\/282"}],"up":[{"embeddable":true,"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/pages\/77"}],"wp:attachment":[{"href":"https:\/\/hhk3.kau.se\/latency\/wp-json\/wp\/v2\/media?parent=83"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}