无标度网络中的临界负荷和拥塞不稳定性外文翻译资料

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

无标度网络中的临界负荷和拥塞不稳定性

摘要

我们研究无标度通信网络对拥塞的抵抗能力。当由于某种原因某个节点的负荷超过其容量从而发生故障时，就把该节点的负荷按照一定的策略分配给网络中的其他节点。这些节点接收了额外的负荷，其总负荷也有可能超过其容量，从而导致新一轮的负荷重新分配。这个过程反复进行，影响的节点逐渐扩散，从而产生相继故障。我们研究的是由于边的拥塞所引发的相继故障。

最近已经对几个自然和人工网络建立了复杂的模型^[1-3]。发现互联网和万维网（WWW）（其中路由器或网页表示节点）具有很多连接到外部设备的节点。最近收集的经验证据表明，这种独特的特征是通过分析统计数据发现的^[4-11]。例如在互联网中，统计分析揭示，平衡状态下，节点个数与节点的度k可以用， ^[5,7,11]表示。这是最近确定的一类针对无标度（SF）网络的主要表示方法^[2]。 很多类似的例子可以证明统计物理学方法是用于研究复杂网络的有价值的工具，并且近年来已经报道了关于在复杂网络上发生的动态过程的一些有价值的研究成果。特别地，SF网络中安全阈值^{[12，13，14,15]}的缺失对系统具有很大的影响，没有安全阈值，实际上是减小了系统对随机损害的抵抗能力^[16]。安全阈值是一种在通信网络中非常重要的属性，保证了系统的稳定性。

SF网络的渗透特性仅指静态拓扑连通性^[12,13]。另一方面，在互联网和其他通信网络中，许多不稳定性是由于负荷拥塞^[17,18]导致的。发生拥塞的节点或边上的负荷被自动转移到网络上没有发生拥塞的节点或边上，这些节点接收了额外的负荷，其总负荷也有可能超过其容量，从而导致新一轮的负荷重新分配。这个过程反复进行，影响的节点逐渐扩散，从而产生相继故障使网络崩溃。因此，这些不稳定性具有动态性质并且取决于负荷如何在网络中路由和分配。然而，到目前为止提出的几个模型都是处理常规结构^[19,20]的。最近，已经有一些学者来尝试研究静态^[21,22]和推演^[23,24]复杂网络中的相继故障。

在本文中，我们提出了一个简单的模型，旨在研究在SF网络中由于拥塞边或节点的负荷重新分配导致的相继故障。我们发现系统的行为取决于施加到网络上的平均负荷。在平均负荷的临界值之上单个边或节点的故障有可能触发整个网络雪崩。因此，本文分析了网络承载的负荷从自由阶段到拥塞阶段的函数变化规律。与静态渗流过渡发生的情况相反^[12,13]，加载的SF网络展示了一个有限的阈值，如果我们考虑在其上面承载的负荷的动态，系统可以由小的损伤发展成宏观不稳定性。这是在对更完整的实时通信网络中负荷不稳定性建模时的一个重要步骤。

为了更好地表示SF网络的程度波动，我们将在下面使用Barabaacute;si-Albert模型^[25]。这是一种随机增长模型，从小节点m₀开始，并且在每个时间都引入新的节点。新节点连接到m个旧节点（这里m=3）的概率，与节点的度k_i满足的关系。该方案的重复迭代得到具有拓扑结构的复杂网络，其特征可以用函数，其中，来表示。原则上，也可以考虑更一般的复杂网络类型^[2,3]。

为了模拟SF网络上沿着边传递的数据包的通信量，考虑到故障情况下的负荷重新分配，我们需要指定网络的初始容量。假设过载发生在最小路径之后，这样的负荷由网络中通过节点i ^[23,24]的任何两个节点之间的最短路径的总数给出。最近在SF网络中的研究表明，这个负荷称为安全阈值^[26,27]。网络的这种性质也可以根据边来定义。然而，在实际系统中，每个边携带的负荷是波动量，其取决于许多变量，例如用户数量，路由协议和可用带宽等。为此，我们将连接网络节点i和j之间的路径称之为边，边上的负荷表示为，从指定系统的初始容量的概率分布中绘制^[28]。为了简单起见，我们考虑了对于的均匀分布，采取如下形式：

