幾種典型AQM算法在高速網(wǎng)絡(luò)下的比較研究

蘇聰

【摘要】 本文分析和比較幾種典型的主動(dòng)隊(duì)列管理（Active Queue Management， AQM）算法在高速網(wǎng)絡(luò)中的性能，經(jīng)仿真實(shí)驗(yàn)發(fā)現(xiàn)這幾種AQM算法在高速網(wǎng)絡(luò)中的性能都不理想，主要表現(xiàn)為：鏈路的帶寬利用率不高，全局同步現(xiàn)象嚴(yán)重，隊(duì)列長(zhǎng)度不能維持在一定值附近。這些現(xiàn)象說(shuō)明了現(xiàn)有的AQM算法在高速網(wǎng)絡(luò)下不能很好地滿足QoS（quantity of serve）的要求，改進(jìn)AQM算法勢(shì)在必行。

【關(guān)鍵詞】 AQM算法 NS仿真模擬

一、引言

當(dāng)前針對(duì)高速網(wǎng)絡(luò)的擁塞控制研究中，主要針對(duì)源端算法或基于反饋的機(jī)制而進(jìn)行，在中間節(jié)點(diǎn)方面研究得較少。而對(duì)于源端算法來(lái)說(shuō)，如果沒(méi)有中間節(jié)點(diǎn)的支持，很難達(dá)到理想的性能。因此，有必要考察各種典型的AQM算法結(jié)合源端算法在高速網(wǎng)絡(luò)下的性能。

二、算法的評(píng)價(jià)指標(biāo)

目前，路由器中大多數(shù)是基于“棄尾”（Drop-Tail）的隊(duì)列管理，RED[1]算法或RED的變種作為可選配置在路由器上，但常常不被使用。AQM的部署步伐之所以慢是由于缺乏對(duì)各種算法較為詳細(xì)的、一致的客觀評(píng)價(jià)標(biāo)準(zhǔn)，大多數(shù)AQM評(píng)價(jià)工作是為了新算法的有效性目的而進(jìn)行的。通常對(duì)AQM算法性能的評(píng)價(jià)主要包括：

1、隊(duì)列的穩(wěn)定性：AQM的目的是控制路由器中的隊(duì)列長(zhǎng)度，因此算法穩(wěn)定與否直接關(guān)系到路由器中隊(duì)列長(zhǎng)度的變化情況，而隊(duì)列長(zhǎng)度的變化又直接影響到網(wǎng)絡(luò)的服務(wù)質(zhì)量。一方面，對(duì)于一個(gè)特定的TCP連接，由于其傳播延遲是固定的，因此該連接傳輸時(shí)延和時(shí)延抖動(dòng)的大小主要是由路由器中的隊(duì)列長(zhǎng)度所決定的；另一方面，路由器中的隊(duì)列長(zhǎng)度直接關(guān)系到其輸出鏈路的帶寬利用率，只有當(dāng)隊(duì)列長(zhǎng)度不為零時(shí)才能保證網(wǎng)絡(luò)帶寬的有效利用。因此一個(gè)好的AQM算法應(yīng)能使隊(duì)列長(zhǎng)度穩(wěn)定在一個(gè)較低的值附近。

2、高效的帶寬利用率：隊(duì)列長(zhǎng)度不為零時(shí)可以保證路由器輸出鏈路的帶寬利用率，但輸入鏈路的帶寬利用率要靠丟包率來(lái)保證，對(duì)于一個(gè)特定的TCP連接，若丟包率過(guò)高，將會(huì)導(dǎo)致不必要的重傳，從而降低帶寬的利用率。因此，一個(gè)好的AQM算法應(yīng)該既要保證隊(duì)列長(zhǎng)度的穩(wěn)定性，又要保證高效的帶寬利用率。

3、公平性：AQM的目標(biāo)之一是改進(jìn)Drop-Tail隊(duì)列的公平性。REC2309強(qiáng)調(diào)：路由器的隊(duì)列機(jī)制應(yīng)保護(hù)適應(yīng)流，對(duì)非適應(yīng)流進(jìn)行有效的鑒別和限制。

