学步园

文/常慧锋

【摘要】本文概述了常用队列调度算法的实现机制，并在此基础上对比了基于理想流模型的WFQ队列算法与其他队列调度算法的公平性能。

【关键字】服务质量 队列调度 通用处理器共享 加权公平队列

1. 引言

队列调度算法是实现网络QoS(Quality of Service，服务质量)控制的核心机制之一，是网络资源管理的重要内容，通过控制不同类型的分组对链路带宽的使用，使不同的数据流得到不同等级的服务。

通常调度算法的工作模式可以分为两种：工作保留模式(work-conserving)和非工作保留模式(non-work-conserving)。如果队列中有数据包等待发送服务器就工作的调度算法称为工作保留调度算法；如果队列中有数据包等待发送但服务器仍然处于空闲状态的调度算法称为非工作保留调度算法，例如，即使服务器处于空闲状态同时队列中有数据包等待发送，但是为了等待下一个高优先级的数据包服务器也会推迟当前数据包的传输，这种调度算法就属于非工作保留调度算法。当数据包的传输时间很短时，非工作保留调度算法几乎是不公平的。

调度算法的另一种分类方法是根据调度算法的内部结构来划分的，主要有两种：基于优先级分类的调度算法和基于帧结构的调度算法。在基于优先级的调度算法中有一个称为虚拟时间(virtual time)的全局变量。调度算法根据该变量为每个数据包计算一个时间戳，然后根据时间戳对数据包排序和调度。虚拟时钟，加权公平队列都属于这种结构。基于优先级的调度算法的实现复杂度取决于两个因素：更新优先级列表算法和选择最高优先级数据包算法的复杂度(至少是，其中是共享输出链路的队列数)和计算时间戳算法的复杂度(这主要取决于所采用的调度算法，加权公平队列(WFQ)的时间戳的计算复杂度为，虚拟时钟的计算复杂度只为O(1))。

在基于帧结构的调度算法中，时间被分为固定长度或可变长度的帧。每个数据流所能使用的带宽资源就是每一帧中所允许传输业务量的最大值。存储转发队列是帧长度固定的基于帧结构的调度算法，在这种结构中，如果一帧中数据流的业务量小于预留带宽，服务器就会空闲。加权循环队列，差额循环队列允许帧长度可变，同时，如果一个数据流的业务量小于预留带宽时，下一个数据流就可以提前被调度。基于帧结构的调度算法最大的优点是实现简单，成本低，最大的缺点是缺乏灵活性和扩展性。

2. 典型的调度算法简介

2.1先进先出队列(FIFO)

FIFO队列是最简单的基于优先级的调度算法。在FIFO队列中数据包的时间戳就是数据包的到达时间。FIFO队列提供了基本的存储转发功能，也是目前因特网中使用最广泛的一种方式，它采用默认的排队方法，不需要配置。其优点是实现简单，成本低，缺点是不能提供QoS功能和隔离技术，缺乏公平性，易于受到非法用户的攻击。

2.2严格优先级调度算法(PQ)

严格优先级调度算法维护一个优先级递减的队列系列并且只有当更高优先级的所有队列为空时才服务低优先级的队列(如图1所示)。假设队列1比队列2具有更高的优先权，队列2比队列3具有更高的优先权等等。只要链路能够传输分组，队列1尽可能快地被服务。只有当队列1为空，调度器才考虑队列2。当队列2有分组等待传输且队列1为空时，队列2以链路速率接受类似地服务。当队列1和队列2为空时，队列3以链路速率接收服务等等。

然而该调度机制会使低优先级队列处于饥饿状态。例如，如果影射到队列1的数据流在一段时间内以100%的输出链路速率到达，调度器将从不为队列2、3、4服务。避免队列饥饿需要上游路由器精心规定数据流的业务特性以确保映射到队列1的业务类不超出输出链路容量的一定比例，这样可以使队列1常常为空，允许调度器为低优先级队列服务。

严格优先级调度算法对低时延业务非常有用。假定数据流X在每一个节点都被映射到最高优先级队列，那么当数据流X的分组到达时，如果调度器是空闲的，则分组被立即服务。

图1 严格优先权调度器 图2 通用处理器共享

2.3通用处理器共享算法(GPS)和加权公平队列算法(WFQ)

u 通用处理器共享(Generalized Processor Sharing)

