摘  要： 在傳統(tǒng)加權(quán)輪詢調(diào)度算法和嚴格優(yōu)先級調(diào)度算法的基礎(chǔ)上，加入令牌桶機制，實現(xiàn)了一種改進算法。在多業(yè)務(wù)并存網(wǎng)絡(luò)中，該算法能夠?qū)Σ煌燃壍臉I(yè)務(wù)實現(xiàn)不同的QoS（服務(wù)質(zhì)量），同時，在業(yè)務(wù)流量發(fā)生變化時，能夠動態(tài)調(diào)整相應(yīng)業(yè)務(wù)的帶寬，且不會對高優(yōu)先級隊列造成影響。仿真實驗表明，該算法可以在一定范圍內(nèi)適應(yīng)網(wǎng)絡(luò)的變化，有效緩解了突發(fā)流量所造成的報文丟包問題，大大提高了網(wǎng)絡(luò)性能。

　　關(guān)鍵詞： 多業(yè)務(wù)網(wǎng)絡(luò)；QoS；動態(tài)調(diào)整；丟包

0 引言

　　隨著科技的飛速發(fā)展，網(wǎng)絡(luò)中的業(yè)務(wù)量也呈爆炸式的增長，而且不同的業(yè)務(wù)在時延、丟包等性能方面也有著不同程度的要求。但網(wǎng)絡(luò)資源總是有限的，在網(wǎng)絡(luò)總帶寬固定的情況下，如果某類業(yè)務(wù)占用的帶寬越多，那么其他業(yè)務(wù)能使用的帶寬就越少，可能會影響其他業(yè)務(wù)的使用。基于此，專家們提出了QoS的概念，針對各種應(yīng)用的不同需求，來對網(wǎng)絡(luò)資源進行合理的規(guī)劃和分配，從而使網(wǎng)絡(luò)資源得到高效利用。

　　隊列調(diào)度機制作為QoS技術(shù)的核心機制之一，一直以來就是研究的熱點。所謂隊列調(diào)度就是在網(wǎng)絡(luò)中傳送業(yè)務(wù)時，如何從多個數(shù)據(jù)包隊列中選擇一個隊列轉(zhuǎn)發(fā)[1]。一個好的隊列調(diào)度算法可以大大提高網(wǎng)絡(luò)的性能，這在帶寬資源擴展速度遠遠落后于網(wǎng)絡(luò)中消息增加速度的今天，重要性不言而喻。

　　目前，已有很多種隊列調(diào)度算法被提出，如嚴格優(yōu)先級隊列調(diào)度（Strict Priority，SP）算法、加權(quán)輪詢調(diào)度（Weighted Round Robin，WRR）算法、加權(quán)差額輪詢調(diào)度（Weighted Deficit Round Robin，WDRR）算法、加權(quán)公平調(diào)度（Weighted Fair Queuing，WFQ）算法等[2-4]，但面對千變?nèi)f化的網(wǎng)絡(luò)環(huán)境，這些算法總是存在著這樣或那樣的缺陷。本文在研究了傳統(tǒng)的各種隊列調(diào)度算法之后，在WRR算法的基礎(chǔ)上加以改進，大大提高了算法的性能，且能在一定范圍內(nèi)適應(yīng)網(wǎng)絡(luò)中流量的變化。

1 幾種典型的隊列調(diào)度算法

　　1.1 SP算法

　　SP算法是針對關(guān)鍵業(yè)務(wù)應(yīng)用設(shè)計的。SP算法嚴格按照優(yōu)先級從高到低的順序調(diào)度隊列，當高優(yōu)先級報文中存在報文時，低優(yōu)先級隊列得不到調(diào)度的機會。這就導(dǎo)致SP算法雖然可以保證高優(yōu)先級隊列的服務(wù)質(zhì)量（Quality of Service，QoS），但是當高優(yōu)先級隊列中始終有報文存在時，低優(yōu)先級隊列中的報文得不到調(diào)度，造成低優(yōu)先級隊列“餓死”現(xiàn)象。

　　1.2 WRR算法

　　WRR算法解決了SP算法中低優(yōu)先級隊列“餓死”的問題。在WRR調(diào)度算法中根據(jù)隊列的權(quán)值來決定轉(zhuǎn)發(fā)報文的數(shù)量。首先設(shè)置一個變量weight記錄隊列的權(quán)值，在進行隊列調(diào)度時，首先判斷weight值是否大于0以及隊列是否非空，若weigdt大于0且隊列非空，則從該隊列中轉(zhuǎn)發(fā)一個分組，并將weight減1，繼續(xù)進行條件判斷，直到weight值等于0或隊列為空，轉(zhuǎn)到下一個隊列開始調(diào)度，當所有隊列都輪詢一遍后，將每個隊列的weight值恢復(fù)為初始值，然后從第一個隊列開始，再次遍歷，不停地重復(fù)以上步驟。

