Binary Search on Tree Levels for IP Address Lookup 


Vol. 31,  No. 2, pp. 71-79, Feb.  2006


PDF
  Abstract

Address lookup is an essential function in the Internet routers, and it determines overall router performance. In this paper, we have thoroughly investigated the binary-search-based address lookup algorithms and proposed a new algorithm based on binary search on prefix lengths. Most of the existing binary search schemes perform binary search on prefix values, and hence the lookup speed is proportional to the length of prefixes or the log function of the number of prefixes. The previous algorithm based on binary search on prefix lengths has superior lookup performance than others. However, the algorithm requires very complicated pre-computation of markers and best matching prefixes in internal nodes since naive binary search is not possible in their scheme. This complicated pre-computation makes the composition of the routing table and incremental update very difficult. By using leaf-pushing, the proposed algorithm in this paper removes the complicated pre-computation of the previous work in performing the binary search on prefix lengths. The performance evaluation results show that the proposed scheme has very good performance in lookup speed compared with previous works.

  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]

J. H. Mun and H. Lim, "Binary Search on Tree Levels for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 31, no. 2, pp. 71-79, 2006. DOI: .

[ACM Style]

Ju Hyoung Mun and Hyesook Lim. 2006. Binary Search on Tree Levels for IP Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 31, 2, (2006), 71-79. DOI: .

[KICS Style]

Ju Hyoung Mun and Hyesook Lim, "Binary Search on Tree Levels for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 31, no. 2, pp. 71-79, 2. 2006.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880