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