This is a survey of the “Sizing Routing Buffers” academic paper by Appenzeller, Keslassy, and McKeown published in 2004.
In the past, Internet routers had buffers that used a rule-of-thumb using the equation of: B = RTT X C. Where RTT is the round-trip time of a packet and C is the data rate. This rule-of-thumb is no longer useful. The primary goal of the rule-of-thumb, or any for that matter, is to keep a link as close to 100% utilization as possible, as this maximizes the throughput of the network.
Why is it no longer useful?
Large buffers are difficult to manufacture, given that they must use slow, off-chip DRAM for memory buffering. DRAM (dynamic RAM) has some problems. It has an access time of about 50ns, whereas a packet of size 40bytes, can arrive and depart in 8ns: DRAM is slow and slows network speed down. Additionally, they require utilization of a wide DRAM bus, which requires a large number of data pins, which in turn increases the power consumption of the DRAM boards.
Large buffers can contribute to lengthening queueing delays which can in turn cause problems with congestion control algorithms, as they rely on packet loss in order to inform them of TCP congestion.
The original rule-of-thumb came from a 1994 paper and experiments that used a small number of multiplexed flows (up to 8) on a now comparatively low-speed connection of only 40 Mb/s. Today, for example, typical backbone links are now beginning to operate at 100 Gb/s or greater[2] with many thousand multiplexed flows.
Some consider router buffers to be one of the largest contributors to network traffic speed uncertainty.
Why is Overbuffering bad?
- In order to accomodate large buffers, routers have to be designed accordingly, leading to larger power consumption, more board space, and lower density.
- It increases delay when congestion occurs and conflict with low-latency real-time applications like video games. And in some cases, make applications completely unusable.
One of the main issues with the idea that a buffer should be utilized to maximize the network throughput is that it doesn’t take into account TCP Congestion Control algorithms that rely on a packet loss to indicate congestion and to go into action. TCP will always make the buffer overflow in order to lead to packet loss.
Single-flow and Synchronized flows
According to the paper, “the key to sizing the buffer is to make sure that the buffer is large enough, so that while the sender pauses, the buffer doesn’t go empty.” In the case of the single, long-lived flow and synchronized TCP flows, for the buffer to never go empty it needs to be half of the window size max. This is because of how TCP performs. When it TCP sees packet loss, it goes into AIMD congestion control mode and drops it’s packet flow by half. So, while the buffer almost hits zero, it never quite does.
Desynchronized flows
Most internet backbones handle enough simultaneous flows, i.e. greater than 500, that they usually operate under a desynchronized flow pattern. In this environment, the TCP sawtooth isn’t synched, so the more flows that are added, the window size from peak to trough is smoothed out and gets smaller. So, given that as discussed before, that the amount of buffer needed to maintain the network utilization was half of the window max size, then if the window size is now smaller, then therefore the buffer size can be even smaller.
Also, in this case, the flow length distribution is heavily distributed towards long flows, as they typically take up 80% of the bandwidth. However, most of the flows are in fact from short-lived flows (fewer than 100 packets). But, they only account for about 20% of the bandwidth. This is partly due because short flows usually don’t get out of TCP slow-start mode and never fully utilize the network bandwidth, whereas long flows typically get into congestion control mode, maximizing the network bandwidth.
Conclusions
Through this survey, it is apparent that smaller buffer sizes are imperative for best network bandwidth utilization no matter the type of flow or flow environment. Smaller buffers increase bandwidth utilization because they 1) signal to the TCP flow when to go into congestion mode sooner, 2) larger buffers can lead to delay, and 3) are cheaper to manufacture.
[1] Appenzaller, Keslassy, McKeown, 2004. Sizing Routing Buffers
[2] Malik, 2013. 100G, 200G, 400G: Internet’s core is getting fatter to meet our tech planet’s bandwidth demand
