魏德賓，沈婷，楊力，戚耀文

（1.南京理工大學(xué)自動(dòng)化學(xué)院，江蘇 南京 210094；2.大連大學(xué)信息工程學(xué)院，遼寧 大連 116622；3.大連大學(xué)通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116622）

1 引言

隨著通信技術(shù)的發(fā)展，網(wǎng)絡(luò)中業(yè)務(wù)種類和業(yè)務(wù)量都在迅速增加，良好的服務(wù)質(zhì)量需要較高的鏈路帶寬來(lái)保證。雖然人們可以通過(guò)提高硬件性能來(lái)增加網(wǎng)絡(luò)帶寬，但是仍然難以滿足日益增長(zhǎng)的用戶需求和避免網(wǎng)絡(luò)中某些路由或交換節(jié)點(diǎn)的擁塞。當(dāng)擁塞發(fā)生時(shí)，如果沒(méi)有有效的隊(duì)列管理和調(diào)度方法，大量的數(shù)據(jù)分組由于不能及時(shí)轉(zhuǎn)發(fā)，積壓在路由器的緩沖區(qū)中。極端情況下會(huì)導(dǎo)致緩沖區(qū)溢出，丟失分組，網(wǎng)絡(luò)將無(wú)法為業(yè)務(wù)提供保障。

隊(duì)列調(diào)度是指路由器以數(shù)據(jù)流的相關(guān)信息為依據(jù)，按照某種規(guī)則從隊(duì)列中選擇待轉(zhuǎn)發(fā)的分組，從而為數(shù)據(jù)流提供公平或有差別的服務(wù)。目前，隊(duì)列調(diào)度算法主要有3 種，分別是簡(jiǎn)單隊(duì)列調(diào)度算法、基于時(shí)間戳的調(diào)度算法和基于輪詢的調(diào)度算法。

簡(jiǎn)單隊(duì)列調(diào)度算法包括先來(lái)先服務(wù)調(diào)度算法、隨機(jī)調(diào)度算法和基于優(yōu)先級(jí)的調(diào)度算法等。先來(lái)先服務(wù)調(diào)度算法按照分組到達(dá)順序確定分組服務(wù)順序，實(shí)現(xiàn)簡(jiǎn)單，管理方便，且最大時(shí)延可由隊(duì)長(zhǎng)決定，但其不能為高優(yōu)先級(jí)的分組提供服務(wù)質(zhì)量（QoS,quality of service）保障，無(wú)法支持區(qū)分服務(wù)。隨機(jī)調(diào)度算法是在所有等待隊(duì)列中隨機(jī)選擇轉(zhuǎn)發(fā)分組，該方法可在某種程度上滿足統(tǒng)計(jì)意義的性能保證，但不能滿足確定性的時(shí)延保證?；趦?yōu)先級(jí)的調(diào)度算法雖然能為高優(yōu)先級(jí)分組提供QoS 保障，但只有當(dāng)高優(yōu)先級(jí)隊(duì)列都為空時(shí)，低優(yōu)先級(jí)隊(duì)列分組才會(huì)被調(diào)度，這會(huì)導(dǎo)致低優(yōu)先級(jí)隊(duì)列的“餓死”現(xiàn)象。

基于時(shí)間戳的調(diào)度算法通過(guò)對(duì)分組記錄開(kāi)始服務(wù)時(shí)間和結(jié)束服務(wù)時(shí)間進(jìn)行排序，選擇具有最小服務(wù)時(shí)間的分組進(jìn)行調(diào)度。這類算法主要是對(duì)Parekh 等[1]提出的最理想的隊(duì)列調(diào)度算法模型——通用處理器共享（GPS,generalized processor sharing）的近似模擬，如加權(quán)公平隊(duì)列（WFQ,weighted fair queuing）、最壞情況加權(quán)公平隊(duì)列（W2FQ,worst-cast weighted fair queuing）和開(kāi)始時(shí)間公平隊(duì)列（STFQ,start time fair queuing）等，具有良好的時(shí)延性能和公平性，但時(shí)間復(fù)雜度高，實(shí)現(xiàn)困難。

