大型互联网络实现拓扑仿真如何抽样3.0.doc

1、大型互联网络实现拓扑仿真如何抽样摘要：在本文中，我们阐述了一种如何从大型互联网络中抽取小样本的方法，尽管最近的研究活动表明：用现实图形模拟和仿真大型互联网络任然是一个没有解决的问题。所以先前试图产生这种图类的工作都是从零开始。我们致力于完善已存在的拓扑网络结构的简化工作，具体说，这项工作分为三个部分。首先我们提出了一系列的简单方法，可以归纳为3 类：（a）删除方法（b）收缩的方法（c）勘探方法。我们验证了这些方法中的一些保持了原始图的一些关键特性。通过执行我们的方法证明了当有效的减少网络 70%的节点时，网络任然能够保持其特性。第二，验证了我们的方法能够很好的应对基本构造发生器。最后，我们成功

2、的验证了我们的方法在实际有效评价多播路由中的研究，除了其实际应用，图的采样来自于网络的某个单独特性。1、 导言 各种网络互联协议要求能够在从大型互联网络中抽取的小样本上执行。实时图应能实现大范围的模拟，特别是非常细节性的例如包一级的模拟。为了验证抽样的有效性，在给定节点数的图上做实验并取实验结果的平均值。做实验时允许实验人员所测节点数在允许范围之外。特别的它证实了这种方法能够适应不同层的网络协议随机网络规模的增加，从而能够对未来的互联网做出更准确的预测。目前，所有一直的仿真模型产生的图都是来自网络的某个特定属性。我们的工作正好采用相反的途径：我们希望要求降级大型网络互联距离来产生小样本拓扑结构

3、。这个想法可被认为是一个采样图，并引起了其他方面的注意。有趣的是，在现有的互联网络拓扑发生器中，还没有一个足够精确得以被广泛接受的发生器这些发生器产生了经过实验论证的仿真图，但是没有必要和互联网络上所有已知的拓扑特性相匹配。近年来在应用层的大多数图发生器产生的图可以增长，这是一个具有建设性的方法这是此领域自互联网络上范县倾斜度分布的空前运动。产生器使用有“偏向性的”或“优生的”增长政策来生成幂律度分布这些有建设性的方法通过集中度分布与真实网络中的距离相匹配产生的合成图。但通常不能兼顾到拓扑结构其它方法来写入文档。本文中，我们阐述了下列问题：如何从真实网络拓扑中抽样或得一个小的仿真图。像我们随后

4、解释的那样，我们在域内和自治系统一级检查网络的拓扑结构。我们这种方法的总体目标是非常明确的：无论是从大的抽样图还是小的抽样图上都能够得出同样的结论。虽然相关工作已在其他领域中存在，但是在网络仿真领域这是一个全新的问题。我们称这种抽样方法为还原图。非常非正式地，直觉告诉我们这种方法应保证不破坏网络已存在的一些特性，期望这种方法能从适应性和统计特性上完成此任务是合理的。相反，这种方法受到了首先确认某功能然后正确产生其他性能的方法的挑战。我们如何评价我们方法的成功之处呢？建立真实产生图的标准是一个开放无终止的问题，在图的抽样中，这个问题变的更棘手：例如怎样的互联网络距离能减少图的匹配问题;如何区分两

5、个实体;如何匹配网络的特性等问题。如果这种特性不随着尺寸的改变而改变，那么这个目标就是相等的。然而，似乎没有脱离时间的独立拓扑存在。研究表明：即使每个网络互联距离在 AS 层都存在幂率特性，但他们的斜率都是不同的。这样，我们选择上面的第一种方法来把简化图和其等价的网络互联距离进行比较。我们使用两种类型的测量来比较图。第一类包括各种图的不变量，例如平均度。第二种类型的测量是基于在两幅图中多播路由协议在其上的比较。事实证明，这些方法在大的互联网络上的测量结果和小的网络上的测量结果是相似的。这就简单的通过比较得出结论:这种测试方法在简化图上得到的结果与大的互联网络得到的结果是一致的。请注意我们的测量

6、方法是参阅了一些广泛应用于复杂网络测量的文献8,16,35,1,24,42,34,39本文的贡献分为 3 个部分（1）提出了一种有效的图采样算法（2）比较了我们的简化图方法和构造图方法（3）使用网络协议来比较我们得到的图11 图的抽样算法作为我们主要的贡献：我们发展和量化了我们一系列简化图的性能。我们把这种方法主要分为三类：（a）删除方法（b）收缩的方法（c）勘探发。我们的工作得出了下列结论：我们最好的方法减少了图中高达 70%的节点时，但很好的实现了图的拓扑性质。我们的方法很好地保持了拓扑结构的鲁棒性和随机性。我们通过分析发现如果原始的拓扑结构中存在幂率分布那么我们的抽样方法能很好的保持其幂

