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 ISBN/ISSN)peer-review

8 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationIEEE International Conference on Communications
Publication statusPublished - 2011

Publication series

Name
ISSN (Print)0536-1486

Conference

Title2011 IEEE International Conference on Communications, ICC 2011
PlaceJapan
CityKyoto
Period5 - 9 June 2011

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.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review