Mihaela Enachescu
Yashar Ganjali
Nick McKeown
Abstract
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 pN without sacrificing throughput, where N is the number of ows sharing the bottleneck. In this paper, 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 ow. 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.
- The network simulator - ns-2. http://www.isi.edu/nsnam/ns/.Google Scholar
- A. Aggarwal, S. Savage, and T. Anderson. Understanding the performance of TCP pacing. In Proceedings of the IEEE INFOCOM, pages 1157--1165, Tel-Aviv, Israel, March 2000.Google ScholarCross Ref
- G. Appenzeller, I. Keslassy, and N. McKeown. Sizing router buffers. In SIGCOMM '04, pages 281--292, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- J. Cao, W. Cleveland, D. Lin, and D. Sun. Internet traffic tends to poisson and independent as the load increases. Technical report, Bell Labs, 2001.Google Scholar
- M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden. Routers with very small buffers. Technical Report TR05-HPNG-060606, Stanford University, High Performance Networking Group, June 2005.Google Scholar
- V. Jacobson. {e2e} re: Latest TCP measurements thoughts. Posting to the end-to-end mailing list, March 7, 1988.Google Scholar
- F. P. Kelly. Chapter 3: Queueing Networks, pages 57--94. Wiley, Chichester, 1979.Google Scholar
- V. Lal, J. A. Summers, M. L. Masanovic, L. A. Coldren, and D. J. Blumenthal. Novel compact inPbased monolithic widely-tunable differential Mach-Zehnder interferometer wavelength converter for 40Gbps operation. In Indium Phosphide and Related Materials, Scotland, 2005.Google Scholar
- M. L. Masanovic, V. Lal, J. S. Barton, E. J. Skogen, J. A. Summers, L. Rau, L. A. Coldren, and D. J. Blumenthal. Widely-tunable monolithically-integrated all-optical wavelength converters in InP. Journal of Lightwave Tehcnology, 23(3), 2005.Google Scholar
- Microsoft. TCP/IP and nbt configuration parameters for windows xp. Microsoft Knowledge Base Article -314053, November 4, 2003.Google Scholar
- J. Padhye, V. Firoiu, D. Towsley, and J. Kurose. Modeling tcp throughput: a simple model and its empirical validation. In SIGCOMM '98, pages 303--314, New York, NY, USA, 1998. ACM Press. Google ScholarDigital Library
- H. Park, E. F. Burmeister, S. Bjorlin, and J. E. Bowers. 40-gb/s optical buffer design and simulations. In Numerical Simulation of Optoelectronic Devices (NUSOD), 2004.Google ScholarCross Ref
- G. Raina and D. Wischik. Buffer sizes for large multiplexers: Tcp queueing theory and instability analysis. http://www.cs.ucl.ac.uk/staff/D.Wischik/Talks/tcptheory.html.Google Scholar
- K. Ramanan and J. Cao. A poisson limit for buffer over ow probabilities. In INFOCOM, 2002.Google Scholar
- C. Villamizar and C. Song. High performance TCP in ANSNET. ACM Computer Communications Review, 24(5):45--60, 1994. Google ScholarDigital Library
Index Terms
- Part III: routers with very small buffers
Recommendations
Update on buffer sizing in internet routers
In the past two years, several papers have proposed rules that suggest two to five orders of magnitude reduction in Internet core router buffers. Others present scenarios where buffer sizes need to be significantly increased. So why the different rules? ...
Part I: buffer sizes for core routers
In this article we describe recent work on buffer sizing for core Internet routers. This work suggests that the widely-used rule of thumb leads to buffers which are much larger than they need to be. For example, the buffer in a backbone router could be ...
Sizing router buffers
All Internet routers contain buffers to hold packets during times of congestion. Today, the size of the buffers is determined by the dynamics of TCP's congestion control algorithm. In particular, the goal is to make sure that when a link is congested, ...
Comments