一種分段平滑的隨機早期檢測隊列管理算法

收稿日期：2014－04－23

基金項目：內蒙古自然科學基金項目（2011MS0916）。

作者簡介：趙宇紅（1974-），女，內蒙古包頭人，碩士，副教授，主要研究方向：復雜網絡建模、智能控制；

白雪冰（1986-），男，內蒙古包頭人，碩士研究生，主要研究方向：AQM；

張曉琳（1986-），女，內蒙古包頭人，博士，教授，主要研究方向：數據庫理論與技術。

摘要：隨機早期檢測算法（RED）的性能受其參數設置的影響較大，并且該算法中的可設置的參數較多。同時，以早期隨機檢測算法（RED）計算得到的丟包概率的變化過于激進，在網絡負載變化較快時，平均隊列長度抖動幅度較大，算法性能不夠穩定。為了克服以上問題，這里提出一種新的改進思路——隨機早期平滑分段算法（RED-P）。該算法采用二次函數分段計算丟包概率，使得丟包概率變化更加平滑，同時對概率計算公式進行了簡化，減少了計算所需的參數量，適度的避免了參數設置對算法性能的影響。經過網絡模擬平臺NS2的網絡模擬仿真實驗的對比，結果表明新算法在端到端的延時方面和平均隊列長度抖動幅度方面都有所改善，且可獲得與原算法幾乎接近的吞吐量，提高了服務質量。

關鍵詞：RED； 隊列管理； 擁塞控制； 抖動; RED-P

中圖分類號：TP301.6文獻標識碼：A文章編號：2095-2163（2014）03-0015-04

An Improved Random Early Detection Queue Management Algorithm

ZHAO Yuhong， BAI Xuebing， ZHANG Xiaolin

(School of Information Engineering， Inner Mongolia University of Science and Technology， Baotou Inner Mongolia 014010， China)

Abstract：The performance of the RED algorithm is greatly affected by its parameter settings and there is more parameters need to be set ， at the same time ， the change of dropping packets probability computing by RED algorithm is too radical ， the faster the change of network load is ， the more the jitter amplitude of average queue length is ， which means the algorithm performance is unstable. In order to overcome the problems above ， this paper presents a new improvement ideas-Red-P . This algorithm calculates the probability of dropping packets piecewisely by using the quadratic function ， making the change of probability of dropping packets more gentle ， meanwhile ， simplifys the probability calculation formula ， decreases the number of parameters the calculation needs ， properly avoids the influence of parameter settings of the algorithm performance. Through the contrast of NS2 simulation experiment ， the result shows that the new algorithm is improved on end-to-end delay and jitter amplitude of average queue length ， in addition ， this algorithm obtains the throughput which is close to the original algorithm ， improves the quality of service .

Key words：RED; Queue Management; Network Congestion Control; Jitter; RED-P

0引言

如今，在迅速發展的網絡系統中，網絡擁塞的情況已經越發嚴重，對于網絡擁塞［1-2］問題的控制也愈顯迫切。其中，TCP/IP［3-4］ 協議下的擁塞控制機制是大多數研究者的主要研究對象。雖然TCP/IP 協議下的擁塞控制機制研究已取得了一定的成果，但是在公平性、靈活性和端節點負擔等方面仍存在一些問題。某些研究人員關于 TCP 端到端擁塞控制部分在進行了眾多的嘗試與努力后卻發現，現存問題仍然并未獲得很好的解決［5-6］，于是開始轉變研究方向，由對發送端擁塞控制的研究轉向對網絡中間節點擁塞控制的研究，以此來對網絡擁塞實現更好的避免與控制。并且中間節點是最早了解網絡負載情況的，所以能夠根據網絡負載情況在第一時間進行鏈路資源調節，從而可以達到對擁塞做出實時反應的目的。研究中，路由緩存隊列管理機制就是中間節點控制擁塞的重要組成部分，可將其大致分為被動隊列管理(PQM)以及主動隊列管理(AQM)［7-8］兩種方式。

被動隊列管理并沒有對網絡負載情況進行預測并采取措施，而是在緩沖溢出時才會丟棄或標記數據包。所以說，這是一種被動的隊列管理方式。但是，隨著緩沖區的溢出就會造成發送端全局同步、死鎖以及緩沖區隊列長度振蕩較大等問題，繼而就有學者提出了主動隊列管理的思想。

