支持QoS的多链路最少变换动态带宽分配算法

梁根，俞鹤伟，孙立民，秦勇

（1.广东石油化工学院 理学院，广东 茂名 525000；2.广东省石化装备故障诊断重点实验室，广东 茂名 525000；3.华南理工大学 计算机科学与工程学院，广东 广州 510641；4.东莞理工学院 计算机学院，广东 东莞 523808）

1 引言

多链路宽带接入网由于网络结构灵活、扩展能力强、建网成本低和故障率低等特性使之成为业界组网的首选方案[1]。网络应用的发展使数据传输己逐步由单一的数据传输过渡到数据、语音、图像等综合信息的传输，因此，新一代宽带接入网必须能够同时提供高速的包括实时业务在内的多种业务传输。然而，实时业务的传输不同于普通的数据传输，这些实时业务往往对服务质量（QoS，quality of service）指标如带宽、时延、抖动等有较高的要求[2]。因此，为了保证实时业务端到端的QoS，多链路宽带接入网作为端到端网络中的一段，必须要具备相应的 QoS保障能力。如何进一步优化组合资源、提供更好的带宽控制和更多样的宽带接入业务支持是多链路宽带接入网中热门的研究内容之一。

QoS是指数据分组在网络传输中的各种性能参数满足某业务的需求[3]，这些性能参数可以用传输时延、分组丢失率、时延抖动、吞吐率和带宽利用率等指标来度量[4]，其主要目的就是为各种业务提供可靠的端到端的QoS保证。为了达到一定的QoS保证，通常会在网络内采用某种带宽分配算法，通过对不同的业务分配不同的带宽来控制其QoS等级。

在带宽分配算法的研究中，不少学者和专家己经做了很多研究工作，目前来看，主要分为2类：静态带宽分配（SBA,static bandwidth allocation）算法和动态带宽分配（DBA,dynamic bandwidth allocation）算法[5]。

静态带宽分配算法SBA在一个轮询周期内为每个接入点AP（access point）分配固定大小的带宽，SBA算法不需要带宽协商过程，因此很简单，容易实现。但是，由于网络流量的突发性，会造成有的接入点负载较小，而有的接入点负载较大。负载较小的接入点不能充分利用带宽，其他负载大的接入点时延增大，系统吞吐量减小，造成带宽浪费。好的带宽分配算法应当能够根据系统的整体情况实时动态地调整各接入点的带宽分配[6]，SBA虽然简单，但在多链路宽带接入网中不是理想的方案。

因此，必须在系统内执行动态带宽分配算法DBA，也就是说，中央控制点根据每个接入点实时的带宽需求分配不同的带宽给每个接入点，这样才能提高带宽的利用率，降低分组时延，增加系统吞吐量[7]。

目前，国内外对DBA算法的研究有很多，在这里把这些DBA算法划分为两大类：一类不支持QoS的DBA算法；一类支持QoS的DBA算法。

不支持QoS的经典DBA算法有自适应交织轮询IPACT(interleaved polling with adaptive cycle time)算法[8]，该算法通过交叉轮询并且轮询周期长度随着带宽请求动态变化的方法来降低数据时延，从而提高系统带宽利用率。IPACT算法和SBA算法相比较，大大提高了带宽利用率，但它仍然存在以下缺点：一个是存在轻负载惩罚问题，因为IPACT算法轮询周期是不固定的，这样当系统的负载比较轻时，分配给每个接入点的时隙很短，轮询周期也相应变得很短，浪费了大量的带宽；另一个是IPACT算法是一种交织轮询算法，不足之处在于只是基于当前获取的接入点带宽请求信息来确定下一个接入点上行信道的带宽，而不能从全局的角度出发，考虑所有接入点的上行带宽请求来进行更合理的带宽分配；另外更重要的一点是，IPACT算法不支持QoS。

