CoDel and Active Queue Management

Buffering packets in a network is both good and bad. It is good because a buffer can hold packets from one stream while another stream’s packets are being processed, to take up and release short bursts of traffic, to hold and then release packets when there is a very short interruption on the wire (or during a route change), and in many other situations. However, queues are bad when there is a standing queue, which means a particular flow always has some number of packets in a particular queue along the path between the source and the destination. This normally occurs at the narrowest point along the path, or rather the link with the lowest bandwidth. In a previous post, I looked at BBR, a change to the way TCP computes its window sizes, that attempts to reduce the amount of traffic “in flight” between a sender and receiver to reduce the number of packets being held in a particular buffer along the way.

This post will consider another solution: CoDel. CoDel is essentially an improved head drop mechanism that provides the correct signals to TCP to slow down its send rate, or rather to reduce the window size (and hence the number of packets in flight on the connection). How does it do this? Consider a buffer, as shown in the following illustration—

Assume the three grey packets—3, 4, and 6—are from a single flow, and the remaining packets are from other flows. A new packet is presented for the queue, the packet marked 1. What should the queue management algorithm do? In a normal tail drop system, the queue manager will drop the packet in the tail of the queue when it arrives, as there is no room on the queue. Here this is packet 1 to the far left of the diagram). So far, so good.

But now we have to ask: what is the difference between a packet that should be queued, because of some transient condition, and a packet that should not have been sent in the first place? If a single application always has packets in the queue, called standing packets, then it should really reduce its window size. Standing packets represent increased delay and jitter across the link, with no corresponding increase in the amount of data being transmitted. To understand this, consider a flow that has a window size of 30 packets. If, during every round trip time between the sender and the receiver, there is always three packets in some queue along the path, then only 27 packets are actually being delivered during the round trip time interval. Those three packets will eventually be delivered, but they will always be replaced by three new packets in the queue—hence the designation standing packets.

These three packets just represent three packets of information that will be delivered more slowly than they should; holding packets in a queue is not increasing the delivery rate, after all. The best solution here is for packets that are being consistently delivered outside the RTT to be dropped, so the sender will know to decrease their window size (keep less packets in flight).

The problem is—how do you detect standing packets exist in the queue? The queue depth, which is the normal quality of service measure, will not tell you this bit of information. What CoDel does is t keep track of how long any particular packet has been in the queue. When a packet is enqueued, it is marked with a timer. When it is dequeued, the timer is checked. If the packet has been in the queue for longer than a preset time (set, by default, to 100ms in the existing CoDel implementations), one packet will be dropped, and the “standing queue” timer is decreased. This causes the sender to slow down, or rather to reduce its send window.

Thus CoDel is a modified head drop queuing mechanism, somewhat similar in intent (but not in function) to wRED (weighted Random Early Detection). The packet that is dropped, in this case, would be packet 7 (to the far right of the queue), if it has been in the queue for too long (has too long of a dwell time).

Does this work? Implementations of CoDel are already available in a number of open source home routing implementations, and hence widely used in smaller home routers to reduce and/or eliminate buffer bloat. The algorithm does seem to work, based on studies and real world use.

You can read more about CoDel, and take a look at pseudocode, in the current IETF draft, which you can find here. Another good source to look at is this article in ACM Queue.