基于輪詢的調(diào)度算法是指調(diào)度器輪詢地對(duì)每個(gè)隊(duì)列中的分組進(jìn)行調(diào)度，一次調(diào)度發(fā)送一個(gè)分組，不考慮業(yè)務(wù)的優(yōu)先級(jí)和處理能力，使不同隊(duì)列平等地使用帶寬。該算法實(shí)現(xiàn)簡(jiǎn)單、復(fù)雜度低，適合高速分組網(wǎng)絡(luò)，但不能解決業(yè)務(wù)不同優(yōu)先級(jí)的需求和變長(zhǎng)分組帶來(lái)的不公平性。因此，研究人員提出了一系列改進(jìn)算法，如加權(quán)輪詢（WRR,weighted round robin）、差額輪詢（DRR,deficit round robin）、差額加權(quán)輪詢（DWRR,deficit weighted round robin）[2]等。文獻(xiàn)[3]依據(jù)各隊(duì)列的平均分組到達(dá)率，調(diào)整各隊(duì)列的調(diào)度權(quán)值，提出了 PFWRR（proportion fairness WRR）算法。文獻(xiàn)[4]提出了逐次最小權(quán)值輪詢（SMRR,successive minimal-weight round robin）調(diào)度算法，它能保證在每個(gè)輪次中為每個(gè)活動(dòng)數(shù)據(jù)流提供與本輪次中的最小權(quán)值相當(dāng)?shù)姆?wù)機(jī)會(huì)。文獻(xiàn)[5]綜合考慮網(wǎng)絡(luò)中分組長(zhǎng)度及隊(duì)列權(quán)重，提出了一種改進(jìn)型WRR（EWRR,enhanced WRR）算法。文獻(xiàn)[6]針對(duì)傳統(tǒng)WRR 算法權(quán)值分配和調(diào)度次序固定不變無(wú)法適應(yīng)網(wǎng)絡(luò)負(fù)載加重帶來(lái)的時(shí)延增大問(wèn)題，提出了可變差額加權(quán)輪詢（VDWRR,variable deficit WRR）調(diào)度算法。文獻(xiàn)[7]針對(duì)DWRR 在考慮分組截止時(shí)間時(shí)，對(duì)即將過(guò)期的分組簡(jiǎn)單轉(zhuǎn)發(fā)或直接丟棄，而不是防止違反最后期限的問(wèn)題，提出了一種破產(chǎn)差額加權(quán)輪詢（I-DWRR,insolvency-deficit WRR）調(diào)度算法。文獻(xiàn)[8]針對(duì)傳統(tǒng)WDRR 帶寬利用不充分的問(wèn)題，提出了一種負(fù)差額加權(quán)輪詢（N-DWRR,negative-deficit WRR）算法。文獻(xiàn)[9]針對(duì)大型數(shù)據(jù)中心數(shù)千個(gè)虛擬機(jī)之間實(shí)現(xiàn)負(fù)載平衡的問(wèn)題，提出了一種基于神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)負(fù)載平衡算法。

上述的調(diào)度方法雖然各有優(yōu)勢(shì)，但它們?nèi)狈?duì)網(wǎng)絡(luò)流量特性的考慮。已有的研究表明，局域網(wǎng)、廣域網(wǎng)、萬(wàn)維網(wǎng)等不同通信網(wǎng)絡(luò)的實(shí)際網(wǎng)絡(luò)流量都具有自相似性[10-12]。網(wǎng)絡(luò)業(yè)務(wù)流自相似性的發(fā)現(xiàn)和研究推翻了之前網(wǎng)絡(luò)流量短相關(guān)的基礎(chǔ)假設(shè)。由于自相似性網(wǎng)絡(luò)流量的突發(fā)性更強(qiáng)，持續(xù)時(shí)間更長(zhǎng)，需要更大的網(wǎng)絡(luò)資源和帶寬，容易導(dǎo)致網(wǎng)絡(luò)路由或交換節(jié)點(diǎn)發(fā)生擁塞，這使網(wǎng)絡(luò)流量的統(tǒng)計(jì)特征提取、排隊(duì)性能分析和緩沖區(qū)設(shè)置等均有所變化，同時(shí)也給網(wǎng)絡(luò)交換節(jié)點(diǎn)的隊(duì)列管理和調(diào)度帶來(lái)挑戰(zhàn)。

