IPStash: a Power-Efficient Memory Architecture for IP-lookup

ABSTRACT

High-speed routers often use commodity, fully-associative,TCAMs (Ternary Content AddressableMemories) to perform packet classification and routing(IP-lookup). We propose a memory architecture calledIPStash to actasa TCAMreplacement,offering atthesame time, better functionality, higher performance,and significant power savings. The premise of our workis that full associativity is not necessary for IP-lookup.Rather, we show that the required associativity is simplya function of the routing table size. We propose a memoryarchitecture similar to set-associative caches butenhanced with mechanisms to facilitate IP-lookup andin particular longest prefix match. To perform longestprefix match efficiently in a set-associative array werestrict routing table prefixes to a small number oflengths using a controlled prefix expansion technique.Since this inflates the routing tables, we use skewedassociativity to increase the effective capacity of ourdevices. Compared to previous proposals, IPStash doesnot require any complicated routing table transformationsbut more importantly, it makes incrementalupdates to the routing tables effortless. The proposedarchitecture is also easily expandable. Our simulationsshow that IPStash is both fast and power efficient comparedto TCAMs. Specifically, IPStash devices -builtin the same technology as TCAMs- can run at speedsin excess of 600 MHz, offer more than twice the searchthroughput (>200Msps), and consume up to 35% lesspower (for the same throughput) than the best commerciallyavailable TCAMs when tested with real routingtables and IP traffic.

REFERENCES

• 1: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• 2: Anant Agarwal , Stephen D. Pudar, Column-associative caches: a technique for reducing the miss rate of direct-mapped caches, Proceedings of the 20th annual international symposium on Computer architecture, p.179-190, May 16-19, 1993, San Diego, California, United States
• 3: [3] F. Baboescu, S. Singh, G. Varghese, "Packet Classification for Core Routers: Is there an alternative to CAMs?" IEEE INFOCOM, April 2003.
• 4: [4] A. Basu, G. Narlikar, "Fast Incremental Updates for Pipelined Forwarding Engines," IEEE INFOCOM, April 2003.
• 5: [5] E. Besson, and P. Brown, "Performance Evaluation of Hierarchical Caching in High-Speed Routers." Proc. Globecom, pp. 2640-45, 1998.
• 6: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 7: [7] X. Chen, "Effect of Caching on Routing-Table Lookup in Multimedia Environments." IEEE INFOCOM, April 1991.
• 8: [8] G. Cheung and S. McCanne, "Optimal Routing Table Design for IP Address Lookups Under Memory Constraints." IEEE INFOCOM, pp. 1437-44, 1999.
• 9: [9] T. Chiueh and P. Pradhan, "High Performance IP Routing Table Lookup Using CPU Caching." IEEE INFOCOM, April 1999.
• 10: [10] T. Chiueh and P. Pradhan, "Cache Memory Design for Network Processors." Proc. High Performance Computer Architecture , pp. 409-418, 1999.
• 11: Deborah Estrin , Danny J. Mitzel, An assessment of state and lookup overhead in routers, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.2332-2342, May 1992, Florence, Italy
• 12: [12] EZ Chip Network Processors. http://ezchip.com
• 13: [13] A. Gallo, "Meeting Traffic Demands with Next-Generation Internet Infrastructure." Lightwave, 18(5):118-123, May 2001.
• 14: [14] G. Huston, "Analyzing the Internet's BGP Routing Table." The Internet Protocol Journal, 4, 2001.
• 15: [15] IBM PowerNP Network Processors. http:// www.chips.ibm.com/products/wired/network_processors.html
• 16: [16] IDT. http://www.idt.com
• 17: [17] Intel IXP2850 Network Processor. http://www.intel.com/ design/network/products/npfamily/ixp2850.htm
• 18: R. Jain, Characteristics of destination address locality in computer networks: a comparison of caching schemes, Computer Networks and ISDN Systems, v.18 n.4, p.243-254, May 1990 [doi>10.1016/0169-7552(90)90106-3]
• 19: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 20: [20] M. Kobayashi, T. Murase, A. Kuriyama, "A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing." In Proceedings of the International Conference on Communications (ICC 2000), pp. 1360-1364, 2000.
• 21: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.515-528, Oct. 1998 [doi>10.1109/90.731185]
• 22: [22] B. Lampson, V. Srinivasan, G. Varghese, "IP-lookups Using Multiway and Multicolumn Search." Proceedings of IEEE INFOCOM, vol. 3, pages 1248-56, April 1998.
• 23: Huan Liu, Routing Table Compaction in Ternary CAM, IEEE Micro, v.22 n.1, p.58-64, January 2002 [doi>10.1109/40.988690]
• 24: [24] H. Liu, "Routing Prefix Caching in Network Processor Design." IEEE ICCCN2001, October 2001.
• 25: [25] J. van Lunteren and A.P.J. Engbersen. "Multi-Field Packet Classification Using Ternary CAM." Electronics Letters, 38(1):21-23, 2002.
• 26: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
• 27: [27] A.J. McAuley and P. Francis, "Fast Routing Table Lookup Using CAMs." In Proceedings of INFOCOM '93, pages 1382- 1391, San Francisco, CA, March 1993.
• 28: [28] Micron Technology. http://www.micron.com
• 29: [29] Netlogic microsystems. http://www.netlogicmicro.com
• 30: [30] Network and Communications ICs. http://www.agere.com/ enterprise_metro_access/network_processors.html
• 31: [31] S. Nilsson and G. Karlsson, "IP-address lookup using LC-tries." IEEE Journal of Selected Areas in Communications, vol. 17, no. 6, pages 1083-92, June 1999.
• 32: [32] C. Partridge, "Locality and Route Caches." NSF Workshop on Internet Statistics Measurement and Analysis (http:// www.caida.org/ISMA/Positions/partridge.html), 1996.
• 33: [33] Passive Measurement and Analysis project, National Laboratory for Applied Network Research. http://pma.nlanr.net/PMA
• 34: Y. Rekhter , T. Li, An Architecture for IP Address Allocation with CIDR, RFC Editor, 1993
• 35: [35] RIPE Network Coordination Centre. http://www.ripe.net
• 36: André Seznec, A case for two-way skewed-associative caches, Proceedings of the 20th annual international symposium on Computer architecture, p.169-178, May 16-19, 1993, San Diego, California, United States
• 37: Devavrat Shah , Pankaj Gupta, Fast Updating Algorithms for TCAMs, IEEE Micro, v.21 n.1, p.36-47, January 2001 [doi>10.1109/40.903060]
• 38: [38] Sibercore Technology. http://www.sibercore.com
• 39: V. Srinivasan , G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems (TOCS), v.17 n.1, p.1-40, Feb. 1999 [doi>10.1145/296502.296503]
• 40: [40] B. Talbot, T. Sherwood, B. Lin, "IP Caching for Terabit Speed Routers." Global Communications Conference (Globecom'99) , pp. 1565-1569, December, 1999.
• 41: [41] Steven J.E. Wilton and Norman P. Jouppi, "Cacti: An Enhanced Cache Access and Cycle Time Model." IEEE Journal of Solid-State Circuits, May 1996.
• 42: [42] Vitesse IQ2200. http://www.vitesse.com
• 43: [43] F. Zane, G. Narlikar, A. Basu, "CoolCAMs: Power-Efficient TCAMs for Forwarding Engines." IEEE INFOCOM, April 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design
          Subjects: Network communications
      C.2.2 Network Protocols

          Nouns: IP

General Terms:
Design, Performance