TY - JOUR
T1 - Name prefix matching using bloom filter pre-searching for content centric network
AU - Lee, Jungwon
AU - Shim, Miran
AU - Lim, Hyesook
N1 - Funding Information:
This research was supported by the National Research Foundation of Korea (NRF) , NRF-2014R1A2A1A11051762 and NRF-2015R1A2A1A15054081 . This research was also supported by the Ministry of Science, ICT and Future Planning (MSIP), Korea, under the Information Technology Research Center (ITRC) support program ( IITP-2015-H8501-15-1007 ) supervised by the Institute for Information & communications Technology Promotion (IITP).
Publisher Copyright:
© 2016 Elsevier Ltd. All rights reserved.
PY - 2016/4
Y1 - 2016/4
N2 - As a new networking paradigm for future Internet, content centric networking (CCN) technology provides a contents-oriented communication infrastructure for the rapidly increasing amount of data traffic. For the successful realization of CCN, 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 nodes of the name prefix trie is only accessed when the Bloom filter states that the node under querying exists in the trie. In accessing the node depending on the result of the Bloom filter, we propose two algorithms that have different strategies. The first algorithm accesses the trie node for every positive result of the Bloom filter, while the second algorithm first attempts to determine the longest matching length using Bloom filter queries. Trie nodes are accessed from the possible longest length, and tracked back if there is no match. Simulation results show that the proposed approach can provide the output face of each input name, with a single node access on average and with two node accesses in the worst-case using a reasonable size of a Bloom filter.
AB - As a new networking paradigm for future Internet, content centric networking (CCN) technology provides a contents-oriented communication infrastructure for the rapidly increasing amount of data traffic. For the successful realization of CCN, 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 nodes of the name prefix trie is only accessed when the Bloom filter states that the node under querying exists in the trie. In accessing the node depending on the result of the Bloom filter, we propose two algorithms that have different strategies. The first algorithm accesses the trie node for every positive result of the Bloom filter, while the second algorithm first attempts to determine the longest matching length using Bloom filter queries. Trie nodes are accessed from the possible longest length, and tracked back if there is no match. Simulation results show that the proposed approach can provide the output face of each input name, with a single node access on average and with two node accesses in the worst-case using a reasonable size of a Bloom filter.
KW - Bloom filter
KW - Content centric network
KW - Name prefix matching
KW - Name prefix trie
UR - http://www.scopus.com/inward/record.url?scp=84960094659&partnerID=8YFLogxK
U2 - 10.1016/j.jnca.2016.02.008
DO - 10.1016/j.jnca.2016.02.008
M3 - Article
AN - SCOPUS:84960094659
SN - 1084-8045
VL - 65
SP - 36
EP - 47
JO - Journal of Network and Computer Applications
JF - Journal of Network and Computer Applications
ER -