Internet routers require buffers to hold packets during times of congestion. The buffers need to be fast, and so ideally they should be small enough to use fast memory technologies such as SRAM or all-optical buffering. Unfortunately, a widely used rule-of-thumb says we need a bandwidth-delay product of buffering at each router so as not to lose link utilization. This can be prohibitively large. In a recent paper, Appenzeller et al. challenged this rule-of-thumb and showed that for a backbone network, the buffer size can be divided by sqrt(N) without sacrificing throughput, where N is the number of flows sharing the bottleneck. In this work, we explore how buffers in the backbone can be significantly reduced even more, to as little as a few dozen packets, if we are willing to sacrifice a small amount of link capacity. We argue that if the TCP sources are not overly bursty, then fewer than twenty packet buffers are sufficient for high throughput. Specifically, we argue that O(log W) buffers are sufficient, where W is the window size of each flow. We support our claim with analysis and a variety of simulations. The change we need to make to TCP is minimal---each sender just needs to pace packet injections from its window. Moreover, there is some evidence that such small buffers are sufficient even if we don't modify the TCP sources, so long as the access network is much slower than the backbone, which is true today and likely to remain true in the future. We conclude that buffers can be made small enough for all-optical routers with small integrated optical buffers.

 

History for quick reference
1) Paper introducing small buffers model (RTTxC / sqrt(N))
"Sizing Router Buffers" Guido Appenzeller, Isaac Keslassy and Nick McKeown, ACM SIGCOMM 2004, Portland, August 2004.

2) Paper introducing tiny buffers model (O(log W))
"Part III: Routers with very small buffers" Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick McKeown, and Tim Roughgarden, ACM/SIGCOMM Computer Communication Revew, 35(3):83 90, July 2005.

3) Nice 4 page paper for quick review on buffer sizing models:
"Update on Buffer Sizing in Internet Routers", Yashar Ganjali, Nick McKeown Computer Communications Review (CCR), Volume 36, Number 5, October 2006.

4) Experimental study, verifying small and tiny buffers models:
"Experimental study of router buffer sizing", Neda Beheshti, Yashar Ganjali, Monia Ghobadi, Nick McKeown, and Geoff Salmon. Internet Measurement Conference (IMC), Oct. 2008. (Best Paper Award)

 

More information:
Buffer sizing web page at University of Toronto.
Buffer sizing web page at Stanford.