新一代網路架構資料命名網路的出現，將傳統以 IP 位址傳送資料轉變成以命名為基礎的連線方式，讓使用者能夠以描述資料內容的方式獲取自己想要的資料。然而隨著物聯網的出現，將會有更多的資訊以及內容在網路當中流通，但是也因為資料命名網路並沒有統一的命名方式和限制內容長度，因此在物聯網當中的眾多應用結合之下，將會造成每一個名字在路由器當中搜尋所需要的時間會有極大的差異，而這樣的差異會使得每一個使用者必須經過非常不一樣的時間才能夠獲取資料，而產生不公平的現象。因此我們針對路由器當中 FIB 的搜尋提出一個方法 DePT (Dispersed eminent Patricia Trie), 其結合兩種演算法的優點去解決在路由器當中搜尋不公平的現象，這個方法除了能夠使得每一個資料名稱在路由器中能夠更公平的搜尋之外，同時也能夠減少搜尋所花費的時間以增加搜尋速率。最後也因為使用也別於其他研究所提到的 Patricia Trie 作為資料結構，所以也比較節省記憶體空間，進一步的降低硬體上的負擔。

The novel network architecture Named Data Networking (NDN) has been proposed. The way of information transfer will be pass by name content rather than IP address. Users could get the content by directly describe the information. However, with the appearance of Internet of Things (IoT), there will be more information in the network flow. On the other hand, names do not have the same length and content, the lookup time of names in router would be very different. The difference of lookup time may result in that every user will get his data by during very different waiting time. Therefore, the “unfair” situation happened. In order to solve the fairness issue, we propose a method “DePT (Dispersed eminent Patricia Trie)” which based on two basic methods. This proposed method will make each name have about the same lookup time in FIB. Besides, the lookup efficiency will be better and the memory consumption will be lower. It will reduce the burden on the hardware.

REFERENCES

[1] Bengt Ahlgren, Christian Dannewitz, Claudio Imbrenda, Dirk Kutscher and B ̈orje Ohlman, “A Survey of Information-Centric Networking,” IEEE Communications Magazine, July 2012, vol. 50, no. 7, pp.26-36.
[2] Lixia Zhang, Deborah Estrin, and Jeffrey Burke, et al, “Name Data Networking (ndn) Project,” PARC, Palo Alto, CA, Tech. Rep. NDN-0001, October 2010.
[3] M. Amadeo, C. Campolo, et al, “Named Data Networking for IOT: an Architectural Perspective,” European Conference on Networks and Communications (EuCNC), June 2014, pp.1-5.
[4] Ghassan Samara, Wafaa A.H. Al-Salihy, R. SuresS, “Security Analysis of Vehicular Ad Hoc Networks (VANET),” Second International Conference on Network Applications, Protocols and Services, NETAPPS 2010, pp.55-60.
[5] Giulio Grassi, Davide Pesavento, Giovanni Pau, Rama Vuyyuru, Ryuji Wakikawa and Lixia Zhang, “VANET via Named Data Networking,” IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), April 2014, pp.410-415.
[6] Wei You, Bertrand Mathieu, Patrick Truong and Jean-Franc ̧ois Peltier, “DiPIT: a Distributed Bloom-Filter based PIT table for CCN Nodes,” 21st International Conference on Computer Communications and Networks (ICCCN), 2012, pp.1-7.
[7] Yujian Fan, Hongli Zhang, Jiahui Liu and Dongliang Xu, “An Efficient Parallel String Matching Algorithm Based on DFA,” Trustworthy Computing Services, Communications in Computer and Information Science, 2013, vol. 320, pp.349-356.
[8] Won So, Ashok Narayanan, David Oran and Yaogong Wang, “Toward Fast NDN Software Forwarding Lookup Engine based on Hash Tables,” ACM/IEEE Symposium on Architectures for Networking and Communications Systems, October 2012, pp.85-86.
[9] D. Xu, and H. Zhang et al. “A Scalable Multi-Hash Name Lookup Method for Named Data Networking.”
[10] Won So, Ashok Narayanan and David Oran, “Named Data Networking on a Router: Fast and DoS-resistant Forwarding with Hash Tables,” ACM/IEEE Symposium on Architectures for Networking and Communications Systems, October 2013, pp.215-226
[11] Sarang Dharmapurikar, Praveen Krishnamurthy and David E. Taylor, “Longest Prefix Matching using Bloom filters,” IEEE/ACM Transactions on Networking, April 2006, vol. 14, no.2, pp.397-409.
[12] Wei Quan, Changqiao Xu, Jianfeng Guan, Hongke Zhang and Luigi Alfredo Grieco, “Scalable Name Lookup with Adaptive Prefix Bloom Filter for Named Data Networking,” IEEE Communications Letters, January 2014, vol. 18, pp.102-105.
[13] Yi Wang, Tian Pan, Zhian Mi, Huichen Dai, Xiaoyu Guo, Ting Zhang, Bin Liu and Qunfeng Dong, “NameFilter: Achieving fast name lookup with low memory consumption via applying two-stage Bloom Filters,” IEEE INFOCOM, April 2013, pp.95-99.
[14] Zhuo Li, Kaihua Liu, Yang Zhao and Yongtao Ma, “MaPIT: An Enhanced Pending Interest Table for NDN with Mapping Bloom Filter,” IEEE Communications Letters, November 2014, pp.1915-1918.
[15] Ioannis Sourdis, Georgios Stefanakis, Ruben de Smet, and Georgi N. Gaydadjiev, “Range Tries for Scalable Address Lookup,” ACM/IEEE Symposium on Architectures for Networking and Communications Systems, 2009, pp. 143-152.
[16] I. Sourdis, and S. H. Katamaneni, et al. “Longest Prefix Match and Updates in Range Tries,” IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP), September 2001, pp.51-58.
[17] Fu Li, Fuyu Chen, Jianming Wu and Haiyong Xie , “Fast longest prefix name lookup for content-centric network forwarding,” ACM/IEEE Symposium on Architectures for Networking and Communications Systems, 2012, pp.73-74
[18] Yi Wang, Keqiang He, Huichen Dai, Wei Meng, Junchen Jiang, Bin Liu and Yan Chen, “Scalable Name Lookup in NDN using Effective Name Component Encoding,” IEEE 32nd International Conference on Distributed Computing Systems (ICDCS), June 2012, pp.688-697.
[19] Yi Wang, Huichen Dai, Junchen Jiang, Keqiang He, Wei Meng and Bin Liu, “Parallel Name Lookup for Named Data Networking,” IEEE Global Telecommunications Conference (GLOBECOM), December 2011, pp.1-5.
[20] Jun-Ichi Aoe, Katsushi Morimoto and Takashi Sato, “An Efficient Implementation of Trie Structures,” Software: Practice and Experience, September 1992, Vol. 22, Issue 9, pp. 695–721.
[21] Ghada Hany Badr and B. John Oommen, “Self-Adjusting of Ternary Search Tries Using Conditional Rotations and Randomized Heuristics,” The Computer Journal, 2005, vol. 48, pp.200-219.
[22] Sebastian Kniesburges and Christian Scheideler, “Hashed Patricia Trie: Effective Longest Prefix Matching in Peer-to-Peer Systems,” 5th International Workshop WALCOM: Algorithms and Computation, 2011, vol. 6552, pp.170-181.
[23] ndnsim. http://ndnsim.net/2.0/
[24] URLBlacklist. http://urlblacklist.com.
[25] NDNstatus. http://www.arl/wustl.edu/~jdd/ndnstatus/ndn_prefix/tbs_ndnx.html.