Scalable name lookup in NDN using effective name component encoding

Yi Wang, Keqiang He, Huichen Dai, Wei Meng, Junchen Jiang, Bin Liu*, Yan Chen

*Corresponding author for this work

Research output: Contribution to conferencePaper

103 Scopus citations

Abstract

Name-based route lookup is a key function for Named Data Networking (NDN). The NDN names are hierarchical and have variable and unbounded lengths, which are much longer than IPv4/6 address, making fast name lookup a challenging issue. In this paper, we propose an effective Name Component Encoding (NCE) solution with the following two techniques: (1) A code allocation mechanism is developed to achieve memory-efficient encoding for name components; (2) We apply an improved State Transition Arrays to accelerate the longest name prefix matching and design a fast and incremental update mechanism which satisfies the special requirements of NDN forwarding process, namely to insert, modify, and delete name prefixes frequently. Furthermore, we analyze the memory consumption and time complexity of NCE. Experimental results on a name set containing 3,000,000 names demonstrate that compared with the character trie NCE reduces overall 30% memory. Besides, NCE performs a few millions lookups per second (on an Intel 2.8 GHz CPU), a speedup of over 7 times compared with the character trie. Our evaluation results also show that NCE can scale up to accommodate the potential future growth of the name sets.

Original languageEnglish (US)
Pages688-697
Number of pages10
DOIs
StatePublished - Oct 5 2012
Event32nd IEEE International Conference on Distributed Computing Systems, ICDCS 2012 - Macau, China
Duration: Jun 18 2012Jun 21 2012

Other

Other32nd IEEE International Conference on Distributed Computing Systems, ICDCS 2012
CountryChina
CityMacau
Period6/18/126/21/12

Keywords

  • Name component encoding
  • Name prefix longest matching
  • Named Data Networking

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Scalable name lookup in NDN using effective name component encoding'. Together they form a unique fingerprint.

  • Cite this

    Wang, Y., He, K., Dai, H., Meng, W., Jiang, J., Liu, B., & Chen, Y. (2012). Scalable name lookup in NDN using effective name component encoding. 688-697. Paper presented at 32nd IEEE International Conference on Distributed Computing Systems, ICDCS 2012, Macau, China. https://doi.org/10.1109/ICDCS.2012.35