对于IPACT算法，国内外很多文献对其进行了改进。文献中提出了预估授权协议IPACT-GE(IPACT with grant estimation)[9]，IPACT-GE 对加速转发流(EF)的抖动性能进行了改进，对EF数据流采用报告前授权，对于EF流，抖动时延是完全确定的。IPACT-GE允许在收到反馈消息之前分配带宽，在前一周期的消息中，局端设备包含了EF数据的带宽分配信息。但是，IPACT-GE同样可能在DBA计算和授权信息往返之间存在空闲信道。文献采用多线程轮询的方式改进了IPACT算法，降低了数据时延，但是由于数据分组的时延抖动比较大，因此不适合语音业务。

支持QoS的DBA算法有增强突发轮询EBDBA(enhanced burst-polling DBA)算法[10,11]。在 EBDBA算法中，根据最小保证带宽，确定是立即给相关的接入点授权带宽，还是等待最后一个接入节点的反馈消息，进行DBA计算之后，再授权分配带宽。这种方法可以减少信道空闲时间，但如果所有接入节点终端都是重负载状态，那么这时候EBDBA算法失效，完全退化为IPACT。

国内有学者在支持QoS的EBDBA算法的基础上进行改进，提出了自适应动态带宽早期分配(ADBEA，adaptivedynamicbandwidthearly allocation)算法[12,13]，ADBEA算法不是根据最小带宽而是根据一个动态变化的门限值，对接入终端进行授权，对于超过门限值的带宽，下一个周期进行分配，当系统负载较低时，轮询周期较短，可以改进系统的时延性能，当系统负载较高时，轮询周期会相应加长，减少了终端间的保证时隙，提高系统的利用率，而门限值的确定，依据业务的最大时延需求确定，从而保证在系统负载较高时，仍能满足业务的时延需求。

上述算法解决了带宽分配的QoS支持问题，但是，上述算法均存在着若干缺陷，有待改进。首先，链路的带宽利用率有所下降，当系统带宽在满足各接入终端的请求后还有剩余带宽时无法继续使用；其次，由于授权的集中进行，局端必须在收到本轮所有请求后才能进行下一轮的授权，这样会导致在局端引入一部分等待延时；另外，更重要的是这些算法没有考虑到实际网络使用环境中带宽分配的变化对系统造成的负载和时延增加问题。

针对动态带宽分配问题，同时考虑到QoS的支持，为了适当地减少因带宽切换造成的实际影响，提出了一种支持QoS的多链路最小变换动态带宽分配方法MCDBA，该方法的主要思想是根据不同的优先级为不同QoS需求的业务分配带宽，为提高系统整体的带宽利用率，将剩余带宽进行重分配，同时加入时延及带宽利用率QoS限制，减少带宽切换对系统造成的不稳定性。

2 带宽分配问题描述

支持QoS的DBA算法在带宽分配架构上通常是基于节点型的[14]，首先为每个接入点分配一块带宽，再在接入点带宽内根据各业务的需求为各业务分配带宽。

2.1 带宽分配体系结构

如图1所示，在基于节点型的DBA中，中央控制节点根据接入点上报的请求带宽，按照某种分配原则为每个接入点分配一定数量的带宽，在每个接入点内，再由调度器负责把所获得的带宽分配给各类业务，在这种带宽分配方式中，中央控制节点仅仅分配给每个接入点总的带宽，接入点自行决定如何把分到的带宽在各个业务优先级队列之间进行二次分配。

图1 基于节点型的DBA

基于节点型的DBA中的队列调度算法，其实质就是基于Diffserv模型的队列调度算法。国内外对这方面的研究经历了相当长的时间，涌现出了很多成熟的调度算法，比如先到先服务、通用处理机共享、优先级调度、循环调度以及随机调度等[15]。但是，该架构下的动态带宽分配存在带宽利用率不高、不能对全网进行统一控制等问题。

