CoDel

In network routing, CoDel (pronounced "coddle") for controlled delay is an active queue management algorithm developed by Van Jacobson and Kathleen Nichols. It is designed to overcome bufferbloat in network links (such as routers) by setting limits on the delay network packets suffer due to passing through the buffer being managed by CoDel.

CoDel aims at improving on the overall performance of the RED algorithm by addressing some fundamental misconceptions in the algorithm (as perceived by Jacobson) and by being easier to manage (since, unlike RED, CoDel does not require manual configuration).

Theoretical underpinnings

The theory behind CoDel is based on a number of observations of packet behavior in packet-switched networks under the influence of data buffers. Some of these observations are about the fundamental nature of queueing and the causes of bufferbloat, others relate to weaknesses of alternative queue management algorithms.

Bufferbloat

CoDel was developed as an attempt to address the problem of bufferbloat. Bufferbloat is a problem that occurs in buffers in network links between networks that are not properly matched with respect to speed of handling packets.

In a network link between a fast and a slow network packets can get backed up, especially at the start of a TCP session, when there is a sudden burst of packets and the link to the slower network may not be able to process the sudden communication burst quickly enough. Buffers exist to ease this problem by giving the fast network a place to push packets, to be read by the slower network as fast as it can. However, a buffer has a finite size: it can hold a maximum number of packets, called the window size. The ideal buffer has a window size such that it can handle a sudden burst of communication and match the speed of that burst to the speed of the slower network. This situation is characterized by a temporary delay for packets in the buffer during the communications burst, after which the delay rapidly disappears and the networks reach a balance in offering and handling packets.

Network links have an inherent balance which is determined by the packet transmission and acknowledgement cycle. When a packet is sent, TCP usually acknowledges it before it will accept the next packet. This means that a network must transmit a packet and then transport the acknowledgement back before the next packet is pushed into the link. The time it takes to transport a packet and transport back the acknowledgement is called the round-trip time (RTT). If a buffer is large enough to handle a burst, the result will be smooth communication with (eventually) a low delay for packets in the buffer. But if the buffer is too small, then the buffer will fill up and will itself not be able to accept more packets than one per RTT cycle. So the buffer will stabilize the rate at which packets enter the network link, but it will do so with a fixed delay for packets in the buffer. This is called bufferbloat: instead of smoothing the communication, the buffer causes communication delays and lowers utilization of the network link (i.e. causes the network link to carry less than its capacity of packets).

Good queue versus bad queue

CoDel distinguishes between two "types" of queue (or rather, the effect that the queue is having):

Good queue

this is defined as a queue that exhibits no buffer bloat, i.e. catches and handles communications bursts with no more than a temporary increase in queue delay and which maximizes utilization of the network link.

Bad queue

this is defined as a queue that exhibits buffer bloat, i.e. where a communications burst has caused the buffer to fill up and stay filled, resulting in low utilization and a constantly high buffer delay.

In order to be effective against bufferbloat, an AQM algorithm must be able to recognize an occurrence of bufferbloat and must then deploy effective countermeasures.

Regarding the recognition of an unwanted situation, Van Jacobson asserted in 2006 that existing algorithms have been using incorrect means of recognizing bufferbloat. In an attempt to recognize the telltale standing queue of bufferbloat, algorithms like RED measure the average queue length (in packets or stored bytes) and consider it a case of bufferbloat if the average grows too large. However, Jacobson demonstrated in 2006 that this measurement is not a good metric: the average queue length rises sharply in case of a communications burst. But this can then dissipate quickly (good queue) or develop a standing queue (bad queue). Also, other factors in network traffic can cause false positives or negatives, causing countermeasures to be deployed unnecessarily — Jacobson suggested therefore that average queue length actually contains no information at all about packet demand or network load. He then suggested that a better metric might be the minimum amount of delay experienced by any packet in the sliding window of the buffer.

The CoDel algorithm

Based on Jacobson's notion from 2006, CoDel was developed to manage queues under control of the minimum delay experienced by packets in the running buffer window. The goal is to keep this minimum delay below 5 milliseconds. If the minimum delay rises to too high a value, packets are dropped from the window until the delay drops below the maximum level.

Nichols and Jacobson cite several advantages to using nothing more than this metric:

• CoDel is parameterless. One of the weaknesses in the RED algorithm (according to Jacobson) is that it is too difficult to configure (and too difficult to configure correctly, especially in an environment with dynamic link rates). CoDel has no parameters to set at all.
• CoDel treats good queue and bad queue differently. Good queue has low delays by nature, so the management algorithm can ignore it. Bad queue is susceptible to management intervention in the form of dropping packets.
• CoDel works off of a parameter that is determined completely locally, so it is independent of round-trip delays, link rates, traffic loads and other factors that simply cannot be controlled or predicted by the local buffer.
• The local minimum delay can only be determined when a packet leaves the buffer. So no extra delay is needed to run the queue to collect statistics to manage the queue.
• CoDel adapts to dynamically changing link rates with no negative impact on utilization.
• CoDel can be implemented relatively simply and therefore can span the spectrum from low-end home routers to high-end routing solutions.

CoDel does nothing to manage the buffer if the minimum delay for the buffer window is below the maximum allowed value. It also does nothing if the buffer is relatively empty (if there are fewer than one MTU's worth of bytes in the buffer). If these conditions do not hold, then CoDel drops packets probabilistically.

Description

The algorithm is independently computed at each hop. The algorithm operates over an interval. The initial interval is 100 milliseconds. Per-packet queuing delay is monitored through the hop. As each packet is dequeued for forwarding, the queuing delay (amount of time the packet spent waiting in the queue) is calculated. The lowest queuing delay for the interval is stored. When the last packet of the interval is dequeued, if the lowest queuing delay for the interval is greater than 5 milliseconds, this single packet is dropped and the interval used for the next group of packets is shortened. If the lowest queuing delay for the interval is less than 5 milliseconds, the packet is forwarded and interval is reset to 100 milliseconds.

When the interval is shortened, it is done so in accordance with the inverse square root of the number of successive intervals in which packets were dropped due to excessive queuing delay. The sequence of intervals is $100$, ${100 \over {\sqrt {2}}}$, ${100 \over {\sqrt {3}}}$, ${100 \over {\sqrt {4}}}$, ${100 \over {\sqrt {5}}}$ ...

Simulation results

CoDel has been tested in simulation tests by Nichols and Jacobson, at different MTUs and link rates and other variations of conditions. In general, results indicate:

• In comparison to RED, CoDel keeps the packet delay closer to the target value across the full range of bandwidths (from 3 to 100 Mbit/s). This seems to result in good queue, since the measured link utilizations are consistently near 100% of link bandwidth.
• At lower MTU, packet delays are lower than at higher MTU. Higher MTU results in good link utilization, lower MTU results in good link utilizations at lower bandwidth, degrading to fair utilization at high bandwidth.

Simulation was also performed by Greg White and Joey Padden at CableLabs.

CoDel in use

A full implementation of CoDel was realized in May 2012 and is available as open-source software to all interested parties. This implementation will be used by different parties to study CoDel in actual use.

As of 21 May 2012, CoDel has been implemented within the Linux kernel (starting with the 3.5 mainline).

CoDel began to appear as an option in some proprietary/turnkey bandwidth management platforms in 2013.