路由器隊列調度機制研究

李 琳

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

1 常見路由器隊列調度機制

（1）先進先出隊列FIFO調度算法

（2）優先級隊列PQ調度算法

（3）加權公平隊列WFQ調度算法

（4）差值加權輪訓隊列DWRR調度算法

2 隊列調度算法的性能指標

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

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

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

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

3 現有隊列調度算法性能比較

3.1 基于輪詢的調度算法

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

3.2 加權公平隊列WFQ調度算法

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

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

3.3 基于時延的調度算法

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

4 基于區分服務的調度算法

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

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

5 結論

隊列調度算法的目的都是以可實現的復雜性為代價來提供更好的服務質量：公平性和時延性能。除了先入先出、優先級和傳統輪循調度外,先進的隊列調度算法都是把分組放到不同的隊列里,然后再為其計算一個時簽,根據時簽的大小來對分組進行調度.對于PFQ算法,其出發點在于為每個隊列提供帶寬保證(從而時延得到一定的保證),所以在其時簽的計算中只用到了速率參數和分組長度參數；而基于時延的調度算法,則以提供時延保證為主要目的,所以在其時簽的計算中,只引入了隊列的時延參數。本文首先介紹了幾種傳統的隊列調度機制的算法如FIFO、PQ、WFQ和DWRR這四種傳統的調度算法。然后接下來對隊列調度算法的性能指標及幾種隊列調度算法的優缺點進行了闡述和比較。最后在這些算法的基礎上，根據現有的區分服務模型的提出了新的調度機制，并對其進行了改進。總之，未來的隊列調度機制一定要適合網絡帶寬的高速化和業務多樣化的發展趨勢。首先要保證高的分組調度速度，同時在時延特性和公平性方面有較好的保證。