Controlled Delay (CoDel) Active Queue Management
Controlling Queue Delay,
K. Nichols and V. Jacobson, ACM Queue, Vol. 10 No. 5, May 2012, queue.acm.org
View recording of the talk at:
Notes on CoDel algorithm and implementation:
addenda, clarifications, and information.
CoDel at the IETF
We have slightly updated our draft to describe CoDel:
draft-nichols-tsvwg-codel-01. The draft is still quite
rough. Van spoke to the original draft and various aspects of CoDel at IETF 84 in the
Transport Area Open Meeting on July 30, 2012, slides and talk listed above.
ns-2 simulation code and scripts.
This is a patch to add CoDel to the
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.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.
For interested de-bloaters
The bufferbloat project has set up a wiki
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
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:
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 firstname.lastname@example.org.