【精品】关于Internet拓扑的综述.doc

《【精品】关于Internet拓扑的综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关于Internet网络拓扑的综述近年來山于网络大规模的使用以及并口云计算的兴起也是对于大规模的复杂Internet网络拓扑分析研究引起了计算机及物理、数学筹多个领域研究人员的兴趣，并口•这种兴趣逐渐的演变为对网络拓扑技术研究的热潮。然Iflj,Internet网络自身具有复杂性和多变性，直接导致把它实验对象进行研究和分析变得十分困难.因此，人们希望根据真实网络数据和关键特征对Internet网络拓扑进行模型抽象，以拓扑模型代替真实Internet网络作为实验对象进行研究分析，达到通过拓扑建模认识，然后利用这些认识的网络的拓扑结构去指导我们具体的实践。第一章网络拓扑的参

2、数和典型网络模型M2]1.1网络拓扑参数要能対网络拓扑特性进行描述，我们要有一些具体的参数进行度量，主要包括节点度分布，聚集系数，介数，核数和平均路径长度。(1)节点度分布P伙)：节点度分布pg函数定义为网络屮度数为k的节点个数占总节点数的比例，也等于在随机一致原则下挑选出的节点具有度数k的概率；所有节点度Z和的平均值则称为网络的节点平均度〈k>.规则图中：所有节点拥有相同数量的边，即节点的度分Y

3、JP(k)函数为定值；随机图中：节点的度分布遵循泊松分布，大多数网络节点的度都集中于网络节点平均度门P附近，远离峰值的节点数呈指数衰减，即随机图中一个节点拥有k条边(七大于等

4、于节点平均度)的概率很小：无标度网络中：节点的度分布接近幕律形式分布p(k)-k-r.(2)聚集系数：聚集系数(clusteringcoefficient)是从全局來刻画网络的聚集特性的度最指标，用來刻画一个节点邻居之间的亲疏程度.有3种不同的衡最聚集特性的参数。分别为：局部聚集系数C(k)：c伙)"％”伙)]/伙伙-1)/2式1.1其中[加祕伙)]表示节点度为k的节点的邻居之间平均存在的连接数・平均聚集系数:具中，P(k)表示图中任意一个节点的度数为k的概率，即节点的度分布.全局聚集系数：式1.3工P伙)[‘％(切]工P(k)(k—)C(k)士P伙冰伙j)匚k(1)

5、介数：介数也是Internet网络拓扑的一个重耍度量，分为节点介数和边介数.其中，节点介数衡量了通过网络中该节点的最短路径的数目，反映了节点在网络中的枢纽性，节点介数越大，说明这个节点的枢纽性越强，删除这样的节点会造成大量节点对Z间的最短路径变长：边介数定义为在网络的所有最短路径中，通过某条边的最短路径的条数，类似地，边介数也同样反映了该边在网络中的枢纽性.若用爲表示节点i和j之间最短路径的数目，1表示节点或边，岛⑴代表节点i和j之间通过1的最短路径的条数，从而得到介数的数学表达为：B]=工第(/)/第式14,=1介数是能够体现流量特性的性能度量指标，关系到链路带宽以及

6、路山器节点的利用率等，尤其是在基于最短路径生成的网络中.(2)核数：若一个节点存在于k-核，而在(k+1)-核中被移除，则称这个节点的核数为k；其中，k-核是指原始图经过迭代消去所有节点度小于或等于k的节点后得到的子图.一个核数为k的节点可以出现在k核子图中，但不会出现在(k+1)核的子图里，我们也把所有节点核数中的最大值称为图的核数.节点核数在某种程度上说是比节点度数更反映关联性的度量指标，可以表明节点在核中的深度.若一•个节点的肖点度数很高而同吋节点核数很小，则说明其关联并不紧密.(3)平均路径长度：平均路径长度代表所有节点对之间的距离的均值，定义为I=-——，(I

7、a式1.5—h(h+1)⑴2其屮，心表示节点i到节点jZ间的最短路径.该度最指标用于刻画网络的连通性。1.2典型网络拓扑模型1.2.1无尺度模型当节点度数与核数都能够满足幕率分如的特点时，即节点度和核数间实际上相差悬殊,在双対数图中应表现为-•条斜率为负的直线，这一•线性关系是判断给定的实例中随机变量是否满足幕律分布的依据.另外，山于幕函数具有标度不变性，因此，人们现在也把节点度服从幕律分布的网络称为无标度网络。图1是航空网络图，是现实生活中无尺度网络的代表。图1航空无尺度网络图图2反应互联网一个无尺度的一个表征图，从图中明显可以看出，有一些的节点的度极大，而一些节点的

8、度很小。图2互联网无尺度网络图1.2.2小世界模型当一个网络相对比较高的节点度和相对有低的平均路径长度是，这个网络就是一个小壯界模型网络。小世界网络是一种数学之图的类型，在这种图中大部份的结点不与彼此邻接，但大部份结点可以从任一其他点经少数几步就可到达。若将一•个小世界网络中的点代表一个人，而连结线代表人与人认识，则这小世界网络可以反映陌生人山彼此共同认的人而连结的小世界现象。Regularnetwork：Small-worldnetwork：Randomnetwork：connectionsto4nearestneighboursafe