　　1.3 WDRR算法

　　WRR調(diào)度雖然解決了SP調(diào)度中的低優(yōu)先級隊列“餓死”問題，但由于算法以分組為單位進行隊列調(diào)度，當隊列中分組長度不同時，就會導(dǎo)致調(diào)度的公平性問題。由此，提出了以字節(jié)為單位來進行調(diào)度的WDRR調(diào)度。WDRR算法中首先要設(shè)置一個粒度值表示每個權(quán)值所代表的字節(jié)數(shù)，并設(shè)置一個變量DC[i]表示第i個隊列在一次輪詢中可以調(diào)度的字節(jié)數(shù)，初始化為0。每輪調(diào)度隊列之前計算隊列權(quán)值與粒度的乘積加上DC[i]的初值，作為本輪調(diào)度可以轉(zhuǎn)發(fā)的最大字節(jié)數(shù)，隊列調(diào)度過程如下：

　?。?）DC[i]=DC[i]+粒度*權(quán)值；

　?。?）若隊列為空，則只需將DC[i]置0，轉(zhuǎn)到下一隊列開始調(diào)度；

　?。?）若隊列不為空，則比較DC[i]與接下來要調(diào)度的分組長度length的大小，若DC[i]>=length，則轉(zhuǎn)發(fā)該分組，更新DC[i]的值（DC[i]=DC[i]-length），并轉(zhuǎn)向（2），否則轉(zhuǎn)到下一個隊列繼續(xù)調(diào)度；

　　（4）若一輪調(diào)度完成，則轉(zhuǎn)到第一個隊列，轉(zhuǎn)到（2），繼續(xù)調(diào)度。

　　DWRR調(diào)度雖然解決了WRR調(diào)度中的公平性問題，但仍然存在如下一系列的缺點[5-6]：

　?。?）不能體現(xiàn)高優(yōu)先級隊列的絕對優(yōu)先級地位。

　?。?）分組時延得不到保證，當某一分組錯過了本次調(diào)度時，它將不得不等待一個輪詢周期的時間，尤其是當這種情況出現(xiàn)在高優(yōu)先級隊列時，會造成嚴重后果。

　　（3）各隊列分配到的權(quán)值是固定的，當網(wǎng)絡(luò)情況發(fā)生變化時，不能很好地適應(yīng)，例如，高優(yōu)先級報文突然增多，但由于分配的帶寬已經(jīng)固定了，多余的報文將得不到轉(zhuǎn)發(fā)，只能丟棄。

2 改進算法描述

　　本文針對以上算法存在的缺點，提出一種改進的隊列調(diào)度算法，經(jīng)驗證，改進算法很好地解決了以上問題。其基本流程如下：

　　（1）報文入普通8隊列。報文根據(jù)dscp值映射出本地優(yōu)先級，根據(jù)本地優(yōu)先級進入相應(yīng)的8隊列。

　?。?）對隊列進行分組。將QoS需求近似的隊列分在同一組，每一組以組中優(yōu)先級最低隊列的優(yōu)先級作為本組中所有隊列的優(yōu)先級（避免優(yōu)先級重復(fù)）。為了保證高優(yōu)先級隊列的絕對優(yōu)先地位，不同組之間的隊列按照SP算法進行調(diào)度，保證高優(yōu)先級隊列優(yōu)先轉(zhuǎn)發(fā)。同一組內(nèi)的各隊列之間進行DWRR調(diào)度，保證QoS需求近似隊列的相對公平性。

　　（3）從8隊列（QueueLoop[8]）映射到64隊列（FlowLoop[64]）。本設(shè)計提供一套模板，該模板包含64個隊列，分8種優(yōu)先級，每個隊列都設(shè)定好了對應(yīng)優(yōu)先級值（priority）。首先從QueueLoop[1]開始，以此與FlowLoop進行匹配，若優(yōu)先級相同且FlowLoop還未被其他隊列占用，則匹配成功，進行下一條QueueLoop的匹配工作，否則繼續(xù)匹配，直到匹配成功為止，流程如圖1。

