Bitmap-based priority-NPT for packet forwarding at named data network

Jihee Seo, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


As a promising future Internet architecture, the named data networking (NDN) technology has recently been widely studied. A Forwarding Information Base (FIB) used in forwarding named packets is composed of a set of name prefixes, each of which consists of multiple variable-length name components. Achieving wire-speed name lookup on an FIB is an essential prerequisite for the successful realization of the NDN. As one of the various data structures for the FIB construction, a name prefix trie (NPT) has an extended structure of a binary trie. Since an FIB can have an excessively large number of name prefixes and the cardinality of components at each trie level is theoretically infinite, the name lookup using an NPT has critical issues in terms of memory usage and lookup performance. In this paper, we propose the use of a priority trie and an encoded bitmap structure for efficient name lookup. The simulation result shows that our proposed algorithm achieves less than 2.5 off-chip memory accesses in average for each name lookup against FIB tables with 10,000 to 600,000 name prefixes.

Original languageEnglish
Pages (from-to)101-112
Number of pages12
JournalComputer Communications
StatePublished - Oct 2018

Bibliographical note

Publisher Copyright:
© 2018 Elsevier B.V.


  • Bitmap
  • Forwarding engine
  • Memory hierarchy
  • Name prefix trie
  • Named data networking


Dive into the research topics of 'Bitmap-based priority-NPT for packet forwarding at named data network'. Together they form a unique fingerprint.

Cite this