李 琳

(浙江工業(yè)大學，浙江 杭州310023)

1 常見路由器隊列調(diào)度機制

（1）先進先出隊列FIFO調(diào)度算法

（2）優(yōu)先級隊列PQ調(diào)度算法

（3）加權(quán)公平隊列WFQ調(diào)度算法

（4）差值加權(quán)輪訓隊列DWRR調(diào)度算法

2 隊列調(diào)度算法的性能指標

隊列調(diào)度算法性能的好壞主要涉及到時延性能、公平性、復(fù)雜性這三個方面。

時延性能:隊列調(diào)度算法應(yīng)為不同的業(yè)務(wù)流提供端到端的時延保證,而且只與此業(yè)務(wù)流的某些參數(shù)(如帶寬需求等)有關(guān),而與其他的業(yè)務(wù)流無關(guān)。Stiliadis和Varma首先提出了一種分析網(wǎng)絡(luò)中不同隊列調(diào)度算法帶來的端到端時延的模型；時延速率調(diào)度器(LRS:Latency2Rate Server)。Francini隨后又提出了另一種分析端到端時延的模型:速率分隔(RST:Rate2Spaced2Timestamp Scheduler),此模型的限制條件比LRS要少且在定長分組環(huán)境下應(yīng)用時更加有效。

公平性:可用的鏈路帶寬必須以公平的方式分配給共享此鏈路的各業(yè)務(wù)流:此外隊列調(diào)度算法必須能夠隔離不同的業(yè)務(wù)流,讓不同的流只享用自己可以享用的帶寬,這樣即使存在惡意或高突發(fā)性業(yè)務(wù),它也不致影響到其他的正常業(yè)務(wù)流。關(guān)于算法公平的定義有:服務(wù)公平指數(shù)(SFI:Service Fairness Index)和最壞公平指數(shù)(WFI:Worst2case Fairness Index)兩種。

復(fù)雜性和可擴展性:調(diào)度算法實現(xiàn)起來應(yīng)該比較簡單.在高速網(wǎng)絡(luò)中,傳輸一個分組的時間很小,所以調(diào)度算法必須在短時間里完成對分組的調(diào)度,這就要求調(diào)度算法盡量簡單,易于實現(xiàn)。 另外當業(yè)務(wù)流數(shù)量增加和鏈路速率變化范圍較大時,調(diào)度算法仍應(yīng)有效工作；這要求調(diào)度算法應(yīng)該具有良好的可擴展性。

3 現(xiàn)有隊列調(diào)度算法性能比較

3.1 基于輪詢的調(diào)度算法

傳統(tǒng)的輪循(RR:Round Robin)算法對不同隊列(業(yè)務(wù)流)進行無區(qū)別的循環(huán)調(diào)度服務(wù).這樣,如果不同的隊列具有不同的分組長度,則分組長度大的隊列可能會比分組長度小的隊列接受更多的服務(wù),使隊列之間產(chǎn)生不公平的現(xiàn)象；而且,這種算法不能對業(yè)務(wù)提供時延保證.后來為了改進RR算法，出現(xiàn)了一些改進型的算法。如加權(quán)輪詢（WRR Weighted Round Robin），差額輪詢（DRR Deficit Round Robin），緊急輪詢（URR Urgencybased Round Robin）。

3.2 加權(quán)公平隊列WFQ調(diào)度算法

WFQ調(diào)度機制是由Demers等人提出,又由Parekh等人實現(xiàn)基于報文的PGPS（packet by packet generalized processor sharing）的排隊算法。

WFQ調(diào)度機制主要分為基于流的WFQ和基于類的WFQ（CBWFQ）2種。它們的主要區(qū)別在于：前者的隊列數(shù)在理論上沒有限制，但隊列數(shù)目太多會增大調(diào)度的復(fù)雜度，而后者最多為64個隊列。WFQ算法能到達很好的公平性和時延保證，但是系統(tǒng)其系統(tǒng)需時間函數(shù)計算復(fù)雜度為O（N）（N為總的隊列數(shù)），且具有較大的WFI，使得輸出的突發(fā)度增加。它雖然很好的解決了RR機制的不公平性，但是包含了GPS調(diào)度機制的局限性，它調(diào)度的結(jié)果會帶來帶寬保證和時延保證的耦合性（即低帶寬保證總以為著不嚴格的時延保證），這個特性使得WFQ不適合調(diào)度某些類型的業(yè)務(wù)，這類業(yè)務(wù)的特點是帶寬需求不大，但是有著極嚴格的時延要求，如語音等實時業(yè)務(wù)。

