利用ＳＤＧＰ算法进行实时动态带宽分配的研究及仿真

摘 要：提出一种在网络通信带宽分配领域，结合自动控制理论，利用基于优先级的串行主导因子法对链路带宽进行动态分配的方案。该算法通过引入主导因子和容忍因子，可以实现在具有流量工程基础的网络中对共享带宽进行实时动态分配。

关键词：基于优先级的串行主导因子法；主导因子；容忍因子；带宽分配

中图分类号：TP393.04 文献标识码：A 文章编号：1004373X(2008)1506704

Research and Simulation for Dynamic Bandwidth Deployment with SDGP Algorithm

YU Xi,LI Dan

(College of Information Science and Technology,Chengdu University,Chengdu,610106,China)

Abstract：This pager refers to a dynamic bandwidth deployment method called SDGP algorithm,which comes from automatic control theory.SDGP has capability to locate the bandwidth in flux engineering network dynamically by introducing two control parameters: Leading key ξ and acceptance key ρ.

Keywords：SDGP;leading key;acceptance key;wideband distribution

1 引 言

现代网络技术中，以提升网络服务质量，提供更多网络业务为目的的网络构建，越来越多地使用到流量工程。以基于MPLS (Multiprotocol Label Switching，多协议标签交换)的PWE3(Pseudo Wire Emulation Edge-to-Edge，边缘到边缘的伪线仿真)网络为例，不是随时都存在足够资源，使每条Pseudo Wire连接都能拥有完全独立的LSP流量路径，这就不可避免地存在多条Pseudo Wire共享一段LSP链路的有限带宽，如图1所示\。

这种情况不仅局限于PWE3网络，在其他具有流量工程基础的网络中，在配置链路共享带宽时，都会遇到以下问题：

可操作性问题 配置方法复杂，专业性强，配置时需要网络设备制造商的技术支持人员进行指导，用户自行配置易出错。

合理性问题 用户通常知道每条连接的数据流的重要性，却只能简单采用固定带宽分配方法为每条连接分配相应带宽，这种分配方法随意性较大，存在不合理因素。

灵活性问题 用户常常希望在保证合理性的基础上，根据自身需求，能够进行更为灵活的带宽配置，比如允许分配的带宽值在一定的接受范围内进行浮动。

及时性问题 用户完成带宽分配后，通常很长时间内保持不变，更新率低。不能及时根据网络流量变化调整，使有限的带宽得到优化配置。

为解决以上网络中共享带宽的分配问题，需要研究一种易操作、合理的、灵活的、及时的、能充分利用网络资源和提升网络效率的实时动态带宽分配算法。这里的“实时”指表现这种带宽分配算法的及时性，“动态”则表现了这种算法进行带宽配置需要以动态变化的数据流量为主要依据。在这种需求下，通常会首先考虑到应用流量反馈进行实时带宽分配控制。但是网络带宽分配的控制具有其特殊性，具体表现在：带宽限制对使用不同协议流量源的影响是不确定的，其作用反馈到使用不同协议的流量源上，使得网络流量增加、减少或者不变都是有可能的。因此流量反馈的实时带宽分配控制方案，在研究诸如PWE3网络环境的动态带宽分配算法上，并不是理想的研究方向。

本文提出的一种解决方案是：在网络通信带宽分配领域，结合自动控制理论，利用基于优先级的串行主导因子法(Serial Dominant Gene with Priority,SDGP)对链路带宽进行动态分配的方案。通过引入主导因子ξ和容忍因子ρ，实现PWE3网络中共享带宽的实时动态分配。同时，SDGP算法也能够为其他具有流量工程基础的网络提供实时动态带宽分配方案。

2 SDGP算法原理

仍以PWE3网络为例，某条链路可分配的共享带宽为Bwmax。某时刻，该链路具有N条优先级从Pri0到PriN-1(Prii=Prii+1或Prii=Prii+1-1，0≤i≤N-2)的Pseudo Wire数据流。其中优先级数值越小，代表优先级越高，故Pri0=0优先级最高，且不存在优先级跳跃情况。从优先级Pri0到PriN-1，具有相同优先级的数据流条数表示为ε0,ε1,ε2,…,εk(0≤k≤N-1)，其中k表示N条数据流中，共有k个不同的优先级别，且εm(0≤m≤k)与N具有以下关系：∑km=0εm=N (0≤k≤N-1)(1) 当使用SDGP方法后，系统将进行周期为T的实时检测和调整，重新分配从Bw0到BwN-1的各条数据流的带宽。重新分配带宽的计算顺序基于每条数据流的优先级，从优先级最高的流开始，逐步分配带宽，直到优先级最低的数据流带宽分配完毕。Bwi表示第i条数据流应分配的带宽。Bwrevi则表示第i条数据流分配后，链路剩余的共享带宽值。两者关系为：

Bwrevi=Bwi+1+ Bwrev(i+1) (0≤i≤N-2)(2)

且不难推导Bwi,Bwrevi和Bwmax的关系为：Bwrevi=Bwmax-∑ij=0Bwj