GPS算法是一种理想的调度算法(如图2所示)，是根据流模型定义的，也就是假设数据包是可以被无限细分的。在GPS算法中，假设服务器的处理速率恒为。在时刻，如果数据流的数据包在队列中等待处理，就认为数据流在时刻处于激活状态。假设有正整数代表各数据流的权重，是时间间隔中服务器为数据流提供的服务，那么对于时间间隔内任何暂存在服务器中的数据流获得的服务，GPS算法定义为。

假设r为服务器的处理速率，将数据流累加可得。根据轮换对称性，任意数据流的保证速率(最小服务速率)为。

GPS算法具有如下特性：

l 假设是数据流的平均速率，只要，就可以保证数据流独立于其它数据流的吞吐率。还可以保证数据流的瞬时数据以大于等于的速率被处理。

l 由于数据流i在任意时刻获得的服务独立于其他数据流，数据流的时延抖动是自己队列长度和达到时间的函数，独立于其它连接的队列长度和到达时间。其它调度算法如FIFO和PQ没有这种性质。

l 通过改变我们可以以不同的方式处理不同的数据流。例如，当所有的都相同时，GPS就退化为均衡处理器共享(Uniform
Processor Sharing)。另外只要数据流的平均速率之和小于，不论怎么分配，系统总是稳定的。

l 通过增加就可以减少数据包经历的时延，虽然这种方式是以牺牲其它数据包的时延作为代价的，但是当激活数据流稳定时，这种代价并不是很大。所以GPS算法和速率整形器联合使用时可以得到性能优良的调度器，为数据流提供最坏情况下的时延和时延抖动保证。

u 加权公平队列算法(WFQ)

GPS算法最大的缺点是不能处理长度可变的数据包。WFQ算法是GPS算法的近似。假设是数据包在GPS算法中的离开时间，那么WFQ算法就是一个模拟GPS算法并按升序调度数据包的工作保留算法，也就是说WFQ算法总是选择值最小的数据包进行调度。下面介绍WFQ算法的虚拟时间实现。

假设时间是事件的发生时间(同时发生的事件可以任意排序)，服务器的处理速率为。在服务器中，第一个发生事件的时间记为＝0。可以看出在时间间隔(，)内处于激活状态的数据流是固定的，我们将它记为集合。当服务器空闲时，虚拟时间记为0，那么WFQ的计算如下：

的变化率为，每个暂存的数据流接收到的处理速度为。假设数据流的第个数据包的到达时间为，长度为，和分别表示这个数据包的开始虚拟时间和结束虚拟时间，，那么，我们可以得到：

从实现的角度来看，WFQ算法的虚拟时间实现有两个重要优点：

l 数据包的完成时间决定于数据包的到达时间和上一个数据包的完成时间；

l 数据包根据完成时间升序被处理；

WFQ使用虚拟时间存在的缺点：跟踪集合需要花费很大的开销。

2.4虚拟时钟算法(Virtual Clock)

虚拟时钟算法根据数据包的到达时间和用户定义的保留速率计算数据包的时间戳。假设是数据流的第个数据包的时间戳，是数据流的保留速率，是长度为的数据包的实际到达时间，那么数据包的时间戳定义如下：

← 

如果数据包比预期的到达时间晚，那么经过最大延迟后数据包被传输；如果数据包比预期的到达时间早，在最坏情况下，数据包被传输的时间为。最坏情况下的服务质量不受其它连接行为的影响。

2.5存储转发队列(Stop-and-Go)

存储转发队列将输入和输出链路的时间轴分为固定长度的时隙“帧”。在两帧之间到达的数据包只能在下一帧中被传输，在同一帧中的数据包可以以任何次序传输，因此每个数据包都被引入一个固定的时延。如果数据包的最大到达速率小于帧中保留的时间片，那么这种算法能确保有限的时延和时延抖动。存储转发队列有两个问题：因为算法是非工作保留的，所以没有静态统计复用收益；时延与帧分配的颗粒度有关，选择小的帧长度可以获得小的，但是，为了得到好的带宽利用率应该选择大一些的帧长度。

2.6循环队列(round-robin)

循环队列通过循环服务避免局部队列饥饿。调度器总是顺序地移到下一个有分组要发送的队列(空队列被跳过)。如果每个队列都有分组等待发送，调度顺序和队列顺序匹配；如果一些队列为空，则其它队列被频繁地服务。在极端情况下，如果其它队列都为空，单个队列就可以使用全部链路带宽。当分组进入一个空队列时，该队列在下一个循环中被服务，这样就可以避免队列“饥饿”。

