2023年7月21日发(作者：)

湖南大学硕士学位论文生成Internet自治系统层次拓扑图算法研究与实现姓名：***申请学位级别：硕士专业：计算机软件与理论指导教师：***20060325硕士学位论文摘要随着网络技术的发展和互联网的广泛应用，人们对网络的研究也在逐步的深入。Ｉｎｔｅｒｎｅｔ拓扑图为大范围开发、利用Ｉｎｔｅｒｎｅｔ提供了一个有力的工具。网络研究者可以利用拓扑生成器生成的网络拓扑图进行网络仿真实验，但在目前的研究中，还没有形成统一的参数集来全面评估Ｉｎｔｅｒｎｅｔ拓扑图。因而，研究者只能尽可能使用更多参数来分析和实验，希望能使拓扑图更好的“逼近”实际Ｉｎｔｅｒｎｅｔ拓扑。首先，本文研究和分析了Ｉｎｔｅｒｎｅｔ拓扑研究的现状，对Ｉｎｔｅｒｎｅｔ拓扑研究的意义、方法以及评估参数进行了详细的探讨并对Ｉｎｔｅｒｎｅｔ拓扑研究的历程、成果和难点作了分析，勾画了当前Ｉｎｔｅｒｎｅｔ拓扑研究的概貌。接着，对Ｉｎｔｅｒｎｅｔ拓扑在自治系统级和路由器级两个层次的研究进行分析。分析了Ｉｎｔｅｒａｅｔ自治系统的机理及工作方式，对Ｉｎｔｅｒｎｅｔ自治系统拓扑图的研究现状进行总结，指出Ｉｎｔｅｒｎｅｔ自治系统拓扑图的应用、方法和前景。Ｉｎｔｅｒｎｅｔ自治系统拓扑图在自治系统的层次上刻画Ｉｎｔｅｒｎｅｔ特征，它在当前很多领域有着广泛应用。另一方面，探讨了路由器级拓扑的应用、研究方式并把Ｉｎｔｅｒｎｅｔ自治系统级拓扑图和路由器级拓扑图进行对比分析，总结各自优缺点。然后，深入研究了Ｉｎｔｅｒｎｅｔ自治系统层次拓扑模型，对目前两个比较成熟的层次拓扑模型Ｔｒａｎｓｉｔ－Ｓｔｕｂ模型和Ｔｉｅｒｓ模型从平均结点度、冗余度和平均每跳直径等参数进行对比分析，发现传统自治系统级层次拓扑模型不能很好的反映实际网络的可靠性。最后，本文提出了生成Ｉｎｔｅｒｎｅｔ自治系统拓扑图的Ｃｏｒｅ－Ｔｒｅｅ算法及其改进算法Ｃｏｍｐｌｅｔｅ—Ｗａｘｍａｎ—Ｔｒｅｅ算法，这两个算法把Ｉｎｔｅｒｎｅｔ自治系统拓扑图分为树形拓扑和高层网络。Ｃｏｒｅ—Ｔｒｅｅ算法生成两个层次的自治系统拓扑图，其生成图具有一些Ｉｎｔｅｒｎｅｔ的基本特征，如多层次、自治系统、低平均结点度、主干网络强连通等；生成图的拓扑性质与从实际数据分析的结果比较接近并且与其它层次模型相比具有相似的性质。但是Ｃｏｒｅ－Ｔｒｅｅ拓扑图存在局部网络不稳定以及主干网络重要性不突出的缺点。为了解决上述两个问题，本文接着提出了其改进算法Ｃｏｍｐｌｅｔｅ—Ｗａｘｍａｎ—Ｔｒｅｅ算法，改进算法的生成图突出了主干网络并且把局部网络不稳定性范围缩小，比Ｃｏｒｅ－Ｔｒｅｅ生成图更为合理。关键词；ｌｎｔｅｒｎｅｔ拓扑；自治系统：层次模型；边界网关协议；拓扑生成器生盛：：皂塑墨竺星姿堑盐里兰鎏婴塞量塞翌ＡｂｓｔｒａｃｔＷｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｔｈｅｎｅｔｗｏｒｋｔｅｃｈｎｏｌｏｇｙａｎｄｗｉｄｅａｐｐｌｉｃａｔｉｏｎｏｆＩｎｔｅｒｎｅｔ，ｏｎｐｅｏｐｌｅ’Ｓｒｅｓｅａｒｃｈｐｏｗｅｒｆｕｌｇｅｎｅｒａｔｏｒｓｔｏｏｌｔｏｎｅｔｗｏｒｋｉｓｍｏｒｅａｎｄｍｏｒｅｄｅｅｐｅｎｌｙ．ＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｇｒａｐｈｉｓａｎｄｕｔｉｌｉｚｅＩｎｔｅｒｎｅｔｏｎａａｄｅｖｅｌｏｐｌａｒｇｅｓｃａｌｅ．Ｍａｎｙｔｏｐｏｌｏｇｙｈａｖｅｂｅｅｎｃｒｅａｔｅｄｔｏｍｏｄｅｌｆｉｅｔｗｏｒｋ，ｅｓｐｅｃｉａｌｌｙＩｎｔｅｒｎｅｔ，ｔｏｉｍｐｌｅｍｅｎｔｏｒｓｉｍｕｌａｔｉｏｎｓｂｙｔｈｅｎｅｔｗｏｒｋｒｅｓｅａｒｃｈｅｒ．Ｕｎｔｉｌｎｏｗ，ｅｉｔｈｅｒｎｅｔｗｏｒｋｒｅｓｅａｒｃｈｅｒｐｅｏｐｌｅｗｈｏｒｅｓｅａｒｃｈｓｃｈａｒａｃｔｅｒｉｚｅａｏｎｔｈｅｇｒａｐｈｔｈｅｏｒｙｈａｖｅｎｏｔａｇｒｅｅａｎｏｎａｕｎｉｆｉｅｄｍｅｔｒｉｃｓｓｅｔｔｏｔｏｐｏｌｏｇｙｇｒａｐｈ．Ｔｈｅｒｅｆｏｒｅ，ｉｔｉｓｓｔｉｌｌｏｐｅｎｑｕｅｓｔｉｏｎｆｏｒｒｅｓｅａｒｃｈｅｒｓ．Ｆｉｒｓｔｌｙ，ｔｈｉｓｐａｐｅｒｓｔｕｄｉｅｓｔｈｅｃｕｒｒｅｎｔｓｉｔｕａｔｉｏｎｏｆＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｒｅｓｅａｒｃｈａｎｄａｎａｌｙｚｅｓｔｈｅｍｅａｎｉｎｇｏｆＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｒｅｓｅａｒｃｈ，ｔｈｅｍｅｔｈｏｄｓｈｏｗｔｏｍｏｄｅｌＩｎｔｅｒｎｅｔａｎｄｉｔ’Ｓｅｖａｌｕａｔｉｎｇｐａｒａｍｅｔｅｒｓｄｅｅｐｌｙ．Ｔｈｅｎｄｉｓｃｕｓｓｅｓｔｈｅｃｏｕｒｓｅ，ａｃｈｉｅｖｅｍｅｎｔａｎｄｄｉｆｆｉｃｕｌｔｙｏｆＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｒｅｓｅａｒｃｈ．Ｓｅｃｏｎｄｌｙ，ｔｈｉｓｐａｐｅｒａｎａｌｙｚｅｓＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｒｅｓｅａｒｃｈａｎｄｔｈｅａｕｔｏｎｏｍｙｏｎｂｏｔｈｔｈｅｒｏｕｔｅｒｌｅｖｅｌｓｙｓｔｅｍｌｅｖｅｌ．Ｉｎｔｒｏｄｕｃｅｓａｎｄａｎａｌｙｚｅｓｔｈｅｔｈｅｏｒｙｏｆａｕｔｏｎｏｍｙｓｙｓｔｅｍａｎｄｉｔ’Ｓｗｏｒｋｉｎｇｗａｙｓ，ｓｕｍｍａｒｉｚｅｓｔｈｅｒｅｓｅａｒｃｈｓｉｔｕａｔｉｏｎｏｆＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｇｒａｐｈｏｎｔｈｅａｕｔｏｎｏｍｙｓｙｓｔｅｍｌｅｖｅｌａｔｐｒｅｓｅｎｔ．Ｄｅｓｃｒｉｂｉｎｇｔｈｅａｐｐｌｉｃａｔｉｏｎ，ｍｅｔｈｏｄｓｏｎａｎｄｆｏｒｅｇｒｏｕｎｄｏｆｔｈｅＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｇｒａｐｈＩｎｔｅｒｎｅｔｔｈｅａｕｔｏｎｏｍｙｓｙｓｔｅｍＩｎｔｅｒｎｅｔｏｎｌｅｖｅｌ．Ｔｈｅｏｎａｕｔｏｎｏｍｙｓｙｓｔｅｍｔｏｐｏｌｏｇｙｇｒａｐｈｐｏｒｔｒａｙｓｃｈａｒａｃｔｅｒｔｈｅａｔａｕｔｏｎｏｍｏｕｓｓｙｓｔｅｍｌｅｖｅｌ，ｉｔｈａｓｔｈｅｗｉｄｅｓｐｒｅａｄａｐｐｌｉｃａｔｉｏｎｍａｎｙｄｏｍａｉｎｓｐｒｅｓｅｎｔ．Ｏｎｔｈｅｏｔｈｅｒｈａｎｄ，ｗｅｎｏｔｏｎｌｙｄｉｓｃｕｓｓｔｈｅａｐｐｌｉｃａｔｉｏｎａｎｄｍｅｔｈｏｄｓｏｆｔｈｅｒｏｕｔｅｒｌｅｖｅｌ’Ｓｔｏｐｏｌｏｇｙｂｕｔａｌｓｏｃｏｎｔｒａｓｔｉｔｔｏｔｈｅａｕｔｏｎｏｍｙｓｙｓｔｅｍｌｅｖｅｌ．Ｔｈｅｎｗｅｂｏｔｈｔｈｉｓｔｗｏｌｅｖｅｌｓ．ｓｙｓｔｅｍｌｅｖｅｌａｎｄｓｕｍｍａｒｉｚｅｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｔｏｐｏｌｏｇｙｈｉｅｒａｒｃｈｙｍｏｄｅｌｓｏｆｏｎＴｈｉｒｄｌｙ，ｆｕｒｔｈｅｒｃｏｎｔｒａｓｔｓｓｔｕｄｉｅｓｔｈｅａｕｔｏｎｏｍｙｔｈｅＴｒａｎｓｉｔ－ＳｔｕｂｍｏｄｅｌｔｏｔｈｅＴｉｅｒｓｍｏｄｅｌｗｉｔｈａｖｅｒａｇｅｎｏｄｅ’Ｓｄｅｇｒｅｅｓ，ＳＯｈｏｐ－ｄｉａｍｅｔｅｒａｎｄｎｕｍｂｅｒｏｆｂｉｅｏｎｎｅｃｔｅｄｃｏｍｐｏｎｅｎｔｓａｎｄｏｎ，ｂｏｔｈＴｒａｎｓｉｔ．ＳｔｕｂｆｉｎｄｔｈａｔａｍｏｄｅｌａｎｄＴｉｅｒｓｍｏｄｅｌａｒｅｔｈｅｍｏｓｔｐｏｐｕｌａｒｈｉｅｒａｒｃｈｙｍｏｄｅｌｓａｔｐｒｅｓｅｎｔ．ＷｅｔｒａｄｉｔｉｏｎａｌｍｏｄｅｌｓｆｏｒＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｄｏｎｏｔｓａｔｉｓｆａｃｔｏｒｉｌｙｒｅｆｌｅｃｔｔｈｅｒｅｌｉａｂｉｌｉｔｙｏｆｔｅａｌｎｅｔｗｏｒｋ．Ｌａｓｔｌｙ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓＣｏｒｅ－Ｔｒｅｅａｌｇｏｒｉｔｈｍａｎｄｉｔ’ＳｉｍｐｒｏｖｉｎｇａｌｇｏｒｉｔｈｍＣｏｍｐｌｅｔｅ—Ｗａｘｍａｎ—Ｔｒｅｅａｌｇｏｒｉｔｈｍ，ｂｏｔｈｏｆｔｈｅｍｃａｎｇｅｎｅｒａｔｅＩｎｔｅｒｎｅｔａｕｔｏｎｏｍｙｎｅｔｗｏｒｋａｎｄｔｈｅｔｒｅｅ－ｌｉｋｅｓｙｓｔｅｍｔｏｐｏｌｏｇｙｇｒａｐｈｗｉｔｈｈｉｇｈｅｒｌｅｖｅｌｏｆｔｈｅｃｏｒｅｔｏｐｏｌｏｇｙ．ＴｈｅＣｏｒｅ—ＴｒｅｅａｌｇｏｒｉｔｈｍｇｅｎｅｒａｔｅｓｔｈｅｔｏｐｏｌｏｇｙｇｒａｐｈｏｆａｕｔｏｎｏｍｙｓｙｓｔｅｍⅡｗｉｔｈｔｗｏｌｅｖｅｌｓ．Ｉｔ’ｓｔｏｐｏｌｏｇｙｇｒａｐｈｈａｓｓｏｍｅｅｓｓｅｎｔｉａｌｃｈａｒａｃｔｅｒｏｆＩｎｔｅｒｎｅｔｓｕｃｈａｓｍａｎｙｈｉｅｒａｒｃｈｙｓ，ａｕｔｏｎｏｍｙｓｙｓｔｅｍ，ｌｏｗｅｒａｖｅｒａｇｅｎｏｄｅｄｅｇｒｅｅｓａｎｄｂａｃｋｂｏｎｅｓｔｒｏｎｇｃｏｎｎｅｃｔｉｖｉｔｙ．Ｔｈｅｔｏｐｏｌｏｇｉｃａｌｐｒｏｐｅｒｔｙｏｆｉｔ’Ｓｇｒａｐｈａｒｅｃｏｎｓｉｓｔｅｎｔｗｉｔｈｔｈｅｒｅｓｕｌｔｓｂｙａｎａｌｙｓｅｒｅａｌｄａｔａｓａｎｄｏｔｈｅｒｈｉｅｒａｒｃｈｙｍｏｄｅｌｓｖｅｒｙｗｅｌｌ．ＢｕｔＣｏｒｅ—Ｔｒｅｅｔｏｐｏｌｏｇｙｇｒａｐｈｈａｓｓｏｍｅｄｉｓａｄｖａｎｔａｇｅｓｓｕｃｈａｓｐａｒｔｎｅｔｗｏｒｋｉｎｓｔａｂｉｌｉｔｙａｎｄｔｈｅｂａｃｋｂｏｎｅｎｅｔｗｏｒｋ’Ｓｉｍｐｏｒｔａｎｃｅｉｓｎｏｔｏｕｔｓｔａｎｄｉｎｇ．Ｉｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｅｓｅｔｗｏｐｒｏｂｌｅｍｓ，ｔｈｅｐａｐｅｒｐｒｏｐｏｓｅｓｉｔ’ＳｉｍｐｒｏｖｉｎｇａｌｇｏｒｉｔｈｍＣｏｍｐｌｅｔｅ—Ｗａｘｍａｎ－Ｔｒｅｅａｌｇｏｒｉｔｈｍ，ｔｈｅｃｏｎｓｉｓｔｅｎｔｗｉｔｈｔｈｅｒｅａｌｇｒａｐｈｏｆＣｏｍｐｌｅｔｅ—ｔｈａｎＣｏｒｅ—ＴｒｅｅＷａｘｍａｎ－Ｔｒｅｅａｌｇｏｒｉｔｈｍ．ａｌｇｏｒｉｔｈｍｍｏｒｅＩｎｔｅｒｎｅｔＫｅｙｗｏｒｄｓ：Ｉｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙ；Ａｕｔｏｎｏｍｏｕｓｓｙｓｔｅｍ；Ｈｉｅｒａｒｃｈｙｍｏｄｅｌ；ＢｏｒｄｅｒＧａｔｅｗａｙＰｒｏｔｏｃｏｌ；ｔｏｐｏｌｏｇｙｇｅｎｅｒａｔｏｒＵＩ生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现插图索引图２—１自治系统号码分配趋势………………………………………………１１图２－２自治系统最基本的拓扑图……………………………………………１１图２—３客户和提供者关系图…………………………………………………１３图２—４ＢＧＰ在自治系统间路由数据示意图…………………………………．１５图２—５自治系统路径树与ＢＧＰ链路…………………………………………１６图２－６自治系统级拓扑图和路由器级拓扑图………………………………１７图２—７ＩＰ网络互连示意图…………………………………………………．．１８图２—８带标记的自治系统拓扑图……………………………………………２３图３－１３０个结点的Ｔｉｅｒｓ拓扑图……………………………………………………………２７图３－２１２５个结点的Ｔｉｅｒｓ拓扑图……………………………………………２７图３．３３６０个结点的Ｔｉｅｒｓ拓扑图……………………………………………２８图３．４ＴＳ模型………………………………………………………………．．２８图３－５Ｗａｘｍａｎ、ＴＳ模型和Ｔｉｅｒｓ之间的参数比较…………………………３０图３－６几个模型的链路权值分布……………………………………………．３２图３—７结点度与路径权值的相关系…………………………………………３２图４－１各类自治系统以及各类边……………………………………………３６图４—２Ｃ—Ｔ算法例图…………………………………………………………３８图４－３结点度分布图…………………………………………………………４ｌ图４－４树大小分布图…………………………………………………………４１图４－５树深度分布……………………………………………………………４１图４－６Ｃ－Ｔ算法与其它模型对比……………………………………………．４３图５－１ＣＷＴ算法例图………………………………………………………．．４６图５－２结点度分布图…………………………………………………………４７图５－３树大小分布图…………………………………………………………４８图５－４树深度分布图…………………………………………………………４８图５－５ＣＷＴ算法与与Ｃ—ｒｒ算法及其它模型对比……………………………４９ＩＶ附表索引表３－１ＴＳ模型参数…………………………………………………………．．２９表４－１Ｗａｘｍａｎ参数值………………………………………………………．４０表４－２其它参数值……………………………………………………………４０Ｖ湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：／９珐谚日期：沙薛斗月文日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于１、保密口，在年解密后适用本授权书。２、不保密团。（请在以上相应方框内打“４”）作者签名：日期：渺辟４月≯日导师签名：日期．妒６年簪月／Ｅｔ第｛章绪论随着计算机及遴傣技术的飞遴发展，计算帆网络已经渗透到社会璧活舱各个方瑟，对疆会逐步与经济发震起繁越来莛重簧瓣捧弼，氇傻天稻嚣王髂方式甚至生活方式欲生了巨大的变革。当人们越来越依赖网络时，就会关心如何保持网络良好的运行，如何对网络系统进行优化，如何增强管理者对网络容量的了解和控镧毙力；魏秘及对发糯弼终运霉遨纛审篷瑗戆数藩、擐告敖薄润嚣、剡凝鼓障蔗函并尽快解决网络故障。Ｉｎｔｅｒｎｅｔ作为人蹙社会信息化的标志，融经广泛应用到社会生活的各个方霞，其规模芷以指数速发高速增长，如今Ｉｎｔｅｒｎｅｔ懿“蔼貌”与其原溅ＡＲＰＡＮＥＴ已大稳径纛。菝其蔫魔鹣复杂经，埘潋将Ｉｎｔｅｒｎｅｔ看作一个由诗葬梳稳藏豹“生态系统”。最然Ｉｎｔｅｒｎｅｔ是人类索手建造的，假却没有人能说出这个庞然大物看上去到底怒什么样子，运作得如何。Ｉｎｔｅｒｎｅｔ由自治系统构成，自治系统独特的工终方式、复杂篱程鹭芙系雾自隽鼹毪壤丈莛袭上决定了熬今Ｉｎｔｅｒｎｅｔ豹滚囊窝行为。近年来随着Ｉｎｔｅｒｎｅｔ重要饿的日盏提高和网络构成的日益复杂，人们发现越来越有必要对Ｉｎｔｅｒｎｅｔ整体拓扑结构和自治城的工作情况进行深入的了解、分概，良列予研究Ｉｎｔｅｒｎｅｔ豹发震糕德，优纯嬲终配墨，趣强网络维护耧管理，使Ｉｎｔｅｒｎｅｔ能够健康、快速豹发展。Ｉｎｔｅｒｎｅｔ拓扑建模就是探求猩这个看似混乱的网络之中蕴含着哪挫还不为我们所知的规律。发现Ｉｎｔｅｒｎｅｔ搬孙靛内在机制是认识Ｉｎｔｅｒｎｅｔ的必然过程，蹩在离瑟次主牙发耧瘸Ｉｎｔｅｒｎｅｔ静基疆。然释，Ｉｎｔｅｒｎｅｔ与生摸来魏舅梅经、动态性、发展的非集中性以及其庞大的规模都给拓扑建模带来巨大挑战ｎ，。Ｉｎｔｅｒｎｅｔ拓扑建模至今仍然是一个开放性问题，在计算机网络研究中占有重要地位。基予上述骧霞，辩Ｉｎｔｅｒｎｅｔ壤羚磺究及撵羚圈生或楚箕是塞浚系绫缓楚羚磅究已经成为学术界、众业界所普遍关心的重要闯题之一。ｌ，１Ｉｎｔｅｒｎｅｔ拓扑建模简介２§整纪§０年我苏寒，Ｉｎｔｅｒｎｅｔ在整雾藏灞肉遂速发麓，１９９２年终鸯１００多万台主枫攘入Ｉｎｔｅｒｎｅｔ，１９９６年约有１２８８多万台主机接入Ｉｎｔｅｒｎｅｔ，刹了２００１年约有１０９５７多万台擞机接入Ｉｎｔｅｒｎｅｔ“１。网络的复杂性、业务的多样性和接入的髓机性使其结梭不獗驰交毪，扶阏络安全、潮终管理及阏终磷发备令方覆都越来越需要深入了解Ｉｎｔｅｒｎｅｔ整体的拓羚结构，分拆其结构行为，以提出优化网络配置的合瑕建议。因此探测Ｉｎｔｅｒｎｅｔ拓扑结构成为了目前的一个研究热点。生藏Ｉｎｔｅｒｎｅｔ蠡治系统层次毒嚣羚謦簿法蟹｝究与实蠛Ｉｎｔｅｒｎｅｔ拓扑作为Ｉｎｔｅｒｎｅｔ这个自组织系统的“骨骼”，与流量、协议共阕构成模拟Ｉｎｔｅｒｎｅｔ的３令组成部分，即在拓扑鼹络中结点闻执行协议，形成流簸。Ｉｎｔｅｒｎｅｔ辐籍模羹怒建立Ｉｎｔｅｒｎｅｔ系统横融的萋穑，巍魏焉俸嚣缀豹拓羚建模意义也可以说就是Ｉｎｔｅｒｎｅｔ建模的意义，即作为一种工具，人们用其来对Ｉｎｔｅｒｎｅｔ避｝行分析、预撤、决策或控制。Ｉｎｔｅｒｎｅｔ模型中的拓扑部分刻画的是Ｉｎｔｅｒｎｅｔ在窳器土夔酶锤，爱映一攀争慧薅麓癸，瑟浚萁痤蔫纛都是在夫尺发生震开的。１，１．１Ｉｎｔｅｒｎｅｔ拓扑麓模的应照Ｉｎｔｅｒｎｅｔ蕹羚在建摸努辑、预测淡及警理Ｉｎｔｅｒｎｅｔ等方嚣寿羞耋螫瓣意义，强前对Ｉｎｔｅｒｎｅｔ拓扑模裂的需求主骚来自以下几个方面：（１）许多新应用或实验不适合或糟不能够直接应用于Ｉｎｔｅｒｎｅｔ，其中一些具蠢危害性，妇蟋虫病毒凌大撬模潮络上的馋搔模拟”１；（２）对予一些依赖予麓络据扑鹃协议（磐多掇协议“勺，程其研发酚段，当前Ｉｎｔｅｒｎｅｔ拓扑只能提供～份测试样本，无法对协议进行全面评估，需要提供多个模拟拓扑娣壤来进行实验。同时还可默为仿真模拟Ｉｎｔｅｒｎｅｔ环境、协议设计与评徐夔筷研究蒸穑；为与糖羚结稳穗芙靛算法毪爱羧迸舞餐羲掇貉】；（３）从国家安全角度考虑，需要在线控制的网络行为，如焚国国防高缀研究计划局（ＤＡＲＰＡ）的ＮＭＳ（ｎｅｔｗｏｒｋｍｏｄｅｌｉｎｇａｎｄｓｉｍｕｌａｔｉｏｎ）项目哺】｛（４）进镑宏蕊网终发溪毒矮戳及辏弱惩终警鬓：魏增热裁爨由器、掰终扩客、从宏观层次褥理规划大范围内的网络发展布局以缩小地区间麓距等铷：辆补图可以帮助选掸多镜像服务器的位置、确定连接哪个ＩＳＰ可能获得最小延迟与鼹大有效带宽等ｏ３；（５）为瓣范大囊模潮络攻击、分橱大规模瓣络自动攻击（麴分布式拒绝缀务攻击ＤＤｏＳ）的发起范围、掇制病毒传播范围以及故障隔离等提供研究平台和预警手段，使国家对全网络更舆宏观控制力ｏ“”。蒽瑟富之，嚣囊摹黠Ｉｎｔｅｒｎｅｔ羟矜磅究戆鬟黎怒寒鑫§方嚣豹，蒺骞麓终管理、席用研究也有网络安全替方面的需簧，开展Ｉｎｔｅｒｎｅｔ拓扑研究是具有十分重要的实际意义的。｛。｛。２Ｉｎｔｅｒｎｅｔ舞扑建模豹辑窕方惫Ｉｎｔｅｒｎｅｔ拓扑建模是一项复杂的工作，涉及网络测量、阉论、算法设计、统计学、数据挖掘、可视化以及数学建模等多个研究领域。Ｉｎｔｅｒｎｅｔ拓扑建模研究内容可归缀必３个阀题；（１）粥俺获得一份宠整丽准确静Ｉｎｔｅｒｎｅｔ拓扑数据；（２）如何对］ｎｔｅｒｎｅｔ网络拓扑特征进行描述；２（３）如何构造一幅类似于Ｉｎｔｅｒｎｅｔ的拓扑图。这３个问题分嗣对疲于３个磷究方向，即拓扑绩梅测纛、辐羚特饺发现、拓矜生成器辩发。其中叛羚结构溅豢愚簇矜建禳豹基础；据静特征发现怒拓狰建模的核心：拓扑生成器就是拓扑模型、算法的软件实现ｎ“。ｌ。１．３籁扑建模研究历程Ｉｎｔｅｒｎｅｔ据羚研究经历了跌缝骏缓｛烫刭窖鼹分耩，献擎纯鹣计算飘网络簪｝究到复杂系统特征化研究的过程。在研究早期，由于缺乏真实测量数据支持，拓扑模型都是纂予经验假设建立韵。最晕的Ｉｎｔｅｒｎｅｔ拓扑模型怒Ｗａｘｍａｎ予１９８８年提鸯熬一秘擎嚣蓬撬攘燮一－－Ｗａｘｍａｎ蒺墅“”，这令模壁一豢浍震了缀多年。１９９６年，Ｄｏａｒ掇出了Ｔｉｅｒｓ等级模型姐”，该模型刻阐了Ｉｎｔｅｒｎｅｔ所具有的层次特征。１９９７年，Ｚｅｇｕｒａ等人提出了另一种层次模型一一Ｔｒａｎｓｉｔ～Ｓｔｕｂ模型“”。在已有豹研究成聚中，１９９９冬Ｆａｌｏｕｔｓｏｓ等人发现Ｉｎｔｅｒｎｅｔ拓羚缭梅中存农瓣幂终关系（Ｐｏｗｅｒ－Ｌａｗｓ）占据极为重要的蛾位””。幂律的发现将Ｉｎｔｅｒｎｅｔ拓扑匈一些生物学、社会举中的复杂网络联系起来，使其成为“无尺度（ｓｃａｌｅ—ｆｒｅｅ）”网络的一个实例，谯Ｉｎｔｅｒｎｅｔ拓扑研究与系统学研究之间絮起了一庭桥梁““。２０００年以来，磅究入曼秀发了诲多遵循幂镶豹羟羚生戒舞法“７１２１班及慈翳生裁瓣牡３’“’２“，为Ｉｎｔｅｒｎｅｔ模拟提供了有力的支持。目前，对拓扑模型、生成算法和拓扑生成器含义的界定比较模糊，研究过程枣邀霉将麓强者弱软耱实瑗与专门憨蓰羚生成器拿到一起皋魄较，或糟将生或算法也称为拓扑模型。遗成这一情况的原因是，一些生成算法涉及蓟了Ｉｎｔｅｒｎｅｔ的内在机制。如ＥＳＦｏ”；而一些拓扑生成器又包含了一些Ｉｎｔｅｒｎｅｔ细节特征，如ｎｅｍ口“。蜜舔上，这三嚣是有本质酝剐的：拓扑模型是用数学语言对Ｉｎｔｅｒｎｅｔ宏鼹旅矜特糕进行刻蘑，并不一定簧提出如籍擒造这一特鬣；生成算法怒接连翔傅产生一幅鼹有某个模型特征的拓扑网，不需要软件化；拓扑生成器要寅现依据已有生成算｛焱来产生具搿某些Ｉｎｔｅｒｎｅｔ特征的拓扑图，需要缡程实现，因髓拓扑生残器豹嚣发爨要簸生戏臻痤惩熬羯度鸯鬟羧考惑。１．１．４辆扑模型Ｉｎｔｅｒｎｅｔ拓扑研究通常把Ｉｎｔｅｒｎｅｔ形式化为无向圈Ｇ，Ｇ＝（ｙ，Ｅ），其中Ｖ＝｛ｖｌ蠖Ｇ孛熬一令繁熹｝，Ｅ＝融ｖ）ｔ瓤ｖ∈通‰壤罄接｝，Ｇ震数学茨方法表示秀邻接矩阵Ｍ。设或表承结点ｖ的出度，ｄｖ＝ｌ恤１０，ｖ）∈ＥＩ（说明：ＩＥＩ表承集合Ｅ中元素的数网）。设兀淡示结点出魔频率，兀＝Ｉｖｌｖ∈咀ｄ，＝ｄｒｌ。Ｉｎｔｅｒｎｅｔ拓扑模型可分为嚣类：一类攒述Ｉｎｔｅｒｎｅｔ摄羚特缝：是一类疆逑壤羚特征形成粒褪瑾。１。箍遴Ｉｎｔｅｒｎｅｔ妊朴特征的援鍪对于描述Ｉｎｔｅｒｎｅｔ拓扑特征的模型来说，Ｉｎｔｅｒｎｅｔ拓扑特征的发现，实际生藏Ｉｎｔｅｒｎｅｔ鑫滏系统层次菝翳强箨法臻究与安璇上就是刻询该特征的度擞（ｍｅｔｒｉｃ）以及刻画方式的发现，它包括Ｗａｘｍａｎ模型，Ｔｉｅｒｓ模型，Ｔｒａｎｓｉｔ—Ｓｔｕｂ模型毒曩幂镎等等。一令演于接述Ｉｎｔｅｒｎｅｔ据羚特征戆拓棼模型就怒包含若干融存在的或新发现静度薰，然后根据实际豹Ｉｎｔｅｒｎｅｔ拓扑数据求出这魑度量的值。因此，对这粪模型进行评价需要从两方面入手：一方面，对它所采用媳辐扑数摄进行评价；舅一方殛，对其度量进行详徐。在所窍已经发蕊静Ｉｎｔｅｒｎｅｔ据卦瘦爨中，簸为纂奉豹就是结点密度颏率．￡。其分布怒翔颧一幅拓扑图魑衙与Ｉｎｔｅｒｎｅｔ拓扑相类似的最重要的依据。在研究早期，研究人员或者认为Ｉｎｔｅｒｎｅｔ结点出度是完全随机的（如Ｗａｘｍａｎ模型“町），或者认为结点出度楚歪褒戆（黧Ｔｉｅｒｓ模登“观）。瑟幂镎鹣发瑷蘧爨ＴＩｎｔｅｒｎｅｔ据蛰结稳分予嚣者之间，呈幂率分布““。２．描述拓扑特征形成的机理的Ｉｎｔｅｒｎｅｔ模激攒述掇磐特薤形成援淫懿攘囊龟疆Ｂａｒａｂｄｓｉ与Ａｌｂｅｒｔ挺窭懿ＢＡ爨法汹１耪ＥＳＦ算法以殿～种改进模型ＧＬＰ㈣。遮一类模型燕爱对Ｉｎｔｅｒｎｅｔ幂律形成机理进行探索，由予发现的数据和原始数据有很大的偏麓，幂律本身的正确性融经受到质疑，因聪这类模型对攀律枧理斡掇述还不或熟，所以更多憋是作茺一秘产生幂律拓扑图静生成算法。零文重点磷巍第一类Ｉｎｔｅｒｎｅｔ拓扑模墼。１．２拓扑生成器据羚生成嚣裁是掇棼模型、强羚舞法静软捧实瑗，一个“努熬”强替整成嚣生成的拓扑黼应该具有浆些实际Ｉｎｔｅｒｎｅｔ的特祗，因而拓扑嫩成器的设计应该遵循一定的规薄。经过研究人员不懈的努力，研究者已经研究出一些比较寅用的拓扑生成器，嚣兹比较濂静的耗扑生成器主要有ＢＲＩＴＥ、Ｎｅｍ、Ｉｎｅｔ等等。＇．２．１拓扑生成器规范与要求１．拓扑嫩成器设计目标狂癸叟戏器是拓羚黛残算法戆软终实瑶，冀浚诤鏊瑟霹麴缀爻３点：（１）代表性，即生成的人工拓扑图要能够准确反映实际Ｉｎｔｅｒｎｅｔ稻扑的某些特征，能够谯某些具体特征参数方筒很好的“邋ｉ厦”实际的Ｉｎｔｅｒｎｅｔ以邋台应用予某些方灏熊模拟仿真；（２）惫含性，帮将许多生成模羹龠并在一起，提供一个避雳鹣拓扑生成工其：（３）兼容性，即为网络模拟应用程序（如：ｎｓ－２）以及可视化工具（如ＣＡＩＤＡ的Ｏｔｔｅｒ）掇供接口。２。螽莽燕成器臻熬耍求为了实现上述目标，一个拓扑擞成器一般包括下面３个功能模块：（１）格式转换，由于目前没有统一的拓扑数据文件格式标准，所以拓扑生成器４器具有在备种拓扑测豢数据，拓扑嫩成器输入输出数据以及网络模拟软件输入数撬之间遴掰文终格式转换的功能；（２）籀棼餮生成，这是拓羚生藏器的核心，滁了根据已蠢豹拓扑生成簿法实现图的生成之外，还要求可以依据其他度量来产缴拓扑图；（３）拓扑分析，檄据拓扑生成模块中所采用的度量来对拓扑数据进行统计分辑，绘窭整箴蚕表现溅发蠢戆篷。１．２．２潮有拓扑生成器目前常用的专门拓扑生成器宥下露几种：１。浚惫壤大学麓ＢＲＩＴＥ逶霉羟矜生袋攀对予舆实Ｉｎｔｅｒｎｅｔ拓扑特被更深层次的研究，是Ｙａｌｏｕｔｓｏｓ等人发现了Ｉｎｔｅｒｎｅｔ中的几种Ｐｏｗｅｒ－Ｌａｗｓ特征，这对于研究网络拓扑生成器和真实网络拓签特性产嫩了重要的彩豌。ＢＲＩＴＥ（ＢｏｓｔｏｎｔｏｐｏｌｏｇｙＵｎｉｖｅｒｓｉｔｙｒｅ》ｒｅｓｅｎｔａｔ｛ｖ８Ｉｎｔｅｒｎｅｔｇｅｎｅｒａｔｏｒ）拓扑生成器怒波士顿大学于２００１年拜发的一个邋埔拓扑生成器。在谖模型中，结点均匀的分布在粗糙网格中或者使用临界的Ｐａｒｅｔｏ分布来确定分布谯每个大方掇中的结点数爨。然后嚣搬一定数譬的缝点放到较小蛇格子串。麸１ｌ孬避免了结煮豹璧复安藏强”。它先疆撬酶产生多塞瓣核心结煮，然后把其它结点和边再逐渐的增加进来，新边的生成采用Ｗａｘｍａｎ模粼的概率函数，或者采用优先权遴按方法。该生成器的特点在于“通用”：首先，它实现了Ｗａｘｍａｎ模型寒Ｂ轰冀法，并霉疆惩鑫簇囊下秘鑫窳淘主嚣耱方法生残ＧＴ－ＩＴＭ瑟次攘麓掘棼霾；其次，它为多个网络模拟程序（如；ｎｓ一２，ＳＳＦ，Ｏｍｎｅｔ＋＋，ＪａｖＡＳｉｍ）提供接口，并支持可视化工具Ｏｔｔｅｒ。ＢＲＩＴＥ可以产生路由器级和自治系统级拓扑圈，并可以为连接分黧带宽窝延迟，具有图形羯户接日。２．法溺ＵＬＰＳ大学豹Ｎｅｍ拓矜缀成嚣Ｎｅｍ（ｎｅｔｗｏｒｋｍａｎｉｐｕｌａｔｏｒ）拓扑生成器怒法国ＵＬＰＳ大学（ＵｎｉｖｅｒｓｉｔｙＬｏｕｉＳＰａｓｔｅｕｒｏｆＳｔｒａｓｂｏｕｒｇ）予２００２年开发的。其特点是嶷有通用性，并对拓扑蓬在最短路径长凄弱鳙绩擒方瑟瓣度量遴嚣稳健。Ｎｅｍ实袋了除旱麓３耪算法与ＧＬＰ之外的全部５种拓扑生成算法。Ｎｅｍ将拓乎卜特征分为５擞：树、距离、连通性、结点对最缀路径数以及类别（ｃｌａｓｓ，包括叶上结点数、环上结点数等），可以对这５类特鬣避孬分爨。Ｎｅｍ秀霹终搂羧软舞ｎｓ－２，ＧｌｏＭｏＳｉｍ羁ＯＰＮｅｔ提供接爨，班批处理文本文件作为用户接口“”。３．密歇根大学的Ｉｎｅｔ拓扑生成器Ｉｎｅｔ壤羚生成嚣爨密歇根大学予１９９９～２０００年阙开发瓣一个自治羝绫据羚生成器，裔前眈较薪的怒３．０舨本。’鼓是翮用ｒｏｕｔｅ—ｖｉｅｗｓ．ｏｒｅｇｏｎ—ｉｘ。ｎｅｔ上１９９７年１１月一２０００年２月间大量的ＢＧＰ数据来确定拓扑度量的值，可信度很高。Ｉｎｅｔ生袋Ｉｎｔｅｒｎｅｔ蠡稂暴绫器凌嚣羚髓舞法臻竟与实现采用ＰＬＧＲ算法与优先附赣实现幂律，菔视连通性（矮小结点攒虢）。并针对最太团尺专帮聚类系数散了撬像。Ｉｎｅｔ使蔫镱便，哭翳在鑫令行输入牾蛰匿孛绪患总数翱可㈤。１．３Ｉｎｔｅｒｎｅｔ拓扑模型的评储参数嚣诗籀羚垒琏器黪翳麓不是为了蹙隆塞与Ｉｎｔｅｒｎｅｔ－－攘～释魏溪终搽矜缮穗髑，而是产缴仿真所需甍的具有菜黪Ｉｎｔｅｒｎｅｔ特性的拓扑鞠。判断拓扑生成器是荫能很好的艇映Ｉｎｔｅｒｎｅｔ的性质，就黼要利用一热参数或标凇，那么到臌需要什么梯懿参数蠛拣难来蔽浚］ｎｔｅｒｎｅｔ镎么样熊特锰，壹裂理农侨没毒久鼹强餐这个滴题。辑激，对予参数的选择还没裔形成统一的标准，而廷能赞对Ｉｎｔｅｒｎｅｔ静不同性质采用爆最多的拓扑参数进行比较。下禹鼹警蘸在Ｉｎｔｅｒｎｅｔ拓拎建援孛一些常孀驹译佶参数；ｉ。Ｌａｐｌａｃｉａｎ耪裁攥榘目前在网络模型的研究领域中，人们将拓扑圈的关系以邻接矩阵形试表达，并且考虑连攘矩阵中的墩太特征售，摄多拓扑圈邻接矩阵的激大特征值满足菜秘器霉关系，羧嚣，鬟这些褥莲蓬嚣努琴嚣懿蕹棼辩，羲显褥没鸯太大瓣翅缝；因而现在一般嘲时考虑小的拉普拉斯斑阵的特征慎集台，称之为谱。设Ｇ一（矿，Ｅ）表示一个简单的无向图，瓣中ｒ表示黼中结点的熊食，Ｅ表泳图中边的襞食。令ｌＶ｜＿拜，嘲刮髓，毛表零结熹ｖ懿连蘧庹，那么定义器Ｇ翡控瞽挝簸矩薄舞。１，脊”＝ｖ，且Ｌ簪０三（Ｇ融，ｖ）；一赤，黼胁，榔按时馥冀它（１．１）这也魑计算拉酱挝新矩阵常用的～种方法，爆后得到的披普拉斯谱就是矩砗上（Ｇ）特征戗的集合。”。根据图的特镊馕分柝理论，拉普拉欺谶参数能体现图各个方夏戆毪震，是～个魄簸大跨薤簸集簿蔓野区努链纛诞鬟链耱参数。ｚ．平均路径长度平均路径长度（ＡｖｅｒａｇｅＰａｔｈＬｅｎｇｔｈ）是一个重要的参数，其计算的方法是对鐾孛每一个缝纛，诗算宅爨其德铭纛酶平均最簸路径。平蝣路径长寝就是囊畜缩点路径长度的平均数。假设彝个结赢匏强Ｇ巾任一结点对缸，ｐ）之闷所有可能豹骼径的距离是Ｅ０，ｖ）（如果０，ｖ）连邋）则图Ｇ的平均路径长度。啦）２南毒≯，Ｖ）文献Ｃ３ｌ，３２］详细描述了该参数。６㈣硕士学位论文３．平均离心率平均离心率（ＡｖｅｒａｇｅＥｃｃｅｎｔｒｉｃｉｔｙ）用于评估拓扑图直径。结点离心率即图中与离它最远结点之间的距离珏“，平均离心率就是所有结点离心率的平均数。４．失真率失真率（Ｄｉｓｔｏｒｔｉｏｎ）来源于研究图形的理论。”，但某些研究者将其用于检测拓扑图的性质“”。失真率测量的是一个原始图生成树使原来邻居结点之间的连接改变的程度，它描述了拓扑图与树状图相似的程度。５．最大集团数图Ｇ的集团ｃ就是满足下面条件的结点子集ｃ：ｃ中所有结点都相互连接。拓扑图的最大集团数（ＭａｘｉｍｕｍＣ１ｉｑｕｅＳｉｚｅ）定义为所有集团的最大值。计算图的最大集团是一个ＮＰ问题，但是有许多启发式算法计算它的近似值“”。６．群集参数群集参数（ｃｌｕｓｔｅｒｉｎｇｃｏｅｆｆｉｃｉｅｎｔ）定义为：假设结点ｖ有七个出度，即有七个邻结点，那么这七个结点之间最多可能有丛嬖型条边（＿｜｝个结点的完全图）。Ｚ令Ｃ，表示七个结点之间实际存在的边数占总边数的比例。Ｃ为所有结点ｅ值的平均数。所以Ｃ。反映的是结点ｖ的邻居结点间的连接关系，而Ｃ表示拓扑图中结点间的连接紧密程度。如平均路径长度一样，群集参数已用于研究“ｓｍａｌｌ图ｎ”以及广泛用于评估拓扑图”””。７．连接冗余度一个多连接组件（ｂｉｃｏｎｎｅｃｔｅｄｃｏｍｐｏｎｅｎｔｓ）就是一个同在环状的结点对之间最大边数的集合，它的数量叫做连接冗余度（ｎｕｍｂｅｒｏｆｂｉｃｏｎｎｅｃｔｅｄｃｏｍｐｏｎｅｎｔｓ），ｗｏｒｋｌｄ”这个参数用于测量拓扑图的连接度或边的冗余度。一般来说，参数值越小对应图中结点间的连接越多”“。８．膨胀率膨胀率（ｅｘｐａｎｓｉｏｎ），描述扩散速度。对每个结点计算其在有限跳内可达的结点数量，然后取平均值，再用结点总数来规格化瞳”。９．恢复率恢复率（ｒｅｓｉｌｉｅｎｃｅ），描述备用路径的存在性。将一个连通图划分为近似相等的两个连通图的最小割集大小，反映图对于连接故障的鲁棒性“”。１０．扭曲度扭曲（ｄｉｓｔｏｒｔｉｏｎ），描述一幅图像一橡树的程度。对图啪一棵生成树ＬＧ中相邻两点在Ｔ上距离的平均值就是Ｄ，值，这表示如果把路径限定在Ｔ上，口中相邻两点需要走多少额外的跳数，图缃扭曲值蹴是所有生成树中最小的研值“”。生潢｜ｎｔｅｒｎｅｔ鲁浚系统麓蒎箍羚糍舞法繇巍写实臻１。４Ｉｎｔｅｒｎｅｔ拓扑德模的难淼等研究路线Ｉｎｔｅｒｎｅｔ掇莽磷突楚～疆菲鬻露攘漩性熬王撵，筵兹嚣赣鹣燕簧邋滚寒爨予嚣含方嚣：一是Ｉｎｔｅｒｎｅｔ基襄载复杂经；薅一穷甏莛嫒乏进簿系统骚究豹方法谂。１．原因志一＃Ｉｎｔｅｒｎｅｔ裔身的复杂僚Ｉｎｔｅｒｎｅｔ爨身性质带亭｜乏的阎题主聚集中在按扑测量上，其殿因是：首先，Ｉｎｔｅｒｎｅｔ鬃摸激犬、臻擒笈寐，适禽予鼹域箍熬方法黪技拳赞不一定逡会予广壤舔。其次，Ｉｎｔｅｒｎｅｔ在零艨上其蠢溺态穗，协议版零舞级、设备受薪、耩差穰接入锌；同时Ｉｎｔｅｒｎｅｔ流爨也具有突发饿，不樽像传统的电傣业务流量那样符合Ｐｏｉｓｓｏｎ分露；簿三，ｔｎｔｅｒｎｅｔ零蹇暴露缀强懿器褥性，荬器个糅分莛焱誉潮辩溺露不簿辩门箴疆葬瓣建，熬鸯分熬茂麓建笈特点，不蘑黎ＩＳＰ瑟骞苓黼熬撩撵和麝全策略，靛蕊Ｉｎｔｅｒｎｅｔ拓扑需辫跨越不同的网络和不简的管理域，这焓软取Ｉｎｔｅｒｎｅｔ拓羚傣患带来大爨盼接入隈铡。第四，鞠关熟识匮芝，鄙人们对Ｉｎｔｅｒｎｅｔ辐势缝秘豢蹇了褥甚多，其零震魏韵悫拣＿ｌ亟搜入｛｝】不鼹终鞍多数祷疆弦浚，只辘依瓣探溯学莰。其体表瑗在：拓补缭鞫渤态变纯彩晌测量豹准确佼；Ｉｎｔｅｒｎｅｔ庞大的规模影响了测量数据的宠整性；昴梅性与管理的ｑ｝集中憔增加了测摄的技术滚蔗秘”。戮筵客鼹遥滋，嚣赫熬掰络测薰鼓寒凳法获缮竞熬嚣臻麓戆Ｉｎｔｅｒｎｅｔ舞耱鍪。现有的Ｉｎｔｅｒｎｅｔ拓扑模型都存谯一定的局限性，由此碍ｌ发～系列的问蘧：Ｉｎｔｅｒｎｅｔ强狰中囊懿嚣凝幂簿噶？这个疑阏塞爨嚣蔗：（１）ＱｉａｎＣｈｅｎ镣人缎蠛Ｆａｌｏｕｔｓｏｓ蒋人在发魏器簿辩掰耀熬鑫渗系统繇芬数摇丢失了２０％～５０％鹣黪毽逑撩，与冀窳的黼络拓扑之间存在较大的差异，也就魑说，鞯襻并不能严格地猁磷Ｉｎｔｅｒｎｅｔ拓扑黪｛正瞳“”３；（２）Ｌａｋｈｉｎａ簿人也对幂拣的正确惶掇燃了挑战，搬鲢鑫乡簸掇灏源蔗稻庞丈鹣翳称结煮鞫成懿搽浏嚣鬈｛ｌｊｌ于曩缀骆径藤疆熬终瑟瑟存在采样傣燕（ｓａｍｐｌｉｎｇｂｉａｓｅｓ）。文黎辫斑，浆瘸这种存谯聚释偏觅鹣技零瓣Ｗａｘｍａｎ模型产擞的拓扑圈进行测量，窳狳结果同样会满足幂律”１。另外，Ｉｎｔｅｒｎｅｔ瓣潞态挂毽综缀了接努壤黧巾静态霓索鹣毒螽，嫒褥强矜建穰蕊究不疑仗饺撵遴当麓Ｉｎｔｅｒｎｅｔ瓣表蒙，逐簧发甏葵鸷蔽夔骧韵辍裁。峦楚莓ｌ发了舅一个龌舔：Ｉｎｔｅｒｎｅｔ拓扑中的幂律是如何形成的？对于这个问蹶，ＱｉａｎＣｈｅｎ等人提出，历史拯挣数据不辘支持ＢＡ横燕牵萋于逡逶搜动力学辩Ｉｎｔｅｒｎｅｔ发展掰箨豹镁设，建议麸ＨＯＴ（ｈｉｇｈｌｙｏｐｔｉｍｉｚｅｄｔｏｌｅｒａｎｃｅ）理论孛嚣求答蹇８驰。２．原戳之二：缺芝努法论随着研究的不断深入，人们发现Ｉｎｔｅｒｎｅｔ不仅仪是硬ｌ牛和软件的筛糠累加，露蔻一个巍一宠爨义主滋籍“藜拣拽谢”蕊塑缀缫系缓。Ｉｎｔｅｒｎｅｔ据羚怒万缭瓣（遴避ＵＲＬ逐接》、鲴瓣网络（逶过纯攀爱巍连接）、人舔关系鞠、萃辜学文漱零ｌ掰瓣８硕士学位论文络等具有共同的内在特征一一自相似性，并且认识到对Ｉｎｔｅｒｎｅｔ拓扑缺乏了解并不只是一个计算机科学问题，而是源于缺少一个对复杂网络进行特征化的科学框架““。因此，成功建立Ｉｎｔｅｒｎｅｔ拓扑模型要依赖于科学界在上述领域的共同努力。拓扑建模的研究成果也会促进这一科学框架的形成。３．研究路线综上所述，今后Ｉｎｔｅｒｎｅｔ拓扑建模的研究路线主要包括以下３个方面㈨：（１）通过分析路由协议与协议栈来开发新的拓扑测量技术，提高数据完整性以及路由器多接口合并比例，以求从新数据中发现新特征；（２）将数据挖掘与图论结合起来，从现有数据中发现新特征；（３）借鉴其他复杂网络的研究成果，特别是复杂系统中具有普遍性的原理，以发现Ｉｎｔｅｒｎｅｔ拓扑形成的内在机制。１．５本文工作及结构出于对整体Ｉｎｔｅｒｎｅｔ拓扑结构了解的重要性，目前对Ｉｎｔｅｒｎｅｔ拓扑的研究已经成为了一个重要的课题，然而Ｉｎｔｅｒｎｅｔ拓扑研究应该使用什么样的方法、怎样评估，到现在为止，都还没有形成一个统一的标准。本文通过分析、模拟，试图找到一种低代价生成Ｉｎｔｅｒｎｅｔ自治系统级层次拓扑图的算法。本文共５章，这一章作了一个概述，介绍了Ｉｎｔｅｒｎｅｔ拓扑研究的发展现状及一些相关的评估参数，下～章将详细介绍Ｉｎｔｅｒｎｅｔ自治系统级拓扑研究现状：第３章具体分析对比了当前流行的Ｉｎｔｅｒｎｅｔ自治系统层次型拓扑模型；第４章提出了生成Ｉｎｔｅｒｎｅｔ自治系统拓扑图的Ｃｏｒｅ－Ｔｒｅｅ算法；第５章介绍Ｃｏｒｅ－Ｔｒｅｅ算法的改进算法ｃｏｍｐｌｅｔｅ—ｗａｘｍａｎ—Ｔｒｅｅ算法。９第２章Ｉｎｔｅｒｎｅｔ自治系统拓扑研究现状２．１自治系统２．１．１自治系统概念Ｉｎｔｅｒｎｅｔ是由成千上万的主机和设备通过路由器连接而成。由于历史发展原因和管理上的需要，各种设备并不是毫无规则的连接在一起，而是划分为自治系统（ＡｕｔｏｎｏｍｏｕｓＳｙｓｔｅｍ，ＡＳ）。一般而言，一个自治系统既可以是拥有同一选路策略、在同一技术管理部门下运行的一组路由器的组合，也可以是工作在一起提供内部选路的内部网关协议以及相关设备的汇集，在实际操作中可以把一个ＩＳＰ看作一个自治系统。在外部世界看来，整个自治系统是一个单一的实体。每个自治系统都有一个由因特网登记处或ＩＳＰ分配的识别码（ＡＳＮｕｍｂｅｒ）…１。自治系统是Ｉｎｔｅｒｎｅｔ的组成部分，自治系统拓扑是Ｉｎｔｅｒｅｎｔ网络状况的反应。网络接入前，必须向因特网注册机构申请自治系统号码，填写有关自治系统的基本信息。目前全球共有三个区域注册机构：亚太网络信息中心（ＡＰＮＩＣ）。”；因特网号码美国注册处（ＡＲＩＮ）“”和ＩＰ网络欧美协调中心（ＲＩＰＥ）“”。其中ＡＰＮＩＣ对自治系统的定义是：自治系统是一个连接单个或多个ＩＰ前缀的群组，由一个或更多的网络运营商在单一而且明确定义的路由策略Ｆ运营。每一个自治系统都有一个１６位的自治系统编号来做其标识，所以在Ｉｎｔｅｒｎｅｔ中最多可以存在６５５３６个自治系统“”。在自治系统内部，路由是通过域内路由协议（如ＲＩＰ、ＯＳＰＦ、ＩＳ—ＩＳ等）来管理和调度的；在自治系统之间，通过边界网关协议（ＢｏｒｄｅｒＧａｔｅｗ，ａｙＰｒｏｔｏｃｏｌ，ＢＧＰ）进行交互。２０００年末，通告地址的年增长率是７％，自治系统数量的增长率是５１％，这表明每一个自治系统平均通告更少的地址范围，意味着更多的路由细节被通告到全局网络路由表中，这是值得关心的趋势。２００２年ＡＲＩＮ年报中自治系统号码的申请趋势如图２一ｌ所示“…，自治系统号码的分配速度令人担忧，如果增长趋势不变，１６位的自治系统号很快就会消耗完毕。从上面数据可见，自治系统数日并不是稳定不变的，它一直处于不断的耗完毕。从上面数据可见，自治系统数日并不是稳定不变的，它一直处于不断的变化中。硕士学位论文图２－１自治系统号码分配趋势２．１．２自治系统拓扑概念Ｉｎｔｅｒｅｎｔ自治系统拓扑图是以自治系统为基本单位，分析它们之间的互联关系，拓扑图中所有结点都表示自治系统，边表示自治系统之间的关联关系。有些自治系统结点存在很多关联结点，称之为主干自治系统，它们负责为其它自治系统转发消息；有些自治系统结点的邻接结点比较少，处于网络的边缘，被称为边界结点。研究者发现Ｉｎｔｅｒｎｅｔ中自治系统域（ＡＳ域）拓扑具有两个特性：Ａｓ域具有很高的增长速率。“；Ａｓ域之间的对等连接有一个递增的概率。根据上述两点，研究者很想定量的知道当Ｉｎｔｅｒｎｅｔ不断发展进化的时侯，结点之间是以怎样的方式连接的。在进行自治系统拓扑研究的时候，一方面要探测自治系统之间的无向拓扑图，另一方面还要探明这些由商业契约决定的各个自治系统之间的关系，如图２—２所示：＜Ｄ囊泊系统Ａ８一自治景娩闽的关联关蒜圈２－２自治系统最基本的拓扑图近年来对Ｉｎｔｅｒｎｅｔ拓扑的研究和建模日益增多，特别是自治系统的拓扑研究。目前，Ｉｎｔｅｒｎｅｔ中自治系统拓扑研究还主要是依据ＢＧＰ路由信息进行的，如美国ＮＬＡＮＲ项目中的ＯｒｅｇｏｎＲｏｕｔｅ—ｖｉｅｗｓ，以及ＣＡＩＤＡ项目中的ＪＡＳＰＶＩ等。２０世纪６０年代末，Ｉｎｔｅｒｎｅｔ从仅有四个结点，通过５６Ｋｂ／ｓ电路连接的ＡＲＰＡＮＥＴ开始，到８０年代三层网络结构的ＮＳＦＮＥＴ，直到现在，规模每年至少翻一番，网络生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现结构愈加复杂，难以预料未来的互联网是什么样子““。更值得关心的是现在互联网的基础能否满足未来扩展的需求。换句话说，互联网技术，或者构架，是否存在内在的限制将影响它的不断增长““。为了掌握Ｉｎｔｅｒｎｅｔ整体互联状况，从而为解决上述问题提供依据，网络专家和学者们对Ｉｎｔｅｒｎｅｔ拓扑结构开始了深入的研究Ⅲ３。对Ｉｎｔｅｒｎｅｔ拓扑图的研究可以分为两个抽象层：路由器级拓扑图和自治系统级拓扑图。路由器级拓扑图刻画物理路由器间的连接关系，反映数据实际的流动方向和路径。自治系统拓扑刻画不同自治系统之间的连接关系和路由更新策略，从中可以考察不同网络的连接情况、网络的关键部分，从而为优化网络结构和网络接入提供依据Ｈ“删。２．２自治系统选路协议２．２．１域问路由通过把路由域划分为独立管理的自治系统，为Ｉｎｔｅｒｎｅｔ提供更加结构化的模式。自治系统问通过外部网关协议ＢＧＰ互相沟通。早期的Ｉｎｔｅｒｎｅｔ使用的外部网关协议是ＥＧＰ，尽管使用很广泛，但是它在处理选路循环和设置选路策略时对拓扑结构有限制以及低效率，这就要求一种更先进的协议出现。当前，ＢＧＰ－４是Ｉｎｔｅｒｎｅｔ选路的实际标准，它是一种距离矢量协议，除标准距离矢量属性以外，ＢＧＰ使用了路径向量技术以消除选路循环““。２．２．２域内路由目前大多数大型服务提供商在自治系统内部选路使用链路状态协议，主要是因为它能够快速收敛。这种协议中使用最广泛的是开放式最短路径优先协议（ＯＳＰＦ）和中间系统到中间级系统（ＩＳ—ＩＳ：ＩｎｔｅｒｍｅｄｉａｔｅＳｙｓｔｅｍｔｏＩｎｔｅｒｍｅｄｉａｔｅＳｙｓｔｅｍ）。许多老的服务商选择ＩＳ—Ｉｓ作为内部网关协议（ＩＧＰ），而一些新的提供商选择ＯＳＰＦ或者ＩＳ—ＩＳ。ＩＳ—ＩＳ能够支持无分类网络协议（ＣＬＮＰ）和ＩＰ网络层信息，而ＯＳＰＦ只支持ＩＰ信息。目前Ｉｓ—Ｉｓ和ＯＳＰＦ都在ＩＳＰ网络中广泛使用，其成熟和稳定的特性使它在大型网络中得以快速发展。２．２．３区别自治系统间选路和自治系统内部选路的根本区别在于前者通常反应了网络或者公司间的行政和业务关系，而后者通常根据需要的技术来优化。经过实际调查，当前国内电信各个省网之问与国外出口间配置的都是ＢＧＰ一４协议。各个省网之内，一般配置Ｉｓ—ＩＳ协议，个别网络内部设置ＯＳＰＦ协议，教育网基本使用静态路由”…。当前对Ｉｎｔｅｒｎｅｔ的拓扑研究集中于路由器级和自治系统级，其中路由器级拓扑研究是研究自治域内的路由状况，而自治系统级拓扑图研究的是自治系统之间的相互关系。１２硕士学位论文２．３研究自治系统关系的意义自治系统的相互关系反映的是实际Ｉｎｔｅｒｎｅｔ中的各自治系统之间是以什么方式相关联。根据不同的研究目的和方式对自治系统关系的界定有不同的方法。在露前众多关系界定中，与最实际最接近的是ＬｉｘｉｎＧａｏ从商业及ＩＳＰ的角度的分类，她把Ｉｎｔｅｒｎｅｔ中的自治系统关系分为三类：提供者／客户关系（Ｃｕｓｔｏｍｅｒ／Ｐｒｏｖｉｄｅｒ）、对等关系（Ｐｅｅｒ／Ｐｅｅｒ）和兄弟关系（Ｓｉｂｌｉｎｇ／Ｓｉｂｌｉｎｇ）。２．３．１自治系统关系代表着Ｉｎｔｅｒｎｅｔ结构中最关键的部分１．自治系统之间物理连接不意味着可达自治系统级拓扑和传统路由器级拓扑一个最主要的区别就在于自治系统间的选路协议ＢＧＰ是基于策略的路由协议，管理域间的商业契约关系对Ｉｎｔｅｒｎｅｔ结构和端到端性能特性起关键作用，如果两个相连接的自治系统之间没有签订商业契约，即使它们在物理上是连接的两者之间也没有业务量，无法互相通信“”。例如：三个自治系统Ａ、Ｂ、ｃ连接情况如图２—３所示，其中０，曰），（ｃ，Ｂ）均为提供者一客户关系，众所周知，流量传输方向和付费方向是一致的，虽然在拓扑图中Ａ、Ｂ、Ｃ直接相连，但是Ｂ的本地策略不允许Ｂ在Ａ、Ｃ之间转发服务，所以ＩＳＰＡ不能通过ＩＳＰＣ到达ＩＳＰＢ。图２－３客户和提供者关系图２．仅从自治系统拓扑连接图上无法得出因特网的结构属性自治系统拓扑里面的连接并不意味着实际可达，即使ＩＳＰＡ和ＩＳＰＢ能够通过其它的ＩＳＰ相通，其端到端的性能特性也不能从Ａ、ｃ间和Ｂ、Ｃ间的性能特性推断出来。例如，Ａ、Ｂ间的延迟独立于Ａ、Ｃ间和Ｂ、Ｃ间的延迟的总和。这已经通过几个测量研究得到证实““”１。因而，互连性（无论是路由层还是自治系统层）本身不能完全表示Ｉｎｔｅｒｎｅｔ的结构属性。２．３．２自治系统关系是１种重要的网络资源在Ｉｎｔｅｒｎｅｔ的应用中，自治系统之间的关系是一种非常重要的资源，它可以使人们更好的“理解”Ｉｎｔｅｒｎｅｔ，从而更加方便的利用、开发以及管理Ｉｎｔｅｒｎｅｔ。生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现但是Ｉｎｔｅｒｎｅｔ中自治系统之间的相互关系是难以直接获取的，这是因为：（１）多个自治系统间的连接关系，属于企业内部的私有协定，ＩＳＰ不愿透露其中的商业秘密，外界很难得到其真实的拓扑结构。（２）目前还没有专门的机构来记录自治系统之间的关系，即使有记录信息也不完备；同时ＩＳＰ之间结成的商业关系是不断变化的，而现有库中的某些信息往往更新速度较慢，不能反映当前网络状况。所以，自治系统的各种属性信息是一种重要的网络资源，对于网络管理和保持网络健康发展有重要意义。２．３．３自治系统间的关系在网络服务方面有重要指导意义可以利用自治系统关系设计和优化网络，为管理域的负载平衡、拥塞避免提供参考；在研究自治系统关系基础上，可确定自治系统在Ｉｎｔｅｒｎｅｔ中的等级，为企业或小的ＩＳＰ提供网络接入，为商业协议提供依据；比较自治系统拓扑图中的逻辑关系和自治系统间的真实关系，发现故障点，减少误配现象，指导并调试路由器配置文件。２．４研究自治系统关系的几种方法可以通过收集自治系统连接关系的信息来构造自治系统拓扑图，下面是目前几种比较常用获取数据源的方法。２．４．１ｆｆＨＯＩｓ数据库亚太网络信息中心、因特网号码美国注册处以及ＩＰ网络欧洲协调中心都提供ＷＨＯＩＳ数据库，允许个人和组织查询已分配的ＩＰ地址和自治系统号码信息。可以通过ＷＨＯＩＳ数据库客户端与服务器建立连接得到需要的信息，有关自治系统的信息包括自治系统号码、名称、描述、输入策略、输出策略等等。通过输入输出策略的描述，可以明确该自治系统从哪些自治系统输入路由更新，向哪些自治系统发送路由更新，从而得到一个自治系统的连接图。但是ＷＨＯＩＳ数据库中的连接信息都是建网申请自治系统号码时的资料，很难反映当前网络的实际路由状况，而ＩＳＰ不对外公稀这些信息。因而也无法从现有的资料得到自治系统的互连信息。２．４．２主动探测方式主动探测方式主要是利用分解向探测集发送的ＩＣＭＰ数据包返回的ＩＰ链路得到单个１Ｐ，然后查询ＢＧＰ路由表，映射到自治系统的路径，从而构造出自治系统级拓扑图。路由器级拓扑图主要采用ＴｒａｃｅＲｏｕｔｅ等主动包探测网络的方法来获得路由信息。但是ＴｒａｃｅＲｏｕｔｅ的返回不包含有关自治系统的信息，也没有类似的命令或者协议可以得到，因而自治系统互连信息无法通过单独的主动探测得到。如硕士学位论文果使用主动探测方法，需要结合ＢＧＰ路由表，根据探测的结果查询ＢＧＰ路由表，把ＩＰ的连接关系映射成自治系统连接关系，构造出自治系统拓扑图。２．４．３利用ＢＧＰ路由表数据１．边界网关协议ＢＧＰＢＧＰ是当今网络中实现路径选择的一种外部网关协议，在ＴＣＰ／ＩＰ网络中实现域间路由。它在多个自治系统和域间执行路由，与其它系统交换路由和可达性信息““”１。ＢＧＰ设计以代替其前身（现在已经不用）外部网关协议ＥＧＰ而作为全球因特网的标准外部网关路由协议。它解决了ＥＧＰ存在的严重问题，更能有效地适应因特网飞速发展。ＢＧＰ经历了不同的阶段，从１９８９年最早版本的ＢＧＰ－１，发展到１９９３年开始开发的新版本ＢＧＰ一４。ＢＧＰ一４是第一个能够处理聚合（ＣＩＤＲ）和超级网的版本［３８］ｏＢＧＰ的出现引起了Ｉｎｔｅｒｎｅｔ韵重大变革，它把多个ＩＳＰ有机的连接起来，真正的成为全球范围内的网络，带来的副作用是路由爆炸，现在Ｉｎｔｅｒｎｅｔ的路由在聚合以后还远远的超过了６万条。２．ＢＧＰ与自治系统的关系图２－４是核心路由器用ＢＧＰ在自治系统问路由数据的示意图：图２—４ＢＧＰ在自治系统问路由数据示意图ＢＧＰ没有对因特网基本拓扑结构加以任何限制，它假定自治系统内部的选路已经通过内部选路协议（如ＩＧＰ）完成了。内是指在一个实体内部选路，外是指在实体之间。给予在ＢＧＰ相邻体之间交换的信息，ＢＧＰ构造了一个自治系统图。这个导引的图形有时叫作树。就ＢＧＰ而论，这个因特网就是一个自治系统图，每个自治系统用自治系统号码来识别。两个自治系统之间的连接形成一条路经，路径信息的汇集形成到达特定目的地的路由。ＢＧＰ使用这些与既定目的地相关的路径信息来确保无循环域间选路。图２－５表示了这个一般的路径树的概念””。生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现图２—５自治系统路径树与ＢＧＰ链路３．ＢＧＰ路由更新信息根据ＧＢＰ一４协议，ＢＧＰ发言者每当收到新的路由时，按照本地策略向建立ＢＧＰ连接的对等ＢＧＰ路由器发送路由更新通告，路由在一对ＢＧＰ发言者之间通过ＵＰＤＡＴＥ消息广播。每条ＵＰＤＡＴＥ消息原来广播一条可达路由或者撤销多条不可用路由到对端”“。这样，通过ＢＧＰＵＰＤＡＴＥ数据包，ＢＧＰ发言者把本地了解到的路由变化根据策略向所有对等路由器发送，从而扩散更新到所有路由器，每个ＢＧＰ路由器根据ＢＧＰ一４协议分析ＵＰＤＡＴＥ消息，修改本地路由表。因此，选取关键网络接入点设置捕包器，可以捕捉所有ＢＧＰＵＰＤＡＴＥ数据包，从而获得路由更新信息。４．ＢＧＰ路由表收集法在大型ＩＳＰ的ＢＧＰ路由表里面都有大量的自治系统路由信息，因而ＢＧＰ路由表数据是一种探求自治系统关系非常有效的资源；另一方面，很多ＢＧＰ路由数据是公开而且很容易获得的，如ＣＡＩＤＡ以及俄亥俄大学公布的ＢＧＰ路由表数据，所以利用ＢＧＰ路由表数据来构造自治系统级拓扑图已经成为目前构造自治系统拓扑图的一种行之有效的方法。由以上ＢＧＰ和自治系统关系可知，在实现ＢＧＰ协议的过程中已经包含了自治系统拓扑图的构造，因而可以通过分析ＢＧＰ协议，模拟ＢＧＰ协议的实现，构造所需要的Ｉｎｔｅｒｎｅｔ自治系统拓扑图。２．４．４以上几种方式的比较从上面的分析可知，ＷＨＯＩＳ数据库中的连接信息都是在申请自治系统号码时的资料，而ＩＳＰ之间的关系是短暂易变的，因丽ＷＨＯＩＳ数据库信息很难反映当前网络的实际路由状况，也无法专门用来构造反映实际网络情况的自治系统拓扑图，但是基于ＷＨＯＩＳ数据库上其它的静态信息，比如自治系统名称、描述、所属国家、管理者等等具有可参考的价值，而且难以以其它方式得到，可以用来作为ＢＧＰ路由信息的有效补充。主动探测方式虽然获得信息量较大，但由于自治系统的范围较大，小范围内无法起作用，而面对整个Ｉｎｔｅｒｎｅｔ，必须尽量全面的探测才能够得到较好的结果。这种方法会给网络带来很重的负担，而且多点测量，往往需要较大的软、硬件开１６销。ＣＡＩＤＡ的ｓｋｉｔｔｅｒ项目采用主动探测与ＢＧＰ路由信息相结合的方式““，对于每次探测得到的ＩＰ链路，查询ＢＧＰ路由表，映射得到自治系统的路径，从而构造出自治系统拓扑图。捕包法获取ＢＧＰ对等体之间的路由更新报文的方法需要在连接路由器的光纤中设置分光镜，把数据分流后进行分析，因而获得的信息只局限于该条光纤所连接的网络。为了更大范围获得路由表信息，需要在关键网络接入点设置，这就给信息收集增加了难度。ＢＧＰ路由边收集法是一种典型的单点测量方法，在没有设置路由器、建立对等连接的情况下，手工导出、汇集路由表。该方法获取信息源方法简单，通过对自治系统路径分解处理，效果较好，但是单点测量会受到漏点、漏边现象的影响。２．５路由器级拓扑和自治系统级拓扑目前对Ｉｎｔｅｒｎｅｔ拓扑的研究主要集中在两个层次：路由器级（ＲｏｕｔｅｒＲ—Ｌ）和自治系统级（ＡｕｔｏｎｏｍｏｕｓＳｙｓｔｅｍＬｅｖｅｌ，Ｌｅｖｅｌ，ＡＳ—Ｌ），其对应关系如图２－６所示，下面分别讨论这两个层次上的拓扑。点图２－６自治系统级拓扑图和路由器级拓扑图２．５．１路由器级拓扑路由器级拓扑研究主要是针对第三层（即ｏｓＩ模型的网络层）设备的，一般而言，第三层设备不是主机就是路由器，但是路由器级拓扑图只关注路由器而不关心其它网络设备。这一类拓扑图主要应用于网络层协议的开发。１．路由拓扑研究概述近年来，ＩＰ网络（特别是Ｉｎｔｅｒｎｅｔ）逐步发展为当前计算机网络的主流，ＴＣＰ／ＩＰ协议也因此成为事实上的工业标准。随着人们研究ＩＰ网络的逐步深入，对ＩＰ网络路由器拓扑的研究也得以广泛开展。Ｉｎｔｅｒｎｅｔ路由器拓扑研究主要任务就是发现ＩＰ网络中第三层（ＯＳＩ模型中的网络层）中各个路由器结点及其互连关系，另外还要发现路由器各端口所关联的子网，如图２—７所示。生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现图２—７ＩＰ网络互连不意图在目前网络拓扑研究领域里，路由器级拓扑是人们研究最多的～个方向，涉及的问题也最多。首先，由于互联网的迅猛发展，加之ＴＣＰ／ＩＰ协议只是一个工业标准，有关网络拓扑研究的规范和文档比较少，使得路由器级拓扑研究缺少可供参考的标准。因此，需要广泛研究各种ＩＰ网络特征，掌握各类路由设备所能提供的路由信息数据。其次，标准的缺乏最直接的一个影响就是研究方法种类繁杂。目前很多研究方法都是基于一定的前提，完成一定范围内的拓扑研究。再次，网络拓扑结构是～种重要的网络信息，因而会涉及网络安全方面的问题，例如：路径信息有时会因为不具备访闽权限而无法获取，或者探测数据包被防火墙过滤等等。所有这些对网络拓扑研究都造成了一定程度的影响。２．路由信息探测方式分类完成ＩＰ路由器级拓扑研究一个关键步骤就是探测基本的ＩＰ路由信息，它是研究者分析拓扑结构的基础。拓扑信息探测方式主要有两类：主动探测和被动探测。１）主动探测主动探测就是拓扑探测站点主动向目标网络中发送探测数据包，然后采集返回信息。最常用的主动探测技术就是利用Ｔｒａｃｅｒｏｕｔｅ和Ｐｉｎｇ命令进行探测。显然，这种方式会增加网络负荷，影响网络的正常运行而且很多网络都设置了防火墙以及其它的安全手段阻止探测。该方式的最大的优点就是可以随时控制探测进程，做到灵活高效。２）被动探测被动探测就是对各个探测的目标网络增加一个信息收集器或代理，被动地收集网络拓扑数据，然后发送给探测站点。和主动探测方式相比，该方式最大的优点就是不会增加太多的网络负荷。其不利的地方是这种方式不容易控制探测的进程，一般需要较长的时间才能获得足够的拓扑信息，时效性比较差。另外，如果网络规模过大，需要设置多个探测信息收集器，这是不太实际的。所幸的是，当前广泛应用于网络设备的ＳＮＭＰ协议，提供了一种信息收集代理，使问题得以解决。硕士学位论文３．相关协议工具及其拓扑研究策略当前，存在很多技术比较成熟、应用比较广泛的网络协议和工具。这些协议和工具可用于实现ＩＰ网络路由器级拓扑发现，如ＤＮＳ域名分析、ＲＩＰ路由协议、ＯＳＰＦ路由协议、Ｔｒａｃｅｒｏｕｔｅ／Ｐｉｎｇ命令、ＳＮＭＰ协议及ＭＩＢ库等。“，下面对此逐一进行简单讨论：１）ＤＮＳ域名分析。域名服务器（ＤＮＳ）维持了一个域内每个机器名字到其ＩＰ地址的映射关系。ＤＮＳ服务器通过域名转换命令返回域内名字列表。因此理论上讲，利用ＤＮＳ的解析命令可以发现域内所有路由器设备，而且使用这种方式发现的速度快、费用低。但是有时候ＤＮＳＢ艮务器不能及时更新列表信息，使得发现结果不够全面、准确。另外，出于安全方面的考虑，网络管理人员会关闭ＤＮＳ域转换服务，使得这种拓扑分析方法受到很大限制。２）基于ＲＩＰ路由协议的拓扑研究。路径信息协议ＲＩＰ是一种路由协议，可以用与路由设备进行通信，访问其路由表信息，从中分析提取路由拓扑。显然，这个方法性能高、速度比较快而且发现的结构准确。但是，该方法首先要实现ＲＩＰ协议（包括协议的各种命令原语，组装和解析协议数据单元）；另外，还要求目的网络内的路由器都支持和运行ＲＩＰ协议。３）基于ＯＳＰＰ协议的拓扑研究。和ＲＩＰ协议类似，ＯＳＰＦ也是一种路由协议，同样可以与路由器直接进行交互，获取相关路由表信息，从而找出网络中路由器及予网的互连关系。显然这种方法也具有快速、高效的特点。同样的道理，其前提也必须实现ＯＳＰＦ协议，和ＲＩＰ相比，该协议更加复杂，实现难度更大；另外，还要求探测的目的网络中路由设备都支持ＯＳＰＦ协议。４）Ｔｒａｃｅｒｏｕｔｅ／Ｐｉｎｇ命令探测。Ｔｒａｃｅｒｏｕｔｅ和Ｐｉｎｇ命令是两个常用的网络探测工具。使用一个ｔｒａｃｅｒｏｕｔｅｍ具探测一个远端主机，会返回到达该主机所经历的各个路由信息。如果远端主机处于活动状态，ｔｒａｃｅｒｏｕｔｅ探测的时间花费比较小，但是如果远端主机处于不活动状态时，ｔｒａｃｅｒｏｕｔｅ就会比较耗时。因此为了提高探测的时效性，可以借助于Ｐｉｎｇ命令事先探测远端主机活动性与否。由于绝大多数网络设备都支持Ｔｒａｃｅｒｏｕｔｅ和Ｐｉｎｇ命令，因而该方法的可行性比较好。但是由于要发送大量探测数据包，因而该方法对网络正常运行影响较大，对网络带宽要求比较高。另外，探测结果也因探测目的结点的选取不同而有所不同。５）ＳＮＭＰ－ＭＩＢ分析简单的网管协议ＳＮＭＰ是目前应用最广泛的网管协议，网络设备特别是路由器１９生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现一般都维护一个管理信息库ＭＩＢ，它包含了路由表、地址表以及地址映射表等路由信息。利用ＳＮＭＰ命令可以方便的访问这些信息，经过简单的分析，就完成路由拓扑研究。和上述方法相比，这个方法消息准确、全面、高效。但是，该方法有一个限制就是利用ＳＮＭＰ协议访问ＭＩＢ库需要提供一个团体字符库，而出于安全考虑，很多时候这个口令字并不公开。从而对该方法的可行性造成一定的影响。２．５．２自治系统级拓扑路由器级拓扑研究主要是针对网络层的路由器，但是由于Ｉｎｔｅｒｎｅｔ中路由器数量太大以及出于商业秘密的原因，获得准确的大规模路由器级拓扑图几乎是不可能的。““１。因而，大范围内考察研究Ｉｎｔｅｒｎｅｔ拓扑结构一般是基于自治系统级拓扑图的。由于自治系统数量比较少（不会超过６５５３６个“２３），所以可以在相对较小的自治系统级拓扑图里研究大范围网络“６’圳。最早的Ｉｎｔｅｒｎｅｔ拓扑建模方法是Ｗａｘｍａｎ提出的Ｗａｘｍａｎ模型““，最早从自治系统角度对网络拓扑结构进行研究的是Ｇｏｖｉｎｄａｎ等人，他们通过“复原”一个骨干网ＢＧＰ路由器从１９９４年６月到１９９５年６月以及另一个路由服务器１９９５年７月到１９９５年１１月的两份路由数据得到了自治系统拓扑图，通过实验他们证实了实验路由结果与实际路由是差不多的，因而他们指出：利用自治系统拓扑图可以得到很稳定的路由结果““，现有的自治系统拓扑图生成模型可以分为以下几类：１．平面随机型这一类模型认为Ｉｎｔｅｒｎｅｔ拓扑图处于一个完全无序的状态，在大尺度上是均一的，最典型的代表就是Ｗａｘｍａｎ模型。Ｗａｘｍａｎ模型是一种类似于ＥｒｄＳｓ－Ｒ６ｎｙｉ（ＥＲ）模型的随机模型，它认为网络结点出度频率呈泊松分布“”。这个模型有两个不同的版本：ＲＧＩ，先将结点随机布置在直角坐标网格中，结点问的距离是欧几里德距离：ＲＧ２，依据（ｏ，三）均匀随机分布为结点对指定距离。两个版本中，结点间相接的概率Ｐ（ｕ，ｖ）与其距离相关，服从泊松分布，距离越近，概率越大。户。，Ｖ）…冲掣（２．１）其中，如咯０，ｖ）表示结点“与ｖ之间的距离，三为结点间最长距离，口与∥为Ｗａｘｍａｎ参数，都在区间（０，ｌ】内取值，卢控制生成图中短边与长边的比例，口控制图中边的密度，其值越大图中的边越密。１９９７年，Ｚｅｇｕｒａ等人提出了Ｗａｘｍａｎ模型边分布的两种改进方法：“指数方法”和“定位方法”，两种方法分别用分布（２．２）和（２．３）代替（２．１）（２．２）盹Ｖ）…冲端硕士学位论文Ｐ０、，＝盯卢０如如果果栅；馨‘咭０∞Ｄ＜≥占艿（２．３）其中口，∥∈（ｏ，１１且占是一个给定的常数。”。２．层次型层次模型出于对Ｉｎｔｅｒｎｅｔ结构所具有的层次特征的认识，认为同一层上的结点出度接近，不同层次间结点出度差别很大，同一层上结点的布置一般借用Ｗａｘｍａｎ模型。Ｔｉｅｒｓ（等级）模型是第一个广泛应用的层次模型，它将Ｉｎｔｅｒｎｅｔ划分为ＬＡＮ（局域网），ＭＡＮ（城域网）和ＷＡＮ（广域网）３个层次。在该模型中，ＷＡＮ只有一个，通过指定ＬＡＮ和ＭＡＮ数量以及各自内部所包含结点的数量来构造拓扑图“”。另一个比较著名的层次模型是Ｔｒａｎｓｉｔ－Ｓｔｕｂ模型（ＴＳ模型），Ｔｓ模型将自治系统域划分为Ｔｒａｎｓｉｔ域和Ｓｔｕｂ域。在该模型中，Ｔｒａｎｓｉｔ结点彼此互联构成一个结点群，一个或多个Ｔｒａｎｓｉｔ结点群构成拓扑图的核心，而Ｓｔｕｂ结点分布在Ｔｒａｎｓｉｔ结点群四周与Ｔｒａｎｓｉｔ结点相连。Ｔｓ模型是ＧＴ—ＩＴＭ（ｇｅｏｒｇｉａｔｅｃｈＩｎｔｅｒｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｍｏｄｅｌｓ）软件包的一部分，有时ＧＴ－ＩＴＭ就是指ＴＳ模型““。３．幂律型１９９９年，ＦａｌｏｕｔＳＯＳ等人对ＮＬＡＮＲ（ＮａｔｉｏｎａｌＬａｂｆｏｒＡｐｐｌｉｅｄＮｅｔｗｏｒｋＲｅｓｅａｒｃｈ）在１９９７～１９９８年间的３份ＢＧＰ数据以及１９９５年的一份ｔｒａｃｅｒｏｕｔｅ测量数据进行分析，发现Ｉｎｔｅｒｎｅｔ自治系统拓扑中存在着４条幂律（ＰｏｗｅｒＬａｗｓ）“”。幂律是指形如Ｙ＊Ｘ。的方程，对于两个变量ｘ和Ｙ，存在一个常数。使得Ｙ与ｘ的ｃ次幂成比例。为了方便说明，在幂律中有两个声明：（１）结点ｖ的等级为Ｌ，－ｐ是在按出度降序排列序列中的索引值：（２）邻接矩阵特征值按降序排列，第ｆ个特征值为丑。幂律１（等级指数Ｒ）：结点出度或与该结点等级。的Ｒ次幂成比例。幂律１说明在Ｉｎｔｅｒｎｅｔ中自治系统的分布既不像在Ｗａｘｍａｎ模型中那样的“平等”，也不像Ｔｉｅｒｓ和Ｔｓ等层次模型那样“等级森严”，而应该是具有一种松散的层次结构。幂律２（出度指数０）：出度频率厶与该出度ｄ的０次幂成比例。幂律２和幂律１反映出Ｉｎｔｅｒｎｅｔ的自治系统具有高度非均一性。即只有少数结点具有很高的出度，大量结点具有较小的出度，这一规律的发现也直接否定了Ｗａｘｍａｎ模型中结点分布规律。近似幂律（ｈｏｐ—ｐｌｏｔ指数Ｈ）：ｈ跳内结点对（ｐａｉｒｓ次幂成比例。近似幂律中的ｈｏｐ—ｐｌｏｔ指数打一般可以用来对生成的拓扑图进行分类，例如：Ｈ＝１对应于环形拓扑；Ｈ＝２对应的是二维网格；对Ｉｎｔｅｒｎｅｔ来说，自治系ｏｆｎｏｄｅｓ）的数量与ｈ的日生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现统级拓扑图Ｈ“４．７，路由器级拓扑图Ｈｍ２．８”“。幂律３（特征指数Ｅ）：特征值＾与其次序ｆ的Ｅ次幂成比例。幂律３可以用来进一步对相似的同类图形进行区分。幂律的发现也给出一个启示：Ｉｎｔｅｒｎｅｔ中某个属性值的平均值不能准确地刻画这一属性，应该尝试用某个指数来进行刻画。对幂律的概念化形象描述是２００１年Ｔａｕｒｏ等人针对幂律１和幂律２提出的一种概念模型。这个模型将自治系统级拓扑图看作一只水母：水母的帽子代表Ｉｎｔｅｒｎｅｔ的核心，随着与核心的远离，结点重要性逐渐下降，中间的腿比两边的长表示出度为１的结点具有聚集性；网络对随机故障是鲁棒的，而若在核心出了故障却是灾难性的““。幂律的发现激发了研究人员在Ｉｎｔｅｒｎｅｔ拓扑结构中寻找更多的规律，也引起了学术界的广泛关注。２００１年，Ｍａｇｏｎｉ和Ｐａｎｓｉｏｔ。”对ＮＬＡＮＲ在１９９７～２０００年间的ＢＧＰ数据进行更细致的分析，提出了Ｉｎｔｅｒｎｅｔ拓扑发展的５条经验规律以及４条关于结点间最短路径和树结构的幂律，２００３年，Ｃｈａｌｍｅｒｓ等人…发现，在多播树的某些特征中也存在类似幂律的分布。４．其它模型在前面几类模型中，注重的是生成拓扑图的方法而没有考虑实际Ｉｎｔｅｒｎｅｔ中自治系统的相互关系。ＬｉｘｉｎＧａｏ从商业以及ＩＳＰ关系的角度把Ｉｎｔｅｒｎｅｔ中自治系统的关系划分为三类：提供者和客户（Ｐｒｏｖｉｄｅｒ—ｔｏ－Ｃｕｓｔｏｍｅｒ）关系、端到端（Ｐｅｅｒ—ｔｏ—Ｐｅｅｒ）关系以及兄弟（Ｓｉｂｌｉｎｇ—ｔｏ—Ｓｉｂｌｉｎｇ）关系“”。ＬｉｘｉｎＧａｏ认为因特网中自治系统是由各个ＩＳＰ所控制，它们之间的商业合同和契约决定各个自治系统所应用的路由转发策略，因而决定了自治系统间的各种关联关系。这种关联关系主要有下面三种：ｃｕｓｔｏｍｅｒ／Ｐｒｏｖｉｄｅｒ、Ｐｅｅｒ／Ｐｅｅｒ和Ｓｉｂｌｉｎｇ／Ｓｉｂｌｉｎｇ。自治系统之间的这些关联类型是它们各自ＢＧＰ路由器的输出策略以及流量转发关系的反映。如图２－８所示，一般对应有下面四种路由输出策略：１．对其Ｐｒｏｖｉｄｅｒ，自治系统ＡＳｘ会输出它自身或者它的Ｃｕｓｔｏｍｅｒ的路由，但是ＡＳｘ不会输出它的Ｐｒｏｖｉｄｅｒ或者Ｐｅｅｒ的路由；２．对其Ｃｕｓｔｏｍｅｒ，自治系统ＡＳｘ会输出其自身、Ｃｕｓｔｏｍｅｒ、Ｐｒｏｖｉｄｅｒ以及Ｐｅｅｒ的路由；３．对其Ｐｅｅｒ，自治系统ＡＳｘ会输出其自身和Ｃｕｓｔｏｍｅｒ的路由，但是不会输出Ｐｒｏｖｉｄｅｒ或者Ｐｅｅｒ的路由；４．对其Ｓｉｂｌｉｎｇ，自治系统ＡＳｘ会输出其自身、Ｃｕｓｔｏｍｅｒ、Ｐｒｏｖｉｄｅｒ以及Ｐｅｅｒ的路由。上述４种关系中关系１和关系３，关系２和关系４的输出策略是相同的。但所幸的是Ｐｅｅｒ／Ｐｅｅｒ关系和Ｓｉｂｌｉｎｇ／Ｓｉｂｌｉｎｇ关系是对称的，而Ｃｕｓｔｏｍｅｎｒ／Ｃｕｓｔｏｍｅｒ是不对称的，阻此可以区分它们。作出上述关系类型判断的自治系统拓扑图称之为带标记图。——＋提供翥到客户的边一一对≈队Ｓ之问的边……兄弟ＡＳ之闻的边图２－８带标记的自治系统拓扑图根据上述讨论，自治系统之间的关联关系类型可以根据它们之间的流量转发关系来进行判断，其判断规则如下：Ａ自治系统“和ｖ是对等关系当且仅当“和ｖ互不为对方提供流量转发服务；Ｂ自治系统ｌ‘是ｖ的Ｐｒｏｖｉｄｅｒ当且仅当“为ｖ通过流量转发服务丽ｖ不为“通过流量转发范围；ｃ自治系统Ⅳ和ｖ是兄弟关系当且仅当材和ｖ相互为对方通过流量转发服务。通过对ＢＧＰ路由表中的自治系统关系进行分类界定以后，ＬｉｘｉｎＧａｏ等人提出了一种由ＢＧＰ路由表数据分析自治系统路径来构造这种商业关系自治系统级拓扑图的启发式算法…１。为了获得更完整的自治系统级拓扑图，Ｃｈａｎｇ等人利用了更多的ＢＧＰ数据源得到了更完整的自治系统级拓扑图，他们的拓扑图中的链路比单一ＢＧＰ路由表的链路多了约４０％“”。２．５．３自治系统拓扑和路由器拓扑的比较自治系统级拓扑图以自治系统为基本研究单位，显示Ｉｎｔｅｒｎｅｔ中各个自治系统间的互联关系和路由更新策略；而路由器级拓扑图则以路由器为结点，直接反映了数据在Ｉｎｔｅｒｎｅｔ中的流动路径。从内容上说，二者处于不同的逻辑层次。路由器级拓扑图从实际数据转发路径得到，描述了路由器间的连通关系。这种图以较细的粒度描述Ｉｎｔｅｒｎｅｔ结构，忽视了不同管理策略的网络间的界限。自治系统级拓扑图以较粗的粒度描述了不同管理部门和ＩＳＰ的网络间的连接关系和路由更新策略，不只是物理上的连接关系还包括不同自治系统根据一些管理上的因素设置的ＢＧＰ路由更新策略，都会影响了自治系统拓扑图中结点的连通性。物理上连通的自治系统，实际上在拓扑图中数据路由时并不一定是连通的，因而不仅反映了硬件、技术上的网络参数，还反映了网络管理上的关系。从实现方法上说，路由器级拓扑图通常通过Ｔｒａｃｅｒｏｕｔｅ方法发送ＩＣＭＰ数据包得到。随着这种主动探测的方法探测范围和探测频率的加大，会给Ｉｎｔｅｒｎｅｔ生盛：：！！：塑鎏墨垫星姿捱盐璺兰鎏堕塑皇塞翌增加大量的负载。另外，一些网关和防火墙为了防止攻击，禁止了对ＩＣＭＰ的响应，探测者得不到ＩＣＭＰ的返回信息，也就无法了解网关和防火墙后的网络。而自治系统级拓扑图通常采用被动测量的方法，在网络的必要位置设置探针或者采用替代方法，不会增加网络负担，也不会受网关和防火墙的限制。应该说Ｉｎｔｅｒｎｅｔ首先是由自治系统构成，各个自治系统包含运行外部网关协议ＢＧＰ和内部嘲关协议ＩＧＰ的路由器，而自治系统之间通过运行ＢＧＰ的路由器互通路由信息，从而构成结构化的Ｉｎｔｅｒｎｅｔ。因而，为了从宏观上了解Ｉｎｔｅｒｎｅｔ结构，有必要构造自治系统级拓扑图。在此基础上，可以进一步了解自治系统内部的网络结构，分层次的构造Ｉｎｔｅｒｎｅｔ拓扑结构。２．５．４自治系统拓扑研究现状１．美国ＮＬＡＮＲ项目中的ＯｒｅｇｏｎＤａｙｉｄＲｏｕｔｅ－ｖｉｅｗｓＭｅｙｅｒ在他主持的一个项目中设置了路由器ＲｏｕｔｅＶｉｅＷＳ与重要骨干位置的路由器建立多跳ＢＧＰ对等会话连接。ＲｏｕｔｅＶｉｅｗｓ在会话连接中使用ＡＳ６４４７作为自身的自治系统号码，只接受路由不转发路由而且自身不发布任何前缀。每隔两个小时从该路由器上导出一个路由表备份””。该项目最初作为Ｉｎｔｅｒｎｅｔ操作员获得实时全球路由系统视图的工具，包括前缀视图和自治系统的视图，后来ＢＧＰ路由表数据在多方面得到使用。比如ＮＬＡＮＲ用来实现自治系统路径可视化和ＩＰＶ４地址空间的使用统计”“；其它一些项目使用这些数据把ＩＰ地址映射到源自治系统，用于各种拓扑研究；ＣＡＩＤＡ把ＲｏｕｔｅＶｉｅｗｓ数据与ＮｅｔＣＥＯ数据库结合起来，用来生成主机地理位置，ＣｏｒａＲｅｅｆ和Ｓｋｉｔｔｅｒ项目都支持这项功能””。２．路由信息服务（ｔｈｅＲｏｕｔｉｎｇＩｎｆｏｒｍａｔｉｏｎＳｅｒｖｉｃｅ，ＲＩＳ）ＲｏｕｔｉｎｇＩｎｆｏｒｍａｔｉｏｎ由ＲＩＰＥ网络协调中心组织，路由信息服务（ｔｈｅＳｅｒｖｉｃｅ，ＲＩＳ）提供的ＢＧＰ路由信息与一些地方提供的“ｌｏｏｋｉｎｇｇｌａｓｓ”服务很相似，但ＲＩＳ不只是传统的“ｌｏｏｋｉｎｇｇｌａｓｓ”，因为它不仅提供了实时的信息，而且提供了用户选择的过去时间段的信息。而且ＲＩＳ在Ｉｎｔｅｒｎｅｔ不同位置收集信息，并把这些信息集中起来““。原始数据采用ＭＲＴ格式，使用Ｚｅｂｒａ收集，这种二进制文件只能用｝ＡＲＴ发布的ｒｏｕｔｅ—ｂｔｏａ工具阅读。３．ＤｉｓｔｒｉｂｕｔｅｄＩｎｔｅｒｎｅｔＲｏｕｔｅＥｙｅ（ＤＩＲＥ）ＤＩＲＥ是一种自治系统问路由监测的分布式代理结构。在这种结构中，监测代理（ＭＡ）详细记录了从其它ＢＧＰ路由表发送来的ＢＧＰ路由更新，操作代理（ＯＡ）查询多个ＭＡ归纳出路由问题的来源和原因。这个系统主要针对Ｒｏｕｔｅｆｌａｇｓ，即ＢＧＰ路由表中的过量路由更新和路由属性变化。Ｒｏｕｔｅｆｌａｇｓ有各种原因，包括物硕士学位论文理设备出错，路由软件错误，路由器配置错误等等。ＤＩＲＥ在多个网络接入点安装ＭＡ。ＭＡ设置成消极模式，与目标ＢＧＰ建立会话，只接收邻接ＢＧＰ发来的路由更新，而不发送，这样来收集ＢＧＰ路由更新信息””。４．ＫＤＤＲ＆Ｄ实验室的Ｉｎｔｅｒｎｅｔ路由信息监测软件这个软件利用ＢＧＰ监听获得路由信息，记录在磁盘文件中留作离线分析，并维护一张路由表作为在线分析，在线分析做成动态库的形式，以便不打断ＢＧＰ会话加载新的功能“”。２．６小结本章对Ｉｎｔｅｒｎｅｔ自治系统拓扑研究现状进行了探讨，首先从自治系统以及自治系统拓扑的概念出发分析了自治系统的工作原理、自治系统拓扑研究的意义。然后研究了自治系统拓扑研究的现状，探讨自治系统拓扑研究的方法以及可用的资源。最后对比分析了目前研究得最多的两个层次的拓扑：路由器级拓扑和自治系统级拓扑的研究对象、方式、意义以及成果。路由器级拓扑图以网络层设备为研究对象主要应用于网络协议的开发及试验而自治系统级的拓扑图以自治系统为基本研究单位刻画网络的连接状况、流量管理策略，它们在对Ｉｎｔｅｒｎｅｔ描述方式、粒度等诸多方面有很大的区别。生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现第３章自治系统层次拓扑模型自治系统是一个由单一管理者管理的网络，但是在Ｉｎｔｅｒｎｅｔ中，不同的自治系统所处的地位并不是平等的，重要的自治系统也称之为骨干自治系统（通常是一些大型的网络服务提供商或者研究机构），由于其管理的范围较大所处的位置关键，它们发挥的作用也是巨大的。一般来说，骨干自治系统连接的结点较多，连通性较强，是可靠的，当自治系统域中某些结点或者边失效后，自治系统仍然正常工作，即使从自治系统中去掉某些结点或者边，自治系统仍能保持连通。连接这些主要自治系统域形成的网络骨干网，具有很好的鲁棒性”“。但是对于其它的一些处于边界的自治系统而言，它们连接的结点数目较少，因而当其中某些环节发生故障后自治系统就可能会失去其功能，另一方面，因为这类自治系统范围较小，即使发生故障也不会对网络造成大范围的影响。所以，Ｉｎｔｅｒｎｅｔ的骨干部分可以看成是一些相互连接或重叠的自治系统域构成的，一些相对小的自治系统其结点度不大，因而可以把Ｉｎｔｅｒｎｅｔ看成由许多不同层次相互连接的自治系统域组成““，可以在拓扑图里用不同的层次来体现。３．１对层次模型的研究和分析在Ｉｎｔｅｒｎｅｔ拓扑研究中对层次结构（ｈｉｅｒａｒｃｈｙ）的定义是：Ｉｎｔｅｒｎｅｔ中结点问的通信量不是平均的分配到每一条链路或者是结点上的，而是存在量骨干（ｂａｃｋｂｏｎｅ）结点，它们负责大量结点对之间的通信，但是更多结点处于边界网络，相对骨干结点而言它们的通信量并不大。“。自１９９５年开始，大规模的Ｉｎｔｅｒｎｅｔ拓扑测量工作已经逐步展开，采集到了大量的拓扑数据，而这些数据对科研机构都是免费开放的，这极大地推动了拓扑研究的发展。Ｉｎｔｅｒｎｅｔ拓扑研究也进入了一个成果不断累加的阶段，出现了很多新的成果，新旧成果共同描绘了Ｉｎｔｅｒｎｅｔ拓扑图研究的前景。由定义知道层次模型是从Ｉｎｔｅｒｎｅｔ所特有的层次特征来对Ｉｎｔｅｒｎｅｔ拓扑进行研究，１９９６年，Ｄｏａｒ提出了Ｔｉｅｒｓ等级模型，这是第一个得到广泛应用的Ｉｎｔｅｒｎｅｔ自治系统层次拓扑模型““；１９９７年，Ｚｅｇｕｒａ等人提出了另一种自治系统层次拓扑模型一一ＴｒａｎｓｉｔＳｔｕｂ模型““，下面讨论这两个应用最广泛的Ｉｎｔｅｒｎｅｔ自治系统级层次拓扑模型。３．１．１Ｔｉｅｒｓ模型Ｔｉｅｒｓ模型是第一个得以广泛应用的自治系统级层次拓扑模型，在Ｔｉｅｒｓ模型里，Ｄｏａｒ把Ｉｎｔｅｒｎｅｔ中的自治系统结点划分为三个层次：ＬＡＮ层结点、ＭＡＮ层结点、ＷＡＮ展结点。Ｔｉｅｒｓ模型首先生成树，蒋将剩下的结点向生成树连撩以保证据羚霆的涟避性。缮点溺趸余边鳃添趣主要蔹搂两绩煮黪Ｅｕｃｌｉｄｅａｎ巍离，获最近豹臻赢开始耱边。Ｔｉｅｒｓ模型虽然保证了鼙豹连通往，稳髭并不韪提供有效魏方法增加遴接以控制描扑图的鲁棒性。在Ｔｉｅｒｓ模型里，锼餍下秀的参数控制生成强躲丈，ｊ、：羁：垒藏霆孛ＷＡＮ结煮鹣数鞠，兔了篱单越冕，一觳取篷秀１；昂：生成图中ＷＡＮ照面结点的数目；Ⅳ。；生成图中ＭＡＮ结点的数目｛ｓ。：每一个ＭＡＮ蹩覆蘸绩点数薅；Ⅳ，：镣个ＭＡＮ里ＬＡＮ的数目：研：每一个ＬＡＮ熙面的结点的数目；嚣嚣Ｔｉｅｒｓ模型生成懿薤羚翟结煮慧鼗Ⅳ巍；Ｎ尝Ｓｗ÷援酣Ｓ嘣÷魏ＭＮＬＳＬ硌≈该模粼的时间复杂腋为０（以２），阁３—１、３－２、３－３是一蝗用Ｔｉｅｒｓ模烈生成的Ｉｎｔｅｒｎｅｔ爨渗系统级按朴匿。匿３－１３０个结点鲶Ｔｉｅｒｓ撼扑匿懑东蝴—ｈ图３－２１２５个结点的Ｔｉｅｒｓ拓扑睦生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现图３－３２６０个结点的Ｔｉｅｒｓ拓扑图３．１．２Ｔｒａｎｓｉｔ—Ｓｔｕｂ模型Ｔｒａｎｓｉｔ—Ｓｔｕｂ模型（后面简称Ｔｓ模型）是Ｚｅｇｕｒａ等人１９９７年提出的另一种得到广泛应用的生成Ｉｎｔｅｒｎｅｔ自治系统拓扑图的层次模型，在该模型中，网络中每个交换域（ＡＳ结点）分为ｔｒａｎｓｉｔ域和ｓｔｕｂ域两种类型。Ｓｔｕｂ域只转发起始结点和目的结点都在自己域内的消息，而ｔｒａｎｓｉｔ没有这样的限制。Ｓｔｕｂ域可以进一步分为Ｓｉｎｇｌｅ—Ｈｏｍｅｄ域和Ｍｕｌｔｉ—Ｈｏｍｅｄ域，其中Ｍｕｌｔｉ—Ｈｏｍｅｄ域连接到多个Ｔｒａｎｓｉｔ域而Ｓｉｎｇｌｅ—Ｈｏｍｅｄ域仅仅连接到一个Ｔｒａｎｓｉｔ域。Ｔｒａｎｓｉｔ域的功能是有效的将ｓｔｕｂ域连接起来，如果没有ｔｒａｎｓｉｔ域，ｓｔｕｂ域之间就需要直接相连接，显而易见这样的连接方式比较复杂并且与实际Ｉｎｔｅｒｎｅｔ的情况不符。Ｓｔｕｂ域通常对应实际的ＬＡＮ或类似的网络类型，ｔｒａｎｓｉｔ则对应ＷＡＮ或ＭＡＮ等一些大型网络，图３—４显示了Ｔｓ模型的基本结构。把自治系统域划分为Ｔｒａｎｓｉｔ域和Ｓｔｕｂ域后，Ｉｎｔｅｒｎｅｔ里的任意两个结点“和ｖ之间的路由要遵循下面两条基本规则：１．如果结点“和ｖ在同一个域内，它们之间的整条路径都保留在该域内；２．如果结点Ｕ∈咀结点ｖ∈ｙ，Ｕ和矿是两个不同的域，从结点Ｕ到结点ｖ的路径从ｕ出发通过零个或者多个域到达矿，最后到达结点ｖ。图３－４ＴＳ模型硕士学位论文ＴＳ模型采用下面的步骤生成具有两个层次的Ｉｎｔｅｒｎｅｔ自治系统级拓扑图：首先，使用任意一种平面随机方法（如Ｗａｘｍａｎ模型）生成一幅连通的随机图，图中每一个结点都代表一个完整的Ｔｒａｎｓｉｔ域，随后图中的每一个结点被一幅表示一个Ｔｒａｎｓｉｔ域骨干结点拓扑的连通随机图所取代：下一步，对每一个Ｔｒａｎｓｉｔ域里面的每一个结点，生成一些代表连接到该结点的Ｓｔｕｂ域的随机连通图连接到该结点，每一个Ｓｔｕｂ域都有一条边连接到自己的Ｔｒａｎｓｉｔ域结点；最后，添加一些“冗余”边以增强图的连通性，这一步主要添加两类边：一类边连接Ｔｒａｎｓｉｔ域和Ｓｔｕｂ域另一类连接相同类型的域。该模型使用表３－Ｉ中的参数控制生成图的大小：表３－１ＴＳ模型参数参数ｒＮｔ足Ｎｉ意义Ｔｒａｎｓｉｔ域数目每个Ｔｒａｎｓｉｔ域的平均结点数连接到Ｔｒａｎｓｉｔ结点的平均Ｓｔｕｂ域数，Ｓｔｕｂ域的平均结点数Ｔｓ模型的平均结点度．＿，＝『可以用下面的公式计算（忽略“额外”边）：万：盟±堡±垦坐１１＋ＫＮ￥０．２）其中Ｅ和Ｅ。分别表示Ｔｒａｎｓｉｔ域和Ｓｔｕｂ域边的密度（每个结点边的数目）。３．２屡次型模型间的比较层次模型采用层次的方式对Ｉｎｔｅｒｎｅｔ进行拓扑建模，层次的拓扑图与平面的拓扑图相比在很多性能参数方面有了很大的差异，为了更好的分析研究层次拓扑模型，针对一些常见参数进行了详细的探讨。下面在平均结点度、冗余度以及平均每跳直径等参数方面对Ｔｓ模型和Ｔｉｅｒｓ模型以及平面随机模型Ｗａｘｍａｎ进行分析对比。３．２．１层次模型和随机模型对比层次拓扑模型与随机模型相比，在各个拓扑图参数（本文选择三个）上都有不小的交化。首先是平均结点度，由图３—５（ａ）可以看出层次拓扑模型在平均结点度方面都比Ｗａｘｍａｎ模型大，但是与随机模型相比较并没有其它参数差别大。对层次拓扑模型与平面模型来说，生成图性质最大的区别表现在冗余度上，层次模型拓扑图的冗余度几乎比平面模型平均大２倍，而尤以Ｔｓ模型的冗余度值大，如图３—５（ｂ）。在每跳直径方面，层次型模型相对来说具有较长的每跳直径，这是由于分层的缘故。比如在ＴＳ模型里，ｓｔｕｂ结点必须与ｔｒａｎｓｉｔ结点相连，通过ｔｒａｎｓｉｔ结点通信，然后才可以和其它的ｓｔｕｂ结点通信；而在Ｔｉｅｒｓ模型里，不处于同一ＭＡＮ的ＬＡＮ即使地理位置很近，如果它们需要通信的话，也不得不通过生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现ＭＡＮ甚至是ＷＡＮ来通信。所以使得每跳直径变长，如图３－５（ｃ）。同样由于分层的原因，层次模型使原本地理距离较近的结点之间的路径变长，所以导致拓扑图的平均直径增长。（ａ）平均结点度（ａｖｅｒａｇｅｄｅｇｒｅｅ）（ｂ）冗余度（ｎｕｍｂｅｒｏｆｂｉｃｏｍｐｏｎｅｎｔｓ）（ｅ）平均每跳直径（ｈｏｐ－－ｄｉａｍｅｔｅｒ）图３－５Ｗａｘｍａｎ、ＴＳ模型和Ｔｉｅｒｓ之间的参数比较３０硕士学位论文３．２．２层次模型之间的对比两个Ｉｎｔｅｒｎｅｔ自治系统层次拓扑模型Ｔｓ模型和Ｔｉｅｒｓ模型在多个参数上都表现出不一样的性质。Ｔｓ模型的拓扑图具有更多的冗余度和更长的直径。这是因为Ｔｓ模型被分为ｔｒａｎｓｉｔ结点和ｓｔｕｂ结点，而ｓｔｕｂ结点之间的通信依赖于ｔｒａｎｓｉｔ结点，所以直径更长。在冗余度方面，由于层次模型的连通性不如随机模型，使得拓扑图的冗余度增多。另一方面Ｔｓ模型膨胀率低，说明其传播的速度慢，即骨干结构不明确，恢复率与Ｉｎｔｅｒｎｅｔ相差很大，因为其结点间的冗余边较少所以网络的鲁棒性较差。３．３传统层次型模型的不足ＴＳ模型提出了具有ｔｒａｎｓｉｔ域和ｓｔｕｂ域两层的层次结构。Ｔｒａｎｓｉｔ域代表的是实际Ｉｎｔｅｒｎｅｔ里的ＷＡＮ或ＭＡＮ，ｓｔｕｂ域代表ＬＡＮ。ＴＳ模型解决了层次问题，但是其连通性的问题没解决。Ｔｉｅｒｓ模型先成生最小生成树，再加边。它保证了拓扑图的连通性，但是并不能提供有效的方法来控制拓扑图的鲁棒性。３．４评测层次结构的参数除了前面所提到的平均结点度、冗余度以及拓扑图直径等参数以外，对于层次模型而言还有一些其它重要的参数。３．４．１链路权值分布对层次结构的评估需要测量链路的最小结点覆盖。最小结点覆盖就是计算当去除一条链路后导致不连通结点的数目““。其值的大小反映该链路的重要性，这一链路值大就说明链路很重要（许多结点依赖于它），反之就表明该链路重要性降低。一般来说，骨干链路的权值应该大于边界链路的值，因而链路权值的分布就是对层次结构所体现出来的层次性的评估。如果所有的链路都有相似的权值，说明网络没有层次性，链路的使用是平均分配的。如果存在权值很大的链路，那就说明网络的层次结构分明。Ｗａｘｍａｎ模型的路径权值分布约７０％的路径权值在０．０５左右，而且这一部分的分布很平均。所以，这类模型的拓扑图层次结构很松散。这与研究者的想法是一致的，Ｗａｘｍａｎ模型没有明确的层次结构（如图３—６）。另外，观察Ｔｓ曲线和Ｔｉｅｒｓ曲线，它们都具有适中的层次结构。因为它们的曲线具有一个快速下降的趋势（小于１０％的结点拥有多于０．００５的链路权值），这与提出层次型模型的初衷是相符的，而其中Ｔｓ的层次性更为明显。可以判断Ｔｓ和Ｔｉｅｒｓ拓扑模型都有严格的层次结构。生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现图３－６几个模型的链路权值分布通过上述分析，可得出下面结论：基于层次结构的拓扑模型形成了非常严格的层次结构，这要比采集到的实际网络数据要高；幂指数模型也显示出了网络的层次结构，虽然没有在算法中明显的加入层次结构，但是却产生了与Ｉｎｔｅｒｎｅｔ相类似的层次结构。３．４．２路径使用率与结点度的相关系为了更好的刻画拓扑图中的层次结构，Ｈ．Ｔａｎｇｍｕｎａｒｕｎｋｉｔ等人提出了路径权值与路径两端结点的出度之间关系（称为相关系）的参数。“。参数值越高说明权值高的路径连接了出度也很高的结点。图３—７给出了几个模型的参数比较。随机拓扑图也有较高的参数值。随机图的算法中没有显式加入层次结构，其参数值高的原因是随机型拓扑图的结点度分布是随机的，其链路的使用率也是随机的，所以显示出来的层次结构非常有限。Ｗａｘｍａｎ模型的参数值较高，而Ｔｓ和Ｔｉｅｒｓ模型的参数相对低一些。这主要是因为基于层次结构的拓扑模型（例如ＴＳ、Ｔｉｅｒｓ）在算法中都非常注重于结点间连接的放置。图３—７结点度与路径权值的相关系硕士学位论文３．５小结层次模型是从Ｉｎｔｅｒｎｅｔ所特有的层次特征来构造Ｉｎｔｅｒｎｅｔ自治系统级拓扑图，本章详细研究了两种应用最广泛的Ｉｎｔｅｒｎｅｔ自治系统层次模型：Ｔｓ模型和Ｔｉｅｒｓ模型，并对两者进行了详细的对比，Ｔｓ模型是层次型拓扑模型中表现最好的，所以广泛的应用于网络仿真。层次型的拓扑生成器更适合模拟包含了带宽、拓扑和地理形态的网络。Ｉｎｔｅｒｎｅｔ由自治系统构成，而自治系统之间的地位是不平等的，这种不平等的关系导致了Ｉｎｔｅｍｅｔ的多层次特性。因而尽管随着幂律的发现。层次模型已经受到一些网络专家的质疑。但是，由于幂律本身就是一种松散的层次结构以及Ｉｎｔｅｒｎｅｔ公认的多层次特征，所以层次模型依然有着重要的现实意义。依据核心自治系统的强连通和边界自治系统树形路径，我们接下来对Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图进行进一步的研究。生盛：：：！旦塑墨丝星姿堑盐璺兰鎏型茎兰塞翌第４章Ｃｏｒｅ－Ｔｒｅｅ算法４．１引言在当前比较成熟的Ｉｎｔｅｒｎｅｔ自治系统级拓扑图生成算法中，随机模型把Ｉｎｔｅｒｎｅｔ看成松散的自治系统集合，认为Ｉｎｔｅｒｎｅｔ处于一个完全无序的状态，不能刻画出Ｉｎｔｅｒｎｅｔ所具有的最基本的层次特征；传统层次模型完全依据结点度来划分层次，在具体操作中不好把握尺度；幂律型以及其它的方法基本上都是利用ＢＧＰ路由表数据来分析Ｉｎｔｅｒｎｅｔ自治系统路径，然后依据路径信息推测出其拓扑结构，但是由于ＢＧＰ路由表数据太大并在不断地增长，因而通过ＢＧＰ路由数据构造自治系统级拓扑图工作量巨大。另一方面，对于那些不是很重要的自治系统结点来说，它们一般是以树的方式连接，构成自治系统路径树。本章提出一种生成Ｉｎｔｅｒｎｅｔ自治系统级拓扑图的Ｃｏｒｅ—Ｔｒｅｅ算法（后面简称Ｃ－Ｔ算法），它可以直接生成两层结构的Ｉｎｔｅｒｎｅｔ自治系统级拓扑图，克服了随机模型的松散结构缺陷的同时具有了Ｉｎｔｅｒｎｅｔ基本层次的特征，它不依据结点出度来分层，可以以较小的开销生成Ｉｎｔｅｒｎｅｔ自治系统级拓扑图。４．２Ｃ－Ｔ算法思想ｃ—Ｔ算法从层次的观点出发把Ｉｎｔｅｒｎｅｔ中的自治系统分为两个层次（如图４—１）：第一层为核心网络（ＣｏｒｅＭｅｓｈ），它由核心自治系统结点组成，所有核心自治系统结点连接组成核心网络，它是Ｉｎｔｅｒｎｅｔ的核心，对应于Ｉｎｔｅｒｎｅｔ中重要的自治系统结点，因而核心结点度都比较大；另一层是树形拓扑，它由一些相互独立的树组成，所有树的根结点都是核心自治系统结点，核心网络和森林中的树通过根结点连接构成ｔｎｔｅｒｎｅｔ自治系统级拓扑图，树中除了根结点以外其余的结点对应于Ｉｎｔｅｒｎｅｔ中处于边界的自治系统结点，其熏要性不如核心网络结点，反映在结点度都比较小。在算法中，首先通过现有模型构造核心网络；然后在核心网络中选择连通性较大（结点度大）的核心结点作为根结点构造树，这样就得到了两层结构的Ｉｎｔｅｒｎｅｔ自治系统级拓扑生成图。４．３定义４．３．１Ｃ—Ｔ生成图结点定义研究了当前应用比较广泛的自治系统结点分类后，对算法中生成的自治系统拓扑图进行说明，在ｃ—Ｔ算法生成的两层结构的自治系统拓扑图中对应两种结点３４硕士学位论文和两种边：核心网络自治系统结点和森林中树自治系统结点以及核心边和树边，下面是它们的定义：１．核心网络自治系统结点位于高层核心网络的自治系统结点称为核心自治系统（ＣｏｒｅＡＳ），它们是构成拓扑图核心网络的自治系统结点。核心自治系统结点出度一般都比较大而且没有度为ｌ的核心自治系统结点；核心网络中的边称为核心边。２．树自治系统结点１）根自治系统（ＲｏｏｔＡＳ，根ＡＳ）根Ａｓ结点既是核心Ａｓ结点又是树Ａｓ结点，即：它是连接两个或者多个核心ＡＳ结点并且连接一个或者更多树Ａｓ结点的ＡＳ结点。从定义可以看出，根ＡＳ结点既是核心网络结点又是树结点，在整个ｃ—Ｔ拓扑图里只有这类Ａｓ结点具有这一性质，它是核心网络中任何结点与树中非根结点以及任何两个不在同一棵树的树Ａｓ结点相互通信的枢纽，也是它们能够相互通信的唯一途径。２）分枝自治系统（ＢｒａｎｃｈＡＳ）ｃ—Ｔ拓扑图里出度大于２的自治系统结点，它有两类：树中分枝结点，其主要作用是连接树中根结点和非根结点：核心网络中的分枝结点的作用是传输和转发流量。３）中继自治系统（ＲｅｌａｙＡＳ）ｃ—Ｔ拓扑图中度为２的结点，这类结点既从别的自治系统那里接收数据同时也为其它自治系统转发数据，它对其它自治系统而言起到中继数据的功能。要指出的是：这一类结点不仅出现在树里面而且还出现在核心网络中，在这里不加以区分，把它们统一称为中继自治系统结点。４）叶子自治系统（ＬｅａｆＡＳ）ｃ—Ｔ拓扑图中度为１的结点（与Ｓｔｕｂ自治系统的定义是相同…１），因为核心网络中没有度为１的结点，所以所有叶子结点都出现在树中。在Ｉｎｔｅｒｎｅｔ中，这类自治系统结点只与和它邻接的自治系统结点交换数据而拒绝为任何其它自治系统转发数据，树中的边称为树边，（各类结点和各类边如图４一ｌ所示）。４．３．２Ｃ－Ｔ算法参数定义在本章提出的生成Ｉｎｔｅｒｎｅｔ自治系统级拓扑图的Ｃ－Ｔ算法里，生成的自治系统拓扑图是一个无向图Ｇ＝（矿，Ｅ），其中ｖ是自治系统结点集合：Ｅ是自治系统结点边的集合：ｄ０）表示结点“的度；（”，，１表示连接结点ｚｆ和ｖ的边；下面是ｃ—Ｔ算法中用到的一些参数的定义：圭盛：！！！望塑至垫星姿堑盐笪兰鎏笪茎兰塞翌Ｎｕｍ。。。：表示生成图中核心网络结点的数目；Ｍ肼而：表示生成图所有树的非根结点的数目；ＴｒｅｅＡ。。：表示生成图中期望的树平均大小（含Ｒｏｏｔ结点，用结点数衡量）Ｅｄｇｅｃｏ。：标示核心网络中的边；Ｅｄｇｅｒ，。．：标示树中的边；ａ、卢：Ｗａｘｍａｎ模型参数，口和卢在区间（０，ｌＩ取值；算法中还用到了下面几个结点集合：Ｎｏｄｅｃｏ。：核心网络结点的集合：ⅣＤ出。：已经加入到树里面的树结点集合；Ⅳ（－出而：还没有加入到树里面的非根树结点集合；ＮｏｄｅＲｏｏ．：树的根结点集合。Ｔｎｅ３ＣｏｒｅＭｅｓｈ图４—１各类自治系统以及各类边４．４算法描述输入：Ｎｕｍｃｏ。，＾Ｊ锄蕊，ＴｒｅｅＡ。。，口，∥输出：自治系统级拓扑图Ｇ初始化：Ｎｏｄｅｃｏ＂＝ｏ；Ｎｏｄｅｒ。＝ｏ；Ｎｏ出蔽＝０；ＮｏｄｅＲｏｏｆ＝０；Ｖ＝０；Ｅ＝ａＰｈａｓｅ１：／／用Ｗａｘｍａｎ模型生成核心网络１：在作图平面内随机放置Ｎｕｍｃ。个结点％，“２，……，“Ｍ‰；Ｎｏｄｅｃ。。＝｛％％…一，“慨。）；矿＝ＶｕＮｏｄｅｃ。２：对任意“，１，∈Ｎｏｄｅｃｏ，。且甜≠Ｖ，则：结点Ｕ和ｖ以概率：盹Ｖ）＝口唧掣３：对前面生成的图进行如下调整：到图中距离它最近的非邻接结点；然后，为了增强核心网络的连通性，增加一些冗余边：（４．１）连接；如果“，Ｖ连接：Ｅ＝五ｕ｛（地ｖ））并且把（“，Ｖ）标记为Ｅｄｇｅｃｏｒｅ首先，调整度为１的结点，给图中所有结点度为１的结点增加一条边，连接对任意“，ｖ∈Ｎｕｍｃｏ，，Ｒｕ≠ｖ，如果（“，Ｖ）萑Ｅ则“，ｖ以０．２的概率连接；如果“，Ｖ连接：Ｅ＝Ｅｕ｛（地ｖ）｝并且把（“，Ｖ）标记为＆‰Ｐｈａｓｅ２：／／构造树形拓扑ｌ：由参数Ⅳ“ｍ而和Ｔｒｅｅ。。。。确定生成图中树的数目：№。－『老蚓Ⅳ。ｄ％。。，＝“，甜：，……，“№。。）；㈦２：找出Ｎｏｄｅｃｏ，，Ⅳ‰个度最大结点｛“。，甜：，……，“Ⅳ。。。。），３：在作图平面内随机放置Ⅳ”ｍ而个结点ｖｌ，ｖ２，……ｋ；Ｎｏｄｅ而＝｛Ｖｌ，ｖ：，……Ｖ。。。而）；矿＝矿ｕⅣＤｄ堍；Ｗｈｉｌｅ（ＮｏｄｅＲ。≠ｏ）／／保证每个Ｒｏｏｔ结点至少有一个非根结点对每一个Ｕ∈Ｎｏ出胁，选择距离“最近的Ｖ∈Ⅳ砒藏连接到就；Ｅ＝Ｅｕ（（“，Ｖ））并且把（“，ｖ）标记为ｍ％帮；Ｎｏｄｅｒ，。；Ｎｏｄｅｒ，。ｕ｛“，Ｖ）；生盛！！：：：：：！旦塑墨篓星盗堑盐里兰鎏堕壅皇茎翌Ｎｏ如褥＝Ｎｏ如而一｛Ｖ））４：Ｗｈｉｌｅ（Ｎｏ如鬲；≠囝）／／添加剩余的非Ｒｏｏｔ结点｛对每一个１，ＥＮｏ如丽，选择距离Ｖ最近的“∈Ｎｏｄｅｍ。连接到ｖＥ＝Ｅｕ｛（“，Ｖ）｝并且把＠ｖ）标记为Ｔｒｅｅｅｄ，：Ｎｏｄｅｒ，。。＝Ｎｏｄｅｒ，。。ｕ｛ｖ）；Ｎｏｄ堍＝Ｎｏ如菇一｛Ｖ｝；｝Ｐｈａｓｅ３：／／边的集合Ｅ和结点集合矿构成拓扑图Ｇ＝（Ｖ，Ｅ）：通过上面的步骤就可以得到具有核心网络和树形拓扑两层结构的Ｉｎｔｅｒｎｅｔ自治系统级拓扑图，图４－２是一幅当Ｎｕｍｃｏ，ｅ＝１００：Ｍ小丽＝７０；ＴｒｅｅＡｖｅ－。＝３；口＝０．２；卢＝Ｏ．３时的ｃ—Ｔ拓扑图，实心结点和实线边为核心网络，空心结点与虚线边为树形拓扑。图４－２Ｃ－Ｔ算法例图４．５算法分析及实验分析４．５．１时间复杂度分析算法的时间开销主要是用在第一部分生成核心网络和第二部分添加非根结点的地方。其中第一部分时间开销主要是在用Ｗａｘｍａｎ方法生成核心网络以及添加冗硕士学位论文余边的地方，它们的代价都取决于核心网络的结点数目大小（即Ｎｕｍｃｏ。），因为要在Ｎｕｍｃｏ。个结点中成对的取结点，所以代价为从Ｎｕｍ。。个结点中任取两个结点的组合数，它的时间开销为：‰：坐丛掣＝Ｏ（Ｎｕｍｃｏ。２）第二部分时间开销主要是在添加非根结点的部分，其中第三步连接Ｒｏｏｔ结点的代价为ＩＮｏｄｅＲ。Ｉ；第四步添加其它非Ｒｏｏｔ结点的开销是：ｌⅣＤ如而１一［ＮＯｄｅＲｏｏｔ［，因而这一部分时间代价是：ＩⅣ０出胁｜＋（｜Ⅳ０ｄ‰卜ＩＮｏａｅ。。，１）＝ＩⅣｏ峙Ｉ＝Ｄ（ＩⅣＤ咭Ｉ）因此算法总的时间代价为Ｏ（Ｎｕｍｃｏｒｅ２）＋Ｄ（ＩⅣｏ如丽１），而算法中Ｎｕｍｃｏ，，和Ⅳｏ出丽ｌ相近，所以Ｎｕｍｃｏ。２＞ｌⅣＤ如丽ｊ，所以该算法的时间复杂度为０（Ｎｕｍｃ。２）即：Ｏ（ｎ２１。４．５．２生成图性质分析下面，对Ｃ—Ｔ算法生成的拓扑图进行分析１．生成图连通性分析结论：采用Ｃ—Ｔ算法生成的自治系统级拓扑图是连通的。证明：首先，核心网络是连通的，ｃ—Ｔ算法用Ｗａｘｍａｎ模型生成核心网络，Ｗａｘｍａｎ模型生成的随机图保证了连通性，而且经过调整以后的核心网络图比由Ｗａｎｍａｎ随机生成的图具有更好的连通性，所以生成的核心网络是连通的；其次，树形拓扑在各自内部是连通的，这是因为由树的定义知道树是连通的；最后，核心网络和树形拓扑之间是连通的，因为生成图中所有树的根结点都是核心结点，树和核心网络通过根结点相连接，所以树和核心网络是连通的；综上所述，Ｃ—Ｔ算法生成的自治系统级拓扑图是连通的。生成Ｉｎｔｅｒｎｅｔ自治系统层次拓扑图算法研究与实现２．生成图链路故障分析Ｃ—Ｔ算法生成图对核心网络而言具有很稳定的性能，当某个核心自治系统结点发生故障时并不会影响整个核心网络的连通性。如果是根自治系统结点发生故障，那么对那棵树所有的结点来说是灾难性的，所有树中的结点都会与核心网络断开，但是由于在生成图中树的规模一般都比较小，所以并不会影响对大范围网络的研究；如果仅仅是根结点某条边发生链路故障就不会存在这样的问题，因为根结点是拓扑图中结点度最大的核心结点，当它的某一条链路发生故障时并不会对其连通性造成很大影响。４．５．３实验结果分析在ＣＰＵ为赛扬１．７Ｇ，２５６Ｍ内存和ＶＣ６．０的环境下进行实验。实验中，对参数《口，∥）取了表４－２中的四组值：对表４—２中每一组口，卢的值对应取了表４—３的其他参数值。表４－１Ｗａｘｍａｎ参数值口∥０．３Ｏ．１Ｏ．２Ｏ．２１２３４Ｏ．２０．０５Ｏ．３Ｏ．１表４－２其它参数值ＮｕｍｃｏⅣ５０８０１００１２０１５０Ｍ册丽３５６０７０９０１１０ＮｕｍＡ㈣３４３４３每一组参数值生成１０００幅拓扑图，下面把实验结果从结点度分布、树大小分布以及树深度分布等几个方面与从ＢＧＰ路由表直接分析的结果Ｈ”相比较。１．生成图结点度分布从图４—３可以看出，ｃ—Ｔ算法生成的自治系统拓扑图结点度的分布总体来说与直接从ＢＧＰ路由表数据分析的结果是很相近的，其中结点度小于７的结点分布比较接近，度大于８的结点分布有一定的偏差，度大于１０的结点在拓扑图里面几乎没有，这主要是由于在实验中选取的生成图结点数目偏少而造成的，另一方面，由实际ＢＧＰ路由表数据分析的结果表明在Ｉｎｔｅｒｎｅｔ中的自治系统有很小一部分度数较大结点，其对应于骨干自治系统结点，因而Ｃ—Ｔ算法生成的拓扑图在反映骨干结点方面并不很十分准确，骨干网络的层次并不突出。图４－３结点度分布图２．生成圈树大小分布图４－４树大小分布图图４—４表明：ｃ—Ｔ算法的生成图树大小的分布与分析结果是基本吻合的，由于实验生成圈的规模比较小而且对树平均大小参数设置得较小，因而没太大的树生成，结点少于７的树分布与分析结果是非常相似的。３．生成图树深度分布１０。，。０口分析结果。一ｃ．Ｔ算法实验结果芜越６０鑫５０霉３４。０：：厂１１２３＋树深度图４－５树深度分布４１生盛！：：！罂！：旦鎏丕竺星盗堑盐里箜鎏婴茎皇塞翌从图４—５可以看出，ｃ—Ｔ算法生成的图在树深度分布方面与分析结果是基本一致的，在Ｃ—Ｔ算法生成图中，深度为１和２的树与分析结果比较相近，但是实验的生成图中有很小一部分深度为３的树。４．５。４与其它模型对比下面将实验结果与其它模型在平均结点度、冗余度以及平均每跳直径等方面进行比较。ｃＴ算法生成的Ｉｎｔｅｒｎｅｔ自治系统拓扑图在平均结点度方面子其它层次模型是比较接近的，但是要高于Ｗａｘｍａｎ模型，这主要是由于在ＣＴ算法里面为了增强图的连通性添加了不少冗余边的原因，如图４－６（ａ）所示。而在冗余度方面远远高于Ｗａｘｍａｎ模型介于ＴＳ和Ｔｉｅｒｓ模型的冗余度之间，具有较大的冗余度，图４－６（ｂ），这也是由于分层的原因使得距离较近的结点连接路径变长，图４－６（Ｃ）。（ａ）平均结点度２００１９０１８０ｉ？Ｏｉ６０１５０１１０１３０ｆ～————１ｒ—————一！—ｒ“一一＿Ｗａｘｎｍｒｌ～（了ＴＳＴｉｅｒｓ（ｂ）冗余度