Article

A novel reconfigurable hardware architecture for IP address lookup

Authors:

Hamid Fadishei,

Morteza Saheb Zamani,

Masoud SabaeiAuthors Info & Claims

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

Pages 81 - 90

https://doi.org/10.1145/1095890.1095903

Published: 26 October 2005 Publication History

Abstract

IP address lookup is one of the most challenging problems of Internet routers. In this paper, an IP lookup rate of 263 Mlps (Million lookups per second) is achieved using a novel architecture on reconfigurable hardware platform. A partial reconfiguration may be needed for a small fraction of route updates. Prefixes can be added or removed at a rate of 2 million updates per second, including this hardware reconfiguration overhead. A route update may fail due to the physical resource limitations. In this case, which is rare if the architecture is properly configured initially, a full reconfiguration is needed to allocate more resources to the lookup unit.

References

[1]

H. Chao, C. Lam, and E. Oki, "Broadband Packet Switching Technologies", John Wiley Publications, 2001, 365--405.

Digital Library

[2]

K. Compton, and S. Hauck, "Reconfigurable Computing: A Survey of Systems and Software", ACM Computing Surveys (CSUR), Vol. 34, No. 2, June 2002, 171--210.

Digital Library

[3]

M. Desai, R. Gupta, A. Karandikar, K. Saxena, and V. Samant, "Reconfigurable Finite-State Machine Based IP Lookup Engine for High-Speed Router", IEEE Journal on Selected Areas in Communications (JSAC), Vol. 21, No. 4, May 2003, 501--512.

Digital Library

[4]

P. Gupta, S. Lin, and N. McKeown, "Routing Lookups in Hardware at Memory Access Speeds", IEEE Informatics and Communications Conference (INFOCOM), Vol. 3, April 1998, 1240--1247.

[5]

N. Huang, S. Zhao, J. Pan, and C. Su, "A Fast IP Routing Lookup Scheme for Gigabit Switching Routers", IEEE Informatics and Communications Conference (INFOCOM), Vol. 3, March 1999, 1429--1436.

[6]

R. Jain, "A Comparison of Hashing Schemes for Address Lookup in Computer Networks", IEEE Transactions on Communications, Vol. 40, No. 10, October 1992, 1570--1573.

[7]

F. Kuhns, J. DeHart, A. Kantawala, R. Keller, J. Lockwood, P. Pappu, D. Richard, D. Taylor, J. Parwatikar, E. Spitzangel, J. Turner, and K. Wong, "Design and Evaluation of a High- Performance Dynamically Extensible Router", IEEE DARPA Active Networks Conference and Exposition (DANCE), May 2002, 42--46.

Digital Library

[8]

B. Lampson, V. Srinivasan, and G. Varghese, "IP Lookups Using Multiway and Multicolumn Search", IEEE/ACM Transactions on Networking (TON), Vol. 7, No. 3, June 1999, 324--334.

Digital Library

[9]

H. Lim, J. Seo, and Y. Jung, "High Speed IP Address Lookup Architecture Using Hashing", IEEE Communications Letters, Vol. 7, No. 10, October 2003, 502--504.

[10]

A. McAuley, P. Tsuchiya, and D. Wilson, "Fast Multilevel Hierarchical Routing Table Lookup Using Content Addressable Memory", US Patent, No. 05386413, January 1995.

[11]

D. Morrison, "PATRICIA- Practical Algorithm to Retrieve Information Coded in Alphanumeric", Journal of ACM (JACM), Vol. 15, No. 4, October 1968, 514--534.

Digital Library

[12]

S. Nilsson, and G. Karlsson, "IP-Address Lookup Using LC-Tries", IEEE Journal on Selected Areas in Communications (JSAC), Vol. 17, No. 6, June 1999, 1083--1092.

Digital Library

[13]

D. Pao, C. Liu, A. Wu, L. Yeung, and K. Chan, "Efficient Hardware Architecture for Fast IP Address Lookup", IEEE Informatics and Communications Conference (INFOCOM), Vol. 2, June 2002, 555--561.

