命名数据网络的路由查找算法研究

发布时间：2017-09-10 22:41

  本文关键词：命名数据网络的路由查找算法研究

  更多相关文章： 命名数据网络 路由查找 查找树 布隆过滤器

【摘要】：以IP包交换为核心的互联网结构设计已经流行了数十年,网络之间互联最初的目标是实现硬件资源的共享。然而,随着技术飞速发展和信息的爆炸式增加,信息共享成为了如今的主要需求,硬件共享变得不再那么重要。命名数据网络作为一种全新的网络模式,其目的是为了更好的满足用户快速便捷的访问互联网内容的需求。命名数据网络通过内容名字进行路由查找与转发。与IP网络路由方法相比,名字查找有一些不同的特征。例如可变长度、层次化的名字结构;比IP网络大2~3个数量级的路由表规模;内容频繁的发布删除导致的路由更新。这些特征使得实现快速名字路由查找算法成为一个重大而艰巨的任务。针对这一问题,本课题结合命名数据网络名字的特性,对名字结构及算法进行了改进。本课题先研究了常用的查找树、哈希表、布隆过滤器三种经典结构的名字路由查找算法。针对查找树存储开销太大,哈希表存在碰撞且不满足最长前缀匹配等问题,并结合名字层次结构的特征,本课题设计了一种基于哈希查找树的路由算法。这种方法通过哈希函数将词元组件而不是整个名字散列成哈希值,从而适用于最长前缀匹配。同时每层词元单独设计哈希函数能保证哈希碰撞控制在一个很低的范围内。然后查找树的状态转移不通过词元而是通过哈希值匹配来确定,使得查找效率得到提升。此外哈希值比名字词元将占用更少的存储空间,从而降低了结构的空间开销。同时哈希计算可以预处理,和名字查找处于并行结构。实验结果表明该结构有效的提升了查找树的空间效率并小幅度提升了查找效率。为了进一步解决名字可变长度导致的查找树结构层次过深,查找效率低下的问题。本课题设计了一种词元查找树结合布隆过滤器的组合数据结构。该算法结构充分考虑到命名数据网络名字分层可变长的结构,将一个完整的名字划分为两个较短的部分处理:前一部分是固定长度的查找树段,后一部分是可变长度的布隆过滤器段。并着重讨论了不同的分层对于算法效率的影响,最终得出一个最优的分层划分。对比实验结果表明,该结构在存储开销和查找速度方面均有良好的表现。
【关键词】：命名数据网络 路由查找 查找树 布隆过滤器
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.02
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第1章 绪论9-15
• 1.1 课题背景及研究的目的和意义9-10
• 1.2 国内外研究现状10-13
• 1.3 本文主要研究内容13-14
• 1.4 本文的组织结构14-15
• 第2章 命名数据网络及其路由算法概述15-24
• 2.1 命名数据网络体系结构15-20
• 2.1.1 数据包类型16-18
• 2.1.2 命名与转发机制18-19
• 2.1.3 数据包路由查找过程19-20
• 2.2 路由查找算法20-23
• 2.3 本章小结23-24
• 第3章 基于哈希多叉树的路由查找算法24-32
• 3.1 名字路由表的建立24-25
• 3.2 词元查找树25-26
• 3.3 哈希多叉查找树算法26-31
• 3.3.1 算法结构26-28
• 3.3.2 算法描述28-30
• 3.3.3 算法分析30-31
• 3.4 本章小结31-32
• 第4章 基于组合结构的路由查找算法32-41
• 4.1 问题分析32-33
• 4.2 建立查找树与布隆过滤器组合模型33-37
• 4.2.1 整体框架描述33
• 4.2.2 模型边界的划分33-35
• 4.2.3 并行查找过程35
• 4.2.4 更新方案35-37
• 4.3 模型分析37-40
• 4.4 本章小结40-41
• 第5章 仿真实验与分析41-50
• 5.1 实验平台及流程41-42
• 5.2 哈希多叉树实验分析42-44
• 5.3 组合结构实验分析44-49
• 5.3.1 内存开销44-45
• 5.3.2 分层影响分析45-48
• 5.3.3 总体时延48-49
• 5.4 本章小结49-50
• 结论50-51
• 参考文献51-57
• 致谢57

