Longest First Binary Search on Prefix Length for IP Address Lookup 


Vol. 31,  No. 8, pp. 691-700, Aug.  2006


PDF
  Abstract

Based on the destination IP address of incoming packets, the Internet routers determine next hops and forward packets toward final destinations through IP address lookup. The bandwidth of communication links increases exponentially fast as well as the routing table size grows significant as the number of single host networks attached to the Internet increases. Since packets should be processed at wire-speed, the increased link speed reduces the processing time of a packet in routers, and hence more efficient and fast IP address lookup algorithms and architectures are required in the next generation routers. Most of the previous IP lookup schemes compare routing prefixes of shorter length first with a given input IP address. Since IP address lookup needs to find the most specific route of the given input, search continues until the longest matched prefix is found while it keeps remembering the current best matching prefix. In this paper, based on binary search on prefix length, we proposed a new IP address lookup algorithm which compares longer prefixes first. The proposed scheme is consisted of multiple tries with prefixes on leaves only. The trie composed of the longest prefixes is primarily searched whether there is a match with the given input. This processing is repeated for the trie of the next longer prefixes until there finds a match. Hence the proposed algorithm provides the fast search speed. The proposed algorithm also provides the incremental update of prefixes while the previous binary search on length scheme does not provide the incremental update because of pre-processing requirement. In this paper, we performed extensive simulations and showed the performance comparisons with related 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]

H. N. Chu and H. Lim, "Longest First Binary Search on Prefix Length for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 31, no. 8, pp. 691-700, 2006. DOI: .

[ACM Style]

Ha Neul Chu and Hyesook Lim. 2006. Longest First Binary Search on Prefix Length for IP Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 31, 8, (2006), 691-700. DOI: .

[KICS Style]

Ha Neul Chu and Hyesook Lim, "Longest First Binary Search on Prefix Length for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 31, no. 8, pp. 691-700, 8. 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