Internet网络拓扑建模(3)

Ｉｎｔｅｍｅｔ网络拓扑建模按照层次的不同，可分为自治域级拓扑建模与路由器级拓扑建模．在自治域级拓扑模型中（如图４所示【１９１），节点代表一个自治系统（Ａｓ），边代表自治系统之间的连接关系．随着网络技术的不断发展，自治域级拓扑建模经历了从随机图拓扑模型发展到基于层次结构的拓扑模型，再到目前基于节点度的拓扑模型这３个发展阶段．由于Ｉｎｔｅｒｎｅｔ网络规模的飞速发展，截止２００７年７月，全世界的自治域总数从２０００年的８０００多个迅速增长到大约２８０００个，自治域间连接超过８２０００条，因此，进一步研究全球互联网络的自治域级拓扑建模成为人们现在的研究重点．

Ｆｉｇ．３Ａｖｅｒａｇｅｃｏｒｅｎｅｓｓｏｆｋ－ｄｅｇｒｅｅｎｏｄｅｓＦｉｇ．４ＩｎｔｅｒｎｅｔＡＳ－ｌｅｖｅｌｔｏｐｏｌｏｇｙ

图３Ｉｎｔｅｒａｃｔ网络节点核数与度数的关系图４Ｉｎｔｅｍｅｔ网络自治域级拓扑

３．１基于随机图的拓扑模型

随机图拓扑模型是Ｉｎｔｅｒｎｅｔ发展处于初级阶段时出现的网络拓扑模型，该类模型基于经典的由Ｅｒｄｏｓ和Ｒｅｎｙｉ所提出ＥＲ随机图理论１３¨，对早期的Ｉｎｔｅｒｎｅｔ，即ＡＲＰＡＮＥＴ进行了模拟再现．此类模型的节点隧机分布在一个平面上，并用概率决定任意两点间是否存在连接，不同的概率函数决定不同的拓扑模型．

Ｗａｘｍａｎ模型是随机图拓扑模型中的典型代表，该模型在１９８８年由Ｗａｘｍａｎ［５１１提出．Ｗａｘｍａｎ模型以任意两节点函数间的距离为自变量来计算两点间直接相连的概率，其概率函数为

Ｐ（∥，ｙ）＝ｔ２ｌｅ－ｄｌ（ＢＬ’．

上式中，ａ＞Ｏ，胚ｌ；ｄ为∥到１，的欧氏距离；￡为两点问的最长距离．当增加口时，所建模型将有更多的短边，更长的跳数直径，更短的长度直径；增加矽将增加模型中长边所占的比例．

Ｗａｘｍａｎ模型的平均节点度为研？ｌ口ｅ－ｄｌ（ｆｌＬ’】＝，疵日ｅ一“肛’】．对于Ｗａｘｍａｎ模型的目标边数，有一组口’肿集合可以保证达到．当模型参数强碉定时，参数工对模型的边数几乎没有影响，因为虽然Ｌ的改变会影响两节点间距离ｄ的值，但是ｄ／Ｌ的值保持不变．

由于在基于随机图的拓扑模型中，节点度数会随着节点数量的增加而增加，因此，随机图拓扑模型无法生成节点众多且节点平均度较小的网络．

３．２基于层次结构的拓扑模型

随着网络技术的进步和网络规模的迅速扩大，早期的基于随机图的拓扑模型已经无法适用，于是出现了基于层次结构的Ｉｎｔｅｒｎｅｔ拓扑模型，这类模型在２０世纪９０年代中期成为Ｉｎｔｅｍｅｔ拓扑建模的主流，可用于生成较大规模且节点平均度较小的网络．其中，较有代表性的有Ｔｉｅｒｓ模型【５２】、Ｔｒａｎｓｉｔ．Ｓｔｕｂ模型【５３１和ＧＴＩＴＭ［５４１模型等．

Ｔｉｅｒｓ模型的目的在于反映ＷＡＮ，ＭＡＮ和ＬＡｂ／这３个层次之间的自治域连接关系，在建摸过程中需要指定

周苗等：Ｉｎｔｅｍｅｔ网络拓扑建模１１５ＭＡＮ和ＬＡＮ的目标个数，并且ＬＡＮ采用星形拓扑结构．Ｔｒａｎｓｉｔ．Ｓｔｕｂ模型则利用不同大小的限制空间分别限制各层上的节点．

３．３基于节点度的拓扑模型

１９９９年至今，随着幂律分布特性的揭示，Ｉｎｔｅｒｎｅｔ网络拓扑建模进入了一个新的发展阶段，出现了更能反映较大规模Ｉｎｔｅｒｎｅｔ网络的自治域级拓扑模型，即基于节点度的自治域级拓扑模型．在目前已出现的大量自治域级拓扑模型中，比较有代表性的是静态模型Ｉｎｅｔ［５５１，动态模型ＢＡｔ５６１，ＡＢ［５６１，ＢＲＩＴＥ［５７１，ＧＬＰ［５８１，Ｄｐ［５９１，ＰＦｐ／砷１，ＴＡＮＧ［６１１，ＧＬＲＧ［６２】，ＣＭＵ［６３垮：