7、率分布。12 简化方法和构造方法的比较比较我们的简化方法和传统的构造方法发现，简化方法能更好的反映真实网络实例的特性。在构造性方法中，网络拓扑产生器很好地发挥了其作用。网络拓扑产生器能很好的发现真是网络的可靠输入。然而网络拓扑产生器不能产生少于 3300 个节点的仿真图，但我们的方法能够产生任意大小的仿真图。13 网络协议仿真我们成功地验证了我们方法在真实网络中多播路由的有效性，经比较简化图在真实网络的使用中得出了相同的结论。例如：按后面细节中提到的多播路由协议在真实网络和简化网络图中的作用是相似的，我们认为这是对我们方法有效性的有力补充。在执行这项工作时，我们发明了一种伴随简化图性能的软件工

8、具，这个工具能提供有效和真实的仿真。在我们的团队中，这种方法已经成功地应用到了几项科学要就中。我们的软件工具作为科学研究是公开的。最后，营房指出的是，此项工作是我们早期工作版本的一个拓展。此版包括：（a）完成了第四部分的证明，这在早期的版本中是一个遗漏（b）一个被称作 moreplots 的延伸实验和图（c）先前和近期工作的一份更详细的清单131 工作远景通过比较简化法和有效法发现简化法更有效。值得指出的是，简化法有另外两条吸引人的特性：（1） 统计事件的减少能保证很多图的特性，包括一些我们没有用作测量的方法，甚至一些我们没有确认的特性。（2） 简化法看起来延伸到了不同类型的图中。例如，政权关

9、系网、网络拓扑网或万维网。图的采用可被用作提供内部拓扑结构和图的构建的工具。最后，当网络尺寸太大，采样同样能够提供可视化的方法。我们强调，减化法不应该被看作构造产生器发的竞争者。相反，这两种方法相互补充，并且，全面的研究能使用这两种图产生器进行各种仿真。本文剩余的部分是这样组织的：在第二部分，我们介绍了必要的背景知识。在第三部分介绍了我们的减化法；第四部分我们为了节点度的分布的幂率分布提供了分布论据； 第五部分 讨论了我们的方法在各种拓扑机制上的性能；第六部分比较简单方法和构造方法；第七部分最优法在多播路由中的应用；第八部分总结全文提出将来的工作。2背景和机制在这部分，介绍了用来评价图的真实性

10、的拓扑模型和几个图的特性。21 网络实例互联网分为自治管理域和自治系统。在我们的研究中我们集中于自治层的拓扑结构。我们把互联网按无向来模拟，无向图的节点是自制系统的，无向图的边是内部控制连接。这里我们指出通过包含商业关系来用有向图模拟互联网。是否我们的简化法能延伸到有向图是将来研究的一个话题。我们的真实数据来自美国俄勒冈州的项目。这份档案数据经常被研究者拿来在此领域做研究，并且这是记录了近五年来唯一存在的一份档案数据应为我们的研究需要很大范围的数据，所以这份数据使我们特地选作我们研究的数据。用IYYMMPD 的形式标记网络实例，这种标注形式用最后的两个数字来标注年月日。例如：2001 年 5

11、月 7 日收集的数据标注为 I010507，在我们实验中我们使用从 1997 年 11 月到2003 年 3 月的数据。请注意，在我们的研究中我们使用从 1997 年到 2003 年跨越 6 年的网络拓扑数据。由于这点，我们确信我们的结果与网络拓扑的演化是极其相似的。这是我们主要用 1997-2001年数据进行仿真，但是我们也用了 2003 年收集的数据仿真。22 图的性质存在几个图的特性来获得真实网络的本领。我们便用几乎所有机制来比较简化图的真实性。这些特性被认为是必需的，但不是以保证构造图的真实性。221 平均程度及其标准偏差图的平局度定义为 2m/n，m 是边数，n 是节点时。我们使用这

12、个测量机制来比较简化图与真实网络拓扑的密集性。人们注意到了平均度随时间的增长，随着互联网规模的增加，自 1997 年的 3.42 到 1999 年 11 月的 3.93，同时，互联网络尺寸大约增长了一倍，为了测量度分布如何分布在平均值附近，我们同样测量标准偏差。222 度分布幂率分布使用了近似的斜率分布，这是由经验观察得来的。这里，我们重点关注幂率分布 1 的度分布指数和幂率分布 2 的度分布指数。节点的度分布指数是按照节点的指数斜率分布的，即第 K 节点的度的大小排在第 K 位。度分布曲线是节点度分布的指数曲线，值得注意的是，如果节点分布极具幂率性，这两种幂率分布在理论程度上是相等的。事实上

