Performance Evaluation of an Alternative IP Lookup Scheme for Implementing High-Speed Routers

Min Young CHUNG  Jaehyung PARK  Jeong Ho KIM  Byung Jun AHN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.12   pp.2764-2772
Publication Date: 2004/12/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Networks
Keyword: 
IP lookup,  forwarding table update,  high-speed router,  IQ2200TM,  

Full Text: PDF(1MB)>>
Buy this Article




Summary: 
The most important function of a router is to perform IP lookup that determines the output ports of incoming IP packets by their destination addresses. Hence, IP lookup is one of the main issues in implementing high-speed routers. The IP lookup algorithm implemented in IQ2200 Chipset with two-level table architecture can efficiently use memory. However, it wastes processor resource for full re-construction of the forwarding tables whenever every route insertion/deletion is requested. In order to improve the utilization of processor resource, we propose an IP lookup algorithm with three-level table architecture for high-speed routers. We evaluate the performance of the proposed algorithm in terms of the memory size required for storing lookup information and the number of memory access in constructing forwarding tables. Being compared with the IQ2200 scheme, the proposed scheme can reduce the number of memory access up to 99% even though it needs about 16% more memory.