CoDel: Improved networking through adaptively managed router queues

Unfortunately nothing guarantees that buffers are only used to cushion transients. In particular, TCP congestion control [RFC 5681] increases the amount of data in-flight by one packet every round-trip time with the goal of keeping link utilization high but once the path from source to destination is full, excess packets queue at the upstream end of the slowest link in the path. Since today’s router interfaces can buffer hundreds to thousands of packets, long-lived connections can create many seconds of unnecessary delay.

This tendency of transport connections to fill router buffers for no good reason was recognized early in the life of the Internet and a variety of router Active Queue Management (AQM) algorithms were proposed to combat it [RFC 2309, REDL1998]. AQM support was provided by major router vendors but the available algorithms required manual configuration of a number of adjustable parameters whose values were difficult to determine and changed unpredictably as load varied. Excessive drops could occur. As a result, ISPs were unable to successfully deploy AQM. By 2010, the persistently full buffer problem remained, worsened by inexpensive memory. Delays and packet drops were making interactive use of the Internet untenable. Jim Gettys re-christened the problem as "bufferbloat", documented its cause and impact, and mobilized a small community to work on fixing it.

The authors of RFC 8289 were part of this effort. CoDel (Controlled Delay) was developed in 2011-12 as a new approach to solve bufferbloat. AQMs of 2010 were difficult to configure for stable link rates and impossible for changing link rates (e.g. wireless). They reacted too slowly both to congestion and to the return to a non-congested state, i.e., reacting too late and dropping when congestion was gone. CoDel’s goals were a configuration-free AQM that correctly recognized bad queue across a range of dynamic network conditions, avoided negative impact on utilization, and had a simple and efficient implementation.

CoDel assumes transient queuing is acceptable, a small amount of standing queue is acceptable, and that it is unacceptable to drop when there are fewer than an MTU worth of bytes in the buffer. CoDel determines standing queue by tracking the minimum packet delay through a buffer over a sliding time window, where the window is on the order of a round trip time (delay measured at each packet's departure as its time spent in the buffer). If the minimum packet delay exceeds the small target standing queue for longer than a time interval on the order of a round trip time, a packet is dropped and a control law used to set the next drop time. As soon as a packet delay at or below target is seen, drops are canceled. This ensures that delay must have persisted for a network-significant amount of time.

Using packet time spent enqueued as the input to the local congestion controller results in an AQM that works at any link bandwidth, including one that is time varying. Target and interval are constants: acceptable queue delay (to prevent starvation) and a time on the order of a worst case RTT of connections through the bottleneck. Tracking the recently experienced standing queue means CoDel reacts to congestion and its removal in a timely fashion and does not make drops that "starve" the buffer.

CoDel achieved its goals and became the first modern AQM, capable of adapting changing link bandwidth and only dropping in the presence of “bad” queue. CoDel pseudocode was released in the Spring of 2012 and turned into running Linux code by Eric Dumazet and Dave Taht. It has been part of the Linux kernel since the 3.5 mainline in May of 2012. CoDel, with and without modifications, has been used in home router products, in datacenter servers at Google, and in graduate student projects at Stanford to validate its performance claims.

Managing the queue is only part of the solution to good local delay management. Separating short packet streams (e.g. ACKs)  from large packet data streams is the other step. RFC 8290 covers fq-codel which addresses these issues.