计算机工程

• 移动互联与通信技术 • 上一篇    下一篇

命名数据网络中基于Hash映射的命名检索

张 良,刘敬浩,李 卓   

  1. (天津大学电子信息工程学院,天津 300072)
  • 收稿日期:2013-02-20 出版日期:2014-04-15 发布日期:2014-04-14
  • 作者简介:张 良(1987-),男,硕士研究生,主研方向:下一代互联网,网络安全;刘敬浩,副教授;李 卓,博士研究生。

Named Retrieval Based on Hash Mapping for Named Data Network

ZHANG Liang, LIU Jing-hao, LI Zhuo   

  1. (School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China)
  • Received:2013-02-20 Online:2014-04-15 Published:2014-04-14

摘要: 命名数据网络(NDN)是一种以内容为中心的新型网络架构,可有效提高网络资源的共享利用率。但与传统的IPv4、IPv6相比,NDN命名的长度更长且具有可变性,因此实现NDN中命名的快速检索对提高网络性能具有重要作用。为此,提出一种基于Hash映射的分治命名检索方法,将命名分解为组件并进行CRC32映射后分别存储在相应的Hash表中,对Hash表中的数据进行快速排序后使用二分查找定位Hash值,并利用排序后Hash表的递增数据结构进行Hash冲突的快速检测,通过对Hash值添加标志位的方法解决冲突问题。实验结果表明,相比建立命名前缀树的检索方法,该分治命名检索方法可将NDN命名的存储空间压缩近65%,并且大幅提升了检索速度。

关键词: 命名检索, 命名数据网络, 前缀匹配, Hash映射, Hash冲突检测, 最长匹配原则

Abstract: Named Data Network(NDN) is a kind of content centered network architecture, which is effectively improved sharing utilization rate of network resource. But name of NDN is much longer than the traditional IPv4’s and IPv6’s and its length is variable. Thus it is important to implement fast named retrieval of NDN, and it has great significance to further improve network performance. Aiming at the problem, this paper presents a division named retrieval method based on Hash mapping. Names are decomposed into components and computed CRC32 Hash values which are stored in corresponding tables. After the values in Hash tables are quickly sorted, they can be located by binary search. And it is benefit to fast detect Hash collisions in the table, because of the tables with increasing data structure. And it uses Hash value added marker bits to solve the problem of Hash collisions. Experimental results show that the division named retrieval method improves the storage compression rate by about 65% and significantly improves the retrieval speed compared with retrieval method of establishing Name Prefix Tree(NPT).

Key words: named retrieval, Named Data Network(NDN), prefix matching, Hash mapping, Hash collision detection, the longest matching principle

中图分类号: