基于NLMS算法的自適應(yīng)AQM控制機(jī)制的研究

郜亞麗,李世勇

(1.濟(jì)源職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)實(shí)訓(xùn)中心,河南濟(jì)源454650;2.北京交通大學(xué) 電子信息工程學(xué)院下一代互聯(lián)網(wǎng)互聯(lián)設(shè)備國家工程實(shí)驗(yàn)室,北京100044)

隨著Intenet網(wǎng)絡(luò)規(guī)模的迅速擴(kuò)大,網(wǎng)絡(luò)上開放的業(yè)務(wù)種類不斷增加,網(wǎng)絡(luò)應(yīng)用的不斷深入,導(dǎo)致網(wǎng)絡(luò)吞吐量急劇降低,嚴(yán)重時(shí)甚至發(fā)生網(wǎng)絡(luò)崩潰,這就是網(wǎng)絡(luò)擁塞現(xiàn)象。網(wǎng)絡(luò)擁塞已經(jīng)成為制約網(wǎng)絡(luò)發(fā)展和應(yīng)用的瓶頸。隨著網(wǎng)絡(luò)規(guī)模的增大,僅僅依靠TCP擁塞控制機(jī)制來提高網(wǎng)絡(luò)的服務(wù)質(zhì)量是遠(yuǎn)遠(yuǎn)不夠的,因此路由器作為網(wǎng)絡(luò)的中間節(jié)點(diǎn)也必須參與到網(wǎng)絡(luò)擁塞控制中來。近年來,主動(dòng)隊(duì)列管理(active queue management,簡稱AQM)[1]成為網(wǎng)絡(luò)擁塞控制研究中的一個(gè)技術(shù)熱點(diǎn)。它通過網(wǎng)絡(luò)中間節(jié)點(diǎn)由控制的分組丟棄機(jī)制,實(shí)現(xiàn)了較低的排隊(duì)延時(shí)和較高的有效吞吐量。研究人員提出了多種 AQM 算法,如 RED[2], REM[3],PI[4],LRC-RED[5]等。最早經(jīng)典的當(dāng)數(shù)由Floyd等于1993年提出的隨機(jī)早期丟棄RED (Random Early Drop)算法。該算法是目前最常用的一種AQM算法。

RED算法以平均隊(duì)列長度作為擁塞指示來控制包的丟失。在動(dòng)態(tài)網(wǎng)絡(luò)中,這些算法對(duì)突發(fā)流不敏感,使得隊(duì)列長度波動(dòng)較大[6]。本文通過引入加權(quán)隊(duì)列長度作為擁塞指示,使用歸一化最小均方(NLMS)算法,結(jié)合對(duì)分組丟棄概率的更合理的計(jì)算,將瞬時(shí)隊(duì)列長度控制在一個(gè)較為穩(wěn)定的范圍內(nèi)。并通過算法仿真實(shí)驗(yàn)和性能比較,驗(yàn)證了該算法在保持隊(duì)列穩(wěn)定的同時(shí)丟包率也有所降低。

1 歸一化最小均方(NLMS)算法

LMS(Least mean square)中文是最小均方算法,是經(jīng)典的自適應(yīng)濾波器算法[7],具有實(shí)現(xiàn)簡單,計(jì)算量小等優(yōu)點(diǎn)。原理圖如圖1所示,分為波束賦形和自適應(yīng)權(quán)重控制兩個(gè)部分,通過迭代的方法來求解MMSE準(zhǔn)則下的最優(yōu)權(quán)重。NLMS算法是改進(jìn)的LMS算法,又稱為歸一化最小均方算法,是采用變步長的方法來縮短自適應(yīng)收斂過程。

以自適應(yīng)系統(tǒng)辨識(shí)[8]為例,x(n)是輸入?yún)⒖夹盘?hào),y(n)是未知系統(tǒng)的輸出信號(hào)。則自適應(yīng)濾波器輸出的y(n)的預(yù)估值為