(0≤i≤N-1,0≤j≤N-1)(3) 在进行每条数据流的带宽分配时，引入两个重要调节控制因子：主导因子ξ和容忍因子ρ。ξi(0≤i≤N-1)表示第i条数据流的主导因子；ρi(0≤i≤N-1)表示第i条数据流的容忍因子。在通常需求下，网络中所有数据流的主导因子都相同，且所有数据流的容忍因子也相同，即ξi=ξ，ρi=ρ，(0≤i≤N-1)。

主导因子ξi的物理意义表示第i条数据流相较其余优先级更低的数据流，在链路剩余共享带宽中应该分配得到带宽的比率。经过主导因子处理过的目前剩余带宽称为第i条流的主导带宽，表示为Bwξi(0≤i≤N-1)。Bwξi在利用主导因子法进行带宽分配时，具有重要作用。当共享带宽的数据流优先级严格区分，互不相同的情况下，Bwξi计算方法为：Bwξ0=Bwmax×ξ(4)

Bwξi=Bwrev(i-1)×ξ (1≤i≤N-1)(5) 当共享带宽的数据流优先级存在重叠现象时，需要利用εm(0≤m≤k)对以上两个公式实施改进，以支持优先级重叠时Bwξi的计算。假设对优先级为Prii-1(Prii-1

Bwξi=Bwrev(i-1)×ξ′

(ξ′=ξ/εm,1≤i≤N-1,0≤m≤k)(7)

Bwtemp=Bwrev(i-1) (1≤i≤N-1)(8)

当Prii=Prii-1时:

Bwξi=Bwtemp×ξ′

(ξ′=ξ/εm,1≤i≤N-1,0≤m≤k)(9)

下文未加说明处，所使用的主导带宽Bwξi均指利用支持优先级重叠的改进算法，由式(6)到式(9)计算得到的。

容忍因子ρi的物理意义表示当第i条流实际流量不足其Bwξi带宽时，是否容忍其继续占有多余带宽与主导带宽Bwξi的比率。值得注意的是，容忍因子ρ根据其应用方式不同，表现出较大灵活性，不仅适用于本节SDGP算法需要，即系统中流量不足引起的“下容忍”，也可以调节流量过载引起的“上容忍”，甚至对系统剩余保留带宽Bwrev也能进行容忍范围调节。本节研究的SDGP算法所涉及的“下容忍”标线称为容忍带宽，表示为Bwtoli，其具体算法为：Bwtoli=Bwξi×(1-ρ) (0≤i≤N-1)(10) 在一个T周期内，第i条数据流实际流量表示为Fluxi(0≤i≤N-1)，当第i条流分配带宽时，先利用容忍带宽Bwtoli与Fluxi进行比较，根据比较的结果不同，进行相应的带宽分配。如果判断为不能容忍第i条流分配到过多带宽，则只对第i条流分配其流量加上容忍因子所容忍的最大额度流量带宽；如果判断为第i条流的闲置带宽为0，或者在容忍范围之内，对其分配的带宽等于主导带宽Bwξi大小。具体实施分配策略如下：

Bwi=Bwξi (当Fluxi≥Bwtoli时,0≤i≤N-1)(11)

Bwi=Fluxi+Bwξi×ρ

(当Fluxi

当在一个T周期内，利用主导因子法完成所有数据流的带宽分配后，延时到下一个周期到来，并再次利用主导因子法，根据下一个周期到来时，实时流量的状况进行带宽分配，从而实现基于SDGP算法的实时动态带宽分配。

根据以上分析，不难看出主导因子ξ和容忍因子ρ之间关系表现为：主导因子ξ对共享带宽进行主要的、粗糙的分配和调节；容忍因子ρ则对ξ调整后的带宽进行细微的，灵活的二次调配。只有两者相互配合，共同作用，才能根据系统流量及时合理地利用SDGP算法进行系统的实时动态带宽分配。

3 SDGP算法实现

在上节SDGP算法原理研究的基础上，本节将对SDGP算法的具体实现进行讨论。考虑到工程实现的方便性、移植性和维护性，故采用算法组件化思想对SDGP算法系统划分为3大组件单元：SDGP Kernel Unit,Stream Information Collection Unit和Assignment Execution Unit。具体架构如图2所示。

图2 SDGP算法系统实现架构当网络节点使用能SDGP算法模块进行实时动态带宽分配后，Stream Information Collection Unit将在每个T周期开始时，负责实时收集Network Node上需要进行带宽分配的数据流信息。这些收集到的信息可以直接实时传送到SDGP Kernel Unit，也可以保存在Trace文件中再供给SDGP Kernel Unit使用。SDGP Kernel Unit的作用是对进行收集到的需分配共享带宽的数据流信息进行分析，并根据SDGP算法进行带宽指派。经过SDGP Kernel Unit完成的带宽分配信息，将传递到Assignment Execution Unit，由其进行具体的带宽分配下发工作。

在整个SDGP算法模块中，SDGP Kernel Unit处于核心地位，其处理流程图如图3所示。

图3 SDGP Kernel Module处理流程4 SDGP仿真及结果分析

SDGP实时动态带宽分配算法仿真方案如下：

假设在基于MPLS的PWE3网络中，存在7条Pseudo Wire流(从Stream0到Stream6)需要共享一段100 Mb/s的LSP链路带宽。其中，Stream0的优先级为0，Stream1和Stream2的优先级为1，Stream3,Stream4和Stream5的优先级为2，Stream6的优先级为3。当完成设置主导因子ξ和容忍因子ρ，且使用SDGP算法后，7条数据流开始进行流量变化，以检测SDGP算法是否能够及时合理地动态调整带宽分配。其流量变化的具体策略为：首先7条流都具有100 Mb/s流量，然后Stream0由100 Mb/s开始，每隔一个T=1 sec依次减小5 Mb/s，直到Stream0流量变化为0，接着Stream1开始模仿Stream0进行流量变化，直到Stream1流量变化为0，依此类推，剩余Stream2到Stream6的流量依此规律进行变化，直至需要共享此段带宽的7条数据流量都减至为0。这种流量输入设计策略的好处在于，不仅可以收集每个T周期所完成的流量分配数据，还可以收集到多条数据流从流量过载变化到流量不足过程中，SDGP算法进行实时动态处理的带宽分配数据，比较全面反映了SDGP算法对流量变化的应对处理结果，为准确地进行仿真分析奠定了基础。

以下使用Network Simulator 2在Linux环境下对SDGP算法进行仿真，以观察其性能。其中，主导因子ξ和容忍因子ρ具有不同配置。部分SDGP Kernel Module代码见附录。

当ξ=0.5，ρ=0.1时，仿真结果如图4所示。

当ξ=0.7，ρ=0.1时，仿真结果如图5所示。

当ξ=0.5，ρ=0.2时，仿真结果如图6所示。

当ξ=0.7，ρ=0.2时，仿真结果如图7所示。图4 ξ=0.5，ρ=0.1时SDGP算法的动态带宽分配情况图5 ξ=0.7，ρ=0.1时SDGP算法的动态带宽分配情况图6 ξ=0.5，ρ=0.2时SDGP算法的动态带宽分配情况图7 ξ=0.7，ρ=0.2时SDGP算法的动态带宽分配情况 由上述仿真结果，对主导因子ξ和容忍因子ρ对SDGP算法的影响进行分析。比较图4与图5，或者图6与图7，当容忍因子ρ相同时，主导因子ξ=0.7时，优先级最高的Stream0在流量足够大的时候，分配的带宽70 Mb/s明显高于主导因子为ξ=0.5时所分配到的50 Mb/s。即使Stream0流量变化为0时，主导因子ξ=0.7时也能够分配到7 Mb/s闲置带宽，而主导因子ξ=0.5时，只能分配到5 Mb/s闲置带宽。其余Stream1到Stream6的仿真数据也都呈现此规律。由此表明，当容忍因子ρ相同时，数据流在相同流量的情况下，主导因子ξ越大，所分配的带宽越大。

比较图4与图6，或者图5与图7，当主导因子ξ相同时，如果Stream0流量足够大且不存在闲置带宽的情况下，其带宽分配均为50 Mb/s，容忍因子ρ的大小对其没有影响；如果Stream0流量下降到可以分配到闲置带宽的情况，Stream0分配得到的带宽，相较容忍因子ρ=0.1时，在容忍因子ρ=0.2时更晚出现下降的现象。且当Stream0流量变化为0时，分配的带宽在ρ=0.2时为10 Mb/s，而在ρ=0.1时为5 Mb/s。其余Stream1到Stream6的仿真数据也呈现出规律。由此表明，当主导因子ξ相同时，容忍因子ρ越大则容忍分配到闲置带宽的比例越大。

综合SDGP算法仿真结果，可以充分说明，SDGP算法根据需要共享链路带宽的数据流(从Stream0到Stream6)的流量信息和优先级信息，能够实时合理地动态调节带宽分配，达到SDGP的设计初衷。

根据以上分析，结合主导因子ξ和容忍因子ρ的物理意义，可以得到下面结论：主导因子ξ越大，当优先级高的数据流流量足够大时，总是能分配到更多的带宽；容忍因子ρ越大，表示该条流能被容忍占有更多的闲置带宽。用户可以根据自身业务需要，方便地调节主导因子ξ和容忍因子ρ，使SDGP算法在实时动态带宽的分配上，取得用户预想的效果。另外，T越小，表示动态调整带宽的时间粒度越细，共享带宽得到更及时地分配和调整。但当数据流条数较多时，减小周期T也会增加系统向硬件下发带宽配置的时间开销。

5 结 语

综上所述，SDGP算法能够较好地实现，包括PWE3在内的具有流量工程基础网络的实时动态带宽分配，具有良好的可操作性、合理性、灵活性与及时性。

参 考 文 献

［1］沈清,马林.十大电信热点技术\.计算机世界报,2005(7):90-100.

［2］Rosen E,Tappan D,Fedorkow G.RFC3032:Multiprotocol Label Switching Label Stack Encoding..cn/qkpdf/moet/moet200815/moet20081523-2.pdf" style="color:red" target="_blank">原版全文