基于兩次丟包策略的主動隊列管理算法研究*

謝立春 張春琴

(浙江工業職業技術學院, 浙江 紹興 312000)

0 前言

隨著網絡的迅速發展，擁塞現象日益嚴重，傳統機制是利用丟包對源端進行擁塞控制。雖然這種被動式隊列管理（Passive Queue Management，PQM）在Internet上得到了廣泛的使用，但存在死鎖、滿隊列和全局同步問題。同時，IETF提出主動式隊列管理（Active Queue Management，AQM）技術[1,2]，即在隊列溢出前進行丟包，使得源端能夠及時對擁塞做出反應，避免死鎖等現象的發生。目前已經存在大量AQM算法。最早提出的是隨機早期檢測

（Random Early Detection，RED）[3-6]，其基本思想是通過監控隊列的平均長度來探測擁塞，當發現擁塞存在時就隨機地丟棄數據包，以此通知源端發生擁塞，使源端在隊列溢出前減小擁塞窗口，降低發送速度，從而緩解網絡擁塞狀況。但是RED算法存在兩個主要缺陷：(i) RED對參數設置很敏感，改變參數對性能影響很大；(ii) 隨著網絡中“流”(Flow)數目的增加，網關的平均隊列長度會逐漸增加。

針對這些問題，研究人員提出了改進方法，包括 ARED、SRED和BLUE算法等。它們是根據網絡中負載的情況對標記/丟棄概率進行動態調整。ARED算法[7]主要思想是根據網絡負載的情況調整最大概率。當平均隊列小于最小閾值，就減小最大概率；當平均隊列大于最大閾值，就增大最大概率。而 SRED 算法[8,9]通過估計網絡中流的個數來調整報文標記/丟棄概率。在SRED中流的個數通過概率統計的方法獲得，所以不需要使用“單流信息”。BLUE算法[10-12]是通過鏈路空閑和緩沖溢出的狀況來調整報文標記/丟棄概率。如果緩沖溢出，就增大概率；如果線路空閑，就減小概率。另外，在PI控制器的基礎上方面又提出了REM(Random Exponential Marking)[13]、PI[14]和 AVQ(Adaptive Virtual Queue)[15]等。

在上述工作基礎上，文章利用兩次丟包策略建立主動隊列管理算法，即通過比較實際隊列長度和等待時間，提出從隊列頭部以及隊中某一位置隨機丟棄數據包。同時，仿真實驗將TDPQW算法與RED算法、DROP-TAIL算法進行對比，分析了有效數據包個數和RTT公平性等性能情況。

1 主動隊列管理算法TDPQW

假設存在一個如圖所示的網絡結構，An為發送數據包的源節點，C為服務節點，其隊長最大閾值為Qmax，實際隊長為q。

圖1 網絡仿真結構示意圖

網絡中經常會出現少數數據流占據大部分帶寬，造成死鎖現象。并且當具有不同RTT的TCP數據流競爭鏈路帶寬時，RTT較小的TCP數據流的擁塞窗口的增長速度會快于RTT大的TCP數據流，從而占有較多的網絡帶寬，造成網絡傳輸中的不公平性現象。RFC2309指出死鎖是由于網絡同步或其它計時作用的結果，從隊列頭部丟棄數據包使得各數據流發現擁塞不一致，就能打破同步，解除網絡死鎖。對此，本文采取了兩次丟包策略，即從隊列頭部丟棄一個數據包，以及隨機產生[1, Qmax-1]之間的隨機值，并丟棄該位置處的數據包。

根據上述思想，這里提出主動管理算法TDPQW（Twice Dropping Packets with Queue length and Waiting time）。TDPQW算法不僅將實際隊長q作為判斷丟包的依據，而且為了避免某種數據流長時間占用帶寬，提出了將實際等待時間w作為另一個判斷依據。同時，考慮到實際流量具有自相似特性，所以這里利用小波變換首先對實際流量進行處理，以此減少長相關所帶來的影響。具體算法如下所述：

(1) 根據式(1)對達到的數據流采用MALLAT算法進行小波變換，通過減少流量的長相關特性，重新獲得重構后的新數據流；

其中，A(j)和D(j)分別為近似系數和小波系數，H為低通濾波器，G為高通濾波器，j為小波分解層次。

(2) 由重構后的新數據流，判斷當前隊列長度q與隊列長度閾值之間的關系，如果q＜Qmin（Qmin為隊長最小閾值），則不進行任何丟包處理，該數據流進入隊列，重復步驟(2)；否則跳轉到步驟(3)；

