（计算机应用技术专业论文）internet自治系统级拓扑模型的优化与实现.pdf

摘要 复杂网络不同于以前的网络系统，它们是动态开放的，不断成长演化而且具 有生命的特点。复杂网络在局部层次上杂乱无序，而在整体层次上都呈现出小世 界、高聚类度和s c a l e f r e e 的特点。目前复杂网络的研究方兴未艾，特别是无标度 b a 网络模型的提出，引发了复杂网络的研究热潮。i n t e m e t 是现实世界中重要的 复杂网络之一，一直是研究的热点。i n t e m e t 作为当今人类社会信息化的标志，其 规模正以指数速度高速增长的同时，其“面貌”已与原型a r p a n e t 大相径庭， 依其高度的复杂性，可以将其看作一个由计算机构成的“生态系统”。虽然i n t e m e t 是人类亲手建造的，但却没有人能说出这个庞然大物看上去到底是个什么样子， 运作得如何。 i n t e m e t 的迅猛发展带来了一系列问题，如网络性能、资源预留和网络管理等 问题。由于在i n t e m e t 上实验非常昂贵而且因为一些商业因素的限制，研究者不可 能直接在i n t e r n e t 上模拟和仿真实验，因此研究者一般都利用网络拓扑模型进行实 验。i n t e m e t 拓扑建模能为网络问题的分析提供一个抽象模型结构，使很多问题易 于分析。拓扑模型研究经历了从随机型到层次型，再到幂律型的过程。然而目前 为止，没有一个公认的模型来全面描述i n t e m e t ，研究者只能希望能更好的“逼近” i n t e m e t 的实际拓扑。 本文主要进行了如下的工作： l ，分析了现有主流的拓扑模型及其算法，包括e r 、w a x m a n 、t i e r s 、t r a n s i t s t u b 、 b a 等模型，从节点度分布、聚类系数、特征路径长度等方面分析了各个模型的优 缺点。 2 提出了一种遵循幂律的网络拓扑生成算法p l o d + 。对传统p l o d 算法进行 了分析，在节点连接时添加了连通性检测，并对出度大的节点实行优先连接，较 好地解决了p l o d 算法存在的“出度贷款过剩”问题。实验结果表明了p l o d + 算 法的可行性和有效性。 3 提出了一种基于幂律的层次型网络拓扑生成算法h i p l 。研究表明层次性特 征和幂律分布是大型网络拓扑结构的两个固有的性质，这两个性质从不同的方面 反映出了大型网络的内在结构特性，层次性质是从宏观的角度反映了网络的结构 特性，而幂律则从微观的角度反映了网络中节点的分布规律。各种现存的拓扑生 成算法只能在某个方面反映网络的性质。h i p l 算法很好地将幂律分布规律融入到 层次型拓扑生成算法中，解决了原先的层次型拓扑模型不满足幂律分布规律的问 题。通过对群集系数、直径、平均度数等拓扑参数的比较，表明了h i p l 的有效性。 关键词：复杂网络，拓扑建模，i n t e m e t ，幂律，层次型 a b s t r a c t i nt h ep a s tf e wy e a r s , t h e r eh a sb e e ni n c r e a s i n gi n t e r e s t i ns t u d y i n gc o m p l e x n e t w o r ka sr e l e v a n tt om a n ya “瑚o f s c i e n c e c o m p l e xn e t w o r ki sd i f f e r e n tf r o mf o r m e r n e t w o r li ti sd y n a m i c ，g r o w i n g ，a n dg r e a t - h e a r t e d i nt h ep a na s p e c t , c o m p l e xn e t w o r k i sd i s o r d e r b u ti nt h ew h o l ea s l 始c t , c o m p l e xn e t w o r kh a ss m a l l - w o r l d ，h i 曲_ c 1 1 l s t e r e d a i l ds c a l e - 丘o ec h 铀蔺c t c ts i i l c eb am o d e lw a sp u tf o r w a r d , t h e r eh a sb e e nag r e a t c o n c e r t io nc o m p l e xn e t w o r k 1 1 i u t e r n e th a se x p e r i e n c e dat r e m e n d o u sg r o w t hi ni t s s i z ea n dc o m p l e x i t ys i n c ei t sc o m m e r c i a l i z a t i o n u n t i ln o w , e i t h e rn e t w o r kr e s e a r c h e r s o rp e o p l ew h or e s e a r c ho nt o p o l o g yt h e o r yh a v ea g r e eo nau n i f i e dm e t r i c s 辩tt o c h 羽鼍c 吲z eat o p o l o g yg r a p h t h e r e f o r e 。i ti ss t i l la no p e nq u e s t i o nf o rr e s e a r c h e r s 。 m a n yt o p 0 1 0 9 yg e n e r a t o r sh a v eb e e nc r e a t e dt om o d e ln e t w o r k , e s p e c i a l l yi n t e r n e t , t oi m p l e m e n ts i m u l a t i o n s a st h eb a s eo fi n t e m e td e v e l o p m e n ta n de x p l o i t a t i o no n h i g h e rl e v e l s , t h ei n t e m e tt o p o l o g ym o d e l i n gm a r t s 毓t h er a n d o mm o d e lt ot h e h i e r a r c h i c a lm o d e l t h e ni td e v e l o p e dt oam o r er e a l i s t i co n e ，t h es c a l e f l e en e t w o r k m o d e l b a s e d0 nt h er e s u l t so f f o r m e rr e s e a r c h e r s w eh a v ed o n et h er e s e a r c ha sf o l l o w s ： 1 w ea n a l y z ec u r r e n tm a i nt o p o l o g ym o d e l ss u c ha sw a x m a na n ds o0 1 1 t h i n k i n g a b o u ta v e r a g ed e g r e ea n dc l u s t e r i n gc o e f f i c i e u ta n dc h a r a c t e r i s t i cp a t hl e n g t h , w e c o m p a r et h ea d v a n t a g ea n dd i s a d v a n t a g eb e t w e e nc m r 胁tt o p o l o g ym o d e l s 2 w eh a v es t u d i e da sl e v e lt o p o l o g yo fi n t e m e ta n dt h ef o r mo fp o w e r - l a w p l o di san e t w o r kt o p o l o g yg e n e r a t i n ga l g o r i t h mf o rp o w e r - l a w s b u tp l o dc a n n o t g u a r a n t e e t h e c o n n e c t i v i t yo ft h et o p o l o g y f u t h e r m o r e ，p l o dh a st h e “c r e d i t o v e r s t o c k p r o b l e m b a s e do np l o d ，p l o d + a d d st h ec o n n e c t i v i t yc h e c ka n dg i v e sl i n k p r e f e r e n c et on o d e sw h i c hh a v em o r eo u t - d e g r e e s p l o d + e n s u r e st h ec o n n e c t i v i t ya n d m i t i g a t e st h e c r e d i to v e r s t o c k p r o b l e m t h ee x p e r i m e n ti n d i c a t e sf e a s i b i l i t ya n d e f f i c i e n c yo f p l o d + 3 r e c e n tw o r kh a ss h o w nt h a tt h ei n t e m e tt o p o l o g yh a st w op r o p e r t i e s ：( 1 ) t h e i n t e m e ti sah i e r 缸c h i c a ln e t w o r k ；( 2 ) t h ei n t e m e tt o p o l o g yi na s l e v e lf o l l o w s p o w e r - l a wd e g r e ed i s t r i b u t i o mb yi n t e g r a t i n gt h ep o w e r - l a wd e g r e ed i s t r i b u t i o na n dt h e h i e r a r c h i c a ls t r u c t u r e ，w ep r e s e n tah i e r a r c h i c a ln e t w o r kt o p o l o g yg e n e r a t i n ga l g o r i t h m f o rp o w e r - l a wh i p l h i p li sv e r i f i e db ys i m u l a t i o n w i t ht h ep a r a m c t c r si d e n t i f i e d f r o mr e a li n t e m e td a 饥h i p lc a p t u r t h eh i e r a r c h i c a ls t r u c t u r ea n dp o w e r - l a wd e g r e ed i s t r i b u t i e n w e l l t h ee x p e r i m e n t sc o i k ：锄w i t ht h et o p o l o g i c a lp r o p e r t i e ss u c ha s c l u s t e r i n gc o e f f i c i e n t , d i a m e t e r , a v e r a g ed e g r e ea n d o i l k e y w o r d s ：c o m p l e xn e t w o r k ，t o p o l o g ym o d e l i n g ，h i e r a r c h i c a l ，i n t e r n e t , p o w e r - l a w 高飞i n t e m e t 自治系统级拓扑模型的优化与实现 第1 章绪论 随着计算机及通信技术的飞速发展，i n t e m e t 己经渗透到社会生活的各个方面， 对社会进步与经济发展起着越来越重要的作用，也使人们的工作方式甚至生活方 式发生了巨大的变革。当人们越来越依赖i n t e r n e t 时，就会关心如何保持i n t e m e t 良好的运行，如何对i n t e r n e t 进行优化，如何增强管理者对网络容量的了解和控制 能力，如何及时发现i n t e m e t 运行过程中出现的故障、报告故障问题、判断故障原 因并尽快解决网络故障。 i n t e m e t 作为当今人类社会信息化的标志，其规模正以指数速度迅猛增长。 i n t e m e t 拓扑模型是在更高层次上开发利用i n t e r n e t 的基础。i n t e m e t 拓扑作为 i n t e m e t 这个自组织系统的“骨干”，与流量、协议共同构成模拟i n t e m e t 的3 个组 成部分。i n t e r n e t 拓扑建模是一项复杂的工作，涉及网络测量、图论、算法设计、 统计学、数据挖掘、可视化以及数学建模等多个研究领域。 1 1复杂网络研究背景 网络是一个由许多节点及连接节点的边组成的集合。其中节点用来代表真实 系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某 种特定的关系则连一条边，有边相连的两个节点被看作是相邻的。系统所表现的 网络形式在现实世界到处可见。例如，i n t e r a c t ，w 砌dw i d ew e b 、社会关系网络或 是其它在个人之间、组织之间、商业公司之间具有联系的网络，以及神经网络、 代谢网络、食物链网络、分布式的血管网络等。 1 7 3 5 年，数学家欧拉对著名的哥尼斯堡七桥问题的解答开创了对图论的研究。 两百多年来，对网络理论的研究经历了三个阶段。在最初的一百多年里，科学家 们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上 的欧几里德格子，它看起来像是格子衫上的花纹；又或者最近邻环网，它总是会 让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了十九世纪五十年代末，数 学家们想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否 不再是确定的事情，而是根据一个概率决定。数学家把这样生成的网络叫做随机 网络，它在接下来的四十年里一直被认为是描述真实系统最好的网络。直到最近 几年，由于计算机数据处理和计算能力的飞速发展，科学家们发现大量的真实网 络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网 2 扬州大学硕士学位论文 络。这样的一些网络被科学家们叫做复杂网络，对于它们的研究标志着第三阶段 的到来【1 l 。 遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义。比 较流行的一种观点是：复杂网络不同于以前的网络系统，它们是动态开放的，不 断成长演化具有生命的特点，在局部层次上杂乱无序，而在整体层次上都呈现出 小世界、高聚类度和s c a l e - f r e e 的特点1 2 , 3 1 。 很多人都尝试着对现实复杂网络进行分类，但是根据一套标准来进行严格的 分类往往比较困难。美国的一些科学家在( n e t w o r ks c i e n c e2 0 0 5 中将现实的复 杂网络大致分为四类：生物网络、技术网络、信息网络、社会网络。随着互联网 技术的发展和大量数字化信息的传播，信息网络越来越成为一类典型的大量存在 的重要网络，而且信息网络包含了上述物理网络和社会网络中的一部分典型例子。 在复杂网络的诸多统计特征中最重要的是小世界效应和无标度特性删。如果 网络中的两个节点可以通过一些首尾相连的边连接起来，我们就说这两个点是可 达的，并把连接它们所需要的最少的边的数目叫做它们之间的距离，显然，这两 个点之间的距离总是比网络拥有的节点总数要小。如果两个节点是不可达的，我 们就令它们之间的距离等于网络的节点总数。把所有节点对的距离求平均，就得 到了网络的平均距离。另外一个叫做簇系数的参数，专门用来衡量节点集聚成团 的情况。对于某个节点，它的簇系数被定义为它所有相邻节点之间连边的数目占 可能的最大连边数目的比例。类似的，网络的簇系数则是所有节点簇系数的平均 值。研究表明，规则网络具有大的簇系数和大的平均距离，随机网络则具有小的 簇系数和小的平均距离。1 9 9 8 年，物理学家通过以某个很小的概率改变规则网络 中边的连接方式构造出了一种介于规则网络和随机网络之间的网络，它同时具有 大的簇系数和小的平均距离，因此既不能当作规则网络处理，也不能被看作是随 机网络。后来物理学家把大的簇系数和小的平均距离两个统计特征合在一起称为 小世界效应，具有这种效应的网络就是小世界网络唧。 高飞i n t e r n e t 自治系统级拓扑模型的优化与实现 圈1 1 小世界网络结构示意图 科学家们对大量的真实网络，比如电力网络、计算机互联网、食物链网络、 演员关系网、科学家合作网络等等做了大量实证性的研究，发现它们几乎都是小 世界网络，同时，他们还发现了真实网络的另一重要统计特征，即节点度服从幂 律分布。节点度是指一个节点拥有相邻节点的数目，节点度服从幂律分布就是说 具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地 表示。幂函数曲线是一条下降相对缓慢的曲线，这使得我们不仅能在网络中发现 大量度很小的节点，还能找到一些度很大的节点。如图1 1 中的规则邻环网络，随 机网络和小世界网络的节点度分布都不是服从幂律分布的，它们的分布区间非常 狭窄，几乎找不到偏离节点度均值较大的点。对于这样的网络，上述均值就可以 被看作衡量其节点度的一个特征标度，在这个意义上，我们把节点度服从幂律分 布的网络叫做无标度网络，并称这种节点度的幂律分布为无标度特性【l o j 。 图1 2 无标度网络结构示意图 上个世纪9 0 年代末，两篇著名的文章引起了广大研究人员的普遍关注。w a t t s 4 扬州大学硕士学位论文 和s t r o g a t z 于1 9 9 8 年在 n a t u r e ) 上发表的论文表明能够产生高聚团性和短路径 的网络模型。b a r a b a s i 和a l b e r t 于1 9 9 9 年在s c i 即c e 上发表的论文表明大规模 真实稀疏网络的节点连接度分布是幂函数形式，他们提出的一种自由标度网络模 型能够预测这种规律。最近5 、6 年以来，大规模复杂网络的研究成果、影响范围、 参与人的数量等都出现了“涌现”现象。目前，复杂网络研究涉及到的范围超过 了我们在上面提到的所有真实网络研究领域。大量关于复杂网络的文章在s c i e n c e ， n a t u r e ，p n a s ，p r l 等国际一流的刊物上发表，从一个侧面反映了复杂网络己经成 为国际学术界一个新兴的研究热点。一个明显的例子是，如果我们通过g 0 0 9 l e s c h o l a r 搜索的话，上述两篇文章被人们引用的次数己经超过了1 5 0 0 次。 到目前为止，针对复杂网络研究的基本问题可以简单概括为五个方面密切相 关却又依次深入的研究内容： ( 1 ) 通过实证方法度量和分析网络的统计性质【1 i 】：具体目的是发现复杂网络的 一些统计特征，例如路径长度、连接度分布、拓扑结构的层次化与聚团性特征等， 并研究相关特征的有效评价方法； ( 2 ) 构建相应的网络模型来理解这些统计性质何以如此：主要为复杂网络建模 研究【1 2 1 。其目标是提出一种相对严谨、可计算的形式化模型，在此基础上分析和 解释网络所具有的拓扑与功能相关的特征； ( 3 ) 在己知网络模型基础上，发现或者挖掘出与功能和语义相关的深层内容。 例如针对信息网络的信息内容挖掘，针对生物信息网络中的功能挖掘等，针对社 会网络中的社会关系发现等； ( 4 ) 在己知网络的结构特征及其形成规则的基础上，预测网络系统的行为。包 括对网络拓扑和功能涌现现象的预测，网络传播行为的预测等； ( 5 ) 设计新网络、引导现有网络演化的复杂网络控管理论研究。例如，p 2 p 网 络构建，社会舆论传播引导等方法手段的研究。 上面五类研究内容层层深入、相互关联。 1 2因特网拓扑建模综述 i n t e r n e t 是复杂网络的一个应用实例。i n t e m e t 作为人类社会信息化的标志，已 经广泛应用到社会生活的各个方面，其规模正以指数速度高速增长，如今i n t e m e t 的“面貌”与其原型a r p a n e t 己大相径庭”】。依其高度的复杂性，可以将i n t e r n e t 看作一个由计算机构成的“生态系统”。虽然i n t e m e t 是人类亲手建造的，但却没 有人能说出这个庞然大物看上去到底是什么样子，运作得如何。i n t e r n e t 由自治系 高飞i n t e m e t 自治系统级拓扑模型的优化与实现 5 统构成，自治系统独特的工作方式、复杂的相互关系和自身属性很大程度上决定 了整个i n t e m e t 的流量和行为。近年来随着i n t e m e t 重要性的日益提高和网络构成 的日益复杂，人们发现越来越有必要对i n t e r n e t 整体拓扑结构和自治域的工作情况 进行深入的了解、分析，以利于研究i n t e m e t 的发展规律，优化网络配置，加强网 络维护和管理，使i n t e m e t 能够健康、快速的发展。 i n t e m e t 拓扑建模就是探求在这个看似混乱的网络之中蕴含着哪些还不为我们 所知的规律。发现i n t e m e t 拓扑的内在机制是认识i n t e m e t 的必然过程，是在高层 次上开发利用i n t e m e t 的基础。然而，i n t e r n e t 与生俱来的异构性、动态性、发展 的非集中性以及其庞大的规模都给拓扑建模带来巨大挑战【1 4 1 。i n t e m e t 拓扑建模至 今仍然是一个开放性问题，在计算机网络研究中占有重要地位i l ”。基于上述原因， 对i n t e m e t 拓扑研究及拓扑图生成尤其是自治系统级拓扑研究已经成为学术界、企 业界所普遍关心的重要问题之一。 2 0 世纪9 0 年代以来，i n t e m e t 在世界范围内迅速发展，1 9 9 2 年约有1 0 0 多万 台主机接入i n t e m e t ，1 9 9 6 年约有1 2 8 8 多万台主机接入i n t e m e t ，到了2 0 0 1 年约有 1 0 9 5 7 多万台主机接入i n t e m e t 。网络的复杂性、业务的多样性和接入的随机性使 其结构不断的变化，从网络安全、网络管理及网络研发各个方面都越来越需要深 入了解i n t e r n e t 整体的拓扑结构，分析其结构行为，以提出优化网络配置的合理建 议。因此探测i n t e m e t 拓扑结构成为了目前的一个研究热点。 i n t e m e t 拓扑作为i n t e m e t 这个自组织系统的“骨骼”，与流量、协议共同构成 模拟i n t e m e t 的3 个组成部分，即在拓扑网络中节点间执行协议，形成流量。i n t e r n e t 拓扑模型是建立i n t e m e t 系统模型的基础，由此而体现出的拓扑建模意义也可以说 就是i n t e m e t 建模的意义，即作为一种工具，人们用其来对i n t e m e t 进行分析、预 报、决策或控制。i n t e m e t 模型中的拓扑部分刻划的是i n t e m e t 在宏观上的特征， 反映一种总体趋势，所以其应用也都是在大尺度上展开的。 i n t e m e t 拓扑在建模分析、预测以及管理i n t e m e t 等方面有着重要的意义，当 前对i n t e m e t 拓扑模型的需求主要来自以下几个方面： ( 1 ) 许多新应用或实验不适合或者不能够直接应用于i n t e m e t ，其中一些具有危 害性，如蠕虫病毒在大规模网络上的传播模拟i l6 j ； ( 2 ) 对于一些依赖于网络拓扑的协议( 如多播协议) 【1 7 1 ，在其研发阶段，当前 i n t e n l e t 拓扑只能提供一份测试样本，无法对协议进行全面评估，需要提供多个模 拟拓扑环境来进行实验。同时还可以为仿真模拟i n t e m e t 环境、协议设计与评价提 供研究基础：为与拓扑结构相关的算法性能改进提供依据； 6 扬州大学硕士学位论文 ( 3 ) 从国家安全角度考虑，需要在线控制网络行为，如美国国防高级研究计划 局的n m s 项目； ( 4 ) 进行宏观网络发展布局以及辅助网络管理：如增加新路由器、网络扩容、 从宏观层次管理规划大范围内的网络发展布局以缩小地区间差距等：拓扑图可以 帮助选择多镜像服务器的位置、确定连接哪个i s p 能获得最小延迟与最大有效带 宽等； ( 5 ) 为防范大规模网络攻击、分析大规模网络自动攻击( 如分布式拒绝服务攻击) 的发起范围、控制病毒传播范围以及故障隔离等提供研究平台和预警手段，使国 家对全网络更具宏观控制力。 总而言之，目前对i n t e r n e t 拓扑研究的需求是来自各方面的，既有网络管理、 应用研究也有网络安全等方面的需要，开展i n t e r n e t 拓扑研究是具有十分重要的实 际意义的。 i n t e r n e t 拓扑建模是一项复杂的工作，涉及网络测量、图论、算法设计、统计 学、数据挖掘、可视化以及数学建模等多个研究领域。i n t e m e t 拓扑建模研究内容 可归结为如下几个问题： ( 1 ) i n t e m e t 网络拓扑数据获取：如何获取一份完整而且准确的i n t e m e t 网络拓 扑数据是一项困难而复杂的工作。由于i n t e r n e t 庞大而且复杂，如果现有的技术条 件下获取一份完整的拓扑数据几乎是不可能的。目前来说，虽然己经提出了多种 方法，但怎样获得一份更加完整的i n t e m e t 网络拓扑数据仍然是研究领域中需要进 一步解决的问题。 ( 2 ) i n t e r n e t 网络拓扑特征发现：i n t e r n e t 虽然是庞大而复杂的，但它自身仍然存 在着某些规律和特征等待我们去探索。在过去的几年里，i n t e m e t 网络拓扑特征发 现一直是i n t e r n e t 网络拓扑研究领域中的热点问题，通过研究人员的不断努力，一 些新奇的网络拓扑特征逐渐的探索出来。 ( 3 ) z n t e r n e t 网络拓扑建模：i n t e r n e t 网络拓扑建模是利用已经发现的拓扑特征把 i n t e m e t 描述和刻划出来。 ( 4 ) i n t e r n e t 网络内部关系分析：当我们得到一幅i n t e m e t 网络拓扑图后，如何 理解和认识图内节点关系也是目前i n t e m e t 网络拓扑研究的热点问题。 i n t e m e t 网络拓扑研究也经历了发展的过程。最初的i n t e m e t 网络拓扑研究由 于缺乏数据，只能进行经验假设，现在已经可以针对相对完整的数据进行统计分 析，并可对各种假设进行验证。从1 9 9 5 年开始，大规模的i n t e m e t 拓扑测量工作 逐渐展开1 1 8 , 1 9 1 ，到目前为止已经收集到了大量的拓扑数据 2 0 - 2 2 。这些拓扑数据相 高飞i n t e m e t 自治系统级拓扑模型的优化与实现 7 对完整，为i n t e m e t 网络拓扑研究者提供了有利的实验数据支持田j 。早期对i n t e r n e t 网络拓扑的特征更是无从认识，现在一些研究成果已经把i n t e m e t 网络与复杂系统 特征研究结合起来。i n t e m e t 网络拓扑的建模工作也取得了长足的进展，从相对简 单的随机模型到复杂的幂律模型，其结果都越来越接近真实的i n t e m e t 。对于节点 间关系的理解更是有了质的突破，从原来对关系的一无所知到现在对关系进行定 义和区分 2 4 , 2 卯。所有这些都说明了i n t e m e t 网络拓扑研究在过去的一些年里取得的 一些成果。即便如此，如果想准确回答i n t e m e t 网络拓扑所提到的几个问题，仍然 还有不小的差距，而且一些新的发现也对己有的成果提出了挑战。 最早的网络拓扑模型是w a x m a n 于1 9 8 8 年提出的一种平面随机模型一 w a x m a n 模型闭，这个模型一直沿用了很多年。随机网络模型认为i n t e r n e t 拓扑处 于一个完全无序的状态，在大尺度上是均一的，出度频率呈泊松分布。1 9 9 6 年， d o a r 提出了t i e r s 等级模型【2 7 l ，该模型刻划了i n t e m e t 所具有的层次特征。1 9 9 7 年， z e g u r a 等人提出了另一种层次模型- - t r a n s i t - s t u b 模型幽j 。层次型拓扑模型来自对 i n t e m e t 结构所具有的层次特征的认识，在同一层上的节点出度接近，不同层问节 点出度差别很大。对同一层上的节点布置借用w a x m a n 模型方法。在己有的研究 成果中，1 9 9 9 年f a l o u t s o s 等人发现i n t e m e t 拓扑结构中存在的幂律关系( p o w e r - l a w s ) 占据极为重要的地位 2 9 - 3 ”。幂律说明在i n t e r n e t 中既不存在w a x m a n 模型中那样的 “平等”，也不像t i e r s 和t r a n s i t - s t u b 模型那样“等级森严”，而是具有一种松散 的层次性。幂律同时说明i n t e m e t 具有高度非均一性，即少数节点具有很高的出度， 而大量节点具有较小的出度。同时，幂律的发现也给出一个启示：i n t e r n e t 中某个 属性值的平均值不能准确地刻划这一属性，应该尝试用某个指数来进行刻划。幂 律的发现将i n t e m e t 拓扑与一些生物学、社会学中的复杂网络联系起来 3 3 - 3 6 1 ，使其 成为无尺度网络的一个实例，在i n t e m e t 拓扑研究与系统学研究之间架起了一座桥 梁1 3 7 。2 0 0 0 年以来，研究人员开发了许多遵循幂律的拓扑生成算法以及拓扑生成 器i 3 8 4 0 ，为i n t e r n e t 拓扑建模提供了有力的支持。 1 3 研究基础和相关定义 i n t e m e t 拓扑通常形式化表示为无向图g ，g 气玎d ，其中p f v l v 是g 中的 一个节点 ，点三 ( v ) l ，v v i i v 相邻接 ，g 表示为邻接矩阵 厶设磊表示节点 1 ，的出度，毋= 俐( 甜，o e e 。设五表示节点出度频率，后= 叫v 矿且蝴 8 扬州大学硕士学位论文 1 3 1自治系统级拓扑概念 对i n t e m e t 拓扑图的研究可以分为两个抽象层：路由器( r o u t e r ) 级拓扑图【4 l 】和 自治系统( a u t o n o m o u ss y s t e m ) 级拓扑图。路由器级拓扑图刻划物理路由器问的连 接关系，反映数据实际的流动方向和路径【4 2 , 4 3 1 。自治系统级拓扑图刻划不同自治 系统之间的连接关系和路由更新策略1 a 4 , 4 5 1 。 i n t e r n e t 是由成千上万的主机和设备通过路由器连接而成。由于历史发展原因 和管理上的需要，各种设备并不是毫无规则的连接在一起，而是划分为自治系统。 一般而言，一个自治系统既可以是拥有同一选路策略、在同一技术管理部门下运 行的一组路由器的组合，也可以是工作在一起提供内部选路的内部网关协议以及 相关设备的汇集，在实际操作中可以把一个i s p 看作一个自治系统。在外部世界 看来，整个自治系统是一个单一的实体。每个自治系统都有一个由因特网登记处 或i s p 分配的识别码。自治系统是i n t e m e t 的组成部分，自治系统级拓扑是i n t e r e n t 网络状况的反应。网络接入前，必须向因特网注册机构申请自治系统号码，填写 有关自治系统的基本信息。 自镕末轴 一 自治系统阃的关联荚蕞 图1 3 量基本的自治系统级拓扑圈 i n t e r e n t 自治系统级拓扑图是以自治系统为基本单位，分析它们之间的互联关 系，拓扑图中所有节点都表示自治系统，边表示自治系统之间的关联关系。有些 自治系统节点存在很多关联节点，称之为主干自治系统，它们负责为其它自治系 统转发消息：有些自治系统节点的邻接节点比较少，处于网络的边缘，被称为边 界节点。研究者发现i n t e r a c t 中自治系统级拓扑图具有两个特性：自治系统域具有 很高的增长速率：自治系统域之间的对等连接有一个递增的概率。根据上述两点， 研究者很想定量的知道当i n t e m e t 不断发展进化的时侯，节点之问是以怎样的方式 连接的。 通过把路由器划分为独立管理的自治系统，网络管理者为i n t e m e t 提供更加结 高飞i n t e m e t 自治系统级拓扑模型的优化与实现 9 构化的模式。自治系统问通过外部网关协议b g p 互相沟通。早期的i 曲；m c t 使用 的外部网关协议是e g p ，虽然使用很广泛，但是它在处理选路循环和设置选路策 略时对拓扑结构有限制而且效率低，这就要求一种更先进的协议出现。当前，b g p - 4 是i m m c t 选路的实际标准，它是一种距离矢量协议，除标准距离矢量属性以外， b g p 使用了路径向量技术以消除选路循环。 目前大多数大型服务提供商在自治系统内部选路使用链路状态协议。主要是 因为它能够快速收敛。这些协议中使用最广泛的是开放式最短路径优先协议( o s p f l 和中间级系统到中间级系统( i n t e r m e d i a t es y s t e m t oi n t e r m e d i a t es y s t e m ) 协议。许多 老的服务商选择中间级系统到中间级系统协议作为内部网关协议( i g p ) ，而一些新 的提供商选择o s p f 协议或者i g p 协议。i g p 协议能够支持无分类网络协议和m 网络层信息，而o s p f 协议只支持m 信息。目前o s p f 协议和i g p 协议都在i s p 网络中广泛使用，其成熟和稳定的特性使它在大型网络中得以快速发展。 自治系统间选路和自治系统内部选路的根本区别在于前者通常反应了网络或 者公司间的行政和业务关系，而后者通常根据需要的技术来优化。经过实际调查， 当前国内电信各个省网之间与国外出口间配置的都是b g p 4 协议。各个省网之内， 一般配置i g p 协议，个别网络内部设置o s p f 协议，教育网基本使用静态路由。 自治系统的相互关系反映的是实际i n t e m e t 中的各自治系统之间是以什么方式 相关联。根据不同的研究目的和方式对自治系统间关系的界定有不同的方法。在 目前众多关系界定中，与实际最接近的是从商业及i s p 的角度的分类，把h n e m e t 中的自治系统关系分为三类：提供者客户关系( c u s t o m e r p r o v i d e r ) 、对等关系 ( p e 既，p r ) 和兄弟关系( s i b l i n g s i b l i n g ) 。 自治系统级拓扑和传统路由器级拓扑一个最主要的区别就在于自治系统问的 选路协议b o p 是基于策略的路由协议，管理域间的商业契约关系对i n t e r n e t 结构 和端到端性能特性起关键作用，如果两个相连接的自治系统之间没有签订商业契 约，即使它们在物理上是连接的两者之间也没有业务量，无法互相通信。 在h t e m e t 的应用中，自治系统之间的关系是一种非常重要的资源，它可以使 人们更好地理解i n t e r a c t ，从而更加方便的利用、开发以及管理i n t e r n e t 。但是h t e m e t 中自治系统之间的相互关系是难以直接获取的，这是因为：多个自治系统间的连 接关系，属于企业内部的私有协定，i s p 不愿透露其中的商业秘密，外界很难得到 其真实的拓扑结构；目前还没有专门的机构来记录自治系统之间的关系，即使有 记录信息也不完备：同时i s p 之间结成的商业关系是不断变化的，而现有库中的 某些信息往往更新速度较慢，不能反映当前网络状况。 1 0 扬州大学硕士学位论文 所以，自治系统的各种属性信息是一种重要的网络资源，对于网络管理和保 持网络健康发展有重要意义。可以利用自治系统间的关系设计和优化网络，为管 理域的负载平衡、拥塞避免提供参考；在研究自治系统间关系的基础上，可确定 自治系统在i n t e r n e t 中的等级，为企业或小的i s p 提供网络接入，为商业协议提供 依据；比较自治系统级拓扑图中的逻辑关系和自治系统间的真实关系，发现故障 点，减少误配现象，指导并调试路由器配置文件。 目前，收集自治系统连接关系的主要方法有查询w h o i s 数据库方法和主动探 测方法。w h o i s 数据库中的连接信息都是在申请自治系统号码时的资料，而i s p 之间的关系是短暂易变的，因而w h o i s 数据库信息很难反映当前网络的实际路由 状况，也无法专门用来构造反映实际网络情况的自治系统级拓扑图，但是基于 w h o i s 数据库上其它的静态信息，比如自治系统名称、描述、所属国家、管理者 等等具有可参考的价值，而且难以以其它方式得到，可以用来作为b g p 路由信息 的有效补充。主动探测方式虽然获得信息量较大，但由于自治系统的范围较大， 小范围内无法起作用，而面对整个i n t e m e t ，必须尽量全面的探测才能够得到较好 的结果。这种方法会给网络带来很重的负担，而且多点测量，往往需要较大的软、 硬件开销。对于每次探测得到的m 链路，查询b g p 路由表，映射得到自治系统的 路径，从而构造出自治系统级拓扑图。 1 3 2 实验数据 本文的数据来源是b g p 路由表数据嗍。b g p 是当今网络中实现路径选择的一 种外部网关协议，在t c p 口网络中实现域间路由。在收集自治系统级的i n t e m e t 网络拓扑数据时，利用b g p 路由信息通常是比较常用的方法。它在多个自治系统 间执行路由，与其它系统交换路由和可达性信息。b g p 设计已代替其前身、外部 网关协议e g p 而作为全球i n t e m e t 的标准外部网关路由协议。它解决了e g p 存在 的严重问题，更能有效地适应i n t e m e t 飞速发展。在收集b g p 路由表信息的方法 中通常采用路由对等监听的方法。这种方法是监测域内i g p 路由或域间b g p 路由 的主要手段。专门收集路由信息的设备上运行i g p 或者b g p 路由协议，与要监测 的路由器建立i g p 或者b g p 对等关系，被监测的路由器把路由信息收集设备看成 它的一个邻居，像其它邻居一样，发送路由更新信息。路由信息收集设备不参加 实际的选路过程，路由表的变化也不向外传播。它只是被动地监听对等路由器的 活动情况。 这种方法可以获得对等路由器的路由表和路由更新消息，能更为直接地监测 高飞i n t e m e t 自治系统级拓扑模型的优化与实现 li 网络路由的状况。我们可以根据收集到的信息分析路由活动情况，推测网络的拓 扑和路由。对等路由器的选择是一个重要问题，对监测结果是否全面有效有直接 影响。一般情况下选择被监测网络中的骨干路由器。如果与多个路由器对等，网 络中会有大量到路由信息收集设备的路由信息流量，这会消耗较多的带宽资源， 也要求路由信息收集设备有很高的性能。 对于构造和分析自治系统级的网络拓扑来说，一个重要的工作就是如何获取构 造网络拓扑的底层数据1 4 7 1 。一般来说，可以根据b o p 路由器的路由表来推断自治 系统间的连接性。自治系统间的逻辑关系，仍然可以通过这种路由表信息进行推 断。但是，少数的路由表信息很难获取自治系统间完整的连接性，更无法推断它 们之间的逻辑关系。因此，如何获取足够多的路由表信息就成为构造和分析自治 系统级网络拓扑的重要工作。 b o p 没有对i n t e r a c t 基本拓扑结构加以任何限制，它假定自治系统内部的选路 己经通过内部选路协议完成了。内是指在一个实体内部选路，外是指在实体之间。 通过在b o p 相邻体之间交换信息，b o p 构造了一个自治系统图。这个导引的图形 有时叫作树。就b g p 而论，因特网就是一个自治系统图，每个自治系统用自治系 统号码来识别。两个自治系统之间的连接形成一条路经，路径信息的汇集形成到 达特定目的地的路由。b g p 使用这些与既定目的地相关的路径信息来确保无循环 域问选路。 图1 4 自治系统间的b b p 数据示意图 为了能有效的传播消息，边界路由器之间不断交换更新的b g p 路由信息，这 些b g p 路由信息存放在每一个b g p 路由器的路由表中。从1 9 9 7 年1 1 月开始， n a t i o n a ll a b o r a t o r yf o ra p p l i e dn e t w o r kr e s e a r c h 就开始每天从路由服务器 m u t e - v i e w s o r e g o n - i x n e t 上采集b o p 路由