Survey and proposal on binary search algorithms for longest prefix match

Hyesook Lim; Nara Lee

doi:10.1109/SURV.2011.061411.00095

Survey and proposal on binary search algorithms for longest prefix match

Hyesook Lim, Nara Lee

Electronic and Electrical Engineering

Research output: Contribution to journal › Article › peer-review

40 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 language	English
Article number	5930300
Pages (from-to)	681-697
Number of pages	17
Journal	IEEE Communications Surveys and Tutorials
Volume	14
Issue number	3
DOIs	https://doi.org/10.1109/SURV.2011.061411.00095
State	Published - 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

Access to Document

10.1109/SURV.2011.061411.00095

Cite this

@article{b4483455f87c46a8be6fcb64882b4e20,

title = "Survey and proposal on binary search algorithms for longest prefix match",

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.",

keywords = "Algorithm, IP address lookup, best matching prefix, binary search, binary trie, longest prefix match",

author = "Hyesook Lim and Nara Lee",

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",

year = "2012",

doi = "10.1109/SURV.2011.061411.00095",

language = "English",

volume = "14",

pages = "681--697",

journal = "IEEE Communications Surveys and Tutorials",

issn = "1553-877X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Survey and proposal on binary search algorithms for longest prefix match

AU - Lim, Hyesook

AU - Lee, Nara

N1 - 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

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Algorithm

KW - IP address lookup

KW - best matching prefix

KW - binary search

KW - binary trie

KW - longest prefix match

UR - http://www.scopus.com/inward/record.url?scp=84864626058&partnerID=8YFLogxK

U2 - 10.1109/SURV.2011.061411.00095

DO - 10.1109/SURV.2011.061411.00095

M3 - Article

AN - SCOPUS:84864626058

SN - 1553-877X

VL - 14

SP - 681

EP - 697

JO - IEEE Communications Surveys and Tutorials

JF - IEEE Communications Surveys and Tutorials

IS - 3

M1 - 5930300

ER -

Survey and proposal on binary search algorithms for longest prefix match

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this