1993 年，Floyd 等人［9］提出了一種主動隊列管理機制——隨機早期檢測（RED）算法。這是一種對緩沖區隊列長度先進行預測，同時根據預測值的大小采取相應措施的方法。只是，隨機早期檢測（RED）算法中需要設置的參數較多，并且參數設置的變化在很大程度上會影響算法性能，同時不同網絡負載對算法性能影響也會較大。為了克服以上問題，本文提出一種新的改進思路——分段平滑的隨機早期檢測隊列管理算法（RED-P）。

1RED算法

RED（Random Early Detection）的基本思想是對下一時刻的隊列長度進行預測，再以此預測值為基礎計算丟包概率，并根據計算得到的丟包概率值對數據包進行預先丟棄，以避免擁塞的發生。其中關鍵就是如何按照預測值計算丟包概率。在 RED算法中，引入了兩個重要的參數，minth和maxth，分別表示隊列門限的最大值與最小值，可用于擁塞檢測。具體計算過程闡述如下：

當一個數據分組進入路由時，主要按如下兩個步驟來執行算法。

第一步計算平均隊列長度:

當前隊列為空時：

m=f(t)（1）

avgn=(1-wq)mavgn-1（2）

當前隊列不為空時：

avgn = (1-wq )avgn-1 + wq（3）

其中，t表示隊列空閑時間，f表示關于空閑時間t的線性函數，avgn表示本次將要計算的平均隊列長度，avgn-1則表示前一次計算隊列的平均隊列長度，而wq表示當前隊列權重。

第二步 依據所得到的平均隊列長度avgn的值計算丟包概率。

當avgn ≥maxth時，pb=1，即到達的所有數據包將會全部丟棄;當avgn ＜minth時，接收所有到達的數據包;當minth ≤avgn ＜maxth時，先計算概率，再以此概率來決策丟包行動。具體公式為：

Pb=maxp×avgn-minthmaxth-minth（4）

Pa=Pb1-count×Pb（5）

其中，maxth表示平均隊列長度上閾值，minth表示平均隊列長度下閾值，pb表示過渡概率值。平均隊列長度avgn在區間（minth，maxth）不斷增大時，pb呈線性增加，從0增加到maxp，如圖1 所示。maxp表示預先設定好的最大概率值，pa表示最終丟棄概率，Count則表示上次丟棄分組后到當前所接受分組數。

在計算最終丟包概率時，加入一個count值，也就是上次丟包后收到的數據包個數。這樣做是為了使得丟包的間隔時間能夠均勻一些，不會因為連續丟包而導致對某一個突發數據流的丟包數量就將偏大現象的發生。第3期趙宇紅，等：一種分段平滑的隨機早期檢測隊列管理算法智能計算機與應用第4卷

圖1丟包概率計算原理圖

Fig.1The principle diagram of the packet loss

probability calculationRED算法的缺陷之一就是丟包概率在不同的網絡負載程度中變化過快，也就是對網絡負載程度的變化較為敏感。如果網絡負載較輕或maxp較大時，avgn接近minth; 如果擁塞比較嚴重或maxp 較小，則avgn接近maxth，尤其avgn超過maxth時，丟包概率將直接突變為1，過于陡峭。同時也可以看到，RED算法對參數的設置也比較敏感，例如上面所說的maxp等。參數設置為不同數值時，算法性能就會產生重大變化。上述這兩個問題也是造成avgn抖動劇烈的主要原因，由此也將導致算法性能的不穩定。avgn作為實際隊列長度的預測量，對實際隊列長度也具有很好的指示作用，為此可將avgn的變化程度作為算法性能目標來對算法性能展開判斷。相應地，降低avgn的抖動幅度就具有十分重要的意義和價值。

2RED-P算法

2.1問題分析

為了改善RED 算法中的以上兩個問題，這里提出針對性的改進思路。具體分析如下。

首先，解決對參數maxp設置敏感的問題。maxp是一個大于0、小于1的常數，根據過渡概率值pb的計算公式，即公式（4）可知，maxp可對pb起到一個適度調小的作用，但maxp的設置卻引入了一定劣勢，如取值。為此，可以通過加大原始比例分母的方法來達到同樣調小概率的目的，即將分母的區間長度由maxth-minth增加為Qmax-minth。這樣既可以減少算法性能對參數設置的敏感性，同時也避免了RED算法中，當avgn超過maxth時丟包概率突變為1的問題，其實現原理如圖1所示，原RED算法中pb的計算公式也由pb=maxp*(a/b)，改進為pb=a/c。

