Fast IP routing lookup scheme

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

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

16 Scopus citations


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
Number of pages5
StatePublished - 3 Dec 2000
Event2000 IEEE International Conference on Communications - New orleans, LA, USA
Duration: 18 Jun 200022 Jun 2000


Conference2000 IEEE International Conference on Communications
CityNew orleans, LA, USA

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

Cite this