An Efficient Prefix Caching Scheme with Bounded Prefix Expansion for High-Speed IP Lookup

Junghwan KIM  Minkyu PARK  Sangchul HAN  Jinsoo KIM  

IEICE TRANSACTIONS on Communications   Vol.E95-B   No.10   pp.3298-3301
Publication Date: 2012/10/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E95.B.3298
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network System
IP address lookup,  prefix caching,  prefix expansion,  routing,  

Full Text: PDF>>
Buy this Article

Prefix caching improves the performance of IP lookup by exploiting spatial and temporal locality of IP references. However, it cannot cache non-leaf prefixes, so several prefix expansion schemes have been proposed to handle those prefixes. Such schemes have some drawbacks to incur modification of routing table or severe miss penalty. We propose an efficient prefix expansion scheme which achieves good performance without additional burden to lookup scheme. In the proposed scheme a non-leaf prefix is expanded to the length of the longest immediate descendant prefix when it is cached. Evaluation result shows our scheme achieves very low miss ratio even though it does not increase the size of routing table and cache miss penalty.