Survey and proposal on binary search algorithms for longest prefix match

Hyesook Lim, Nara Lee

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

The IP address lookup has been a major challenge for Internet routers. This is accompanied with a background of advances in link bandwidth and rapid growth in Internet traffic and the number of networks. This survey paper explores binary search algorithms as a simple and efficient approach to the IP address lookup problem. Binary search algorithms are categorized as algorithms based on the trie structure, algorithms performing binary search on prefix values, and algorithms performing binary search on prefix lengths. In this paper, algorithms in each category are described in terms of their data structures, routing tables, and performance. Performance is evaluated with respect to pre-defined metrics, such as search speed and memory requirement. Table update, scalability toward large routing data, and the migration to IPv6 are also discussed. Simulation results are shown for real routing data with sizes of 15000 to 227000 prefixes acquired from backbone routers. Suggestions are made for the choice of algorithms depending on the table size, routing data statistics, or implementation flexibility.

Original languageEnglish
Article number5930300
Pages (from-to)681-697
Number of pages17
JournalIEEE Communications Surveys and Tutorials
Volume14
Issue number3
DOIs
StatePublished - 2012

Bibliographical note

Funding Information:
Manuscript received 10 July 2010; revised 14 May 2011. This work was supported by the Mid-Career Researcher Program through NRF grant funded by the MEST (2011-0000232). This work was also supported by the MKE (The Ministry of Knowledge Economy), Korea, under the HNRC-ITRC support program supervised by the NIPA (2011-C1090-1111-0010). H. Lim is with the Ewha Womans University, Seoul, Korea (e-mail: [email protected]). N. Lee is with the Ewha Womans University, Seoul, Korea. Digital Object Identifier 10.1109/SURV.2011.061411.00095

Keywords

  • Algorithm
  • IP address lookup
  • best matching prefix
  • binary search
  • binary trie
  • longest prefix match

Fingerprint

Dive into the research topics of 'Survey and proposal on binary search algorithms for longest prefix match'. Together they form a unique fingerprint.

Cite this