改進ARED擁塞控制算法研究與實現

薛禮　陳利

摘要：為實現基于路由器的擁塞控制算法性能提升，分析了RED與ARED擁塞控制算法，并提出一種改進算法QARED。與傳統DropTail算法對比，RED算法具有較高鏈路利用率、吞吐量及較低網絡延遲、丟包率等優點，但存在參數配置無法適應網絡動態改變的缺點。ARED算法增加了自適應功能，根據平均隊列長度變化動態調整最大丟包概率，穩定平均隊列長度在最小閾值與最大閾值之間，但存在瞬時隊列長度振蕩等穩定性問題。改進算法QARED，通過優化最大丟包概率計算函數，以提高平均隊列長度穩定性、降低丟包率、提高吞吐量。通過NS2仿真網絡環境對比，改進算法QARED相對ARED算法在控制平均隊列長度上更具穩定性，能夠實現更低網絡延遲與丟包率，提高了動態網絡環境下擁塞控制穩定性。

關鍵詞關鍵詞：擁塞控制；ARED；NS2網絡模擬

DOIDOI：10.11907/rjdk.171861

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2017）011004103

0引言

隨著互聯網流量增多，網絡擁塞日趨嚴重。網絡出現擁塞，會帶來延時增大、丟包、重發增多、吞吐量減少等問題，嚴重時還會導致網絡癱瘓。因此網絡擁塞控制成為傳輸層協議實現的重要功能，在TCP協議Tahoe、Reno等版本中包含了慢啟動、擁塞避免、快速重傳、快速恢復算法以及改進算法。通過端系統擁塞控制機制能夠很好地保證網絡可靠性與穩定性，改善服務質量QoS。近年來，擁塞控制機制在路由器中也開始實施，擁塞控制策略研究主要集中于主動隊列管理AQM算法[1]。AQM算法一個代表是隨機早期丟棄RED，相比傳統隊尾丟棄Droptail具有較高鏈路利用率、吞吐量與較低網絡延遲、丟包率等優點，IETF推薦其作為唯一候選算法，在目前結點擁塞控制中起到了重要作用[2]。

1算法原理

1.1RED算法思想

RED算法中，路由器通過監測平均隊列長度探測擁塞，在擁塞可能出現的時候，按一定概率隨機丟棄某些分組，通知發送端降低數據發送速率，維持合適隊列長度，降低網絡延遲，緩解網絡擁塞[3]。RED算法中對瞬時隊列長度Lsa采用指數加權計算平均隊列長度Lav，權值Wq介于0～1之間，如式（1）所示：

Lav=（1-Wq ）×Lav+Wq×Lsa（1）

對比平均隊列長度與事先設置的隊列最小閾值THmin、最大閥值THmax，判斷網絡擁塞程度，決定分組丟棄概率。具體標準是若LavTHmax，則丟棄概率為1，分組被丟棄；若THmin≤Lav≤THmax，則計算出丟棄概率P，并以此概率丟棄分組。其中P的計算會利用事先選用的最大丟棄概率Pmax以及計算函數（例如采用線性增長從0變到Pmax），count代表上一次丟包后新進入隊列的包數量。

Pb=Pmax×Lav-THminTHmax-THmin（2）

P=Pb1-count×Pb（3）

從式（2）、式（3）可以看出，丟棄概率P不僅與平均隊列長度Lav有關，還隨著隊列中不被丟棄數據包數目增多而增大，這樣可使數據包丟棄間隔相對均勻，避免數據包丟棄過于集中，造成全局同步現象[4]。RED算法缺點在于參數設定，一組固定參數值無法滿足網絡動態變化需求[5]。

1.2ARED算法思想

研究者針對RED算法提出了改進方案，其中ARED算法是通過檢查平均隊列長度變化來動態調節最大丟棄概率Pmax，如果平均隊列長度是在THmin附近波動，那么擁塞控制就太積極，應減小Pmax值；如果在THmax附近波動，那么擁塞控制就太保守，應增大Pmax值。動態調整Pmax算法如下：

every interval time

if （Lav>target && Pmax≤0. 5）

Pmax=Pmax+α；

else if （Lav

Pmax=Pmax*β；

其中interval time為調整丟棄概率時間間隔，一般取0.5s；target表示平均隊列理想區間范圍[THmin+0.4*（THmax-THmin） ， THmin+0.6*（THmax-THmin）]；α、β分別表示Pmax增大及減小因子，α=min（0.01，Pmax/4），β= 0.9。

1.32種算法對比

利用網絡模擬軟件NS2構建仿真環境，網絡拓撲如圖1所示。

仿真環境中路由器r1與r2之間為瓶頸鏈路，帶寬45Mbps，延遲20ms，隊列算法分別采用RED與ARED。s1到sn為源端，d1到dn為目的端，分別與r1、r2相連的鏈路帶寬為100Mbps，延遲1ms。sn與dn依次對應建立TCP連接，使用FTP數據流。算法參數設置為Wq=0.002，Pmax=0.1，interval=0.1，THmin=50packets，THmax=150packets，Buffersize=200packets。圖2與圖3是構建80個連接，運行100s模擬時間，分別跟蹤RED與ARED算法的平均隊列長度[6]。通過比較可以發現ARED算法平均隊列長度穩定性優于RED算法。

2ARED算法改進及對比

2.1QARED算法思想

ARED算法改進了Pmax的動態調整，但計算過程又引入了3個參數interval、α、β，同樣存在參數設置問題，不同設置會影響Pmax調整效果[7]。因此本文提出一種改進的QARED算法，通過修改丟棄概率計算來鞏固平均隊列長度穩定性[8]。

式（2）中，Pb的計算采用線性函數，而改進算法采用二次方函數計算，如式（4）所示，它們的函數曲線見圖4。由圖4可知，平均隊列長度接近THmin值時，丟棄概率變化相對緩慢，而超過0.5*（THmin+THmax）之后，變化加快，就能夠在平均隊列較短時降低包的丟棄概率；接近最大門限值時加大丟包概率，平均隊列長度維持在合適值，可保證穩定性。