4、算法的復(fù)雜程度：算法的復(fù)雜程度是決定AQM算法是否實(shí)用的一個(gè)關(guān)鍵因素。近年來(lái)，隨著網(wǎng)絡(luò)帶寬的迅速增加，路由器的處理速度成為影響網(wǎng)絡(luò)性能的一個(gè)主要因素，因此應(yīng)盡可能降低AQM算法的復(fù)雜程度以減小路由器的計(jì)算量。由于骨干路由器的負(fù)荷相當(dāng)重，瓶頸鏈路非常繁忙，因此一個(gè)簡(jiǎn)單高效的擁塞檢測(cè)方法以及丟棄策略對(duì)于算法的利用及有效推廣是至關(guān)重要的。

5、對(duì)網(wǎng)絡(luò)狀態(tài)變化的適應(yīng)能力：具有較強(qiáng)的魯棒性，即對(duì)環(huán)境變化不敏感。Internet的復(fù)雜性和異構(gòu)性決定了網(wǎng)絡(luò)狀態(tài)的變化是難以避免的，因此一個(gè)好的AQM算法應(yīng)該對(duì)網(wǎng)絡(luò)狀態(tài)的變化具有很好的適應(yīng)能力，在網(wǎng)絡(luò)負(fù)載、傳輸時(shí)延等因素發(fā)生變化時(shí)，仍可實(shí)現(xiàn)好的傳輸性能。

下面，筆者將從帶寬利用率、丟包率、隊(duì)列長(zhǎng)度的穩(wěn)定性來(lái)考察幾種典型的AQM算法在高速網(wǎng)絡(luò)中的性能。

三、仿真實(shí)驗(yàn)環(huán)境

對(duì)于現(xiàn)有的AQM算法，可以歸為三類，分別為：基于隊(duì)列長(zhǎng)度的AQM算法、基于瞬時(shí)隊(duì)列長(zhǎng)度和裝載量的AQM算法和基于速率的AQM算法。這里，筆者選擇典型的、具有代表性的RED、PI[2]、BLUE[3]和REM[4]算法和現(xiàn)行使用的Drop-Tail算法來(lái)進(jìn)行考察。筆者在ns-2[5]平臺(tái)上進(jìn)行仿真，仿真的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示，該環(huán)境中，有兩個(gè)中間節(jié)點(diǎn)N1、N2，其相連的鏈路為瓶頸鏈路，帶寬為1Gbps，時(shí)延為20ms。發(fā)送端和接收端各為4個(gè)節(jié)點(diǎn)，其中，S1到N1，R1到N2之間的鏈路帶寬為1Gbps，時(shí)延為1ms， 其他節(jié)點(diǎn)到N1和N2的鏈路帶寬均為1Gbps和2ms。瓶頸鏈路的緩沖區(qū)容量設(shè)為2500個(gè)數(shù)據(jù)包。每隔0.1s，S1、S2、S3、S4各發(fā)起一個(gè)HSTCP連接，這里需要說(shuō)明的是，HSTCP是針對(duì)高速網(wǎng)絡(luò)而設(shè)計(jì)的協(xié)議，正如前面所討論，TCP協(xié)議在高速網(wǎng)絡(luò)下性能非常差，而筆者仿真的目的是考察各種AQM算法在高速網(wǎng)絡(luò)下的性能，因此不能使用TCP連接，而HSTCP在響應(yīng)性、公平性、TCP友好性上都較為優(yōu)秀，因此筆者的仿真實(shí)驗(yàn)選擇HSTCP作為配合AQM的端算法。為了能引起擁塞，四個(gè)HSTCP連接的應(yīng)用均為FTP，也就是說(shuō)只要擁塞窗口允許就一直發(fā)送數(shù)據(jù)，且不考慮接收端的接收能力，只考慮網(wǎng)絡(luò)傳輸能力，為了做到這點(diǎn)，筆者設(shè)置接收端的通告窗口為8000個(gè)數(shù)據(jù)包。同時(shí)，接收端采用每收到一個(gè)數(shù)據(jù)包就發(fā)回一個(gè)確認(rèn)的機(jī)制。整個(gè)仿真過(guò)程為1000s，在瓶頸鏈路上，筆者分別使用Drop-Tail，RED，REM，PI及BLUE算法。其中，BLUE使用原算法的參數(shù)值，RED算法的minth，maxth分別設(shè)為瓶頸鏈路緩沖區(qū)的1/4和3/4，REM和PI控制器的期望隊(duì)列長(zhǎng)度設(shè)1000個(gè)數(shù)據(jù)包。