通過(guò)文獻(xiàn)檢索發(fā)現(xiàn)，針對(duì)上述問(wèn)題，國(guó)內(nèi)外的研究（如文獻(xiàn)[13-15]）都是基于網(wǎng)絡(luò)流量自相似性對(duì)主動(dòng)隊(duì)列管理算法的影響展開(kāi)的，缺少基于網(wǎng)絡(luò)流量自相似性的隊(duì)列調(diào)度算法研究。為此，本文綜合考慮網(wǎng)絡(luò)流量自相似性對(duì)網(wǎng)絡(luò)性能的影響和不同數(shù)據(jù)業(yè)務(wù)的傳輸需求，在傳統(tǒng)差額加權(quán)輪詢調(diào)度算法的基礎(chǔ)上，根據(jù)自相似流量水平分級(jí)預(yù)測(cè)結(jié)果，動(dòng)態(tài)分配權(quán)值和更新服務(wù)量子，并根據(jù)業(yè)務(wù)優(yōu)先級(jí)和隊(duì)列等待時(shí)間對(duì)隊(duì)列進(jìn)行排序，完成調(diào)度，從而達(dá)到減小隊(duì)列時(shí)延、降低分組丟失率的目的。

2 DWRR 隊(duì)列調(diào)度算法

隊(duì)列管理與調(diào)度算法基本原理如圖1 所示。隊(duì)列管理機(jī)制一般位于隊(duì)列輸入端，依靠網(wǎng)絡(luò)節(jié)點(diǎn)主動(dòng)感知緩沖區(qū)的占用率來(lái)管理緩存，在網(wǎng)絡(luò)發(fā)生擁塞時(shí)通過(guò)分組丟失管理隊(duì)列長(zhǎng)度。隊(duì)列調(diào)度機(jī)制則在隊(duì)列的輸出端，按規(guī)則決定下一次要發(fā)送的分組，管理各流之間的帶寬分配。

圖1 隊(duì)列管理與調(diào)度算法基本原理

DWRR 算法為每一個(gè)隊(duì)列分配的權(quán)值是基于字節(jié)數(shù)的，其中主要參數(shù)定義如下。

1)權(quán)值。分配給各隊(duì)列的輸出端口帶寬的比例。

2)差值計(jì)數(shù)器DC。在某一服務(wù)周期內(nèi)，每個(gè)隊(duì)列在每次進(jìn)行調(diào)度服務(wù)時(shí)允許隊(duì)列傳輸?shù)淖止?jié)數(shù)。

3)服務(wù)量子q。用字節(jié)數(shù)表示，正比于其隊(duì)列權(quán)值。調(diào)度器對(duì)某隊(duì)列調(diào)度服務(wù)結(jié)束后，在下一次輪詢到此隊(duì)列時(shí)，將此隊(duì)列差值計(jì)數(shù)器的值增加服務(wù)量子，為此隊(duì)列調(diào)度服務(wù)做準(zhǔn)備。

DWRR 算法針對(duì)網(wǎng)絡(luò)分組大小可變的情況，調(diào)度器依次服務(wù)當(dāng)前非空隊(duì)列，基本調(diào)度過(guò)程如圖2所示，其中陰影部分為已經(jīng)調(diào)度出去的分組。如果此隊(duì)列首部等待發(fā)送分組長(zhǎng)度小于或等于DC 值，則發(fā)送此分組，在差值計(jì)數(shù)器中減掉相應(yīng)的字節(jié)數(shù)，并反復(fù)發(fā)送分組，直到此隊(duì)列首部等待發(fā)送分組長(zhǎng)度大于DC 值，調(diào)度器將移向下一隊(duì)列，此時(shí)剩下的DC值累積到下次輪詢。如果此隊(duì)列為空，DC 值仍有剩余，設(shè)置DC 值為0，調(diào)度器移向下一隊(duì)列。

3 基于流量分級(jí)預(yù)測(cè)的P-DWRR 算法

鑒于現(xiàn)有隊(duì)列調(diào)度算法沒(méi)有考慮網(wǎng)絡(luò)流量的自相似特性，導(dǎo)致數(shù)據(jù)分組時(shí)延和時(shí)延抖動(dòng)增大、分組丟失率增高的問(wèn)題，本文提出 P-DWRR（prediction DWRR）算法，即在原DWRR 算法的基礎(chǔ)上采用基于流量自相似特性的流量分級(jí)預(yù)測(cè)與隊(duì)列優(yōu)先級(jí)的權(quán)值設(shè)定：每隔一定的時(shí)間間隔Δt，根據(jù)流量當(dāng)前的水平等級(jí)預(yù)測(cè)下一個(gè)時(shí)間間隔的流量水平等級(jí)，進(jìn)而依據(jù)流量水平等級(jí)動(dòng)態(tài)地調(diào)整每個(gè)隊(duì)列的權(quán)值和服務(wù)量子，再根據(jù)業(yè)務(wù)優(yōu)先級(jí)和隊(duì)列等待時(shí)間調(diào)整調(diào)度順序。

