High-performance IP routing table lookup

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 packets forwarding, which complicates the IP lookup. Currently, this process is mainly done in softwar...

Full description

Saved in:
Bibliographic Details
Published in:Computer communications 2002-02, Vol.25 (3), p.303-312
Main Authors: Wang, Pi-Chung, Chan, Chia-Tai, Chen, Yaw-Chung
Format: Article
Language:English
Subjects:
Classless interdomain routing
IP routing
Networks
Pipeline technique
Routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 packets forwarding, which complicates the IP lookup. Currently, this process is mainly done in software and several schemes have been proposed for hardware implementation. Since the IP lookup performance is a major design issue for the new generation routers, in this article we propose a fast IP address lookup scheme, which significantly reduces the forwarding table to fit into SRAM with very low cost. It can also be implemented in hardware using the pipeline technique. By using our proposed method, the required memory space can be 90–170 Kb less than the previous scheme and three memory accesses for a lookup in the worst case. When implemented in hardware pipeline architecture, our mechanism can achieve one routing lookup per memory access.
ISSN:0140-3664
1873-703X
DOI:10.1016/S0140-3664(01)00360-7