多業(yè)務(wù)網(wǎng)絡(luò)中一種新隊(duì)列調(diào)度算法的研究

張春風(fēng)，錢(qián)學(xué)榮

（南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003）

0 引言

隨著科技的飛速發(fā)展，網(wǎng)絡(luò)中的業(yè)務(wù)量也呈爆炸式的增長(zhǎng)，而且不同的業(yè)務(wù)在時(shí)延、丟包等性能方面也有著不同程度的要求。但網(wǎng)絡(luò)資源總是有限的，在網(wǎng)絡(luò)總帶寬固定的情況下，如果某類(lèi)業(yè)務(wù)占用的帶寬越多，那么其他業(yè)務(wù)能使用的帶寬就越少，可能會(huì)影響其他業(yè)務(wù)的使用?；诖?，專(zhuān)家們提出了QoS的概念，針對(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)輪詢(xún)調(diào)度（Weighted Round Robin，WRR）算法、加權(quán)差額輪詢(xú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ì)列都輪詢(xún)一遍后，將每個(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ì)列在一次輪詢(xún)中可以調(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)值；

（2）若隊(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)度；

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

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

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

（2）分組時(shí)延得不到保證，當(dāng)某一分組錯(cuò)過(guò)了本次調(diào)度時(shí)，它將不得不等待一個(gè)輪詢(xún)周期的時(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)題。其基本流程如下：

（1）報(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。

圖1 報(bào)文入隊(duì)列流程圖

（4）隊(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所示。

圖算法調(diào)度原理圖

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

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

圖3 實(shí)驗(yàn)組網(wǎng)圖

用打流儀構(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)控起到了一定的作用。

圖4 帶寬占用曲線

接下來(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à)的。

圖5 丟包率曲線

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ò)丟包率。

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

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

[3]熊李艷，張勝輝.WRR算法在多類(lèi)別實(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 2ndIEEE International Conference on Advanced Computer Con-Trol，2010：117-122.

[6]ZHANG Y，HARRISON P G.Performance of a priorityweighted 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.