[14]

M. Ruiz-Sánchez, E. Biersack, and W. Dabbous, "Survey and Taxonomy of IP Address Lookup Algorithms", IEEE Network Magazine, March/April 2001, 8--23.

Digital Library

[15]

R. Sangireddy, and A. Somani, "High-Speed IP Routing with Binary Decision Diagrams Based Hardware Address Lookup Engine", IEEE Journal on Selected Areas in Communications (JSAC), Vol. 21, No. 4, May 2003, 513--521.

Digital Library

[16]

M. Sprachmann, "Automatic Generation of Parallel CRC Circuits", IEEE Conference on Design and Test of Computers, Vol. 18, No. 3, May 2001, 108--114.

Digital Library

[17]

V. Srinivasan, and G. Varghese, "Fast Address Lookups Using Controlled Prefix Expansion", ACM Transactions on Computer Systems (TOCS), Vol. 17, No. 1, February 1999, 1--40.

Digital Library

[18]

D. Taylor, J. Lockwood, T. Sproull, J. Turner, and D. Parlour, "Scalable IP Lookup for Programmable Routers", IEEE Informatics and Communications Conference (INFOCOM), Vol. 2, 2002, 562--571.

[19]

M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, "Scalable High Speed IP Routing Lookups", ACM Special Interest Group on Data Communications (SIGCOMM), September 1997, 25--36.

Digital Library

[20]

L. Wuu, and S. Pin, "A Fast IP Lookup Scheme for Longest- Matching Prefix", IEEE International Conference on Computer Networks and Mobile Computing (ICCNMC), October 2001, 407--412.

Digital Library

[21]

N. Yazdani, and P. Min, "Fast and Scalable Schemes for the IP Address Lookup Problem", IEEE Conference on High Performance Switching and Routing (HPSR), 2000, 83--92.

[22]

Routing Information Service, Online, http://www.ripe.net/ris/.

[23]

Xilinx Virtex-II Pro FPGA Family Users Guide and Datasheets, Online, http://www.xilinx.com.

Cited By

Cong PZhang YLiu BWang WXiong ZXu K(2022)A&B: AI and Block-Based TCAM Entries Replacement Scheme for RoutersIEEE Journal on Selected Areas in Communications10.1109/JSAC.2022.319135140:9(2643-2661)Online publication date: Sep-2022
https://doi.org/10.1109/JSAC.2022.3191351
Higuchi SKoizumi YTakemasa JTagami AHasegawa T(2021)Learned FIB: Fast IP Forwarding without Longest Prefix Matching2021 IEEE 29th International Conference on Network Protocols (ICNP)10.1109/ICNP52444.2021.9651956(1-11)Online publication date: 1-Nov-2021
https://doi.org/10.1109/ICNP52444.2021.9651956
Chuprikov PDemianiuk VGorinsky S(2021)PREDICAT: Efficient Packet Classification via Prefix Disjointness2021 International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN52240.2021.9522287(1-11)Online publication date: Jul-2021
https://doi.org/10.1109/ICCCN52240.2021.9522287
Show More Cited By

Index Terms

A novel reconfigurable hardware architecture for IP address lookup
1. Hardware
  1. Very large scale integration design
    1. Application-specific VLSI designs
      1. Application specific processors
2. Networks
  1. Network components
    1. Intermediate nodes
      1. Routers

Recommendations

A fast IP routing lookup architecture for multi-gigabit switching routers based on reconfigurable systems

With today's networks complexity, routers in backbone links must be able to handle millions of packets per second on each of their ports. Determining the corresponding output interface for each incoming packet based on its destination address requires a ...
A SRAM-based Architecture for Trie-based IP Lookup Using FPGA
FCCM '08: Proceedings of the 2008 16th International Symposium on Field-Programmable Custom Computing Machines

