Sundar Iyer
Nick McKeown
Abstract
Internet routers and Ethernet switches contain packet buffers to hold packets during times of congestion. Packet buffers are at the heart of every packet switch and router, which have a combined annual market of tens of billions of dollars, and equipment vendors spend hundreds of millions of dollars on memory each year. Designing packet buffers used to be easy: DRAM was cheap, low power and widely used. But something happened at 10 Gb/s when packets started to arrive and depart faster than the access time of a DRAM. Alternative memories were needed, but SRAM is too expensive and power-hungry. A caching solution is appealing, with a hierarchy of SRAM and DRAM, as used by the computer industry. However, in switches and routers it is not acceptable to have a "miss-rate" as it reduces throughput and breaks pipelines. In this paper we describe how to build caches with 100% hit-rate under all conditions, by exploiting the fact that switches and routers always store data in FIFO queues. We describe a number of different ways to do it, with and without pipelining, with static or dynamic allocation of memory. In each case, we prove a lower bound on how big the cache needs to be, and propose an algorithm that meets, or comes close, to the lower bound. These techniques are practical and have been implemented in fast silicon; as a result, we expect the techniques to fundamentally change the way switches and routers use external memory.
- Cisco GSR 12000 Series Quad OC-12/STM-4 POS/SDH Line Card. Cisco Systems. {Online}. Available: http://www.cisco.com/en/US/ products/hw/routers/ps167/products_data_sheet09186a00800920a7. htmlGoogle Scholar
- Juniper E Series Router. {Online}. Available: http://juniper.net/products/eseries/Google Scholar
- Force 10 E-Series Switch. {Online}. Available: http://www.force10net- works.com/products/pdf/prodoverview.pdfGoogle Scholar
- Cisco Catalyst 6500 Series Router. Cisco Systems. {Online}. Available: http://www.cisco.com/en/US/products/hw/switches/ps708/prod- ucts_data_sheet0900aecd8017376e.htmlGoogle Scholar
- Foundry BigIron RX-Series Ethernet Switches. {Online}. Available: http://www.foundrynet.com/about/newsevents/releases/pr5_03_05b. htmlGoogle Scholar
- QDRSRAM Consortium. {Online}. Available: http://www. qdrsram.comGoogle Scholar
- Micron Technology DRAM. {Online}. Available: http://www.micron. com/products/dramGoogle Scholar
- RLDRAM Consortium. {Online}. Available: http://www.rldram.comGoogle Scholar
- Fujitsu FCRAM. Fujitsu USA. {Online}. Available: http://www.fujitsu. com/us/services/edevices/microelectronics/memory/fcramGoogle Scholar
- CAIDA. {Online}. Available: http://www.caida.org/analysis/workload/ byapplication/oc48/stats.xmlGoogle Scholar
- C. Villiamizar and C. Song, "High performance TCP in ANSNET," ACM Comput. Commun. Rev., 1995. Google Scholar
- Cisco 12000 Series Gigabit Switch Router (GSR) Gigabit Ethernet Line Card. Cisco Systems. {Online}. Available: http://www.cisco.com/ warp/public/cc/pd/rt/12000/prodlit/gspel_ov.htmGoogle Scholar
- M-Series Routers. {Online}. Available: http://www.juniper.net/products/dsheet/100042.htmlGoogle Scholar
- Packet Length Distributions. CAIDA. {Online}. Available: http://www. caida.org/analysis/AIX/plen_histGoogle Scholar
- Round-trip time measurements from CAIDA's macroscopic internet topology monitor. CAIDA. {Online}. Available: http://www.caida.org/ analysis/performance/rtt/walrus2002Google Scholar
- D. A. Patterson and J. L. Hennessy, "Computer architecture," in A Quantitative Approach. San Francisco, CA: Morgan Kaufmann, 1996, sec. 8.4, pp. 425-432. Google Scholar
- K. G. Coffman and A. M. Odlyzko, "Is there a Moore's law for data traffic?," in Handbook of Massive Data Sets. Boston, MA: Kluwer, 2002, pp. 47-93. Google Scholar
- ESDRAM. {Online}. Available: http://www.edram.com/products/legacy/ESDRAMlegacy.htmGoogle Scholar
- RDRAM. Rambus. {Online}. Available: http://www.Rambus.com/ technology/rdram_overview.shtmlGoogle Scholar
- A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queuing algorithm," ACM Comput. Commun. Rev. (SIG-COMM'89) , pp. 3-12, 1989. Google Scholar
- A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks: The single node case," IEEE/ACM Trans. Netw., vol. 1, no. 3, pp. 344-357, Jun. 1993. Google Scholar
- J. Corbal, R. Espasa, and M. Valero, "Command vector memory systems: High performance at low cost," in Proc. 1998 Int. Conf. Parallel Architectures and Compilation Techniques, Oct. 1998, pp. 68-77. Google Scholar
- B. K. Mathew, S. A. McKee, J. B. Carter, and A. Davis, "Design of a parallel vector access unit for SDRAM memory systems," in Proc. 6th Int. Symp. High-Performance Computer Architecture, Jan. 2000.Google Scholar
- S. A. McKee and W. A. Wulf, "Access ordering and memoryconscious cache utilization," in Proc. 1st Int. Symp. High-Performance Computer Architecture, Jan. 1995, pp. 253-262. Google Scholar
- S. Rixner, W. J. Dally, U. J. Kapasi, P. Mattson, and J. D. Owens, "Memory access scheduling," in Proc. 27th Annu. Int. Symp. Computer Architecture, Jun. 2000, pp. 128-138. Google Scholar
- T. Alexander and G. Kedem, "Distributed prefetch-buffer/cache design for high performance memory systems," in Proc. 2nd Int. Symp. High-Performance Computer Architecture, Feb. 1996, pp. 254-263. Google Scholar
- W. Lin, S. Reinhardt, and D. Burger, "Reducing DRAM latencies with an integrated memory hierarchy design," in Proc. 7th Int. Symp. High-Performance Computer Architecture, Jan. 2001. Google Scholar
- S. I. Hong, S. A. McKee, M. H. Salinas, R. H. Klenke, J. H. Aylor, and W. A. Wulf, "Access order and effective bandwidth for streams on a direct Rambus memory," in Proc. 5th Int. Symp. High-Performance Computer Architecture, Jan. 1999, pp. 80-89. Google Scholar
- R. Bhagwan and B. Lin, "Fast and scalable priority queue architecture for high-speed network switches," in Proc. IEEE INFOCOM 2000, Tel-Aviv, Israel, 2000, pp. 538-547.Google Scholar
- P. Chen and D. A. Patterson, "Maximizing performance in a striped disk array," in Proc. ISCAS, 1990, pp. 322-331. Google Scholar
- Y. Joo and N. McKeown, "Doubling memory bandwidth for network buffers," in Proc. IEEE INFOCOM'98, San Francisco, CA, 1998, vol. 2, pp. 808-815.Google Scholar
- D. Patterson and J. Hennessy, Computer Architecture: A Quantitative Approach, 2nd ed. San Francisco, CA: Morgan Kaufmann, 1996. Google Scholar
- L. Carter and W. Wegman, "Universal hash functions," J. Comput. Syst. Sci., vol. 18, pp. 143-154, 1979.Google Scholar
- R. Impagliazzo and D. Zuckerman, "How to recycle random bits," in Proc. 30th Annu. Symp. Foundations of IEEE, 1989.Google Scholar
- B. R. Rau, M. S. Schlansker, and D. W. L. Yen, "The CYDRA 5 strideinsensitive memory system," in Proc. Int. Conf. Parallel Processing, 1989, pp. 242-246.Google Scholar
- S. Iyer, R. R. Kompella, and N. McKeown, "Analysis of a memory architecture for fast packet buffers," in Proc. IEEE HPSR, Dallas, TX, 2001.Google Scholar
- S. Iyer, R. R. Kompella, and N. McKeown, "Techniques for fast packet buffers," in Proc. GBN 2001, Anchorage, AK, Apr. 2001.Google Scholar
- A. Birman, H. R. Gail, S. L. Hantler, and Z. Rosberg, "An optimal service policy for buffer systems," J. Assoc. Comput. Mach., vol. 42, pp. 641-57, May 1995. Google Scholar
- H. Gail, G. Grover, R. Guerin, S. Hantler, Z. Rosberg, and M. Sidi, "Buffer size requirements under longest queue first," in Proc. IFIP'92, 1992, vol. C-5, pp. 413-24. Google Scholar
- G. Sasaki, "Input buffer requirements for round robin polling systems," in Proc. 27th Annu. Conf. Communication, Control and Computing, 1989, pp. 397-406.Google Scholar
- I. Cidon, I. Gopal, G. Grover, and M. Sidi, "Real-time packet switching: A performance analysis," IEEE J. Sel. Areas Commun., vol. SAC-6, pp. 1576-1586, Dec. 1988.Google Scholar
- A. Birman, P. C. Chang, J. Chen, and R. Guerin, "Buffer sizing in an ISDN frame relay switch," IBM Research Rep., RC14286, Aug. 1989.Google Scholar
- A. Bar-Noy, A. Freund, S. Landa, and J. Naor, "Competitive on-line switching policies," Algorithmica, vol. 36, pp. 225-247, 2003.Google Scholar
- R. Fleischer and H. Koga, "Balanced scheduling toward loss-free packet queueing and delay fairness," Algorithmica, vol. 38, pp. 363-376, 2004.Google Scholar
- P. Damaschek and Z. Zhou, "On queuing lengths in on-line switching," Theoretical Computer Science, vol. 339, pp. 333-343, 2005. Google Scholar
- J. García-Vidal, M. March, L. Cerdà, J. Corbal, and M. Valero, "A DRAM/SRAM memory scheme for fast packet buffers," IEEE Trans. Comput., vol. 55, pp. 588-602, May 2006. Google Scholar
- S. Iyer and N. McKeown, "High speed memory control and I/O processor system," U.S. Patent Application 20050240745, Ser. No: 20050240745.Google Scholar
- S. Iyer, N. McKeown, and J. Chou, "High speed packetbuffering system," Patent Application 20060031565, Serial No. 182731.Google Scholar
- S. Kumar, P. Crowley, and J. Turner, "Design of randomized multi-channel packet storage for high performance routers," Proc. Hot Interconnects , Aug. 2005. Google Scholar
- Cisco Systems Catalyst 6500 Switches. Cisco Systems. {Online}. Available: http://www.cisco.com/en/US/products/hw/switches/ps708/ products_data_sheet0900aecd801459a7.htmlGoogle Scholar
- S. Iyer, R. R. Kompella, and N. McKeown, "Designing packet buffers for router line cards," Stanford Univ., Stanford, CA {Online}. Available: http://yuba.stanford.edu/techreports/TR02-HPNG-031001.pdfGoogle Scholar
Index Terms
- Designing packet buffers for router linecards
Recommendations
Sizing router buffers (redux)
The queueing delay faced by a packet is arguably the largest source of uncertainty during its journey. It therefore seems crucial that we understand how big the buffers should be in Internet routers. Our 2004 Sigcomm paper revisited the existing rule of ...
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, ...
Sizing router buffers
SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communicationsAll 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