DocumentCode
2404364
Title
Bit-Shuffled Trie: IP Lookup with Multi-Level Index Tables
Author
Pao, Derek ; Lu, Ziyan ; Poon, Yat Hang
Author_Institution
Electron. Eng. Dept., City Univ. of Hong Kong, Hong Kong, China
fYear
2011
fDate
5-9 June 2011
Firstpage
1
Lastpage
5
Abstract
Simplicity is the major advantage of implementing hardware IP lookup engine using multi-level index tables. However, the memory efficiency of the conventional multi-level indexing approach is relatively low. In this paper we shall show that by restructuring the binary-trie using a method called bit-shuffling, highly efficient index tables to support the IP lookup operation can be built. The proposed method is evaluated using a real-life IPv4 routing table with 321K prefixes. The required lookup tables occupy 0.8MB on-chip memory. The memory cost is about 21 bits per prefix.
Keywords
IP networks; indexing; table lookup; telecommunication network routing; bit-shuffled trie; bit-shuffling method; hardware IP lookup engine; multilevel index tables; multilevel indexing approach; real-life IPv4 routing table; Engines; Hardware; IP networks; Indexes; Memory management; Peer to peer computing; Routing;
fLanguage
English
Publisher
ieee
Conference_Titel
Communications (ICC), 2011 IEEE International Conference on
Conference_Location
Kyoto
ISSN
1550-3607
Print_ISBN
978-1-61284-232-5
Electronic_ISBN
1550-3607
Type
conf
DOI
10.1109/icc.2011.5962429
Filename
5962429
Link To Document