Controlled Delay Management
A new aggregate queue length algorithm for network bottlenecks.
ByThe persistent and growing problem of bufferbloat is getting serious relief thanks to a new active queue management tool known as a Controlled Delay – a tool that, thanks to heroic efforts, is now ready for Linux.
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.
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
Halcyon Creates Anti-Ransomware Protection for Linux
As more Linux systems are targeted by ransomware, Halcyon is stepping up its protection.
-
Valve and Arch Linux Announce Collaboration
Valve and Arch have come together for two projects that will have a serious impact on the Linux distribution.
-
Hacker Successfully Runs Linux on a CPU from the Early ‘70s
From the office of "Look what I can do," Dmitry Grinberg was able to get Linux running on a processor that was created in 1971.
-
OSI and LPI Form Strategic Alliance
With a goal of strengthening Linux and open source communities, this new alliance aims to nurture the growth of more highly skilled professionals.
-
Fedora 41 Beta Available with Some Interesting Additions
If you're a Fedora fan, you'll be excited to hear the beta version of the latest release is now available for testing and includes plenty of updates.
-
AlmaLinux Unveils New Hardware Certification Process
The AlmaLinux Hardware Certification Program run by the Certification Special Interest Group (SIG) aims to ensure seamless compatibility between AlmaLinux and a wide range of hardware configurations.
-
Wind River Introduces eLxr Pro Linux Solution
eLxr Pro offers an end-to-end Linux solution backed by expert commercial support.
-
Juno Tab 3 Launches with Ubuntu 24.04
Anyone looking for a full-blown Linux tablet need look no further. Juno has released the Tab 3.
-
New KDE Slimbook Plasma Available for Preorder
Powered by an AMD Ryzen CPU, the latest KDE Slimbook laptop is powerful enough for local AI tasks.
-
Rhino Linux Announces Latest "Quick Update"
If you prefer your Linux distribution to be of the rolling type, Rhino Linux delivers a beautiful and reliable experience.