Length Indexed Bloom Filter Based Forwarding in Content Centric Networking
1. On Simulating Bloom Filters in the ndnSIM Open Source Simulator M. Tortelli, G. Piro, L. A. Grieco, G. Boggia 2015 2. NameFilter: Achieving fast name lookup with low memory cost via applying two stage Bloom filters Yi Wang, Tian Pan, Zhian Mi, Huichen Dai, Xiaoyu Guo, Ting Zhang, Bin Liu, Qunfeng Dong 3. Tian Song, Haowei Yuan, Patrick Crowley, and Beichuan Zhang. 2015. Scalable Name Based Packet Forwarding: From Millions to Billions. In Proceedings of the 2nd ACM Conference on Information Centric Networking (ACM ICN '15) ACM, New York, NY, USA, 19 28. DOI: http:/dx.doi.org/10.1145/2810156.2810166 4. Won So, Ashok Narayanan, and David Oran. 2013. Named data networking on a router: fast and dos resistant forwarding with hash tables. In Proceedings of the ninth ACM/IEEE symposium on Architectures for networking and communications systems (ANCS '13) IEEE Press, Piscataway, NJ, USA, 215 226. 5. Caesar: High Speed and Memory Efficient Forwarding Engine for Future Internet Architecture Mehrdad Moradi, Feng Qian, Qiang Xu, Z. Morley, Mao Darrell, Bethea Michael, K. Reiter 6. Fukushima, M. Hasegawa, T. Tagami, A. (2013) Efficient Lookup Scheme for Non aggregatable Name Prefixes and Its Evaluation. IEICE Transactions, 96 B, 2953 2963. References We introduce a Length indexed bloom filter (LIBF) based tree datastructure for efficient Longest prefix match in Named data network forwarding that enables us to find the longest match given the initial length of prefix. Name prefixes are distributed based on number of components into set of bloom filters arranged in binary tree structure. Results show that the LIBF helps in reducing the false positive rate and increasing speed of longest prefix match at the expense of slight increase in memory compared to single bloom filter. Abstract Length Indexed Bloom Filter (LIBF) contains NDN forwarding table name prefixes distributed into set of nodes containing bloom filters based on number of components (length) in each name prefix and arranged in the form of a binary tree. Longest Prefix Match (LPM) in LIBF improves from K to log(K) where K is the maximum number of components in NDN name prefixes. LPM starts with initial length calculated using the frequency distribution of name prefixes at each node. LPM proceeds to right node if the bloom filter in current node contains name prefix of the respective length or else it proceeds to left node. LPM halts if the search reaches either minimum or maximum possible length. Length Indexed Bloom Filter