这个均匀分布意味着边承载的最小初始负荷由平均负荷的非零值限定。这意味着将不存在负载小于该下限的边。本文报道的结果是用初始分布来获得的。为了测试关键行为的普遍性，我们也考虑形如的分布，这允许存在具有非常小的负荷的边，而不考虑平均负荷流经系统的情况。两个分布和产生了相同的定性结果。 与负荷一样，我们将每个边与相同容量C相关联，为了一般表示，我们取C=1。该选择可以被认为是近似的，因为通信网络中的线路带宽之间可能相差很大。从这个角度来说，我们认为不同量的负荷通过网络的流动是差异性的最重要的来源。

随机选择边，并通过提高其负荷来过载。当边承载的负载是，即当它超过边的容量时，则表明这条边发生了拥塞，并且其携带的负荷转移向不过载的相邻边。负载的重新分配可能会引起其他边发生过载，从而触发相继故障。我们探索了三种不同的负荷重新分配规则。第一种我们将其称为随机分配负荷或丢弃。第二种是随机分配或全局分配。第三种是平均分配或全局分配。最后，我们注意到在拥塞边的负载可以在网络中所有剩余工作线路之间平等地共享或者从网络中丢弃。我们通过在BA网络上反复应用上述规则进行了大规模数值模拟。在模拟中使用的网络的大小范围从N=5*10³个节点（15*10³个边）到N=10⁵个节点（3*10⁵个边）不等。所有数值结果都是通过对10个不同的网络进行平均计算得到的，至少实现了100个初始负荷的重新分配。

为了检查动态不稳定性的发生，我们构建系统的相图。图1给出了网络具有最大连通子图的概率与网络平均负荷的关系。在系统已经达到稳定状态（当对于所有的i和j，时）时，对应不同的动态分配规则均有一个临界值 。当时，网络会以一定的概率处于拥塞状态。

图.1系统的相图给出了网络有最大连通子图的概率与网络平均负载的关系。图中三条曲线分别对应三种分配策略：（a）随机分配负荷或丢弃；(b)随机分配或全局配；(c)平均分配或全局分配。网络包含N=10⁴个节点（3*10⁴个边）。

如果网络的最大连通子图为零，则网络的通信能力被破坏，并且系统将发生相继故障。

在图1中，我们绘制了与的关系图。在平均负荷的低值处，网络总是达到稳定状态，其中孤立节点的数量非常小，并且概率，此时网络是最完整的。当增加施加在网络上的负荷时，系统开始产生不稳定性。特别是，当负荷在临界负荷以上（其值取决于所考虑的模型）时，系统将会以一定的概率处于拥塞状态。网络中同时发生过载的边的数目S的概率分布近似服从幂指数为1的幂律分布。当平均负载为，我们得到，即，平均负荷大于0.82时，任何不稳定性都会导致整个网络中所有的边拥塞，直到网络的完全崩溃。值得注意的是，这种情况与其中具有大的节点集团的概率在转变点处从一突然下降到零的渗透性情况非常不同。这里，概率连续地衰减到零，在一个比较宽的区域，其中一定的故障可以以概率触发大规模拥塞。此外，我们提供了完全隔离节点的密度的度量。在没有一个大的连通子图的情况下，大多数网络可以看成隔离的节点。图2表示在没有大的连通子图存活的情况下孤立节点的密度S与概率的关系。这种分布也在相对较大的值处达到峰值，这证明了一旦一个主要故障被触发，它几乎影响网络的整体。

从图1可以看出时的平均负荷的值相对较高。另一方面，明显小于1的值远低于通过各个边的容量C = 1测得的网络的理论容量（，见图1 ）。

图2，对于不同的，和S的函数分布图，网络由N=10⁴个节点构成

这个证据定义了负荷值的宽区域，其中存在小的但是有限的概率，小的不稳定性通过系统传播，并且可以解释为什么在实际通信网络中可以不时地遇到不同程度的拥塞。在图1中，我们还报告了先前定义的通过不同动力学规则获得的曲线，并且有趣的是，我们注意到对于模型的确定性在保守版本里已经获得了最高水平的稳定性（）。此外，过渡的动态不依赖于初始负载的分布和网络尺寸N。

