基于速率的分组调度算法模型的研究

李志华

[摘 要] 分组调度算法是为网络提供服务质量保证的一项重要措施。本文提出了一种具有良好通用性的分组调度算法模型，该模型为实现各种基于速率的调度算法提供基本框架，模块化的设计方式使得算法的实现简便易行。

[关键词] 分组调度；服务质量；速率；算法；模型

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2014 . 05. 023

[中图分类号] TP301.6 [文献标识码] A [文章编号] 1673 - 0194（2014）05- 0038- 03

0 引 言

随着网络的飞速发展，其承载的业务逐渐向多媒体方向发展。视频点播、远程会议等实时性业务需要网络为用户提供QoS（Quality of Service）保证。分组调度算法克服了传统网络无法提供QoS保证的缺点，其中基于速率的分组调度算法由于可以为用户提供时延保证和良好的公平性，已成为近年来人们研究的重点。

基于速率的分组调度算法主要包括：GPS（Generalized Processor Sharing）、VC（Virtual Clock）、SFQ（Start-time Fairness Queuing）、WFQ（Weighted Fair Queuing）、WF2Q（Worst-case Weighted Fair Queuing）和SCFQ（Self-Clocked Fair Queuing）等。本文总结以上算法的公共特征提出了一种分组调度算法模型。该模型具有很好的通用性，可以作为载体实现各种基于速率的调度算法。同时，模块化的设计方式为算法的实现提供了统一的框架，使得算法实现简便易行。

本文首先介绍了几种经典调度算法的原理，在此基础上提出了一种算法模型并给出了模型的模块化实现方法，最后以模型为基础实现了WFQ和VC两种算法。

1 算法简介

GPS和Virtual Clock是两种具有代表性的基于速率的分组调度算法。经过严格数学证明的GPS算法为许多后续算法提供了理论依据。

GPS定义为：

■≥■ （j=1，2，…，n）（1）

对每个连接i均成立。其中Si（t1，t2）表示连接i在[t1，t2]内获得的服务量，？准i是和连接i相对应的非负实数[1]。

GPS能够同时调度n个连接的数据并为每个连接提供一个最小的服务速率gi=r·？准i /■？准i。它可以为每个连接提供严格的端到端时延保证和绝对的公平性，但它是一种理想的算法（同时为n个连接提供服务且调度的数据无限可分）。实际中，调度器在某一时刻只能为一个连接服务且数据包作为一个传输实体不是无限可分的。

为了实现GPS算法的各项性能指标，人们提出了许多逼近GPS的算法，其中WFQ[2]和WF2Q[3]最具代表性。二者都是按照数据包在GPS中完成时间的递增顺序来转发各个连接的数据包。不同的是：WFQ从已经到达的所有数据包中选择在相应的GPS中具有最小完成时间的数据包来转发；而WF2Q是从GPS中已经开始接受服务的数据包中选择完成时间最小的数据包发送即{Pik|bikGPS≤？子≤b■■}，bik表示连接i的第k个数据包在GPS系统中开始接受服务的时刻[3]。

Virtual Clock算法为每个连接定义了两个虚拟时钟：Virtual clock和auxVC[4]。数据包到达后被打上一个由虚拟时钟根据连接速率计算出来的时间戳。调度器按照时间戳的递增顺序转发各个连接的数据包。

2 基于速率的分组调度模型

在基于速率的调度算法中速率是一个关键的概念。调度器中带宽的分配、流量的调节等操作都是以速率为参数执行的。

2.1 模型概述

网络中的每个连接在完成一次通信的过程中都要经历3个状态：Idle、Enabled和Blocked（如图1所示）。连接建立后首先进入Idle状态等待数据包的到达。当第一个数据包到达后连接被标记为eligible，进程模型调用函数choose_connection（）在所有标记为eligible的连接中选择一个连接发送数据。如果该连接得到发包权，进程由Idle转入Enabled状态。进入Enabled状态的进程调用函数dequeue（）发送数据，之后调用函数choose_connection（）确定状态转移方向：

（1）如果该连接队列中仍有待发的数据包且连接有权发包，状态转移到自身；

（2）如果队列中仍有待发的数据包但连接无权发包，状态转移到Blocked；

（3）如果队列为空则转移到Idle状态。处于Blocked状态的连接随着时间的推移可以重新获取发包权，此时进程状态由Blocked转移到Enabled并发送数据。

2.2 模型的模块化实现

为了更加精确地说明进程的原理，为每个连接定义了一个数据结构，如表1所示。连接建立时会提供一个速率参数rq。re是调度器为连接提供的服务速率的最大值，它是根据rq的值计算得到的，计算的方法由具体的算法指明。rm是连接实际得到的服务速率。对于有包待发的连接，如果它的rm小于re，则此连接将被标记为eligible，否则被标记为ineligible。

