Kathie Nichols and Van Jacobson today published an article entitled “Controlling Queue Delay” in the ACM Queue. which describes a new adaptive active queue management algorithm (AQM), called CoDel (pronounced “coddle”). This is their third attempt over a 14 year period to solve the adaptive AQM problem and it is finally a successful solution. The article will appear sometime this summer in the Communications of the ACM. Additionally, another independent adaptive AQM algorithm by other authors is also working its way through the academic publication cycle.
A working adaptive AQM algorithm is essential to any full solution to bufferbloat. Existing AQM algorithms are inadequate, particularly in wireless with its very rapid changes in bandwidth.
Everyone working in networking, not just those interested in AQM systems, should read the article, as it dispels common misunderstandings about how TCP interacts with queuing.
CoDel (“coddle”) is a novel “no knobs”, “just works”, “handles variable bandwidth and RTT”, and simple AQM algorithm. To quote from the article,
In the decade since, many researchers have made strides in AQM, but no one has produced an AQM that has the following characteristics:
- It is parameterless—it has no knobs for operators, users, or implementers to adjust.
- It treats good queue and bad queue differently—that is, it keeps the delays low while permitting bursts of traffic.
- It controls delay, while insensitive to round-trip delays, link rates, and traffic loads.
- It adapts to dynamically changing link rates with no negative impact on utilization.
- It is simple and efficient—it can easily span the spectrum low-end, Linux-based access points and home routers up to high-end commercial router silicon.
and:
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.
Without an AQM, a standing queue can be normal result of TCP’s window mechanism, and is not “congestion” as most people have understood it. And since TCP attempts to run a link as fast as it can, any bulk data transfer will cause a modern TCP to open its window continually, and the standing queue grows the longer a connection runs at full bandwidth, continually adding delay unless a AQM is present. Attacking this standing queue is why an AQM is essential in the Internet; and then TCP can be properly responsive to competing traffic.
Network traffic patterns change unexpectedly and rapidly, particularly in the edge of the Internet. Any algorithm requiring manual tuning is unlikely to be configured when and where it may be needed. Common available AQM algorithms (e.g. RED and variants available in today’s routers) can hurt you if misconfigured. The lack of an algorithm that obeys the medical maxim of “First, do no harm” has meant that queue management is often/usually disabled even on Internet routers where it could and should be used (until better algorithms such as CoDel are available). AQM is unavailable on many devices where we now understand it is necessary, including our hosts, laptops, smartphones and other devices. The hope and belief is that CoDel is such a “do no harm” algorithm, that can always be “on” so it can work its magic whenever it is needed.
Mechanisms such as “fair” queuing and traffic classification are also needed for a low latency edge of the Internet, and to try to solve all issues in an AQM algorithm leads to unnecessary complexity and inflexibility, but those other necessary components are well understood and I will blog about them soon.
A small meeting among people interested in ethernet and WiFi implementations was hosted by ISC less than two weeks ago, where we saw the CoDel algorithm for the first time. Ethernet implementations should be straight-forward in most operating systems (if they have a BQL like system to control buffering in device drivers). Wireless and other technologies may be much more difficult, both because queuing is sometimes much more complex than Ethernet, but also since packet aggregation has resulted in OS/driver boundaries hiding information that is necessary for proper functioning. Green ethernet, TSO/GSO are also complicating problems.
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.
Other technologies and environments will be a greater challenge; for example device drivers using Linux’s Mac802.11 framework aggressively pull packets from Linux’s packet queuing system in order to perform packet aggregation, removing the packets from Linux before the current CoDel prototype would get a chance to act on them.
There will be aspects of CoDel needing tweaking for some technologies or environments, along with interactions with queuing and classification systems. Work to integrate adaptive AQM algorithms into wireless systems will take months or years, rather than the week that initial CoDel prototype implementation for Ethernet took. But at least much testing of the CoDel algorithm, experimentation, and refinement can now take place.
Kathie Nichols’ NS2 simulator implementation will become available soon; her CoDel web page is located at: http://www.pollere.net/CoDel.html. Andrew McGregor has written a preliminary NS3 patch.
Discussions about CoDel take place on the codel@lists.bufferbloat.net mailing list. Discussions about bufferbloat in general, and how to attack latency on the edge of the network, takes place on the bloat@lists.bufferbloat.net mailing list. CeroWrt, an advanced build of OpenWrt where our bufferbloat experiments take place, has its development discussions on the cerowrt-devel@lists.bufferbloat.net mailing list. Real time discussions take place on the #bufferbloat channel on IRC on freenode.net.
Both financial and programming/documentation support for both CeroWrt/OpenWrt are needed. We now have the tools in hand to make a home network that works well, at last!
jg's Ramblings 
May 8, 2012 at 10:06 am |
I’d be waiting for a more complete document. Certainly, just having a “pseudo code” that is not clear where it came from, and comparing it only to RED and Drop tail (not precisely the best AQM algorithms out there), doesn’t seem like a complete work.
May 8, 2012 at 10:12 am |
As to where the pseudo code came from, it is derived from the NS2 code that Kathie and Van did the simulations described in the article. Kathie will be posting that NS2 code when she gets a chance to breathe slightly.
See the archives of the codel mailing list for a Linux implementation. https://lists.bufferbloat.net/listinfo/codel
May 8, 2012 at 12:07 pm |
Thanks. Yes, I know where the code is supposedly testing on. I was wondering about the actual algorithm. The amount of papers on AQM makes me believe you can mark packets in many several different ways. I wonder what’s the background on the algorithm, what kind of modeling, was used, would it work in the same way for New Reno, HSTCP, CUBIC and UDP? Optionality, stability.. etc.
As someone that worked on AQM I feel this publication is a bit weak, and they reference only old papers, not a complete journal publication with the methodology and how did they come up with the algorithm.
I’ll keep an eye on more publications, it would be quite interesting understanding the “behind the scenes” from the algorithm.
May 8, 2012 at 12:23 pm
The history of the algorithm goes back to the beginning of AQM’s. The most commonly available AQM has been some version of RED, which was published by Floyd and Jacobson in 1993. The Jacobson on the article is the same Jacobson as who invented RED.
Van Jacobson asked Kathie to look into RED’s problems in 1999, at which point they realized RED was fundamentally flawed; but for reasons covered in my posting “RED in a different light”, this result was never formally published.
They tried again in 2006 to publish a much longer, extensive paper; and it was again rejected, this time with the comments that were roughly “This result can’t possibly be right”, and “The authors should read the fundamental research on AQM, Floyd and Jacobson, 1993”.
Having had the “peer review” process fail not once, but twice, Kathie and Van have had little interest repeating in the academic journal publishing route. What matters is getting the algorithm out there, and running code.
And CACM has word count limits that would make the kind of publication you are asking for impossible, in any case. Feel free to do additional simulations and comparisons, to your hearts content.
May 10, 2012 at 8:33 pm
Better explanations of how the algorithm actually works are being discussed on the codel email list. A start at one is here:
https://lists.bufferbloat.net/pipermail/codel/2012-May/000172.html
May 8, 2012 at 11:07 am |
I wonder – you mention another algorithm also making its way through the publication cycle, any more pointers…?
An interesting question that already arises is how each of these algorithms behaves when some parts of the network are misbehaving (like today), or use the competing algorithm…
May 8, 2012 at 11:12 am |
I was asked to review a journal paper a month or two ago; I liked most of what I saw, and sent back comments. There were some things I didn’t understand about how it worked, as it used a technique I don’t have experience in. But it’s inappropriate for me to say more.
Ultimately, it’s how well real implementations work that will matter. The fundamental issue is before these papers, we had no viable AQM as far as I could see, so “Controlling Queue Delay” gets us unstuck.
May 8, 2012 at 1:42 pm |
[…] by Kathleen Nichols and Van Jacobson. If you read the paper please also look at today’s blog post from bufferbloat pioneer Jim Gettys explaining what it’s all […]
May 8, 2012 at 3:17 pm |
Where does CoDel need to be implemented to be effective? Only in the endpoints, only in intermediate points like routers, or both? Does it matter how much of the round-trip path is using CoDel as opposed to other queue management techniques?
Upgrading endpoints can be relatively easy (run a software update in Linux/Mozilla/etc.), and updating some routers and firewalls can be easy if the vendor updates their code, but others are hard to fix (like home DSL routers and cable modems.)
May 8, 2012 at 3:25 pm |
That’s a really good question.
In short, any queue that could ever be a bottleneck needs management. So ultimately it needs to be in our operating systems (even on ethernet!), our home routers, our broadband gear, and everywhere else, including internet routers (where CoDel would be able to replace the existing *RED or other AQM algorithms).
We know we’ve got really bad problems in our OS’s, our home routers, broadband gear and 3g. Beyond that, the data gets spottier and less definitive, though convincing there are still lots of problems. In short, we’re draining an Internet wide swamp.
May 13, 2012 at 9:05 am |
I guess the flip side is that CoDel can be implemented anywhere to be effective; the more places it is implemented the more effective it is. My understanding is that we can see some benefit without upgrading the entire internet.
May 8, 2012 at 4:32 pm |
Great stuff, Jim, thanks for covering this!
ps. You forgot to put a PayPal donation link there around financial support 🙂
May 8, 2012 at 10:43 pm |
I almost put up a paypal link this week. Still may. I’m rather tired of living on top ramen.
May 9, 2012 at 2:04 pm |
At the expanse of being slightly off-topic, I found the diagrams in the article a bit unclear. Since I’ve been following the discussion, that was a mere nuisance. For others, it could be less good. –dave
May 9, 2012 at 5:19 pm |
Unless you can explain what was unclear about them, it’s hard for Kathie and Van to clarify the diagrams. Remember, the CACM version is later this summer; it’s still possible for them to do such clarifications.
May 10, 2012 at 1:31 pm |
I’ll have to think about how to express what I don’t see… (not as hard as proving a negative, but sorta brain-warping (:-))