自適應(yīng)PI主動(dòng)隊(duì)列管理算法（

1、盧錫城 等:自適應(yīng)PI主動(dòng)隊(duì)列管理算法909自適應(yīng)PI主動(dòng)隊(duì)列管理算法*Supported by the National Natural Science Foundation of China under Grant Nos.90104001, 90204005 (國(guó)家自然科學(xué)基金)作者簡(jiǎn)介: 盧錫城(1946),男,江蘇靖江人,教授,博士生導(dǎo)師,中國(guó)工程院院士,主要研究領(lǐng)域?yàn)橄冗M(jìn)網(wǎng)絡(luò)技術(shù),高性能計(jì)算,并行與分布處理;張明杰(1974),男,博士生,主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)服務(wù)質(zhì)量,擁塞控制;朱培棟(1971),男,博士,副教授,主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)路由,組播技術(shù),高性能路由器.盧錫城, 張明杰+,

2、 朱培棟(國(guó)防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)An Adaptive PI Active Queue Management AlgorithmLU Xi-Cheng, ZHANG Ming-Jie+, ZHU Pei-Dong(School of Computer, National University of Defense Technology, Changsha 410073, China)+ Corresponding author: Phn: +86-10-66241219, E-mail: canicula, Received 2003-11-17; Accep

3、ted 2004-06-10Lu XC, Zhang MJ, Zhu PD. An adaptive PI active queue management algorithm. Journal of Software, 2005, 16(5):903-910. DOI: 10.1360/jos160903Abstract:Active queue management (AQM) is a very active research area in networking. Compared with drop-tail, AQM can provide smaller average queue

4、 delay and higher bandwidth utilization. Although the performance of proportional integral (PI) controller is superior to that of random early detection (RED), its convergence speed is slow. This paper proposes an adaptive proportional integral (API) algorithm based on the original PI. API obtains l

5、oad information by measuring the current packet-dropping rate, then sets PI parameters accordingly. Verified by using NS-2 simulations, API can achieve faster convergence speed and smaller queue oscillation than PI and PIP (proportional integral based series compensation and position feedback compen

6、sation) which is an improved algorithm of PI.Key words:active queue management; proportional integral; adaptive; convergence speed; queue oscillation摘 要:主動(dòng)隊(duì)列管理是一個(gè)非?；钴S的研究領(lǐng)域,相對(duì)于丟尾算法,AQM(active queue management)能夠提供更短的平均隊(duì)列延遲和更高的帶寬利用率.雖然PI(proportional integral)主動(dòng)隊(duì)列管理算法的性能優(yōu)于RED(random early detection)算法

7、,但是PI算法的收斂速度比較慢.以PI算法為基礎(chǔ)提出了一種自適應(yīng)PI算法API(adaptive proportional integral).API通過實(shí)時(shí)測(cè)量鏈路的報(bào)文丟失率,獲得當(dāng)前的負(fù)載信息,然后動(dòng)態(tài)設(shè)置PI算法中的有關(guān)參數(shù).通過ns-2模擬表明,相對(duì)于PI及其改進(jìn)算法PIP(proportional integral based series compensation and position feedback compensation),API具有更快的收斂速度和更小的隊(duì)列抖動(dòng).關(guān)鍵詞:主動(dòng)隊(duì)列管理;成比例積分;自適應(yīng);收斂速度;隊(duì)列抖動(dòng)中圖法分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼: A因特

8、網(wǎng)中大量存在的傳輸層協(xié)議是TCP,如何針對(duì)TCP設(shè)計(jì)緩沖管理算法一直是人們研究的重點(diǎn).由于丟尾算法的缺點(diǎn),AQM(active queue management)1成為近幾年來?yè)砣刂祁I(lǐng)域中的研究熱點(diǎn).Floyd提出的RED(random early detection) 2算法根據(jù)平均隊(duì)列長(zhǎng)度計(jì)算報(bào)文丟棄概率.自從RED提出以來,人們從理論和實(shí)驗(yàn)兩方面對(duì)其性能進(jìn)行了大量研究,同時(shí)對(duì)RED進(jìn)行了許多改進(jìn).研究表明,RED算法的性能和配置參數(shù)緊密相關(guān),不正確的參數(shù)配置導(dǎo)致很大的隊(duì)列抖動(dòng)3.從端系統(tǒng)的角度看,文獻(xiàn)4通過實(shí)驗(yàn)表明,相對(duì)于其他主動(dòng)隊(duì)列管理算法,自適應(yīng)RED5算法對(duì)Web的性能改進(jìn)最小.

