Survey and Proposal on Binary Search Algorithms for Longest Prefix Match

被引:26
作者
Lim, Hyesook [1 ]
Lee, Nara [1 ]
机构
[1] Ewha Womans Univ, Dept Elect Engn, Seoul, South Korea
来源
IEEE COMMUNICATIONS SURVEYS AND TUTORIALS | 2012年 / 14卷 / 03期
关键词
Algorithm; IP address lookup; longest prefix match; best matching prefix; binary trie; binary search; IP ADDRESS LOOKUP; EFFICIENT CONSTRUCTION; MEMORY EFFICIENT; MULTIWAY;
D O I
10.1109/SURV.2011.061411.00095
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:681 / 697
页数:17
相关论文
共 40 条
[1]  
[Anonymous], ACM SIGMETRICS
[2]   Next generation routers [J].
Chao, HJ .
PROCEEDINGS OF THE IEEE, 2002, 90 (09) :1518-1558
[3]   Longest prefix matching using bloom filters [J].
Dharmapurikar, S ;
Krishnamurthy, P ;
Taylor, DE .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2006, 14 (02) :397-409
[4]   Tree bitmap: Hardware/software IP lookups with incremental updates [J].
Eatherton, W ;
Varghese, G ;
Dittia, Z .
ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2004, 34 (02) :97-122
[5]   Scalable, memory efficient, high-speed lookup and update algorithms for IP routing [J].
Futamura, N ;
Sangireddy, R ;
Aluru, S ;
Somani, AK .
ICCCN 2003: 12TH INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS, PROCEEDINGS, 2003, :257-263
[6]  
Kim KS, 2003, IEEE SYMP COMP COMMU, P77
[7]   Efficient construction of pipelined multibit-trie router-tables [J].
Kim, Kun Suk ;
Sahni, Sartaj .
IEEE TRANSACTIONS ON COMPUTERS, 2007, 56 (01) :32-43
[8]  
Kurose J. F., 2010, COMPUTER NETOWRKING
[9]   IP lookups using multiway and multicolumn search [J].
Lampson, B ;
Srinivasan, V ;
Varghese, G .
IEEE-ACM TRANSACTIONS ON NETWORKING, 1999, 7 (03) :324-334
[10]   High speed IP address lookup architecture using hashing [J].
Lim, H ;
Seo, JH ;
Jung, YJ .
IEEE COMMUNICATIONS LETTERS, 2003, 7 (10) :502-504