Stanford

Buffer Sizing in the Internet

Buffer Sizing Video

For an introduction to the buffer sizing problem, our results, and our demo in a real backbone network please see the short video below.

The Buffer Sizing Problem

Until quite recently, Internet routers were widely believed to need large buffers. Commercial routers today have huge packet buffers, often storing millions of packets, under the assumption that large buffers lead to good statistical multiplexing and hence efficient use of expensive long-haul links. A widely-used rule-of-thumb states that, because of the dynamics of TCP's congestion control mechanism, a router needs a bandwidth-delay product of buffering, in order to fully utilize bottleneck links. Here, bandwidth refers to the router's capacity, and delay refers to the average two way propagation delay of packets going through the router.

We have developed an analytical model that suggests that router buffers of core routers could be decreased by about two order of magnitude. This result has been validated by thousands of ns2 simulations as well as experiments done on Stanford's dormitory traffic, University of Wisconsin's WAIL testbed, Internet2, and some commercial operational backbones. This result has significant implications in router design. If big electronic routers require only tens of thousands of packet buffers, it could reduce their complexity, making them easier to build and easier to scale. A typical router linecard today contains about one million packet buffers, using many external DRAM chips. The board space the DRAMs occupy, the pins they require, and the power they dissipate all limit the capacity of the router. By Reducing the buffer size to tens of thousands of pacets, then packet buffers could be incorporated inside the network processor (or ASIC) in a small on-chip SRAM. Not only would external memories be removed, but it would allow the use of fast on-chip SRAM, which scales in speed much faster than DRAM.

Recently, we have shown that the under certain constraints we can reduce the buffer size of Internet routers even more, to just 10-20 packets without any degradation in performance. While this is an interesting intellectual exercise in its own right, there would be practical consequences if it were possible. It could facilitate the building of all-optical routers. With recent advances, it is now possible to perform all-optical switching, opening the door to routers with huge capacity and lower power than electronic routers. Recent advances in technology make possible optical FCFS packet buffers that can hold a few dozen packets in an integrated opto-electronic chip. Larger all-optical buffers remain infeasible, except with unwieldy spools of optical fiber (that can only implement delay lines, not true FCFS packet buffers).

Experiments

To run buffer sizing experiments in a real network, we deployed a number of NetFPGA routers in the backbone of the Internet2 network


NetFPGA is a programmable hardware platform. The NetFPGA board has 4 GigE interfaces and because the entire datapath is implemented in hardware, it can support back-to-back packets at full line rate. The size of the output buffers in NetFPGA can be changed as accurately as one byte at a time. These output buffers are monitored by an event-capturing module on the board, which records all packet arrival, removal, and drop events, and allows a precise measurement of queue occupancy and throughput.

In our experiments, TCP traffic is generated by end hosts at Stanford and Rice University and goes through a bottleneck link between Los Angeles and Houston. We do our measurements on this link. Using a control panel, we can remotely and in real time change the buffer size of the Los Angeles router and set it to any desired value. We can also change the number of TCP flows on the bottleneck link. Flows can be added or removed as desired.

The results of our experiments are matched to what our analysis predicted: that high-speed routers could buffer a few dozens of packets instead of millions of packets and yet result in high throughput if their traffic is not overly bursty.

To learn more about our demo, please see the video at the top of this page.

Papers

  • "Optical packet buffers for backbone Internet routers"
    N. Beheshti, E. Burmeister, Y. Ganjali, J. Bowers, D.Blumenthal, and N. McKeown
    IEEE Transactions on Networking, Vol. 18, No. 5, Oct 2010. (PDF)

  • "Experimental study of router buffer sizing"
    N. Beheshti, Y. Ganjali, M. Ghobadi, N. McKeown, and G. Salmon
    The Internet Measurement Conference (IMC), Vouliagmeni, Greece, October 2008 (PDF)

  • "Towards obtaining high throughput in networks with tiny buffers"
    N. Beheshti, Y. Ganjali, A. Goel, and N. McKewon
    16th International Workshop on Quality of Service (IWQoS), Enschede, The Netherlands, June 2008.(PDF)

  • "Experimenting with buffer sizing in router"
    N. Beheshti, Y. Ganjali, J. Naous and N. McKeown
    ANCS, Orlando, Florida, December 2007. (PDF)

  • "Buffer Sizing in All-Optical Packet Switches"
    Neda Beheshti, Yashar Ganjali, Ramesh Rajaduray, Daniel Blumenthal, and Nick McKeown
    Buffersizing in all-optical packet switches
    Proceedings of OFC/NFOEC, Anaheim, CA, March 2006. (PDF)

  • "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. (PDF)
    Extended version: technical report TR05-HPNG-060606, High Performance Networking Group, Stanford University, June 2005. (PDF)

  • "Sizing Router Buffers"
    Guido Appenzeller, Isaac Keslassy and Nick McKeown
    ACM SIGCOMM 2004, Portland, August 2004. (PDF)

Talks

  • "High Performance Networking with Little or No Buffers"
    CAIDA, San Diego, CA, May 5, 2005. (PPT)

Other Interesting Papers

Adaptive Routing and Congestion Control

Deflection Routing

Congestion Control

Contact

For more information about our buffer sizing results and to learn how you can use our tools to repeat similar experiments, please contact