（１）静态模型Ｉｎｅｔ：在建模过程中采用非线性优先的连接方式，通过初始放置所有节点，并对每个节点分配连接度，从而有层次地添加边．尽管ｌｎｅｔ无法反应Ｉｎｔｅｍｅｔ的动态变化，但对于某种特定规模的Ｉｎｔｅｍｅｔ网络，能够较为真实地反应某些拓扑特性，如度分布遵循幂律分布，且最大度也接近真实网络的实际值等．Ｗｉｎｉｃｋ和Ｊａｍｉｎ在文献［５５】中提出Ｉｎｅｔ模型可模拟３０３７个节点的实际网络，即１９９７年Ｉｎｔｅｒｎｅｔ网络中的自治域数目．

（２）动态模型ＢＡ：ＢＡ模型是第一个演化网络模型，由Ｂａｒａｂａｓｉ和Ａｌｂｅｒｔ等人提出，现在拓扑建模研究中普遍将其作为无标度网络基本模型．ＢＡ模型也是第一个从动态增长观点研究复杂网络具有幂律度分布特性的模型，并论证了生成无标度网络的两条重要机理：增长（ｇｒｏｗｔｈ）和择优（ｐｒｅｆｅｒｅｎｔｉａｌａｔｔａｃｈｍｅｎｔ）．但是，ＢＡ模型对初始网络没有完全设定，只说明开始给定玎。个节点，但这胛。个节点间如何建边尚未讨论，而对于不同的初始网络，其后演化的结果网络并不相同；并且，ＢＡ模型的算法可能导致重复建边．另外，优先连接也并不适用于所有出现幂律分布的情形，即便是对于某些无标度网络，利用优先连接来解释幂律的形成机理也很不合理【６４１．

（３）ＡＢ模型：ＡＢ模型是Ａｌｂｅｒｔ和Ｂａｒａｂａｓｉ对ＢＡ模型的修正，该模型采用了线性优先的连接方式，通过概率增加点和边，并对内部边重新配置，保证了孤立节点建立新连接的可能性，逐步生成动态的ＡＳ级拓扑模型．ＡＢ模型的连接度分布呈现幂律，且幂律指数接近真实网络．但是，它在聚类系数和特征路径长度上存在着很强的负相关性，其聚类系数严重低于网络实际值；并且，在最大连接度和次最大连接度等方面也都和实际网络存在较大的偏差∽１．

（４）ＢＲＩＴＥ模型：是一种采用Ｗａｘｍａｎ概率与线性优先相结合方式的动态自治域级拓扑模型，其特点在于反映实际Ｉｎｔｅｒｎｅｔ拓扑的多面性，如层次性和连接度分布等，对于不同的参数及不同的节点分布方式，ＢＲＩＴＥ会产生不同的拓扑特性．另外，在建模过程中，它将当时已存在的Ｗａｘｍａｎ，ＡＢ，Ｉｎｅｔ都融合其中，并提供了更好的接口界面供仿真使用．

（５）ＧＬＰ模型：即广义线性优先模型，它的建模过程依靠广义线性优先的连接方式，其思想方法是假设Ｉｎｔｅｒｎｅｔ网络中的节点比ＢＡ线性优先连接更倾向于连接到高度数节点．ＧＬＰ模型中的度分布也服从幂律分布规律，在幂律指数和最大连接度上接近真实Ｉｎｔｅｒｎｅｔ网络，但其特征路径长度和聚类系数略低于实际值畔】．

（６）ＤＰ模型：亦采用线性优先的连接方式，又叫动态优先模型．其建边条件根据自治域之间的Ｃ．Ｓ关系或对等关系，其结果反映了一定规模Ｉｎｔｅｍｅｔ的小世界现象，但当聚类系数不断增大时。ＤＰ模型无法反映这种变化趋势．

（７）ＰＦＰ模型：又称为正反馈优先模型，其建模过程基于新的节点与内部边交互增长和非线性优先连接这两个机理，重点在于反映自治域层面Ｉｎｔｅｍｅｔ拓扑中存在的富人俱乐部（ｒｉｃｈ．ｃｌｕｂ）现象．

（８）ＴＡＮＧ模型：ＴＡＮＧ模型的幂律指数和叶子节点所占比例均接近实际值，并且在一定程度上反映出Ｉｎｔｅｒｎｅｔ的聚类特性，其构建思想基于增量加边和超线性优先连接．

小结上述自治域级拓扑模型可以看到：现有自治域级拓扑建模算法相对单一，大多数模型都基于优先连接这样的类似原理上，造成所建模型的不完备性．除不完备性外，在最 …… 此处隐藏：2823字，全部文档内容请下载后查看。喜欢就下载吧 ……