Optimized Binary-Search-on-Range Architecture for IP Address Lookup 


Vol. 33,  No. 12, pp. 1103-1111, Dec.  2008


PDF
  Abstract

Internet routers forward an incoming packet to an output port toward its final destination through IP address lookup. Since each incoming packet should be forwarded in wire-speed, it is essential to provide the high-speed search performance. In this paper, IP address lookup algorithms using binary search are studied. Most of the binary search algorithms do not provide a balanced search, and hence the required number of memory access is excessive so that the search performance is poor. On the other hand, binary-search-on-range algorithm provides high-speed search performance, but it requires a large amount of memory. This paper shows an optimized binary-search-on-range structure which reduces the memory requirement by deleting unnecessary entries and an entry field. By this optimization, it is shown that the binary-search-on-range can be performed in a routing table with a similar or lesser number of entries than the number of prefixes. Using real backbone routing data, the optimized structure is compared with the original binary-search-on-range algorithm in terms of search performance. The performance comparison with various binary search algorithms is also provided.

  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]

K. H. Park and H. Lim, "Optimized Binary-Search-on-Range Architecture for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 33, no. 12, pp. 1103-1111, 2008. DOI: .

[ACM Style]

Kyong Hye Park and Hyesook Lim. 2008. Optimized Binary-Search-on-Range Architecture for IP Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 33, 12, (2008), 1103-1111. DOI: .

[KICS Style]

Kyong Hye Park and Hyesook Lim, "Optimized Binary-Search-on-Range Architecture for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 33, no. 12, pp. 1103-1111, 12. 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