四、性能分析

對(duì)于PI控制器，計(jì)算丟包概率的公式為：

其中，q（k）是在k時(shí)刻的瞬時(shí)隊(duì)列長(zhǎng)度，q0為目標(biāo)隊(duì)列長(zhǎng)度。參數(shù)a、b的取值跟鏈路容量、數(shù)據(jù)流的個(gè)數(shù)、時(shí)延有關(guān)，但是PI控制器本身不提供計(jì)算a、b的值，即在路由器執(zhí)行PI時(shí)，不根據(jù)實(shí)時(shí)的網(wǎng)絡(luò)狀況調(diào)整a、b的值，一經(jīng)設(shè)定，則固定不變。在這個(gè)模擬環(huán)境下，a的取值為：0.0000001822，b的取值為：0.0000001816，這個(gè)值在高速網(wǎng)絡(luò)下不適用，導(dǎo)致了PI的帶寬利用率沒(méi)有達(dá)到理想的效果，如圖2（b）所示。

REM算法適用于基于速率的擁塞控制，而本身不能提供與源端速率控制算法進(jìn)行合作的機(jī)制，當(dāng)與之相配合的是TCP擁塞控制機(jī)制或TCP的變種時(shí)，它將退化成一般的AQM算法。而且， REM算法其實(shí)是PI控制器的一個(gè)特例，其在高速網(wǎng)絡(luò)中的帶寬利用率同樣沒(méi)有達(dá)到理想的效果，如圖2（c）所示。

BLUE算法在隊(duì)列溢出時(shí)增加丟包概率，在隊(duì)列為空時(shí)減小丟包概率。但是，隊(duì)列溢出和隊(duì)列為空是兩個(gè)極端，并且，丟包概率的增減步長(zhǎng)缺乏對(duì)環(huán)境的適應(yīng)性，所以，在高速網(wǎng)絡(luò)下，同樣出現(xiàn)同步的問(wèn)題，使得帶寬利用率時(shí)高時(shí)低，如圖2（e）所示。

從圖2（d）可以很明顯地看出Drop-Tail算法固有的問(wèn)題：容易導(dǎo)致TCP連接的全局同步。

在筆者的模擬環(huán)境下，在N1節(jié)點(diǎn)分別使用RED、PI、REM、Drop-Tail和BLUE時(shí)，瓶頸鏈路的平均帶寬利用率在表1給出，由表可以看出，這幾種AQM算法的平均帶寬利用率在75%左右，不是很高。

4.2 瓶頸節(jié)點(diǎn)丟包率的比較

隊(duì)列長(zhǎng)度不為零時(shí)可以保證路由器輸出鏈路的帶寬利用率，但輸入鏈路的利用率要靠丟包率來(lái)保證，對(duì)于一個(gè)特定的TCP連接，若丟包率過(guò)高，將會(huì)導(dǎo)致不必要的重傳，從而降低帶寬的利用率。因此，一個(gè)好的AQM算法應(yīng)該在保證帶寬利用率的前提下，保證低的丟包率。筆者在N1節(jié)點(diǎn)分別使用RED，PI，REM，DROP-TAIL和BLUE算法，并統(tǒng)計(jì)N1節(jié)點(diǎn)的丟包率，結(jié)果如圖3所示。

