全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology.docx
《全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology.docx》由会员分享，可在线阅读，更多相关《全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology.docx（23页珍藏版）》请在冰点文库上搜索。
全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology
北京航空航天大学第四届研究生学术论坛
th
4thAcademicForumforGraduateStudentsatBeihangUniversity
全球IPv6骨干网络拓扑建模研究
肖波，刘连栋，许可
（北京航空航天大学，计算机学院，软件开发环境国家重点实验室,北京市,100083）
2007年10月
October2007
摘要：
当前全球IPv6网络仍主要通过隧道相联，本文在实验室基于隧道探测得到的丰
富拓扑数据基础上，证实了AS层次的IPv6骨干网络是一个无尺度网络，并发现其度分布的幂率指数较大幅度小于IPv4的新特点。
幂率指数作为无尺度网络的幂率分布一个关键特性，我们对其针对无尺度网络拓扑结构的意义进行了分析，指出幂率指数是网络拓扑的度分布均衡程度的一个度量，在现有模型的基础上总结了影响幂率指数的两个重要因素：
一是优先附着概率，二是网络演化形式。
对这两个因素，以EBA模型为基础提出了一个具有拟和小于2
的幂率指数的新模型，对这个模型进行了理论和实验的分析，结果较好的拟和了各种幂率指数情况，特别是幂率指数小于2的情况，本文还提出了拓扑均衡基尼系数的概念并验证了幂率指数是度分布均衡的一个度量。
最后，利用这个模型对IPv6AS拓扑进行了模拟生成，并得到了较好的结果。
关键词：
IPv6，拓扑，无尺度网络，幂率指数，拓扑均衡
中图分类号：
TP393.07
文献标识码：
A
文章编号：
AF040199
ModelingtheTopologyoftheGlobalBackboneIPv6Networks
BoXiao,Lian-dongLiuandKeXu
（StateKeyLaboratoryofSoftwareDevelopmentEnvironment,BeihangUniversity,Beijing,100083）Abstract:
GlobalIPv6networksconnecttoeachotherthroughIPv4tunnelsandformtheIPv6
Internet.WefindthattheIPv6Internetisalsoscale-freeatASlevelbutwithanewfeature:
itsscalingexponentofdegreedistributionismuchsmallerthanthatoftheIPv4Internet.Currentevolvingnetworkmodels,however,encounterdifficultiesinexplainingwhyascale-freenetworkcanhaveascalingexponentfarsmallerthan2.Wediscussthescalingexponentofascale-freenetworkanditsimplications.Then,basedonthetwomajorfactorsaffectingtheexponentandtheEBAmodel,weproposeanewmodelwhichhasthecapabilitytoreproduceascale-freenetworkwiththescalingexponentsmallerthan2.Toverifythevalidityofthismodel,boththeoreticalandexperimentalanalyseshavebeencarriedout.Finally,wedemonstratetheeffectivenessofthemodelbysuccessfullyreproducingthetopologyofthecurrentIPv6Internet.
Keywords:
IPv6，topology，scale-free，scalingexponent，topologyequilibrium
引言
Internet作为20世纪最伟大的发明之一，把人类带入了信息化社会的新阶段。
从90年代中期开始，随着WWW的兴起，Internet呈现指数式的增长，各服务提供商接入方式纷繁异构，Internet自身的结构高度复杂。
当前由于IPv4地址资源越来越少、应用需求却越来越多，IPv6开始投入运营并逐步发展起来，形成了IPv4与IPv6网络共存的局面。
Internet的拓扑结构可以在路由器级（Router）和自治域（AutonomousSystem）上分别进行研究，由于数量级别和代表性上的关系，对自治域AS层次上的拓扑结构研究更加关注一些。
Internet的AS拓扑结构是这个复杂系统的“骨骼”，是从宏观的角度看待Internet。
研究其拓扑
收稿日期：
2007-06-18
基金项目：
国家973，项目编号2005CB321901；北京科技新星，项目编号2005B12作者简介：
肖波，软件开发环境国家重点实验室硕士研究生，研究兴趣集中于IPv6网络拓扑发现，网络拓扑结构分析、建模论文研究方向：
网络拓扑结构分析、建模。
E-mail:
xiaobo@
导师简介：
许可教授，软件开发环境国家重点实验室硕士生导师，2002年全国百篇优秀博士论文获得者，研究领域包括算法理论、数据挖掘、复杂网络分析等。
E-mail:
kexu@
2007年10月
肖波等：
全球IPv6骨干网络拓扑建模研究
特性，是网络分析的重要内容，并为网络管理和网络设计提供理论证明和事实根据。
尤其是近年来，把Internet的拓扑研究纳入到复杂网络的研究领域后，Internet的拓扑研究就有了更加坚实的理论基础。
复杂网络是具有大量节点和复杂连接关系的网络，例如Internet，社会关系网，经济网络，电力网，交通网，神经网络等。
20世纪90年代末，复杂网路的理论研究取得了两个重大进展：
一是提出了解释“小世界”产生机理的WS模型和NW模型[1]，二是提出了解释“幂率”产生机理的无尺度网络模型[2]。
几乎在无尺度网络模型提出的同时，Internet自身的幂率也被发现[3]，这说明
Internet本身就是一个复杂的无尺度网络。
在这之后，Internet的拓扑研究进入了新阶段，产生了大量的基于连接度的拓扑模型。
本文主要分以下几个部分，背景部分介绍InternetIPv4AS幂率的发现和复杂网络中几种典型的拓扑演化模型，IPv6拓扑结构新特性介绍IPv6AS的拓扑发现结果，幂率指数分析部分明确了幂率指数的意义并分析了影响幂率指数的优先附着概率和网络演化形式两个主要因素，我们的模型部分提出了以这两个因素为出发点的新的拓扑模型，理论推导了该模型的幂率指数，模型的验证部分验证了模型对幂率指数范围的拓宽和幂率指数是网络拓扑均衡的衡量，并利用该模型模拟生成了当前IPv6AS拓扑。
Internet拓扑本身规律认识的突破性进展，证明了Internet本身就是一个无尺度网络，开辟了Internet拓扑研究的新局面。
度分布符合幂率是无尺度网络的关键特征，然而实际中大多数无尺度网络的幂率指数γ都是2～3之间，如表1。
1.2拓扑演化模型
实际网络
规模
γ
Internet
10697
2.2
演员关系
0.4M
2.3
论文引用
0.78M
3
Peer网络
880
2.1
代谢网络
765
2.2
WWW
203M
2.7
拓扑演化模型是从系统演化的角度，利用数表1无尺度网络的幂率分布[5]
1背景
1.1幂率及幂率指数
1999年，Faloutsos等人对1997年11月～1998年12月的Internet的IPv4环境下的AS连接关系进行了统计分析，他们发现了四条幂率[3]：
幂律1：
dvrvR节点v的度dv与该节点排序序号rv的R次幂成正比，R是常数；
幂律2：
fdd度的频率fd与该度d的次幂成正比，是常数；
幂律3：
ii特征值i与其次序i的次幂成正比，是常数；
H
近似幂律：
p（h）hHh跳内节点对的数量p（h）与h的H次幂成正比，H是常数。
2003年，他们又对1997年9月～2002年2月的Internet的AS拓扑演化做了进一步研究，得到了同样的结果并验证了网络的增长性[4]。
在这些幂率中，最重要最根本的是幂率2，
它刻画了网络拓扑度分布的基本规律。
说明了Internet的拓扑结构并非随机模型那样“平等均匀”，也不像层次模型那样“等级分明”；而是表明：
网络中的绝大多数节点拥有较少的度，少量的节点拥有较多的度。
Internet幂率的发现是对
学的方法，结合图的形式，在理论上对拓扑特性进行建模的结果。
拓扑演化模型是解释拓扑特性的方式，也是模拟网络生长的工具，对网络结构本身的研究具有重要的意义。
在研究无尺度网络的拓扑模型中，著名的模型有BA模型，EBA模型，非线性优先附着模型，GLP模型，PFP模型等。
BA模型[2]，1999年Barabasi和Albert提出了网络的增长和优先附着的特性是网络中“幂率”
产生的根源，由此提`出了“无尺度”网络的概念，并设计了一个无尺度网络的进化模型，它的构造过程如下：
1、增长：
从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连到m个已经存在的节点上，m一个新节点与一个已存在的节点i相连接的概率∏i与节点i的度ki、所有节点的度的总和之间满足如下关系：
ki
kj
（1）
BA模型的特征如下。
经过t步后，算法产生一个
N＝t＋m0个节点，mt条边的网络，产生度分布：
Pk
2mm1
kk1k2
2m2k
（2）
的无尺度网络。
BA模型的精彩之处在于它把实际复杂网络的无尺度特性归结为增长和优先附着的两个简单明了的特性，然而BA模型只能生成幂率指数为3的拓扑；BA模型只有“加点”、“加边”的操作，跟真实拓扑改变的情况还有一定的差别。
EBA模型[6，7]，2000年Albert和Barabasi有对他们的BA模型进行了改进，新算法如下，初始有m0个孤立的节点，每一步执行下面三个步骤的
2007年10月
肖波等：
全球IPv6骨干网络拓扑建模研究
（7）
一个：
1、以概率p增加m条新的内部边，即在已存在的节点间添加新的边，随机选取一个节点作为新的边的起始点，边的另一个端点由下面的概率公式决定，重复此过程m次（m（k）ki1
ab（ki）（kj1）（3）
j
2、以概率q重新配置m条边。
随机选取节点i和连接到节点i的一条边lij，然后移走此边，以连接节点i和j'的新边lij'取代。
每次根据上述概率式来选取j'配置新边，并重复此过程m次。
3、以概率1-p-q增加一个新节点。
根据上述概率式与网络中已存在的m个节点相连接。
EBA模型的度分布满足幂率，幂率指数为：
12m1q1pq，（4）
m，（4）
由于还要保证得到无尺度网络的拓扑，对p，q
取值都有一定的限制，EBA模型可以较好的得到
2拓扑。
非线性优先附着模型[8]，Krapivsky，Render和Leyvraz在2000年对非线型优先附着的情况进行了讨论。
他们先假设优先附着的概率为：
ki
（ki）kikj（5）
j
他们用速率方程法计算了在t时刻有入度为k-1的节点的平均值Nk（t），根据的值可以得到两种不同状态：
1、亚线型状态
（1）：
在此状态中，结果可以成伸展指数，即度分布为指数分布；2、超线型状态
（1）：
在此状态中，1中p（k）
中的表达式无法解析，特别的是当2时，会
出现“寡头”现象，即只有一个节点占有大量的度，其余节点都是度为1的节点。
总之，计算和实验都表明非线性优先附着会破坏网络的无尺度特性。
网络拓扑结构的无尺度特性要选择的唯一状态就是线型或者是接近线型的优先附着。
GLP模型[9]，在2002年，Bu和Towsley发现，现实Internet中的节点比BA线型优先更倾向与连接到度大的节点，于是他们提出了广义线型优先模型GLP，它的网络演化如下：
初始m0条边讲m0个点连接起来，然后执行：
1、以概率p加入m条边，边连到的节点按如下概率在已有节点中选择：
ki
（ki）（ki）其中1（6）
j
2、以概率1-p增加一个新节点，并按照上面的概率把它连接到已有的m节点上。
它得到的幂率指数为：
12m（1p）。
m（1p）
按照GLP模型[8]参数取值的约束得到累积度分布指数所以12。
正反馈（PFP）模型[10]，是2004年ShiZhou等人提出的较新的拓扑模型，它主要是为了反映InternetAS拓扑中的“富人俱乐部”现象在交互增长（IG）模型的基础上发展而来的。
从多次实验中发现，在非线型优先附着中，如果当
1.13~1.15的时候得到的拓扑关系跟实际比较接近，把优先附着概率改为
（9）
但是实验结果表明，PFP拟和的还是IPv4现有的幂率指数，它的实质是非线性程度较小的非线性模型，所以2。
综上所述，大多数发现的无尺度网络幂率指数大于2是当前一些主要的模型产生的背境是，它们对于生成幂率指数较大幅度小于2的网络拓扑具有较大难度。
这些模型的局限见表2。
2IPv6拓扑结构新特性从2004年开始，我们开始利用多隧道接入的分布式的多点探测方式对全球IPv6骨干网络进
行了拓扑发现，构建了全球IPv6骨干网分布式拓扑发现系统Dolphin[13，14]，Dolphin系统收集了大量IPv6路由器、AS（自治域）的连接和流量信息。
到2006年10月份，共发现了6325个路由器设备，51115条链路，508个AS，系统所发现的具体拓扑数据如表3所示。
评价Internet拓扑发现的效果好坏一个比较重要的指标是发现AS域覆盖率。
系统发现了508个自治域，而Cernet所统计的IPv6网络自治域数量为562个。
AS拓扑发现覆盖率达到90.4%。
而对于Traceroute方法的拓扑发现，覆盖率达到75％。
国际著名网络研究组织CAIDA（theCooperativeAssociationforInternetDataAnalysis）也进行了与Dolphin类似的一项IPv6拓扑发现工作，即Scamper[15]。
Dolphin与Scamper的发现结果对比如表4所示。
在2005年同期，Dolphin使用了4条手动配置隧道所发现的拓扑数据除了在IPv6链路数目上
不如Scamper外，其他部分均超过Scamper。
由于Scamper在全球17个不同的网络部署了探测代
理，因此其发现的链路数目要多一些。
2006年以来，Dolphin用6个探测点，利用自己研发的第三方探测技术部署了91个隧道进行新的IPv6拓扑发现，其拓扑发现数据量大大增加，目前已经远超原有系统和Scamper所发现的数据。
我们对收集到的大量数据进行了分析、整理，尤其在IPv6幂率部分得到了新的发现，如图1所示。
幂率拟和相关系数为0.958，表明：
IPv6AS层次拓扑结构完全符合幂率，所以IPv6网络也是无尺度网络的一个实例。
然而IPv6网络的幂率指数仅为1.2727，远小于IPv4的2.22[3，4]。
既然幂率分布是无尺度网络的关键特性，那么幂率指数的不同则反映了不同无尺度网络的个体特征，也就是说当前IPv6网络在分布上具有不同与IPv4
网络的新特性。
对于这种差异原因可能是多方面。
首先，
IPv6的规模还远没有IPv4大。
对于本文进行验证的500个左右的AS，比起IPv4上万量级的AS，还是有些过于小了。
除此之外，IPv6的网络目前仍还处于在试验向全面部署过渡的阶段，因此不可避免的拥有某些试验网络的特点（一些大的IPv6试验网络平台几乎和所有IPv6的AS域都有连接，而大量的小的IPv6AS域，只和这些大的网络试验平台有连接），这些试验平台所处的AS域网络拥有很大的出度，因此也造成拓扑图形特性的差异。
大多数无尺度网络的幂率指数都是2～3之间，
但在实际中，除了我们发现的IPv6网络的幂率指数较大程度小于2外，也有少量网络的幂率指
2007年10月
肖波等：
全球IPv6骨干网络拓扑建模研究
图2幂率指数越大，度分布的区间越集中，度分布越“均匀”，（a）；幂率指数越小，度分布的区间越发散，度分布
越不“均匀”，（b）
（10）
（12）
数是小于2的。
如社会领域的e-mail网络的入度幂率为1.5，技术领域的软件包网络的出度幂率为1.4，入度幂率为1.6等[5]。
因此无尺度网络的幂率指数小于2的情形是客观存在的。
但现阶段解释无尺度网络演化理论的各种模型只能构造出幂率指数大于2的无尺度网络，所以对幂率指数表征的物理意义和影响幂率指数的因素进行研究，以及对这些模型进行相应的扩展都是重要的研究工作。
3幂率指数物理意义分析在度分布的幂率关系图上，幂率指数越大，度分布的区间越集中，如图2（a）所示。
特别的当幂率指数为∞，所有节点的度都在同一个数值上，即为一个度均匀分布的网络，这说明幂率指数越大网络度分布越“均匀”；相反，幂率指数越小，度分布的区间越发散，如图2（b）所示。
特别的当幂率指数为0的时候，即所有的度都有相同概率的分布，即最大度与最小度极为悬殊，这说明幂率指数越小网络度分布越“不均匀”。
现阶段IPv6网络幂率指数较大幅度小于IPv4说明：
处于发展初始阶段的IPv6网络度分布更不均匀，节点间更不平等。
度分布的幂率指数是无尺度网络度分布均衡程度的刻画，它受多个因素的影响。
从已有的演化模型分析，幂率指数会受到优先附着概率的影响，也会收到网络演化形式的影响。
在优先附着概率方面，线型附着是最基本和最简单的附着方式，然而实际网络的附着情况远比这个简单的模型复杂，而且对真实网络的优先附着情况表明：
对于度大的节点，实际附着的概率要比上述表达式的值大。
于是有人提出其他的各种附着方式：
如非线性[8]、超线型[8]、正反馈[10]等等。
但是实际大量的模拟实验表明，线型附着已经是实际情况较贴近的拟和，尤其如果改
ii
ikj
j
非线型附着形式被证明只有当α＝1时才满足符合无尺度的幂率分布，特别当α>2时，网络所有的连接极大概率就会被某一个点“吸引”[8]。
这说明优先附着的方式不能太远的偏离线型附着的基线。
我们的出发点是在线型附着模型的基础上对所有的点同时提升或降低相同的附着概率调整基数－λ，这样从本质上看，这种附着方式还是满足了线型附着的基本特点。
然而，当我们精心选取附着概率调整基数就可以达到对幂率指数的精确调节。
具体的做法是附着概率调整基数λ按如下关系选取：
k,（11）其中k为网络的平均度。
这里，取k的意义在于k可以作为已有网络的一种特性引入到网络的演化形式中，并且k给理论计算度分布幂率指数带来较大方便，这样优先附着的概率计算形式改为：
kik
kjk
经过证明发现得到幂率指数32（证明过程见第4部分）。
但对与线型拥有初始连接形式的附着方式，已经证明2[12]，但是却说明了附着概率调整基数是网络度分布幂率指数的一个重要影响因素。
在网络演化形式方面，EBA模型[7]对我们有较大的启发。
EBA模型对BA模型的扩展主要在
2007年10月
肖波等：
全球IPv6骨干网络拓扑建模研究
于网络本身的变化机制上：
增加了网络中边重新连接的机制，这可以看作是复杂网络中节点间调整连接关系的模拟。
这种已有连接关系调整的机制可以作为调整幂率指数的一个方法。
EBA模型的度分布满足幂率，幂率指数为：
12m1q1pq（13）m由于还要保证得到无尺度网络的拓扑，对p，q
取值都有一定的限制，EBA模型可以较好的得到23拓扑，EBA模型虽然也不能把降到2以
下，但是它表明了：
重新连接的机制也是网络中幂率指数变化的重要原因。
4我们的模型
ki
tii
qmkik
qm
N（t）M（t）
iii.
以概率1-p-q加入一个新节点并加入
以其为一端的m条边时,
因此，在时刻t，可以得到下列关系：
（17）
m条
（18）
N（t）（1pq）t,（19）
N（t）
ki2（1q）mt,（20）i1
综合考虑了附着概率调整基数和网络演化形式中的重新连接对幂率指数的影响，我们提出了一个旨在扩大幂率指数范围的无尺度网络演化模型。
这个模型以EBA模型为基础，添加了带附着概率调整基数的优先附着概率计算方式，具体算法如下。
初始有m0个孤立的节点，每一步执行下面三个步骤的一个：
i.以概率p增加m条新的内部边，即在已存在的节点间添加新的边，随机选取一个节点作为新的边的起始点，边的另一个端点的概率由公式2决定，重复此过程m次（mii.以概率q重新配置m条边。
随机选取节点i和连接到节点i的一条边lij，然后移走此边，以连接节点i和j'的新边lij'取代。
每次根据上述概率式来选取j'配置新边，并重复此过程m次。
iii.以概率1-p-q增加一个新节点。
根据公式
（12）计算连接概率与网络中已存在的m个节点相连接。
我们运用连续场理论，对
升级会员 