th
th
北京航空航天大学第四届研究生学术论坛
2007 年 10
月
4 Academic Forum for Graduate Students at Beihang University
October 2007
（北京航空航天大学，计算机学院，软件开发环境国家重点实验室 , 北京
全球IPv6骨干网络拓扑建
， 刘连栋，许模研究 肖波可
市 , 100083）
摘 要：当前全球 IPv6 网络仍主要通过隧道相联， 本文在实验室基于隧道探测得到的丰 富拓扑数据基础上，证实了 AS层次的 IPv6 骨干网络是一个无尺度网络，并发现其度分布的 幂率指数较大幅度小于 IPv4 的新特点。幂率指数作为无尺度网络的幂率分布一个关键特性， 我们对其针对无尺度网络拓扑结构的意义进行了分析， 指出幂率指数是网络拓扑的度分布均 衡程度的一个度量， 在现有模型的基础上总结了影响幂率指数的两个重要因素： 一是优先附 着概率，二是网络演化形式。对这两个因素，以 EBA模型为基础提出了一个具有拟和小于 2 的幂率指数的新模型， 对这个模型进行了理论和实验的分析， 结果较好的拟和了各种幂率指 数情况，特别是幂率指数小于 2的情况，本文还提出了拓扑均衡基尼系数的概念并验证了幂 率指数是度分布均衡的一个度量。最后，利用这个模型对 IPv6 AS拓扑进行了模拟生成，并 得到了较好的结果。
关 键 词： IPv6 ，拓扑，无尺度网络，幂率指数，拓扑均衡 中图分类号： TP393.07 文献标识码： A
文章编号： AF04 0199
Modeling the Topology of the Global Backbone IPv6 Networks
Bo Xiao, Lian-dong Liu and Ke Xu
(State Key Laboratory of Software Development Environment, Beihang University, Beijing, 100083 )
Abstract: Global IPv6 networks connect to each other through IPv4 tunnels
and form the IPv6 Internet. We find that the IPv6 Internet is also scale-free at AS level but with a new feature: its scaling exponent of degree distribution is much smaller than that of the IPv4 Internet. Current evolving network models,
however, encounter difficulties in explaining why a scale-free network can have a scaling exponent far smaller than 2. We discuss the scaling exponent of a scale-free network and its implications. Then, based on the two major
factors affecting the exponent and the EBA model, we propose a new model which has the capability to reproduce a scale-free network with the scaling
成了 IPv4 与 IPv6网络共存 的局面。 引言 exponent smaller than 2. To verify the validity of this model, both
Internet 的 拓 扑 结 构 可 以 在 路 由
theoretical and experimental analyses have been carried out. Finally, we Internet 作为 20 世纪最伟大的发明之器 级 （ Router）和自治域 （ Autonomous demonstrate the effectiveness of the model by successfully reproducing the 一，把 人类带入了信息化社会的新阶段。 从 90System ）上分 别进行研究，由于数量级别和代topology of the current IPv6 Internet. 年代中期 开始，随着 WWW 的兴起， Internet表性上的关系， 对自治域 AS 层次上的拓扑结构Key words: IPv6 ，topology ， scale-free， scaling exponent ， topology 呈现指数式的 增长，各服务提供商接入方式纷繁研究更加关注一 些。Internet 的AS 拓扑结构equilibrium 异构， Internet 自身的结构高度复杂。 当前是这个复杂系统的 “骨 骼 ”，是从宏观的角度由于 IPv4地址资源越 来越少、 应用需求却越来看待 Internet。研究其拓扑越多， IPv6开始投入运 营并逐步发展起来， 形
收稿日期： 2007-06-18
基金项目：国家 973，项目编号 2005CB321901；北京科技新星，项目编号 2005B12 作者简介：肖波，软件开发环境国家重点实验室硕士研究生，研究兴趣集中于 IPv6 网络拓扑发现，网络拓扑结构分析、建模 论文研究方向：网络拓扑结构分析、建模。 E-mail: xiaobo@nlsde.buaa.edu.cn
导师简介：许可教授， 软件开发环境国家重点实验室硕士生导师， 2002 年全国百篇优秀博士论文获得者，研究领域包括算法理 论、数据挖掘、复杂网络分析等。 E-mail: kexu@nlsde.buaa.edu.cn
2007 年 10 肖波等：全球 IPv6 骨干网络拓扑建 月 模研究
特性， 是网络分析的重要内容， 并为网络管理和
网络设计提供理论证明和事实根据。 尤其是近年 来，把 Internet 的拓扑研究纳入到复杂网络的
研
究领域后， Internet 的拓扑研究就有了更加坚实 的理论基础。 复杂网络是具有大量节点和复杂连接关系 的 网络，例如 Internet ，社会关系网，经济网
络，
电力网，交通网，神经网络等。 20世纪 90年代末，
复杂网路的理论研究取得了两个重大进展：
一是 提出了解释 “小世界 ”产生机理的 WS模型和 NW 模型 [1]
，二是提出了解释 “幂
率
”产生机理的无尺 度网络模型 [2] 。几乎在无尺度网络模型提出的同
时， Internet自身的幂率也被发现 [3]
，这说明 Internet本身就是一个复杂的无尺度网络。在这
之后，
Internet 的拓扑研究进入了新阶段，产生
了大量的基于连接度的拓扑模型。 本文主要分以下几个部分，背景部分介绍 Internet IPv4 AS 幂率的发现和复杂网络中几 种 典型的拓扑演化模型，
IPv6 拓扑结构新特性介
绍 IPv6 AS 的拓扑发现结果， 幂率指数分析部分 明确了幂率指数的意义并分析了影响幂率指 数 的优先附着概率和网络演化形式两个主要因
素，
我们的模型部分提出了以这两个因素为出发点
的新的拓扑模型，理论推导了该模型的幂率指 数，模型的验证部分验证了模型对幂率指数范围 的拓宽和幂率指数是网络拓扑均衡的衡量， 并利
用该模型模拟生成了当前 IPv6 AS 拓扑。
1 背
1.1 景
幂率及幂率指数
1999年，Faloutsos等人对 1997年 11月～
1998 年 12月的 Internet的 IPv4 环境下的
AS连接关系进 行了统计分析，他们发现了四条幂率
[3]
： 幂律 1： dv rvR
节点v的度 dv 与该节点排
序
序号 rv 的 R次幂成正比， R是常数； 幂律 2：fd d
度的频率 fd与该度 d 的 次 幂 成正比， 是常数；
幂律 3： i i 特征值 i 与其次序 i 的 次 幂
成正比， 是常数；
H 近似幂律： p(h) hH h跳内节点对的数量 p(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< m0； 2、优先附着：一个新节点与一个已存在的节点 i 相连接的概率∏ i与节点 i的度 ki 、所有节点的度 的总和之间满足如下关系： ki
kj
(1)
BA 模型的特征如下。经过 t步后，算法产生
一个N＝t ＋m0 个节点， mt条边的网络， 产生度分
布： Pk 2mm 1 22mk
k k 1 k 2
(2)
的无尺度网络。 BA 模型的精彩之处在于它把实际复杂网络 的无尺度特性归结为增长和优先附着的两个简 单明了的特性，然而 BA 模型只能生成幂率指数 为3的拓扑；BA模型只有 “加点”、“加边”的操作， 跟真实拓扑改变的情况还有一定的差别。
EBA 模型 [6，
7]，2000年Albert 和
Barabasi有对 他们的 BA 模型进行了改进，新算法如下，初始 有 m0个孤立的节点， 每一步执行下面三个步骤的
肖波等：全球 IPv6 骨干网络拓扑建
2007 年 10
一个：月 模研究 1、以概率 p增加 m条新的内部边，即在已存在的 节点间添加新的边， 随机选取一个节点作为新的 边的起始点， 边的另一个端点由下面的概率公式 决定，重复此过程 m次( m ki 1 ab (ki ) (kj 1) (3) j 2、以概率 q重新配置 m条边。随机选取节点 i 和连 接到节点 i 的一条边 lij，然后移走此边， 以连接节 点i 和j'的新边 lij'取代。每次根据上述概率式来 选取 j'配置新边，并重复此过程 m 次。 3、以概率 1-p-q 增加一个新节点。根据上述概率 式与网络中已存在的 m个节点相连接。 EBA 模型的度分布满足幂率，幂率指数为： 1 2m1 q 1 p q ， (4) m ， (4) 由于还要保证得到无尺度网络的拓扑，对 p， q 取值都有一定的限制， EBA 模型可以较好的得到 2 拓扑。 非线性优先附着模型 [8] ，Krapivsky ，Render 和 Leyvraz 在 2000 年对非线型优先附着的情况 进行了讨论。他们先假设优先附着的概率为： ki (ki ) k i kj (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 (k i ) (ki ) 其中 1(6) j 2、以概率 1-p增加一个新节点， 并按照上面的概 率把它连接到已有的 m节点上。 它得到的幂率指 数为： 2m (1 p) (7) 1。 m(1 p) 按照 GLP 模型 [8]参数取值的约束得到累积 2m (1 p) 1， m(1 p) (8) 度分布指数 所以 1 2 。 正反馈( PFP)模型 [10] ，是2004年Shi Zhou 等人提出的较新的拓扑模型， 它主要是为了反映 Internet AS 拓扑中的 “富人俱乐部 ”现象在交互增 长( IG )模型的基础上发展而来的。 从多次实验 中发现，在非线型优先附着中，如果当 1.13 ~ 1.15的时候得到的拓扑关系跟实 际 比较接 (ki) kj j 近，把优先附j 着概率改为 (9) 但是实验结果表明， PFP拟和的还是 IPv4现有的 幂率指数，它的实质是非线性程度较小的非线性 模型，所以 2 。 综上所述，大多数发现的无尺度网络幂率指 数大于 2 是当前一些主要的模型产生的背境是， 它们对于生成幂率指数较大幅度小于 2 的网络 拓扑具有较大难度。这些模型的局限见表 2。 2 IPv6 拓扑结构新特性 从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 ( the Cooperative Association for Internet Data Analysis )也进行了与 Dolphin 类似的一项 IPv6 拓 扑发现工作，即 Scamper[15] 。 Dolphin 与 Scamper 的发现结果对比如表 4所示。
相关推荐：
loading