3.3 基于時延的調(diào)度算法

基于輪詢和WFQ的調(diào)度算法可以看成是基于速率的調(diào)度算法，這種算法通常為每個隊列提供一定的速率保證來達到提供時延保證的目的。而基于時延的調(diào)度算法則是以（為各隊列）直接提供時延保證為目的，這類算法的代表是最早期限優(yōu)先（EDF，Earliest Deadline First）。

4 基于區(qū)分服務(wù)的調(diào)度算法

區(qū)分業(yè)務(wù)(Diffserv Differentiated Service)體系結(jié)構(gòu)正成為解決因特網(wǎng)上服務(wù)質(zhì)量的一種有效的辦法，能支持DiffServ技術(shù)的一個子網(wǎng)被稱為DiffServ域,它由一些邊緣路由器和域內(nèi)路由器組成,邊緣路由器執(zhí)行較為復(fù)雜的業(yè)務(wù)流分類、業(yè)務(wù)量調(diào)節(jié)及隊列管理和調(diào)度的功能,而域內(nèi)路由器則執(zhí)行較為簡單的隊列管理和調(diào)度的功能。之前介紹的隊列調(diào)度都沒有邊緣交換節(jié)點和域內(nèi)交換節(jié)點。都是基于每個業(yè)務(wù)流的調(diào)度算法，他們需要交換節(jié)點維護每個業(yè)務(wù)流的一些狀態(tài)信息，盡管這樣可以達到很好的調(diào)度性能，但同時帶來了不易擴展和不強壯的缺點。

基于這種考慮，Stocia提出了兩種新的調(diào)度算法：CSFQ(Core Stateless Fair Queueing)和CJVC(Core Jitter Virtual Clock),其核心在于對交換節(jié)點進行了“邊界交換節(jié)點”和“域內(nèi)交換節(jié)點”的區(qū)分，從而不需要每個交換節(jié)點都維護所有業(yè)務(wù)流的狀態(tài)信息。

5 結(jié)論

隊列調(diào)度算法的目的都是以可實現(xiàn)的復(fù)雜性為代價來提供更好的服務(wù)質(zhì)量：公平性和時延性能。除了先入先出、優(yōu)先級和傳統(tǒng)輪循調(diào)度外,先進的隊列調(diào)度算法都是把分組放到不同的隊列里,然后再為其計算一個時簽,根據(jù)時簽的大小來對分組進行調(diào)度.對于PFQ算法,其出發(fā)點在于為每個隊列提供帶寬保證(從而時延得到一定的保證),所以在其時簽的計算中只用到了速率參數(shù)和分組長度參數(shù)；而基于時延的調(diào)度算法,則以提供時延保證為主要目的,所以在其時簽的計算中,只引入了隊列的時延參數(shù)。本文首先介紹了幾種傳統(tǒng)的隊列調(diào)度機制的算法如FIFO、PQ、WFQ和DWRR這四種傳統(tǒng)的調(diào)度算法。然后接下來對隊列調(diào)度算法的性能指標及幾種隊列調(diào)度算法的優(yōu)缺點進行了闡述和比較。最后在這些算法的基礎(chǔ)上，根據(jù)現(xiàn)有的區(qū)分服務(wù)模型的提出了新的調(diào)度機制，并對其進行了改進?？傊磥淼年犃姓{(diào)度機制一定要適合網(wǎng)絡(luò)帶寬的高速化和業(yè)務(wù)多樣化的發(fā)展趨勢。首先要保證高的分組調(diào)度速度，同時在時延特性和公平性方面有較好的保證。