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

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

0 引言

　　隨著科技的飛速發(fā)展,，網(wǎng)絡(luò)中的業(yè)務(wù)量也呈爆炸式的增長(zhǎng)，而且不同的業(yè)務(wù)在時(shí)延,、丟包等性能方面也有著不同程度的要求,。但網(wǎng)絡(luò)資源總是有限的，在網(wǎng)絡(luò)總帶寬固定的情況下,，如果某類業(yè)務(wù)占用的帶寬越多,，那么其他業(yè)務(wù)能使用的帶寬就越少，可能會(huì)影響其他業(yè)務(wù)的使用,?；诖耍瑢＜覀兲岢隽薗oS的概念,，針對(duì)各種應(yīng)用的不同需求,，來(lái)對(duì)網(wǎng)絡(luò)資源進(jìn)行合理的規(guī)劃和分配，從而使網(wǎng)絡(luò)資源得到高效利用。

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

　　目前,，已有很多種隊(duì)列調(diào)度算法被提出，如嚴(yán)格優(yōu)先級(jí)隊(duì)列調(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]，但面對(duì)千變?nèi)f化的網(wǎng)絡(luò)環(huán)境,，這些算法總是存在著這樣或那樣的缺陷,。本文在研究了傳統(tǒng)的各種隊(duì)列調(diào)度算法之后，在WRR算法的基礎(chǔ)上加以改進(jìn),，大大提高了算法的性能,，且能在一定范圍內(nèi)適應(yīng)網(wǎng)絡(luò)中流量的變化。

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

　　1.1 SP算法

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

　　1.2 WRR算法

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

　　1.3 WDRR算法

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

　　（1）DC[i]=DC[i]+粒度*權(quán)值,；

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

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

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

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

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

　　（2）分組時(shí)延得不到保證,，當(dāng)某一分組錯(cuò)過(guò)了本次調(diào)度時(shí),，它將不得不等待一個(gè)輪詢周期的時(shí)間，尤其是當(dāng)這種情況出現(xiàn)在高優(yōu)先級(jí)隊(duì)列時(shí),，會(huì)造成嚴(yán)重后果,。

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

2 改進(jìn)算法描述

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

　?。?）報(bào)文入普通8隊(duì)列。報(bào)文根據(jù)dscp值映射出本地優(yōu)先級(jí),，根據(jù)本地優(yōu)先級(jí)進(jìn)入相應(yīng)的8隊(duì)列,。

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

　　本文在實(shí)體路由器上進(jìn)行測(cè)試,，實(shí)驗(yàn)組網(wǎng)如圖3所示,。

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

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

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

4 結(jié)論

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

　　參考文獻(xiàn)

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

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

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