3.1 自相似過(guò)程

設(shè)X={Xi:i=1,2,…}表示一個(gè)廣義平穩(wěn)離散隨機(jī)過(guò)程，其中，Xi表示第i個(gè)時(shí)間間隔到達(dá)網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)據(jù)分組數(shù)。X具有恒定均值μ和有限方差σ2，且其自相關(guān)函數(shù)為r(k)。

圖2 DWRR 算法的調(diào)度過(guò)程

隨機(jī)過(guò)程X的m階聚集過(guò)程,i=1,2,…}的定義為

對(duì)每個(gè)m，X(m)都定義了一個(gè)廣義平穩(wěn)隨機(jī)過(guò)程，其方差和自相關(guān)函數(shù)分別為V(m)和r(m)(k)。

如果隨機(jī)過(guò)程X的自相關(guān)函數(shù)滿足r(k)=，則稱X為嚴(yán)格二階自相似過(guò)程，且具有 Hurst 參數(shù),0＜β＜1。如果隨機(jī)過(guò)程X的自相關(guān)函數(shù)滿足r(k)～ck-β,k→∞，其中c為正常數(shù)，則稱X為長(zhǎng)相關(guān)過(guò)程。如果隨機(jī)過(guò)程X的m階聚集過(guò)程X(m)的自相關(guān)函數(shù)滿足，k∈Z+，則稱X為漸近二階自相似過(guò)程。

當(dāng)H∈(0.5,1)時(shí)，隨機(jī)過(guò)程具有自相似性，并且H值越大，自相似程度越高。文獻(xiàn)[16]指出，當(dāng)足夠多的、服從重尾分布的ON/OFF 過(guò)程疊加在一起時(shí)，疊加后的過(guò)程具有自相似性，其 Hurst 參數(shù)為，其中α為重尾分布的形狀參數(shù)。

3.2 流量水平分級(jí)

設(shè){X(t),t∈T}是一個(gè)廣義平穩(wěn)隨機(jī)過(guò)程，x(t)是隨機(jī)過(guò)程的一個(gè)樣本函數(shù)。

取2 個(gè)參數(shù)T1,T2＞ 0，在t時(shí)刻，可以使

其中，a表示在最近的過(guò)去[t-T1,t)上觀察到的總流量，b表示在最近的未來(lái)[t,t+T2)上觀察到的總流量，V1和V2表示最近的過(guò)去和最近的未來(lái)的復(fù)合隨機(jī)變量。

假設(shè)隨機(jī)過(guò)程{X(t),t∈T}具有有限的均值和方差，分別為，為了描述流量水平的“高”和“低”，本文將Vk的變化范圍分為以下6 個(gè)級(jí)別

定義2 個(gè)新的隨機(jī)變量L1和L2，其中L1為T1時(shí)間段上的流量等級(jí)，L2為T2時(shí)間段上的流量等級(jí)，則有

其中，k=1,2，Lk是Vk的函數(shù)，即Lk=Lk(Vk)。因此，如果Lk≈ 1，那么流量水平相對(duì)于平均值是“低”；如果Lk≈ 6，那么流量水平相對(duì)于平均值是“高”。

3.3 流量水平條件轉(zhuǎn)移概率估計(jì)

取長(zhǎng)度為ns 的聚合流量序列Xt，將其分為塊，每個(gè)連續(xù)非重疊塊的長(zhǎng)度為T1+T2，并且對(duì)于第j=1,2,…,N個(gè)非重疊塊，計(jì)算長(zhǎng)度為T1,T2上的總流量，分別記為V1,V2。令 ?,?′=1,2,…,6分別為T1,T2上的流量等級(jí)，h?為滿足L1(V1)=?（即T1上的流量等級(jí)為?）的總塊數(shù)，h?′為當(dāng)L1(V1)=?時(shí)，滿足L2(V2)=? ′（即T1的流量等級(jí)為? 條件下，T2的流量等級(jí)為? ′）的總塊數(shù)，則流量水平條件轉(zhuǎn)移概率計(jì)算式為。

3.4 P-DWRR 算法設(shè)計(jì)

