改進(jìn)ARED擁塞控制算法研究與實(shí)現(xiàn)

薛禮　陳利

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

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

DOIDOI：10.11907/rjdk.171861

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2017）011004103

0引言

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

1算法原理

1.1RED算法思想

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

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

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

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

P=Pb1-count×Pb（3）

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

1.2ARED算法思想

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

every interval time

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

Pmax=Pmax+α；

else if （Lav

Pmax=Pmax*β；

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

1.32種算法對(duì)比

利用網(wǎng)絡(luò)模擬軟件NS2構(gòu)建仿真環(huán)境，網(wǎng)絡(luò)拓?fù)淙鐖D1所示。

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

2ARED算法改進(jìn)及對(duì)比

2.1QARED算法思想

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

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