13、，它们所提出的度分布特点是大致相同的。在这种测量机制中，验证了度分布的存在性并且比较了幂率分布的指数值，通过对关系系数的量化发现米律分布是很相似的。关系系数对相似精确的一个测量，超过 97%的系数被认为都是合理的近似。223 光谱分析网络拓扑结构光谱分析采用邻接矩阵图分析网络的聚簇性和空间特性、光谱分析在拓扑结构的聚簇特性中获得了显著的信息。它包含了以前使用过的聚簇系数统计法。具体点：光谱分析测量的是整个网络拓扑结构的逆置邻接矩阵的特征向量。仿真图描述了一系列与特征向量有关的特征值。结果表明：网络的聚簇性并没有随着网络尺寸的增大而改变。224 同边函数与节点跳周边函数定义为大多数节点之间的跳数

14、，周边函数是对图的输出的一个测量。距离分布和节点跳并没有随时间而改变，这是一个很好的度量比较指标。这是我们绘出了在节点跳内节点能否互相到达的百分率。值得注意的是，近来其他测量方法已经被提出来作为图的测量比较方法。一个基于邻接节点度的概性方法已经被提出来了。23 图产生器早期的图产生器对图的倾斜度分布的匹配是失败的，在思想上，近来的图产生器用幂率分布产生拓扑结构。早期的 Barabasi-Albert 模型通过偏好连接产生图：在新的节点连接已经存在的节点时，它趋向于连接度数大的几点。Mitzammacher 概括了近来产生器幂率分布的方法。为了阐述我们方法的优越性，用简化法简化 AS 层的拓扑结

15、构得到的相似图与 GLP比较拓扑机构的特性。值得注意的是：其他产生器和研究集中在网络路由层的拓扑结构。网络的本质特性与我们测量的特性是不同的，既然在不同粒度级别上模拟互联网络，这样节点拥有比较大的度就有了物理上的限制。24 简化图虽然在不同学科的不同对象中也出现了简化图和采样问题。例如：图的抽样已经应用到分布式计算文章的图的分隔中。随机抽样已经被转移用于了解不同图的问题。例如分隔逼近。尽管一些算法存在相似性，但这些算法人不能直接用于我们的减化法中，最近，特别是我们工作的会议版本出现之后，数据挖掘已经在不同起源的大图采样中应用了这种方法。25 多播路由作为我们减化法的一个补充，我们做了许多特别的

16、网络仿真，来验证我们的实验结果在真实图和生成图中是否一致。我们首先把我们的简化图应用于 ABT 和 CBT 这两个多播路由算法中，然后通过比较单播路由和多播路由在简化图和真实网络中的有效性来评价我们的简化法。我们选择最近作为一个研究课题的多播路由算法评价性能。多播路由与节点连接相对于图的拓扑结构更敏感。概括的说，多播路由在一组节点中建立了一个通信树，有两种方法来支持多对多组通信，在这里每个组同样是数据源。SBT 方法为每个数据源单独建立一棵树。CBT 方法建立一颗所有数据源可双向传递数据包的树。我们使用曾经用过的机制来比较这两种路由协议。我们不去讨论在多播路由仿真中这些是最重要的机制。但是这些

17、协议已经被应用到多播路由协议的评价中。时正率：在分布树种，我们从源点到接收点测量平均时延，这种机制捕获每个接受节点经过的端到端的时延，这对于实时交互应用是非常重要的。为了简便起见，我们假设时延与路劲长度成正比。结果 SBT 的平均时延超过了 CBT 的平均时延。树的代价率：树的代价是通过多播分布树的连接数量来测试的。它对路由表的效率进行了量化。SBT 树的生成平均代价率高于 CBT 树的平均代价率。最后，我们用多播有效机制比较我们的图，多播有效机制是通过对多播连接点数和单播跳点数的比较来正常测量的。按照成员数量 chuang 和 sirbu 提出了一个幂率分布关系来表示多播有效性对中小尺寸的多