式中N—濾波器的階數(shù);{{hi(n)|i=0,1,…,N-1}—第n次迭代后自適應(yīng)濾波器的系數(shù)。

該算法在輸入信號(hào)較大的情況下避免梯度噪聲放大的干擾,因而具有較好的收斂性能[8]。

2 NLMS算法在主動(dòng)隊(duì)列管理中的實(shí)現(xiàn)

2.1 算法的描述

基于NLMS算法的基本原理是：引入加權(quán)隊(duì)列長度作為擁塞指示,通過對(duì)過去N個(gè)時(shí)刻的瞬時(shí)隊(duì)列長度信息分別賦以不同權(quán)重,并采用NLMS算法中的參數(shù)調(diào)整方法對(duì)權(quán)重自適應(yīng)調(diào)整來得到加權(quán)隊(duì)列長度。由于權(quán)重因子可以自適應(yīng)調(diào)節(jié),且采用了過去時(shí)刻的瞬時(shí)隊(duì)列值,因此加權(quán)隊(duì)列長度比RED算法中的平均隊(duì)列長度更及時(shí)地反映網(wǎng)絡(luò)流量變化情況,從而對(duì)擁塞作出反應(yīng)。

算法的實(shí)現(xiàn)主要分三步：

第一步：計(jì)算加權(quán)隊(duì)列長度。第二步：結(jié)合加權(quán)隊(duì)列長度和網(wǎng)絡(luò)負(fù)載流量進(jìn)行丟包決策。第三步：采用NLMS的方法更新權(quán)值,回到第一步。

2.2 加權(quán)隊(duì)列長度計(jì)算及權(quán)值更新

式中wq—加權(quán)隊(duì)列長度;w(n-i)—過去第i個(gè)時(shí)刻的瞬時(shí)隊(duì)列值所占的權(quán)重;q(n-i)—過去第i個(gè)時(shí)刻的瞬時(shí)隊(duì)列值。

權(quán)重因子在加權(quán)隊(duì)列長度和當(dāng)前瞬時(shí)隊(duì)列長度之差的基礎(chǔ)上動(dòng)態(tài)更新。誤差e(n)計(jì)算為e (n)=q(n)-wq,由式(1)得到隊(duì)列權(quán)重的更新

μ為NLMS的比例因子,由下式?jīng)Q定

式中 μ0取1得以保證收斂,a取1得以保證分母不為零。

2.3 丟包決策

式中λ—負(fù)載因子(load factor);γ—包到達(dá)速率; C—鏈路的服務(wù)速率(即鏈路帶寬)。

在進(jìn)行分組丟棄概率計(jì)算時(shí),考慮了鏈路負(fù)載和隊(duì)列長度信息,分組的丟棄概率p計(jì)算如下

式中wq—估計(jì)的隊(duì)列長度;B—緩存的大小。

通過這種概率丟棄使得(被接納的)包到達(dá)速率與鏈路容量達(dá)到平衡,同時(shí)還考慮了隊(duì)列長度,隊(duì)列長度越長則分組被丟棄的概率也越大。

具體丟包策略如下：

3 仿真實(shí)驗(yàn)與性能比較

利用網(wǎng)絡(luò)仿真軟件NS-2來驗(yàn)證算法的性能。采用NLMS(實(shí)驗(yàn)中稱為NAQM)算法、RED算法、REM算法、LRC-RED算法進(jìn)行仿真比較。實(shí)驗(yàn)環(huán)境為多瓶頸鏈路,實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示。在圖2中,從左到右的五條鏈路帶寬均為15M,延時(shí)20ms。sender為發(fā)送端,receiver為接收端。其中,senderl到 receiverl是 100個(gè)TCP流, sender2到receiver2是30個(gè)TCP流,sender3到receiver3是30個(gè)TCP流。在實(shí)驗(yàn)中,瓶頸鏈路r2-r3的特性和r4-r5的特性類似,而鏈路r1-r2、r3 -r4、r5-r6基本不會(huì)出現(xiàn)擁塞。因此僅分析r2-r3之間的性能。

3.1 負(fù)載固定情況下的性能

實(shí)驗(yàn)中,考慮隨時(shí)間變化負(fù)載固定的情況下,考察各算法在隊(duì)列長度的穩(wěn)定性、丟包率大小的變化。其中,sendersl,senders2,senders3分別同時(shí)啟動(dòng)100個(gè),30個(gè),30個(gè)TCP連接,仿真時(shí)間為50s。下面是各種性能指標(biāo)的仿真結(jié)果。

隊(duì)列長度的變化。圖3所示的是在負(fù)載固定的情況下,各算法在維持隊(duì)列穩(wěn)定性方面的性能。由圖中四種算法的對(duì)比可以看出,在多瓶頸鏈路中,NAQM算法能夠很好的維持在200附近,并且波動(dòng)較小,因此穩(wěn)定性也最好。LRC-RED算法的隊(duì)列長度也基本保持在200附近,但隊(duì)列的波動(dòng)比NAQM算法稍大一些。RED算法所維持的隊(duì)列長度波動(dòng)較大。REM算法基本處于滿隊(duì)列,無法保持在期望值附近,且波動(dòng)大。由此可見,在多瓶頸鏈路中,負(fù)載固定時(shí),NAQM算法所表現(xiàn)出的性能是最好的,其隊(duì)列最穩(wěn)定,能夠很好的保持在期望值附近,隊(duì)列波動(dòng)小,且響應(yīng)時(shí)間短。

丟包率的變化。表1所示為靜態(tài)情況下節(jié)點(diǎn)r2-r3之間的鏈路的各算法丟包率。通過表中四個(gè)算法的比較,RED與NAQM算法的丟包率較為接近,約為3.3%左右。其次是LRC-RED,丟包率最大的是REM算法。

表1 靜態(tài)時(shí)各算法在鏈路r2-r3之間的丟包率Tab.1 The packet loss rate of each algorithm between link r2 and link r3 in static state

3.2 負(fù)載變化環(huán)境下的性能

實(shí)驗(yàn)中,考慮負(fù)載隨時(shí)間變化的情況下,考察各算法在隊(duì)列長度的穩(wěn)定性、丟包率大小的變化方面的性能。其中,sendersl分別在0s,5s,10s,20s, 30s啟動(dòng)20組TCP連接,senders2、senders3分別在0s啟動(dòng)30組TCP連接,仿真時(shí)間為50s。下面是各種性能指標(biāo)的仿真結(jié)果。

表2 動(dòng)態(tài)時(shí)各算法在鏈路r2-r3之間的丟包率Tab.2 The packet loss rate of each algorithm between link r2 and link r3 in dynamic state

隊(duì)列長度的變化。圖4所示的是在負(fù)載變化的情況下,各算法在維持隊(duì)列穩(wěn)定性方面的性能。由圖中四種算法的對(duì)比可以看出,在動(dòng)態(tài)多瓶頸鏈路中,NAQM算法能夠很好地維持在200附近,并且波動(dòng)較小。LRC-RED算法次之,RED算法的隊(duì)列長度波動(dòng)較大,并且在每次增加負(fù)載時(shí),隊(duì)列有波動(dòng)。REM算法基本處于滿隊(duì)列,無法保持在期望值附近。由此可見,在多瓶頸鏈路中,負(fù)載變化時(shí),NAQM算法所表現(xiàn)出的性能是最好的,其隊(duì)列最穩(wěn)定,能夠很好地保持在期望值附近,隊(duì)列波動(dòng)小,且響應(yīng)時(shí)間較短。

丟包率的變化。表2所示為動(dòng)態(tài)情況下節(jié)點(diǎn)r2-r3之間鏈路的各算法丟包率。通過表中四個(gè)算法的比較,RED算法的丟包率最小,REM和NAQM算法的丟包率相近,約為2.8%左右。丟包率最大的是LRC-RED算法,約為3.2%左右。

4 結(jié)論

1)主動(dòng)隊(duì)列管理在保證高吞吐量的同時(shí),能有效控制緩沖隊(duì)列的長度,減小網(wǎng)絡(luò)時(shí)延。

2)采用歸一化最小均方(Normal Least Mean Square,NLMS)的方法對(duì)權(quán)值自適應(yīng)調(diào)整,結(jié)合負(fù)載因子對(duì)分組進(jìn)行更為合理的丟棄,將隊(duì)列長度的變化穩(wěn)定在一個(gè)理想的水平。

3)仿真實(shí)驗(yàn)表明該算法具有較好的動(dòng)靜態(tài)性能,且能提高隊(duì)列穩(wěn)定性,降低丟包率。尤其在多瓶頸鏈路中,算法的隊(duì)列穩(wěn)定性最好。

[1]朱小艷,李向麗.主動(dòng)式隊(duì)列管理(AQM)算法研究[J].微計(jì)算機(jī)信息,2006(1)：2-3.

[2]魏濤,張順頤.一種模糊自調(diào)整的PD-RED算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(5)：124-126.

[3]蘇聰,陳元琰,羅曉曙.基于模糊理論的主動(dòng)隊(duì)列管理算法-FBLUE[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(23)：117-120.

[4]朱華,向少華.一種模糊自適應(yīng)PI算法在網(wǎng)絡(luò)擁塞控制中的應(yīng)用[J].大眾科技,2009,123(11)：32-34.

[5]任豐原,林闖,劉衛(wèi)東.IP網(wǎng)絡(luò)中的擁塞控制[J].計(jì)算機(jī)學(xué)報(bào),2003,26(9)：1025-1034.

[6]薛質(zhì),潘理,李建華.基于模糊RED算法的IP擁塞控制機(jī)制[J].計(jì)算機(jī)工程,2002,28(3)：60-61.

[7]谷源濤,唐 昆,崔慧娟,等.變步長歸一化最小均方算法[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2002,42(1)：15 -18.

[8]HAYKIN S.自適應(yīng)濾波器原理(第三版)[M].北京：電子工業(yè)出版社,1998.