Designing packet buffers for router linecards

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.

REFERENCES

• 1: 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. html
• 2: Juniper E Series Router. [Online]. Available: http://juniper.net/products/eseries/
• 3: Force 10 E-Series Switch. [Online]. Available: http://www.force10net- works.com/products/pdf/prodoverview.pdf
• 4: Cisco Catalyst 6500 Series Router. Cisco Systems. [Online]. Available: http://www.cisco.com/en/US/products/hw/switches/ps708/prod- ucts_data_sheet0900aecd8017376e.html
• 5: Foundry BigIron RX-Series Ethernet Switches. [Online]. Available: http://www.foundrynet.com/about/newsevents/releases/pr5_03_05b. html
• 6: QDRSRAM Consortium. [Online]. Available: http://www. qdrsram.com
• 7: Micron Technology DRAM. [Online]. Available: http://www.micron. com/products/dram
• 8: RLDRAM Consortium. [Online]. Available: http://www.rldram.com
• 9: Fujitsu FCRAM. Fujitsu USA. [Online]. Available: http://www.fujitsu. com/us/services/edevices/microelectronics/memory/fcram
• 10: CAIDA. [Online]. Available: http://www.caida.org/analysis/workload/ byapplication/oc48/stats.xml
• 11: Curtis Villamizar , Cheng Song, High performance TCP in ANSNET, ACM SIGCOMM Computer Communication Review, v.24 n.5, p.45-60, Oct. 1994 [doi>10.1145/205511.205520]
• 12: 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.htm
• 13: M-Series Routers. [Online]. Available: http://www.juniper.net/products/dsheet/100042.html
• 14: Packet Length Distributions. CAIDA. [Online]. Available: http://www. caida.org/analysis/AIX/plen_hist
• 15: Round-trip time measurements from CAIDA's macroscopic internet topology monitor. CAIDA. [Online]. Available: http://www.caida.org/ analysis/performance/rtt/walrus2002
• 16: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 17: K. G. Coffman , A. M. Odlyzko, Internet growth: is there a "Moore's law" for data traffic?, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 18: ESDRAM. [Online]. Available: http://www.edram.com/products/legacy/ESDRAMlegacy.htm
• 19: RDRAM. Rambus. [Online]. Available: http://www.Rambus.com/ technology/rdram_overview.shtml
• 20: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.1-12, Sep. 1989
• 21: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 22: Jesus Corbal , Roger Espasa , Mateo Valero, Command Vector Memory Systems: High Performance at Low Cost, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.68, October 12-18, 1998
• 23: 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.
• 24: S. A. Mckee , W. A. Wulf, Access ordering and memory-conscious cache utilization, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.253, January 22-25, 1995
• 25: Scott Rixner , William J. Dally , Ujval J. Kapasi , Peter Mattson , John D. Owens, Memory access scheduling, Proceedings of the 27th annual international symposium on Computer architecture, p.128-138, June 2000, Vancouver, British Columbia, Canada
• 26: Thomas Alexander , Gershon Kedem, Distributed Prefetch-buffer/Cache Design for High Performance Memory Systems, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.254, February 03-07, 1996
• 27: Wi-fen Lin, Reducing DRAM Latencies with an Integrated Memory Hierarchy Design, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.301, January 20-24, 2001
• 28: Sung I. Hong , Sally A. McKee , Maximo H. Salinas , Robert H. Klenke , James H. Aylor , Wm. A. Wulf, Access Order and Effective Bandwidth for Streams on a Direct Rambus Memory, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.80, January 09-12, 1999
• 29: 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.
• 30: Peter M. Chen , David A. Patterson, Maximizing performance in a striped disk array, Proceedings of the 17th annual international symposium on Computer Architecture, p.322-331, May 28-31, 1990, Seattle, Washington, United States
• 31: 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.
• 32: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 33: L. Carter and W. Wegman, "Universal hash functions," J. Comput. Syst. Sci., vol. 18, pp. 143-154, 1979.
• 34: R. Impagliazzo and D. Zuckerman, "How to recycle random bits," in Proc. 30th Annu. Symp. Foundations of IEEE, 1989.
• 35: 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.
• 36: S. Iyer, R. R. Kompella, and N. McKeown, "Analysis of a memory architecture for fast packet buffers," in Proc. IEEE HPSR, Dallas, TX, 2001.
• 37: S. Iyer, R. R. Kompella, and N. McKeown, "Techniques for fast packet buffers," in Proc. GBN 2001, Anchorage, AK, Apr. 2001.
• 38: Alexander Birman , H. Richard Gail , Sidney L. Hantler , Zvi Rosberg , Moshe Sidi, An optimal service policy for buffer systems, Journal of the ACM (JACM), v.42 n.3, p.641-657, May 1995 [doi>10.1145/210346.210422]
• 39: H. Richard Gail , George A. Grover , Roch Guérin , Sidney L. Hantler , Zvi Rosberg , Moshe Sidi, Buffer size requirements under longest queue first, Proceedings of the IFIP WG 7.3 International Conference on Performance of Distributed Systems and Integrated Communication Networks, p.413-424, September 10-12, 1991
• 40: G. Sasaki, "Input buffer requirements for round robin polling systems," in Proc. 27th Annu. Conf. Communication, Control and Computing, 1989, pp. 397-406.
• 41: 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.
• 42: A. Birman, P. C. Chang, J. Chen, and R. Guerin, "Buffer sizing in an ISDN frame relay switch," IBM Research Rep., RC14286, Aug. 1989.
• 43: A. Bar-Noy, A. Freund, S. Landa, and J. Naor, "Competitive on-line switching policies," Algorithmica, vol. 36, pp. 225-247, 2003.
• 44: R. Fleischer and H. Koga, "Balanced scheduling toward loss-free packet queueing and delay fairness," Algorithmica, vol. 38, pp. 363-376, 2004.
• 45: Peter Damaschke , Zhen Zhou, On queuing lengths in on-line switching, Theoretical Computer Science, v.339 n.2, p.333-343, 12 June 2005 [doi>10.1016/j.tcs.2005.03.025]
• 46: Jorge Garcia-Vidal , Maribel March , Llorenc Cerda , Jesus Corbal , Mateo Valero, A DRAM/SRAM Memory Scheme for Fast Packet Buffers, IEEE Transactions on Computers, v.55 n.5, p.588-602, May 2006 [doi>10.1109/TC.2006.63]
• 47: S. Iyer and N. McKeown, "High speed memory control and I/O processor system," U.S. Patent Application 20050240745, Ser. No: 20050240745.
• 48: S. Iyer, N. McKeown, and J. Chou, "High speed packetbuffering system," Patent Application 20060031565, Serial No. 182731.
• 49: Sailesh Kumar , Patrick Crowley , Jonathan Turner, Design of Randomized Multichannel Packet Storage for High Performance Routers, Proceedings of the 13th Symposium on High Performance Interconnects, p.100-106, August 17-19, 2005 [doi>10.1109/CONECT.2005.17]
• 50: Cisco Systems Catalyst 6500 Switches. Cisco Systems. [Online]. Available: http://www.cisco.com/en/US/products/hw/switches/ps708/ products_data_sheet0900aecd801459a7.html
• 51: 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.pdf

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
      B.3.2 Design Styles
          Subjects: Cache memories

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

General Terms:
Algorithms, Design, Performance

Keywords:
cache, hit-rate, line-card, memory hierarchy, packet buffer, router, switches