数据包到达后，进程调用函数packet_arrival（）完成数据包入队等相关操作。函数effective_rate_update（）负责更新的值，结果作为参数传递给eligible_update（）函数，用于更新各个连接的eligible标记。当调度器空闲时调用函数choose_connection（）在标记为eligible的所有连接中选取一个连接，然后利用packet_send（）函数完成发送数据的任务。进程中主要模块的伪代码如下所示，抽象模块的实现方法由具体算法指明。

Eligible_update（）

1 for each connection in Connections do

2 if c.is_overserved（）==TRUE

3 c.state←ineligible

4 else if c's queue is empty

5 c.state←idle

6 else

7 c.state←eligible

Is_overserved（）

1 if rm > re

2 return TRUE

3 else

4 return FALSE

Packet_send（）

1 dequeue（）；

2 if c.is_overserved（）==TRUE

3 c.state←ineligible

4 else if c is empty

5 c.state←idle

6 else

7 c.state←eligible

3 模型的特点

（1）模型提供了良好的通用性。进程模型中没有说明带*的抽象模块的实现方法，而是留给应用时由具体算法来指明。这样做的好处是使得进程模型具有良好的通用性，可以作为载体实现多种算法。

（2）模块化的实现方法。 模型采用了模块化的设计方式并提供了各模块间的接口。设计算法时只需将重点放在各个模块的具体实现上，使得算法开发高效而快速。

（3）能够提供速率保证。模型以各个连接的速率为主要参数为其分配系统资源。各个连接都能够得到满意的服务速率，并保证了端到端的时延。且根据各个连接速率值的大小按比例分配资源也体现了良好的公平性。

4 进程的应用

4.1 模型在WFQ中的应用

WFQ模拟数据包在相应GPS中的转发顺序，提供了和GPS算法相近的性能。为了做到这一点，WFQ必须计算各个数据包在GPS中的完成时间并按递增顺序转发数据包。文献[5]证明在包到达时只计算一次虚拟完成时间并按其递增顺序发包不会影响算法的性能。这样做的好处是：在不降低算法性能的前提下大大减小了算法的复杂度。

在WFQ算法中GPS作为参考系统而存在，决定了各个连接的数据包的转发顺序。因此，可以用两个进程来实现WFQ：①GPS进程；②WFQ进程。前者通过唤醒connection_setup（）和packet_arrival（）完成连接建立、虚拟时间的计算和effective_rate_update（）的更新工作，结果被WFQ进程利用作为选包的依据。当WFQ调度器空闲时唤醒WFQ进程，调用choose_connection（）和packet_send（）选择数据包并完成发送工作。主要模块的伪代码如下所示。

Packet_arrival（）

1 p.vt=p′s finishing virtual time

2 enqueue（）

Effective_rate_update（）

1 ？准total =■r■

2 for each connection which has packet to send do

3 c·re=r·■

Choose_connection（）

1 for each connection which has arrival packets do

vt[]=the head packets vt of all busy connections

2 INDEX=Min（vt[]）

3 Return INDEX

4.2 模型在VC中的应用

VC不需要计算rq和？准total之间的关系，使得算法的实现简便易行。在VC中每个连接都能够按照r■接受服务而无需考虑其他连接的状态.当调度器空闲时进程唤醒packet_send（），选择具有最小虚拟完成时间的数据包发送。模块伪码如下所示。

Packet_arrival（）

1 If the packet is the first packet

2 p.vt=Current_time

3 else[2]

4 auxVC←max（real time，auxVC）

5 p.vc←vc+Vtick

6 auxVC←auxVC+Vtick

7 p.vt←auxVC

8 equeue（packet p）

Choose_connection（）

1 connection c=the connection， among the set of eligible ones， whose first packet in the packet queue has the smallest virtual clock stamp

2 return connection c

5 结 论

本文提出了一种基于速率的分组调度算法模型。该模型具有很好的通用性，可以作为载体实现各种基于速率的调度算法。模型具有很多优良的特性，其中模块化的设计方式为算法的实现提供了统一的框架，使得算法实现简便易行。

主要参考文献

[1]A K Parekh，R G Gallage. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks：The Single-node Case[J]. IEEE/ACM Transactions on Networking，1993，1（3）：344-357.

[2]J C R Bennett，H Zhang. Hierarchical Packet Fair Queuing Algorithms[J].IEEE/ACM Transactions on Networking，1997，5（5）：675-689.

[3]J C R Bennett，H Zhang. WF2Q： Worst-Case Fair Weighted Fair Queuing[C].Proceedings of 15th Annual Joint Conference of The IEEE Computer Societies（IEEE INFOCOM96），1996，Vol.1：120-128.

[4]L Zhang. Virtual Clock： A New Traffic Control Algorithm for Packet Switching Networks[J]. ACM SIGCOMM Computer Communication Review， 1990， 20（4）：19-29.

[5]H Y Tyan， B Wang， Y Ye， J C Hou. NetSimQ： A Java Integrated Network Simulation Tool for QoS Control in Point-to-point High Speed Networks[C]. 3rd NASA Research and Education Network Workshop， Moffett Field， CA ，1998.