Name prefix matching using bloom filter pre-searching

Hyesook Lim, Miran Shim, Jungwon Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

For the successful realization of content-centric network, it is essential to design an efficient forwarding engine that performs high-speed name lookup. This paper proposes the use of a hashing-based name prefix trie and a Bloom filter. In the proposed approach, an off-chip hash table storing the trie is accessed when the Bloom filter States that the node exists in the trie. In accessing the hash table depending on the result of a Bloom filter, we propose two algorithms that have different search strategies. The first algorithm accesses the hash table for every positive result in a Bloom filter, while the second algorithm firstly attempts to determine the longest matching length using Bloom filter queries. The simulation result shows that the proposed approach can provide the output face of each input name, with a single hash table access on average and with two hash table accesses in the worst-case.

Original languageEnglish
Title of host publicationANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages203-204
Number of pages2
ISBN (Electronic)9781467366335
DOIs
StatePublished - 18 May 2015
Event11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015 - Oakland, United States
Duration: 7 May 20158 May 2015

Publication series

NameANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems

Conference

Conference11th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2015
Country/TerritoryUnited States
CityOakland
Period7/05/158/05/15

Keywords

  • Bloom filter
  • content centric network
  • name prefix matching
  • name prefix trie

Fingerprint

Dive into the research topics of 'Name prefix matching using bloom filter pre-searching'. Together they form a unique fingerprint.

Cite this