Bit-shuffled trie : IP lookup with multi-level index tables
Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with host publication) › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | IEEE International Conference on Communications |
| Publication status | Published - 2011 |
Publication series
| Name | |
|---|---|
| ISSN (Print) | 0536-1486 |
Conference
| Title | 2011 IEEE International Conference on Communications, ICC 2011 |
|---|---|
| Place | Japan |
| City | Kyoto |
| Period | 5 - 9 June 2011 |
Link(s)
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. © 2011 IEEE.
Research Area(s)
- IP lookup, packet forwarding, pipelined architecture
Citation Format(s)
Bit-shuffled trie: IP lookup with multi-level index tables. / Pao, Derek; Lu, Ziyan; Poon, Yat Hang.
IEEE International Conference on Communications. 2011. 5962429.
IEEE International Conference on Communications. 2011. 5962429.
Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with host publication) › peer-review
