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

Junghwan KIM; Minkyu PARK; Sangchul HAN; Jinsoo KIM

doi:10.1587/transcom.E95.B.3298

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

Junghwan KIM, Minkyu PARK, Sangchul HAN, Jinsoo KIM

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Communications Vol.E95-B No.10 pp.3298-3301

Publication Date: 2012/10/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1587/transcom.E95.B.3298

Type of Manuscript: LETTER

Category: Network System

Cite this

Copy

Junghwan KIM, Minkyu PARK, Sangchul HAN, Jinsoo KIM, "An Efficient Prefix Caching Scheme with Bounded Prefix Expansion for High-Speed IP Lookup" in IEICE TRANSACTIONS on Communications, vol. E95-B, no. 10, pp. 3298-3301, October 2012, doi: 10.1587/transcom.E95.B.3298.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E95.B.3298/_p

Copy

@ARTICLE{e95-b_10_3298,
author={Junghwan KIM, Minkyu PARK, Sangchul HAN, Jinsoo KIM, },
journal={IEICE TRANSACTIONS on Communications},
title={An Efficient Prefix Caching Scheme with Bounded Prefix Expansion for High-Speed IP Lookup},
year={2012},
volume={E95-B},
number={10},
pages={3298-3301},
abstract={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.},
keywords={},
doi={10.1587/transcom.E95.B.3298},
ISSN={1745-1345},
month={October},}

Copy

TY - JOUR
TI - An Efficient Prefix Caching Scheme with Bounded Prefix Expansion for High-Speed IP Lookup
T2 - IEICE TRANSACTIONS on Communications
SP - 3298
EP - 3301
AU - Junghwan KIM
AU - Minkyu PARK
AU - Sangchul HAN
AU - Jinsoo KIM
PY - 2012
DO - 10.1587/transcom.E95.B.3298
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E95-B
IS - 10
JA - IEICE TRANSACTIONS on Communications
Y1 - October 2012
AB - 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.
ER -