其次，解決RED算法性能不穩定的問題。在原RED算法中，pb是基于avgn的一個線性函數，若pb的變化較快則會導致avgn也隨之發生很快變化，以及高抖動，由此即進入惡性循環，最終則造成算法性能不穩定。此處采用二次函數來完成概率計算，見公式（6）：

Pb=avgn-minthQmax-minth2，avgn∈(minth，Qmax)（6）

即pb=（a/c）2可以緩解這一問題。

二次函數較線性函數來說具有天然的非線性特性，在關鍵參數已知的情況下，可以使得二次函數的變化率始終大于線性函數的變化率，這就決定了利用二次函數計算得到的結果更小，丟包概率也將更為平滑，并減小了隊列的抖動，因而采用二次函數既可以滿足所需求的丟包概率，也可以減緩丟包概率變化速度，并減小平均隊列長度avgn的抖動，進一步增強了算法的穩定性。同時，也能夠減小端到端的延時，這一點即可從下文的仿真結果中得到明確的驗證。

公式（6）下的算法命名為RED-T，其中Qmax為隊列物理緩沖的最大長度。該算法不需如RED一樣分別設置maxp和maxth，而是只需設置Qmax，因此RED-T比RED的設置參數要更少，即適度減小了算法性能對參數設置的敏感性。仿真驗證，算法取得了良好的效果。

但是，在仿真分析的過程中，發現該算法仍然存在一定缺陷，即當網絡負載較高時，二次函數的計算會將丟包概率調小，從而無法在高負載時對擁塞實施有力控制。為應對這一狀況，對算法實行了進一步的改進，通過控制不丟包概率來控制丟包概率。

2.2RED-P算法描述

采用不丟包的概率只需將分子區間由avgn-minth改為Qmax-avgn即可，如圖1中不丟包概率為1-a/c=d/c，同理仍然對保留概率進行平方計算，而后用1減去保留概率的平方即可，如公式（7）：

Pb=1-Qmax-avgnQmax-minth2，avg∈(minth，Qmax)（7）

即pb=1-（d/c）2。

這樣的話就將保留概率適當調小，并適度地放大了丟包概率，在滿足概率變化平滑性的同時，也部分放大了概率值，當網絡負載較為嚴重時，丟包概率也不會過小，由此可以對擁塞進行有效控制。公式（7）下的算法命名為RED-S（RED-Smooth）。

RED-S算法pb計算概率則如公式（7）所示。

但是，這個方案同樣存在類似的問題，對丟包概率的適度放大并沒有分段，當負載不嚴重時，概率也將適當放大，這樣就有可能會使得低負載時的丟包數量增多，并降低吞吐量。所以這里在區間（minth，Qmax）范圍內找到中點P，將區間（minth，Qmax）分隔為相等的兩個區間（minth，P）以及（P，Qmax）。當avgn位于區間（minth，P）時，采用公式（6）對過渡概率進行計算。當avgn位于區間（P，Qmax）時，采用公式（7）對過渡概率進行計算。綜合公式如公式（8）所示。

pbpb=avgn-minthQmax-minth2，avgn∈(minth，P)

pb=1-Qmax-avgnQmax-minth2，avg∈(P，Qmax)(8)

這樣的話就既可以保證網絡負載較高時算法對擁塞的控制力度，同時也可以在網絡負載較低時保證相應的吞吐量，避免過度丟包。這就是本文提出的算法RED-P(RED-Paragraphing)。

RED-P通過擴大概率計算比例的分母區間省略了maxp的參數設置，也減小了算法的參數敏感性。同時，利用二次函數特性來增加丟包概率變化的平滑性，由此而減小avgn的抖動率。再通過反面控制來保證需求的丟包概率大小，并且在不同區間采用了不同公式計算丟包概率，這就在增加擁塞控制力度的同時，進一步保證了吞吐量。當平均隊列長度在［minth，Qmax］變化時，pb概率將在［0，1］之間平滑過渡。

3RED-P算法的仿真和結果分析

在NS2下構建如圖2 所示的仿真網絡拓撲。由圖2可見，源端S1～Sn均為TCP 發送端，分別向終端D1～Dn一一對應發送數據，即Si發送數據，而由Di接收。S1～Sn均為持續性FTP源，到R0的鏈路速率為10Mbps，延時2 ms。R0-R1為瓶頸鏈路，鏈路速率為1.5 Mbps ，延時20 ms。R1到D1~Dn鏈路速率為10 Mbps，延時2ms。n為120。R0-R1節點緩存隊列長度均為300 packets，數據包大小為1 000 packets，接收窗口設置足夠大，使得TCP的發送僅受擁塞窗口的控制。

