The criminal mastermind: bufferbloat!

Each of these initial experiments were been designed to clearly demonstrate a now very common problem: excessive buffering in a network path. I call this “bufferbloat“. We all suffer from it end-to-end, and not just in our applications, operating systems and home network, as you will see.

Large network buffers can be thought of as “dark buffers”, analogous to “dark matter” in the universe; they are undetectable under many/most circumstances, and you can detect them only by indirect means.  Buffers do not cause problems when they are empty.  But when they fill they introduce additional latency (and create other problems, possibly very severe) to other traffic sharing the link.

In the past, memory was expensive, and bandwidth on a link fixed; in most parts of the path your bytes take through the network, necessary buffering was easy to predict and there were strong cost incentives to minimize extra buffering. Times have changed, memory  is really cheap, but our engineering intuition is to avoid dropping data.  This intuition turns out to be wrong, and has become counter-productive.

The network is often completely congested

All modern operating systems on modern hardware (this leaves out Windows XP, which does not implement TCP window scaling and on continental U.S .delays won’t go much faster than 6Mbps, or have more than 64KB in flight at once) can trivially saturate any network up to a gigabit per second with even a *single* TCP connection.  This means that bulk data transfer, in either direction on broadband links (and other internet links) will routinely saturate one hop in a path, the minimum bandwidth path from sender to receiver.  In your home, this is most likely your broadband Internet connection, though as Experiment 2 showed, it can easily be the wireless link in your home router.  Other protocols can also saturate a link: e.g. bittorrent, UDP based protocols, etc.

As I demonstrated, it’s really easy to saturate a 100Mbps link (on Linux or Mac OSX) in your home or office (still probably the most common ethernet switch), and even more easily, any wireless link, with bad consequences.

Congestion avoiding protocols (e.g. TCP, which is our commonly accepted touch-stone of congestion avoiding protocols, by which others are judged) rely on a low level of timely packet drop to detect congestion (or, in modern TCP stacks, packets marked by ECN bits; for various reasons, ECN is not typically used today). They regulate their sending by noticing when packets have dropped to not overfill the chokepoint on their network path. Timely congestion notification via packet drop is a fundamental design presumption of the Internet communications protocols.

Buffering is necessary

Some buffering is clearly necessary in a network: it means that short bursts of packets can be absorbed without significant loss. It is important there is space available to put packets waiting for transmission.  We certainly don’t want a lot of packet loss anytime two packets happen to arrive at once, or happen to be generated nearly simultaneously on a host.  And for reasons that will become clear, some applications (e.g. web browsers) are causing packet bursts.

Too much buffering is bad

Packets reach a choke point on the path, and are queued; a queue cannot drain until packets have been transmitted.  If more packets come in than can be transmitted, the queue gets longer.  Clearly, we don’t want the queue length to go to infinity; sooner or later we better drop some data. (Note that even with traffic classification, you still have queuing going on; just in more than one queue). There are three choices: you can drop from the tail of the queue, the head of the queue, or pick a random packet.

Two queues will grow: one on either side of the slowest hop in the network path, depending on which direction packets are flowing.  The more packets queued, the higher the latency in the queue.  The bottleneck, of course, may be a different hop in the path in one direction than the other.

In the experiments, you are seeing (excessive) queuing in operating systems, and in home routers.  You see various behavior going on as TCP tries to find out how much bandwidth is available, and (maybe) different kinds of packet drop (e.g. head drop, or tail drop; you can choose which end of the queue to drop from when it fills). Note that any packet drop, whether due to congestion or random packet loss (e.g. to wireless interference) is interpreted as possible congestion, and TCP will then back off how fast to will transmit data.

This begs a fundamental question in a packet switched network: how much buffering is enough? Well, this is a complex question: the optimum shown by Kleinrock is the bandwidth * the delay * sqrt(Nflows). The “bandwidth delay product” is needed in order to keep enough data in flight to go as fast as it can over the transmission path; but we also need to have some space to deal with other traffic that might arrive (the number of flows). There is recent research that shows that in fact Kleinrock’s optimum is more likely an upper bound; many real routers may be able to work better with fewer packets queued.

We clearly need some buffering, but not too much.  Cheap memory means we can have GOBS of buffering.  In fact, many Linux network drivers are telling Linux to buffer 1000 packets in transmission!  at 1500 bytes/packet, this is 1.5 megabytes! (X11 was developed on VAXes with 2MB of RAM total). This is 12 megabits.  At 10 megabits/second, it’s going to take more than a second for any such queue to drain.  At 1Mbps, well over 10 seconds.

These network devices cover 2 orders of  magnitude of performance (both ethernet and wireless), but the buffering number was probably picked (if thought about consciously at all) to enable high bandwidth over planetary scale at highest bandwidth for a server with many simultaneous flows, but without thought about latency when the same hardware is running very slowly, on low delay paths, with just a few flows

What is more, I’ve demonstrated in these experiments two cases of bufferbloat in Linux: it’s transmit queue (the txqueuelen knob we twisted), and the transmit rings in the NIC’s (sometimes adjustable as well). Other hardware/software combinations has additional hidden buffer locations.

There is no (single) right answer

I hope the previous paragraph’s discussion makes it clear there is no single right answer possible for buffering.  It is a function of bandwidth (which on both ethernet and wireless can easily vary by several orders of magnitude; further complicating wireless is the difference between “goodput” and “bandwidth”), your workload (the number of flows), and your tolerance for latency.

Next installment

Having demonstrated bufferbloat in simple experiments everyone can perform, we’ll move on to what these bloated buffers are doing to TCP in more detail and why it ends up filling the buffers at the choke point, as best I can explain (I’m not a full fledged TCP expert). I’ll include TCP traces illustrating the problem (over home broadband links). Other protocols are equally capable of causing the buffers to fill; this is not unique to TCP.