For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2012/10/01
Online ISSN: 1745-1345
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network System
IP address lookup, prefix caching, prefix expansion, routing,
Full Text: PDF(472.2KB)>>
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.