A Fast IP Address Lookup Algorithm Based on Search Space Reduction

Hyuntae PARK  Hyunjin KIM  Hong-Sik KIM  Sungho KANG  

IEICE TRANSACTIONS on Communications   Vol.E93-B   No.4   pp.1009-1012
Publication Date: 2010/04/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E93.B.1009
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Switching for Communications
IP address lookup,  search space reduction,  partitioning,  

Full Text: PDF(230.6KB)>>
Buy this Article

This letter proposes a fast IP address lookup algorithm based on search space reduction. Prefixes are classified into three types according to the nesting relationship and a large forwarding table is partitioned into multiple small trees. As a result, the search space is reduced. The results of analyses and experiments show that the proposed method offers higher lookup and updating speeds along with reduced memory requirements.