P-DWRR 算法基本步驟介紹如下。

Step1根據(jù)n個(gè)隊(duì)列優(yōu)先級(jí)初始化隊(duì)列的權(quán)值w0i(i=1,2,…,n)，若最小權(quán)值不為1，則需將其設(shè)為1，其他權(quán)值同比例縮放，最后歸一化為。

Step2計(jì)算過(guò)去Δt時(shí)間段內(nèi)隊(duì)列i的流量水平的具體等級(jí)?，根據(jù)條件轉(zhuǎn)移概率計(jì)算式Pr{L2=?′|L1=?}，預(yù)測(cè)下一時(shí)間段隊(duì)列i的流量等級(jí)為。

Step3根據(jù)的值將隊(duì)列降序排列，其中ti為隊(duì)列i的等待時(shí)間，依次從高到低進(jìn)行調(diào)度，以平衡隊(duì)列優(yōu)先級(jí)、數(shù)據(jù)突發(fā)程度和隊(duì)間公平性。

Setp4判斷隊(duì)列i是否為空，若為空，則設(shè)DC[i]=0，隊(duì)列i=i+1；若不為空，轉(zhuǎn)到Step5。

Step5根據(jù)計(jì)算出的流量等級(jí)改變權(quán)值，計(jì)算更新后的wi=w0i+Δwi，并將結(jié)果寫入隊(duì)列的權(quán)值表中，其中Δwi的計(jì)算過(guò)程介紹如下。

由式(5)可知，當(dāng)流量等級(jí)小于3 時(shí)，該Δt時(shí)間段內(nèi)流量水平遠(yuǎn)低于其均值，可減少其預(yù)先分配的帶寬，即；當(dāng)流量等級(jí)處于3～4 時(shí)，該Δt時(shí)間段內(nèi)流量水平在均值上下浮動(dòng)，令Δwi=0，即流量等級(jí)處于3～4 時(shí)，不調(diào)整其預(yù)先分配的帶寬；當(dāng)流量等級(jí)大于4 時(shí)，該Δt時(shí)間段內(nèi)流量水平高于其均值，且隨著流量等級(jí)的增大，數(shù)據(jù)突發(fā)程度增高，可將其預(yù)先分配的帶寬增大，其中maxiΔwi表示隊(duì)列i權(quán)值增量的最大閾值。

總的來(lái)說(shuō)，權(quán)值增量Δwi的計(jì)算式為

Step6從隊(duì)列的權(quán)值表讀取隊(duì)列i的新權(quán)值wi，歸一化為。

Step7根據(jù)隊(duì)列i的權(quán)值，分配隊(duì)列i一次可增加的服務(wù)量子，其中C為服務(wù)速率。

Step8判斷當(dāng)前調(diào)度隊(duì)列中的首部分組的字節(jié)數(shù)和差值計(jì)數(shù)器值的關(guān)系。

如果差值計(jì)數(shù)器的值大于隊(duì)列首部分組的字節(jié)數(shù)，則調(diào)度器允許從輸出端口將該首部分組發(fā)送出去，并且差值計(jì)數(shù)器的值減去隊(duì)列首部分組的字節(jié)數(shù)P_size。調(diào)度器在發(fā)送完該分組后，繼續(xù)檢測(cè)當(dāng)前隊(duì)列新的隊(duì)列首部分組的字節(jié)數(shù)與差值計(jì)數(shù)器值的大小情況。如果該隊(duì)列首部分組的字節(jié)數(shù)仍然小于差值計(jì)數(shù)器的值，繼續(xù)發(fā)送該隊(duì)列首部分組，并將差值計(jì)數(shù)器的值減去首部分組的字節(jié)數(shù)，重復(fù)該過(guò)程，直到當(dāng)前隊(duì)列為空，或者當(dāng)前隊(duì)列首部分組的字節(jié)數(shù)大于差值計(jì)數(shù)器值。如果隊(duì)列為空，則轉(zhuǎn)到Step4。

如果差值計(jì)數(shù)器的值小于當(dāng)前隊(duì)列首部分組的字節(jié)數(shù)，將拒絕對(duì)該隊(duì)列進(jìn)行調(diào)度服務(wù)，差值計(jì)數(shù)器將該次未使用的額度保留，并在下一次輪詢到該隊(duì)列時(shí)加入差值計(jì)數(shù)器中使用，然后轉(zhuǎn)到Step4。

