多业务流量预测动态带宽分配方法

梁 根，梁活民

1.广东石油化工学院 理学院，广东 茂名 525000

2.华南理工大学 计算机科学与工程学院，广州 510641

多业务流量预测动态带宽分配方法

梁 根1，梁活民2

1.广东石油化工学院 理学院，广东 茂名 525000

2.华南理工大学 计算机科学与工程学院，广州 510641

1 引言

随着宽带网络通信技术的快速发展，下一代宽带网络将承载话音、数据、多媒体等业务，如何保证多用户、多业务的服务质量（QoS）是宽带网络中一个至关重要的问题[1]。因此，需要一种有效的带宽分配机制，在保证多业务对服务质量不同需求的前提下，尽可能充分地利用带宽资源[2]。

当前实现QoS的主要技术机制主要是基于不同业务对QoS的需求不同采用静态带宽资源分配方法（Static Bandwidth Allocation，SBA）[3]，即在节点设置各类业务的带宽资源分配算法及相应权值参数，网络运行时带宽资源分配算法与QoS参数均不再变化。静态资源的分配一般采用传统的QoS参数方法估计各业务的峰值带宽需求、平均带宽需求，并根据各业务的相关QoS指标要求，经综合平衡计算后固定设置。但SBA方法很难适应业务流特性的变化，因此难以做到在网络拥塞时有效保证优先业务的服务质量，又难以在网络较为空闲时提高网络的吞吐量[4]。

文献[5]等利用适当的业务统计建模来预测未来的业务带宽需要，通过这种预测的方式进行带宽分配。这种方法考虑了在不同用户中利用区分服务的管理来保证 QoS优先级，可以为不同业务提供相应的QoS。文献[6]基于业务分类的动态带宽分配算法（Class of Services Dynamic Bandwidth Allocation，CoSDBA）中，每个业务被划分为高、中、低三个优先级，CoSDBA算法根据这些优先级来分配带宽。具体来讲，带宽首先满足高优先级业务的请求，然后考虑中等优先级的业务，若剩余带宽不能满足所有中等优先级业务的需求，则按照中优先级队列的带宽需求占整个系统中该优先级的所有队列的带宽需求的比例来分配剩余带宽，这种方法也适用于对低优先级业务的带宽分配，但在这种方法中低优先级的队列有可能得不到任何带宽。

传统的动态带宽分配方法存在着带宽分配的多分配与少分配的情况，前者降低带宽利用率，而后者则以侵犯业务的服务质量为代价[7]。大量的研究结果表明：网络业务流量具有自相似的特征，网络流量在较长时间范围内具有长时相关性[8-9]。

因此，本文利用带宽预测技术，对实际的业务流量信息进行了预测，并且根据预测流量的大小对系统的带宽进行动态分配，从而提高系统带宽分配的精度和响应速度。

2 MSTPDBA模型及方法设计

2.1 流量预测及带宽分配模型设计

设有并发的m个业务流同时进入系统，并行的流量控制器分别对每一个业务流作预测，把预测的结果发送到动态带宽分配器中，动态带宽分配器根据流量的预测大小和带宽分配算法动态地对系统的带宽进行分配，具体的模型如图1。

图1 流量预测带宽分配模型

本文研究的多业务流量预测动态带宽分配方法的工作过程分为两个阶段：流量预测阶段和带宽分配阶段。从时刻0开始，以t为控制周期，每个控制周期内分别循环完成流量预测和带宽分配这两个过程。在第t个周期里，并行带宽控制器对输入的业务流在下一个周期的流量进行预测，在该周期内对前一个周期预测的流量进行带宽分配，在下一个周期则对本周期预测的流量进行带宽分配。

2.2 流量预测计算方法

设系统的最小处理时隙为τ，每一次流量预测及带宽分配的控制周期为t，并且有t=k×τ(n=1，2，…，∞)。一般来说，k值越小，流量预测的误差就越小，而当k比较大时，或者当流量变化比较大时，流量预测的误差就会越大。

设系统支持i种业务类型(i=1，2，…，m)，业务的权重系数为φi(i=1，2，…，m)，Bti为业务类型i在周期t的预测流量，周期t前的过去n个周期t0，t1，…，tn的平均实际流量值为：，那么利用预测函数可得业务流i在控制周期t的流量值为：

其中：

2.3 基于流量预测的动态带宽分配方法

带宽分配算法根据可用网络带宽的预测值和当前各链路的情况，对各链路的可用带宽进行动态分配，以优化整体的控制性能。在本文中，基于下一周期各业务的流量预测以及当前系统带宽、各业务的优先级指数等，计算各业务的带宽分配参数。

（1）若预测的所有业务流量小于或者等于系统的总可用带宽，即

在这种情况下，系统有足够大的带宽可以进行分配，因此，各业务流的带宽分配大小为：

