TY - GEN
T1 - Name prefix matching using bloom filter pre-searching
AU - Lim, Hyesook
AU - Shim, Miran
AU - Lee, Jungwon
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/5/18
Y1 - 2015/5/18
N2 - 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.
AB - 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.
KW - Bloom filter
KW - content centric network
KW - name prefix matching
KW - name prefix trie
UR - http://www.scopus.com/inward/record.url?scp=84936110480&partnerID=8YFLogxK
U2 - 10.1109/ANCS.2015.7110141
DO - 10.1109/ANCS.2015.7110141
M3 - Conference contribution
AN - SCOPUS:84936110480
T3 - ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems
SP - 203
EP - 204
BT - ANCS 2015 - 11th 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 7 May 2015 through 8 May 2015
ER -