謝立春 張春琴

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

0 前言

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

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

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

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

1 主動(dòng)隊(duì)列管理算法TDPQW

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

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

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

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

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

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

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

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

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

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

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

在實(shí)際運(yùn)行中，節(jié)點(diǎn) C的服務(wù)率可能因?yàn)榄h(huán)境和資源的影響而造成動(dòng)態(tài)變化，所以以下結(jié)合M/G/1排隊(duì)模型來(lái)研究實(shí)際隊(duì)長(zhǎng)q和等待時(shí)間w。

2 實(shí)際隊(duì)長(zhǎng)和等待時(shí)間的計(jì)算

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

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

其中，k≥0。

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

其中，|y|≤1，并且

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

其中，j≥1。

由于隊(duì)列長(zhǎng)度q(t)只與數(shù)據(jù)包個(gè)數(shù)有關(guān)，則：

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

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

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

則：

即：

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

即：

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

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

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

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

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

圖3 TDPQW算法的RTT公平性

圖4 RED算法的RTT公平性

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

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

圖6 算法TDPQW和DropRand2性能比較

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

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

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

4 結(jié)論

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

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

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

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

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