一種分段平滑的隨機(jī)早期檢測隊(duì)列管理算法

收稿日期：2014－04－23

基金項(xiàng)目：內(nèi)蒙古自然科學(xué)基金項(xiàng)目（2011MS0916）。

作者簡介：趙宇紅（1974-），女，內(nèi)蒙古包頭人，碩士，副教授，主要研究方向：復(fù)雜網(wǎng)絡(luò)建模、智能控制；

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

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

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

關(guān)鍵詞：RED； 隊(duì)列管理； 擁塞控制； 抖動; RED-P

中圖分類號：TP301.6文獻(xiàn)標(biāo)識碼：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引言

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

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

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

1RED算法

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

當(dāng)一個數(shù)據(jù)分組進(jìn)入路由時，主要按如下兩個步驟來執(zhí)行算法。

第一步計算平均隊(duì)列長度:

當(dāng)前隊(duì)列為空時：

m=f(t)（1）

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

當(dāng)前隊(duì)列不為空時：

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

其中，t表示隊(duì)列空閑時間，f表示關(guān)于空閑時間t的線性函數(shù)，avgn表示本次將要計算的平均隊(duì)列長度，avgn-1則表示前一次計算隊(duì)列的平均隊(duì)列長度，而wq表示當(dāng)前隊(duì)列權(quán)重。

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

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

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

Pa=Pb1-count×Pb（5）

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

在計算最終丟包概率時，加入一個count值，也就是上次丟包后收到的數(shù)據(jù)包個數(shù)。這樣做是為了使得丟包的間隔時間能夠均勻一些，不會因?yàn)檫B續(xù)丟包而導(dǎo)致對某一個突發(fā)數(shù)據(jù)流的丟包數(shù)量就將偏大現(xiàn)象的發(fā)生。第3期趙宇紅，等：一種分段平滑的隨機(jī)早期檢測隊(duì)列管理算法智能計算機(jī)與應(yīng)用第4卷

圖1丟包概率計算原理圖

Fig.1The principle diagram of the packet loss

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

2RED-P算法

2.1問題分析

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

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

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

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

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

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

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

但是，在仿真分析的過程中，發(fā)現(xiàn)該算法仍然存在一定缺陷，即當(dāng)網(wǎng)絡(luò)負(fù)載較高時，二次函數(shù)的計算會將丟包概率調(diào)小，從而無法在高負(fù)載時對擁塞實(shí)施有力控制。為應(yīng)對這一狀況，對算法實(shí)行了進(jìn)一步的改進(jìn)，通過控制不丟包概率來控制丟包概率。

2.2RED-P算法描述

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

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

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

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

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

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

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

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

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

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

3RED-P算法的仿真和結(jié)果分析

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

圖2 仿真網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

Fig.2The simulation network topology3.1仿真實(shí)驗(yàn)的描述

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

3.2仿真實(shí)驗(yàn)的分析

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

圖3 端到端延時的對比

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

圖4 平均隊(duì)列長度的對比

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算法能有效改進(jìn)RED的參數(shù)敏感性以及網(wǎng)絡(luò)負(fù)載敏感性的問題，簡化了參數(shù)設(shè)置，在瓶頸段端到端的延時更小，同時更減小了平均隊(duì)列的波動范圍與抖動幅度，并且能維持幾乎接近的吞吐量。

4結(jié)束語

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

參考文獻(xiàn)：

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

［2］馮峰.互聯(lián)網(wǎng)絡(luò)擁塞控制分析與研究［J］.計算機(jī)工程與科學(xué)，2008，30(6):37-39.

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

［4］魏佳杰，郭曉金.TCP 擁塞控制技術(shù)研究［J］.現(xiàn)代電子技術(shù)， 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］暴建民.物聯(lián)網(wǎng)技術(shù)與應(yīng)用導(dǎo)論［M］.北京:人民郵電出版社，2011.

［7］吳俊新，趙旭，張宇獻(xiàn)，等.主動管理隊(duì)列算法的研究［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.