基于自相似流量水平分級預(yù)測的網(wǎng)絡(luò)隊列調(diào)度算法

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 自相似過程

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

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

隨機過程X的m階聚集過程,i=1,2,…}的定義為

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

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

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

3.2 流量水平分級

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

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

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

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

定義2 個新的隨機變量L1和L2，其中L1為T1時間段上的流量等級，L2為T2時間段上的流量等級，則有

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

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

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

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

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

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

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

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

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

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

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

總的來說，權(quán)值增量Δwi的計算式為

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

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

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

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

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

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

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

4 仿真校驗

4.1 流量等級預(yù)測結(jié)果

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

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

圖3 P-DWRR 算法流程

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

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

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

4.2 性能指標選取

1)分組丟失率

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

2)時延

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

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

仿真實驗采用Matlab 仿真軟件進行，實驗使用的仿真拓撲結(jié)構(gòu)如圖4 所示。

圖4 仿真拓撲結(jié)構(gòu)

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

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

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

圖5 3 個隊列的分組丟失率曲線

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

2)調(diào)度算法排隊時延

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

圖6 3 種算法的排隊時延曲線

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

表4 3 種算法平均排隊時延的比較

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

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

表5 3 種算法排隊時延標準差的比較

5 結(jié)束語

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