基于NLMS算法的自適應AQM控制機制的研究

郜亞麗,李世勇

(1.濟源職業技術學院實驗實訓中心,河南濟源454650;2.北京交通大學 電子信息工程學院下一代互聯網互聯設備國家工程實驗室,北京100044)

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

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

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

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

以自適應系統辨識[8]為例,x(n)是輸入參考信號,y(n)是未知系統的輸出信號。則自適應濾波器輸出的y(n)的預估值為

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

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

2 NLMS算法在主動隊列管理中的實現

2.1 算法的描述

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

算法的實現主要分三步：

第一步：計算加權隊列長度。第二步：結合加權隊列長度和網絡負載流量進行丟包決策。第三步：采用NLMS的方法更新權值,回到第一步。

2.2 加權隊列長度計算及權值更新

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

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

μ為NLMS的比例因子,由下式決定

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

2.3 丟包決策

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

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

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

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

具體丟包策略如下：

3 仿真實驗與性能比較

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

3.1 負載固定情況下的性能

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

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

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

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

3.2 負載變化環境下的性能

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

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

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

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

4 結論

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

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

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

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

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

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

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

[5]任豐原,林闖,劉衛東.IP網絡中的擁塞控制[J].計算機學報,2003,26(9)：1025-1034.

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

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

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