Controlled Delay (CoDel) Active Queue Management

Background

Controlling Queue Delay , K. Nichols and V. Jacobson, ACM Queue, Vol. 10 No. 5, May 2012, queue.acm.org

Van spoke to the original draft at IETF-84 in the Transport Area Open Meeting on July 30, 2012. slides. Listen to recording of the talk at: recording.

There is now an Internet RFC describing CoDel, RFC 8289.

Kathie's BITAG slides

Notes on CoDel algorithm and implementation

CoDel in buffers feeding "bursty" MAC layers

The question of how to adapt CoDel to work with "bursty" MAC layers comes up from time to time. For the most part, nothing needs to be changed and to clarify, we finally wrote a short note about this. Bursty MAC note.

ns-2 simulation code and scripts.

This is a patch to add CoDel to the ns-2 simulator. To apply it, download and untar ns-allinone, cd into ns-allinone-2.35, run patch -p1 < CoDel-ns-2.35.patch then build ns-2 normally (see its README). The install leaves a test driver script in ns-2.35/codel.tcl that you can run to try it out. For example, the simulation data in figure 7 of the Queue paper is the result of: ./ns codel.tcl 4 5 0 100Mb -1 5

The ns-2 codel.cc reflects the code used to produce the results in the ACM Queue paper. We continue to work on CoDel and will post updated versions here when we feel that they're stable. Work-in-progress is generally discussed on the CoDel mailing list.

For real-world implementation guidance, Eric Dumazet's excellent linux kernel implementation of CoDel (net/sched/sch_codel.c and include/net/codel.h) would be better than the ns-2 simulator code. Note that as of this writing (13May12), Eric is using a slightly more recent version of the algorithm than the one give here for ns-2.

The original version of CoDel can let the count_ value grow without bounds under continuous loads. A "fix" for this was proposed by VJ and put into the Linux code by Eric. This works for lower bandwidths and/or low degrees of multiplexing but can also have issues. The best solution is to make the control law somewhat more sophisticated while preserving its implementation efficiency. KMN has been experimenting with some other minor "fixes" in the meantime and these are included in the ns-2 files codel.h and codel.cc. The only recommended change is to move the increment of count_ outside of the repeat dropping loop in deque(). The others are experimental hacks; use at your own risk. Results are welcome.

Ancient history, or the path to CoDel

In the last decade of the last century, we (the CoDel authors) spent a lot of time trying to understand the RED AQM, how to improve it (e.g., not drop packets that arrive to an empty buffer) and how to parameterize its settings. With hindsight, we were using the wrong measure of congestion (an EWMA of queue size), among other things. However, we did learn a lot about how an AQM ought not to behave and that many things will "kind of" work for long-lived TCP flows through a fixed rate bottleneck but all bets are off when you throw short-lived short flows into the mix. Red in a Different Light is a draft of the original work and some updates from a few years later.

Problems inherent in designing an AQM did bug us. Van realized that average queue length was a bad metric and said so in A Rant on Queues. Kathie decided that, from a certain point of view, almost any AQM works on well-behaved long-lived TCPs and almost nothing works on short, bursty traffic and mixes. ( slides)

Fortunately, along came Jim Gettys in 2010 with his insistence that we ought to come up with an AQM that worked in the presence of changing bandwidth and required little or no configuration. CoDel was created as a way to get Jim off our backs. Thanks, Jim.

For interested de-bloaters

The bufferbloat project has set up a CoDel Wiki and a mailing list.

Extensions to CoDel

The ACM paper focused on CoDel in the general Internet and, in particular, at the Internet edge. CoDel can be applied more generally to problems of congestion in networks. For some of these applications, CoDel may need to be adapted and parameterized for that particular niche, rather than using the general Internet version described in the paper.

As noted in "Controlling Queue Delay", queue management needs to be applied at the fast-to-slow transition buffers. The bufferbloat project has been working to address the problem of "dark buffers" both by exposing the problem and by creative "hacks" like BQL that push the large queues back to buffers that can be managed. This is not an adequate solution for multiple parallel buffers; rather CoDel needs to be applied to the hardware buffers themselves. It's perfectly reasonable to apply CoDel to layer 2 or hardware buffers. Similarly, there's no reason CoDel can't be applied to packet switches as well as routers.

Work continues on integrating CoDel with stochastic queuing techniques which creates a much better environment for managing traffic. See the bufferbloat lists mentioned above for the status of this implementation by Eric Dumazaet, called FQ_CoDel. We have implemented an ns-2 version of codel with SFQ that is closely related, called sfqcodel (or smart flow codel as suggested by Jim Gettys). This approach is very exciting as its traffic mixing removes issues associated with "reverse" traffic, improves utilization, prevents large flows from dominating, and, for moderate loads, VoIP-like flows can experience no drops while drops are confined to the data streams. Note, the simulator version is still experimental.

Cable Television Laboratories, Inc. ("CableLabs") has been interested in experiments with CoDel and sfqCoDel and paid for some additional enhancements to the sfqcodel code we originally published. Since these are useful for experimentation, CableLabs has generously allowed us to include them in our files posted here: sfqcodel.h and sfqcodel.cc. Note that there may be some bugs we haven't found yet and please let us know if you do.

To better study AQMs at the consumer edge, CableLabs also requested a specific type of web browser traffic model for ns-2 and is generously permitting us to make it publicly available. This is a directory with files that can be added to ns-2. This is not for the novice ns-2 user. We are hoping that the ns-2 community might improve upon this model.

A particularly interesting application is in Data Centers. Here, several of the assumptions that apply to general Internet traffic no longer hold: the round trip times, the rates, and (lack of) assumptions about the behavior of the packet flows through the bottleneck. In typical Data Centers, the protocol implementation and end-point behavior is completely under the control of the operator. In this situation, CoDel parameters can be adjusted and approaches like ECN might prove useful.

For more information on these and other applications, contact info@pollere.com.

About Us | Services | Resources | Contact | Home

Copyright © 2012-2021, Pollere LLC All Rights Reserved.