全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology.docx
- 文档编号:14057271
- 上传时间:2023-06-20
- 格式:DOCX
- 页数:18
- 大小:158.99KB
全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology.docx
《全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology.docx》由会员分享,可在线阅读,更多相关《全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology.docx(18页珍藏版)》请在冰点文库上搜索。
全球IPv6骨干网络拓扑建模研究IPv6BackboneNetworkTopology
全球IPv6骨干网络拓扑建模研究
肖波,刘连栋,许可
(北京航空航天大学,计算机学院,软件开发环境国家重点实验室,北京市,100083)
摘要:
当前全球IPv6网络仍主要通过隧道相联,本文在实验室基于隧道探测得到的丰富拓扑数据基础上,证实了AS层次的IPv6骨干网络是一个无尺度网络,并发现其度分布的幂率指数较大幅度小于IPv4的新特点。
幂率指数作为无尺度网络的幂率分布一个关键特性,我们对其针对无尺度网络拓扑结构的意义进行了分析,指出幂率指数是网络拓扑的度分布均衡程度的一个度量,在现有模型的基础上总结了影响幂率指数的两个重要因素:
一是优先附着概率,二是网络演化形式。
对这两个因素,以EBA模型为基础提出了一个具有拟和小于2的幂率指数的新模型,对这个模型进行了理论和实验的分析,结果较好的拟和了各种幂率指数情况,特别是幂率指数小于2的情况,本文还提出了拓扑均衡基尼系数的概念并验证了幂率指数是度分布均衡的一个度量。
最后,利用这个模型对IPv6AS拓扑进行了模拟生成,并得到了较好的结果。
关键词:
IPv6,拓扑,无尺度网络,幂率指数,拓扑均衡
中图分类号:
TP393.07
文献标识码:
A文章编号:
AF040199
ModelingtheTopologyoftheGlobalBackboneIPv6Networks
BoXiao,Lian-dongLiuandKeXu
(StateKeyLaboratoryofSoftwareDevelopmentEnvironment,BeihangUniversity,Beijing,100083)
Abstract:
GlobalIPv6networksconnecttoeachotherthroughIPv4tunnelsandformtheIPv6Internet.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。
研究其拓扑特性,是网络分析的重要内容,并为网络管理和网络设计提供理论证明和事实根据。
尤其是近年来,把Internet的拓扑研究纳入到复杂网络的研究领域后,Internet的拓扑研究就有了更加坚实的理论基础。
复杂网络是具有大量节点和复杂连接关系的网络,例如Internet,社会关系网,经济网络,电力网,交通网,神经网络等。
20世纪90年代末,复杂网路的理论研究取得了两个重大进展:
一是提出了解释“小世界”产生机理的WS模型和NW模型[1],二是提出了解释“幂率”产生机理的无尺度网络模型[2]。
几乎在无尺度网络模型提出的同时,Internet自身的幂率也被发现[3],这说明Internet本身就是一个复杂的无尺度网络。
在这之后,Internet的拓扑研究进入了新阶段,产生了大量的基于连接度的拓扑模型。
本文主要分以下几个部分,背景部分介绍InternetIPv4AS幂率的发现和复杂网络中几种典型的拓扑演化模型,IPv6拓扑结构新特性介绍IPv6AS的拓扑发现结果,幂率指数分析部分明确了幂率指数的意义并分析了影响幂率指数的优先附着概率和网络演化形式两个主要因素,我们的模型部分提出了以这两个因素为出发点的新的拓扑模型,理论推导了该模型的幂率指数,模型的验证部分验证了模型对幂率指数范围的拓宽和幂率指数是网络拓扑均衡的衡量,并利用该模型模拟生成了当前IPv6AS拓扑。
1背景
1.1幂率及幂率指数
1999年,Faloutsos等人对1997年11月~1998年12月的Internet的IPv4环境下的AS连接关系进行了统计分析,他们发现了四条幂率[3]:
幂律1:
节点v的度
与该节点排序序号
的R次幂成正比,R是常数;
幂律2:
度的频率
与该度
的
次幂成正比,
是常数;
幂律3:
特征值
与其次序i的
次幂成正比,
是常数;
近似幂律:
h跳内节点对的数量
与h的H次幂成正比,H是常数。
2003年,他们又对1997年9月~2002年2月的Internet的AS拓扑演化做了进一步研究,得到了同样的结果并验证了网络的增长性[4]。
在这些幂率中,最重要最根本的是幂率2,它刻画了网络拓扑度分布的基本规律。
说明了Internet的拓扑结构并非随机模型那样“平等均匀”,也不像层次模型那样“等级分明”;而是表明:
网络中的绝大多数节点拥有较少的度,少量的节点拥有较多的度。
Internet幂率的发现是对Internet拓扑本身规律认识的突破性进展,证明了Internet本身就是一个无尺度网络,开辟了Internet拓扑研究的新局面。
度分布符合幂率是无尺度网络的关键特征,然而实际中大多数无尺度网络的幂率指数γ都是2~3之间,如表1。
1.2拓扑演化模型
拓扑演化模型是从系统演化的角度,利用数
表1无尺度网络的幂率分布[5]
实际网络
规模
γ
Internet
10697
2.2
演员关系
0.4M
2.3
论文引用
0.78M
3
Peer网络
880
2.1
代谢网络
765
2.2
WWW
203M
2.7
学的方法,结合图的形式,在理论上对拓扑特性进行建模的结果。
拓扑演化模型是解释拓扑特性的方式,也是模拟网络生长的工具,对网络结构本身的研究具有重要的意义。
在研究无尺度网络的拓扑模型中,著名的模型有BA模型,EBA模型,非线性优先附着模型,GLP模型,PFP模型等。
BA模型[2],1999年Barabasi和Albert提出了网络的增长和优先附着的特性是网络中“幂率”产生的根源,由此提`出了“无尺度”网络的概念,并设计了一个无尺度网络的进化模型,它的构造过程如下:
1、增长:
从一个具有m0个节点的网络开始,每次引入一个新的节点,并且连到m个已经存在的节点上,m 2、优先附着: 一个新节点与一个已存在的节点i相连接的概率∏i与节点i的度ki、所有节点的度的总和之间满足如下关系: (1) BA模型的特征如下。 经过t步后,算法产生一个N=t+m0个节点,mt条边的网络,产生度分布: (2) 的无尺度网络。 BA模型的精彩之处在于它把实际复杂网络的无尺度特性归结为增长和优先附着的两个简单明了的特性,然而BA模型只能生成幂率指数为3的拓扑;BA模型只有“加点”、“加边”的操作,跟真实拓扑改变的情况还有一定的差别。 EBA模型[6,7],2000年Albert和Barabasi有对他们的BA模型进行了改进,新算法如下,初始有m0个孤立的节点,每一步执行下面三个步骤的一个: 1、以概率p增加m条新的内部边,即在已存在的节点间添加新的边,随机选取一个节点作为新的边的起始点,边的另一个端点由下面的概率公式决定,重复此过程m次(m (3) 2、以概率q重新配置m条边。 随机选取节点i和连接到节点i的一条边lij,然后移走此边,以连接节点i和j’的新边lij’取代。 每次根据上述概率式来选取j’配置新边,并重复此过程m次。 3、以概率1-p-q增加一个新节点。 根据上述概率式与网络中已存在的m个节点相连接。 EBA模型的度分布满足幂率,幂率指数为: ,(4) 由于还要保证得到无尺度网络的拓扑,对p,q取值都有一定的限制,EBA模型可以较好的得到 拓扑。 非线性优先附着模型[8],Krapivsky,Render和Leyvraz在2000年对非线型优先附着的情况进行了讨论。 他们先假设优先附着的概率为: (5) 他们用速率方程法计算了在t时刻有入度为k-1的节点的平均值 ,根据 的值可以得到两种不同状态: 1、亚线型状态( ): 在此状态中,结果可以成伸展指数,即度分布为指数分布; 2、超线型状态( ): 在此状态中,1中p(k)中的表达式无法解析,特别的是当 时,会出现“寡头”现象,即只有一个节点占有大量的度,其余节点都是度为1的节点。 总之,计算和实验都表明非线性优先附着会破坏网络的无尺度特性。 网络拓扑结构的无尺度特性要选择的唯一状态就是线型或者是接近线型的优先附着。 GLP模型[9],在2002年,Bu和Towsley发现,现实Internet中的节点比BA线型优先更倾向与连接到度大的节点,于是他们提出了广义线型优先模型GLP,它的网络演化如下: 初始m0条边讲m0个点连接起来,然后执行: 1、以概率p加入m条边,边连到的节点按如下概率在已有节点中选择: 其中 (6) 2、以概率1-p增加一个新节点,并按照上面的概率把它连接到已有的m节点上。 它得到的幂率指数为: 。 (7) 按照GLP模型[8]参数取值的约束得到累积度分布指数 ,(8) 所以 。 正反馈(PFP)模型[10],是2004年ShiZhou等人提出的较新的拓扑模型,它主要是为了反映InternetAS拓扑中的“富人俱乐部”现象在交互增长(IG)模型的基础上发展而来的。 从多次实验中发现,在非线型优先附着中,如果当 的时候得到的拓扑关系跟实际比较接近,把优先附着概率改为 (9) 但是实验结果表明,PFP拟和的还是IPv4现有的幂率指数,它的实质是非线性程度较小的非线性模型,所以 。 综上所述,大多数发现的无尺度网络幂率指数大于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个不同的网络部署了探测代 表2主要拓扑演化模型特征及其幂率指数局限a 拓扑演化模型 特征 幂率指数局限 BA模型[2] 线型增长,线型优先附着 非线附着型模型[8] 仅当 才能得到无尺度网络 EBA模型[7] 加入边重连接机制 GLP模型[9] PFP模型[10] 实验表明 Gradualaging模型[11] if if Initialattractiveness模型[12] A是一个常数 if if a本表主要参考了[6]表III 表3IPv6拓扑发现总体数据[14] 统计项 数据 探测列表地址数 5256 一次探测发送探测包数 43046640 发现IPv6地址数 7401 发现IPv6链路数 51115 发现路由设备数 6325 发现地址前缀数 680 发现AS数目 508 路由设备平均出度 8.014 AS域平均出度 4.21 隧道使用数 91 表4BUAADolphin与CAIDAScamper发现结果对比[14] Dolphin(2006/10) Dolphin (2005/4) Scamper (2005/4) 探测点 6 4 17 AS 508 346 333 IPv6地址 7401 3022 2913 IPv6链路 51115 6825 7905 图1IPv6AS度分布幂率关系图 说明: 图中横轴为节点的度,纵轴为该度出现的频度 幂率拟和相关系数为0.958,IPv6AS层次拓扑结构完全符合幂率,但幂率指数仅为1.2727,远小于IPv4的2.22 理,因此其发现的链路数目要多一些。 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外,也有少量网络的幂率指 图2幂率指数越大,度分布的区间越集中,度分布越“均匀”,(a);幂率指数越小,度分布的区间越发散,度分布越不“均匀”,(b) 数是小于2的。 如社会领域的e-mail网络的入度幂率为1.5,技术领域的软件包网络的出度幂率为1.4,入度幂率为1.6等[5]。 因此无尺度网络的幂率指数小于2的情形是客观存在的。 但现阶段解释无尺度网络演化理论的各种模型只能构造出幂率指数大于2的无尺度网络,所以对幂率指数表征的物理意义和影响幂率指数的因素进行研究,以及对这些模型进行相应的扩展都是重要的研究工作。 3幂率指数物理意义分析 在度分布的幂率关系图上,幂率指数越大,度分布的区间越集中,如图2(a)所示。 特别的当幂率指数为∞,所有节点的度都在同一个数值上,即为一个度均匀分布的网络,这说明幂率指数越大网络度分布越“均匀”;相反,幂率指数越小,度分布的区间越发散,如图2(b)所示。 特别的当幂率指数为0的时候,即所有的度都有相同概率的分布,即最大度与最小度极为悬殊,这说明幂率指数越小网络度分布越“不均匀”。 现阶段IPv6网络幂率指数较大幅度小于IPv4说明: 处于发展初始阶段的IPv6网络度分布更不均匀,节点间更不平等。 度分布的幂率指数是无尺度网络度分布均衡程度的刻画,它受多个因素的影响。 从已有的演化模型分析,幂率指数会受到优先附着概率的影响,也会收到网络演化形式的影响。 在优先附着概率方面,线型附着是最基本和最简单的附着方式,然而实际网络的附着情况远比这个简单的模型复杂,而且对真实网络的优先附着情况表明: 对于度大的节点,实际附着的概率要比上述表达式的值大。 于是有人提出其他的各种附着方式: 如非线性[8]、超线型[8]、正反馈[10]等等。 但是实际大量的模拟实验表明,线型附着已经是实际情况较贴近的拟和,尤其如果改为 (10) 非线型附着形式被证明只有当α=1时才满足符合无尺度的幂率分布,特别当α>2时,网络所有的连接极大概率就会被某一个点“吸引”[8]。 这说明优先附着的方式不能太远的偏离线型附着的基线。 我们的出发点是在线型附着模型的基础上对所有的点同时提升或降低相同的附着概率调整基数-λ,这样从本质上看,这种附着方式还是满足了线型附着的基本特点。 然而,当我们精心选取附着概率调整基数就可以达到对幂率指数的精确调节。 具体的做法是附着概率调整基数λ按如下关系选取: (11) 其中 为网络的平均度。 这里,取 的意义在于 可以作为已有网络的一种特性引入到网络的演化形式中,并且 给理论计算度分布幂率指数带来较大方便,这样优先附着的概率计算形式改为: (12) 经过证明发现得到幂率指数 (证明过程见第4部分)。 但对与线型拥有初始连接形式的附着方式,已经证明 [12],但是却说明了附着概率调整基数是网络度分布幂率指数的一个重要影响因素。 在网络演化形式方面,EBA模型[7]对我们有较大的启发。 EBA模型对BA模型的扩展主要在于网络本身的变化机制上: 增加了网络中边重新连接的机制,这可以看作是复杂网络中节点间调整连接关系的模拟。 这种已有连接关系调整的机制可以作为调整幂率指数的一个方法。 EBA模型的度分布满足幂率,幂率指数为: (13) 由于还要保证得到无尺度网络的拓扑,对p,q取值都有一定的限制,EBA模型可以较好的得到 拓扑,EBA模型虽然也不能把 降到2以下,但是它表明了: 重新连接的机制也是网络中幂率指数变化的重要原因。 4我们的模型 综合考虑了附着概率调整基数和网络演化形式中的重新连接对幂率指数的影响,我们提出了一个旨在扩大幂率指数范围的无尺度网络演化模型。 这个模型以EBA模型为基础,添加了带附着概率调整基数的优先附着概率计算方式,具体算法如下。 初始有m0个孤立的节点,每一步执行下面三个步骤的一个: i.以概率p增加m条新的内部边,即在已存在的节点间添加新的边,随机选取一个节点作为新的边的起始点,边的另一个端点的概率由公式2决定,重复此过程m次(m ii.以概率q重新配置m条边。 随机选取节点i和连接到节点i的一条边lij,然后移走此边,以连接节点i和j’的新边lij’取代。 每次根据上述概率式来选取j’配置新边,并重复此过程m次。 iii.以概率1-p-q增加一个新节点。 根据公式(12)计算连接概率与网络中已存在的m个节点相连接。 我们运用连续场理论,对该模型的演化过程进行推导,得到该模型的幂率指数为: ,(14) 推导过程如下: i.以概率p添加m条边时,: (15) 其中 是节点i在时刻t的度,N(t)是时刻t所有节点个数,且 (16) ii.以概率q重新连接m条边时, (17) iii.以概率1-p-q加入一个新节点并加入m条以其为一端的m条边时, (18) 因此,在时刻t,可以得到下列关系: (19) (20) (21) 和 (22) 把上面三个过程相加,可以得到: (23) 其中 (24) .(25) 根据连续场理论,度 出现的概率 可以由下面关系式确定: (26) 可以得到, . (27) 容易看出度分布 符合幂率,并且幂率指数为: .(28) 5模型的验证 模型的验证是通过大量的实验进行的,实验的工作是多次分析实验结果和再实验的循环组成的。 在对实验结果特别是幂率指数进行统计的时候,采用了无尺度网络研究中的惯用处理办法,即对于幂率分布的统计,去掉少数度特别大的节点以减少“重尾”想象的影响。 由于优先附着概率 ,要保证 有意义就要使得 。 但是,当 时,有可能 。 但是大量的实验表明,即使有部分节点(15%左右)即使出现 ,我们只要对这些节点在运行模型的生长算法的时候保持连接度为1的最少连接,得到的结果仍然较好的符合理论推导。 模型的验证实验主要从四个方面进行: 验证是否突破幂率指数大于2的限制、验证各种情况幂率指数的拟和情况、验证幂率指数是否反映拓扑的不均衡性和用该模型拟和当前IPv6网络拓扑结构。 5.1验证是否突破幂率指数大于2的限制 该模型可以得到幂率指数小于2的无尺度网络,如图3所示,用该模型得到节点数 ,边数 的幂率指数 的一个无尺度网络拓扑
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全球 IPv6 骨干 网络 拓扑 建模 研究 IPv6BackboneNetworkTopology
![提示](https://static.bingdoc.com/images/bang_tan.gif)