基于速率的分組調(diào)度算法模型的研究

李志華

[摘 要] 分組調(diào)度算法是為網(wǎng)絡(luò)提供服務(wù)質(zhì)量保證的一項(xiàng)重要措施。本文提出了一種具有良好通用性的分組調(diào)度算法模型，該模型為實(shí)現(xiàn)各種基于速率的調(diào)度算法提供基本框架，模塊化的設(shè)計(jì)方式使得算法的實(shí)現(xiàn)簡(jiǎn)便易行。

[關(guān)鍵詞] 分組調(diào)度；服務(wù)質(zhì)量；速率；算法；模型

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

[中圖分類號(hào)] TP301.6 [文獻(xiàn)標(biāo)識(shí)碼] A [文章編號(hào)] 1673 - 0194（2014）05- 0038- 03

0 引 言

隨著網(wǎng)絡(luò)的飛速發(fā)展，其承載的業(yè)務(wù)逐漸向多媒體方向發(fā)展。視頻點(diǎn)播、遠(yuǎn)程會(huì)議等實(shí)時(shí)性業(yè)務(wù)需要網(wǎng)絡(luò)為用戶提供QoS（Quality of Service）保證。分組調(diào)度算法克服了傳統(tǒng)網(wǎng)絡(luò)無法提供QoS保證的缺點(diǎn)，其中基于速率的分組調(diào)度算法由于可以為用戶提供時(shí)延保證和良好的公平性，已成為近年來人們研究的重點(diǎn)。

基于速率的分組調(diào)度算法主要包括：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）等。本文總結(jié)以上算法的公共特征提出了一種分組調(diào)度算法模型。該模型具有很好的通用性，可以作為載體實(shí)現(xiàn)各種基于速率的調(diào)度算法。同時(shí)，模塊化的設(shè)計(jì)方式為算法的實(shí)現(xiàn)提供了統(tǒng)一的框架，使得算法實(shí)現(xiàn)簡(jiǎn)便易行。

本文首先介紹了幾種經(jīng)典調(diào)度算法的原理，在此基礎(chǔ)上提出了一種算法模型并給出了模型的模塊化實(shí)現(xiàn)方法，最后以模型為基礎(chǔ)實(shí)現(xiàn)了WFQ和VC兩種算法。

1 算法簡(jiǎn)介

GPS和Virtual Clock是兩種具有代表性的基于速率的分組調(diào)度算法。經(jīng)過嚴(yán)格數(shù)學(xué)證明的GPS算法為許多后續(xù)算法提供了理論依據(jù)。

GPS定義為：

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

對(duì)每個(gè)連接i均成立。其中Si（t1，t2）表示連接i在[t1，t2]內(nèi)獲得的服務(wù)量，？準(zhǔn)i是和連接i相對(duì)應(yīng)的非負(fù)實(shí)數(shù)[1]。

GPS能夠同時(shí)調(diào)度n個(gè)連接的數(shù)據(jù)并為每個(gè)連接提供一個(gè)最小的服務(wù)速率gi=r·？準(zhǔn)i /■？準(zhǔn)i。它可以為每個(gè)連接提供嚴(yán)格的端到端時(shí)延保證和絕對(duì)的公平性，但它是一種理想的算法（同時(shí)為n個(gè)連接提供服務(wù)且調(diào)度的數(shù)據(jù)無限可分）。實(shí)際中，調(diào)度器在某一時(shí)刻只能為一個(gè)連接服務(wù)且數(shù)據(jù)包作為一個(gè)傳輸實(shí)體不是無限可分的。

為了實(shí)現(xiàn)GPS算法的各項(xiàng)性能指標(biāo)，人們提出了許多逼近GPS的算法，其中WFQ[2]和WF2Q[3]最具代表性。二者都是按照數(shù)據(jù)包在GPS中完成時(shí)間的遞增順序來轉(zhuǎn)發(fā)各個(gè)連接的數(shù)據(jù)包。不同的是：WFQ從已經(jīng)到達(dá)的所有數(shù)據(jù)包中選擇在相應(yīng)的GPS中具有最小完成時(shí)間的數(shù)據(jù)包來轉(zhuǎn)發(fā)；而WF2Q是從GPS中已經(jīng)開始接受服務(wù)的數(shù)據(jù)包中選擇完成時(shí)間最小的數(shù)據(jù)包發(fā)送即{Pik|bikGPS≤？子≤b■■}，bik表示連接i的第k個(gè)數(shù)據(jù)包在GPS系統(tǒng)中開始接受服務(wù)的時(shí)刻[3]。

