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

高仲合，田 碩

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

0 引言

隨著互聯網的不斷發展，網絡擁塞已經成為制約網絡發展和應用的瓶頸問題。擁塞控制成為維持當今網絡正常運行的關鍵手段之一，也是當前研究的熱點問題。

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

1 改進公平性的AQM算法

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

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

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

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

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

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

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

LFED算法主要采用的機制：

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

②算法采用指數函數來計算丟包率。

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

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

2.1 基于負載丟棄概率計算

網絡負載()ρk定義為在一定測量周期內數據包到達速率與服務速率的比值：

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

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

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

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

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

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

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

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

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

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

引入公式（6）是為了實現均勻丟包。

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

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

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

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

2.2 對非響應流的懲罰

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

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

3 仿真實驗與分析

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

網絡拓撲結構采用雙啞鈴型，如圖1所示。

圖1 實驗拓撲

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

（1）仿真場景1

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

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

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

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

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

圖 3 UDP流的吞吐量

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

4 結語

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

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

[2] 鄧偉華, 劉國富. 隨機早期檢測算法的參數研究[J]. 通信技術,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]. 通信技術,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.