基于自相似流量水平分級預測的網絡隊列調度算法

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

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

1 引言

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

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

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

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

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

上述的調度方法雖然各有優勢，但它們缺乏對網絡流量特性的考慮。已有的研究表明，局域網、廣域網、萬維網等不同通信網絡的實際網絡流量都具有自相似性[10-12]。網絡業務流自相似性的發現和研究推翻了之前網絡流量短相關的基礎假設。由于自相似性網絡流量的突發性更強，持續時間更長，需要更大的網絡資源和帶寬，容易導致網絡路由或交換節點發生擁塞，這使網絡流量的統計特征提取、排隊性能分析和緩沖區設置等均有所變化，同時也給網絡交換節點的隊列管理和調度帶來挑戰。

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

2 DWRR 隊列調度算法

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

圖1 隊列管理與調度算法基本原理

DWRR 算法為每一個隊列分配的權值是基于字節數的，其中主要參數定義如下。

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

2)差值計數器DC。在某一服務周期內，每個隊列在每次進行調度服務時允許隊列傳輸的字節數。

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

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

3 基于流量分級預測的P-DWRR 算法

鑒于現有隊列調度算法沒有考慮網絡流量的自相似特性，導致數據分組時延和時延抖動增大、分組丟失率增高的問題，本文提出 P-DWRR（prediction DWRR）算法，即在原DWRR 算法的基礎上采用基于流量自相似特性的流量分級預測與隊列優先級的權值設定：每隔一定的時間間隔Δt，根據流量當前的水平等級預測下一個時間間隔的流量水平等級，進而依據流量水平等級動態地調整每個隊列的權值和服務量子，再根據業務優先級和隊列等待時間調整調度順序。

3.1 自相似過程

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

圖2 DWRR 算法的調度過程

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

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

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

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

3.2 流量水平分級

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

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

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

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

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

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

3.3 流量水平條件轉移概率估計

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

3.4 P-DWRR 算法設計

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

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

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

Step3根據的值將隊列降序排列，其中ti為隊列i的等待時間，依次從高到低進行調度，以平衡隊列優先級、數據突發程度和隊間公平性。

Setp4判斷隊列i是否為空，若為空，則設DC[i]=0，隊列i=i+1；若不為空，轉到Step5。

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

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

總的來說，權值增量Δwi的計算式為

Step6從隊列的權值表讀取隊列i的新權值wi，歸一化為。

Step7根據隊列i的權值，分配隊列i一次可增加的服務量子，其中C為服務速率。

Step8判斷當前調度隊列中的首部分組的字節數和差值計數器值的關系。

如果差值計數器的值大于隊列首部分組的字節數，則調度器允許從輸出端口將該首部分組發送出去，并且差值計數器的值減去隊列首部分組的字節數P_size。調度器在發送完該分組后，繼續檢測當前隊列新的隊列首部分組的字節數與差值計數器值的大小情況。如果該隊列首部分組的字節數仍然小于差值計數器的值，繼續發送該隊列首部分組，并將差值計數器的值減去首部分組的字節數，重復該過程，直到當前隊列為空，或者當前隊列首部分組的字節數大于差值計數器值。如果隊列為空，則轉到Step4。

如果差值計數器的值小于當前隊列首部分組的字節數，將拒絕對該隊列進行調度服務，差值計數器將該次未使用的額度保留，并在下一次輪詢到該隊列時加入差值計數器中使用，然后轉到Step4。

Step9如果所有隊列中都沒有等待調度轉發的數據分組存在，則調度算法結束。

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

4 仿真校驗

4.1 流量等級預測結果

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

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

圖3 P-DWRR 算法流程

表1α=1.2時流量水平條件轉移概率

表2 α=1.4時流量水平條件轉移概率

表3 α=1.6時流量水平條件轉移概率

4.2 性能指標選取

1)分組丟失率

分組丟失率是指測試中丟失數據分組占所發送數據分組的比例，與數據分組長度和發送頻率相關。在隊列調度算法中，要求在緩沖區大小固定的情況下，盡可能降低分組丟失率。

2)時延

時延是指數據從網絡的一端傳送到另一端所需的時間，一般由發送時延、傳播時延、排隊時延和處理時延組成。在隊列調度算法中，以排隊時延作為衡量指標。

4.3 仿真結果及分析

仿真實驗采用Matlab 仿真軟件進行，實驗使用的仿真拓撲結構如圖4 所示。

圖4 仿真拓撲結構

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

1)調度算法分組丟失率

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

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

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

2)調度算法排隊時延

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

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

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

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

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

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

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

5 結束語

本文通過分析網絡流量自相似特性對隊列調度算法影響以及不同業務的QoS 需求，設計了隊列調度算法P-DWRR。隊列調度算法在業務優先級決定隊列初始權值的基礎上，根據每個隊列在一定時間間隔內流量等級的不同進行調整，實現權值的動態分配，并對隊列的服務順序進行調整。實驗結果表明，P-DWRR 算法具有較好的時延和分組丟失性能，可滿足網絡不同業務類型的數據在不同自相似程度下的QoS 要求。