Virtual Clock算法為每個(gè)連接定義了兩個(gè)虛擬時(shí)鐘：Virtual clock和auxVC[4]。數(shù)據(jù)包到達(dá)后被打上一個(gè)由虛擬時(shí)鐘根據(jù)連接速率計(jì)算出來的時(shí)間戳。調(diào)度器按照時(shí)間戳的遞增順序轉(zhuǎn)發(fā)各個(gè)連接的數(shù)據(jù)包。

2 基于速率的分組調(diào)度模型

在基于速率的調(diào)度算法中速率是一個(gè)關(guān)鍵的概念。調(diào)度器中帶寬的分配、流量的調(diào)節(jié)等操作都是以速率為參數(shù)執(zhí)行的。

2.1 模型概述

網(wǎng)絡(luò)中的每個(gè)連接在完成一次通信的過程中都要經(jīng)歷3個(gè)狀態(tài)：Idle、Enabled和Blocked（如圖1所示）。連接建立后首先進(jìn)入Idle狀態(tài)等待數(shù)據(jù)包的到達(dá)。當(dāng)?shù)谝粋€(gè)數(shù)據(jù)包到達(dá)后連接被標(biāo)記為eligible，進(jìn)程模型調(diào)用函數(shù)choose_connection（）在所有標(biāo)記為eligible的連接中選擇一個(gè)連接發(fā)送數(shù)據(jù)。如果該連接得到發(fā)包權(quán)，進(jìn)程由Idle轉(zhuǎn)入Enabled狀態(tài)。進(jìn)入Enabled狀態(tài)的進(jìn)程調(diào)用函數(shù)dequeue（）發(fā)送數(shù)據(jù)，之后調(diào)用函數(shù)choose_connection（）確定狀態(tài)轉(zhuǎn)移方向：

（1）如果該連接隊(duì)列中仍有待發(fā)的數(shù)據(jù)包且連接有權(quán)發(fā)包，狀態(tài)轉(zhuǎn)移到自身；

（2）如果隊(duì)列中仍有待發(fā)的數(shù)據(jù)包但連接無權(quán)發(fā)包，狀態(tài)轉(zhuǎn)移到Blocked；

（3）如果隊(duì)列為空則轉(zhuǎn)移到Idle狀態(tài)。處于Blocked狀態(tài)的連接隨著時(shí)間的推移可以重新獲取發(fā)包權(quán)，此時(shí)進(jìn)程狀態(tài)由Blocked轉(zhuǎn)移到Enabled并發(fā)送數(shù)據(jù)。

2.2 模型的模塊化實(shí)現(xiàn)

為了更加精確地說明進(jìn)程的原理，為每個(gè)連接定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)，如表1所示。連接建立時(shí)會(huì)提供一個(gè)速率參數(shù)rq。re是調(diào)度器為連接提供的服務(wù)速率的最大值，它是根據(jù)rq的值計(jì)算得到的，計(jì)算的方法由具體的算法指明。rm是連接實(shí)際得到的服務(wù)速率。對(duì)于有包待發(fā)的連接，如果它的rm小于re，則此連接將被標(biāo)記為eligible，否則被標(biāo)記為ineligible。

數(shù)據(jù)包到達(dá)后，進(jìn)程調(diào)用函數(shù)packet_arrival（）完成數(shù)據(jù)包入隊(duì)等相關(guān)操作。函數(shù)effective_rate_update（）負(fù)責(zé)更新的值，結(jié)果作為參數(shù)傳遞給eligible_update（）函數(shù)，用于更新各個(gè)連接的eligible標(biāo)記。當(dāng)調(diào)度器空閑時(shí)調(diào)用函數(shù)choose_connection（）在標(biāo)記為eligible的所有連接中選取一個(gè)連接，然后利用packet_send（）函數(shù)完成發(fā)送數(shù)據(jù)的任務(wù)。進(jìn)程中主要模塊的偽代碼如下所示，抽象模塊的實(shí)現(xiàn)方法由具體算法指明。

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 模型的特點(diǎn)

