NDN中快速的贪婪名称查找策略  

Fast greedy name lookup strategy for NDN

作　　者：杨晓非[1] 牛翠翠[1] 丁志鹏[1] 张宏宇[1] 

机构地区：[1]重庆邮电大学通信与信息工程学院光纤通信技术重点实验室,重庆400065

出　　处：《计算机工程与应用》2016年第11期44-49,共6页Computer Engineering and Applications

基　　金：国家重点基础研究发展规划(973)(No.2012CB315803)

摘　　要：针对当前基于Trie的变长层次化且可以无限长度的命名的数据网络(Named Data Networking,NDN)内容名称的最长前缀匹配查找策略存在复杂性高、查找速率低且树型数据结构的更新开销高等问题,导致算法效率低,提出一种快速的贪婪名称查找机制(FGNL)来实现数据包的快速转发。快速的贪婪的组件代码分配机制复杂性较低,容易实现,支持快速更新;组件编码树本质上是一个二维状态转移表,进一步转换成快速的哈希表查找;多哈希表结构创建速度快,且压缩存储空间,能够极大地加快名称查找的速度。实验结果证明,与字符查找树相比FGNL方案减少大约48.71%的内存,与NCE相比节省26.98%的存储空间,且查找速度获得了2倍的加速。评估结果也表明,该方案可以向上扩展来适应名称集潜在的未来增长。Considering that the current Trie-based longest prefix matching search strategy of NDN content names, which are length-variable, hierarchical and unbounded length, has features including the high complexity, the lower lookup rate and the high updating overhead of tree data structure, leading to low efficiency of algorithm, this paper puts forward a Fast and Greedy Name Lookup mechanism（FGNL）to realize the rapidly forwarding of packets. Fast and greed component code allocation mechanism is low complexity, easy to implement and supports rapid update operations. Component encoding Trie is essentially a two-dimensional state transition table, so it can be further transformed into fast hash table lookup. The multi-hash table structure is fast created, compressed in storage space, and can greatly accelerate the name lookup rate. Extensive experiments demonstrate that FGNL mechanism can save approximately 48.71% memory cost compared with TCT, 26.98% compared with NCE and has a two times speedup compared with NCE. Evaluation results also show that this scheme can be extended up to adapt to the potential future growth of the name set.

关 键 词：命名数据网络(NDN) 名称查找 最长前缀匹配 哈希表 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]