异质化带宽分配下的复杂网络数据流负载问题研究*

于灏 周玉成 井元伟 徐佳鹤 张星梅 马妍3)

1)(东北大学信息科学与工程学院,沈阳 110004)

2)(中国林业科学研究院木材工业研究所,北京 100091)

3)(青岛理工大学经济与贸易学院,青岛 266520)

(2012年7月17日收到;2012年12月23日收到修改稿)

1 引言

随着小世界[1]和无标度[2]等重要的网络特性在20世纪末被陆续发现,越来越多的科研工作者开始通过复杂网络的视角来审视和研究自然和人类社会当中的复杂系统,投身于复杂网络的研究中[3-8].复杂网络的数据流研究是其中的重点研究方向之一.伴随着网络数据流量的不断增加,发生传输拥塞是不可避免的.所以,尽可能地提升拥塞发生临界的网络负载能力便成了要解决的核心问题.许多科研工作者此前做出了大量的研究,取得了丰硕的成果.文献[9]提供了一个状态参量,为分析网络自由状态向拥塞状态转变提供了完美的理论描述方式;文献[10—16]提出了多个能够提高网络负载的路由策略;文献[17]发现了网络数据流负载与网络介数的关系,发现网络负载与网络节点的最大介数成反比;文献[18,19]提出了通过删除网络上的一些边,降低网络节点最大介数,能提高网络负载能力的‘删边扩容’方法,文献[20,21]分析了匀质化的带宽分配下的网络负载能力变化.文献[22]提出了一种带宽分配方案,针对其文中的路由策略,对相对重要的连接边有所偏重地分配带宽,达到了提升网络性能的目的.

通常对网络数据流负载提升问题的研究主要从两方面入手：一是寻求更适合数据传输的网络拓扑结构,二是找寻更高效的路由策略.先前的许多研究中很少把连接边带宽约束加以考虑,在节点处理能力强的网络中,连接边的传输容量限制往往成为导致拥塞发生的重要原因.科学研究和生活经验证明,网络中连接边的带宽约束往往作为制约网络数据流通的一个瓶颈,既然多数的现实问题不能回避和忽略带宽约束,那么把合理有效的带宽分配作为充分利用和发挥网络资源优势,提高网络数据流通效率的重要武器将更具有现实意义.

因此,本文在流量模型中加入了连接带宽约束机制,从制约数据传输的网络关键拓扑特性出发,提出了一种异质化网络带宽分配方案;并结合路由选择策略,运用连接带宽的分配来调节网络中数据流的流向,从而实现缓解网络拥塞发生,提升网络的负载能力;同时,定性分析了流量变化的过程及其原因.本文第二部分介绍了网络模型和数据流模型;第三部分介绍本文提出的带宽分配方案;第四部分模拟并分析应用带宽方案的网络数据流,第五部分是结论.

2 网络模型与数据流量模型

2.1 网络拓扑模型

2.1.1 WS小世界网络

作为复杂网络研究的一个重大发现——小世界现象,反映了许多现实网络中所具有的大的聚类系数和小的平均距离的特性.为了构建能反映出这种特性的网络,Watts和Strogatz[1]于1998年提出了小世界网络模型,称为WS小世界模型.该模型可以看作是从规则网络向随机网络的过渡过程,其构造算法如下：给定含有N个点的最近邻耦合网络,其中每个节点都与它左右相邻的各K/2个节点相连,以概率p随机地重新连接网络中的每条边.其中规定,任意两个不同的节点之间至多只能连一条边,并且每一个节点都不能有边与自身相连.

在WS模型中,p=0对应于完全规则网络,p=1则对应于完全随机网络,通过调节p值就可以控制从完全规则网络到完全随机网络的过渡[6].

2.1.2 BA无标度网络

近年在复杂网络研究上的另一重大发现就是许多复杂网络,包括Internet,WWW以及新陈代谢网络等的连接度分布函数具有幂律形式.由于这类网络节点的连接度没有明显的特征长度,故称为无标度网络.为了解释幂律分布的产生机理,Baraba´si和Albert[2]提出了一个无标度网络模型,被称为BA无标度网络模型.BA模型包含着两个主要特性：1)增长(growth)特性,即网络的规模是不断扩大的;2)优先连接(preferential attachment)特性,即新的节点更倾向于与那些具有较高连接度的节点相连接,这种现象也称为“富者更富(rich get richer)”或“马太效应(matthew effect)”特性.BA网络模型构建如下：

1)初始网络,具有m0个节点;

2)网络生长过程,每一步加入一个节点v和m条边(m≤m0);

2.2 数据流量模型

本文采用加入连接边传输容量限制(带宽约束)的网络数据流量模型,具体描述如下.

把N个节点的网络中的每个节点看作主机和路由器的结合体,同时具有产生、转发、接收数据包的能力;每个节点i的数据包处理能力为Ci,即每单位时间步节点i最多可以处理Ci个数据包.为简单起见,定义每个节点的数据包处理能力Ci都相同,且为常数.节点拥有无限长的缓冲队列,新加入的数据包放置在队列的尾部,并按照“先入先出”(FIFO)原则处理;新产生的数据包选择源节点和目标节点是随机的;单位时间步,整个网络中新数据包的产生率为R;网络拥塞仅发生在节点端.

此外,每条连接边传递能力定义为带宽B,即单位时间步每条边上单向最多可以有B个数据包在传递,且一条边上同时有相向传递数据包时互不影响.如果带宽使用饱和,那么数据包仍被储存在发包节点的缓冲队列当中.抵达目标节点的数据包将立刻从网络中去除.

网络上的数据包流量可以看作两部分,一部分由新流入网络中的数据包构成,另一部分则是到达目的地从网络中消失的流出数据包构成.当两者流量平衡时数据流处于自由流状态,当前者大于后者时数据包开始在网络中累积,达到一定的累积程度时网络拥塞开始发生.为了清晰地描述网络中的自由流状态向拥塞状态的相变过程,这里引入一个相变参量η[9]：

其中η(R)是R的函数,〈ΔW〉是相邻时刻网络中总数据包的平均增加量.当R＜Rc时,网络中流入和流出的数据包能够平衡,〈ΔW〉≈0,此时η≈0,网络处于自由流状态;当R＞Rc时,〈ΔW〉随时间的增长逐渐增加,数据包开始在网络中累积,此时η＞0并持续上升,数据流进入拥塞状态,并且拥塞随η值越大,越显明显.因此,拥塞转变发生在R=Rc时,Rc是使网络的自由流状态向拥塞状态相变的临界值,标志此时网络达到了最大的负载能力,也因此把R作为网络负载的标志,本文把Rc作为网络最大负载能力.

路由选择策略：采用一种全局信息和局部信息相结合的具有拥塞感知能力的路由算法.假设数据包从源节点s传递到目标节点t.首先,对节点邻居节点执行局域搜索.如果发现了目标节点,则数据包被直接送达目的地,否则,就按照如下策略寻找下一投递节点.

首先,计算节点s的所有邻居节点的权值ωi.对于邻居节点i来说,权值ωi通过如下表达式进行计算：

其中,Li→t是节点i到目标节点t的最短路径长度,Qi是节点i当前所存储待处理的数据包个数,相当于路由器的缓冲队列长度,α是一个可以调节的参数,其范围位于0和1之间.当节点i发生拥塞时,Qi的值会非常大.

然后,选取权值最小的节点作为下一个路由节点.如果权值最小的节点有多个,那么随机选取其中一个.

依照上述过程直到找到目标节点t.

当参数α=1时,或节点没有累积数据包时,该算法则退化为最短路径路由算法(SPR),当α向0靠近说明路由线路在远离最短路径.

3 带宽分配方案

介数(betweenness centrality or betweenness)代表了网络经过节点(边)的最短路径的数目,如果节点(边)介数较高就说明通过该节点(边)的最短路径较多,所以经过该节点(边)到达其他节点(边)的平均路径长度也就较短.通常一对节点之间进行传递,经过最短路径无疑会使传递的成本最低.但在多对节点同时发生传递时,就会使经过最短路径数目多的高介数节点负担加重,产生拥堵的概率加大.

网络节点介数对负载的影响起到至关重要的作用[17],存在如下关系：

即网络最大负载能力Rc与网络最大节点介数g∗成反比.

理论上改变网络结构,降低网络节点的最大介数能够提升网络的负载能力.为了不破坏网络现有结构,本文提出一个带宽分配方案来降低高介数节点负载,提升网络整体负载能力,可以看作改变网络结构提升负载的等效方法.

3.1 异质化带宽分配方案

网络中的边被划分成“受控边”和“非受控边”两部分,受控边的带宽为b1,非受控边的带宽为b2.这里,在考虑连接边带宽约束的网络上,把整个网络带宽资源作为一个固定的总量来看待.

为了确定“受控边”,首先计算每个节点的介数,并为整个网络匀质化分配带宽——每条边分配带宽b0,网络上的带宽总量为B=b0M,M是网络总的边数;然后,给每条边赋权σij=gi·gj;其中gi和gj分别是一条边两端节点的介数,按权值从大到小的顺序排列,将σij最大的那条边删除,在删除边的过程中,如权值最大的边有多条,则随机选取一条;同时,标记删去的边,作为“受控边”放入一个“受控边”表中;重复上述过程直到达到设定的“受控边”比例上限 fce或网络连通性遭到破坏停止,“受控边”表中标记的删除边按删除的先后顺序排列.这样就确定了网络中的“受控边”.

为“受控边”表中的边分配带宽b1,且b1≪b0,即：单位时间步只允许相对较少数据包通过该边.这样,保证了网络的连通性,同时大大降低了这些“受控边”的数据包传递能力.并为非受控边分配带宽当 fce=0时,网络带宽为匀质化分配b1=b2=b0.

4 仿真与分析

分别选取BA无标度网络和WS小世界网络作为网络拓扑平台.网络规模都为1000个节点,且为无向网络.BA网络模型初始节点互不相连m0=m=3,〈K〉=6;WS网络模型随机重连概率p=0.3,〈K〉=4.节点节点数据包处理能力都为100,每条连接边的初始带宽为b0=10,受控边带宽b1=1.在流量模型中,运行5000时间步后认为网络流量达到稳定,取后1000步的平均值来计算.仿真结果均取20次独立实验的平均值.

图1反映了在受控边比例变化时BA网络模型中网络负载能力的变化.可以看出受控边比例 fce适度增加时,网络的负载能力有不同程度的增加,当受控边比例 fce加大到一定程度时,网络中的负载能力开始下降,说明了受控边比例在网络中存在最优值.α值为达到Rc时的值,可以看出,通过异质化地分配带宽,使得数据流向得以改变(α值改变反映了网络数据流向的变化,而α具体值属于路由算法的性质,不是本文重点,故在后面不再讨论).在图1仿真中BA网络的最优受控边比例 fce出现在0.45附近.

图1 BA网络N=1000,m0=m=3,在不同受控边比例时η与R变化对比

在我们的流量模型中,Soiut不仅受到节点i处理数据包能力Ci的限制,还要受到节点i连接边带宽总量Bi的影响,即Siout=min(Ci,Bi).因此,尽量做到Ci和Bi接近是既不浪费资源又能提升负载性能的理想状态.在我们的仿真中,BA网络的节点度最大值为102,fce=0时节点i连接边带宽Bi=b0Ki.此时,最大度节点总的连接边带宽Bi达到1020,而节点的处理能力是100,Ci≪Bi,因此在高度数节点存在着带宽资源的浪费.BA无标度网络中存在少数中心节点,拥有非常高的度,而大部分的一般节点度都较小,小于网络节点度的平均值.在本文的仿真选取的BA网络中,一般节点的连接边带宽要小于60,Ci＞Bi,这些节点的Siout受限于带宽,提升这些节点的连接边带宽格外重要.

从图2中可以看出,BA无标度网络中,度数大的节点往往也是介数高的节点,节点的度与介数之间具有正相关性,且仿真中的BA网络Pearson Correlation Coeffi cients达到了0.95.因此,根据我们的带宽分配方案,在BA网络中度数高的节点周围会出现大量受控边.

图2 BA网络中,各个节点的度和介数,插图是序号1—50的节点相应的度和介数

