Nichols, Jacobson: Controlling Queue Delay [LWN.net]

Kathleen Nichols and Van Jacobson have published a paper describing a new network queue management algorithm that, it is hoped, will play a significant role in the solution to the bufferbloat problem. "CoDel (Controlled Delay Management) has three major innovations that distinguish it from prior AQMs. First, CoDel’s algorithm is not based on queue size, queue-size averages, queue-size thresholds, rate measurements, link utilization, drop rate or queue occupancy time. Starting from Van Jacobson’s 2006 insight, we used the local minimum queue as a more accurate and robust measure of standing queue. Then we observed that it is sufficient to keep a single-state variable of how long the minimum has been above or below the target value for standing queue delay rather than keeping a window of values to compute the minimum. Finally, rather than measuring queue size in bytes or packets, we used the packet-sojourn time through the queue. Use of the actual delay experienced by each packet is independent of link rate, gives superior performance to use of buffer size, and is directly related to the user-visible performance."

For more information, see this blog post from Jim Gettys. "A preliminary Linux implementation of CoDel written by Eric Dumazet and Dave Täht is now being tested on Ethernet over a wide range of speeds up to 10gigE, and is showing very promising results similar to the simulation results in Kathie and Van’s article. CoDel has been run on a CeroWrt home router as well, showing its performance."

(Log in to post comments)

Nichols, Jacobson: Controlling Queue Delay

Posted May 9, 2012 21:54 UTC (Wed) by jg (subscriber, #17537) [Link]

You can/should run CoDel on your laptop/desktop/servers as well. it will be quite a while before we have an optimal WiFi implementation, however. The 802.11 stack sucks lots of packets into its internal buffering, often before a line discipline can do its things.

With luck, the current patch will go upstream into the next Linux release; if not, the release after.

Nichols, Jacobson: Controlling Queue Delay

Posted May 10, 2012 0:00 UTC (Thu) by Fowl (subscriber, #65667) [Link]

And how long until it's on by default in all the distributions? Or is this something safe enough to turn on by default in the kernel?

Nichols, Jacobson: Controlling Queue Delay

Posted May 10, 2012 5:45 UTC (Thu) by mtaht (✭ supporter ✭, #11087) [Link]

I would argue that a fq + codel could go on by default someday.

In the interim, please play with the code...

Nichols, Jacobson: Controlling Queue Delay

Posted May 11, 2012 16:25 UTC (Fri) by jg (subscriber, #17537) [Link]

It looks like CoDel will make the upcoming Linux merge window, for Ethernet, anyway. So you'll see it available very soon for testing. (the patch went into net-next yesterday). It will need BQL based drivers.

Eric Dumazet is working on a SFBCODEL (like the SFBRED he did); I don't know if that will make the next merge window. That would probably be what most people would want to use on their laptop.

However, note that the problems are more subtle in general. The 802.11 drivers will need a lot of work to be able to use CoDel. I don't know how long that will take, but my guess is months to have even a preliminary version to play with. So don't expect magic over night.

And remember, your home routers and broadband gear are also bloated; so expect you need to do something there. CeroWrt is attacking this problem head on right now, so if you want a home router, that is the direction to go right now. By bandwidth shaping, you can hide most of the bloated buffers in the broadband hop.

Nichols, Jacobson: Controlling Queue Delay

Posted May 11, 2012 20:26 UTC (Fri) by zlynx (subscriber, #2285) [Link]

I think that the largest problem with broadband and doing your own traffic shaping right now is what you lose when you do it.

For example, my Comcast cable is rated at 20 Mbit, but I often get more. A LOT more. Downloads from CDNs that have local servers can reach 45 Mbit in bursts. I don't have really reliable bandwidth tracking, so that number could be off, but 45 is what I've seen.

If I use standard traffic shaping I'm limiting my speeds to 20 Mbit when I might have the option of twice that speed.

Nichols, Jacobson: Controlling Queue Delay

Posted May 17, 2012 10:55 UTC (Thu) by njs (guest, #40338) [Link]

Unless you have access to your ISP's equipment, you can't really traffic-shape downloads anyway -- just uploads.

Nichols, Jacobson: Controlling Queue Delay

Posted May 17, 2012 12:47 UTC (Thu) by Cyberax (✭ supporter ✭, #52523) [Link]

You can, by dropping ACK packets. Works surprisingly well.

Nichols, Jacobson: Controlling Queue Delay

Posted May 17, 2012 19:06 UTC (Thu) by zlynx (subscriber, #2285) [Link]

I find that it works very well if you put an outgoing queue on the inside LAN port of your router and force it to schedule packets at the desired download rate.

This makes your router the bottleneck. This also lets you do RED with ECN and other things. Doing a traffic police rate drop on the WAN port just isn't as good.

Nichols, Jacobson: Controlling Queue Delay

Posted May 9, 2012 21:57 UTC (Wed) by jg (subscriber, #17537) [Link]

Once you have an effective AQM (e.g. CoDel), the buffer length no longer makes much of a difference, to first order. Second order, it gets more subtle.

You certainly don't want to artificially under buffer; that can have serious performance consequences.

Nichols, Jacobson: Controlling Queue Delay

Posted May 10, 2012 20:21 UTC (Thu) by luto (subscriber, #39314) [Link]

The linked paper is the best explanation I've seen for why largish buffers are needed at all.

One thing I wonder, though: would it make sense for TCP implementations to space out multiple-segment sends if those sends are the result of a congestion window increase or a received ack that does not increase the advertised receive window size?

The idea is that, if the receiver stopped reading for awhile (due to load, for example), then it would ack a segment and decrease its window. When it catches up, the window will increase and the sender should send as much data as will fit.

On the other hand, if the connection is starting up or if the receiver only acks full windows, there's no real benefit to sending the full cwnd all at once, since it's unlikely to reach the receiver any faster than spacing the data out. The latter would improve latency of competing flows.

Nichols, Jacobson: Controlling Queue Delay

Posted May 20, 2012 22:31 UTC (Sun) by farnz (guest, #17727) [Link]

One of the challenges is determining the "correct" spacing; for Ethernet, it's trivial, as to send at a given speed, you just maintain a steady inter-packet spacing. For other link layers, however, it gets more complex.

Assume that your sender is on 10G Ethernet (a nice fast server for a web company, for example). Put the bottleneck link on VDSL2 (often used as the copper end of FTTC connectivity). VDSL2 has a fixed 4 kilobaud signalling rate, so 80MBit/s down (the current fastest in the UK) is provided as 20,000 bits per symbol. A standard ISP MTU in the UK is 1,500 bytes, or 9,000 bits. You therefore need to send a burst of 3 packets to guarantee enough bits buffered to sustain the full 80MBit/s down, then spacing, then another burst.

And note that you can't rely on link speeds to identify what the connection technology in the bottleneck is - if I run a VDSL2 link at 25kbit/symbol, I get 100MBit/s, same as 100BASE-TX; but 100BASE-TX sends at under 1 bit/symbol, so can saturate with a single packet buffered, while VDSL2 at 25kbit/symbol and an Ethernet-compatible 1,500 byte MTU needs 3 packets buffered to saturate.