论文部分内容阅读
路由是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上下波动,且都随网络的规模增加有略微的递减趋势。