Internet Protocol (IP) lookup in routers can be implemented by some form of tree traversal. Pipelining can dramatically improve the search throughput. However, it results in unbalanced memory allocation over the pipeline stages. This has been identified ...
Implementing an OFDM Receiver on the RaPiD Reconfigurable Architecture

Field-programmable gate arrays (FPGAs) have become an extremely popular implementation technology for custom hardware because they offer a combination of low cost and very fast turnaround. Because of their in-system reconfigurability, FPGAs have also ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

October 2005

230 pages

ISBN:1595930825

DOI:10.1145/1095890

General Chair:
Alan Berenbaum
SMSC
,
Program Chairs:
Kai Li
Princeton University, Princeton, NJ
,
Jonathan Turner
Washington University in St. Louis

Copyright © 2005 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: 26 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ANCS05

Sponsor:

ANCS05: Symposium on Architecture for Networking and Communications Systems 2005

October 26 - 28, 2005

NJ, Princeton, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
520
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cong PZhang YLiu BWang WXiong ZXu K(2022)A&B: AI and Block-Based TCAM Entries Replacement Scheme for RoutersIEEE Journal on Selected Areas in Communications10.1109/JSAC.2022.319135140:9(2643-2661)Online publication date: Sep-2022
https://doi.org/10.1109/JSAC.2022.3191351
Higuchi SKoizumi YTakemasa JTagami AHasegawa T(2021)Learned FIB: Fast IP Forwarding without Longest Prefix Matching2021 IEEE 29th International Conference on Network Protocols (ICNP)10.1109/ICNP52444.2021.9651956(1-11)Online publication date: 1-Nov-2021
https://doi.org/10.1109/ICNP52444.2021.9651956
Chuprikov PDemianiuk VGorinsky S(2021)PREDICAT: Efficient Packet Classification via Prefix Disjointness2021 International Conference on Computer Communications and Networks (ICCCN)10.1109/ICCCN52240.2021.9522287(1-11)Online publication date: Jul-2021
https://doi.org/10.1109/ICCCN52240.2021.9522287
Ueno YNakamura RKuga YEsaki H(2020)Fast Longest Prefix Matching by Exploiting SIMD InstructionsIEEE Access10.1109/ACCESS.2020.30231568(167027-167041)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3023156
Liu LHu JYan YGao SYang TLi X(2019)Longest Prefix Matching with Pruning2019 IEEE 20th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2019.8808125(1-6)Online publication date: May-2019
https://doi.org/10.1109/HPSR.2019.8808125
Yang TXie GLiu AFu QLi YLi XMathy L(2018)Constant IP Lookup With FIB ExplosionIEEE/ACM Transactions on Networking10.1109/TNET.2018.285357526:4(1821-1836)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2853575
Fradj BWolff BBelanger NSavaria Y(2018)Implementation of a Cache-Based IPv6 Lookup System with Hashing2018 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2018.8351362(1-4)Online publication date: May-2018
https://doi.org/10.1109/ISCAS.2018.8351362
NAKAHARA HSASAO TMATSUURA MIWAMOTO HTERAO Y(2015)A Memory-Based IPv6 Lookup Architecture Using Parallel Index Generation UnitsIEICE Transactions on Information and Systems10.1587/transinf.2014RCP0006E98.D:2(262-271)Online publication date: 2015
https://doi.org/10.1587/transinf.2014RCP0006
Yang TXie GLi YFu QLiu ALi QMathy L(2014)Guarantee IP lookup performance with FIB explosionACM SIGCOMM Computer Communication Review10.1145/2740070.262629744:4(39-50)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.1145/2740070.2626297
Yang TXie GLi YFu QLiu ALi QMathy LBustamante FHu YKrishnamurthy ARatnasamy S(2014)Guarantee IP lookup performance with FIB explosionProceedings of the 2014 ACM conference on SIGCOMM10.1145/2619239.2626297(39-50)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.1145/2619239.2626297
Show More Cited By

View Options

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.

Figures

Tables

Media

View Table of Conten