由于在实际的网络使用环境中QoS类别相对较少和中央控制节点有较高的处理能力，因此设计了如图2所示的基于业务型的DBA架构，该架构由中央控制节点集中控制整个系统，各终端通过逻辑链路连接到某接入点，首先，在系统中计算某业务所能获得的总带宽，然后在该业务带宽内对每个接入点分配带宽，接入点通过反馈帧向中央控制节点报告它所有优先级队列的队列长度，该架构便于对全局进行统一控制，适用于核心交换机。

图2 基于业务型的DBA

2.2 动态带宽分配方法

在实际的网络使用环境中，业务的带宽需求是不断变化的，往往会造成网络流量的突发，如图3所示，在带宽充足的环境下记录的某业务在某段时间内的流量情况，即带宽需求。图4和图5表示的静态带宽分配算法SBA，在图4所示的最大静态带宽分配方法下，虽然数据分组的时延会较小，但是会导致系统总带宽利用率下降，若采用图5所示的平均静态带宽分配方法，系统总带宽利用率会提高，但是数据分组的时延会明显增大。

图6所示的是大部分常用的动态带宽分配方法，这些方法主要是根据带宽请求动态地分配带宽，但是，在实际的网络环境中，改变带宽的分配会花费系统更多的时间去完成，反而导致数据分组时延的增大[16]，过多的带宽分配变换会成为系统的一个重要负担。如图7所示，本文算法的主要目的就是在保证一定QoS限制的前提下，减少带宽分配的切换，达到尽量降低对系统的影响。

图3～图6中的细线代表带宽需求，粗线代表分配的带宽。

图3 某业务带宽需求

图4 最大SBA

图5 平均SBA

图6 基于带宽请求的DBA

图7 最小变换DBA

3 支持QoS的动态带宽分配理论分析

3.1 符号约定

设多链路接入系统内共有i个终端接入点，φi为接入点i的权重，由于本文侧重研究算法对QoS的支持，所以在这里假设每个接入点的权重相等，并且φi满足

实际的网络数据中包含语音、视频、数据等各种业务流，某些业务可能用于低时延，需要一定的稳定带宽保证，因此被分配较高权重；某些普通数据业务对时延、分组丢失不敏感，无特殊QoS要求，因此，可能被分配较低权重。假设系统支持m类业务，ωj为j类业务所能获得的保证权重，并且ωj满足条件

为了便于讨论，各符号定义如表1所示。

表1 符号定义

3.2 问题描述

QoS的支持通常希望端到端的时延最小，系统带宽利用率最高，数据分组丢失率最小，系统负载最轻，但这些目标的最优值往往不能同时达到。因此，带宽分配优化问题可以从其中的一个或部分参数去处理。

定义1系统总带宽容量为所有接入点分配到的带宽之和，即所有接入点中各类业务已分配带宽和可用剩余带宽之和，可得

定义2接入点初始带宽为系统的总带宽与接入点权重的乘积，即

定义3重负载接入点集合为接入点中各业务带宽需求总和大于该接入点的初始带宽的接入点集合，即满足

定义4轻负载接入点集合为接入点中各业务带宽需求总和小于或等于该接入点的初始带宽的接入点集合，即满足

3.3 支持QoS的动态带宽分配计算

假设j类业务所能获得的保证权重大于j+1类业务，因此，对于j+1类业务来说，要先完成j类业务的带宽分配，然后才能再对j+1类业务进行带宽分配。

假设系统在第T个轮询周期，在这个周期里，首先为j类(j=1)业务分配带宽。对于某接入点APi的j类业务，在该轮询周期开始时所分配的带宽为

对于j类业务未获得全部需求带宽的接入点，将剩余带宽按照以下方法重新进行分配。

1)当系统内的剩余的带宽大于或者等于不足带宽即Bresidual≥Black时，说明此时系统能满足j类业务的带宽需求，因此，剩余的系统带宽将被分别分配到各个接入点，由接入点将带宽分配给各自的j类业务，即

2)若系统内的剩余的带宽小于不足带宽即Bresidual＜Black时，则说明此时系统带宽不能满足j类业务的带宽需求，系统剩余带宽Bresidual将按一定比例分配给重负载的接入点。

