|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
An Efficient IP Address Lookup Scheme Using Balanced Binary Search with Minimal Entry and Optimal Prefix Vector
Hyuntae PARK
Hyejeong HONG
Sungho KANG
Publication
IEICE TRANSACTIONS on Communications Vol.E94-B No.11 pp.3128-3131
Publication Date: 2011/11/01
Online ISSN: 1745-1345
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network System
Keyword:
IP address lookup,
balanced binary search,
minimal entry,
optimal prefix vector,
Full Text: PDF(158.9KB)
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.
|
|
