research-article

Low power fast and dense longest prefix match content addressable memory for IP routers

Authors:

Satendra Kumar Maurya,

Lawrence T. ClarkAuthors Info & Claims

ISLPED '09: Proceedings of the 2009 ACM/IEEE international symposium on Low power electronics and design

Pages 389 - 394

https://doi.org/10.1145/1594233.1594333

Published: 19 August 2009 Publication History

Publisher Site Get Access

Abstract

An IP router determines the next hop for an internet protocol packet by finding the longest prefix match. Ternary CAMs, which allow bit masking of the IP address, are commonly used for this fast search function. In this paper, a CAM that directly determines the longest prefix match to the stored address is described. One of these best matching (IPCAM) entries replaces on average 22 TCAM entries. Overall, the resulting IPCAM array is less than 1/10 the size of the equivalent TCAM and dissipates 93.5% less dynamic power. The design automatically produces an encoded prefix match length that is limited by the prefix mask, so entries do not need to be sorted in prefix mask length order. Simulations of extracted layouts in a bulk CMOS 65-nm foundry process show the proposed IPCAM circuits can operate above 1 GHz

References

[1]

Baker, F. RFC1812"2.2.5.2ClasslessInterDomain Routing (CIDR)". Online: http://rfc.sunsite.dk/rfc/rfc1812.html.

[2]

Sklower, K., A Tree-Based Routing Table for Berkeley Unix, Technical report, University of California, Berkeley, 1993.

[3]

Gupta, P., Lin, S., McKeown, N., "Routing Lookups in Hardware at Memory Access Speeds", Proc. IEEE INFOCOM (March 1998) 1240--1247.

[4]

Wuu, L., Pin, S., "A Fast IP Lookup Scheme for Longest-Matching Prefix", Proc. IEEE Intl. Conf. on Computer Networks and Mobile Computing (Oct. 2001) 407--412.

Digital Library

[5]

Pei, T., Zukowski, C., "Putting routing tables in silicon, IEEE Network Mag., 6, 1, (Jan. 1992) 42--50.

Digital Library

[6]

Degermark, M., Brodnik, A., Carlsson, S., Pink, S., "Small forwarding tables for fast routing lookups," Proc. ACM SIGCOMM Computer Communication Review 27, 4 (October 1997) 3--15.

Digital Library

[7]

Huang, N., Zhao, S., Pan, J., Su, C., "A fast IP routing lookup scheme for gigabit switching routers," Proc. IEEE INFOCOM, vol. 3 (March 1999) 1429--436.

[8]

Pagiamtzis, K., Sheikholeslami, A., "Content-addressable memory circuits and architectures: A tutorial and survey, IEEE J. Solid-state Circuits, 41, 3 (March 2006) 712--727.

[9]

McAuley, A., Francis, P., "Fast routing table lookup using CAMs," in Proc. IEEE INFOCOM vol. 3 (March 1993) 1382--1391.

[10]

Hayashi, T. and Miyazaki, T., "High-speed table lookup engine for IPv6 longest prefix match," in Proc. IEEE GLOBECOM vol.2 (Dec. 1999) 1576--1581.

[11]

Akhbarizadeh, M., Nourani, M., Vijayasarathi, D., Balsara, P., "A Nonredundant Ternary CAM Circuit for Network Search Engines," IEEE Trans. VLSI Syst. 14, 3 (March 2006) 268--278.

Digital Library

[12]

Chaudhary, V., Clark, L., "Low-power high-performance NAND match line content addressable memories" IEEE Trans. VLSI Syst. 14, 8 (Aug. 2006) 895--905.

Digital Library

[13]

Panigrahy, R., Sharma, S., "Reducing TCAM Power Consumption and Increasing Throughput" Proc. IEEE Symp. on High Performance Interconnects. (Aug. 2002) 107--112.

Digital Library

[14]

Online: http://www-03.ibm.com/technology/foundry.

[15]

Online: http://bgp.potaroo.net.

Cited By

Rasmussen AKragelund ABerger MWessing HRuepp S(2013)TCAM-based high speed Longest prefix matching with fast incremental table updates2013 IEEE 14th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2013.6602288(43-48)Online publication date: Jul-2013
https://doi.org/10.1109/HPSR.2013.6602288
Maurya SClark L(2011)A Dynamic Longest Prefix Matching Content Addressable Memory for IP RoutingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2010.204282619:6(963-972)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TVLSI.2010.2042826
Du HWei WYang J(2011)A B-Tree Algorithm for Partitioned Index Based on CIDR List in High-End RouterProceedings of the 2011 International Conference of Information Technology, Computer Engineering and Management Sciences - Volume 0210.1109/ICM.2011.125(124-128)Online publication date: 24-Sep-2011
https://dl.acm.org/doi/10.1109/ICM.2011.125

Low power fast and dense longest prefix match content addressable memory for IP routers
1. Hardware
2. Networks
  1. Network protocols
    1. Network layer protocols

Recommendations

A Dynamic Longest Prefix Matching Content Addressable Memory for IP Routing

An internet protocol (IP) router determines the next hop for a packet by finding the longest prefix match. This lookup often occurs in ternary content addressable memory (TCAM), which allows bit masking of the IP address. In this paper, an internet ...
Low-power high-performance NAND match line content addressable memories

Content addressable memory (CAM) is used in fully associative VLSI lookup circuits for cache memory, translation lookaside buffers (TLBs), and in Internet Protocol (IP) address comparison. In this paper, the use of dynamic NAND match lines is ...
Fast binary and multiway prefix searches for packet forwarding

Backbone routers with tens-of-gigabits-per-second links are indispensable communication devices to deploy on the Internet. The IP lookup operation is the most critical task that must be improved in routers. In this paper, we first present a systematic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISLPED '09: Proceedings of the 2009 ACM/IEEE international symposium on Low power electronics and design

August 2009

452 pages

ISBN:9781605586847

DOI:10.1145/1594233

General Chairs:
Jörg Henkel
University of Karlsruhe
,
Ali Keshavarzi
Taiwan Semiconductor Manufacturing Company
,
Program Chairs:
Naehyuck Chang
Seoul National University
,
Tahir Ghani
Intel Corporation

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISLPED'09

Sponsor:

ISLPED'09: International Symposium on Low Power Electronics and Design

August 19 - 21, 2009

CA, San Fancisco, USA

Acceptance Rates

ISLPED '09 Paper Acceptance Rate 72 of 208 submissions, 35%;

Overall Acceptance Rate 398 of 1,159 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
257
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rasmussen AKragelund ABerger MWessing HRuepp S(2013)TCAM-based high speed Longest prefix matching with fast incremental table updates2013 IEEE 14th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2013.6602288(43-48)Online publication date: Jul-2013
https://doi.org/10.1109/HPSR.2013.6602288
Maurya SClark L(2011)A Dynamic Longest Prefix Matching Content Addressable Memory for IP RoutingIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2010.204282619:6(963-972)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1109/TVLSI.2010.2042826
Du HWei WYang J(2011)A B-Tree Algorithm for Partitioned Index Based on CIDR List in High-End RouterProceedings of the 2011 International Conference of Information Technology, Computer Engineering and Management Sciences - Volume 0210.1109/ICM.2011.125(124-128)Online publication date: 24-Sep-2011
https://dl.acm.org/doi/10.1109/ICM.2011.125

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents