随机带宽分配对复杂网络传输性能的影响分析

于 灏，马 妍，王新华，井元伟，周玉成，王 丹

（1.山东科技大学经济管理学院，山东 青岛266590；2.青岛理工大学经济与贸易学院，山东 青岛266520；3.东北大学a.工商管理学院；b.信息科学与工程学院，辽宁 沈阳110819；4.中国林业科学院木材工业研究所，北京100091；5.沈阳大学装备制造综合自动化重点实验室，辽宁 沈阳110044）

0 引言

研究任何现实系统时都不能忽略的一个重要问题，就是资源的有限性，在复杂网络传输问题研究上也不例外。现实网络传输系统发生拥堵的主要原因来自于网络资源方面的限制，通常在网络传输中的资源限制主要包括两个方面：一是网络节点资源的有限性，例如：通信网络路由器的转发能力和缓冲区的队列长度限制，交通网络中的交通枢纽站点的转运能力和容纳能力等；二是网络中连接边的容量（带宽）资源的有限性，它主要是指网络中连接边在单位时间运送数据包的能力，例如：通信网络的传输带宽限制，交通道路上承载车流量的能力等等。除了提高网络资源供给之外，制定有效的资源分配策略是提高网络传输性能的必要手段。在考虑连接边带宽资源限制下的复杂网络传输问题的研究中，文献［1］分析了平均分配带宽时，带宽限制对网络传输性能的影响。文献［2］提出了一种“反直觉”的带宽分配方案，通过引入“受控边”优化了带宽资源的利用效率，使得网络负载性能较匀质化分配带宽有了很大提升，文献［3］设计了带宽分配方案，有效地改善了网络负载性能。本文通过设计异质化随机带宽分配方案来分析带宽分配对网络传输性能的影响。

1 传输流量模型

在本文传输流量模型中，网络中的所有节点被看作是主机和路由器的结合体，具有产生、储存、传递数据包的功能。每个节点的处理数据包能力为Ci，规定每个节点的处理能力Ci相同且为常数。每个节点容量为无限大，且每个节点缓冲队列中等待发送的数据包都是按照先入先出的规则按顺序进行处理。连接边只具有传递功能。如发生网络拥塞仅出现在节点处。R为数据包产生率，即：单位时间内新加入R个数据包。数据包的出发节点和目的节点随机选取，到达目的节点后的数据包自动从网络上移除。数据包的传递依照路由策略进行。其中路由策略以文献［4－6］中的路由策略方案为基础，并加以改进得到——G－L路由策略。

G－L路由策略中的节点权值为

其中，Li→t为节点i到目标节点t的最短路径长度，Qi为节点i当前所存储待处理的数据包个数，相当于路由器的缓冲队列长度，α为一个可以调节的参数，其范围位于0和1之间。Bi为节点i的连接边带宽，即节点i所有相邻连接边带宽的总和。

路由选择策略中，选取相邻连接节点权值最小的节点作为下一路由节点，进行传递。如遇到最小权值节点不唯一的情况，则随机选择一个作为下一路由节点。

为了更好描述网络传输中流量状态变化过程，引入状态相变参数η来进行描述［7－9］：

其中，〈ΔW（t）〉为相邻时刻网络中总的数据包变化量。Rc作为网络流量由自由流状态向拥塞状态转变过程中数据包产生率的临界值。当R＜Rc时，网络系统中产生的数据包和到达目标节点的数据包数量维持均衡，此时η值近似为零，网络传输系统处于稳定的自由流状态；当R＞Rc时，网络传输系统不能及时地、完全地消化新产生的数据包，数据包在网络中开始累积，此时系统进入拥塞状态，且η值伴随着R的增加而增大，同时η值越大，表示拥塞程度越高。最终η＝1时，网络传输系统处于完全堵塞状态，此时代表网络中新产生的数据包一个都不能传出，全部滞留在网络中。本文中把传输效率最高时的状态相变临界值Rc作为网络最大负载能力的标志进行研究。

2 随机带宽分配方案设计

为了通过带宽随机分配对网络传输的影响，探索合理的分配方案制定依据，本文设计了两种随机带宽分配方案：完全随机带宽分配方案和分类随机带宽分配方案来进行研究。

完全随机带宽分配方案：为每条连接边随机分配带宽集合B∈［a －b］，1≤a＜b中的带宽值。为了使得每次随机分配带宽的网络传输之间能够进行性能比较，这里规定网络的连接边带宽资源总量固定为常数BT。

分类随机带宽分配方案：为网络中的每条边分配权值σij＝gi＊gj，其中gi和gj分别为连接边两端节点i和节点j的介数，网络边的平均权值为。网络的边被分成两组E1和E2。E1中，所有连接边权值小于或等于平均边权值；E2中，所有连接边权值大于平均边权值。网络连接边的平均带宽，选取两个带宽集合B1∈［a～］，1≤a＜和B2∈分别为两组边随机分配带宽集B1，B2中的带宽值。规定网络的连接边带宽资源总量固定为常数BT。

3 随机带宽分配网络流量仿真与分析

选取HK－BA无标度网络［10］作为网络拓扑平台。网络规模为1 000个节点。网络模型初始节点互不相连m0＝m＝3，调节概率为0.5。

应用完全随机带宽分配方案，带宽集B∈ ［1 ～ 10］。使用最短路径路由策略（SPR）（α＝1）和G－L路由策略

既然完全随机带宽分配不是实用有效的带宽分配方式，为了进一步探求带宽的“合理”或接近“合理”的分配方案，下面讨论研究本文提出的另一种带宽分配方式——分类随机带宽分配方案。仿真中，网络平均带宽带宽集B1∈［1～5］，B2∈（5～10］。网络的连接边带宽资源总量固定。

为了清晰比较，选取4种带宽分配与路由策略的组合进行网络传输性能的对比。4种组合及对比关系如图2所示，方框中标明了带宽分配与路由策略的组合方式，双向箭头代表组合间进行对比。每种组合分别进行20次试验，其结果的平均值呈现在图3～图6。在各组合采用的路由策略下，平均分配带宽（每条边的带宽都相等，为5）的网络最大负载作为对比中间值。（α＝0.7）选取了20组流量试验得到的各自最大负载（每组20次试验的平均结果）（见图1），所有试验中网络节点处理能力相同Ci＝50。图1中纵坐标是代表网络最大负载能力的Rc值，横坐标是试验组序号，圆形标示是最短路径路由策略下网络带宽完全随机分配时的网络最大负载值，方形标示是G－L路由策略下网络带宽完全随机分配时的网络最大负载值。通过图1发现：1）在应用同一路由策略网络时，随机分配连接边带宽产生了不同的网络最大负载能力，且无法判断其中规律；2）在相同带宽分配的网络中，应用G－L路由策略所产生的网络最大负载都要高于应用最短路由策略时的网络最大负载；3）相对于最短路径路由策略，G－L路由策略在不同带宽分配时，对网络最大负载影响方面表现出较强的鲁棒性。

从以上对完全随机分配带宽方案的研究，可以看出，完全随机地分配网络连接边带宽对网络负载的影响带有不确定性，因此，这种方案不是一种实用有效的带宽分配方案，但同时也发现不同带宽分配时，不同路由策略对网络性能的影响情况是不尽相同的。

文献［4－6］对路由策略的性能的分析比较可以说明图1发现中的第2点。下面来分析图1中的第3点发现。网络连接边的介数反映了某条边在网络中的重要性，边介数高代表网络中通过这些边的最短路径数量较多。在应用最短路径路由时，数据包传输路径严格遵循着由拓扑结构决定的最短拓扑距离线路，此时，通过高介数边的数据包相应较多，并且整个网络的数据包流向也是向着最高介数边方向聚集，如果随机分配带宽时，分配到这些重要的介数高的边的带宽值很小，就会造成数据包在这些边附近的节点大量累积，造成传输流量放缓，并很快拥堵，降低网络传输性能。G－L路由策略本身能够根据网络局部节点数据包的拥塞程度的动态信息而选择调整流向，离开最短路径传输线路，这使得部分数据流避免涌向数据包最聚集的地方，能够一定程度上缓解拥塞的发生，因此，使得G－L路由策略在遭遇上面所述高介数边被分配小带宽时，网络性能表现不会像最短路径策略时那么糟糕。而当网络上连接边带宽的分配较为合理时，最短路径策略路由下的网络负载能力得到提升，此时，采用GL路由策略的路由线路也会靠近最短路径线路。因此，G－L路由策略可以根据网络不同带宽分配情况，通过调节远离或靠近最短路径线路，来保持随机性分配对网络最大负载影响方面的鲁棒性。

图1 完全随机异质化带宽分配时，SPR与G－L路由策略下网络最大负载Fig.1 Maximum load with SPR and G－L routing strategy with complete random heterogeneous bandwidth allocation

图2 带宽分配与路由策略组合对比关系Fig.2 Correlation of bandwidth allocations and routing strategies

图3 采用组合1时，网络流量状态Fig.3 The network traffic with group 1

图4 采用组合2时，网络流量状态Fig.4 The network traffic with group 2

图5 采用组合3时，网络流量状态Fig.5 The network traffic with group 3

图6 采用组合4时，网络流量状态Fig.6 The network traffic with group 4

由图3与图4可以看出，采用组合1方式分配带宽时网络的最大负载能力Rc要高于组合2带宽分配方式下的。对比图5与图6可以看出，采用组合3方式分配带宽时网络的最大负载能力Rc要高于组合4带宽分配方式下的。并且，组合1、组合2仿真得到的网络最大负载分别优于组合3、组合4的。

