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

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

2、 朱培棟(國防科學技術(shù)大學 計算機學院,湖南 長沙 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摘 要:主動隊列管理是一個非常活躍的研究領(lǐng)域,相對于丟尾算法,AQM(active queue management)能夠提供更短的平均隊列延遲和更高的帶寬利用率.雖然PI(proportional integral)主動隊列管理算法的性能優(yōu)于RED(random early detection)算法

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

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

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

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

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

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

13、PI在這方面進行了努力,下面具體介紹API算法的理論基礎(chǔ)和實現(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è)計2.1 根據(jù)丟失率推測鏈路負載信息文獻11分析了TCP的吞吐量,得到如下表達式:(3)其中,T的單位為報文/秒,R是RTT大小,是連接超時值,p是報文丟失率.一般12,則式(3)變形為(4)其中.如果當前TCP連接的數(shù)目為N,每

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

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

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

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

18、R2DnDmD130M30M10ms30MFig.3 Simulation topology圖3 模擬拓撲本文使用NS-213模擬器對API算法進行了驗證,同時與PI和PIP算法進行了比較.模擬拓撲如圖3所示,其中S1Sn為發(fā)送節(jié)點,D1Dn為接收節(jié)點,R1,R2為路由器,SiR1和R2Di的傳輸延遲為10ms,50ms之間平均分布的隨機延遲,R1R2的鏈路構(gòu)成瓶頸.R1上分別運行API,PI和PIP算法.目標隊列長度設(shè)置為25個報文.實驗中,TCP使用Reno,報文大小為1000字節(jié);CBR報文大小為500字節(jié),報文發(fā)送間隔為0.5s;HTTP短連接的平均頁面請求大小為10K字節(jié).實驗1.實

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

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

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

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

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

24、數(shù)是Rmax,由于網(wǎng)絡(luò)環(huán)境不同,很難知道Rmax的數(shù)值,因此可以使用一定的策略探測值,從而使API能夠適應(yīng)更加復雜的網(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