18、播组是一个有效的近似。我们使用基于 SBT 多播路由算法的多播有效性和这种算法的幂率分布来验证我们简化法的有效性。3、缩减图分法这部分提出我们的方法对一个真实的应用服务器层网络拓扑进行采样，我们的方法分成 3 类：（1）删除方法，这种方法从图形中一个接一个的移出边和点，直到达到所需要的数量。 （2）合并方法，逐步使相邻结点合并，直到达到所需要的数量。 （3）探测方法，根据给定的探测方法，遍历所需数目的结点，保留这些结点的子图。为了保证符号的一致性，我们用字母来简化上述方法，来表示它们所属的分类，D 代表删除方法，C 表示合并方法，E 表示探测方法3.1 删除方法我们的删除方法是内嵌在以下框架中

19、：我们通过在每一个阶段移出图形中一定比例的结点来迭代缩减这个图形，输入为一个初始化图 G，有 n 个结点和 m 条边，在每一阶段，结点的 s%必须移除，最终总结点的 P%将从图形中被移除。一个阶段分成 n 步，每一步移除根据我们方法选出的一条边或一个顶点。在每一个阶段之后，呈现出多个连在一起的局部图形，最大的那个被保留。当图形 G 减少到大的有 n（ 1-P%）的结点时,停止。在每个迭代周期内仅减少这个图形的很少的百分比 S%，能够使最终的目标数量更准确，事实上，每个阶段减少结点的 3-5%是够我们所需要的减少量。我们只在每个阶段之后对存在的图形进行加和，这样可以加快进程。我们研究的删除方法有

20、以下：DRV（随机删除顶点）：以相同的概率随即删除顶点DRE（随机删除边）： 以相同的概率随即删除边DRVE（随机删除顶点和边）随机选择一个顶点，随机删除与这个顶点相连的边。DHYBB（DRVE 与 DRE 的混合方法）：这种方法，以概率 B 执行 DRVE 方法，以概率（1-B）执行 DRE 方法。例：概率执行 DRVE，概率执行 DHYB这种混合方法起源于我们对 DRVE 和 DRE 最初的研究，它们对我们的机制具有相反的性能，也就是说，当其中一种方法低估了我们机制的价值，另一种方法则高估，在我们的实验中对 B 取 9 个值，从 0 到 1.0，以 0.1 的增量增加，为了清晰，我们仅给出

21、了其中的一部分子集。3.2 合并方法这种方法通过合并相邻结点执行。以下两种方法在形式上不同。CRE（随机合并边）：随机选择一个边，合并其两结点，被合并的两结点的相邻结点成了新结点的邻居。这种方法在文献 27 中提到的随机匹配方法以及文献中的边粗化方法具有一定类似性。我们也考虑了 CRE 方法的概括化，一次结合更多的结点，但是结果不能让人满意，这里不再一一介绍。CRVE（随机结合顶点和边）：随机选择一个顶点，与随机选择的一个邻居结合。3.3 探测方法随机选择一个初始化的结点，根据给定的探测方法遍历这个图形，直到结点数目符合要求，保留包含这些结点的子图。所有被访问的结点和边组成最终图形，其中包括以

22、下两种探测方法。EBFC（宽度优先搜索）：随机选择一个结点，从这个结点开始进行宽度优先搜索，直到图形结点数目符合要求。EDFS（深度优先搜索）：随机选择一个结点，从这个结点开始进行深度优先搜索每一条随机的并且没有被遍历的边向前遍历，直到所访问的节点数目符合要求。4、分析与验证本节我们证明我们的两种缩减法，DRE 和 DRV，保持了结点度的幂率分布。更准确的说，我们的方法表明，如果原始图形 G 满足幂率分布，缩减成的图形 G 也同样满足，具有相同的指数分布。设原始图 G 有 n 个结点，n 条边， nd 表示度为 d 的节点数目，dave 为结点的平均度数，各数据之间的关系用如下公示表示：n=

23、，m=1/2 ，dave=2m/n.dnn用 n,m,nd,dave，分别表示被缩减之后的图形的相关值，因为我们的缩减方法具有概率性，这些符号表示相关随机覆盖预测值。假设度序列在以下公式中满足幂率分布：Nd=cn (1)2d其中 c= 并且 1， 为度的幂指数。我们希望在图形 G具有相似的性质。12nd当然，幂率分布是通过实验验证的，它们确实具有近似性。实际上公示（1）中 cn 的值2d不一定是整数，为了方便，我们想把公示(1)写成等式，把 nd作为度序列的近似值。4.1 DRE 和幂率分布的确定性试验中执行 DRE 方法，每次随机的移除一些边，保留最大的子图，这个过程分布形式，并不适于我们分

