Balanced Binary Search Using Prefix Vector for IP Address Lookup 


Vol. 33,  No. 5, pp. 285-295, May  2008


PDF
  Abstract

Internet routers perform packet forwarding which determines a next hop for each incoming packet using the packet's destination IP address. IP address lookup becomes one of the major challenges because it should be performed in wire-speed for every incoming packet under the circumstance of the advancement in link technologies and the growth of the number of the Internet users. Many binary search algorithms have been proposed for fast IP address lookup. However, tree-based binary search algorithms are usually unbalanced, and they do not provide very good search performance. Even for binary search algorithms providing balanced search, they have drawbacks requiring prefix duplication. In this paper, a new binary search algorithm which provides the balanced binary search and the number of its entries is much less than the number of original prefixes. This is possible because of composing the binary search tree only with disjoint prefixes of the prefix set. Each node has a prefix vector that has the prefix nesting information. The number of memory accesses of the proposed algorithm becomes much less than that of prior binary search algorithms, and hence its performance for IP address lookup is considerably improved.

  Statistics
Cumulative Counts from November, 2022
Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


  Cite this article

[IEEE Style]

H. Kim and H. Lim, "Balanced Binary Search Using Prefix Vector for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 33, no. 5, pp. 285-295, 2008. DOI: .

[ACM Style]

Hyeong-gee Kim and Hye-sook Lim. 2008. Balanced Binary Search Using Prefix Vector for IP Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 33, 5, (2008), 285-295. DOI: .

[KICS Style]

Hyeong-gee Kim and Hye-sook Lim, "Balanced Binary Search Using Prefix Vector for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 33, no. 5, pp. 285-295, 5. 2008.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880