一種改進ARED擁塞控制算法的實現

薛 禮

(湖北汽車工業學院 電信學院，湖北 十堰 442002)

0 引 言

進入二十一世紀以來，基于互聯網的應用越來越廣泛，網絡數據流量急劇增加，帶來的一個嚴重問題就是網絡擁塞。當網絡上出現擁塞時，會造成通信雙方數據包傳輸時延增大、數據包容易丟失并重發、網絡吞吐量降低等問題，嚴重的情況下會導致網絡死鎖和癱瘓，因此TCP/IP網絡體系結構實現的過程中在運輸層中引入了擁塞控制策略。目前運輸層中最重的TCP協議各版本實現機制中均引入了慢啟動、擁塞避免、快速重傳等一系列算法來實現可靠的擁塞控制[1]。這種擁塞控制機制是建立在端到端的基礎上，在早期互聯網運行過程中能夠很好地保障網絡的可靠性和穩定性，提升服務質量QoS，因此傳輸控制協議TCP成為一種可靠的運輸層協議[2]。但隨著互聯網規模的激增，通信子網的結構越來越復雜，大量數據包涌入到通信子網的節點路由器上，造成網絡層的數據擁塞，這樣僅僅依靠端到端的擁塞控制機制已經無法滿足需求[3]。于是近些年來路由器上的擁塞控制機制也逐漸部署起來，稱為節點擁塞控制機制，對于這類研究主要以主動隊列管理AQM算法為主[4]。主動隊列管理是一種基于先進先出(first input first output)調度策略的隊列管理，能夠控制路由器丟棄數據包的時間和數量。其核心思想是通過對網絡擁塞實施早期監測，一旦發現擁塞的可能性，便主動向發送端發出擁塞信號，這時發送端便會降低數據包的發送速率，從而減少網絡中數據包的數量，達到降低數據包丟失率和提高通信鏈路吞吐量的目的。在AQM算法控制下，路由器緩沖區出現溢出之前以一定的策略丟棄數據包，避免了隊列溢出，解決了滿隊列問題。從擁塞控制的角度看，傳統的隊列管理算法只包含擁塞恢復機制，而AQM算法既包含擁塞恢復機制又包括擁塞避免機制，因此AQM算法對于提高擁塞控制的性能具有比較重要的作用，在路由器中使用AQM算法可以帶來的好處包括：

(1)降低路由器中被丟棄數據包的數量。互聯網中數據包的突發性從根本上是不可避免的，而AQM算法通過使路由器保持較短的平均隊列長度(average queue length)，從而能夠解決吸收突發數據包的問題，大大降低了突發數據包丟失的可能性。

(2)交互式應用實現更低的延時。AQM算法中路由器可以保持較短的平均隊列長度，因此能夠降低數據包的排隊時延(queuing delay)，而排隊時延是端到端時延的重要組成部分，這對交互式應用(如WEB瀏覽、Telnet和視頻會議等)有重要幫助。

(3)避免網絡“死鎖”現象。“死鎖”是指當擁塞嚴重到網絡無吞吐量的現象，AQM算法能夠確保路由器幾乎總有可用的隊列空間來容納到達的數據包，從而可以防止“死鎖”情況的發生。同時因為這個原因，AQM算法也能防止路由器對突發數據流的偏見。

隨機早期丟棄算法(random early detection，RED)是AQM算法的一個代表，相比隊尾丟棄算法DropTail，RED算法具有網絡鏈路利用率較高、吞吐量較大、網絡時延和丟包率較小的優點[5-6]。因此互聯網工程任務組IETF將其作為唯一擁塞控制候選算法極力推薦使用，希望達到良好的節點擁塞機制的效果。

1 RED及ARED算法原理

1.1 RED算法概述

當節點路由器實施了RED算法，它會實時監控緩沖區平均隊列長度，因為其作為一個重要指標用來判斷網絡是否出現擁塞。如果發現網絡有出現擁塞的可能性，那么路由器便會以一定的概率丟棄接收到的數據包，并向發送端發送通知，發送端收到通知后會降低數據包的發送速率，這樣進入網絡的數據包便會減緩，使路由器隊列長度維持在一個良性的狀態，從而降低了網絡傳輸延遲和丟包率，提高了網絡資源的利用率，達到有效緩解網絡擁塞的目的[7-8]。與傳統DropTail算法相比，RED算法改進點主要體現在兩個方面：第一，路由器不是等隊列全部填滿后再丟棄隨后到來的數據包，而是在有可能出現擁塞之前通過計算概率隨機丟棄部分數據包來預防可能出現的擁塞；第二，計算數據包隨機丟棄概率時采納平均隊列長度而不是瞬時隊列長度，因此能盡量滿足突發數據流對路由器緩沖區空間的需求，降低產生網絡全局同步現象的可能性。

當路由器實施RED算法控制機制時，其針對緩沖區隊列事先設置了兩個重要參數，即最小隊列長度閾值THmin和最大隊列長度閾值THmax。路由器接收到一個新到達的數據包時，首先計算緩沖區隊列平均長度Lav，如果Lav小于閾值THmin，則丟棄概率為0，允許新到的數據包進入隊列排隊；如果Lav大于最大閾值THmax，則丟棄概率為1，將新到的數據包丟棄；如果Lav在閾值THmin和THmax之間，則會依據控制策略中的相關機制計算丟包概率P，并將新收到的該數據包按此概率實施丟棄。RED控制策略中計算平均隊列長度Lav的方法是將瞬時隊列長度Lsa和舊的平均隊列長度Lav進行加權計算，其中權值Wq根據實際情況取[0,1]之間的值[9]，Lav的計算如式(1)所示。

Lav=(1-Wq)×Lav+Wq×Lsa

(1)

根據式(1)計算出平均隊列長度Lav，與預先設定好的最小隊列長度閾值THmin、最大隊列長度閾值THmax進行比較，通過比較結果來判定網絡擁塞的程度，以此作為決定數據包丟棄概率P的依據。具體來說就是：如果LavTHmax，則丟棄概率P為1，不允許新到的數據包進入緩沖區排隊，直接丟棄；若THmin≤Lav≤THmax，會利用線性函數計算出丟棄概率P，并以此概率丟棄新到的數據包。其中計算丟棄概率P會涉及到預先設定的最大丟棄概率Pmax、上一次丟包之后新進入隊列的數據包數量count以及相關的計算函數，式(2)和式(3)為采用線性函數計算所得從0到Pmax變化的Pb和丟棄概率P。

(2)

(3)

從以上公式可以看出，丟棄概率P的值不僅和路由器緩沖區平均隊列長度Lav有關，同時也會隨著進入緩沖區隊列數據包數量count的增加而平緩增大，這樣會使新到數據包的丟棄時間間隔相對平滑，避免密集地產生丟包現象[10]。

算法RED的劣勢在于前面提到的各種參數的預置上，網絡擁塞情況影響因素很多，是動態變化的，而相對固定的參數值不能很好地滿足網絡擁塞情況動態變化的需求[11]，因此對于RED算法的各種改進研究便集中在這點上面。

1.2 ARED算法概述

針對上面提到的RED算法中固定參數無法適應動態網絡需求的缺點，相關研究提出了一些改進方法，其中最具有代表性的就是自適應RED算法，簡稱為ARED。在ARED算法中，最大丟棄概率Pmax不是使用事先設定好的固定值，而是根據平均隊列長度的動態變化來調整Pmax。具體檢測策略就是如果緩沖區平均隊列長度在THmin附近波動，說明數據包丟失過多，擁塞控制策略過于激進，應減小Pmax；如果緩沖區平均隊列長度在THmax附近波動，說明數據包丟失過少，擁塞控制策略有點保守，應增大Pmax。動態調整算法的具體偽代碼如下：

every intertime

if(Lav>targetl &&Pmax≤0.5)

Pmax=Pmax+α;