24、布研究，因为被删除结点的度的分布依靠 G 图形的拓扑属性。为了便于分析，我们通过另外的公式近似模拟 DRE 方法，这种过程便于分析。这种公式分为几步。首先，我们忽略了一个事实，DRE 移除了最大连通图之外的结点，边被删除之后没有考虑，图形 G 中所有结点的度的分布。因此在这个部分 G和 G 有相同的最高点并且 n=n。通过实验结果证明：通过简化法移除的结点具有较低的度，这样简化方法不当说影响到结点度分布的大致范围设 p=m/m，为图形中一条边被保留的概率，在第二个近似阶段以概率 q 移除某条边，其中 q=1-P。虽然这并不能保证最终的图形确切有 m条边，但是图形的期望值围绕 m左右，这两个进程

25、有相似的渐进性为。4.1.1 论点证明（非正式）这一章我们证明在图形 G中，结点的度满足 nd=cn ，c 为常数。我们的论证观2d点可以总结如下。假设 n 足够大， 。一般来说，G 图形中结点的度在 d/p 左右，1dn即（d-0.5 ）/P 与(d+0.5)/P 之间，最终图形 G，期望的结点度为 d，这个范围涵盖 1/P 个不同的度，并且因为度 c 接近 d/p，则值 nc 接近 nd/p。因为 d 太小，我们可以得到 nd(1/p)nd/p= ，以此保证相同指数的幂率分布1cpd我们提出一种更准确的论证，假设顶点 ，并且 deg(v)=k，结点 v 的边以概率 PV被保留，以概率 q（

26、q=1-p）被移除，这仅仅是成功概率 p 的柏努里过程，所以在 G中结点的度为 d 的概率是：PdegG(v)=d= =1/p （1）()kdkpdkp其中 = ，通过公式（1） ，有如下：dkp()dq(2 )()cnkdkdkpkdkdn从现在开始，不处理度的分布，我们处理度的频率 fd=nd/n，这样可以考虑极限情况，这是第三次也是最后一次逐近最终的图形。我们可以归纳如下：序列 （3）d0,代表原始图形的度的频率，其中 。通过fdc 11()dc公式（2）缩减图形的度的频率用如下公式表示：（4）cdkpkdf这一章节的其他内容须是证明 fd满足幂率分布 ，其中1fdcpd，除极少数情况下

27、满足 x=y，即xy()()xyv引入一个随机变量 Yd，满足 ，其中 ，Yd 的期望值为dkpYpd，差额值 ，这可以()/EYddq2(1)/EYqp由 其中 xd-1 是具有负的二项式分布的随机变量，由文献 44 中理论，1X设 ，可以得到如下公式：3/4()（5）22 dVYqpdpYd首先，在引理 1 中，估计 的期望值，然后，通过引理估计 fd的值d引理 1：任何常指数 并且概率 p， ，有如下：(0,1)()ddkpkdEY证明：把 分成若干数据，中间的部分 =T+M，其中 EYddk kknddkTppkdkdM使用 和不等式（5） ，差额分布是：Yd2 (1)/22() ()

28、Tpddqpd 因为 ，证明 （6）)(/)Mp我们把“ ”， “ ”分开估计，通过 M 和 的定义我们得到()()(/)()kdndkndMdpd 并且在公式 5 中2() ()(1/()/(kdndkndMpqpddp 这就完成了公式（6）和引理的证明为了完成我们主要结论的证明，值得注意的是，在定义（4）中。使用引理中 的估计值，我们的得出了 ccdkppkfdEYEYd的结论1(/)/)f d引理 1：假设对于一些常量 ，起始图的度频率满足 。G 是用fdc的概率移除边得到的简化图，在图 G中期望的度分布频率满足(0,)p1fdc换句话说，引理 1 证实 DRE 方法满足幂率分布：如果在

29、图 G 中度分布顺序是，那么经简化后的图度序列满足具有相同指数的幂率分布。nC4.2DRV 和幂率分布一种类似的有关 DRE 的论证也可以应用到 DRV，这里我们仅仅列出一些解释（利用前面章节分析的相似性，我们可以进行正式的论证） ，设 ，我们认为 DRV 方法np以概 独立从图形 G 中移除顶点，粗略的讲，结点度的范围为（d-0.5 ）/P 与(1)qp(d+0.5)/P。最终 G图形中的结点度为 d（重复） ，其他结点或者被删除或者它们的度不是 d，既然这可范围覆盖了 1/p 的不同度，度 c 接近与 d/p， 的值接近于 ，我们预计 d 不能cn/ndp太小， ，保持相同指数的幂率分布。1/ndpC5、简化图的评6、简化图法与构造法的比较7、多播路由仿真8、结论3 和 4 是重点