Step9如果所有隊(duì)列中都沒(méi)有等待調(diào)度轉(zhuǎn)發(fā)的數(shù)據(jù)分組存在，則調(diào)度算法結(jié)束。

P-DWRR 算法中，計(jì)算均值和方差的時(shí)間復(fù)雜度均為O(n)，隊(duì)列調(diào)度算法的時(shí)間復(fù)雜度為O(n2)。P-DWRR 算法流程如圖3 所示。

4 仿真校驗(yàn)

4.1 流量等級(jí)預(yù)測(cè)結(jié)果

為了得到自相似流量，本文利用100 個(gè)獨(dú)立Pareto 分布的ON/OFF 源疊加模型來(lái)模擬網(wǎng)絡(luò)自相似流，Pareto 分布的累積分布函數(shù)為

其中，α值分別取1.2、1.4 和1.6，由可得其對(duì)應(yīng)的Hurst 參數(shù)值分別為0.9、0.8 和0.7，數(shù)據(jù)分組大小為128 B，ON 持續(xù)時(shí)間均值為50 ms，OFF 持續(xù)時(shí)間均值為10 ms，仿真時(shí)間長(zhǎng)度為10 000 s，取T1=T2=5 s，通過(guò)3.2 節(jié)流量水平分級(jí)的條件轉(zhuǎn)移概率計(jì)算方法，可得表1～表3。

圖3 P-DWRR 算法流程

表1α=1.2時(shí)流量水平條件轉(zhuǎn)移概率

表2 α=1.4時(shí)流量水平條件轉(zhuǎn)移概率

表3 α=1.6時(shí)流量水平條件轉(zhuǎn)移概率

4.2 性能指標(biāo)選取

1)分組丟失率

分組丟失率是指測(cè)試中丟失數(shù)據(jù)分組占所發(fā)送數(shù)據(jù)分組的比例，與數(shù)據(jù)分組長(zhǎng)度和發(fā)送頻率相關(guān)。在隊(duì)列調(diào)度算法中，要求在緩沖區(qū)大小固定的情況下，盡可能降低分組丟失率。

2)時(shí)延

時(shí)延是指數(shù)據(jù)從網(wǎng)絡(luò)的一端傳送到另一端所需的時(shí)間，一般由發(fā)送時(shí)延、傳播時(shí)延、排隊(duì)時(shí)延和處理時(shí)延組成。在隊(duì)列調(diào)度算法中，以排隊(duì)時(shí)延作為衡量指標(biāo)。

4.3 仿真結(jié)果及分析

仿真實(shí)驗(yàn)采用Matlab 仿真軟件進(jìn)行，實(shí)驗(yàn)使用的仿真拓?fù)浣Y(jié)構(gòu)如圖4 所示。

圖4 仿真拓?fù)浣Y(jié)構(gòu)

圖4 中，S1、S2和S3為3 個(gè)源節(jié)點(diǎn)，分別采用100 個(gè)獨(dú)立Pareto 分布的ON/OFF 源疊加模型來(lái)模擬網(wǎng)絡(luò)自相似流，具體參數(shù)與4.1 節(jié)的設(shè)置相同。其中Pareto 分布的α值分別取1.2、1.4 和1.6，對(duì)應(yīng)的隊(duì)列分別為隊(duì)列1、隊(duì)列2 和隊(duì)列3，Hurst 參數(shù)值分別為0.9、0.8、0.7，3 個(gè)隊(duì)列的優(yōu)先級(jí)按由高到低的順序排列，初始權(quán)值設(shè)置為3:2:1。C 為中間節(jié)點(diǎn)，D 為目的節(jié)點(diǎn)，中間節(jié)點(diǎn)服務(wù)速率為5 Mbit/s，源節(jié)點(diǎn)向中間節(jié)點(diǎn)的發(fā)送速率均為1.8 Mbit/s，maxiΔwi=1。

1)調(diào)度算法分組丟失率

當(dāng)DWRR 算法[2]、VDWRR 算法[6]和P-DWRR算法在緩沖區(qū)長(zhǎng)度從5 個(gè)分組變化到100 個(gè)分組時(shí)，分組丟失率曲線如圖5 所示。

圖5 3 個(gè)隊(duì)列的分組丟失率曲線

