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.
Course lecture: A closer look at bufferbloat
If you did not read the paper on bufferbloat 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, Bufferbloat: Dark Buffers in the Internet, ACM Queue, nov. 2011, vol . 9, no. 11.
Course lecture: Active queue management
Practical Exercise
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.
The experiment environment consists of the network emulator ’mininet’, 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.
VirtualBox to run the virtual machine is available (without cost) at https://www.virtualbox.org/
The virtual machine is available at https://kau.box.com/v/latency-vm
The experiment code is available at https://git.cse.kau.se/courses/dvad60/blob/master/latency
The instructions to perform the exercise is documented in https://git.cse.kau.se/courses/dvad60/blob/master/latency/README.txt
There is a presentation slideset at https://git.cse.kau.se/courses/dvad60/blob/master/latency/dvad61-latency-exercise.pptx and you can also follow along in the video recording below:
Related readings
As part of the revival of AQM to address the bufferbloat problem, two new key algorithms have beed developed and also standardized by the IETF AQM working group, 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 read the detailed performance evaluations depending on your preferences. You can also check the standards documents if you like.
- K. Nichols and V. Jacobson, “Controlling Queue Delay”, ACM Queue, Vol. 10 No. 5, May 2012. (Mandatory for credit bearing course)
- Rong Pan et al. “PIE: A lightweight control scheme to address the bufferbloat problem“. 14th IEEE International Conference on High Performance Switching and Routing (HPSR), 2013. (See Article access page for information on how to access this article.) (Mandatory for credit bearing course)
- K. Nichols, V. Jacobson, A. McGregor, Ed., J. Iyengar, Ed., “Controlled Delay Active Queue Management“. RFC 8289. January 2018.
- R. Pan, P. Natarajan, F. Baker, G. White.”Proportional Integral Controller Enhanced (PIE): A Lightweight Control Scheme to Address the Bufferbloat Problem“. RFC 8033. February 2017.
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 in a paper by Sally Floyd and Van Jacobson, “Random early detection gateways for congestion avoidance“, in 1993.
AQM algorithms can help manage queues and reduce bufferbloat, but are ineffective if 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:
For an illustration of how the different AQMs and queueing algorithms behave you can check the evaluations in the paper below:
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: