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

謝立春 張春琴

(浙江工業(yè)職業(yè)技術(shù)學(xué)院, 浙江 紹興 312000)

0 前言

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

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

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

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

1 主動隊列管理算法TDPQW

假設(shè)存在一個如圖所示的網(wǎng)絡(luò)結(jié)構(gòu)，An為發(fā)送數(shù)據(jù)包的源節(jié)點，C為服務(wù)節(jié)點，其隊長最大閾值為Qmax，實際隊長為q。

圖1 網(wǎng)絡(luò)仿真結(jié)構(gòu)示意圖

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

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

(1) 根據(jù)式(1)對達(dá)到的數(shù)據(jù)流采用MALLAT算法進(jìn)行小波變換，通過減少流量的長相關(guān)特性，重新獲得重構(gòu)后的新數(shù)據(jù)流；

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

(2) 由重構(gòu)后的新數(shù)據(jù)流，判斷當(dāng)前隊列長度q與隊列長度閾值之間的關(guān)系，如果q＜Qmin（Qmin為隊長最小閾值），則不進(jìn)行任何丟包處理，該數(shù)據(jù)流進(jìn)入隊列，重復(fù)步驟(2)；否則跳轉(zhuǎn)到步驟(3)；

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

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

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

(6) 算法結(jié)束。

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

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

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

令Qt表示t時刻系統(tǒng)到達(dá)的數(shù)據(jù)包，rt表示第t個服務(wù)時間段θt到達(dá)的數(shù)據(jù)包個數(shù)，{Qt,t≥0}是一個不可約、非齊次MC，易知一步轉(zhuǎn)移概率pk：

其中，k≥0。

假設(shè)P(y)為pk的母函數(shù)，當(dāng)時，是正常返的，存在：

其中，|y|≤1，并且

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

其中，j≥1。

由于隊列長度q(t)只與數(shù)據(jù)包個數(shù)有關(guān)，則：

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

假設(shè)W(t)、U(t)分別代表穩(wěn)態(tài)下數(shù)據(jù)包的等待時間和逗留時間分布，滿足：

那么在該逗留時間U(t)內(nèi)到達(dá)的數(shù)據(jù)包個數(shù)為[19]：

則：

即：

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

即：

3 數(shù)學(xué)仿真

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

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

同時，這里為了驗證算法的公平性，節(jié)點A1、A2和A3發(fā)送數(shù)據(jù)包的延時分別為10ms、20ms和30ms。圖3、圖4和圖5分別給出了TDPQW算法、RED算法和DROP-TAIL算法RTT公平性情況。從圖5可以看出RTT存在不公平情況，在RTT為29ms附近時，其節(jié)點A3發(fā)送的有效數(shù)據(jù)包明顯超過節(jié)點A2，這是由于網(wǎng)絡(luò)發(fā)生死鎖現(xiàn)象。而從圖3和圖4可以看出，TDPQW算法的公平性要優(yōu)于RED算法。

圖2 有效數(shù)據(jù)包個數(shù)比較

圖3 TDPQW算法的RTT公平性

圖4 RED算法的RTT公平性

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

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

圖6 算法TDPQW和DropRand2性能比較

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

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

圖7 等待時間與服務(wù)率之間關(guān)系

4 結(jié)論

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

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

[2]黃磊, 吳春明, 姜明, 張棟. REDu: 一種新的識別并懲罰非適應(yīng)流的主動式隊列管理算法[J]. 電子學(xué)報, 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穩(wěn)定性的主動式隊列管理算法[J]. 通信學(xué)報, 2005,26(3): 68-74.

[12]劉偉彥, 孫雁飛, 張順頤, 等. 一種參數(shù)自適應(yīng)的主動隊列管理算法——自適應(yīng)BLUE[J]. 電子與信息學(xué)報, 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]錢艷平, 李奇. 大時滯網(wǎng)絡(luò)自適應(yīng)預(yù)測 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反饋的負(fù)顧客M/G/1休假排隊系統(tǒng)[J]. 工程數(shù)學(xué)學(xué)報, 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]唐應(yīng)輝, 唐小我. 排隊論[M]. 科學(xué)出版社, 2006.

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