(3) 如果Qmin＜q＜Qmax，并且w＜Wmax（Wmax為等待時間最大閾值），說明當前網絡有輕度擁塞現象，按照概率Pb隨機丟棄[1, Qmax-1]中某一位置的數據包，該數據流進入隊列，跳轉到步驟(1)；否則跳轉到步驟(4)；

(4) 如果Qmin＜q＜Qmax，并且w≥Wmax，按照概率Pb首先丟棄隊列頭部的一個數據包，然后隨機丟棄[1, Qmax-1]中某一位置的數據包，該數據流進入隊列，跳轉到步驟(1)；否則跳轉到步驟(5)；

(5) 如果 q≥Qmax，直接丟棄隊列頭部的一個數據包以及[1, Qmax-1]中某一位置的數據包，該數據流進入隊列，跳轉到步驟(1)；

(6) 算法結束。

在實際運行中，節點 C的服務率可能因為環境和資源的影響而造成動態變化，所以以下結合M/G/1排隊模型來研究實際隊長q和等待時間w。

2 實際隊長和等待時間的計算

假設系統滿足 M/G/1排隊模型[16-18]，采用先來先服務的策略。數據包到達時如果服務源空閑就立即服務，否則進行排隊等待。服務節點C服務率為μ，數據包平均到達率為p，并且服從一般分布G(t)，則：

令Qt表示t時刻系統到達的數據包，rt表示第t個服務時間段θt到達的數據包個數，{Qt,t≥0}是一個不可約、非齊次MC，易知一步轉移概率pk：

其中，k≥0。

假設P(y)為pk的母函數，當時，是正常返的，存在：

其中，|y|≤1，并且

后續數據包服務時間θn(n=2, 3, 4, …)，并且θn之間相互獨立，根據文獻[19]，利用全概率公式可得其隊列長度q(t)的瞬時分布為：

其中，j≥1。

由于隊列長度q(t)只與數據包個數有關，則：

并且結合θn的獨立同分布性，有：

假設W(t)、U(t)分別代表穩態下數據包的等待時間和逗留時間分布，滿足：

那么在該逗留時間U(t)內到達的數據包個數為[19]：

則：

即：

同時由于逗留時間為等待時間與服務時間之和，所以可得實際等待時間：

即：

3 數學仿真

根據上述穩態下的等待時間的計算方法，這里首先假設服務時間服從1/μ的定長分布。根據式(15)，其數據包的等待時間w1可表示為：

在NS2中建立如圖1仿真網絡拓撲，假設存在3個數據源節點An（n=1, 2, 3），各鏈路容量為15Mbps，延時20ms，緩存大小為50 packets；節點An均為持久性FTP業務源，采用TCP Newreno協議，數據包均為2000Byte。為了驗證TDPQW算法的有效性，這里將RED算法和DROP-TAIL算法進行對比分析。圖2顯示了在50ms內從節點An到節點C的有效數據包個數。從圖中可以看處，DROP-TAIL算法性能較差，而TDPQW算法性能最優。通過數據分析，TDPQW算法比DROP-TAIL算法和RED算法的性能分別提高了10.23%和7.91%。

同時，這里為了驗證算法的公平性，節點A1、A2和A3發送數據包的延時分別為10ms、20ms和30ms。圖3、圖4和圖5分別給出了TDPQW算法、RED算法和DROP-TAIL算法RTT公平性情況。從圖5可以看出RTT存在不公平情況，在RTT為29ms附近時，其節點A3發送的有效數據包明顯超過節點A2，這是由于網絡發生死鎖現象。而從圖3和圖4可以看出，TDPQW算法的公平性要優于RED算法。

圖2 有效數據包個數比較

圖3 TDPQW算法的RTT公平性

圖4 RED算法的RTT公平性

圖5 DROP-TAIL算法的RTT公平性

在文獻[20]中，提出了一種兩次隨機丟包的被動隊列管理算法DropRand2，這里將TDPQW算法和DropRand2算法進行比較。針對于節點A1，在圖6中給出了這兩種算法的RTT公平性比較。從圖6可以看出，本文提出的TDPQW算法在前期具有一定優勢，而在后期劣于DropRand2算法。

圖6 算法TDPQW和DropRand2性能比較

為了深入TDPQW算法中各種影響因素對性能產生的影響，這里假設服務時間服從kμ的k階Erlang分布，其數據包等待時間w2可表示為：

