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 √ N without sacrificing throughput, where N is the number of flows 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 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. Until quite recently, Internet routers were widely believed to need large buffers. Commercial routers today An earlier, shorter, incomplete, invited and unreviewed version of this paper appeared in ACM CCR, July 2005. The editor encouraged us to submit to Infocom so that a complete, reviewed version would be available to the community. This work was supported under DARPA/MTO DOD-N award no. W911NF-04-0001/KK4118 (LASOR PROJECT) and the Buffer Sizing Grant no. W911NF-05-1-0224. Ashish Goel's work was also supported by an NSF career grant and an Alfred P. Sloan faculty fellowship, and the Tim Roughgarden's work was also supported in part by ONR grant N00014-04-1-0725. 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, B = RTT × C, in order to fully utilize bottleneck links [5] , [6] , [16] . Here, C is the capacity of the bottleneck link, B is the size of the buffer in the bottleneck router, and RTT is the effective round-trip propagation delay of a TCP flow through the bottleneck link. Recently, Appenzeller et al. proposed using the rule B = RTT × C/ √ N instead, where N is the number of flows through the bottleneck link [3] . In a backbone network today, N is often in the thousands or the tens of thousands, and so the sizing rule B = RTT × C/ √ N results in significantly fewer buffers. In this paper, we explore if and how we could build a network with much smaller buffers still-perhaps with only a few dozen packet buffers in each router, and perhaps at the expense of 100% link utilization. While this is an interesting intellectual exercise in its own right, there would be practical consequences if it were possible. First, it could facilitate the building of all-optical routers. With recent advances [8] , [9], [13], 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 [13] . Larger all-optical buffers remain infeasible, except with unwieldy spools of optical fiber (that can only implement delay lines, not true FCFS packet buffers). We are interested in exploring the feasibility of an operational all-optical network with just a few dozen optical packet buffers in each router. Second, if big electronic routers required only a few dozen packet buffers, it could reduce their complexity, making them easier to build and easier to scale. A typical This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the Proceedings IEEE Infocom.
Enachescu et al. REF showed that a 80% workload consisting of long-lived TCP sessions only achieves a 20% link utilization when the buffer size of the shared link is 10 packets.
Routers with Very Small Buffers
Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications
Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications
Computer Science