Dec 5, 2019 — I. INTRODUCTION. Named Data Networking (NDN) has evolved to be a favorable architecture for the applications of current network scenario.
214 KB – 6 Pages
PAGE – 1 ============
International Journal of Innovative Technology and Exp loring Engineering (IJITEE) ISSN: 2278 – 3075, Volume – 9 Issue – 2S, December 2019 621 Published By: Blue Eyes Intelligence Engineering & Sciences Publication Retrieval Number: B10 97 1292S19 /2019©BEIESP DOI: 10.35940/ijitee. B10 97. 1292S19 Abstract : Named Data Networking (NDN) is afast growing architecture, which is proposed as an alternative to existing IP. NDN allows users to request the data identified by a unique name without any information of the hosting entity. NDN supports in – network caching of contents, multi – path forwardi ng, and data security. In NDN, packet – forwarding decisions are driven by lookup operations on content name of the NDN packets. An NDN node maintains set of routing tables that aid in forwarding decisions. Forwarding the NDN packets depend on lookup of thes e NDN tables and performing Longest Prefix Matching (LPM) against these NDN tables. The NDN names are unbounded and of variable length. These features along with large and dynamic NDN tables pose several challenges that include increased memory requirement and delayed lookup operations. To this end, there is a need for an efficient data structure that support fast lookup operations with low memory overhead. Sev eral lookup techniques are proposed in this direction. Tra versing trie structures would be slow since every level of trie require a memory access. Hash tables incur additional hash computations on names and suffer from collisions. Bloom filters suffer from false positives and do not support deletions. Improving the performance of these structures ca n lead to a better lookup solution. This survey paper explores different lookup structures for NDN networks. Performance is measured with respect to lookup rate and memory efficiency. Keywords: Cache store (CS), Forwarding Information Base (FIB), Longest Pr efix Matching (LPM), Pending Interest Table (PIT). I. INTRODUCTION N amed Data Networking (NDN) has evolved to be a favorable architecture for the applications of current network scenario. At recent tim – server communication model has ev olved into peer – to – peer mode of data sharing. IP facilitates to create a communication network, where packets are recognized by source and destination addresses [11] . There is a substantial rise in user – generated data, with growing demand for applications like YouTube, Bit Torrent, and social networking sites [12] . The IP architecture fails to handle the large data traffic with desired quality of service. Mobility and security is not in – built in Internet but offered as multiple patches, which sometimes may fail. To overcome these shortcom ings of IP architecture, NDN is proposed as a n alternate architecture Revised Manuscript Received on December 05, 2019. * Correspondence Author Swetha B . , Department of Electronics and Communication , RNS I nstitute of T echnology , Bengaluru , India . Ema il: swetab26@gmail.com D r. S . V . Uma, Department of Electronics and Communication , RNS Institute of Technol ogy, Bengaluru , India . Em ail: umakeshav2000@gmail.com where communication takes place by the exchanging Interest and Data packets. NDN leverages in – network caching, support mobility and multicasting, content level security and scalability. NDN names are hierarchical in structure with variable lengths comprising of sequence of delimited components. These characteristics present challenges to the fast lookup operations that rely on longest prefix matching (LPM) of content names. Due to frequent changes in the content distribution, NDN routers need to perform incremental route updates. In addition to this, the need for large table size for FIB implementation call for a careful design of memory efficient lookup str uctures. Several NDN forwarding structures are proposed to meet the need of fast table lookups without increasing the storage requirements. These lookup methods make use of one or more combination of data structures that include hash tables, Bloom filter s, trie structures, bitmaps, and state transition arrays. The paper is arranged into 5 sections. The general idea of NDN naming and packet forwarding architecture are described in section II. Section III describes different NDN lookup data structures. Th e simulation results are presented for different lookup techniques in section IV. We conclude the paper in Section V. II. NDN OVERVIEW This section explains NDN naming, NDN communication and NDN forwarding. A. NDN naming Each NDN packet is assigned a unique application dependent name. Based on the names, NDN packets are forwarded. NDN names are hierarchically structured delimited components. As per NDN design, name is a reversed domain name, e.g. in/icdecs2019/pdf/Conclave.pdf where in/icdecs2019 is reversed domain name of icdecs2019.in, and pdf/Conclave.pdf is the directory path of the content [1]. Hierarchical structure allows name aggregation and longest prefix matching. B. NDN communication To initiate the data exchange, it is required that the consumer would send an Interest packet with the header carrying the desired content name. This name is used by the routers to dispatch the Interest packet in the network. Nodes that contain requested d ata forward the Data packet that contains the desired data and the name. Efficient Lookup Solutions for Named Data Networks Swetha B . , S. V . U ma
PAGE – 2 ============
Efficient Lookup Solutions for Named Data Networks 622 Published By: Blue Eyes Intelligence Engineering & Sciences Publication Retrieval Number: B10 97 1292S19 /2019©BEIESP DOI: 10.35940/ijitee. B10 97. 1292S19 C. NDN Forwarding Architecture NDN forwarding plane is made up of 3 tables for packet forwarding. A copy of previously answered data packets is cached to answer similar requests by Ca che Store (CS). A list of unanswered Interest requests that are forwarded upstream towards the data sources is held in Pending Interest Table (PIT). Forwarding Information Base (FIB) holds the information regarding the name prefixes and their corresponding next hop interfaces. Upon receiving the Interest request, the CS is checked to see if similar entry exists. If available, the Data packet is returned directly. If not found in CS, it looks PIT for an entry with similar Interest packet . If similar entry al ready exists, the requesting interface is appeneded to that PIT entry and rejects the incoming Interest packet . If not, a new PIT entry is created and recordes the requesting interface. Interest packet is dispatched to next hop faces by FIB lookup. When Da ta packet is recieved, it is dispatched to all requesting interfaces. This particular PIT record is erased and caches the data in CS. Fig. 1. shows the data communication at an NDN node. Fig. 1. NDN forwarding process. III. NAME LOOKUP SOLUTION S NDN forwardi ng solutions for high – speed table lookup with challenges of data structures for efficient memory. A. Adaptive prefix Bloom Filter (NLAPB) NLAPB technique is proposed by Wei Quan, et al. which splits the NDN name into B – prefix and T – suffix [2]. Prefixes with a fixed size can be processed by Counting Bloom Filters (CBF). Suffixes with variable sizes can be stored using Trie structures. A hash is used to attach T – suffix Tries to B – prefix. NLAPB data structure is depicted in Fig. 2. B – Prefixes of each length are assigned one filter. The filter size is computed according to the number of prefixes with varied lengths contributed by it.While adding or removing the prefixes, the counters analogous to hash values are incremented or decremented. Also the hash structure mapping prefixes to suffixes is updated. Fig. 2. NLAPB lookup structure. While adding or removing the prefixes, the counters analogous to hash values are incremented or decremented. Also the hash structure mapping prefixes to suffixes is updated. Each suffix tree component maps to one entry of trie. The root of the trie is connected to prefix through hash table. The components are inserted or removed along the trie knowing the root node. During lookup operation, for B – prefix matched by CBFs, the hash ta ble provides the suffix tree position. For short prefixes, the outgoing faces will be returned directly. With the knowledge of root information, the corresponding next hop information is returned. By reducing the number of entries of CBFs, probability of f alse positive rate can be reduced. The lookup processing rate, update rate and false positive rate of NLAPB outperform that of Bloom hash, Hash table and Component trie methods. B. Bloom Filter Assisted Hash Table Huichen Dai, et al. proposed a structure that employs BF with hash table for LPM. It proposes the idea that a unified index can address all 3 tables namely CS, PIT and FIB [1]. This reduces the multiple lookups to only once. BFAST data structure is depicted in Fig. 3. The pointer field of the en try in the index point to the entry of one of CS, PIT or FIB table . The table to which the entry belongs to is indicated by i ts associative type . For prefix insertion, the item is inserted into CBF and then into least loaded hash bucket. While inserting an item, it employs k auxillary CBFs to identify the hash function used to calculate the hash bucket with the smallest counter. Fig. 3. BFAST data structure for NDN forwarding. Major benefits of this structure are better LPM lookup performance, improved sclability and support to high speed incremental updates. BFAST lookup throughput under average workload of 10M FIB reaches 2.33 M/s, obtaining 12.40x, 1.27x, 4.49x speedup over CCNx, NameFilter, and NCE, respectively. C. Name Filte r Name Filter proposed by Yi Wang , et al. suggest the use of two stage Bloom filter [3]. To avoid performance degradation in lookup speed and memory consumption, the hash tables are replaced with Merged Bloom filter.
PAGE – 3 ============
International Journal of Innovative Technology and Exp loring Engineering (IJITEE) ISSN: 2278 – 3075, Volume – 9 Issue – 2S, December 2019 623 Published By: Blue Eyes Intelligence Engineering & Sciences Publication Retrieval Number: B10 97 1292S19 /2019©BEIESP DOI: 10.35940/ijitee. B10 97. 1292S19 Bloom filters are used as identifiers for names to the same outward ports. The N Bloom filters are attached to m forwarding ports, with a bit sequence made up of aggregated m bits in the same position. Each entry in second stage filter stores a bit sequenc e from MSB to LSB. The AND operation on n – bit strings analogous to n hash functions decide the outgoing port. Proposed data structure is depicted in Fig. 4. Advantages of this structure include high lookup performance with reduced memory utilization, bette r scalability and improved update efficiency. Compared to CharacterTrie and BlooomHash, it achieves 17 times and 1.8 times speedup. Fig. 4. Merged Bloom filter. D. Parallel Name lookup (PNL) PNL structure proposed by Yi Wang, et al. builds name pre fix trie (NPT) of component granularity [4]. A name component is represented as an edge of NPT and each node of NPT represents lookup state. The name prefix lookup starts at the root to see if the beginning component equals any of the edges that begin from the root. If it matches, the lookup process shifts from the root to the next level node. This lookup continues until the it reaches one of the leaf nodes or the transfer condition be unsuccessful. Then the lookup The name lookup for NPT is shown in Fig. 5. Fig. 5. NPT structure. Different physical modules are assigned group of states of state hav ing access probability higher than threshold is duplicated. Original and duplicated states are assigned to different physical modules. The PNL structure is shown in Fig. 6. The dotted circles indicate duplicated states. Fig. 6. PNL structure. E. Lookup b ased on Name Component Encoding This structure proposed by Yi Wang, et al. employs a code assignment mechanism where total number of codes are reduced to reduce the bytes used to denote a code [5]. Unique codes are assigned to all components in NPT. Code of the component is set as the ma ximum code plus one, if different codes are assigned to a component. State Transition Arrays (STA) are used to design the Encoded Name Prefix Trie (ENPT) to accelerate longest prefix lookup and compress memory size. There are 3 types of arrays. The transition array which stores state information is indicated by number is denoted by indicator. The free entries are represented b y Manage Array. Code allocation mechanism and ENPT are shown in Fig. 7 and Fig.8 respectively. Fig. 7. Illustration of Code Allocation Mechanism. Fig. 8. State Transition Arrays for Encoded NPT. F. Name lookup using FPGA Yanbiao Li, et al. proposed FPG A based name lookup that employs compact data structure called Hierarchical Aligned Transition arrays (HATA) [6]. Parallelism on FPGA is added by parallel reading of different RAMs. The transitions of the same state, which are in the same level and same le ngth are stored in different transition arrays. Based on the offset value resulting from the source state and input number,the state transition is calculated. The valid transitions are identified by the transitions stored in all ATAs at that position. An i llustration of 4 – stride name trie and corresponding HATA is shown in Fig. 9 and Fig. 10, respectively. Fig. 9. A 4 – stride name trie.
PAGE – 4 ============
Efficient Lookup Solutions for Named Data Networks 624 Published By: Blue Eyes Intelligence Engineering & Sciences Publication Retrieval Number: B10 97 1292S19 /2019©BEIESP DOI: 10.35940/ijitee. B10 97. 1292S19 Fig. 10. HATA corresponding to name trie. G. Name lookup using Iterative Bloom filters (IBFs) Cristina Munoz, et al. p roposed name lookup using IBFs that take advantage of iterative hash functions properties [7]. To reduce the number of elements, I(FIB)F technique splits the standard BF into m number of bit positions. A standard BF is split into d number of IBFs represent ing n elements and m/d bit – positions. The iterated hash outputs that belong to each field of the name serve as input to individual IBFs. Thus, name is inserted in four IBFs using a single hash function. While standard BF requires 4 hashes per element, the IBF technique require only one hash to each of the four Iterated BFs. If the top leaves of names coincide, it reduces the probability of false positives. This technique proposes to map each interface with a separate iterated BF made of IBFs. When an int erest is received, it checks the iterated hash values contained in the name with every possible outgoing interface. The IBFs of every FIB is tested for membership. Fig. 11 compares the standard BF with I(IBF)F considering four different names which employ four IBFs. Fig. 12 shows the forwarding plane at node C. Fig. 11. Comparison of Standard Bloom filter with Iterated Bloom filter. Fig. 12. Interfaces at node C that receives interest through interface 1. H. Split name trie (SNT) Name lookup using split name trie proposed by YunTan, et al. split the existing FIB into two reduced ones to perform longest prefix matching on them separately [8]. By eliminating the redundancies resulting from the similarity in the prefixes, the memory c ost is reduced. Before performing lookup, each name component is hashed to 32 – bit integer. For name lookup, the name need to be hashed to an integer string, and then perform longest prefix matching the NDN table against this integer string. These integers are used as state transitions to construct character trie stored as a Aligned Transition Array. By using all names having length smaller than n , character trie T 1 is constructed. For content names longer than p components, character trie T 2 is constructed after the name is split at the position p . Front prefix (FP) is made of components from 1 to n, and components from n+1 to the end make up Rear prefix (RP). Character trie T 2 is constructed using all RPs. Each RP in T 2 is assigned to a hash table with its associated front prefix as key. It stores FP in its hash table. Experiments prove that SNT generates fewer transitions when split position is chosen to be 2, 3 or 4. SNT technique is illustrated in Fig. 13. Fig. 13. An illustration of Split name trie . I. Optimized Name trie using minASCII encoding ChavooshGhasemi, et al. proposed Name trie using minASCII encoding which demonstrates the idea of NameTrie to overcome the node partitioningexisting in the trie [9]. All pointers of the trie are stored in has h table which eliminates the need of saving the pointers of leaf nodes. The control information of trie structure is encoded using ASCII characters. The lookup structure consists of minASCII name encoding and the NameTrie data structure. The minASCII codes are stored in NameTrie data structure. The NameTrie design is depicted in Fig. 14. Fig. 14. NameTrie design. In NameTrie , a dummy node is used to connect several tries starting with dissimilar characters. Every name is stored as an array of bytes. The set of names in NameTrie is shown in Fig. 15. The name lookup in the NameTrie is shown in Fig. 16. Fig. 15. NameTrie for a set of input names.
PAGE – 5 ============
International Journal of Innovative Technology and Exp loring Engineering (IJITEE) ISSN: 2278 – 3075, Volume – 9 Issue – 2S, December 2019 625 Published By: Blue Eyes Intelligence Engineering & Sciences Publication Retrieval Number: B10 97 1292S19 /2019©BEIESP DOI: 10.35940/ijitee. B10 97. 1292S19 Fig. 16. Name lookup in NameTrie. The characters of NDN name are stored contiguously in an array. Names are stored using Dynamic memory allocation. NameTrie byte of a child nod e. Hash table, EdgeHT stores all edges of NameTrie. The keys of hash table made of
PAGE – 6 ============
Efficient Lookup Solutions for Named Data Networks 626 Published By: Blue Eyes Intelligence Engineering & Sciences Publication Retrieval Number: B10 97 1292S19 /2019©BEIESP DOI: 10.35940/ijitee. B10 97. 1292S19 Author – 1 Photo Author – 2 Photo Fig. 27. NameTrie Lookup Speed Fig. 28. MaPIT false positive rate V. CONCLUSION The implementation of memory efficient high – speed table lookup is the mo st essential feature for the optimized forwarding of the NDN packets. This faces several challenges due to large NDN tables and longer NDN names. Existing lookup solutions in implementing NDN table lookup are discussed and their performances are compared i n this paper. REFERENCES 1. Conference on Computer Communications (INFOCOM). 2. Wei Quan, Changqiao, Jianfeng Guan, Hongke Zhang, and L uigi LETTERS, VOL. 18, NO. 1, JANUARY 2014. 3. Yi Wang, Tian Pan, Zhian Mi, Huichen Dai, Xiaoyu Guo, Ting Zhang, Bin Liu, and Qunfeng Dong, with low memory cost via applying two – Proceedings IEEE INFOCOM. 4. Yi Wang, Huichen ai, Junchen Jiang, Keqiang He, Wei Meng, and Bin Globecom 2011 proceedings. 5. Yi Wang, Keqiang He, Huichen Dai, Wei Meng, Junchen Jiang, Bin Liu, nd IEEE International Conference on Distributed Computing Systems. 6. Yanbiao Li, Dafang Zhang, Xian Yu, Wei Liang, Jing Long, and Hong Liang Wang, Eduardo Solana and 7. in Named 8. th Web Information System and Application Conference. 9. ChavooshGhasemi, Hamed Yousefi, Kang G. Shin, and Beichuan – Efficient Trie structure for Name – based th International Conference on Network Protocols. 10. Zhuo Li, Kaihua Liu, Yang Zhao, and Yongtao Ma MaPIT: An Enhanced Pending Interest Table forNDN wi th Mapping Bloom Filter IEEE COMMUNICATIONS LETTERS, VOL. 18, NO. 11, NOVEMBER 2014 . 11. Lixia Zhang, Alexander Afanasyev, Jeffrey Burke, Van Jacobson, kc claffy, CAIDA, Patrick Crowley, Christos Papadopoulos, Lan Wang, Computer Communication Review. 12. DivyaSaxenaa, VaskarRaychoudhurya, Neeraj Surib, Christian Beckerc, Science review, 2016. AUTHORS PROFILE Swetha B is a resea rch scholar at R.N.S Institute of technology, Bengaluru. She received M.Tech degree in VLSI and Embedded systems, in 2007 from K.L.E Engineering College under V isvesvaraya technological university . She received B.E degree in Electronics and Communication E ngineering, in 2005 from BDT College under KuvempuUniversity.Her research area is Named data networks (NDN). She has a teaching experience of 10 years. Her subjects of interest include Computer networks, Operating systems, Data structures, and Computer arc design methodology for distributed EDS applications using .NET She is currently working on developing efficient algorith ms for NDN table lookups. Dr. S V Uma is working as Associate professor at R.N.S Institute of technology, Bengaluru. She received Ph.D. University, in 2015. She received M.Tech in Digital Communication from BMSCE under Visvesvaraya technological University, in 2002. She received B.E degree in Electronics and Communication Engineering from Malnad College of engineering, in 1996. She has a t eaching experience of 22 years. Her research interests include Communication Networks, Network security, Cryptography, Signal and blishing, Germany. She has authored and co – authored several technical publications in National Conferences, International Conferences and International Journals. – IP protocol for efficient International Journal of Computer Science and Information Security. She has guided more than 50 UG projects and more than 12 PG students for their d currently guiding 5 doctoral students in different areas of Computer Networks.
214 KB – 6 Pages