在隊(duì)列分組丟失率方面，隨著緩沖區(qū)長(zhǎng)度的增加，3 種算法的分組丟失率都呈現(xiàn)出減小趨勢(shì)。其中在同一個(gè)緩沖區(qū)長(zhǎng)度下分組丟失率的不同主要受隊(duì)列權(quán)值設(shè)定的影響，而在同一個(gè)隊(duì)列的不同調(diào)度算法的分組丟失率比較中，P-DWRR 算法的分組丟失率是最低的。以隊(duì)列3 為例，在不同的緩沖區(qū)長(zhǎng)度下，P-DWRR 算法相對(duì)于DWRR算法，平均分組丟失率降低了約7.1%；相對(duì)于VDWRR 算法，平均分組丟失率降低了約4.4%。這是由于本文的P-DWRR 算法根據(jù)優(yōu)先級(jí)和隊(duì)列的流量水平預(yù)測(cè)結(jié)果動(dòng)態(tài)地調(diào)整權(quán)值和調(diào)度順序，把調(diào)度過(guò)程劃分為多個(gè)調(diào)度周期，在一個(gè)調(diào)度周期內(nèi)根據(jù)事先預(yù)測(cè)的隊(duì)列流量突發(fā)程度，設(shè)置一個(gè)合適的權(quán)值比例進(jìn)行調(diào)度，減少隊(duì)列由于流量突發(fā)導(dǎo)致從緩存中溢出的數(shù)據(jù)分組數(shù)量。

2)調(diào)度算法排隊(duì)時(shí)延

DWRR 算法、VDWRR 算法和P-DWRR 算法的排隊(duì)時(shí)延曲線如圖6 所示。為了更好地觀察時(shí)延的變化情況，設(shè)定此處的緩沖區(qū)長(zhǎng)度為100 個(gè)分組，仿真時(shí)間為1 000 s。

圖6 3 種算法的排隊(duì)時(shí)延曲線

3 種算法平均排隊(duì)時(shí)延的比較如表4 所示。從表4 中可以看出，本文的P-DWRR 算法的平均排隊(duì)時(shí)延是最低的。

表4 3 種算法平均排隊(duì)時(shí)延的比較

以隊(duì)列1 為例，P-DWRR 算法比DWRR 算法的排隊(duì)時(shí)延降低了27%左右，比VDWRR 算法的排隊(duì)時(shí)延降低了22%左右。這主要是因?yàn)椴煌琀urst參數(shù)下的流量突發(fā)程度不同，其流量水平在不斷變化，相對(duì)于權(quán)值和調(diào)度順序都不變的DWRR 算法、調(diào)度順序動(dòng)態(tài)調(diào)整的VDWRR 算法而言，本文的P-DWRR 算法權(quán)值的動(dòng)態(tài)設(shè)置利用了預(yù)測(cè)的網(wǎng)絡(luò)流量水平等級(jí)，更能貼合隊(duì)列中實(shí)際的流量水平，同時(shí)因其調(diào)度順序考慮了業(yè)務(wù)優(yōu)先級(jí)和排隊(duì)等待時(shí)間，使其排隊(duì)時(shí)延更低。

3 種算法排隊(duì)時(shí)延標(biāo)準(zhǔn)差的比較如表5 所示。從表5 可以看出，P-DWRR 算法的隊(duì)列時(shí)延變化更平穩(wěn)。

表5 3 種算法排隊(duì)時(shí)延標(biāo)準(zhǔn)差的比較

5 結(jié)束語(yǔ)

本文通過(guò)分析網(wǎng)絡(luò)流量自相似特性對(duì)隊(duì)列調(diào)度算法影響以及不同業(yè)務(wù)的QoS 需求，設(shè)計(jì)了隊(duì)列調(diào)度算法P-DWRR。隊(duì)列調(diào)度算法在業(yè)務(wù)優(yōu)先級(jí)決定隊(duì)列初始權(quán)值的基礎(chǔ)上，根據(jù)每個(gè)隊(duì)列在一定時(shí)間間隔內(nèi)流量等級(jí)的不同進(jìn)行調(diào)整，實(shí)現(xiàn)權(quán)值的動(dòng)態(tài)分配，并對(duì)隊(duì)列的服務(wù)順序進(jìn)行調(diào)整。實(shí)驗(yàn)結(jié)果表明，P-DWRR 算法具有較好的時(shí)延和分組丟失性能，可滿足網(wǎng)絡(luò)不同業(yè)務(wù)類型的數(shù)據(jù)在不同自相似程度下的QoS 要求。