Power and Time Efficient IP Lookup Table Design Using Partitioned TCAMs

Youngjung Ahn, Yongsuk Lee, Gyungho Lee

Department of Computer Science & Engineering, Korea University, Seoul, South Korea.

DOI: 10.4236/cs.2013.43041                

Abstract

This paper proposes a power and time efficient scheme for designing IP lookup tables. The proposed scheme uses partitioned Ternary Content Addressable Memories (TCAMs) that store IP lookup tables. The proposed scheme enables O(1) time penalty for updating an IP lookup table. The partitioned TCAMs allow an update done by a simple insertion without the need for routing table sorting. The organization of the routing table of the proposed scheme is based on a partition with respect to the output port for routing with a smaller priority encoder. The proposed scheme still preserves a similar storage requirement and clock rate to those of existing designs. Furthermore, this scheme reduces power consumption due to using a partitioned routing table.

Keywords

IP Lookup Device; Routing Table; TCAMs; Insertion

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	“Latest Version of AS65000-BGP Routing Table Statistics Analysis Report.” http://bgp.potaroo.net/as2.0/bgp-active.html
[2]	V. Srinivasan, B. Nataraj and S. Khanna, “Methods for Longest Prefix Matching In a Content Addressable Memory,” US Patent 6237061, 1999.
[3]	R. Guo and J. G. Delgado-Frias, “IP Routing Table Compaction and Sampling Schemes to Enhance TCAM Cache Performance,” Journal of Systems Architecture, Vol. 55, No. 1, 2009, pp. 61-69. doi:10.1016/j.sysarc.2008.08.001
[4]	K. Pagiamtzis and A. Sheikholeslami, “Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey,” IEEE Journal of Solid-State Circuits, Vol. 41, No. 3, 2006, pp. 712-727. doi:10.1109/JSSC.2005.864128
[5]	S. Kaxiras and G. Keramidas, “IPStash: A Power-Efficient Memory Architecture for IP-Lookup,” 36th International Proceedings of Symposium on Microarchitecture, San Diego, 3-5 December 2003, pp. 361-372.
[6]	M. J. Akhbarizadeh and M. Nourani, “An IP Packet Forwarding Technique Based on Partitioned Lookup Table,” IEEE International Conference on Communications, Vol. 4, 2002, pp. 2263-2267.
[7]	D. Shah and P. Gupta, “Fast Updating Algorithms for TCAMs,” IEEE Micro, Vol. 21, No. 1, 2001, pp. 36-47. doi:10.1109/40.903060
[8]	T. Kocak and F. Basci, “A Power-Efficient TCAM Architecture for Network Forwarding Tables,” Journal of Systems Architecture, Vol. 52, No. 5, 2006, pp. 307-314. doi:10.1016/j.sysarc.2005.12.001
[9]	V. C. Ravikumar, R. N. Mahapatra and L. N. Bhuyan, “EaseCAM: An Energy and Storage Efficient TCAMBased Router Architecture for IP Lookup,” IEEE Transactions of Computer, Vol. 54, No. 5, 2005, pp. 521-533. doi:10.1109/TC.2005.78
[10]	B. S. Amrutur and M. A. Horowitz, “Speed and Power Scaling of SRAMs,” IEEE Transactions on Solid-State Circuits, Vol. 35, No. 2, 2000, pp. 175-185. doi:10.1109/4.823443
[11]	The Internet Performance Measurement and Analysis Project. http://ftp.chg.ru/pub/network/routing/ipma/Manual/
[12]	C. H. Huang and J. S. Wang, “High-Performance and Power-Efficient CMOS Comparators,” IEEE Journal of Solid-State Circuits, Vol. 38, No. 2, 2003, pp. 254-262. doi:10.1109/JSSC.2002.807409
[13]	W. Lu and S. Sahni, “Low-Power TCAMs for Very Large Forwarding Tables,” IEEE/ACM Transactions on Networking, Vol. 18, No. 3, 2010, pp. 948-959. doi:10.1109/TNET.2009.2034143
[14]	B. Agrawal and T. Sherwood, “Ternary CAM Power and Delay Model: Extensions and Uses,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 16, No. 5, 2008, pp. 554-564.