节点介数可以表示理论上通过某一节点的最短路径的数量，也就是说在网络传输中节点的介数越高代表了数据包通过它的概率越高。在分类随机带宽分配方案中，这里为网络中的每条边分配权值σij＝gi＊gj，其中，gi和gj分别为连接边两端节点i和节点j的介数。此时，网络中边的权值σij高的边意味着在网络传输中占据着重要的位置，这些边会是网络上数据包流经量很高的边，肩负的传递负担也重。因此，在带有带宽约束限制的网络中，为权值高的连接边分配的带宽量对网络传输性能会产生重大的影响。

组合2、组合3中，为低权值的边（E1）分配低带宽值（B1），相应权值高的边（E2）分配高带宽值（B2），这种分配方式下的网络最大负载均高于各自网络带宽均分时产生的网络最大负载。因此，在网络总带宽资源固定情况下，负载较重的高权值边得到相应较高的带宽分配会得到较好的网络传输性能。

组合2、组合4中，为低权值的边（E1）分配高带宽值（B2），相应权值高的边（E2）分配较低带宽值（B1），这种分配方式下的网络负载性能均劣于各自网络带宽均分时产生的网络负载性能。此时，由于网络传输中总的带宽资源是固定不变的，为传输负载较重的边分配较小带宽会带来网络传输抑制数据包传递过程，而分配传输负载较轻的边较多带宽存在带宽的浪费，从而影响到网络负载性能，造成整个网络负载能力降低。

此外，采用G－L路由策略的组合1、组合2带宽分配下网络传输性能分别优于采用最短路由策略的组合3、组合4，说明文中的分类随机带宽分配方案没有影响到路由策略本身对网络传输性能的作用效果。

4 结论

设计了完全随机带宽分配方案和分类随机带宽分配方案。通过仿真试验发现，完全随机地分配网络连接边带宽对网络负载的影响带有不确定性，因此，这种方案不是一种实用有效的带宽分配方案，同时还发现，G－L路由策略相对于最短路由策略在保持带宽随机分配对网络最大负载影响方面具有较好的鲁棒性。在对分类随机带宽分配方案的研究中发现，在介数存在异质性分布的复杂网络中，为依据介数由高到低的边集分派相应由高到低的带宽集，有利于提升网络负载性能。

［1］ 于灏，井元伟，周玉成，等.固定带宽下的无标度网络数据传输流量分析 ［J］.东北大学学报（自然科学版），2010，31（9）：1226－1229.Yu Hao，Jing Yuanwei，Zhou Yucheng，et al.Dynamic analysis of scale－free network traffic with fixed bandwidth［J］.Journal of Northeastern University（Natural Science），2010，31（9）：1226－1229.

［2］ 于灏，周玉成，井元伟，等.异质化带宽分配下的复杂网络数据流负载问题研究 ［J］.物理学报，2013，62（8）：080502.Yu Hao，Zhou Yucheng，Jing Yuanwei，et al.Traffic dynamics of the complex networks with the heterogeneous bandwidth allocation［J］.Acta Phys Sin，2013，62（8）：080502.

［3］ Ling X，Hu M B，Du W B，et al.Bandwidth allocation strategy for traffic systems of scale－free network［J］.Physics Letters A，2010，374（48）：4825－4830.

［4］ Echenique Pablo，Oacute，Garde Mez，et al.improved routing strategies for internet traffic delivery［J］.Physical Review E，2004，70（5）：056105.

［5］ Chen Z Y，Wang X F.A congestion awareness routing strategy for scale－free networks with tunable clustering［J］.Physica A－Statistical Me－chanics and Its Applications，2006，364：595－602.

［6］ 王丹，于灏，井元伟，等.无标度网络中拥塞转变的动态分析 ［J］.东北大学学报（自然科学版），2009，30（4）：462－465.Wang Dan，Yu Hao，Jing Yuanwei，et al.Dynamics of jamming transitions in scale－free networks［J］.Journal of Northeastern University（Natural Science），2009，30（4）：462－465.

［7］ Arenas A，Danon，Diaz G A，et al.Local search with congestion in complex communication networks［J］.Lecture Notes in Computer Science，2004，3038：1078－1085.

［8］ Wang D，Jing Y W，Zhang S Y.Traffic dynamics based on a traffic awareness routing strategy on scale－free networks［J］.Physica A－Statistical Mechanics and Its Applications，2008，387：3001－3007.

［9］ 王丹，于灏，井元伟，等.基于感知流量算法的复杂网络拥塞问题研究 ［J］.物理学报，2009，58（10）：6802－6808.Wang Dan，Yu Hao，Jing Yuanwei，et al.Study on the congestion in complex network based on traffic awareness algorithm［J］.Acta Phys Sin，2009，58（10）：6802－6808.

［10］Holme P，Kim B J.Growing scale－free networks with tunable clustering［J］.Physical Review E，2002，65：026107.