Scalable Multi-Hash Name Lookup Method for Named Data Networking

Dongliang Xu^1,2, Hongli Zhang¹, Yanbin Sun¹,Yufeng Liu³

(1.School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China;2.School of Information Engineering, Shandong University(Weihai), Weihai 264209, China;3.90 Sub Unit, 63851 Troops, the Pelople''s Liberation Army, Baicheng Jilin 137001, China)



Abstract:

A Scalable Multi-Hash (SMH) name lookup method is proposed, which is based on hierarchical name decomposition to aggregate names sharing common prefixes and multiple scalable hash tables to minimize collisions among prefixes. We take the component instead of the entire name as a key in the hash functions. The SMH method achieves lookup speeds of 21.45 and 20.87 Mbps on prefix table with 2 million and 3.6 million names, respectively. The proposed method is the fastest of the four methods considered and requires 61.63 and 89.17 Mb of memory on the prefix tables with 2 million and 3.6 million names, respectively. The required memory is slightly larger than the best method. The scalability of SMH outperforms that of the other two methods.

Key words:  NDN  name lookup  scalable multi-hash  longest prefix match

DOI：10.11916/j.issn.1005-9113.2015.06.009

Clc Number:TP393

Fund: