May 8, 2012

Nichols, Jacobson: Controlling Queue Delay

Kathleen Nichols and Van Jacobson have published a paper describing a new network queue management algorithm that, it is hoped, will play a significant role in the solution to the bufferbloat problem. "CoDel (Controlled Delay Management) has three major innovations that distinguish it from prior AQMs. First, CoDel’s algorithm is not based on queue size, queue-size averages, queue-size thresholds, rate measurements, link utilization, drop rate or queue occupancy time. Starting from Van Jacobson’s 2006 insight, we used the local minimum queue as a more accurate and robust measure of standing queue. Then we observed that it is sufficient to keep a single-state variable of how long the minimum has been above or below the target value for standing queue delay rather than keeping a window of values to compute the minimum. Finally, rather than measuring queue size in bytes or packets, we used the packet-sojourn time through the queue. Use of the actual delay experienced by each packet is independent of link rate, gives superior performance to use of buffer size, and is directly related to the user-visible performance."

For more information, see this blog post from Jim Gettys. "A preliminary Linux implementation of CoDel written by Eric Dumazet and Dave Täht is now being tested on Ethernet over a wide range of speeds up to 10gigE, and is showing very promising results similar to the simulation results in Kathie and Van’s article. CoDel has been run on a CeroWrt home router as well, showing its performance."

Read more at LWN


Click Here!