　?。?）隊列調(diào)度。如上所述，分組內(nèi)進行DWRR調(diào)度，分組間進行SP調(diào)度。為了使低優(yōu)先級隊列不被“餓死”，本算法引入了令牌桶機制對隊列和整個分組進行限速，對每個隊列的超帶寬流量進行降級處理，將優(yōu)先級降為最低，并加入優(yōu)先級最低的分組與組中原有隊列按權(quán)值共享剩余帶寬。這樣當隊列出現(xiàn)突發(fā)流量時，可以有效減小突發(fā)報文的丟包率，并且在低優(yōu)先級隊列空閑時可以自動占用剩余帶寬，避免浪費，算法調(diào)度的框架如圖2所示。

3 實驗及結(jié)果分析

　　本文在實體路由器上進行測試，實驗組網(wǎng)如圖3所示。

　　用打流儀構(gòu)建8條優(yōu)先級各不相同的流，其中6、7隊列為高優(yōu)先級隊列，要求快速轉(zhuǎn)發(fā)（EF），2~5隊列為中優(yōu)先級隊列，要求保障轉(zhuǎn)發(fā)（AF），0、1隊列為低優(yōu)先級隊列，要求盡力而為地轉(zhuǎn)發(fā)（BE）[7]。發(fā)送端g2/1/5流量的發(fā)送速率除5隊列外，都固定為100 MB/s（每個優(yōu)先級報文為100 MB/s），路由器出端口g2/1/6限速為700 MB/s。在上圖構(gòu)建的通路中，分別執(zhí)行WRR算法和本文改進的算法，統(tǒng)計在不同算法下各隊列的調(diào)度情況。

　　首先驗證各算法對網(wǎng)絡(luò)的適應(yīng)情況，將隊列5的報文發(fā)送速率逐步從100 MB/s增加到200 MB/s，比較各隊列占用帶寬的情況。對WRR算法，設(shè)置8隊列的權(quán)值分別為3、3、2、2、1、1、1、1。對本文改進的算法，在以上所設(shè)基礎(chǔ)上，將8條流量分為三組，第一組包含隊列0和隊列1，第二組為隊列2到5，剩下的隊列分到第三組，同時對第二組限速350 MB/s，結(jié)果如圖4所示。可見，當流量增加時，WRR算法對網(wǎng)絡(luò)變化缺乏調(diào)控能力，而改善算法對超帶寬的流量做了降級處理，在第一組中得以再次調(diào)度，等于增加了權(quán)值，分配到了更多帶寬，且不會對比其優(yōu)先級高的隊列造成影響，也不會造成低優(yōu)先級隊列“餓死”，改進的算法對流量調(diào)控起到了一定的作用。

　　接下來驗證隊列的丟包情況，在擁塞的網(wǎng)絡(luò)環(huán)境中必然會有丟包。既然丟包是必然的，就要盡量保證優(yōu)先級高的隊列少丟包。以下比較三種算法的丟包情況。首先構(gòu)建這樣的網(wǎng)絡(luò)環(huán)境，在上文的條件基礎(chǔ)上將隊列5報文到達速率不停地增加，觀察該隊列的丟包情況。如圖5所示。改進算法的丟包率遠遠小于WRR算法的丟包率，SP算法丟包率雖然低，但是它是以更多低優(yōu)先級隊列“餓死”為代價的。

4 結(jié)論

　　本文在現(xiàn)有SP算法和WRR算法的基礎(chǔ)上作出改進，主要是為了實現(xiàn)不同業(yè)務(wù)的不同服務(wù)質(zhì)量要求，同時提高對網(wǎng)絡(luò)變化的自適應(yīng)性。仿真實驗證明，當某分組到達隊列的速率不斷加快時，通過對超帶寬流量降級，使其更低優(yōu)先級分組得到再次調(diào)度的機會，相當于增加了該隊列的權(quán)值，實現(xiàn)了帶寬資源的動態(tài)分配。同時，算法還大大減小了網(wǎng)絡(luò)丟包率。

　　參考文獻

　　[1] 林闖，單志廣，任豐原.計算機網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS）[M].北京：清華大學(xué)出版社，2004.

　　[2] 董民，沈慶國.輪詢類分組調(diào)度算法的研究[J].系統(tǒng)仿真學(xué)報，2010，22（11）：2593-2596.

　　[3] 熊李艷，張勝輝.WRR算法在多類別實時數(shù)據(jù)流中的優(yōu)化[J].計算機科學(xué)與工程，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] 劉威，楊宗凱.多服務(wù)級別帶寬公平分配算法的研究[J].計算機科學(xué)，2005，32（1）：37-40.