郜亞麗,李世勇

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

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

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

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

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

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

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

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

2 NLMS算法在主動隊列管理中的實現(xiàn)

2.1 算法的描述

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

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

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

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

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

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

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

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

2.3 丟包決策

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

在進行分組丟棄概率計算時,考慮了鏈路負載和隊列長度信息,分組的丟棄概率p計算如下

式中wq—估計的隊列長度;B—緩存的大小。

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

具體丟包策略如下：

3 仿真實驗與性能比較

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

3.1 負載固定情況下的性能

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

[3]蘇聰,陳元琰,羅曉曙.基于模糊理論的主動隊列管理算法-FBLUE[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].計算機學(xué)報,2003,26(9)：1025-1034.

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

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

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