薛禮　陳利

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

關鍵詞關鍵詞：擁塞控制；ARED；NS2網(wǎng)絡模擬

DOIDOI：10.11907/rjdk.171861

中圖分類號：TP312

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

0引言

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

1算法原理

1.1RED算法思想

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

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

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

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

P=Pb1-count×Pb（3）

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

1.2ARED算法思想

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

every interval time

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

Pmax=Pmax+α；

else if （Lav

Pmax=Pmax*β；

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

1.32種算法對比

利用網(wǎng)絡模擬軟件NS2構建仿真環(huán)境，網(wǎng)絡拓撲如圖1所示。

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

2ARED算法改進及對比

2.1QARED算法思想

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

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