一種基于負載的公平性主動隊列管理算法

高仲合，田 碩

（曲阜師范大學 計算機科學學院，山東 日照 276826）

0 引言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，網(wǎng)絡擁塞已經(jīng)成為制約網(wǎng)絡發(fā)展和應用的瓶頸問題。擁塞控制成為維持當今網(wǎng)絡正常運行的關(guān)鍵手段之一，也是當前研究的熱點問題。

主動隊列管理（AQM，Active Queue Management）是基于路由器擁塞控制領(lǐng)域的研究熱點。其中隨機早期檢測（RED，Random Early Detection）[1]算法是主動隊列管理算法中最著名的一個。但是由于 RED算法存在對參數(shù)設置敏感和不能保證公平性等問題，所以該算法并沒有在實際中得到廣泛應用，后來很多學者對 RED算法進行了大量地研究和改進[2-4]。

1 改進公平性的AQM算法

針對RED算法在公平性方面存在不足，一些公平性AQM算法被提出，例如FRED[5]，CSFQ[6]，CHOKe[7]，F(xiàn)ERED[8]等。

FRED（Flow RED）通過考察某個流當前隊列緩存占用量來決定該流的分組丟棄概率。由于對不同的流采用了不同的丟棄概率，因此提高了 RED的公平性，但是算法需要在路由器維持流的狀態(tài)信息，降低了算法的效率，并存在可擴展問題。

核心無狀態(tài)公平隊列（CSFQ，Core Stateless Fair Queue）通過一些措施來實現(xiàn)最大-最小公平原則。并通過采用 DPS技術(shù)來實現(xiàn)核心無狀態(tài)。算法在邊緣路由器的狀態(tài)寫入需要代價開銷。

CHOKe是一種完全無狀態(tài)的近似公平隊列管理算法。CHOKe懲罰非響應流的機制是：在檢測到擁塞發(fā)生時，將到達分組與從當前隊列中選出的1個分組進行比較，如果2個分組屬于同一個流，則對兩個分組進行丟棄，否則，只對到達分組進行RED處理。雖然CHOKe能以較低的代價提高網(wǎng)絡帶寬公平性，但是算法對參數(shù)設置敏感。

FERED利用了IP報頭中生存時間（TTL，Time To Live）字段信息來增強算法的公平性，算法實現(xiàn)簡單，并且無需在路由器保存流信息。但是算法存在的不足是當經(jīng)過較多路由器跳數(shù)的數(shù)據(jù)包卻具有較小往返時延（RTT，Round-Trip Time）時可能會加重TCP的RTT不公平性。

2 基于負載的公平性AQM算法

基于對現(xiàn)有的AQM算法的研究，提出一種新的公平性主動隊列管理算法（LFED）。

LFED算法主要采用的機制：

①綜合考慮負載和平均對長的情況作為擁塞指標。

②算法采用指數(shù)函數(shù)來計算丟包率。

③算法借鑒 CHOKe中的方法來實現(xiàn)對非響應流的懲罰。

這3個機制主要是解決RED算法利用平均隊長帶來的響應時間和穩(wěn)定性之間的矛盾，并避免 RED算法非線性丟包率公式帶來的不連續(xù)丟包現(xiàn)象和 RED算法無法解決帶寬公平問題。

2.1 基于負載丟棄概率計算

網(wǎng)絡負載()ρk定義為在一定測量周期內(nèi)數(shù)據(jù)包到達速率與服務速率的比值：

Rin(k)，Rout(k)分別代表包到達速率和服務速率，k表示第k個采樣時刻。

為了計算負載，首先要估計數(shù)據(jù)包到達速率的大小。因為TCP流具有多尺度突發(fā)特性，在大時間尺度上具有長相關(guān)性，因而速率具有可預測性。LFED算法采用指數(shù)加權(quán)滑動平均（EWMA，Exponentially Weighted Moving Average）[9]來計算數(shù)據(jù)包的到達速率：

L(k+1)表示是第k+1個包的長度，δT(K+1)表示第k+1個包與第k個包到達時間間隔。K反映2個包到達時間的相關(guān)度。

為了避免算法對時間間隔的敏感性。使用負載的平均值來計算低保率。平均負載計算如下：

ρavg(k ),ρ(k)分別代表 k時刻的平均和瞬時負載，w為平均權(quán)值。

由于平均隊長具有抑制短暫突發(fā)流量的優(yōu)點，算法也采用隊長作為擁塞指標之一。平均隊長計算如下：

qavg(tn) ， wq， q (tn)分別為平均隊列長度，加權(quán)系數(shù)和瞬時隊列長度。

在實際計算中，又引入了隊列剩余長度這一重要概念。當網(wǎng)絡負載相同時，擁塞程度主要與隊列剩余長度相關(guān)，因為在負載和隊列長度相同的情況下，當隊列中剩余長度越小時，對應的擁塞程度就越高。

LFED算法采用指數(shù)函數(shù)作為丟包率函數(shù)，函數(shù)的最大值為1，最小值為0，算法的丟包率公式如下：

其中，qavg、qtotal、 ρavg(k)、qtotal- qavg、count分別代表平均隊長、路由器中隊列總長度、平均負載、隊列剩余長度和上次丟棄分組后收到的分組數(shù)。

引入公式（6）是為了實現(xiàn)均勻丟包。

通過新的丟包率公式可得出：

①當負載平衡時，丟包率與平均隊長和隊列剩余長度的比值有關(guān)，比值越大，則丟包率越大。

②當負載加重時，如果平均隊長與隊列剩余長度的比值較小，則不會引起過大的丟包率。