從丟包率的情況來(lái)看，RED、REM、DROP-TAIL和 BLUE都存在同步現(xiàn)象。而PI的丟包率則維持在一定的值附近，因?yàn)閰?shù)a、b不能根據(jù)網(wǎng)絡(luò)環(huán)境而自適應(yīng)地進(jìn)行調(diào)整，在筆者的仿真環(huán)境下，擁塞控制過(guò)于激進(jìn)，使得丟包率一直維持在0.001附近，造成了帶寬利用率的降低。與帶寬利用率相對(duì)應(yīng)的是，丟包率增大，則利用率降低，如圖3（a），與之對(duì)應(yīng)的是圖2（a），在16s時(shí)，丟包率為0.001149，相應(yīng)的帶寬利用率降為31%。

4.3 瓶頸節(jié)點(diǎn)隊(duì)列長(zhǎng)度的比較

AQM對(duì)隊(duì)列長(zhǎng)度的要求是：維持較小的隊(duì)列長(zhǎng)度，避免隊(duì)列長(zhǎng)度劇烈抖動(dòng)，以減小排隊(duì)時(shí)延。

筆者在N1節(jié)點(diǎn)分別使用RED，PI，REM，DROP-TAIL和BLUE算法，并統(tǒng)計(jì)N1節(jié)點(diǎn)的實(shí)時(shí)隊(duì)列長(zhǎng)度，結(jié)果如圖4所示。從圖4可以看出，PI不能很好地控制隊(duì)列長(zhǎng)度在所期望的值附近，而DROP-TAIL、RED和REM的隊(duì)列長(zhǎng)度劇烈抖動(dòng)，表現(xiàn)出了明顯的同步現(xiàn)象。

4.4不同帶寬時(shí)平均利用率和平均隊(duì)列長(zhǎng)度的比較

圖5是瓶頸鏈路的帶寬從200M變化到1000M，在N1節(jié)點(diǎn)分別使用RED、PI、REM、DROP-TAIL和BLUE時(shí)，瓶頸鏈路的平均帶寬利用率和N1節(jié)點(diǎn)的平均隊(duì)列長(zhǎng)度情況。從實(shí)驗(yàn)結(jié)果圖來(lái)看，帶寬越大，各種算法的平均利用率性能表現(xiàn)越差，同時(shí)，平均隊(duì)列長(zhǎng)度也很低，這雖然符合AQM的初衷（盡可能使隊(duì)列長(zhǎng)度很?。@是以犧牲鏈路的帶寬利用率為代價(jià)的。筆者評(píng)價(jià)一個(gè)AQM算法的好壞，要看它是否能在高的鏈路帶寬利用率和低的隊(duì)列長(zhǎng)度之間做好平衡，RED、PI、REM、DROP-TAIL和BLUE在高速網(wǎng)絡(luò)中，這點(diǎn)就沒(méi)有做好。

五、結(jié)論

本文通過(guò)仿真實(shí)驗(yàn)，比較研究了RED、PI、REM、BLUE這幾種典型的AQM算法和Drop-Tail在高速網(wǎng)絡(luò)下的性能，發(fā)現(xiàn)這幾種AQM算法的性能都不理想，鏈路利用率較低，并且全局同步的現(xiàn)象很嚴(yán)重。因此，設(shè)計(jì)新的或改進(jìn)已有的AQM算法勢(shì)在必行。

參 考 文 獻(xiàn)

[1] Floyd， S. Jacobson， V. Random early detection gateways for congestion avoidance [J]. IEEE/ACM. Transactions on Networking， 1993， 1（4）： 397～413

[2] C Hollot， V Misra， D Towsley， W B Gong. On designing improved controllers for AQM routers supporting TCP flows [A]. In： IEEE INFOCOM 2001[C]. Anchorage， Alaska， 2001.1726～1734

[3] W Feng， D Kandlur， D Sah， K Shin. Blue： A new class of active queue management algorithm [R]. University of Michigan Technical Reports CSE-TR-387-99， April 1999

[4] Sanjeewa Athuraliya， Steven H Low， Victor H Li， Qinghe Yin. REM： Active queue management [J]. IEEE Network， 2001， 15（3）： 48～53

[5] S Mccannne， S Floyd. Ns-LBNL the network simulator [EB/OL]. http：//www.isi.edu/nsnam/ns.