圖2 仿真網絡拓撲結構

Fig.2The simulation network topology3.1仿真實驗的描述

圖2中t=1秒時，開始啟動30個TCP發送端，30秒啟動90個TCP發送端，60秒后停止90個TCP的發送端，100秒停止120個發送端，仿真結束。瓶頸鏈路隊列管理分別采用RED，RED-T，RED-S以及RED-P。RED 的參數設置maxth =150packets，minth=15 packets，其余參數為NS2［10］默認。RED-T，RED-S以及RED-P的參數設置:minth = 15 packets，Qmax= 250packets。仿真結果分別對端到端的延時、隊列的平均長度、還有吞吐量進行了比較，詳細仿真結果分別如圖3 ～5所示。

3.2仿真實驗的分析

圖3中，delay1、delay2 、delay3以及delay4為使用原RED算法、算法RED-T、算法RED-S以及RED-P下得到的延時。從仿真結果來看，RED-P算法在端到端的延時方面性能最優。

圖3 端到端延時的對比

Fig.3The contrast of end-to-end delay 圖4中，AVG1、 AVG2、 AVG3、 AVG4分別為原RED算法、RED-T、RED-S以及RED-P算法所得到的平均隊列的長度。由圖4可以看出RED算法得到的AVG波動曲線其波動范圍大大超過了RED-T、 RED-S以及RED-P的波動范圍，且由RED-P算法得到的平均隊列長度的波動最小，且抖動率最低。

圖4 平均隊列長度的對比

Fig.4The contrast of avgn圖5中，Th1、Th2 、Th3以及Th4分別為使用原RED算法、RED-T算法、RED-S算法以及RED-P算法得到的吞吐量。仿真顯示，三種算法得到的吞吐量是比較接近的。

圖5 吞吐量的對比

Fig.5The contrast of throughput仿真表明，本文提出的RED-P算法能有效改進RED的參數敏感性以及網絡負載敏感性的問題，簡化了參數設置，在瓶頸段端到端的延時更小，同時更減小了平均隊列的波動范圍與抖動幅度，并且能維持幾乎接近的吞吐量。

4結束語

為了改進RED算法中平均隊列長度對網絡負載程度以及參數設置較為敏感的問題，提出了一種改進的算法RED-P。RED-P采用分段正反面控制并且將二次函數融入丟包概率的計算，適當地減少了參數的數量，并有效改進了算法的性能。最后通過NS2仿真實驗進行了驗證，得到了較為理想的仿真效果，使得平均隊列長度的抖動幅度得到了有效控制，同時也減小了算法在瓶頸段端到端的延時，而且能保持接近或者相等的吞吐量，進而提高了服務質量。

參考文獻：

［1］徐昌彪，鮮永菊.計算機網絡中的擁塞控制與流量控制 ［M］.北京:人民郵電出版社，2007.

［2］馮峰.互聯網絡擁塞控制分析與研究［J］.計算機工程與科學，2008，30(6):37-39.

［3］劉俊，童學紅.TCP 擁塞控制算法［J］.計算機工程與設計， 2011，32(7):2309-2313.

［4］魏佳杰，郭曉金.TCP 擁塞控制技術研究［J］.現代電子技術， 2009，32(15):2-4.

［5］FUKATUS T， KIURA T， HIRAFUJI M. A web-based sensor system with distributed data processing approach via web application［J］.Computer Standards Interface，2011，33(6): 565-573.

［6］暴建民.物聯網技術與應用導論［M］.北京:人民郵電出版社，2011.

［7］吳俊新，趙旭，張宇獻，等.主動管理隊列算法的研究［J］.控制工程，2008，15(2):178-181.

［8］SABATO M， MARIO B， FRANCO G. Design validation and experim- ental testing of a robust AQMcontrol ［J］. Control Engineering Practice， 2009， 19(3): 1-6．

［9］FUKATSU T， HIRAFUJI M．Field monitoring using sensor-nodes with a Web server［J］.Journal of Robotics and Mechatronics，2005，17(2):164-172.

［10］USC/ISI.The NS simulator and the documentation［EB/OL］ .http://www.isi.edu/nsnam/ns/，2013 September.