摘 要： 在傳統加權輪詢調度算法和嚴格優先級調度算法的基礎上，加入令牌桶機制，實現了一種改進算法。在多業務并存網絡中，該算法能夠對不同等級的業務實現不同的QoS（服務質量），同時，在業務流量發生變化時，能夠動態調整相應業務的帶寬，且不會對高優先級隊列造成影響。仿真實驗表明，該算法可以在一定范圍內適應網絡的變化，有效緩解了突發流量所造成的報文丟包問題，大大提高了網絡性能。
關鍵詞： 多業務網絡；QoS；動態調整；丟包
0 引言
隨著科技的飛速發展，網絡中的業務量也呈爆炸式的增長，而且不同的業務在時延、丟包等性能方面也有著不同程度的要求。但網絡資源總是有限的，在網絡總帶寬固定的情況下，如果某類業務占用的帶寬越多，那么其他業務能使用的帶寬就越少，可能會影響其他業務的使用。基于此，專家們提出了QoS的概念，針對各種應用的不同需求，來對網絡資源進行合理的規劃和分配，從而使網絡資源得到高效利用。
隊列調度機制作為QoS技術的核心機制之一，一直以來就是研究的熱點。所謂隊列調度就是在網絡中傳送業務時，如何從多個數據包隊列中選擇一個隊列轉發[1]。一個好的隊列調度算法可以大大提高網絡的性能，這在帶寬資源擴展速度遠遠落后于網絡中消息增加速度的今天，重要性不言而喻。
目前，已有很多種隊列調度算法被提出，如嚴格優先級隊列調度（Strict Priority，SP）算法、加權輪詢調度（Weighted Round Robin，WRR）算法、加權差額輪詢調度（Weighted Deficit Round Robin，WDRR）算法、加權公平調度（Weighted Fair Queuing，WFQ）算法等[2-4]，但面對千變萬化的網絡環境，這些算法總是存在著這樣或那樣的缺陷。本文在研究了傳統的各種隊列調度算法之后，在WRR算法的基礎上加以改進，大大提高了算法的性能，且能在一定范圍內適應網絡中流量的變化。
1 幾種典型的隊列調度算法
1.1 SP算法
SP算法是針對關鍵業務應用設計的。SP算法嚴格按照優先級從高到低的順序調度隊列，當高優先級報文中存在報文時，低優先級隊列得不到調度的機會。這就導致SP算法雖然可以保證高優先級隊列的服務質量（Quality of Service，QoS），但是當高優先級隊列中始終有報文存在時，低優先級隊列中的報文得不到調度，造成低優先級隊列“餓死”現象。
1.2 WRR算法
WRR算法解決了SP算法中低優先級隊列“餓死”的問題。在WRR調度算法中根據隊列的權值來決定轉發報文的數量。首先設置一個變量weight記錄隊列的權值，在進行隊列調度時，首先判斷weight值是否大于0以及隊列是否非空，若weigdt大于0且隊列非空，則從該隊列中轉發一個分組，并將weight減1，繼續進行條件判斷，直到weight值等于0或隊列為空，轉到下一個隊列開始調度，當所有隊列都輪詢一遍后，將每個隊列的weight值恢復為初始值，然后從第一個隊列開始，再次遍歷，不停地重復以上步驟。
1.3 WDRR算法
WRR調度雖然解決了SP調度中的低優先級隊列“餓死”問題，但由于算法以分組為單位進行隊列調度，當隊列中分組長度不同時，就會導致調度的公平性問題。由此，提出了以字節為單位來進行調度的WDRR調度。WDRR算法中首先要設置一個粒度值表示每個權值所代表的字節數，并設置一個變量DC[i]表示第i個隊列在一次輪詢中可以調度的字節數，初始化為0。每輪調度隊列之前計算隊列權值與粒度的乘積加上DC[i]的初值，作為本輪調度可以轉發的最大字節數，隊列調度過程如下：
（1）DC[i]=DC[i]+粒度*權值；
（2）若隊列為空，則只需將DC[i]置0，轉到下一隊列開始調度；
（3）若隊列不為空，則比較DC[i]與接下來要調度的分組長度length的大小，若DC[i]>=length，則轉發該分組，更新DC[i]的值（DC[i]=DC[i]-length），并轉向（2），否則轉到下一個隊列繼續調度；
（4）若一輪調度完成，則轉到第一個隊列，轉到（2），繼續調度。
DWRR調度雖然解決了WRR調度中的公平性問題，但仍然存在如下一系列的缺點[5-6]：
（1）不能體現高優先級隊列的絕對優先級地位。
（2）分組時延得不到保證，當某一分組錯過了本次調度時，它將不得不等待一個輪詢周期的時間，尤其是當這種情況出現在高優先級隊列時，會造成嚴重后果。
（3）各隊列分配到的權值是固定的，當網絡情況發生變化時，不能很好地適應，例如，高優先級報文突然增多，但由于分配的帶寬已經固定了，多余的報文將得不到轉發，只能丟棄。
2 改進算法描述
本文針對以上算法存在的缺點，提出一種改進的隊列調度算法，經驗證，改進算法很好地解決了以上問題。其基本流程如下：
（1）報文入普通8隊列。報文根據dscp值映射出本地優先級，根據本地優先級進入相應的8隊列。
（2）對隊列進行分組。將QoS需求近似的隊列分在同一組，每一組以組中優先級最低隊列的優先級作為本組中所有隊列的優先級（避免優先級重復）。為了保證高優先級隊列的絕對優先地位，不同組之間的隊列按照SP算法進行調度，保證高優先級隊列優先轉發。同一組內的各隊列之間進行DWRR調度，保證QoS需求近似隊列的相對公平性。
（3）從8隊列（QueueLoop[8]）映射到64隊列（FlowLoop[64]）。本設計提供一套模板，該模板包含64個隊列，分8種優先級，每個隊列都設定好了對應優先級值（priority）。首先從QueueLoop[1]開始，以此與FlowLoop進行匹配，若優先級相同且FlowLoop還未被其他隊列占用，則匹配成功，進行下一條QueueLoop的匹配工作，否則繼續匹配，直到匹配成功為止，流程如圖1。
（4）隊列調度。如上所述，分組內進行DWRR調度，分組間進行SP調度。為了使低優先級隊列不被“餓死”，本算法引入了令牌桶機制對隊列和整個分組進行限速，對每個隊列的超帶寬流量進行降級處理，將優先級降為最低，并加入優先級最低的分組與組中原有隊列按權值共享剩余帶寬。這樣當隊列出現突發流量時，可以有效減小突發報文的丟包率，并且在低優先級隊列空閑時可以自動占用剩余帶寬，避免浪費，算法調度的框架如圖2所示。
3 實驗及結果分析
本文在實體路由器上進行測試，實驗組網如圖3所示。
用打流儀構建8條優先級各不相同的流，其中6、7隊列為高優先級隊列，要求快速轉發（EF），2~5隊列為中優先級隊列，要求保障轉發（AF），0、1隊列為低優先級隊列，要求盡力而為地轉發（BE）[7]。發送端g2/1/5流量的發送速率除5隊列外，都固定為100 MB/s（每個優先級報文為100 MB/s），路由器出端口g2/1/6限速為700 MB/s。在上圖構建的通路中，分別執行WRR算法和本文改進的算法，統計在不同算法下各隊列的調度情況。
首先驗證各算法對網絡的適應情況，將隊列5的報文發送速率逐步從100 MB/s增加到200 MB/s，比較各隊列占用帶寬的情況。對WRR算法，設置8隊列的權值分別為3、3、2、2、1、1、1、1。對本文改進的算法，在以上所設基礎上，將8條流量分為三組，第一組包含隊列0和隊列1，第二組為隊列2到5，剩下的隊列分到第三組，同時對第二組限速350 MB/s，結果如圖4所示。可見，當流量增加時，WRR算法對網絡變化缺乏調控能力，而改善算法對超帶寬的流量做了降級處理，在第一組中得以再次調度，等于增加了權值，分配到了更多帶寬，且不會對比其優先級高的隊列造成影響，也不會造成低優先級隊列“餓死”，改進的算法對流量調控起到了一定的作用。
接下來驗證隊列的丟包情況，在擁塞的網絡環境中必然會有丟包。既然丟包是必然的，就要盡量保證優先級高的隊列少丟包。以下比較三種算法的丟包情況。首先構建這樣的網絡環境，在上文的條件基礎上將隊列5報文到達速率不停地增加，觀察該隊列的丟包情況。如圖5所示。改進算法的丟包率遠遠小于WRR算法的丟包率，SP算法丟包率雖然低，但是它是以更多低優先級隊列“餓死”為代價的。
4 結論
本文在現有SP算法和WRR算法的基礎上作出改進，主要是為了實現不同業務的不同服務質量要求，同時提高對網絡變化的自適應性。仿真實驗證明，當某分組到達隊列的速率不斷加快時，通過對超帶寬流量降級，使其更低優先級分組得到再次調度的機會，相當于增加了該隊列的權值，實現了帶寬資源的動態分配。同時，算法還大大減小了網絡丟包率。
參考文獻
[1] 林闖，單志廣，任豐原.計算機網絡的服務質量（QoS）[M].北京：清華大學出版社，2004.
[2] 董民，沈慶國.輪詢類分組調度算法的研究[J].系統仿真學報，2010，22（11）：2593-2596.
[3] 熊李艷，張勝輝.WRR算法在多類別實時數據流中的優化[J].計算機科學與工程，2012，34（7）：35-38.
[4] NIKOLOVA D， BLONDIA C. Bonded deficit robin scheduling for multi-channel networks[J]. Computer Networks，2011，55（15），3503-3516.
[5] Li Miaoyan，Song Bo. Design and implementation of a new queue scheduling scheme in DiffServ networks[C]. The 2nd IEEE International Conference on Advanced Computer ConTrol， 2010：117-122.
[6] ZHANG Y， HARRISON P G. Performance of a priority-weighted round robin mechanism for differentiated service networks[C]. International Conference on Computer Communications and Networks， 2007：1198-1203.
[7] 劉威，楊宗凱.多服務級別帶寬公平分配算法的研究[J].計算機科學，2005，32（1）：37-40.