A TCAM-Based Parallel Architecture for High-Speed Packet Forwarding
|
A partitioned TCAM-based search engine is presented that increases the packet forwarding rate multiple times over traditional TCAMs. The model works for IPv4 and IPv6 packet forwarding. Unlike the previous art, the improvement is achieved regardless of the incoming traffic pattern. Employing small and private memories that dynamically store popular route prefixes inside the ASIC and taking advantage of the inherent characteristics of Internet traffic to exploit parallelism make this improvement possible. Using four TCAM chips, an embodiment of the proposed model delivered more than six times the throughput of a conventional configuration with equal storage capacity and equal clock rate. Power consumption is also reduced in the new system. Other parameters such as storage density and table update performance are not adversely affected.
[1] 58 T. Pei and C. Zukowski, “Putting Routing Tables in Silicon,” IEEE Network Magazine, Jan. 1992.
[2] A. McAuley and P. Francis, “Fast Routing Table Lookup Using CAMs,” Proc. IEEE INFOCOM '93, Mar. 1993.
[3] P.C. Lekkas, Network Processors—Architectures, Protocols, and Platforms. McGraw Hill, 2004.
[4] V. Srinivasan, B. Nataraj, and S. Khanna, “Methods for Longest Prefix Matching in a Content Addressable Memory,” US Patent 6,237,061, Jan. 1999.
[5] F. Yu and R. Katz, “Efficient Multi-Match Packet Classification with TCAM,” Proc. 12th IEEE Symp. High Performance Interconnects (HOTI 12), Aug. 2004.
[6] H. Miyatake, M. Tanaka, and Y. Mori, “A Design for High-Speed Low-Power CMOS Fully Parallel Content-Addressable Memory Macros,” IEEE J. Solid-State Circuits, vol. 36, no. 6, June 2001.
[7] I. Arsovski, T. Chandler, and A. Sheikholeslami, “A Ternary Content-Addressable Memory (TCAM) Based on 4T Static Storage and Including a Current-Race Sensing Scheme,” IEEE J. Solid-State Circuits, vol. 38, no. 1, Jan. 2003.
[8] F. Zane, G. Narlikar, and A. Basu, “CoolCAMs: Power-Efficient TCAMs for Forwarding Engines,” Proc. IEEE INFOCOM, Mar. 2003.
[9] M. Akhbarizadeh, M. Nourani, D. Vijayasarathi, and P. Balsara, “PCAM: A Ternary CAM Optimized for Packet Forwarding Tasks,” Proc. IEEE Int'l Conf. Computer Design, Oct. 2004.
[10] R. Panigrahy and S. Sharma, “Reducing TCAM Power Consumption and Increasing Throughput,” Proc. 10th IEEE Symp. High Performance Interconnects (HOTI 10), Aug. 2002.
[11] M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network Magazine, Mar. 2001.
[12] G. Kasai et al., “2000MHz/200MSPS 3.2W at 1.5V Vdd, 9.4Mbits Ternary CAM with New Charge Injection Match Detect Circuits and Bank Selection Scheme,” Proc. IEEE Custom Integrated Circuits Conf., 2003.
[13] V.C. Ravikumar and R. Mahapatra, “TCAM Architecture for IP Lookup Using Prefix Properties,” IEEE Micro, Apr. 2004.
[14] K. Zheng et al., “An Ultra High Throughput and Power Efficient TCAM-Based IP Lookup Engine,” Proc. IEEE INFOCOM, Mar. 2004.
[15] “Intenet2 NetFlow Statistics,” http:/netflow.internet2.edu, 2004.
[16] M. Akhbarizadeh and M. Nourani, “Efficient Prefix Cache for Network Processors,” Proc. 12th IEEE Symp. High Performance Interconnects (HOTI 12), Aug. 2004.
[17] “Catalyst 6500/Cisco 7600 Series Supervisor Engine 720 Data Sheet,” http:/www.cisco.com, 2005.
[18] J. Wang and C. Huang, “High-Speed and Low-Power CMOS Priority Encoders,” IEEE J. Solid State Circuits, vol. 35, no. 10, Oct. 2000.
[19] M. Akhbarizadeh, M. Nourani, R. Panigrahy, and S. Sharma, “High-Speed and Low-Power Network Search Engine Using Adaptive Block-Selection Scheme,” Proc. 13th IEEE Symp. High Performance Interconnects (HOTI 13), pp. 73-78, Aug. 2005.
[20] “BGP Routing Table Analysis Reports,” http:/bgp.potaroo.net, 2004.
[21] Synopsys, Inc., “User Manuals for SYNOPSYS Toolset,” 2003.
[22] IDT Co., “Datasheet Brief 75P52100,” 2004.
[23] T. Chiueh and P. Pradham, “Cache Memory Design for Internet Processors,” IEEE Micro, Feb. 2000.
Index Terms:
System design, throughput increase, Internet packet forwarding engine, ternary content addressable memory, block selection scheme.
Citation:
Mohammad J. Akhbarizadeh, Mehrdad Nourani, Rina Panigrahy, Samar Sharma, "A TCAM-Based Parallel Architecture for High-Speed Packet Forwarding," IEEE Transactions on Computers, vol. 56, no. 1, pp. 58-72, Jan. 2007, doi:10.1109/TC.2007.5
PURCHASE ARTICLE: $19
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb