Bit-Shuffled Trie: IP Lookup With Multi-Level Index Tables
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, the authors shall show that by restructuring the binary-trie using a method called bit-shuffling, highly efficient index tables can be built to support the IP lookup operation. The proposed method is evaluated using a real-life IPv4 routing table with 321K prefixes. The amortized memory cost of their method is less than 3 bytes per prefix.