由上式可以看出，带宽的分配首先是在保证各链路有足够的可用带宽的基础上，对当前的系统可分配的带宽资源按预测值大小按比例进行分配。这样，权重较低的链路也能获得一定数量的带宽资源，不会给权重高的链路占有大部分带宽资源，导致部分权重低的链路得不到任何资源。利用这种带宽分配策略，在系统负载低的时候也能提高总体利用率。

（2）若预测的所有业务流量大于系统的总可用带宽，即

当预测的所有业务流量大于系统的总可用带宽，系统的总带宽资源有限时，即网络负载很重的时候，部分流量预测值比较低的链路可能长时间得不到或得到很少的带宽资源，导致该链路将在较大程度上受到丢包和长时延的影响，使得传输性能持续恶化。

因此，为了优化系统的整体性能，在这种情况下，首先对系统中的资源按照各业务的权重进行初始化分配，即

设Bfree为空闲带宽，对于所有初始化分配带宽大于或者等于预测带宽的业务，进行如下配置：

然后，将空闲带宽Bfree再重新分配到那些初始化分配带宽小于预测带宽的业务，具体分配的数量为：

3 实验和性能评估

3.1 实验方法、参数和环境

使用NS-2验证本文提出的MSTPDBA方法的有效性。网络中业务流属于不同优先级，其到达速率为随机，所有业务流的数据帧长度均为1 000字节，测试时间长度为100个控制周期。首先通过本文MSTPDBA方法预测业务流加入网络后所能达到的吞吐量，并将预测结果与实际结果相比较。为充分验证本文MSTPDBA方法的有效性，再与静态带宽分配算法（SBA）、基于业务分类的动态带宽分配算法（CoSDBA）进行了仿真比较，具体仿真参数如表1。

表1 仿真参数说明

在仿真中，使用了三种业务流等级，最高优先级的EF流，中等优先级的AF数据流和最低优先级的BE数据流，并且采用两组不同的流量比例的仿真测试场景：在第一组仿真场景中，EF、AF和BE业务流分别各占33.3%；在第二组仿真场景中，EF、AF和BE流的比例分别变为60%、30%、10%。分别对这两组场景下的时延和总带宽利用率进行性能测试。

3.2 MSTPDBA方法预测性能分析

由于流量的突发和负载的变化，监测到的实际流量和预测结果如图2所示。实际流量在15～40之间波动增加，从图2中可知，MSTPDBA方法每个控制周期内均能较好地预测下一个周期的流量。从图3可以看出，其预测误差范围大致在±20%区间之间，但在流量瞬时波动较大的时候，预测误差较大。

图2 实际带宽与预测带宽比较

图3 预测误差百分比

图4 场景1下时延对比

图5 场景2下时延对比

图4和图5分别给出了在两种不同流量占用场景下三种算法的端到端平均包时延。在场景1中，根据图4可以看出，对于BE业务流，CoSDBA显示出最大的平均包时延，而SBA显示出最小平均包时延。这是因为在各种不同优先级的业务流在占用相同比例的情况下，BE业务流流量较大，CoSDBA方法中低优先级的业务流得不到优先处理；对于AF业务流，三种方法的平均包时延相差不大；由于MSTPDBA和CoSDBA引入了业务权重或优先级机制以满足高优先级业务的QoS需求，正如所预料的，对EF业务流来说，MSTPDBA具有最小的平均时延，同时，CoSDBA的平均包时延与MSTPDBA的平均包时延接近，并较优于SBA的平均包时延。

在场景2中，不同的业务流量占用场景对三个算法的时延性能有较明显的影响，从图5可以发现，当EF业务占总流量的比例更多的时候，SBA由于不能给EF业务流保障足够的带宽分配，因此显示出最差的性能。MSTPDBA在该场景负载较轻的情况下比CoSDBA的平均包时延稍好，但当负载超过60%时，由于预测的误差与运算量的增加，MSTPDBA的平均包时延有所增加；在该场景下，三个算法的AF业务流的平均时延相差不大，CoSDBA表现出较好的性能；由于在该场景下，BE业务流只占总流量的10%，SBA分配给BE业务流的带宽有所剩余，因此对于BE业务流，SBA的平均包时延在这三个算法中最小，CoSDBA最大，MSTPDBA次之，但通过对比图4的BE流可以看出，它们之间的差距已经明显缩小。

图6和图7给出了在两种不同流量占用场景下三种算法的系统带宽利用率比较。由图6可以看出，在场景1下，三种算法的系统带宽利用率基本上呈现线性增加关系，除部分系统开销带宽外，由于MSTPDBA能对剩余空闲带宽进行再分配，因此在负载较重的情况下表现出较好的带宽利用率；由于在该场景下各类流量所占的比例相同，SBA的系统带宽利用率基本上也能维持呈现线性增长。

图6 场景1下系统带宽利用率对比

图7 场景2下系统带宽利用率对比

