The controlled delay management (CoDel) aggregate queue length (AQL) algorithm is the brainchild of Kathleen Nichols and Van Jacobson, who have been working on creating a workable active queue management (AQM) solution for modern broadband-rich networks for 14 years, according to Bell Labs programmer Jim Gettys (one of the creators of X Window), who has been vocal on the problem of bufferbloat that now plagues systems.

Gettys has written quite a bit about bufferbloat and has gotten a lot of people worked up about the continued health of the Internet. But if you’ve missed the discussion, here’s a quick review.

Buffer Backups

Operating systems and routers have large, scaling TCP network buffers that, by design, “trap” large numbers of packets to maintain maximum possible throughput (the number of packets that get from point A to point B). Throughput, it has been reasoned, is the best value for a network to have: the fewer lost packets, the better the integrity of the data coming in. And, as files have gotten larger – and larger files more numerous and traffic far more busy – more buffers have been added to hardware and software to handle the flow in a smoother manner (i.e., with less packet loss).

However, in the obsessive quest for reducing packet loss and smoothing out traffic, Gettys argues, another bad situation has been made worse.

Even though a given network has a lot of buffers, the chance is that one (or more) of those buffers will become full. If that full buffer happens to be near a known (or unknown) network bottleneck and that bottleneck gets saturated, suddenly you have packets running smack dab into a queue, waiting for the buffer in question to empty out and deliver said packets to the next hop in the network. Packets are getting lost, so TCP (and UDP) try to work around the problem and deliver the information via another route. However, if that full buffer is on the last network hop or two before its destination (or just outside the source of the packets), the packets can do very little but sit in the buffer queue and wait to be passed on.

Buffers in situations like this actually defeat congestion avoidance protocols because they’re impossible to get around.

It’s important to note that bufferbloat is not just that more buffers exist; it’s that so many buffers are on the network that the odds of one being near a network bottleneck have risen very significantly.

The intuitive solution might be simply to add more bandwidth. After all, adding more traffic lanes seems to help highway congestion. Got a slow network? Add more pipe, that’ll take care of the problem. But Gettys knows this is not the case.

“It’s often counterintuitive,” Gettys told me. “People have to understand concepts that don’t make sense at first. Such as the fact that more is not always better.”

Another counterintuitive notion Gettys emphasizes is that packet loss is actually essential for networks to work more efficiently under load. By obsessively holding on to as little packet loss as possible, networks are actually tripping themselves up.

What makes this problem even more difficult to solve is that buffers will only be noticeable in a network path where they are near a saturated bottleneck. So, you might have a buffer causing problems one day and be perfectly fine (and invisible) the next.

As Gettys himself points out, you have various ways to engineer around the problem – low extra delay background transport (Ledbat) being popular. But such solutions might only work for a short time because, although they benefit the few using them, such congestion-avoidance systems can disrupt “normal” traffic, further damaging the network ecosystem. For Gettys, it’s an application of gaming theory: Why would anyone disadvantage themselves over the long term with these workarounds?

CoDel and AQM

Thus, Gettys is pretty excited about the prospect of AQM, particularly the solution proffered on May 6 by Nichols and Jacobson and outlined in their ACM Queue article. The new CoDel algorithm specifically focuses on AQM issues out on the edge of the network – in the operating systems and connective hardware.

Previously, AQM has existed most commonly as the random early detection (RED) algorithm. But RED was designed in the 1990s, Gettys explained, when bandwidth was very scarce and queue management was focused on the central part of the network, not its edges.

CoDel (pronounced “coddle”) is designed to better apply AQM out on the edges of the network. Although this is not the only place bufferbloat might exist, Gettys emphasized, it is definitely more visible on the edges.

That the solution is already included within the main line kernel production of Linux 3.5 is a testament to the hard work of two men, Gettys said: Dave Täht, who created the initial “quick-and-dirty” CoDel prototype for the Linux kernel, and Eric Duzamet, who massively rewrote Täht’s implementation to include fair queuing tools within the solution.

“Dave worked 12-hour days for about 16 months fixing problems all over the Linux networking stack in preparation for the day we’d have all the pieces to solve bufferbloat,” Gettys told me.

“That’s how miracles like four months from the availability of the algorithm to [inclusion within a] released Linux kernel happen.”

Gettys also praised Tom Herbert’s byte queue limits (BQL) work in Linux 3.3 as a key contribution to the bufferbloat problem.

Thus far, the solution has been positive.

“Eric and others have tested CoDel on 10G Ethernet interfaces; as expected, CoDel performance is good in what’s been tested to date,” Gettys recently wrote on his blog.

Some challenges to using CoDel are still out there, including the massive variability of wireless networks out on the network edges.

“Wireless is much more of a challenge than Ethernet for Linux, particularly 802.11n wireless; the buffering and queuing internal to these devices and drivers is much more complex, and the designers of those software stacks are still understanding the implications of AQM, particularly since the driver boundary has partitioned the buffering in unfortunate ways,” Gettys said.

Linux users who want to give it a try now without waiting for Linux 3.5 can find kernel patches for Linux 3.3 and 3.4 on the Bufferbloat.net site. The CoDel patch code has also been patched for the open source router project, if you are using that platform.

Although Gettys is pleased with the progress thus far, he also emphasized that solutions like BQL and CoDel might only be the tip of the iceberg. Buffers seem to be written into a whole slew of software on the network – even drivers can contain buffer controls. AQM could indeed be the best solution, but deploying AQM tools to so many different pieces of software might take something familiar to long-suffering bufferbloat affectees: time.