这样，在该周期中，完成对j类业务的带宽分配。

对于j+1类业务的带宽分配，首先要计算已经分配到带宽的1到j类业务的总和，然后在分配j+ 1 类业务带宽之前重新初始化，因此可得

4 MCDBA算法

由2.2节的说明可知，在实际的网络环境中，带宽分配的改变往往会使系统花费更多的时间去完成，不但没有降低数据分组的时延，反而会导致数据分组时延的增大，过多的带宽切换会成为系统的一个重要负担，因此在本节设计一个算法，该算法控制带宽分配的切换次数。

4.1 MCDBA算法设计

为了说明MCDBA算法，新定义2个QoS变量Qd和Qu，其中Qd为QoS限制的时延上限，它表示系统内所有数据分组的平均时延不能超过该值；Qu为QoS限制的系统总带宽利用率下限，它表示系统的总带宽利用率不能低于该值。显然，Qd由业务数据分组的平均时延确定，当Qd变小时，数据分组的时延会减少；Qu由系统带宽利用率限制确定，当Qu变高时，会使系统整体带宽利用率上升。

4.2 MCDBA算法描述及步骤

在MCDBA算法中，通过Qd和Qu这2个参数控制带宽分配的变换。设在周期T中，按照3.3节的计算方法对各接入点和各业务进行带宽分配，若在该周期内，能够满足Qd和Qu，那么在下一个周期T+1中，将不进行带宽分配变换，避免因带宽分配变换造成的队列调整和系统负载，否则在下一个周期T+1中，在等待前一周期的数据全部发送完毕后，启用CONVERSION操作。在CONVERSION操作过程中等被重新设置，MCDBA算法描述及步骤具体如下。

算法说明：

1)QoS限制参数Qd和Qu可以在实际使用过程中根据系统状况动态调整；

3)先处理所有接入点中的高优先级业务带宽请求，通过判断不足带宽和剩余带宽计算需分配带宽的大小；

4)带宽分配变换可以是部分接入点。

5 实验及性能分析

5.1 实验环境、参数和方法

在实验测试中，采用OPNET Modeler仿真工具搭建了网络测试环境，并进行仿真测试。仿真实验环境包括一个中央控制节点，100个接入点，由此产生100条链路，并且假设链路的长度为5 km，各链路的固定传输时延均为3 ms，链路的最大带宽为100 Mbit/s，系统可供分配的总带宽为1 Gbit/s，具体的仿真实验参数如表2所示。

表2 仿真实验参数

假设系统产生的流量包含3种业务流量，其中最高优先级的EF数据流对应语音业务，是固定比特速率的数据流，该类业务流必须保证有较小的时延和时延抖动；中等优先级的AF数据流对应视频业务是可变比特速率的，该类业务需要有一定带宽保证；最低优先级的BE数据流对应数据传输业务对时延和抖动没有要求，需要提供尽力而为的服务。在实验中假设以上业务流数据分组的大小为64～1 518 byte之间平均分布，并且分别被随机分配到各条链路。

为评估MCDBA算法的性能，本文对比的算法为平均静态带宽分配算法SBA、不支持QoS的周期自适应交叉轮询算法IPACT、支持QoS的EBDBA和ADBEA算法，对以上算法的不同业务分组时延和带宽利用率进行对比测试。

5.2 实验结果分析

实验中链路的端到端时延主要由两部分组成：从中央控制节点到接入点的固定传输时延和数据分组在接入点缓冲队列中的排队时延，其中传输时延由链路的长度确定，它是一个固定值，在本实验中假设其为3 ms；排队时延的大小则主要由调度算法来确定，它反映了算法的性能。图8～图10所示为各种业务分组在5种带宽分配算法控制下的平均时延变化情况。