在图7显示的场景2的测试中，由于EF业务流占比例较大，当系统负载超过50%的时候，SBA的EF业务流得不到足够的带宽，数据排队时延加大，系统带宽利用率较其他两种方法增长得慢许多；在该场景下，MSTPDBA仍然能维持较好的线性增长，由于CoSDBA对占用比例较大的EF业务流处理得较有优势，系统带宽利用率与MSTPDBA相差不大。

4 结论和进一步的研究工作

实际的网络带宽控制系统一般在网络带宽受到一定限制且负载可变的动态环境中运行。传统的静态资源调度策略不能适应不可预见的动态环境。因此，开发合适的动态调度策略以适应网络中业务流的变化，优化系统的性能尤为重要。

本文在多业务环境下提出了一种流量预测动态带宽分配方法，该方法基于插值预测函数动态预测方法对系统的业务流量进行在线预测，并通过带宽管理器对预测到流量进行可用带宽资源动态分配，提高了系统的整体性能，同时也优化了带宽资源的利用。仿真结果表明本文提出方法具有较好的性能和适应性。

如何结合具体业务的服务质量要求（吞吐量、延迟、丢包率等）以及网络的业务流量配置协议参数，在满足服务质量要求的同时达到最佳的网络性能，是下一步的研究目标。

[1]林闯，李寅，万剑雄.计算机网络服务质量优化方法研究综述[J].计算机学报，2011，34（1）：1-14.

[2]Cruz-Perez F A,Ortigoza-Guerrero L.Flexible resource allocation strategies for class-based QoS provisioning in mobile networks[J].IEEE Transactions on Vehicular Technology，2004，53（3）：805-819.

[3]宾雪莲，杨玉海，金士尧.一种有限优先级的静态优先级分配算法[J].软件学报，2004，15（6）：815-822.

[4]Yeoul S，Lee S，Lee Tae-Jin，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.

[5]Chiti F，Fantacci R，Tarchi D，et al.QoS provisioning in GEO satellite with onboard processing using sredictor algorithms[J]. IEEE Wireless Communications Magazine，2005，12（5）：21-27.

[6]Choi S I，Huh J D.Dynamic bandwidth allocation algorithm for multimedia services over Ethernet PONs[J].Journal of Electronics and Telecommunications Research Institute，2002，24（6）：465−468.

[7]张晋豫，刘犁.基于效用EPON分布式动态带宽分配实现机制[J].软件学报，2008，19（7）：1693-1706.

[8]姜明，吴春明，张旻，等.网络流量预测中的时间序列模型比较研究[J].电子学报，2009，37（11）：2354-2358.

[9]聂得欣，袁小坊，王东，等.链路层分类包的网络流量自相似性研究[J].计算机工程与应用，2009，45（5）：129-131.

LIANG Gen1,LIANG Huomin2

1.College of Science,Guangdong University of Petrochemical Technology,Maoming,Guangdong 525000,China
2.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510641,China

Static bandwidth resource allocation or class of services dynamic bandwidth allocation is difficult to adapt to the characteristics of service flow,and unable to ensure the QoS of all levels service.The model of traffic prediction and bandwidth allocation is designed.The method of traffic prediction and Multi-Service Traffic Prediction Dynamic Bandwidth Allocation（MSTPDBA）are proposed.MSTPDBA can reallocate the available bandwidth by the size of traffic prediction.MSTPDBA which can control the services delay and improve utilization ratio of system bandwidth is proven to be effective by simulated experiments.

Quality of Service（Qos）;class of service;interpolation prediction;available bandwidth;dynamic allocation

静态带宽资源分配方法或基于业务分类的动态带宽分配方法等很难适应业务流特性，无法保证各级业务的服务质量。设计了流量预测及带宽分配模型，给出了流量预测计算方法，提出多业务流量预测动态带宽分配方法（MSTPDBA），该方法基于业务预测流量的大小进行可用带宽的重新分配。仿真实验证明了MSTPDBA的有效性，能控制不同业务的时延，并提高了系统带宽资源的利用率。

服务质量；业务类型；插值预测；可用带宽；动态分配

A

TP393

10.3778/j.issn.1002-8331.1202-0137

LIANG Gen,LIANG Huomin.Dynamic bandwidth allocation method of multi-service based on traffic prediction.Computer Engineering and Applications,2013,49（18）：82-85.

广东省自然科学基金（No.10151601501000015）；广东高校优秀青年创新人才培育项目（No.LYM08080）。

梁根（1979—），男，副教授，主要研究方向为网络协议及算法；梁活民（1980—），男，博士，讲师，主要研究方向为网络并行分布式处理。E-mail：L_Gen@126.com

2012-02-08

2012-04-09

1002-8331（2013）18-0082-04

CNKI出版日期：2012-06-15 http://www.cnki.net/kcms/detail/11.2127.TP.20120615.1727.049.html