另一种阐明拥塞动态的方法是检查拥塞不稳定性的生成过程。我们定义拥塞脉冲或雪崩的大小s作为网络最大连通子图的故障规模。对于施加在网络上的平均负荷的值有三个不同范围，范围大于s的累积分布在图3中为本模型的随机分配或丢弃的分配原则。主图是对数线性刻度，因此一条直线观察到大小为s的雪崩的概率是形式为的幂函数。已经发现因特网的几个特征的幂指数为-1的幂函数，例如延迟时间，队列长度和拥塞长度^[19,32,33]。在图中我们专注于靠近稳定的区域的研究分析，网络不必非常接近临界点，便遵守几个量幂律分布。图3表示了拥塞边的累积大小也随系统大小的改变而改变，然而缩放动态性保持不变。这可以帮助理解为什么在实际通信网络中观察幂率分布要针对不同的网络大小测量，即针对局部网络和延伸到大规模的网络。

图3网络承受不同的平均负荷时，故障规模S的累积概率分布

总之，我们引入了一个简单的阈值模型，目的在于描述由于SF网络的拓扑性质的负荷拥塞引起的不稳定性。结果指出网络可以自由处理高于临界负荷的负荷。高于该水平，网络面临部分拥塞，其开始在各种地方建立局部瓶颈，并且小的不稳定性可能以有限概率触发相继故障。高于临界负荷值任何小的不稳定性都将导致整个网络崩溃。类似于在互联网的实验研究中观察到的，在网络负载的中间区域,同时崩溃的网络数量遵循无相加权法。我们希望我们的工作将对互联网建模和WWW大规模交通行为提供准确的参考。

***

这项工作得到了欧盟委员会 - Fet Open COSIN IST-2001-33555项目的部分支持 。YM感谢来自教育大学教育学院的资金支持（西班牙，SB2000-0357）。RP-S感谢西班牙部长的财政支持。

参考文献

[1] Strogatz S. H., Nature (London), 410 (2001) 268.

[2] Albert R. and Barabaacute;si A.-L., Rev. Mod. Phys., 74 (2002) 47.

[3] Dorogovtsev S. N. and Mendes J. F. F., Adv. Phys., 51 (2002) 1079.

[4] Barabaacute;si A.-L., Albert R. and Jeong H., Physica A, 281 (2000) 69.

[5] Faloutsos M., Faloutsos P. and Faloutsos C., Comp. Com. Rev., 29 (2000) 251.

[6] Broder A., Kumar R., Maghoul F., Raghavan P., Rajagopalan S., Stata R., TomkinsA. and Wiener J., Comput. Networks, 33 (2000) 309.

[7] Govindan R. and Tangmunarunkit H., in Proceedings of IEEE INFOCOM 2000, Tel Aviv,Israel (IEEE, Piscataway) 2000.

[8] Caldarelli G., Marchetti R. and Pietronero L., Europhys. Lett., 52 (2000) 386.

[9] Chen Q., Chang H., Govindan R., Jamin S., Shenker S. J. and Willinger W., Proceed-ings of INFOCOM 2002, Twenty-First Annual Joint Conference of the IEEE Computer andCommunications Societies, Vol. 2 (IEEE) 2002.

[10] Broido A. and Claffy K. C., in SPIE International Symposium on Convergence of IT andCommunication, Denver, 2001.

[11] Pastor-Satorras R., Vaacute;zquez A. and Vespignani A., Phys. Rev. Lett., 87 (2001) 258701;Vaacute;zquez A., Pastor-Satorras R. and Vespignani A., Phys. Rev. E, 65 (2002) 066130.

[12] Cohen R., Erez K., ben-Avraham D. and Havlin S., Phys. Rev. Lett., 85 (2000) 4626.

[13] Callaway D. S., Newman M. E. J., Strogatz S. H. and Watts D. J., Phys. Rev. Lett., 85(2000) 5468.

[14] Pastor-Satorras R. and Vespignani A., Phys. Rev. Lett., 86 (2001) 3200.

[15] Pastor-Satorras R. and Vespignani A., Handbook of Graphs and Networks: From t

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[137134]，资料为PDF文档或Word文档，PDF文档可免费转换为Word