路由器隊(duì)列調(diào)度機(jī)制研究

李 琳

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

1 常見(jiàn)路由器隊(duì)列調(diào)度機(jī)制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于輪詢和WFQ的調(diào)度算法可以看成是基于速率的調(diào)度算法，這種算法通常為每個(gè)隊(duì)列提供一定的速率保證來(lái)達(dá)到提供時(shí)延保證的目的。而基于時(shí)延的調(diào)度算法則是以（為各隊(duì)列）直接提供時(shí)延保證為目的，這類算法的代表是最早期限優(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ù)的一個(gè)子網(wǎng)被稱為DiffServ域,它由一些邊緣路由器和域內(nèi)路由器組成,邊緣路由器執(zhí)行較為復(fù)雜的業(yè)務(wù)流分類、業(yè)務(wù)量調(diào)節(jié)及隊(duì)列管理和調(diào)度的功能,而域內(nèi)路由器則執(zhí)行較為簡(jiǎn)單的隊(duì)列管理和調(diào)度的功能。之前介紹的隊(duì)列調(diào)度都沒(méi)有邊緣交換節(jié)點(diǎn)和域內(nèi)交換節(jié)點(diǎn)。都是基于每個(gè)業(yè)務(wù)流的調(diào)度算法，他們需要交換節(jié)點(diǎn)維護(hù)每個(gè)業(yè)務(wù)流的一些狀態(tài)信息，盡管這樣可以達(dá)到很好的調(diào)度性能，但同時(shí)帶來(lái)了不易擴(kuò)展和不強(qiáng)壯的缺點(diǎn)。

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

5 結(jié)論

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