IP address lookup for internet routers using balanced binary search with prefix vector

Hyesook Lim, Hyeong Gee Kim, Changhoon Yim

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.

Original languageEnglish
Pages (from-to)618-621
Number of pages4
JournalIEEE Transactions on Communications
Volume57
Issue number3
DOIs
StatePublished - 2009

Bibliographical note

Funding Information:
Paper approved by T.-S. P. Yum, the Editor for Packet Access and Switching of the IEEE Communications Society. Manuscript received October 25, 2007. This research was supported by the Ministry of Information and Communications under a HNRC-ITRC support program supervised by IITA. H. Lim and H. G. Kim are with the Department of Electronics Engineering, Ewha W. University, Seoul, Korea (e-mail: hlim@ewha.ac.kr). C. Yim is with the Department of Internet and Multimedia Engineering, Konkuk University, Seoul, Korea (e-mail: cyim@konkuk.ac.kr). Digital Object Identifier 10.1109/TCOMM.2009.03.070146

Keywords

  • Binary search tree
  • Binary trie
  • IP address lookup
  • Internet
  • Router

Fingerprint

Dive into the research topics of 'IP address lookup for internet routers using balanced binary search with prefix vector'. Together they form a unique fingerprint.

Cite this