0 引言

随着用户对网络服务质量QoS要求日益多样，越来越多开发者开始重视QoS技术的研究，要使网络应用的服务质量充分满足用户需求，采用路由器队列调度算法是很好的一种方式.队列调度算法主要实现各信息流之间带宽分配管理，即按照一定的标准从所有等待服务的队列中实现分组选择，并输出到链路上去. ^[1]目前，比较常用的调度算法有：先进先出队列算法FIFO、优先队列算法PQ、公平队列算法FQ、基于加权公平队列WFQ算法和加权轮询算法WRR^[2]等.

先进先出队列算法FIFO^[3]是最基础的队列调度算法，体现报文派发公平性，先进入队列报文最先发送.优先队列算法PQ会将进入队列的报文进行优先级分类，优先级高的报文先进行转发，当优先级相同时即按照FIFO算法原则进行转发.GPS模型^[4]可以按照用户预约速率对不同业务进行理想的公平排队，分组公平排队(PFQ)是GPS模型的近似算法，通过引入虚拟事件与虚拟时间因子，假设后到达的分组没有及时到达服务节点，对已经排队等候的分组进行选择性服务，以使其尽快离开积压队列，WFQ调度算法^[5]即是最典型的算法之一.

国内学者主要通过WFQ调度算法对链路带宽的分配问题进行改进型研究，典型算法如FWFQ算法，其通过引入权值系数达到延迟和抖动等因素的改善，但由于该算法中权值为固定值，无法实现动态调整. ^[6]基于优先级带宽的WFQ算法存在无法增大业务流的处理能力的缺点，为此笔者提出了基于优先级带宽保证的权值的SRWFQ改进算法.

1 WFQ算法分析 1.1 算法工作原理

加权公平调度算法WFQ是通过计算分组的最小虚拟完成时间来近似得到GPS的调度算法. ^[3]算法引入了随时间变化的虚拟时间函数，假设当前一个数据报文p_j到达时刻t_j=0，在时间段(t_j-1, t_j)内，需要将积排队等待中的数据发送出去，并保持队列的完整性，B_j为所有队列集合.此处定义虚拟时间函数V_j.虚拟时间初值假定为0.

函数关系^[7]如式(1) 所示