由于在开始阶段系统负载较小，并且存在足够的可用带宽，接入点的各种业务能得到足够的带宽分配，因此，各业务分组的平均时延相差不大；由图8可以看出，随着系统负载的增加，EF业务分组的时延开始出现较大不同。对于SBA，由于不能借用其他低优先级业务的带宽，当负载超过60%的时候，EF业务的时延超过了50 ms，并且时延出现增长趋势；IPACT的交叉轮询策略对于降低业务的时延有一定的作用，但是在处理EF业务上，分组的平均时延相比EBDBA与ADBEA，仍然高出约23%和34%；由于MCDBA先处理高优先级的业务，所以EF业务平均分组时延较其他4种算法有较大的降低。图9表示的是各算法的AF业务平均分组时延，由该图明显可以看出，SBA的时延最大，但是对于AF业务，IPACT、EBDBA、ADBEA与MCDBA的平均时延则相差不大。图10表示的是各算法的BE业务平均分组时延，SBA的BE业务时延最大时延达到约70 ms，与EF、AF业务基本相同；由于ADBEA的门限值可以动态变化，对于低优先级BE业务，在这5种算法中ADBEA显示出最好的性能；由于MCDBA算法的优先级顺序原因，对于BE业务，MCDBA和IPACT的性能差不多，但是时延分别比EBDBA与ADBEA高出约45%和26%，的MCDBA算法在处理低优先级业务的性能仍有待改善。

图8 EF业务平均分组时延

图9 AF业务平均分组时延

图10 BE业务平均分组时延

在测试各算法队列长度和分组丢失率的实验中，设定各接入点队列缓冲区的大小为1×106byte，超过缓冲区大小的分组将被丢弃。图11和图12反映的是接入点分组队列长度和分组丢失率的情况。可以看出，随着系统负载的增加，接入点队列缓冲区最先填满的是SBA，开始出现大量分组丢失的情况；当系统负载达到约60%的时候，IPACT和EBDBA出现分组丢失，并且最高分组丢失率达到约40%；由于在系统负载较高时，ADBEA轮询周期可以相应加长，MCDBA的剩余带宽可以重新分配，因此，重负载情况下，ADBEA和MCDBA的性能表现较好，直到系统负载超过了约75%才出现队列缓冲满和分组丢失的情况，并且最大分组丢失率不超过25%。

图11 接入点分组队列长度

图12 接入点分组丢失率

5种算法控制下系统带宽利用率如图13所示，由图13可以看出，随着系统负载的增加，各算法的系统带宽利用率都有持续的上升。由于IPACT算法轮询周期是不固定，在系统负载较轻时，浪费了不少的带宽，导致轻负载时其性能与SBA差不多，但是随着系统负载的增加，IPACT的系统带宽利用率比SBA有较大的提高；ADBEA比EBDBA在系统带宽利用率方面约有8%的提高，并且在重负载时最高带宽利用率比MCDBA高约6%；但是，该图也反映出在系统轻负载时，MCDBA较其他4种算法有较大优势的系统带宽利用率。

图13 系统平均带宽利用率

6 结束语

本文研究了带宽分配方法和带宽分配体系结构，提出一种支持QoS的最少变换动态带宽分配算法MCDBA，该算法支持多业务，利用剩余带宽重新分配提高了系统带宽利用率，并且通过QoS参数限制减少了带宽变换频率，解决了实际网络使用中因带宽变换造成的时延和系统负载增加，仿真实验证明该算法对于系统性能有一定的提高。

此外，对于大规模网络链路环境，下一步的研究工作重点是对提出的MCDBA算法进行接入点分区策略，对于主要承载不同业务的接入点，为了减少系统负载，对接入点进行分区，每个分区分别计算自己分区内主要承载业务的综合性能最优QoS限制，从而获得更佳的全网带宽分配。

[1] 林闯,李寅,万剑雄.计算机网络服务质量优化方法研究综述[J].计算机学报,2011,34(1):1-14.LIN C,LI Y,WAN J X.Optimization approaches for QoS in computer networks:a survey[J].Chinese Journal of Computers,2011,34(1):1-14.