循环调度的缺点是分组时延难于改进，它不可能为低时延业务分配专用队列。每个队列的服务间隔完全依赖于那段时间内其他队列中有多少分组等待发送以及这些分组的长度，这些变量难以准确预测，所以RR调度容易产生时延抖动。调度器可以通过改变服务顺序(例如采用顺序1，2，3，2，4，2，1，2，…)更频繁地调度某些队列以给这些队列更频繁的传送机会，然而分组大小的随机分布仍然会造成时延抖动问题。

2.7差额循环队列(DRR)和加权循环队列(WRR)

DRR算法是RR算法的扩展。DRR算法为每个队列分配一个常量Q_N(以权重为比例的时间片)和一个变量D_N(差额)。Q_N反应了该队列可以发送的长期平均字节数。D_N的初始值为零且当队列为空时复位为0。当DRR算法服务一个新队列时，调度器复位计数器B_sent(表示该循环已经从队列中发送的字节数)。当下面两个条件满足时，DRR算法从队列中发送分组：

l 队列中有分组等待发送；

l (Q_N+D_N)大于等于(B_sent+队列中下一个分组的长度)。

否则，该队列的差额D_N+1被置为Q_N+D_N－B_sent，调度器按顺序移到下一个队列。Q_N+D_N表示在服务时间间隔内队列能够发送的最大字节数，在一定程度上D_N可以平滑数据流的突发。队列通过Q_N可以获得长期的相对带宽分配。如果激活队列的数目小于N，则激活队列可以根据Q_N值共享未用的输出链路带宽。

WRR算法非常类似于DRR算法。WRR算法采用类似的时间片和差额的概念，但是算法稍有不同。在WRR中，当队列发送(B_sent)的字节数超过队列允许的限制时(仍为Q_N+D_N)，才对下一个队列进行服务。因此，差额是一个负数值(超出Q_N+D_N的数量)且被当作下一个循环该队列发送的字节数的减少量。

3. WFQ算法与其他调度算法的比较

在DRR算法中，每个队列都有一个权值。服务器按照预先规定的顺序以速率轮询每个队列。如果遇到一个空队列，服务器立即移到下一个队列。如果队列错过了它的传输时序就只能等到下一个属于它的时序才能传输。如果每个队列都在使用，那么该队列的数据包要等到所有的队列都处理完之后才能被处理。WFQ不受这种影响，而且比DRR更适合于处理变长数据包。

图3 虚拟时钟算法(VC)的局部不公平性

虚拟时钟算法(VC)可以为数据流提供带宽和平均时延保证，但是，如果当系统处于轻负荷状态时，某个数据流发送了大量的突发分组，那么当其他数据流被激活以后，这个数据流会受到惩罚(称为局部不公平性，如图3所示)，WFQ算法不会产生局部不公平性，这样数据流就可以充分利用网络轻载时的系统资源。

Stop-and-Go队列采用基于全网范围的时隙划分结构，有两个优点：可以提供好的时延抖动控制和易于实现。但是Stop-and-Go 队列没有WFQ调度算法灵活，而且它属于非工作保留调度算法，无法充分利用服务器的资源，而WFQ算法属于工作保留调度算法，所以WFQ算法能够比Stop-and-Go 队列提供好的多的平均时延控制。

4. 结束语

为了平衡影响调度算法设计的各种因素，获得比较好的性价比，调度算法的设计必须根据每类业务的特点选择不同的算法，但是任何调度算法都必须具有以下基本特征：

l 调度算法必须能够隔离不同数据流之间的相互影响，也就是说，即使是在有恶意数据流存在的情况下，调度算法也能够提供最基本的QoS保证；

l 调度算法必须在不过分影响网络资源利用率的前提下，为单个数据流提供端到端时延保证。同时，调度算法还应该具有能够通过只控制保留带宽资源来控制数据流的时延上下限的能力。

l 调度算法必须能够有效地利用共享链路带宽，这意味着调度算法必须充分利用数据流的统计复用特性，有效地处理突发信源；

l 共享链路带宽必须在队列中加权公平分配，不公平的调度算法在短时间间隔内可能会为两个具有相同保留带宽的数据流提供差别很大的服务速率；

l 实现的简单性；

l 可扩展性：调度算法必须适用于巨大的数据流和变化范围很大的链路速率；

网络的发展趋势是业务多样化，在实际网络中，彼此有分层关系的业务流常常共享链路，这时单一的调度算法无法满足链路带宽共享的需求，需要考虑使用综合结构的调度算法。也就是说，在追求简单性和易实现性的同时，考虑算法的综合性能。