Understanding Controlling Queue Delay and CoDel

This is a survey of the “Controlling Queue Delaty” academic paper by Kathleen Nichols and Van Jacobson from ACMQueue in 2012.[1]

Bufferbloat is still a problem!

Packet-based networks use buffers to handle short-term fluctuation in traffic flow. Bufferbloat describes the standing packet queue that’s created when there is a mismatch between the senders maximum send rate (window size) and the bottleneck’s pipe size. This issue of bufferbloat has been known for many decades now.

And given all the streaming today, it’s an important issue as applications today are much more delay-sensitive.

The Standing Queue

This standing queue is the result from this mismatch. Because it creates delays and doesn’t improve throughput, it gets seen as a congestion issue and not properly seen in the light of queue or traffic theory. This is due to theorists seeing TCP’s reliable and highly correlated process, in which the packet arrival rate equals the departure rate, as improbable.

Not an easy problem

And the problem has been difficult to solve. Given that senders set the window size, queues begin to build up at the bottlenecks. This, thereby, makes it difficult for senders to adjust their sending rate given the constantly changing with conditions (flows coming and going, physical conditions, etc.) that occur in the bandwidth of the bottlenecks.

Reliable Detection is Hard

A large queue is necessary to get started as the buffer needs to initially fill, so queue size really doesn’t give us much information about excess queue.

A good queue is occupancy that goes away in about one RTT; bad queue persists for several RTTs [1]

Active Queue Management (AQM)

Active Queue Management is the solution for this bufferbloat problem, but it’s lack of widespread adoption has emanated from implementation difficulties and misunderstanding in the overall issue.

AQM Goals

Paramaterless - no implementation needed
Treats good and bad queue differently
Controls delay
Adapts to dynamically changing link rates
Simple and efficient - from home to enterprise use

CoDel: A proposed solution

CoDel (Contolled Delay Management) is a proposed piece to that solution to this issue of queue management. It makes three main innovations to it’s algorithm:

Using the local minimum queue to measure standing queue and not based on any of the previously used metrics such as the average size, etc.
Keeping a single-state variable measuring how long the minimum have above or below the target for standing queue rather than a window of values to compute the minimum.
Using the packet-sojourn time through the queue as the unit of measure as opposed to bytes or packets.

Why the minimum value?

The minimum packet sojourn can be decreased only when a packet is dequeued, so CoDel can go to work when packets are dequeued for sending and no locks are needed in the software. If the buffer is full on arrival, then a packet is dropped.

The `target` and `interval`

The target represents the “acceptable standing queue delay.” Very importantly, it’s measured in packet-sojourn time, not bytes or packets. Additionally, it’s unacceptable to drop packets if there are fewer than one MTU of bytes in the buffer.
The interval represents “a time on the order of a worst-case RTT of connections through the bottleneck.”

Let’s put it together

So, the crux here is that when the queue delay (it’s packet-sojourn time) is more than the target for at least interval time, then a packet is dropped and it’s not until the queue delay gets itself back below target that it stops dropping packets. In it’s dropping mode, it’s ‘next drop time’ is decreased each time as 1/SqRt(total_number_of_drops) with the intention of getting a linear change in throughput (TCP flow rate).

Conclusion

CoDel looks to be the best way to attack queue delay. While not the silver bullet for queue delay, it satisfies the five goals it set out. Manufacturers still need to build and market devices with proper buffer management.