Binary searches on multiple small trees for IP address lookup

Hyesook Lim, Bomi Lee, Wonjung Kim

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


Rapid growth of internet traffic requires more internet bandwidth and high-speed packet processing in internet routers. IP address lookup in routers is an essential operation that should be performed in real-time for routers where hundreds of million packets arrive per second. In this paper, we propose a new software-based architecture for efficient IP address lookup. In the proposed scheme, a large routing table is divided into multiple balanced trees, and sequential binary searches are performed on those trees, and hence the number of memory accesses depends on the number of routing entries not on the length of routing prefixes. Performance evaluation results show that the proposed architecture requires a single 301.7 KByte SRAM to store about 41000 routing entries, and an address lookup is achieved by 11 memory accesses in average.

Original languageEnglish
Pages (from-to)75-77
Number of pages3
JournalIEEE Communications Letters
Issue number1
StatePublished - Jan 2005

Bibliographical note

Funding Information:
Manuscript received June 28, 2004. The associated editor coordinating the review of this letter and approving it for publication was Prof. Changcheng Huang. This research was supported by the Ministry of Information and Communication (MIC), Korea, under the Chung-Ang University Home Network Research Center (HNRC-ITRC) support program supervised by the Institute of Information Technology Assessment (IITA).


  • Binary search
  • Disjoint prefix
  • Enclosure prefix
  • IP address lookup
  • Multiple balanced trees


Dive into the research topics of 'Binary searches on multiple small trees for IP address lookup'. Together they form a unique fingerprint.

Cite this