A Bitmap-based Approach For Fast Name Lookup In Named Data Networking

In recent years,the rapid developing Internet has been gradually affecting all aspects of daily life.The conventional communication model,say addresses and hosts-based model in TCP/IP,has confronted with various challenges in both performance and scalability,due to its essential limitations.To meet the problem from the traditional Internet in mobility,security and scalability,new networking architecture appeared.Named Data Networking(NDN)is the typical one.it brings a new model which focuses on "what" except "where".The transform of the communication model makes the route forwarding mechanism evolution once more.In IP network,the key of the route forwarding is ip lookup,which based on the destination IP address,and make the longest prefix match in forwarding base.And in NDN forwarding lookup,there are 2 packages and 3 databases.The name lookup not only need longest prefix matching but also need some exactly match and update.The object is not like IP address,it has more complex structure,no limit length data name.So,it is finded in the performance,efficiency and storage update many aspects of scalability,NDN data name lookup are facing more severe challenges.Based on the requirement and related work,the paper use trie,combined with Tree Bitmap and level-based component encoding,which propose a new structure(Bitmap-based Name Trie,BNT)for Name lookup.The experiments on real-world data show that,BNT sacrifices storage space,and improve the speed of lookup and update.Compare with NCE,the lookup time and update time of BNT is only 1%of it.To store a 3 million forwarding base,BNT just need 593.72MB,which is accepted in normal PC.To against crisis from the storage of BNT,which will be space explosion in one node.The paper design a cutting encode-based scheme,optimized the structure of trie node,decrease a number of redundant points.BNT keeps the high efficiency of name lookup and update and upgrades the scalability of storage.In small database,CBNT need space cost only 33%of BNT,and in 10 million database,it just need only 720.84MB,also it has the similar lookup and update time with BNT.