Bufferbloats—an amusing word for a less-than-delightful issue (we reported on these last year). A bufferbloat is the proliferation of more and more buffering of IP packets in routers, switches, modems, and other devices that connect both users to the Internet and different parts of the Internet together. Having packets stuck in buffers unnecessarily means communication slows down. Van Jacobson, creator of the TCP congestion control mechanisms, and Kathleen Nichols now propose a general purpose solution to the bufferbloat problem.
In their paper, Nichols and Jacobson point out the difference between a good and bad queue. A good queue consists of a number of buffered packets that come in faster than the device in question can send them on their way. A good queue quickly drains as packets are transmitted. Such queues are necessary to smooth over the inherent bursts of arriving packets at bottlenecks in the network. Such bottlenecks can be between a fast LAN and a slower Internet connection, between a 1Gbps Ethernet link and a 100Mbps one, between a wired and a wireless network, and so on. But without buffering, burst can't be accommodated, which makes it impossible to make use of the full capacity of a given network link.
A bad queue, on the other hand, is filled up at the same rate as packets are transmitted, so the queue never empties. In its steady state, the TCP protocol will release more packets as the reception of earlier packets is acknowledged. At this point, a queue at the bottleneck between the sender and the receiver will become a standing queue—filling up and draining at the same rate to stay the same size.
Suppose the bottleneck is 1Mbps, and the standing queue is ten packets. At 1Mbps, it takes 120 milliseconds to transmit those ten packets. Packets from other communication sessions now have to join the queue and wait for the ten packets that were already there to be transmitted, so now all communication is delayed by 0.12 seconds. For many types of communication, that's not a big deal, but it's not ideal for real-time communication such as VoIP or video conferencing, and can be deadly for many types of online games.
In an earlier rant on queues, Jacobson states that many researchers in the field fail to understand the problem. They assume that packets arrive randomly according to a Poisson distribution. However, TCP, which is used for more than 80 percent of the Internet's traffic, sends its packets anything but randomly. Instead, there is a control loop between the sender and the receiver. Based on this insight, Nichols and Jacobson came up with CoDel, Controlled Delay Management.
Unlike other active queue management (AQM) algorithms, CoDel is not interested in the sizes of the queues. Instead, it measures how long packets are buffered. Specifically, CoDel looks at the minimum time that packets spend in the queue. The maximum time relates to good queues which resolve quickly, but if the minimum is high, this means that all packets are delayed and a bad queue has built up. If the minimum is above a certain threshold—the authors propose 5 milliseconds—for some time, CoDel will drop (discard) packets. This is a signal to TCP to reduce its transmission rate. If the minimum delay experienced by buffered packets is 5ms or less, CoDel does nothing.
In simulation results, CoDel compares favorably to the common RED (random early detect/discard) AQM algorithm in most regards. However, RED requires careful tuning of parameters to work well, while CoDel works within a broad range of bandwidths without the need to change any settings. It also doesn't matter how much buffer space is available—CoDel always kicks in when standing queues exceed five milliseconds. In addition, CoDel has some implementation advantages over other AQMs as it does nearly all of its work at the dequeue stage (when packets are transmitted). CoDel does require adding a timestamp to each individual packet as it is received, but even if the network hardware can't do this, timing information is directly available from a CPU register in modern CPUs. This requirement shouldn't be problematic.
The authors write that the algorithm is now mature enough for experimentation, and not just in open source IP router implementations. "Things would probably go fastest if we had some interested party who wanted to apply it, for example in the cable data edge network," Nichols told Ars. "We've had a 'do no harm' but reduce the standing queue philosophy in our testing. In particular, we were trying to keep the utilization high while reducing the persistent queue delay and not introducing any additional unfairness or problems beyond those that might already occur in a TCP-based network with a variety of flows. That will be what we are looking for in our testing."
Nichols believes that bufferbloat currently impacts the consumer edge the most. "This means the residential access networks, Wi-Fi hot spots, mobile device access networks. Van has seen data on the latter that convinces him that what is called congestion in the cellular network is actually bufferbloat."
The code that implements CoDel is available under a dual BSD/GPL license, so we may see the algorithm adopted in the foreseeable future.
reader comments
23