skip to main content
article

Designing packet buffers for router linecards

Published: 01 June 2008 Publication History

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]
C. Villiamizar and C. Song, "High performance TCP in ANSNET," ACM Comput. Commun. Rev., 1995.
[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]
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.
[17]
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.
[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, and S. Shenker, "Analysis and simulation of a fair queuing algorithm," ACM Comput. Commun. Rev. (SIG-COMM'89) , pp. 3-12, 1989.
[21]
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.
[22]
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.
[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 and W. A. Wulf, "Access ordering and memoryconscious cache utilization," in Proc. 1st Int. Symp. High-Performance Computer Architecture, Jan. 1995, pp. 253-262.
[25]
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.
[26]
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.
[27]
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.
[28]
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.
[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]
P. Chen and D. A. Patterson, "Maximizing performance in a striped disk array," in Proc. ISCAS, 1990, pp. 322-331.
[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]
D. Patterson and J. Hennessy, Computer Architecture: A Quantitative Approach, 2nd ed. San Francisco, CA: Morgan Kaufmann, 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]
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.
[39]
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.
[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]
P. Damaschek and Z. Zhou, "On queuing lengths in on-line switching," Theoretical Computer Science, vol. 339, pp. 333-343, 2005.
[46]
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.
[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]
S. Kumar, P. Crowley, and J. Turner, "Design of randomized multi-channel packet storage for high performance routers," Proc. Hot Interconnects , Aug. 2005.
[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

Cited By

View all
  • (2021)Superways: A Datacenter Topology for Incast-heavy workloadsProceedings of the Web Conference 202110.1145/3442381.3449966(317-328)Online publication date: 19-Apr-2021
  • (2019)Efficient Traffic Load-Balancing via Incremental Expansion of Routing ChoicesACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/32431734:1(1-35)Online publication date: 24-Jan-2019
  • (2017)Improving Backpressure-based Adaptive Routing via Incremental Expansion of Routing ChoicesProceedings of the Symposium on Architectures for Networking and Communications Systems10.1109/ANCS.2017.11(1-12)Online publication date: 18-May-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 3
June 2008
249 pages

Publisher

IEEE Press

Publication History

Published: 01 June 2008
Published in TON Volume 16, Issue 3

Author Tags

  1. cache
  2. hit-rate
  3. line-card
  4. memory hierarchy
  5. packet buffer
  6. router
  7. switches

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)1
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Superways: A Datacenter Topology for Incast-heavy workloadsProceedings of the Web Conference 202110.1145/3442381.3449966(317-328)Online publication date: 19-Apr-2021
  • (2019)Efficient Traffic Load-Balancing via Incremental Expansion of Routing ChoicesACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/32431734:1(1-35)Online publication date: 24-Jan-2019
  • (2017)Improving Backpressure-based Adaptive Routing via Incremental Expansion of Routing ChoicesProceedings of the Symposium on Architectures for Networking and Communications Systems10.1109/ANCS.2017.11(1-12)Online publication date: 18-May-2017
  • (2016)Hardware-Software Co-Design for Network Performance MeasurementProceedings of the 15th ACM Workshop on Hot Topics in Networks10.1145/3005745.3005775(190-196)Online publication date: 9-Nov-2016
  • (2016)An ultra-low-latency guaranteed-rate internet for cloud servicesIEEE/ACM Transactions on Networking10.1109/TNET.2014.235849724:1(123-136)Online publication date: 1-Feb-2016
  • (2016)Supporting consumer services in a deterministic industrial internet core networkIEEE Communications Magazine10.1109/MCOM.2016.749809654:6(110-117)Online publication date: 22-Jun-2016
  • (2016)The emerging era of fog computing and networking [The President's Page]IEEE Communications Magazine10.1109/MCOM.2016.749775754:6(4-5)Online publication date: 22-Jun-2016
  • (2015)Improving network routing energy-efficiency for real-time workloads by stochastic service modelInternational Journal of Information and Communication Technology10.1504/IJICT.2015.0684067:2/3(302-315)Online publication date: 1-Apr-2015
  • (2015)Two-Port PCM Architecture for Network ProcessingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2014.236080123:10(2135-2148)Online publication date: 1-Oct-2015
  • (2015)The Bloom paradoxIEEE/ACM Transactions on Networking10.1109/TNET.2014.230606023:3(703-716)Online publication date: 1-Jun-2015
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media