图3 显示了随着网络中受控边比例的增加,中心节点的连接边带宽资源被减少,并且减少的这部分带宽资源被均匀地分配给了带宽资源不足的一般节点,使得整个网络各个节点的连接边带宽资源分配更加趋于均衡.

图3 BA网络中,在受控边比例 f ce=0,0.1,0.2,0.3,0.4时,节点连接边带宽Bi的变化

这里,我们引入统计中的标准差概念来反映均衡程度和异质程度.标准差值越小代表越均衡,反之则表明异质性强.

图4是在BA网络中受控边增加时,节点连接边带宽的标准差变化.随着受控边比例在BA网路中增加,带宽标准差值是持续下降的,网络中节点的连接边带宽在趋于均衡.

图4 BA网络(m0=m=3,〈K〉=6)节点连接边带宽Bi标准差在不同受控边比例下的变化

图5 WS网络(p=0.3,〈K〉=4)节点连接度分布

图5 和图6分别是WS网络节点度分布和介数分布,可以看出WS网络的度分布较为均匀,而介数分布异质性较大.在对WS网络平台仿真中,图7反映了WS网络节点连接边带宽Bi的标准差和网络最大负载能力Rc随受控边比例增加的变化.发现 fce为0.1(±0.01),带宽标准差出现最小值时,网络带宽分布最优,同时负载能力最大.再加入受控边的过程中,计算节点连接边带宽Bi标准差与网络负载能力Rc的Pearson Correlation Coeffi cients为-0.87,可以看出,在WS小世界网络中节点的连接边带宽分布得越均衡,网络整体的负载能力越强.

由于WS小世界网络中,虽然介数分布异质,但度分布均匀,在为负载重的节点周围加入相对较少的受控边就能使得网络各个节点的负载和带宽相对均衡,使得负载和带宽具有较强的相关性;而BA网络中,无论是节点介数还是连接度,中心节点与一般节点的差异性很大.所以,达到网络最大负载能力时,各个节点间的节点连接边带宽Bi仍然存在较大异质性.

图6 WS网络(p=0.3,〈K〉=4)节点介数分布

图7 WS网络(p=0.3,〈K〉=4)节点连接边带宽Bi标准差和网络最大负载能力R c在不同受控边比例下的变化

图 8 WS 网络 (N=1000,p=0.1,0.2,0.3,0.4,0.5,〈K〉=4)节点度的标准差变化

网络节点度的标准差可以衡量网络拓扑结构的异质程度,标准差值越大网络拓扑异质性越强.从图8可以看出,WS小世界网络拓扑异质化程度随着p值增大而加强.从图9中可见,在WS小世界网络中,最优节点连接边带宽分布和相对应的受控边比例都随着网络异质性加强而增加.

图 9 WS 网络 (N=1000,p=0.1,0.2,0.3,0.4,〈K〉=4)节点连接边带宽Bi标准差最小值和网络最大负载能力R c在不同受控边比例下的变化

5 结论

存在节点度或介数异质化分布的网络中,在数据包传递过程中存在一定量的冗余路径.当一些节点数据包负载较重时,存在可以绕开这些节点的其他路径.我们发现,节点的处理能力相同且带宽分配匀质时,负载重的中心节点受限于自身的数据处理能力,其周围连接边占据着大量过剩带宽资源;而具有同样数据处理能力的一般节点通常都是带宽较少,在需要一般节点为中心节点分担负载的时候往往又受限于连接边的带宽.根据这一发现,提出了带宽分配方案,通过合理地释放一些节点过剩的带宽资源,把部分中心节点周围的连接边变成“受控边”,减少“受控边”的带宽,在不破坏网络拓扑结构的同时释放出“受控边”的带宽资源分给其他一般节点周围的连接边,以此来提高带宽资源的利用效率,提升网络的负载性能.在相同类型和规模的WS网络中,异质化程度越高,相应网络中冗余边存在的比例就越高,也因此需要加入的受控边比例也越高.我们也对相同规模不同网络做了仿真,发现异质化程度高的网络,达到最优负载时需要加入的受控边比例相应也高.