③當負載減輕時，只有平均隊長與隊列剩余長度的比值較大時才會產(chǎn)生較大的丟包率。

2.2 對非響應流的懲罰

為了提高LFED算法的公平性，對非響應流進行有效懲罰，同時降低算法的復雜度。借鑒CHOKe算法對非響應流的懲罰機制。

當有一個分組到達時，LFED就隨機從當前隊列中選取一個分組與到達分組進行比較；如果它們屬于同一個流，則同時丟棄這兩個分組，否則，把選取的分組放回隊列，只對到達的分組進行概率丟棄，分組丟棄概率計算見公式（5）。

3 仿真實驗與分析

通過NS2仿真平臺，對RED，CHOKe和LFED進行性能比較。

網(wǎng)絡拓撲結(jié)構(gòu)采用雙啞鈴型，如圖1所示。

圖1 實驗拓撲

在圖1中，S1-Sn為發(fā)送節(jié)點，D1-Dn為接收節(jié)點。每個發(fā)送節(jié)點和接收節(jié)點與路由器之間的帶寬為10 Mb/s，時延為5 ms。2個路由器之間的瓶頸帶寬是1 Mb/s，時延為2 ms，RED參數(shù)設置：minth=20，maxth=60，maxp=0.1，wq=0.002，LFED中K=0.3，CHOKe相關(guān)參數(shù)設置與RED相同，緩沖區(qū)隊列長度為120。仿真時間60 s。

（1）仿真場景1

仿真實驗假設R1與R2之間的TCP連接數(shù)從10增加到100（步長為10）。

仿真結(jié)果如圖 2。圖 2(a)是瞬時隊列長度的標準差，它反映了隊列變化程度。從圖2(a)可以看出，LFED算法下的瞬時隊列標準差遠小于RED和CHOKe，說明LFED算法隊列長度的穩(wěn)定性較好，隊列抖動較小。圖2(b)是該鏈路分組被丟棄的概率，從圖中可以看出，LFED算法的丟包率要小于RED和CHOKe，其中圖2（b）的縱坐標數(shù)量級為10-3。

圖 2 瓶頸鏈路下三種算法的性能比較

（2）仿真場景2（UDP流吞吐量）

仿真實驗設計30條TCP流，S1-S30為發(fā)送端，D1-D30為接收端。1條UDP流，S31為發(fā)送端，D31為接收端。TCP應用固定發(fā)送速度（0.2 Mb/s）的FTP型數(shù)據(jù)包，UDP應用CBR型數(shù)據(jù)包，CBR包在0.5 Mb/s到10 Mb/s間變化，所有包大小均為1 Kb。TCP最大窗口為200。仿真結(jié)果如圖3。

圖 3 UDP流的吞吐量

從圖3看出，在LFED算法下，UDP流的吞吐量遠遠小于RED算法下的情況，并且也小于CHOKe算法下的情況。雖然LFED算法采用對非響應流的懲罰機制和CHOKe算法相同，但是由于LFED算法結(jié)合負載和平均隊長對網(wǎng)絡擁塞進行更為準確的判斷，并采用了指數(shù)函數(shù)來計算丟包率，使得LFED算法表現(xiàn)稍好于CHOKe算法。

4 結(jié)語

在分析研究多個主動隊列管理算法的基礎(chǔ)上，提出一種新的基于負載的公平性主動隊列管理算法。該算法結(jié)合了負載和平均隊長作為擁塞指標，設計了指數(shù)函數(shù)作為新的丟包率函數(shù)，并借鑒CHOKe中的方法來實現(xiàn)對非響應流的懲罰。仿真結(jié)果表明，LFED算法有效地保證了隊列穩(wěn)定性和魯棒性，并在公平性方面效果良好。

[1] FLOYD S, JACOBSON V. Random Early Detection Gateways for Congestion Avoidance[J]. IEEE/ACM Transactions on Networking,1993, 1(04): 397-413.

[2] 鄧偉華, 劉國富. 隨機早期檢測算法的參數(shù)研究[J]. 通信技術(shù),2009, 42 (06): 65-67.

[3] MANFREDI S, BERNARDO D M, GAROFALO F. Design Validation and Experimental Testing of a Robust AQM Control[J]. Control Engineering Practice, 2009, 17(03): 394-407.

[4] 趙文波, 劉群. 基于鏈路資源改進 RED算法研究[J]. 通信技術(shù),2009, 42(02): 124-126.

[5] LIN D, MORRIS R. Dynamics of Random Early Detection[J]. ACM SIGCOMM Computer Communication Review, 1997, 27(04): 127-137.

[6] STOICA I, SHENKER S, ZHANG H. Core-stateless Fair Queue:Achieving Approximately Fair Bandwith Allocation in High Speed Networks[J]. IEEE/ACM Transactions on Networking, 2003,11(01): 33-46.

[7] PAN R, PRABHAKAR B, PSOUNIS K. CHOKe: A Stateless Active Queue Management Scheme for Approximating Fair Bandwith Allocation[C].USA: IEEE Computer Society, 2000: 942- 951.

[8] 武航星, 慕德俊, 龔賢武, 等. FERED: 公平性增強的RED算法[J].計算機科學, 2009, 36(02): 122-124.

[9] STOICA I, SHENKER S, ZHANG H. Core-Stateless Fair Queuing: a Scalable Architecture to Approximate Fair Bandwidth Allocations in High Speed Networks[J]. IEEE/ACM Transactions on Networking, 2003, 11 (01): 33-46.