Bit-Shuffled Trie: IP Lookup With Multi-Level Index Tables

Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 250.1 KB