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