We propose a fast and compact longest match table look-up method for very long network addresses like IP version 6. This method uses two ideas for a routing-table arranged in a tree-structure. The first idea is to make table look-up fast by caching pointers to intermediate nodes in the tree, reducing the number of node traversals. The second idea is to reduce the memory size required for each node in the tree by one-third by eliminating common parts of addresses of adjacent nodes. Evaluating the performance of this method by using actual routing table data of an IP backbone network, we found it was five to ten times faster than a conventional method.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Masanori UGA, Kohei SHIOMOTO, "A Longest Match Table Look-up Method Using Pointer Cache" in IEICE TRANSACTIONS on Communications,
vol. E84-B, no. 6, pp. 1664-1673, June 2001, doi: .
Abstract: We propose a fast and compact longest match table look-up method for very long network addresses like IP version 6. This method uses two ideas for a routing-table arranged in a tree-structure. The first idea is to make table look-up fast by caching pointers to intermediate nodes in the tree, reducing the number of node traversals. The second idea is to reduce the memory size required for each node in the tree by one-third by eliminating common parts of addresses of adjacent nodes. Evaluating the performance of this method by using actual routing table data of an IP backbone network, we found it was five to ten times faster than a conventional method.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e84-b_6_1664/_p
Copy
@ARTICLE{e84-b_6_1664,
author={Masanori UGA, Kohei SHIOMOTO, },
journal={IEICE TRANSACTIONS on Communications},
title={A Longest Match Table Look-up Method Using Pointer Cache},
year={2001},
volume={E84-B},
number={6},
pages={1664-1673},
abstract={We propose a fast and compact longest match table look-up method for very long network addresses like IP version 6. This method uses two ideas for a routing-table arranged in a tree-structure. The first idea is to make table look-up fast by caching pointers to intermediate nodes in the tree, reducing the number of node traversals. The second idea is to reduce the memory size required for each node in the tree by one-third by eliminating common parts of addresses of adjacent nodes. Evaluating the performance of this method by using actual routing table data of an IP backbone network, we found it was five to ten times faster than a conventional method.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - A Longest Match Table Look-up Method Using Pointer Cache
T2 - IEICE TRANSACTIONS on Communications
SP - 1664
EP - 1673
AU - Masanori UGA
AU - Kohei SHIOMOTO
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E84-B
IS - 6
JA - IEICE TRANSACTIONS on Communications
Y1 - June 2001
AB - We propose a fast and compact longest match table look-up method for very long network addresses like IP version 6. This method uses two ideas for a routing-table arranged in a tree-structure. The first idea is to make table look-up fast by caching pointers to intermediate nodes in the tree, reducing the number of node traversals. The second idea is to reduce the memory size required for each node in the tree by one-third by eliminating common parts of addresses of adjacent nodes. Evaluating the performance of this method by using actual routing table data of an IP backbone network, we found it was five to ten times faster than a conventional method.
ER -