9、還需要指出的是,即使是自適應(yīng)RED算法,它也是基于一種直覺的合理性,缺乏嚴(yán)謹(jǐn)?shù)目茖W(xué)論證.除了RED之外,研究人員還提出了自適應(yīng)虛緩沖6和REM7主動(dòng)隊(duì)列管理算法.這兩種基于優(yōu)化的方法更多地關(guān)注系統(tǒng)的穩(wěn)態(tài)特性,而不是隊(duì)列的瞬態(tài)性能.文獻(xiàn)8建立了TCP/AQM控制論模型,從而可以使用控制理論研究主動(dòng)隊(duì)列管理算法.Hollot對(duì)建立的控制論模型進(jìn)行了合理的線性化處理,提出了PI(proportional integral)算法9.PI使用瞬時(shí)隊(duì)列長(zhǎng)度計(jì)算報(bào)文丟棄概率,這一點(diǎn)和RED不同,理論分析和模擬都表明,PI算法比RED算法具有更小的隊(duì)列抖動(dòng),從而在保證高帶寬利用率的前提下,為端用戶提供更小的延

10、遲抖動(dòng).但是PI算法中,參數(shù)是固定設(shè)置的,固定的參數(shù)設(shè)置導(dǎo)致PI算法在較小的目標(biāo)隊(duì)列長(zhǎng)度情況下收斂速度較慢,為了改進(jìn)PI算法的收斂特性,文獻(xiàn)10提出了PIP(proportional integral based series compensation and position feedback compensation)算法,PIP算法在PI算法的基礎(chǔ)上引入了位置反饋補(bǔ)償,使得系統(tǒng)具有更快的收斂速度.本文針對(duì)PI算法的缺點(diǎn),提出了自適應(yīng)PI算法API(adaptive proportional integral),API算法通過實(shí)時(shí)測(cè)量鏈路的報(bào)文丟失率,動(dòng)態(tài)地調(diào)整PI算法的配置參數(shù),從而保證

11、PI算法具有更快的收斂速度和更小的隊(duì)列抖動(dòng).本文第1節(jié)介紹TCP/AQM控制理論模型.第2節(jié)闡述API算法設(shè)計(jì).第3節(jié)通過實(shí)驗(yàn)驗(yàn)證API算法的有效性.第4節(jié)總結(jié)全文并指出下一步的工作.1 TCP/AQM控制理論模型以控制論為基礎(chǔ)的TCP/AQM(PI)系統(tǒng),如圖1所示.在圖1中,q0是目標(biāo)隊(duì)列長(zhǎng)度,p是報(bào)文丟失率.如果系統(tǒng)的負(fù)載為N,連接的RTT(round-trip time)為R,則PI模塊可以表示為(t,T是待確定的參數(shù)),AQM dynamic模塊可以表示為,其中,.整個(gè)系統(tǒng)的開環(huán)傳遞函數(shù)為(1)文獻(xiàn)9給出了當(dāng)時(shí)系統(tǒng)的穩(wěn)定性條件,PI算法根據(jù)式(2)計(jì)算報(bào)文丟棄概率.(2)在式(2)中

12、,p(k)是在k時(shí)刻的報(bào)文丟棄概率,q(k)是在k時(shí)刻的瞬時(shí)隊(duì)列長(zhǎng)度,a,b是t和T的函數(shù).在PI算法中,參數(shù)a,b是固定配置好的,不能隨網(wǎng)絡(luò)動(dòng)態(tài)變化而靈活設(shè)置,因而導(dǎo)致PI算法收斂較慢,這一點(diǎn)在文獻(xiàn)10中通過實(shí)驗(yàn)進(jìn)行了驗(yàn)證,本文的實(shí)驗(yàn)也證明了這一點(diǎn).PIP10算法在PI基礎(chǔ)上引入了位置反饋補(bǔ)償,如圖2所示.在圖2中,要求|G2()Gc()|>>1.PIP算法得到的開環(huán)帶寬比PI算法的要大,從而獲得更快的收斂速度.雖然PIP優(yōu)于PI算法,但是PIP算法的穩(wěn)定性條件也是固定的.如果PI算法的參數(shù)能夠隨著網(wǎng)絡(luò)的動(dòng)態(tài)變化而靈活設(shè)置,那么就可以取得更好的隊(duì)列特性,本文提出的自適應(yīng)PI算法A