引入异质化带宽分配方案使得BA网络负载性能提升主要来自于两部分贡献,其一是异质化带宽分配方案有效地限制了涌向中心节点数据流量,有效缓解了中心节点拥塞,将部分负载转向一般节点,相对平衡了各个节点的负载;其二是将中心节点的过剩的连接边带宽分配给连接边带宽不足的一般节点,使得大多数节点连接边的传递能力增强,同时更好地消化转移过来的负载.

对于WS小世界网络,由于节点度分布均匀,带宽约束对所有节点的数据流量都起到了制约作用.加入少量受控边就会使得各个节点的连接边带宽达到最佳状态,同时实现网络负载能力的最优.

本文中,带宽分配方案是与感知节点拥塞的路由算法配合应用的.在特殊情况下,受控边的带宽为0时,本套方案仍然有效.值得注意的是,如果使用最短路径路由时,加入受控边带宽为0则需要重新考虑网络拓扑结构,按照删除受控边后新的网络结构重新计算最短路径,否则会造成数据包在原来最短路径上的节点处大量累积,大大降低网络负载能力.

总之,本文提出的异质化带宽分配方案,优化了网络上带宽资源的分配,有效调节网络流量走向,使得网络总体负载能力较匀质分配带宽时有较大提升,为提高网络负载性能研究提供了一个新思路.

感谢中国科学研究院计算所(北京)的张国清副研究员对于删边扩容效应以及算法实现上的热情讨论和帮助.

[1]Watts D,Strogatz S 1998 Nature 393 440

[2]Barab´asi A L,Albert R 1999 Science 286 509

[3]Ohira T,Sawatari R 1998 Phys.Rev.E 58 193

[4]Faloutsos M,Faloutsos P,Faloutsos C 1999 Comp.Commun.Rev.29 251

[5]Albert R,Barab´asi A L 2002 Rev.Mod.Phys.74 47

[6]Newman M EJ2003 SIAM Rev.45 167

[7]Wang X F,Chen G R 2003 IEEETrans.Circuits Syst.3 6

[8]Hao B B,Yu H,Jing Y W,Zhang SY 2009 Physica A 388 1939

[9]Arenas A,Diaz-Guilera A,Guimera R 2001 Phys.Rev.Lett.86 3196

[10]Wang W X,Wang B H,Yin CY,Xie Y B,Zhou T 2006 Phys.Rev.E 73 026111

[11]Yan G,Zhou T,Hu B,Fu ZQ 2006 Phys.Rev.E 73 046108

[12]Chen Z Y,Wang X F 2006 Physica A 364 595

[13]Wang D,Jing Y W,Zhang SY 2008 Physica A 387 3001

[14]Pu CL,Pei W J2010 Acta Phys.Sin.59 3841(in Chinese)[濮存来,裴文江2010物理学报59 3841]

[15]Danila B,Yu Y,Marsh JA,Bassler K E 2006 Phys.Rev.E 74 046106

[16]Wang D,Yu H,Jing Y W,Jiang N,Zhang SY 2009 Acta Phys.Sin.58 6802(in Chinese)[王丹,于灏,井元伟,姜囡,张嗣赢2009物理学报58 6802]

[17]Guimer`a R,D´ıaz-Guilera A,Vega-Redondo F,Cabrales A,Arenas A 2002 Phys.Rev.Lett.89 248701

[18]Zhang GQ,Wang D,Li GJ2007 Phys.Rev.E 76 017101

[19]Zhang G Q,Cheng S Q 2012 Sci.Sin.Infom.42 151(in Chinese)[张国清,程苏琦2012中国科学(信息科学)42 151]

[20]Hu M B,Wang W X,Jiang R,Wu Q S,Wu Y H 2007 Euro.Phys.Lett.79 14003

[21]Yu H,Jing Y W,Zhou Y C,Ma Y 2010 Journal of Northeastern University(Nat.Sci.)31 1226(in Chinese)[于灏,井元伟,周玉成,马妍2010东北大学学报(自然科学版)31 1226]

[22]Ling X,Hu M B,Du WB,Jiang R,Wu Y H,Wu QS2010 Phys.Lett.A 374 4825