基于速率的分組調度算法模型的研究

李志華

[摘 要] 分組調度算法是為網絡提供服務質量保證的一項重要措施。本文提出了一種具有良好通用性的分組調度算法模型，該模型為實現各種基于速率的調度算法提供基本框架，模塊化的設計方式使得算法的實現簡便易行。

[關鍵詞] 分組調度；服務質量；速率；算法；模型

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.