基于无标度网络的紧凑路由策略研究

发布时间：2017-05-14 05:04

  本文关键词：基于无标度网络的紧凑路由策略研究，由笔耕文化传播整理发布。

【摘要】：路由是Internet网络的基本功能。随着Internet网络规模的增长,节点路由表规模急剧膨胀,致使传统最短路径路由系统的扩展性面临着严峻的挑战。紧凑路由通过适当增加路径长度,从而大幅降低路由表的规模,很好地保证了Internet路由系统的扩展性。 紧凑路由分为通用的紧凑路由和专用的紧凑路由。通用的紧凑路由适合于任意网络,专用的紧凑路由利用了特定网络的拓扑特性,在该拓扑类型的网络上取得了比通用紧凑路由更好的路由性能。而Internet网络是无标度网络,具有明显的幂率分布、小世界等特性。因此,本文主要对无标度网络下专用的紧凑路由进行了一系列的研究工作,具体的研究工作如下： 1.研究无标度网络下地标节点的覆盖面对Thorup-Zwick(TZ)紧凑路由策略的影响。在无标度网络下,系统分析了地标节点的覆盖面与平均伸长系数、平均路由表的关系,并通过设置阈值来约束地标节点的最小覆盖面,提出了基于地标节点覆盖面的紧凑路由算法,同时在Internet AS图上进行仿真实验。研究结果表明,随着地标节点最小覆盖面的增大,平均伸长系数先减小而后逐渐增加,平均路由表先减小而后保持不变；阂值的选取与实际网络模型有关,当选取一个合适的阈值时,基于地标节点覆盖面的紧凑路由算法比原始的TZ算法有更小的平均伸长系数和平均路由表。 2.研究基于无标度网络的名字无关的紧凑路由策略。在连续10年的Internet AS图上,深入分析了基于TZ策略和基于Carmi-Cohen(CC)策略的名字无关的NIHDLR(Name-Independent Highes-Degree Landmark Routing)紧凑路由算法的性能,并通过仿真实验对两算法做了系统地分析与比较。具体表现如下：基于CC策略的NIHDLR算法与基于TZ策略的NIHDLR算法取得了近乎一致的路由性能,其中,基于CC策略的NIHDLR算法有略微偏小的平均伸长系数,但其平均路由表略微偏大。对于引入握手机制可以优化路由性能,实验结果表明,当未引入握手机制时,两算法的平均伸长系数都在1.5上下波动,且都随网络的规模增加有略微的增长趋势；当引入握手机制后,两算法的平均伸长系数都在1.08上下波动,且都随网络的规模增加有略微的递减趋势。
【关键词】：紧凑路由 无标度网络 地标节点 TZ算法 名字无关
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.02
【目录】：

• 摘要5-6
• ABSTRACT6-8
• 目录8-11
• 第1章 绪论11-17
• 1.1 研究背景11-13
• 1.2 国内外研究现状13-15
• 1.3 论文研究内容15
• 1.4 论文结构安排15-17
• 第2章 Internet AS拓扑分析17-29
• 2.1 拓扑特性17-22
• 2.1.1 无标度特性18-19
• 2.1.2 小世界特性19-21
• 2.1.3 富俱乐部特性21
• 2.1.4 异配性21-22
• 2.2 拓扑模型22-25
• 2.2.1 BA模型23-24
• 2.2.2 PLRG模型24
• 2.2.3 GLP模型24-25
• 2.2.4 Tang模型25
• 2.3 k-核分解25-27
• 2.4 拓扑数据来源27
• 2.5 本章小结27-29
• 第3章 紧凑路由策略研究29-39
• 3.1 通用的紧凑路由策略30-35
• 3.1.1 名字有关的紧凑路由30-33
• 3.1.2 名字无关的紧凑路由33-35
• 3.2 专用的紧凑路由策略35-38
• 3.2.1 树模型35-36
• 3.2.2 无标度网络36-37
• 3.2.3 其它拓扑模型37-38
• 3.3 本章小结38-39
• 第4章 基于地标节点覆盖面的TZ紧凑路由研究39-53
• 4.1 TZ紧凑路由算法39-42
• 4.1.1 地标节点和节点邻域40-41
• 4.1.2 路由转发机制41-42
• 4.2 改进的TZ紧凑路由算法42-44
• 4.2.1 地标节点特性分析42-43
• 4.2.2 改进的TZ算法43-44
• 4.3 算法实现44-45
• 4.4 仿真实验45-51
• 4.4.1 地标节点覆盖范围的影响46-49
• 4.4.2 伸长系数49-51
• 4.4.3 路由表大小51
• 4.5 本章小结51-53
• 第5章 名字无关的紧凑路由算法研究53-67
• 5.1 基于TZ策略的NIHDLR算法53-56
• 5.2 基于CC策略的NIHDLR算法56-59
• 5.2.1 CC策略56-58
• 5.2.2 改进的CC策略58-59
• 5.3 算法实现59
• 5.4 仿真实验59-65
• 5.4.1 伸长系数60-64
• 5.4.2 路由表大小64-65
• 5.4.3 消息头大小65
• 5.5 本章小结65-67
• 第6章 总结与展望67-69
• 6.1 总结67
• 6.2 展望67-69
• 参考文献69-73
• 致谢73-75
• 在读期间发表的学术论文与其它成果75

【参考文献】

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

1 唐明董;刘建勋;张国清;;紧凑路由研究[J];计算机科学与探索;2011年03期

2 唐明董;刘建勋;张国清;杨景;;无标度网络上名字无关的紧凑路由研究[J];计算机学报;2014年11期

3 张宇,张宏莉,方滨兴;Internet拓扑建模综述[J];软件学报;2004年08期

4 周苗;杨家海;刘洪波;吴建平;;Internet网络拓扑建模[J];软件学报;2009年01期

5 唐明董;张国清;杨景;张国强;;针对无标度网络的紧凑路由方法[J];软件学报;2010年07期

6 唐明董;张国清;杨景;张国强;;互联网可扩展路由[J];软件学报;2010年10期

7 范涛;刘勇;蔡世民;傅忠谦;;基于Internet AS图的紧凑路由算法研究[J];中国科学技术大学学报;2013年01期

  本文关键词：基于无标度网络的紧凑路由策略研究，，由笔耕文化传播整理发布。

本文编号：364304