Fast IP routing lookup scheme

Pi Chung Wang*, Chia Tai Chan, Yaw-Chung Chen

*Corresponding author for this work

Research output: Contribution to conferencePaper

16 Scopus citations

Abstract

A major design issue for the next generation routers is the IP lookup mechanism. The router needs to perform a longest prefix matching on the address lookup for each incoming packet to determine the next hop. Currently, the process is done in software and has become a major performance bottleneck of the router. In this paper, we propose a fast IP lookup mechanism in which the forwarding table is small enough to fit in SRAM with very low cost. It also can be implemented in hardware using the pipeline technique. A large routing table with 45,000 routing prefixes can be compressed to a forwarding table with about 430 Kbytes in size by using our proposed method. In the worst case, the number of memory accesses for a lookup is three. When implemented in pipeline technique, the proposed mechanism can achieve one routing lookup per memory access. With current 10 ns SRAM, this mechanism provides approximately 100 million routing lookups per second. Furthermore, the lookup speed can be improved linearly through the speedup of the memory access.

Original languageEnglish
Pages1140-1144
Number of pages5
StatePublished - 3 Dec 2000
Event2000 IEEE International Conference on Communications - New orleans, LA, USA
Duration: 18 Jun 200022 Jun 2000

Conference

Conference2000 IEEE International Conference on Communications
CityNew orleans, LA, USA
Period18/06/0022/06/00

Fingerprint Dive into the research topics of 'Fast IP routing lookup scheme'. Together they form a unique fingerprint.

  • Cite this

    Wang, P. C., Chan, C. T., & Chen, Y-C. (2000). Fast IP routing lookup scheme. 1140-1144. Paper presented at 2000 IEEE International Conference on Communications, New orleans, LA, USA, .