else if(Lav

Pmax=Pmax*β;

其中intertime為檢測緩沖區平均隊列長度的間隔時間，一般取值為0.5秒；targetl表示緩沖區平均隊列長度的目標值，其取值范圍是[THmin+0.4*(THmax-THmin)，THmin+0.6*(THmax-THmin)]；α是加法增大Pmax的因子，一般取值為α=min(0.01,0.25*Pmax)，β是乘法減少Pmax的因子，一般取值為β=0.9。

1.3 算法對比

以下將通過仿真網絡環境來模擬兩種算法，模擬環境的組建采用網絡仿真軟件NS2[12-13]，對應的網絡拓撲結構如圖1所示。

圖1 仿真實驗網絡拓撲結構

路由器r1和r2之間的鏈路為瓶頸鏈路，帶寬設置為45 Mb/s，往返時延設置為20 ms，在路由器r1和r2上依次實施網絡擁塞算法RED和ARED。s1到sn為一定數量的發送實體，d1到dn為對應數量的接收實體，發送實體與路由器r1連接，接收實體與路由器r2連接，所有鏈路的帶寬均設置為100 Mb/s，往返時延設置為1 ms。在發送實體sn及對應的接收實體dn之間建立TCP連接，使用FTP協議流量。在兩種擁塞控制算法中所用到的參數分別設置為Wq=0.002，Pmax=0.1，intertime=0.5 s，THmin=40 packets，THmax=180 packets，Buffersize=200 packets。建立80個發送實體和接收實體的并發連接，模擬運行時間100 s，在此過程中分別跟蹤實施RED和ARED算法的路由器平均隊列長度[14]，并繪制其變化如圖2和圖3所示。通過比較可以發現，ARED算法的平均隊列長度振蕩平緩，穩定性優于RED算法。

圖2 RED算法平均隊列長度變化

圖3 ARED算法平均隊列長度變化

2 ARED算法的優化

2.1 QARED算法概述

ARED算法在控制策略上增加了對Pmax參數的動態修訂，這使得丟包概率能夠隨著網絡數據流量的變化而動態調整，但隨之又引入了三個新的參數intertime、α、β，造成ARED算法與RED算法一樣存在著預置參數值選取的問題，不同參數值的選取會影響Pmax動態調整的效果。因此以下提出一種改進算法，稱為QARED算法，主要目的是希望通過優化丟棄概率Pb的計算方式來提高路由器緩沖區平均隊列長度的穩定性，以減少算法中固定參數值設定所帶來的影響[15]。

在式(2)中計算Pb所采用的是線性函數，而QARED算法提出采用平方函數來進行計算，如式(4)所示，兩種計算函數的曲線如圖4所示。

(4)

圖4 兩種算法丟棄概率計算函數曲線

通過平方函數曲線可以看到，當緩沖區平均隊列長度比較接近THmin時，丟棄概率Pb變化比較平緩；而當超過0.5*(THmin+THmax)，丟棄概率Pb變化加劇。這種處理方式帶來的好處是在緩沖區平均隊列長度較小時降低丟包率，從而提高包轉發效率；而接近THmax時加大丟包率，減少擁塞的可能，最終維持緩沖區平均隊列長度在一個穩定值，保證了網絡的吞吐量。

2.2 QARED算法模擬實驗及對比

在NS2網絡仿真軟件中，通過路徑ns-allinone-2.29 s-2.29queue打開ARED算法實現C++源程序red.cc，其中calculate_p_new()便是Pb的計算函數，對應的語句為：

p=v_a * v_ave + v_b;

p*=max_p;

將計算方式改為：

p=(v_a * v_ave+v_b)*(v_a * v_ave+v_b);

p=0.5 * max_p+0.5*max_p*p;

然后重新編譯NS2：

cd ns-allinone-2.29

cd ns-2.29

make clean

make

模擬QARED算法運行時設置與1.3小節中相同的參數，跟蹤獲得路由器緩沖區平均隊列長度變化如圖5所示。通過與ARED算法進行對比可以發現，在改進算法中緩沖區平均隊列長度振蕩更趨于平緩，其長度值差不多維持在0.5*(THmin+THmax)附近，這進一步證實了其穩定性要優于ARED算法，從而更有效地保證路由器緩沖區隊列有空間來處理突發數據流，不會造成數據包的大量丟失，提高了數據包轉發的效率。

圖5 QARED算法平均隊列長度

2.3 三種算法的時延和丟包率對比

在QARED算法中，由于緩沖區平均隊列長度更加平穩，從而達到了降低數據包丟失率和網絡平均往返時延的目的。在模擬實驗定量分析中，通過NS2系統中的數據流監控對象Flowmon和分類器對象Classifier/Hash/Fid來對各種算法下鏈路的平均往返時延、路由器到達數據包數量和被丟棄數據包數量分別進行跟蹤并記錄，相關程序如下：

set fmon [$ns makeflowmon Fid];

$ns attach-fmon $link_r1r2 $fmon;

set redq [[$ns link $r1 $r2] queue];

set traceq [open red-tra($minthresh).tr w];

$redq trace curq;

$redq trace ave;

$redq attach $traceq;

然后利用繪圖工具plot基于上面的跟蹤數據繪制平均隊列長度變化圖。

plot 'red-cur(15).tr' using 2:3 title 'RED Buffersize=48' with lines

最后分別統計三種算法模擬實驗中的平均往返時延、到達數據包數量、被丟棄數據包數量，以及計算丟包率，如表1所示。通過表中數據可以看出，QARED算法是最優的，證明了這種改進思路的有效性。

表1 三種算法數據對比

3 結束語

RED及其改進算法是更為有效的節點擁塞控制策略，通過模擬實驗對比可以發現，當網絡流量動態變化時，RED算法在控制平均隊列長度穩定性上是成功的，因為當路由器平均隊列長度超過了最大閾值后就采用均勻隨機丟棄數據包的策略，有效控制了平均隊列長度，降低了平均時延，消除了對突發數據流的偏見；同時也在很大程度上緩解了TCP數據流的“全局同步”現象。由于RED算法在不降低吞吐量的情況下可以大大降低傳輸延時，因此其綜合性能要優于傳統的DropTail算法。

基于RED及ARED算法，文中提出了一種調整丟棄概率計算函數的思路，并利用網絡模擬軟件NS2模擬算法的運行并跟蹤收集相關數據，通過三種算法的對比分析驗證了改進算法QARED相對于ARED算法在控制路由器緩沖區平均隊列長度穩定性上的優勢，QARED算法能夠支持更低的網絡時延和丟包率，提升網絡動態變化下擁塞控制策略的穩定性。但不管是ARED還是QARED算法，在其運行過程中相關參數的預置仍然是基于常規的網絡情況，如何更好地動態調整相關參數的設置來滿足不同的網絡情況是這類算法后續改進的研究點。