Fast trie-based routing lookup with tiny searchable core

被引:0
作者
Wang, PC [1 ]
Chan, CT [1 ]
Tseng, WC [1 ]
Chen, YC [1 ]
机构
[1] Chunghwa Telecom Co Ltd, Telecommun Labs, Taipei, Taiwan
来源
GLOBECOM'02: IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, VOLS 1-3, CONFERENCE RECORDS: THE WORLD CONVERGES | 2002年
关键词
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We present a novel solution to the problem of best matching prefix (BMP) which is required in the IP routing lookup. Our approach is based on the trie-based algorithm. The idea is to prune the trie so that the main-searchable portion of the trie can be fit into the small on-chip SRAM. The algorithm consists of two parts: Level Smart-Compression Trie and Trie Pruning. In the first part, we presents the new trie-based algorithm which can provide flexibility, storage efficiency and incremental update. Moreover, the fix-size data structure eliminates the complexity of the memory management. Secondly, we define the "core" and present how to apply the concept "trie pruning" to achieve fast IP routing lookup. With the currently popular platform, the proposed scheme can provide 40 MPPS without any assumption. While considering route flaps, the performance will degrade by only 0.01% with 4,000 BGP updates per 30 seconds.
引用
收藏
页码:2328 / 2332
页数:5
相关论文
共 14 条
[1]  
[Anonymous], 1993, 1518 RFC
[2]  
CHIUEH T, 1999, P IEEE INF 99 NEW YO
[3]  
DAVIS B, 2000, 3 INT S HIGH PERF CO, P26
[4]  
DEGERMARK M, 1997, P ACM SIGCOMM, P3
[5]  
GUPTA P, 1998, P IEEE INF 98 SAN FR
[6]  
Huang ZL, 1999, J RARE EARTH, V17, P6
[7]   Issues and trends in router design [J].
Keshav, S ;
Sharma, R .
IEEE COMMUNICATIONS MAGAZINE, 1998, 36 (05) :144-151
[8]  
LABOVITZ C, 1997, P ACM SIGCOMM 97, P115
[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]  
*MER NETW INC, INT PERF MEAS AN IPM