[2]TOMKOS I,KAZOVSKY L,KITAYAMA K I.Next-generation optical access networks:dynamic bandwidth allocation,resource use optimization,and QoS improvements[J].Network,IEEE,2012,26(2):4-6.

[3] 徐战,王劲林,吴刚等.业务质量约束下最大化收益的HFC频点带宽分配方法[J].小型微型计算机系统,2012,33(6):1223-1227.XU Z,WANG J L,WU G,et al.HFC frequency bandwidth allocation method based on constraints of QoS and maximum revenue[J].Journal of Chinese Computer Systems,2012,33(6):1223-1227.

[4] ZHENG J,MOUFTAH H T.A survey of dynamic bandwidth allocation algorithms for ethernet passive optical networks[J].Optical Switching and Networking,2009,6(3):151-162.

[5] 张晋豫,刘犁.基于效用EPON分布式动态带宽分配实现机制[J].软件学报,2008,19(7):1693-1706.ZHANG J Y,LIU L.Implement mechanism on distributed EPON DBAbased on utility[J].Journal of Software,2008,19(7):1693-1706.

[6] 张耀东,王钺,霍金海等.基于业务认知的多用户带宽分配方法[J].通信学报,2013,34(2):109-116.ZHANG Y D,WANG Y,HUO J H,et al.Multi-user bandwidth allocation method based on traffic cognition[J]. Journal on Communications,2013,34(2):109-116.

[7] SONG H,KIM B W,MUKERJEE B.Long-reach optical access networks:a survey of research challenges,demonstrations,and bandwidth assignment mechanisms[J].IEEE Communications Surveys&Tutorials 2010,12(l):112-123.

[8]KRAMER G,MUKHERJEE B,ESAVENTO G.Interleaved polling with adaptive cycle time(IPACT):a dynamic bandwidth distribution scheme in an optical access network[J]. Photon Network Communication,2002,4(1):89-107.

[9] ZHU Y Q,MA M D.IPACT with grant estimation(IPACT-GE)seheme for ethernet passive optical networks[J].Journal of Lightwave Technology,2008,26(14):2055-2063.

[10]YEOUL S,LEE S H,LEE T J,et al.Double-phase polling algorithm based on partitioned onu subgroups for high utilization in EPONs[J].Journal Optical Communication Network,2009,1(5):484-497.

[11]LIM W S,YUN C H,YANG Y M,et al.Burst-polling-based dynamic bandwidth allocation using adaptive minimum guaranteed bandwidth for EPONs[J].Journal Optical Communication Network,2009,1(7):594-599.

[12]汪学舜,余少华,罗婷等.自适应门限的EPON动态带宽分配实现[J].软件学报,2012,23(3):724-734.WANG X S,YU S H,LUO T,et al.Dynamic bandwidth allocation with adaptive threshold in EPON[J].Journal of Software,2012,23(3):724-734.

[13]汪学舜,余少华,戴锦友.新颖的WDMEPON动态带宽调度算法[J].通信学报,2012,33(2):69-75.WANG X S,YU S H,DAI J Y.Novel algorithm for dynamic bandwidth scheduling in WDM EPON[J].Journal on Communications,2012,33(2):69-75.

[14]CALINESCU R,GRUNSKE L,KWIATKOWSKA M,et al.Dynamic QoS management and optimization in service-based systems[J].IEEE Transactions on Software Engineering,2011,37(3):387-409.

[15]ZHAO H,NIU W,QIN Y,et al.Traffic load-based dynamic bandwidth allocation for balancing the packet loss in DiffServ network[A].Computer and Information Science(ICIS),2012 IEEE/ACIS 11th International Conference on[C].IEEE,2012.99-104.

[16]ESMAILPOUR A,NASSER N.Dynamic QoS-based bandwidth allocation framework for broadband wireless networks[J].IEEE Transactions on Vehicular Technology,2011,60(6):2690-2700.