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

　　[關(guān)鍵詞] 中文社科類核心期刊,分組調(diào)度,服務(wù)質(zhì)量,速率,算法,模型

　　0 引 言

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

　　基于速率的分組調(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)度算法模型。該模型具有很好的通用性，可以作為載體實現(xiàn)各種基于速率的調(diào)度算法。同時，模塊化的設(shè)計方式為算法的實現(xiàn)提供了統(tǒng)一的框架，使得算法實現(xiàn)簡便易行。

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

　　1 算法簡介

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

　　GPS定義為：

　　■≥■ (j=1，2，…，n)(1)

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

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

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

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

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

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

　　2.1 模型概述

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

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

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

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

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

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

　　數(shù)據(jù)包到達后，進程調(diào)用函數(shù)packet_arrival()完成數(shù)據(jù)包入隊等相關(guān)操作。函數(shù)effective_rate_update()負責更新的值，結(jié)果作為參數(shù)傳遞給eligible_update()函數(shù)，用于更新各個連接的eligible標記。當調(diào)度器空閑時調(diào)用函數(shù)choose_connection()在標記為eligible的所有連接中選取一個連接，然后利用packet_send()函數(shù)完成發(fā)送數(shù)據(jù)的任務(wù)。進程中主要模塊的偽代碼如下所示，抽象模塊的實現(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 模型的特點

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

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

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

　　4 進程的應(yīng)用

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

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

　　在WFQ算法中GPS作為參考系統(tǒng)而存在，決定了各個連接的數(shù)據(jù)包的轉(zhuǎn)發(fā)順序。因此，可以用兩個進程來實現(xiàn)WFQ：①GPS進程;②WFQ進程。前者通過喚醒connection_setup()和packet_arrival()完成連接建立、虛擬時間的計算和effective_rate_update()的更新工作，結(jié)果被WFQ進程利用作為選包的依據(jù)。當WFQ調(diào)度器空閑時喚醒WFQ進程，調(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 ?準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 packet’s vt of all busy connections

　　2 INDEX=Min(vt[])

　　3 Return INDEX

　　4.2 模型在VC中的應(yīng)用

　　VC不需要計算rq和?準total之間的關(guān)系，使得算法的實現(xiàn)簡便易行。在VC中每個連接都能夠按照r■接受服務(wù)而無需考慮其他連接的狀態(tài).當調(diào)度器空閑時進程喚醒packet_send()，選擇具有最小虛擬完成時間的數(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)度算法模型。該模型具有很好的通用性，可以作為載體實現(xiàn)各種基于速率的調(diào)度算法。模型具有很多優(yōu)良的特性，其中模塊化的設(shè)計方式為算法的實現(xiàn)提供了統(tǒng)一的框架，使得算法實現(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 Net