Binary search on prefix lengths for IP address lookup

Ju Hyoung Mun, Hyesook Lim, Changhoon Yim

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

Address lookup is an essential function in the Internet routers that should be performed in wire-speed. A lot of address lookup algorithms have been widely studied. Among them, we have thoroughly investigated the binary-search-based address lookup algorithms. 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 for internal nodes. This complicated pre-computation makes the composition of the routing table and the incremental update difficult. In this letter, a new IP address lookup scheme based on binary search on prefix lengths is proposed. The performance evaluation results show that the proposed scheme has very good performance in the lookup speed and the scalability.

Original languageEnglish
Pages (from-to)492-494
Number of pages3
JournalIEEE Communications Letters
Volume10
Issue number6
DOIs
StatePublished - Jun 2006

Bibliographical note

Funding Information:
Manuscript received December 23, 2005. The associated editor coordinating the review of this letter and approving it for publication was Prof. Christos Douligeris. This research was supported by the Ministry of Information and Communications, Korea, under a HNRC-ITRC support program supervised by IITA.

Keywords

  • Binary search
  • Binary search on prefix length
  • Binary trie
  • IP address lookup
  • Leaf pushing

Fingerprint

Dive into the research topics of 'Binary search on prefix lengths for IP address lookup'. Together they form a unique fingerprint.

Cite this