幾種典型AQM算法在高速網絡下的比較研究

蘇聰

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

【關鍵詞】 AQM算法 NS仿真模擬

一、引言

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

二、算法的評價指標

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

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

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

3、公平性：AQM的目標之一是改進Drop-Tail隊列的公平性。REC2309強調：路由器的隊列機制應保護適應流，對非適應流進行有效的鑒別和限制。

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

5、對網絡狀態變化的適應能力：具有較強的魯棒性，即對環境變化不敏感。Internet的復雜性和異構性決定了網絡狀態的變化是難以避免的，因此一個好的AQM算法應該對網絡狀態的變化具有很好的適應能力，在網絡負載、傳輸時延等因素發生變化時，仍可實現好的傳輸性能。

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

三、仿真實驗環境

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

四、性能分析

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

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

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

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

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

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

4.2 瓶頸節點丟包率的比較

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

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

4.3 瓶頸節點隊列長度的比較

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

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

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

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

五、結論

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

參 考 文 獻

[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.