根據式(16)和式(17)得到兩種分布下數據包的等待時間與服務率之間的關系，如圖7所示。從圖7可以看出，整體趨勢上隨著服務率的增加數據包的等待時間是隨之減小，直至平穩狀態。但是當處于相當服務率下時，k階Erlang分布比定長分布下降的速度更快，這說明k階Erlang分布下的數據包等待時間更短，也即是意味著要獲得相同的等待時間，定長分布下所要求系統的服務率更高，此時采用k階Erlang分布能夠獲得更好的性能。

圖7 等待時間與服務率之間關系

4 結論

針對隊列管理中的死鎖和公平性問題，本文采取兩次丟包策略建立了主動隊列管理算法TDPQW。通過比較實際隊列長度和等待時間，提出從隊列頭部以及[1, Qmax-1]中的某一位置隨機丟棄數據包。同時，以M/G/1排隊模型推導了實際隊列長度和等待時間的數學表達式。最后仿真實驗將TDPQW算法與RED算法、DROP-TAIL算法、DropRand2算法進行對比，深入分析了有效數據包個數和RTT公平性情況，結果表明TDPQW算法的性能更優。在后續研究中，可考慮結合REM、PI控制器等建立一套完善的隊列管理模型。

[1]吳春明, 姜明, 朱淼良. 幾種主動式隊列管理算法的比較研究[J]. 電子學報, 2004, 32(3):429-434.

[2]黃磊, 吳春明, 姜明, 張棟. REDu: 一種新的識別并懲罰非適應流的主動式隊列管理算法[J]. 電子學報, 2010, 38(8): 1759-1762.

[3]S. Floyd, V. Jacobson. Random early detection gateways for congestion avoidance[J].IEEE/ACM Transactions on Networking, 1993, 1(4): 397-413.

[4]W. Zhang, L. Tan, G. Peng. Dynamic queue level control of TCP/RED systems in AQM routers[J]. Computers & Electrical Engineering, 2009, 35(1): 59-70.

[5]M. Christiansen, K. Jeffay, D. Ott, F. D. Smith. Tuning RED for Web Traffic[J]. ACM Computer Communication Review, 2000, 30(4): 139-150.

[6]S. Liu, T. Basar, R. Srikant. Exponential-RED: a stabilizing AQM scheme for low-and high-speed TCP protocols[J]. IEEE/ACM Transactions on Networking, 2005, 13(5):1068-1081.

[7]W. Chen, S. H. Yang. The mechanism of adapting RED parameters to TCP traffic[J].Computer Communications, 2009, 32(13): 1525-1530.

[8]Feng-yuan Ren, Chuang Lin, Fu-bao Wang. Stability of RED algorithm: analysis based on nonlinear control theory[J]. Chinese Journal of Computers, 2002, 25(12): 1302-1307.

[9]T. J. Ott, T. V. Lakshman, L. H. Wong. SRED: Stabilized RED[C]. In Proceedings of IEEE INFOCOM, New York, USA: IEEE Communications Society, 1999: 1346-1355.

[10]Wu-chang Feng, K. G. Shin, D. D. Kandlur, et a1. The BLUE active queue management algorithms[J]. IEEE/ACM Trans. on Networking, 2002, 10(4): 513-528.

[11]吳春明, 姜明. SBlue: 一種增強Blue穩定性的主動式隊列管理算法[J]. 通信學報, 2005,26(3): 68-74.

[12]劉偉彥, 孫雁飛, 張順頤, 等. 一種參數自適應的主動隊列管理算法——自適應BLUE[J]. 電子與信息學報, 2009, 31(2): 442-446.

[13]S. Athuraliya, V. H. Li, S. H. Low, Q. Yin. REM: Active queue management[J]. IEEE Network, 2001, 15(3): 48-53.

[14]錢艷平, 李奇. 大時滯網絡自適應預測 PI主動隊列管理算法[J]. 控制與決策, 2006,21(8): 937-940.

[15]S. Kunniyur, R. Srikant. Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management[J]. ACM Computer Communication Review, 2001, 31(4):123-134.

[16]Kim B.. Tail asymptotics for the queue size distribution in a discrete-time Geo/G/1 retrial queue [J]. Queueing System, 2009, 61: 243-254.

[17]朱翼雋, 馮艷剛, 周宗好. 具有Bernoulli反饋的負顧客M/G/1休假排隊系統[J]. 工程數學學報, 2009, 26(2): 369-372.

[18]Tian N., Zhao X., Wang K. The M/M/1 queue with single working vacation[J]. Journal of Information and Management Sciences, 2009, 19: 621-634.

[19]唐應輝, 唐小我. 排隊論[M]. 科學出版社, 2006.

[20]姜文剛, 孫金生, 王執銓. 兩次隨機丟包的被動隊列管理算法[J]. 系統仿真學報, 2011,23(5): 987-997.