Router Buffer Sizing Problem:
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. However, until quite recently it has been widely believed that these routers 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.
During the past four years, several papers have proposed rules for sizing buffers in Internet core routers. Appenzeller et al. suggest that a link needs a buffer of size O(C/sqrt(N)), where C is the capacity of the link, and N is the number of flows sharing the link. If correct, buffers could be reduced by 99% in a typical backbone router today without loss in throughput. Enachecsu et al., and Raina et al. suggest that buffers can be reduced even further to 20-50 packets if we are willing to sacrifice a fraction of link capacities, and if there is a large ratio between the speed of core and access links. If correct, this is a five orders of magnitude reduction in buffer sizes.
Update on Buffer Sizing in Internet Routers, Yashar Ganjali, Nick McKeown , ACM/SIGCOMM Computer Communication Review, October, Volume 36, Number 5, p.67–70, (2006)
Part III: Routers with very small buffers, Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick McKeown, and Tim Roughgarden.ACM/SIGCOMM Computer Communication Review, 35(3):83--90, July 2005.
Obtaining High Throughput in Networks with Tiny Buffers, Neda Beheshti, Yashar Ganjali, Ashish Goel, Nick McKeown, Proceedings of 16th International Workshop on Quality of Service (IWQoS), June, Enschede, Netherlands, (2008)
Packet Scheduling in Optical FIFO Buffers, Neda Beheshti, Yashar Ganjali, Proceedings of IEEE INFOCOM High-Speed Networks Workshop, May, Anchorage, Alaksa, USA, (2007)
The Effects of Fairness in Buffer Sizing, Mei Wang, Yashar Ganjali , Proceedings of IFIP Networking, May, Atlanta, Georgia, USA, (2007)
Buffer Sizing in All-optical Packet Switches, Neda Beheshti, Yashar Ganjali, Ramesh Rajaduray, Daniel Blumenthal, Nick McKeown, Proceedings of OFC/NFOEC, March, Anaheim, CA, (2006)
Routers with Very Small Buffers, Mihaela Enachescu, Yashar Ganjali, Ashish Goel, Nick McKeown, Tim Roughgarden, Proceedings of the IEEE INFOCOM'06, April, Barcelona, Spain, (2006)
Experimental Study of Router Buffer Sizing:
Each buffer sizing proposal mentioned above, is based on theoretical analysis and validated using simulations. Given the potential benefits (and the risk of getting it wrong!) it is worth asking if these results hold in real operational networks. In this project, we report buffer-sizing experiments performed on real networks - either laboratory networks with commercial routers as well as customized switching and monitoring equipment (UW Madison, Sprint ATL, and University of Toronto), or operational backbone networks (Level 3 Communications backbone network, Internet2, and Stanford).
The good news: Subject to the limited scenarios we can create, the buffer sizing results appear to hold. While we are confident that the O(C/sqrt(N)) will hold quite generally for backbone routers, the 20-50 packet rule should be applied with extra caution to ensure that network components satisfy the underlying assumptions.
Experimental study of router buffer sizing, Neda Beheshti, Yashar Ganjali, Monia Ghobadi, Nick McKeown, Geoff Salmon , Internet Measurement Conference (IMC), (2008)
Experimental Study of Router Buffer Sizing, Neda Beheshti, Yashar Ganjali, Monia Ghobadi, Nick McKeown, Geoff Salmon , May, Number TR08-UT-SN, (2008)
Experimenting with buffer sizes in routers, Neda Beheshti, Jad Naus, Yashar Ganjali, Nick McKeown, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems (ANCS), December, Orlando, Florida, USA, (2007)
Performing Time-Sensitive Network Experiments:
Time-sensitive network experiments are difficult. There are major challenges involved in generating high volumes of sufficiently realistic traffic. Additionally, accurately measuring system metrics is not trivial when highly precise timings are required. The majority of these problems arise because generic network software and hardware components do not provide high-precision timing guarantees. In this project, we study the challenges associated with performing time-sensitive network experiments in a testbed, including generating realistic network traffic, emulating delay, approximating large topologies, and collecting high-resolution packet-level measurements. We provide guidelines for setting up testbeds, paying particular attention to factors that may affect the accuracy of experimental results, and we describe obstacles encountered during our own experiments. Many seemingly minor details can have significant influence on an experiment’s results and, therefore, require careful attention. We illustrate how some of these issues can be addressed by software tuning. For others, hardware support is necessary, and we demonstrate how NetFPGA, a programmable and configurable network component, can provide the required precision.
Performing Time-Sensitive Network Experiments, Neda Beheshti, Yashar Ganjali, Monia Ghobadi, Jad Naous, Nick McKeown, Geoff Salmon, ANCS'08, (2008)
Time-Sensitive Network Experiments, Neda Beheshti; Yashar Ganjali; Monia Ghobadi; Jad Naous; Nick McKeown; Geoff Salmon , April, Number TR08-UT-SN, (2008)
Performing Time-Sensitive Network Experiments, Neda Beheshti, Yashar Ganjali, Monia Ghobadi, Nick McKeown, Jad Naous, Geoff Salmon , 09/2008, (2008)