13、PI在這方面進(jìn)行了努力,下面具體介紹API算法的理論基礎(chǔ)和實(shí)現(xiàn).AQMdynamicPIqq0p0pdp-G1(s)qqG2(s)Gc(s)-Fig.1 TCP/AQM control system (PI) Fig.2 TCP/AQM control system (PIP)圖1 TCP/AQM控制系統(tǒng)(PI) 圖2 TCP/AQM控制系統(tǒng)(PIP)2 API算法設(shè)計(jì)2.1 根據(jù)丟失率推測(cè)鏈路負(fù)載信息文獻(xiàn)11分析了TCP的吞吐量,得到如下表達(dá)式:(3)其中,T的單位為報(bào)文/秒,R是RTT大小,是連接超時(shí)值,p是報(bào)文丟失率.一般12,則式(3)變形為(4)其中.如果當(dāng)前TCP連接的數(shù)目為N,每

14、條連接的RTT為R,鏈路帶寬為C,那么由式(4)可知,從而可以導(dǎo)出N,R和p的關(guān)系式:(5)其中.由式(5)可知,給定N,R,可以確定鏈路的丟失率p;反過來,知道鏈路的丟失率p,可以推測(cè)負(fù)載N和R.定義集合,是所有丟失率為p時(shí)的N,R組合.2.2 調(diào)整參數(shù)定理這一節(jié)介紹API算法參數(shù)調(diào)整的理論依據(jù).定理1. 當(dāng)系統(tǒng)負(fù)載為N,RTT為R時(shí),如果,那么系統(tǒng)(1)是穩(wěn)定的.證明:整個(gè)系統(tǒng)的開環(huán)傳遞函數(shù),則系統(tǒng)的頻率響應(yīng)為,.相角頻率特性:.因?yàn)?所以.由Nyquist穩(wěn)定性判據(jù)可知系統(tǒng)是穩(wěn)定的.定理2. 對(duì)于N,R變化的系統(tǒng)而言,當(dāng)丟失率為p時(shí),取, ,則,系統(tǒng)穩(wěn)定.證明:對(duì)于,令,則,系統(tǒng)的頻率響

15、應(yīng)為,=1.相角頻率特性:.由Nyquist穩(wěn)定性判據(jù)可知系統(tǒng)穩(wěn)定.定理3. 對(duì)于N,R變化的系統(tǒng)而言,當(dāng)報(bào)文丟失率為p,最大的RTT為時(shí),取, ,則,系統(tǒng)穩(wěn)定.證明:由定理2可知,只需證明.取,由定理2可知,因?yàn)?定理3說明了為什么API算法比PI和PIP算法具有更大的開環(huán)帶寬.例如,當(dāng)C=3750,時(shí),PI給出的開環(huán)帶寬為0.66(rad/s),PIP算法給出的開環(huán)帶寬為1.7(rad/s),定理3給出的開環(huán)帶寬為3.57(rad/s).開環(huán)帶寬越大,系統(tǒng)的收斂速度越快.當(dāng)時(shí),由PI和PIP算法給出的穩(wěn)定性條件可能使系統(tǒng)不穩(wěn)定,如果按定理3進(jìn)行參數(shù)調(diào)整,仍可以使系統(tǒng)處于穩(wěn)定狀態(tài).2.3 A

16、PI算法設(shè)計(jì)根據(jù)定理3我們?cè)O(shè)計(jì)了自適應(yīng)算法API,API由兩部分組成:初始化部分和參數(shù)調(diào)節(jié)部分,下面分別加以介紹.2.3.1 API算法初始化過程initAPIAPI維護(hù)兩個(gè)簡(jiǎn)單的數(shù)組、,每一個(gè)元素與一個(gè)丟失率p相對(duì)應(yīng).初始化過程就是初始化這兩個(gè)數(shù)組.初始化過程如下:for (i=0;i<30;i+)p=i/100;if (p=0)p=0.001;根據(jù)定理3計(jì)算,;在initAPI過程中,p表示當(dāng)前的報(bào)文丟失率.最大的報(bào)文丟失率設(shè)置為30%.網(wǎng)絡(luò)管理員也可以根據(jù)具體的操作環(huán)境來設(shè)置最大的報(bào)文丟棄概率.2.3.2 API參數(shù)調(diào)整過程updateAPI每隔adaptiveInterval時(shí)間

