Hardware-based IP routing lookup with incremental update

Pi Chung Wang, Chia Tai Chan, Shuo Cheng Hu, Yu Chen Shin, Yaw-Chung Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Nowadays, the commonly used table lookup scheme for IP routing is based on the so-called classless interdomain routing (CIDR). With CIDR, routers must find out the best matching prefix (BMP) for IP packet forwarding, which complicates the IP lookup. Since the IP lookup performance is a major design issue for the new generation routers, we investigate the properties of the routing table and present a new IP lookup scheme. By adopting the extreme compression, the size of the forwarding table can be compressed to 360 Kbytes for a large routing table with 58,000 routing entries. It can accomplish one IPv4 route lookup within maximum nine memory accesses. Consequently, the data structure for the incremental update is introduced. With the new data structure, the proposed scheme can accomplish one route update within 500 ns. Even under the circumstance with 4000 route updates per second, the performance degradation is as low as 0.2 %.

Original languageEnglish
Title of host publicationProceedings - 9th International Conference on Parallel and Distributed Systems, ICPADS 2002
PublisherIEEE Computer Society
Pages183-188
Number of pages6
ISBN (Electronic)0769517609
DOIs
StatePublished - 1 Jan 2002
Event9th International Conference on Parallel and Distributed Systems, ICPADS 2002 - Taiwan, China
Duration: 17 Dec 200220 Dec 2002

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
Volume2002-January
ISSN (Print)1521-9097

Conference

Conference9th International Conference on Parallel and Distributed Systems, ICPADS 2002
CountryChina
CityTaiwan
Period17/12/0220/12/02

Keywords

  • Data structures
  • Degradation
  • Internet
  • Laboratories
  • Routing
  • Spine
  • Table lookup
  • Technology management
  • Telecommunications
  • World Wide Web

Fingerprint Dive into the research topics of 'Hardware-based IP routing lookup with incremental update'. Together they form a unique fingerprint.

Cite this