IP address lookup using bit-shuffled trie

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

9 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)51-64
Journal / PublicationComputer Communications
Volume47
Online published18 Apr 2014
Publication statusPublished - 1 Jul 2014

Abstract

An algorithmic RAM-based IP address lookup method called bit-shuffled trie is presented. By rearranging the bits of the prefixes, memory efficient index tables can be constructed to support IP address lookup. The address lookup engine can be implemented using pipelined architecture with simple processing logic. The proposed method has superior memory efficiency. The memory cost for a 474 K prefixes IPv4 routing table is only 1.1 MB, and the memory cost for a 215 K 64-bit prefixes IPv6 routing table is about 1.7 MB. The exceptional memory efficiency of the proposed method allows us to implement the IP address lookup engine for both IPv4 and IPv6 on a single FPGA device. Incremental updates to the routing table can be handled efficiently. On average, about 8 memory-write operations to the data structures are required to process an insertion or deletion. © 2014 Elsevier B.V. All rights reserved.

Research Area(s)

  • IPv4 and IPv6 address lookup, Packet forwarding, Pipelined architecture

Citation Format(s)

IP address lookup using bit-shuffled trie. / Pao, Derek; Lu, Ziyan; Poon, Yat Hang.

In: Computer Communications, Vol. 47, 01.07.2014, p. 51-64.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review