17、:計(jì)算當(dāng)前的報(bào)文丟失率p;index=(int)(p´100);更新PI算法中對(duì)應(yīng)的系數(shù)a,b.在updateAPI過程中,adaptiveInterval是算法的執(zhí)行周期,具體實(shí)現(xiàn)時(shí)取1s.PI算法中參數(shù)a,b與t,T的關(guān)系是(S是PI算法采樣隊(duì)列長(zhǎng)度的頻率),.關(guān)于丟失率p的計(jì)算可以有兩種方法:指數(shù)平滑均值(EWMA)法.k是加權(quán)因子,P是上一時(shí)間間隔(長(zhǎng)度為adaptiveInterval)的報(bào)文丟失率.加權(quán)因子越大,算法對(duì)負(fù)載變化的響應(yīng)速度就越快.直接使用上一時(shí)間間隔的報(bào)文丟失率.,相當(dāng)于k=1時(shí)的EWMA方法.updateAPI使用了第2種方法.3 模擬驗(yàn)證S1SmSnR1

18、R2DnDmD130M30M10ms30MFig.3 Simulation topology圖3 模擬拓?fù)浔疚氖褂肗S-213模擬器對(duì)API算法進(jìn)行了驗(yàn)證,同時(shí)與PI和PIP算法進(jìn)行了比較.模擬拓?fù)淙鐖D3所示,其中S1Sn為發(fā)送節(jié)點(diǎn),D1Dn為接收節(jié)點(diǎn),R1,R2為路由器,SiR1和R2Di的傳輸延遲為10ms,50ms之間平均分布的隨機(jī)延遲,R1R2的鏈路構(gòu)成瓶頸.R1上分別運(yùn)行API,PI和PIP算法.目標(biāo)隊(duì)列長(zhǎng)度設(shè)置為25個(gè)報(bào)文.實(shí)驗(yàn)中,TCP使用Reno,報(bào)文大小為1000字節(jié);CBR報(bào)文大小為500字節(jié),報(bào)文發(fā)送間隔為0.5s;HTTP短連接的平均頁(yè)面請(qǐng)求大小為10K字節(jié).實(shí)驗(yàn)1.實(shí)

19、驗(yàn)1比較了3種算法的響應(yīng)速度.實(shí)驗(yàn)過程:在0s10s之間啟動(dòng)200條FTP連接;然后在50s60s之間再啟動(dòng)200條FTP連接.總的模擬過程持續(xù)100s.瞬時(shí)隊(duì)列長(zhǎng)度隨時(shí)間變化的過程如圖4(a)和圖4(b)所示.從圖4(a)可以看出,當(dāng)FTP連接數(shù)從0增加到200時(shí),PI算法的隊(duì)列長(zhǎng)度從0攀升到最大值,然后緩慢收斂到目標(biāo)隊(duì)列長(zhǎng)度.當(dāng)FTP連接數(shù)目在50s增加時(shí), PI算法的隊(duì)列長(zhǎng)度又會(huì)出現(xiàn)較大的抖動(dòng).從圖4(b)可以看出,PIP算法的隊(duì)列長(zhǎng)度能夠很快地收斂到目標(biāo)值,在隊(duì)列長(zhǎng)度穩(wěn)定之后,PIP和PI算法具有相似的抖動(dòng).API不僅具有較快的收斂速度,而且具有比PIP更小的隊(duì)列抖動(dòng). (a) Que

20、ue evolution of Exp 1 (PI vs. API) (b) Queue evolution of Exp 1 (PIP vs. API) (a) 實(shí)驗(yàn)1隊(duì)列變化(PI vs. API) (b) 實(shí)驗(yàn)1隊(duì)列變化(PIP vs. API)Fig.4 Simulation results of Exp.1圖4 實(shí)驗(yàn)1模擬結(jié)果實(shí)驗(yàn)2.實(shí)驗(yàn)2驗(yàn)證了API在重負(fù)載情況下的性能.實(shí)驗(yàn)過程:在0s10s之間啟動(dòng)500條TCP連接.模擬結(jié)果如圖5(a)和圖5(b)所示.從圖5(a)可以看出,在重負(fù)載情況下,PI算法的收斂速度很慢;從圖5(b)可以看出,雖然PIP算法的收斂速度比PI算法快,但是

