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: hlim@ewha.ac.kr). 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
VL - 14
SP - 681
EP - 697
JO - IEEE Communications Surveys and Tutorials
JF - IEEE Communications Surveys and Tutorials
SN - 1553-877X
IS - 3
M1 - 5930300
ER -