More Web Proxy on the site http://driver.im/

Article

A Scalable and Small Forwarding Table for Fast IP Address Lookups

Authors:

Sang-Hung Chung,

Hyunsoo YoonAuthors Info & Claims

ICCNMC '01: Proceedings of the 2001 International Conference on Computer Networks and Mobile Computing (ICCNMC'01)

Page 413

Published: 16 October 2001 Publication History

Abstract

IP address lookup is an important design issue for the high performance Internet routers. The most important function of routers is to determine the output port of an incoming IP packet according to its destination address. In this paper, we propose a scalable and simple forwarding table structure for fast hardware-based IP address lookup which reduces memory requirements and memory access times. Proposed scheme requires maximum two memory access times in the worst case to finish an IP address lookup. And it consumes about 0.6 ¢ 1.1MBytes memory for large routing tables with 16,000 ¢ 43,000 routing prefixes whenany compression method is not used.

References

[1]

Chris Metz. IP ROUTERS: New Tool for Gigabit Networking. IEEE Internet Computing, 2(6):14-18, Nov/Dec 1998.

Digital Library

[2]

Gene Cheung, and Steve McCanne. Optimal Routing Table Design for IP Address Lookups Under Memory Constraints. In Proceedings of the INFOCOM 1999, volume 3, pages 1437-1444, 1999.

[3]

Henry Hong-Yi Tzeng, and Tony Przygienda. On Fast Address-Lookup Algorithms. IEEE Jouranl on Selected Areas in Communications, 17(6): 1067-1082, June 1999.

Digital Library

[4]

M. Degermark, A. Brodnik, S. Carlsson, and S. Pink. Small Forwarding Tables for Fast Routing Lookups. In Proceedings of the ACM SIGCOMM 1997, pages 3-14, 1997.

Digital Library

[5]

Marcel Waldvogel, George Varghese, Jon Turner, and Bernhard Plattner. Scalable High Speed IP Routing Lookups. In Proceedings of ACM SIGCOMM 1997, pages 25-36, 1997.

Digital Library

[6]

Merit Inc. IPMA Statistics. http://nic.merit.edu/ipma, 1998.

[7]

Nen-Fu Huang, and Shi-Ming Zhao. A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers. IEEE Jouranl on Selected Areas in Communications, 17(6):1093-1104, June 1999.

Digital Library

[8]

P. Newman, G. Minshall, T. L. Lyon, and L. Huston. IP Switching and Gigabit Routers. IEEE Communications Magazine, 35(1):64-69, Jan 1997.

Digital Library

[9]

Pankaj Gupta, Steven Lin, and Nick McKeown. Routing Lookups in Hardware at Memory Access Speeds. In Proceedings of INFOCOM 1998, pages 1240-1247, 1998.

[10]

Pi-Chung Wang, Chia-Tai Chan, and Yaw-Chung Chen. A Fast IP Routing Lookup Scheme. In Proceedings of the ICC 2000, volume 2, pages 1114-1144, 2000.

[11]

Stefan Nilsson, and Gunnar Karlsson. IP-Address Lookup Using LC-Tries. IEEE Jouranl on Selected Areas in Communications, 17(6):1083-1092, June 1999.

Digital Library

[12]

T. Chaney, J. Andrew Fingerhut, M. Flucke, Jonathan S. Turner. Design of A Gigabit ATM Switch. In Proceedings of the INFOCOM 1997, volume 1, pages 2-11, 1997.

Digital Library

[13]

V. Fuller, T. Li, J. Yu, and K. Varadhan. Classless Inter-Domain Routing(CIDR): an Address Assignment and Aggregation Strategy. RFC1519, Sep 1993.

[14]

V. Srinivasan and G. Varghese. Fast Address Lookups using Controlled Prefix Expansion. ACM Transactions on Computer Systems, 17(1): 1-40. Feb 1999.

Digital Library

[15]

Willibald Doeringer, Gunter Karjoth and Mehdi Nassehi. Routing on Longest-Matching Prefixes. IEEE/ACM Transactions on Networking, 4(1):86-97, Feb 1996.

Digital Library

Cited By

Park JChung MKim JWon Y(2004)A distributed architecture of the indirect IP lookup scheme for high-speed routersProceedings of the 5th international conference on Parallel and Distributed Computing: applications and Technologies10.1007/978-3-540-30501-9_100(519-526)Online publication date: 8-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30501-9_100

A Scalable and Small Forwarding Table for Fast IP Address Lookups
1. Networks
  1. Network protocols
    1. Network layer protocols

Recommendations

A fast and scalable IPv4 and 6 address lookup algorithm

Due to Internet's exponential growth in the last few years, we face two serious problems. First, the network becomes congested. Second, the number of IP addresses is not enough for distribution. For network congestion, we use fibers in the backbone of ...
Small forwarding tables for fast routing lookups
SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication

For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the longest matching prefix, a task that has been ...
Small forwarding tables for fast routing lookups

For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the longest matching prefix, a task that has been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICCNMC '01: Proceedings of the 2001 International Conference on Computer Networks and Mobile Computing (ICCNMC'01)

October 2001

ISBN:0769513816

Copyright © Copyright (c) 2001 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 16 October 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Park JChung MKim JWon Y(2004)A distributed architecture of the indirect IP lookup scheme for high-speed routersProceedings of the 5th international conference on Parallel and Distributed Computing: applications and Technologies10.1007/978-3-540-30501-9_100(519-526)Online publication date: 8-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30501-9_100

View Options

View options

Media

Figures

Other

Tables

View Table of Contents