蘇聰

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

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

一、引言

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

二、算法的評價指標(biāo)

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

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

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

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

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

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

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

三、仿真實驗環(huán)境

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

四、性能分析

對于PI控制器，計算丟包概率的公式為：

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

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

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

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

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

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

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

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

4.3 瓶頸節(jié)點隊列長度的比較

AQM對隊列長度的要求是：維持較小的隊列長度，避免隊列長度劇烈抖動，以減小排隊時延。

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

4.4不同帶寬時平均利用率和平均隊列長度的比較

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

五、結(jié)論

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

參 考 文 獻(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.