21、在10s30s之間,PIP算法出現(xiàn)了隊(duì)列下溢現(xiàn)象.在重負(fù)載情況下,API算法的性能不僅明顯優(yōu)于PI,而且優(yōu)于PIP算法.實(shí)驗(yàn)3.實(shí)驗(yàn)3評(píng)估了API算法在混合連接類型情況下的性能.具體的模擬過程:在0s10s之間,啟動(dòng)150條FTP連接,在150s時(shí)停止這些連接;在20s30s之間,啟動(dòng)100條CBR連接,在120s時(shí)停止這些連接;在40s50s時(shí)啟動(dòng)200條HTTP連接;在60s70s之間再啟動(dòng)70條FTP連接,這些連接在140s時(shí)停止;在80s90s之間啟動(dòng)100條CBR連接,在160s時(shí)停止這些連接.模擬結(jié)果如圖6(a)和圖6(b)所示.從實(shí)驗(yàn)3可以看出,在有短連接(HTTP)和UDP(C

22、BR)連接存在的情況下,API算法仍然具有較快的收斂速度和較小的隊(duì)列長(zhǎng)度抖動(dòng),性能優(yōu)于PI和PIP算法. (a) Queue evolution of Exp 2 (PI vs. API) (b) Queue evolution of Exp 2 (PIP vs. API) (a) 實(shí)驗(yàn)2隊(duì)列變化(PI vs. API) (b) 實(shí)驗(yàn)2隊(duì)列變化(PIP vs. API)Fig.5 Simulation results of Exp.2圖5 實(shí)驗(yàn)2模擬結(jié)果 (a) Queue evolution of Exp 3 (PI vs. API) (b) Queue evolution of Exp 3

23、 (PIP vs. API) (a) 實(shí)驗(yàn)3隊(duì)列變化(PI vs. API) (b) 實(shí)驗(yàn)3隊(duì)列變化(PIP vs. API)Fig.6 Simulation results of Exp.3圖6 實(shí)驗(yàn)3模擬結(jié)果綜合以上3個(gè)實(shí)驗(yàn)可以看出,與PI和PIP算法相比,API具有更好的隊(duì)列特性,包括更快的收斂速度和更小的隊(duì)列抖動(dòng).4 結(jié)束語(yǔ)及下一步工作本文基于PI算法提出了一種自適應(yīng)的主動(dòng)隊(duì)列管理算法API,通過分析和模擬表明,API算法能夠適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境,與PI和PIP算法相比,具有更快的收斂速度和更小的隊(duì)列抖動(dòng).文中通過丟失率估計(jì)負(fù)載的方法具有一定的普適性.在API算法中,唯一需要配置的參

24、數(shù)是Rmax,由于網(wǎng)絡(luò)環(huán)境不同,很難知道Rmax的數(shù)值,因此可以使用一定的策略探測(cè)值,從而使API能夠適應(yīng)更加復(fù)雜的網(wǎng)絡(luò)環(huán)境,這是我們下一步要做的工作.References:1 Braden B, Clark D, Crowcroft J, Davie B, Deering S, Estrin D, Floyd S, Jacobson V, Minshall G, Partridge C, Peterson L, Ramakrishnan K, Shenker S, Wroclawski J, Zhang L. Recommendations on queue management and c

25、ongestion avoidance in the Internet. RFC2309, Internet Engineering Task Force, 1998.2 Floyd S, Jacobson V. Random early detection gateways for congestion avoidance. IEEE/ACM Trans. on Networking, 1993, 1(4):397-413.3 Hollot CV, Misra V, Towsley D, Gong W. A control theoretic analysis of RED. In: Amm

26、ar M, ed. Proc. of the IEEE INFOCOM. Anchorage: IEEE Communications Society, 2001. 1510-1519.4 Le L, Aikat J, Jeffay K, Smith FD. The effects of active queue management on Web performance. In: Proc. of the ACM SIGCOMM 2003. Karlsruhe, 2003. 265-276. /jeffay/papers/SIGCOMM-03.pdf5

27、 Floyd S, Gummadi R, Shenker S. Adaptive RED: An algorithm for increasing the robustness of REDs active queue management. 2001. /floyd6 Kunniyur S, Srikant R. A time scale decomposition approach to adaptive ECN marking. In: Ammar M, ed. Proc. of the IEEE INFOCOM. Anchorage: IEEE Co

28、mmunications Society, 2001. 1330-1339.7 Athuraliya S, Low S, Li VH, Yin QH. REM: Active queue management. IEEE Network, 2001,15(3):48-53.8 Misra V, Gong WB, Towsley D. Fluid-Based analysis of a network of AQM routers supporting TCP flows with an application to RED. In: Proc. of the ACM SIGCOMM 2000. Stockholm, 2000. 151-16