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.
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 firstname.lastname@example.org mailing list. Discussions about bufferbloat in general, and how to attack latency on the edge of the network, takes place on the email@example.com mailing list. CeroWrt, an advanced build of OpenWrt where our bufferbloat experiments take place, has its development discussions on the firstname.lastname@example.org 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!