（1）模型提供了良好的通用性。進(jìn)程模型中沒有說明帶*的抽象模塊的實(shí)現(xiàn)方法，而是留給應(yīng)用時(shí)由具體算法來指明。這樣做的好處是使得進(jìn)程模型具有良好的通用性，可以作為載體實(shí)現(xiàn)多種算法。

（2）模塊化的實(shí)現(xiàn)方法。 模型采用了模塊化的設(shè)計(jì)方式并提供了各模塊間的接口。設(shè)計(jì)算法時(shí)只需將重點(diǎn)放在各個(gè)模塊的具體實(shí)現(xiàn)上，使得算法開發(fā)高效而快速。

（3）能夠提供速率保證。模型以各個(gè)連接的速率為主要參數(shù)為其分配系統(tǒng)資源。各個(gè)連接都能夠得到滿意的服務(wù)速率，并保證了端到端的時(shí)延。且根據(jù)各個(gè)連接速率值的大小按比例分配資源也體現(xiàn)了良好的公平性。

4 進(jìn)程的應(yīng)用

4.1 模型在WFQ中的應(yīng)用

WFQ模擬數(shù)據(jù)包在相應(yīng)GPS中的轉(zhuǎn)發(fā)順序，提供了和GPS算法相近的性能。為了做到這一點(diǎn)，WFQ必須計(jì)算各個(gè)數(shù)據(jù)包在GPS中的完成時(shí)間并按遞增順序轉(zhuǎn)發(fā)數(shù)據(jù)包。文獻(xiàn)[5]證明在包到達(dá)時(shí)只計(jì)算一次虛擬完成時(shí)間并按其遞增順序發(fā)包不會(huì)影響算法的性能。這樣做的好處是：在不降低算法性能的前提下大大減小了算法的復(fù)雜度。

在WFQ算法中GPS作為參考系統(tǒng)而存在，決定了各個(gè)連接的數(shù)據(jù)包的轉(zhuǎn)發(fā)順序。因此，可以用兩個(gè)進(jìn)程來實(shí)現(xiàn)WFQ：①GPS進(jìn)程；②WFQ進(jìn)程。前者通過喚醒connection_setup（）和packet_arrival（）完成連接建立、虛擬時(shí)間的計(jì)算和effective_rate_update（）的更新工作，結(jié)果被WFQ進(jìn)程利用作為選包的依據(jù)。當(dāng)WFQ調(diào)度器空閑時(shí)喚醒WFQ進(jìn)程，調(diào)用choose_connection（）和packet_send（）選擇數(shù)據(jù)包并完成發(fā)送工作。主要模塊的偽代碼如下所示。

Packet_arrival（）

1 p.vt=p′s finishing virtual time

2 enqueue（）

Effective_rate_update（）

1 ？準(zhǔn)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中的應(yīng)用

VC不需要計(jì)算rq和？準(zhǔn)total之間的關(guān)系，使得算法的實(shí)現(xiàn)簡(jiǎn)便易行。在VC中每個(gè)連接都能夠按照r■接受服務(wù)而無需考慮其他連接的狀態(tài).當(dāng)調(diào)度器空閑時(shí)進(jìn)程喚醒packet_send（），選擇具有最小虛擬完成時(shí)間的數(shù)據(jù)包發(fā)送。模塊偽碼如下所示。

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 結(jié) 論

本文提出了一種基于速率的分組調(diào)度算法模型。該模型具有很好的通用性，可以作為載體實(shí)現(xiàn)各種基于速率的調(diào)度算法。模型具有很多優(yōu)良的特性，其中模塊化的設(shè)計(jì)方式為算法的實(shí)現(xiàn)提供了統(tǒng)一的框架，使得算法實(shí)現(xiàn)簡(jiǎn)便易行。

主要參考文獻(xiàn)

[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.