Efficient binary search for IP address lookup

Changhoon Yim, Bomi Lee, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

As an essential function in internet routers, address lookup determines overall router performance. The most important performance metric in software-based address lookup is the number of memory accesses since it is directly related to lookup time. This letter proposes an algorithm to perform efficient binary search for IP address lookup. The depth of the proposed binary tree is very dose to the minimum bound, and hence it results in much smaller number of worst case memory accesses compared to previous schemes. The proposed algorithm requires comparably small size of memory, and it can be used for software-based address lookup in practical internet routers.

Original languageEnglish
Pages (from-to)652-654
Number of pages3
JournalIEEE Communications Letters
Volume9
Issue number7
DOIs
StatePublished - Jul 2005

Bibliographical note

Funding Information:
Manuscript received November 16, 2004. The associated editor coordinating the review of this letter and approving it for publication was Prof. Iakovos Venieris. This research was supported by the Ministry of Information and Communications, Korea, under a HNRC-ITRC support program supervised by IITA. C. Yim is with the Department of Internet and Multimedia Engineering, Konkuk University, Seoul, Korea. Bomi Lee is with Digital Media Research Center, MCT Group, LG Electronics, Seoul, Korea. H. Lim is with the Department of Information and Electronics Engineering, Ewha W. University, Seoul, Korea (e-mail: hlim@ewha.ac.kr). Digital Object Identifier 10.1109/LCOMM.2005.07010.

Keywords

  • Address lookup
  • Ancestor
  • Balance degree
  • Binary tree
  • Binary trie
  • Descendant
  • Longest prefix matching

Fingerprint

Dive into the research topics of 'Efficient binary search for IP address lookup'. Together they form a unique fingerprint.

Cite this