【相似文献】

中国期刊全文数据库 前10条

1 徐恪,徐明伟,吴建平,吴剑;路由查找算法研究综述[J];软件学报;2002年01期

2 王智强,王振兴,张定心;快速路由查找算法研究[J];计算机应用研究;2004年02期

3 刘英臣;傅光轩;;路由查找技术的分析及研究[J];贵州大学学报(自然科学版);2006年03期

4 郭润伟;;路由查找算法研究与分析[J];科技经济市场;2009年06期

5 朱国胜;余少华;;一种新的二分路由查找方法[J];小型微型计算机系统;2010年09期

6 袁博;汪斌强;王志明;;并行多流水绿色路由查找架构和算法[J];西安电子科技大学学报;2012年02期

7 田园;王萌;缪建军;刘葳;;星上路由查找的设计与分析[J];电子质量;2012年04期

8 徐宇锋,李乐民;快速路由查找算法及其实现[J];通信技术;2001年07期

9 姚兴苗,李乐民,胡光岷;快速路由器的路由查找和流分类算法研究[J];电子科技大学学报;2004年06期

10 周昔平;高德远;樊晓桠;张盛兵;;基于索引和压缩的超高速路由查找及更新算法[J];小型微型计算机系统;2006年06期

中国重要会议论文全文数据库 前3条

1 张荣高;龚雪春;;基于位图映射路由查找算法的研究[A];2006通信理论与技术新进展——第十一届全国青年通信学术会议论文集[C];2006年

2 王燕;;IPv6的快速路由查找算法研究[A];2005年全国开放式分布与并行计算学术会议论文集[C];2005年

3 苗建松;丁炜;;改进的TCAM路由更新方法与实现[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

中国重要报纸全文数据库 前1条

1 吴;神码网络加速多业务融合[N];计算机世界;2006年

中国博士学位论文全文数据库 前6条

1 王振兴;NGI高性能路由器转发处理算法与实现[D];南京理工大学;2004年

2 谭明锋;域间路由协议BGP-4健壮性测试技术的研究[D];国防科学技术大学;2005年

3 郑凯;高性能IP路由查找和分组分类技术的研究[D];清华大学;2006年

4 汪漪;内容中心网络路由查找关键技术研究[D];清华大学;2013年

5 胥小波;新型蜜网体系结构及告警聚类的关键技术研究[D];北京邮电大学;2012年

6 朱国胜;高速分组查找规则匹配算法研究[D];华中科技大学;2010年

中国硕士学位论文全文数据库 前10条

1 张宁;基于Lua的手游服务器的研究与设计[D];南华大学;2015年

2 贺雨虹;命名数据网络的路由查找算法研究[D];哈尔滨工业大学;2015年

3 张理阳;一种基于哈希策略的路由查找算法[D];长沙理工大学;2011年

4 王智强;高速路由查找算法研究[D];中国人民解放军信息工程大学;2003年

5 张荣高;网络处理器原型系统路由查找算法的研究[D];国防科学技术大学;2006年

6 陈静;路由器中路由查找子系统的实现和优化[D];华中科技大学;2006年

7 王波;基于FPGA的快速路由查找算法研究及实现[D];西安电子科技大学;2009年

8 奚晓华;基于FPGA的可编程高速路由查找算法的研究与实现[D];南京邮电大学;2013年

9 张晓波;路由查找算法的研究及其FPGA实现[D];华东师范大学;2006年

10 杨斌涛;IP路由查找算法的研究[D];电子科技大学;2010年

，

本文编号：827102