摘 要： 在传统加权轮询调度算法和严格优先级调度算法的基础上，加入令牌桶机制，实现了一种改进算法。在多业务并存网络中，该算法能够对不同等级的业务实现不同的QoS（服务质量），同时，在业务流量发生变化时，能够动态调整相应业务的带宽，且不会对高优先级队列造成影响。仿真实验表明，该算法可以在一定范围内适应网络的变化，有效缓解了突发流量所造成的报文丢包问题，大大提高了网络性能。
关键词：多业务网络；QoS；动态调整；丢包
0 引言
随着科技的飞速发展，网络中的业务量也呈爆炸式的增长，而且不同的业务在时延、丢包等性能方面也有着不同程度的要求。但网络资源总是有限的，在网络总带宽固定的情况下，如果某类业务占用的带宽越多，那么其他业务能使用的带宽就越少，可能会影响其他业务的使用。基于此，专家们提出了QoS的概念，针对各种应用的不同需求，来对网络资源进行合理的规划和分配，从而使网络资源得到高效利用。
队列调度机制作为QoS技术的核心机制之一，一直以来就是研究的热点。所谓队列调度就是在网络中传送业务时，如何从多个数据包队列中选择一个队列转发[1]。一个好的队列调度算法可以大大提高网络的性能，这在带宽资源扩展速度远远落后于网络中消息增加速度的今天，重要性不言而喻。
目前，已有很多种队列调度算法被提出，如严格优先级队列调度（Strict Priority，SP）算法、加权轮询调度（Weighted Round Robin，WRR）算法、加权差额轮询调度（Weighted Deficit Round Robin，WDRR）算法、加权公平调度（Weighted Fair Queuing，WFQ）算法等[2-4]，但面对千变万化的网络环境，这些算法总是存在着这样或那样的缺陷。本文在研究了传统的各种队列调度算法之后，在WRR算法的基础上加以改进，大大提高了算法的性能，且能在一定范围内适应网络中流量的变化。
1 几种典型的队列调度算法
1.1 SP算法
SP算法是针对关键业务应用设计的。SP算法严格按照优先级从高到低的顺序调度队列，当高优先级报文中存在报文时，低优先级队列得不到调度的机会。这就导致SP算法虽然可以保证高优先级队列的服务质量（Quality of Service，QoS），但是当高优先级队列中始终有报文存在时，低优先级队列中的报文得不到调度，造成低优先级队列“饿死”现象。
1.2 WRR算法
WRR算法解决了SP算法中低优先级队列“饿死”的问题。在WRR调度算法中根据队列的权值来决定转发报文的数量。首先设置一个变量weight记录队列的权值，在进行队列调度时，首先判断weight值是否大于0以及队列是否非空，若weigdt大于0且队列非空，则从该队列中转发一个分组，并将weight减1，继续进行条件判断，直到weight值等于0或队列为空，转到下一个队列开始调度，当所有队列都轮询一遍后，将每个队列的weight值恢复为初始值，然后从第一个队列开始，再次遍历，不停地重复以上步骤。
1.3 WDRR算法
WRR调度虽然解决了SP调度中的低优先级队列“饿死”问题，但由于算法以分组为单位进行队列调度，当队列中分组长度不同时，就会导致调度的公平性问题。由此，提出了以字节为单位来进行调度的WDRR调度。WDRR算法中首先要设置一个粒度值表示每个权值所代表的字节数，并设置一个变量DC[i]表示第i个队列在一次轮询中可以调度的字节数，初始化为0。每轮调度队列之前计算队列权值与粒度的乘积加上DC[i]的初值，作为本轮调度可以转发的最大字节数，队列调度过程如下：
（1）DC[i]=DC[i]+粒度*权值；
（2）若队列为空，则只需将DC[i]置0，转到下一队列开始调度；
（3）若队列不为空，则比较DC[i]与接下来要调度的分组长度length的大小，若DC[i]>=length，则转发该分组，更新DC[i]的值（DC[i]=DC[i]-length），并转向（2），否则转到下一个队列继续调度；
（4）若一轮调度完成，则转到第一个队列，转到（2），继续调度。
DWRR调度虽然解决了WRR调度中的公平性问题，但仍然存在如下一系列的缺点[5-6]：
（1）不能体现高优先级队列的绝对优先级地位。
（2）分组时延得不到保证，当某一分组错过了本次调度时，它将不得不等待一个轮询周期的时间，尤其是当这种情况出现在高优先级队列时，会造成严重后果。
（3）各队列分配到的权值是固定的，当网络情况发生变化时，不能很好地适应，例如，高优先级报文突然增多，但由于分配的带宽已经固定了，多余的报文将得不到转发，只能丢弃。
2 改进算法描述
本文针对以上算法存在的缺点，提出一种改进的队列调度算法，经验证，改进算法很好地解决了以上问题。其基本流程如下：
（1）报文入普通8队列。报文根据dscp值映射出本地优先级，根据本地优先级进入相应的8队列。
（2）对队列进行分组。将QoS需求近似的队列分在同一组，每一组以组中优先级最低队列的优先级作为本组中所有队列的优先级（避免优先级重复）。为了保证高优先级队列的绝对优先地位，不同组之间的队列按照SP算法进行调度，保证高优先级队列优先转发。同一组内的各队列之间进行DWRR调度，保证QoS需求近似队列的相对公平性。
（3）从8队列（QueueLoop[8]）映射到64队列（FlowLoop[64]）。本设计提供一套模板，该模板包含64个队列，分8种优先级，每个队列都设定好了对应优先级值（priority）。首先从QueueLoop[1]开始，以此与FlowLoop进行匹配，若优先级相同且FlowLoop还未被其他队列占用，则匹配成功，进行下一条QueueLoop的匹配工作，否则继续匹配，直到匹配成功为止，流程如图1。
（4）队列调度。如上所述，分组内进行DWRR调度，分组间进行SP调度。为了使低优先级队列不被“饿死”，本算法引入了令牌桶机制对队列和整个分组进行限速，对每个队列的超带宽流量进行降级处理，将优先级降为最低，并加入优先级最低的分组与组中原有队列按权值共享剩余带宽。这样当队列出现突发流量时，可以有效减小突发报文的丢包率，并且在低优先级队列空闲时可以自动占用剩余带宽，避免浪费，算法调度的框架如图2所示。
3 实验及结果分析
本文在实体路由器上进行测试，实验组网如图3所示。
用打流仪构建8条优先级各不相同的流，其中6、7队列为高优先级队列，要求快速转发（EF），2~5队列为中优先级队列，要求保障转发（AF），0、1队列为低优先级队列，要求尽力而为地转发（BE）[7]。发送端g2/1/5流量的发送速率除5队列外，都固定为100 MB/s（每个优先级报文为100 MB/s），路由器出端口g2/1/6限速为700 MB/s。在上图构建的通路中，分别执行WRR算法和本文改进的算法，统计在不同算法下各队列的调度情况。
首先验证各算法对网络的适应情况，将队列5的报文发送速率逐步从100 MB/s增加到200 MB/s，比较各队列占用带宽的情况。对WRR算法，设置8队列的权值分别为3、3、2、2、1、1、1、1。对本文改进的算法，在以上所设基础上，将8条流量分为三组，第一组包含队列0和队列1，第二组为队列2到5，剩下的队列分到第三组，同时对第二组限速350 MB/s，结果如图4所示。可见，当流量增加时，WRR算法对网络变化缺乏调控能力，而改善算法对超带宽的流量做了降级处理，在第一组中得以再次调度，等于增加了权值，分配到了更多带宽，且不会对比其优先级高的队列造成影响，也不会造成低优先级队列“饿死”，改进的算法对流量调控起到了一定的作用。
接下来验证队列的丢包情况，在拥塞的网络环境中必然会有丢包。既然丢包是必然的，就要尽量保证优先级高的队列少丢包。以下比较三种算法的丢包情况。首先构建这样的网络环境，在上文的条件基础上将队列5报文到达速率不停地增加，观察该队列的丢包情况。如图5所示。改进算法的丢包率远远小于WRR算法的丢包率，SP算法丢包率虽然低，但是它是以更多低优先级队列“饿死”为代价的。
4 结论
本文在现有SP算法和WRR算法的基础上作出改进，主要是为了实现不同业务的不同服务质量要求，同时提高对网络变化的自适应性。仿真实验证明，当某分组到达队列的速率不断加快时，通过对超带宽流量降级，使其更低优先级分组得到再次调度的机会，相当于增加了该队列的权值，实现了带宽资源的动态分配。同时，算法还大大减小了网络丢包率。
参考文献
[1] 林闯，单志广，任丰原.计算机网络的服务质量（QoS）[M].北京：清华大学出版社，2004.
[2] 董民，沈庆国.轮询类分组调度算法的研究[J].系统仿真学报，2010，22（11）：2593-2596.
[3] 熊李艳，张胜辉.WRR算法在多类别实时数据流中的优化[J].计算机科学与工程，2012，34（7）：35-38.
[4] NIKOLOVA D， BLONDIA C. Bonded deficit robin scheduling for multi-channel networks[J]. Computer Networks，2011，55（15），3503-3516.
[5] Li Miaoyan，Song Bo. Design and implementation of a new queue scheduling scheme in DiffServ networks[C]. The 2nd IEEE International Conference on Advanced Computer ConTrol， 2010：117-122.
[6] ZHANG Y， HARRISON P G. Performance of a priority-weighted round robin mechanism for differentiated service networks[C]. International Conference on Computer Communications and Networks， 2007：1198-1203.
[7] 刘威，杨宗凯.多服务级别带宽公平分配算法的研究[J].计算机科学，2005，32（1）：37-40.