An Efficient IP Address Lookup Scheme Using Balanced Binary Search with Minimal Entry and Optimal Prefix Vector
Summary :
Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E94-B No.11 pp.3128-3131
- Publication Date
- 2011/11/01
- Publicized
- Online ISSN
- 1745-1345
- DOI
- 10.1587/transcom.E94.B.3128
- Type of Manuscript
- LETTER
- Category
- Network System
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Hyuntae PARK, Hyejeong HONG, Sungho KANG, "An Efficient IP Address Lookup Scheme Using Balanced Binary Search with Minimal Entry and Optimal Prefix Vector" in IEICE TRANSACTIONS on Communications,
vol. E94-B, no. 11, pp. 3128-3131, November 2011, doi: 10.1587/transcom.E94.B.3128.
Abstract: Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E94.B.3128/_p
Copy
@ARTICLE{e94-b_11_3128,
author={Hyuntae PARK, Hyejeong HONG, Sungho KANG, },
journal={IEICE TRANSACTIONS on Communications},
title={An Efficient IP Address Lookup Scheme Using Balanced Binary Search with Minimal Entry and Optimal Prefix Vector},
year={2011},
volume={E94-B},
number={11},
pages={3128-3131},
abstract={Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.},
keywords={},
doi={10.1587/transcom.E94.B.3128},
ISSN={1745-1345},
month={November},}
Copy
TY - JOUR
TI - An Efficient IP Address Lookup Scheme Using Balanced Binary Search with Minimal Entry and Optimal Prefix Vector
T2 - IEICE TRANSACTIONS on Communications
SP - 3128
EP - 3131
AU - Hyuntae PARK
AU - Hyejeong HONG
AU - Sungho KANG
PY - 2011
DO - 10.1587/transcom.E94.B.3128
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E94-B
IS - 11
JA - IEICE TRANSACTIONS on Communications
Y1 - November 2011
AB - Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.
ER -
English