$\left\{ {\begin{array}{*{20}{l}} {V\left( 0 \right) = 0}\\ {V\left( {{t_{j - 1}} + \tau } \right) = V\left( {{t_{j - 1}}} \right) + \frac{\tau }{{\sum\limits_{i \in {B_j}} {{\phi _i}} }}r}\\ {\tau \le {t_j} - {t_{j - 1}},j = 1,2,3, \cdots ,n} \end{array}} \right.$

(1)

假设业务p_i^k是第i个连接中第k个分组到达队列的业务，业务的到达时间、服务开始时间、服务结束时间和分组长度分别定义为a_i^k，S_i^k，F_i^k，L_i^k，r_i定义为连续的预约服务率，业务量化存在如下关系：

$\left\{ {\begin{array}{*{20}{l}} {S_i^k = \max \left( {F_i^{k - 1},V\left( {a_i^k} \right)} \right)}\\ {F_i^k = S_i^k + \frac{{L_i^k}}{{{r_i}}}} \end{array}} \right.$

(2)

由文献[3]中(2) 式可得，分组的虚拟结束时间与业务流预约的服务速率成反比，故服务等待的时间越久，则队列延迟也会加大.

1.2 算法存在的缺陷

由于WFQ对业务流都有一个固定带宽，不支持实时业务流快速转发且和其他业务流同时分享带宽，不能得到优先的转发调度延时敏感的业务流.分组虚拟结束时间和分配的带宽均保持不变，致使后面业务等待时间更长.

2 基于权值改进和带宽优先的WFQ改进算法分析

针对WFQ算法的不足，提出了一种基于权值改进和带宽优先相结合的算法.相比较于WFQ算法所做改进之处是SRWFQ改进算法可支持实时业务流，从而使网络性能更加良好.改进算法流程图如图 1所示.

业务流分组入队后，首先通过优先级判别器和CAR模块，判断业务流是否为实时性的业务流，按照不同的判别情况下给定的权值获得最优的带宽服务.

2.1 权值改进WFQ策略

权值改进策略是在分类器和调度器之间增加速率控制和FCFS队列调度模块.首先对进入调度器的业务流通过CAR进行流量控制，缓和突发性业务流，然后通过改变实时业务的权值，使业务流输出时间变小，提高业务流服务率，达到用户满意程度.权值改进策略结构^[8]如图 2所示.

2.2 优先级带宽保证策略

当进入分类器的区分开的实时或非实时业务流完成带宽分配后，可以通过网络带宽和预约业务流总带宽判断突发情况，该算法规定当调度器后的链路带宽小于预期总带宽时，队列排队中的业务数据流靠前部分优先进行带宽分配，剩余未分配到带宽的业务流采用加权方法分配到非实时业务流中进行处理.带宽保证数学表达^[8]如下所示：

${g_i} = \left\{ {\begin{array}{*{20}{l}} {{\sigma _i},i \in R}\\ {\left( {r - \sum\limits_{j \in R} {{\sigma _j}} } \right)\frac{{{\phi _i}}}{{\sum\limits_{k \notin R} {{\phi _k}} }},i \notin R} \end{array}} \right.$

定义r为网络带宽和σ_i为业务流报文预约服务带宽，该调整策略主要是通过CAR模块实现服务带宽准确赋予，从而降低业务突发性.宽带保证的权值调整策略可以保证实时业务流拥塞时的带宽需求，缩短时延.

3 仿真实验与结果分析 3.1 仿真拓扑结构

仿真实验采用基于Linux开发环境下的网络仿真软件NS-2网络仿真平台作为仿真工具，编写好SRWFQ改进算法程序并编译到NS-2平台中，通过运行Otc1脚本文件得到预期数据文件，再利用Gnuplot和GAWK等数据分析软件分析预期数据文件，实验仿真拓扑^[9]结构如图 3所示.

数据源S1、S2、S3对应发送音频数据、视频数据和FTP普通数据业务流.R和E分别为路由节点和终端接收节点.数据源S1、S2、S3端在UDP协议下发送数据业务，在1.2Mbit/s、1.5 Mbit/s和3.5 Mbit/s的传输速率下传送数据流.^[10]

该仿真实验将3种数据业务流的数据流长度设为512、840、1024Byte，其中最大长度为1024 Byte.路由节点R至终端接收节点E的链路带宽分别设置为3.0 Mbit/s(带宽不足)和5.0 Mbit/s(带宽充足)，在两种带宽模式下突发速率分别为64 kbit/s、80 kbit/s.路由节点R分别使用WFQ、SRWFQ算法，仿真实验为30秒时间，在第9秒时突发.

3.2 实验数据分析

采用仿真实验以语音业务流为例，在相同条件下对比分析两种算法的延迟、抖动和丢包率.为比较分析突发速率在不同带宽下业务流延迟和抖动的规律，仿真实验针对两种情形展开，分别是带宽充足和带宽不足.^[11]

图 4为突发速率为60 kbit/s时两种带宽下音频数据流的延迟比较.由图 4可见，数据流的突发对WFQ算法比SRWFQ算法的影响大.两种算法的延迟时间在9秒时开始变大，但WFQ先达到稳态，SRWFQ会经过1至2秒的时间调节进入稳态，但SRWFQ算法时间延迟要明显优于WFQ算法.

图 5为突发速率为80 kbit/s时两种带宽下音频数据流的延迟比较.两种算法下的延迟在9秒后显著增大，经过20秒左右进入稳态.由图 5可见，WFQ算法的延迟略大于SRWFQ算法，但它们从突发到稳态的时间均大于突发速率为60 kbit/s的情况.

图 6显示了链路带宽为5.0、3.0 Mbit/s时WFQ、SRWFQ算法的丢包率，可知不同带宽下WFQ算法的丢包率比不上SRWFQ算法.

图 7为链路带宽为5.0 Mbit/s和3.0 Mbit/s时，WFQ算法和SRWFQ算法的吞吐量对比图.改进的SRWFQ算法语音业务吞吐量分别为450 Kbps和200 Kbps，而WFQ算法的业务吞吐量明显低于改进SRWFQ算法.^[12]

从实验中得出，SRWFQ算法在数据流出现突发的情况下性能优于WFQ算法.因为数据流突发时SRWFQ算法采取了相应的调整策略，使网络畅通，根据实时业务吞吐量对比明显看出在队列拥堵时，改进算法的吞吐量大于WFQ算法，保证了实时业务流的带宽.当链路带宽为5.0 Mbit/s和3.0 Mbit/s时，突发速率为60 kbit/s的算法性能效果优越；当突发速率为80 kbit/s时，两种算法在时间延迟上无差别.^[13]

4 结语

SRWFQ通过业务流实时分类对WFQ算法无法区分会话优先级的情况进行了优化.SRWFQ调度算法可以在业务流报文突发的情况下，保证语音业务流的QoS需求，又可通过提高权值来获得高服务带宽，使其在延时、网络吞吐量和丢包率等服务需求上大为改进.