閆英戰(zhàn)，田立偉

(廣東科技學(xué)院計(jì)算機(jī)系,廣東東莞 523083)

一種基于排隊(duì)論的主動(dòng)隊(duì)列擁塞控制算法

閆英戰(zhàn)*，田立偉

(廣東科技學(xué)院計(jì)算機(jī)系,廣東東莞 523083)

主動(dòng)隊(duì)列(AQM)算法存在諸多的不足，如排隊(duì)延時(shí)大、時(shí)延抖動(dòng)性強(qiáng)、數(shù)據(jù)進(jìn)隊(duì)與出隊(duì)速率不匹配等，從而導(dǎo)致數(shù)據(jù)的滯留、丟失和振蕩．基于此，在BLUE算法的基礎(chǔ)上，引入M/M/m (n)排隊(duì)系統(tǒng)的思想，提出一種新的算法——PBLUE．該算法根據(jù)穩(wěn)定狀態(tài)下的平衡方程來(lái)保證隊(duì)列長(zhǎng)度的穩(wěn)定性，增加擴(kuò)充因子調(diào)節(jié)路由器的緩存來(lái)快速恢復(fù)丟失的數(shù)據(jù)．通過(guò)仿真實(shí)驗(yàn)，改進(jìn)的算法降低了丟包率，提高了帶寬利用率，并穩(wěn)定了隊(duì)列長(zhǎng)度．

排隊(duì)論； 主動(dòng)隊(duì)列； BLUE； 帶寬利用率； 丟包率； 隊(duì)列長(zhǎng)度

目前常見(jiàn)的主動(dòng)隊(duì)列管理算法有：RED,PI,REM,BLUE[1],AVQ等．作為中間路由管理算法，他們共同的目標(biāo)就是期望在減小排隊(duì)時(shí)延的同時(shí)保證較高的吞吐量和帶寬利用率，并減小丟包率．綜合比較之下，BLUE算法表現(xiàn)得最為優(yōu)秀，但在鏈路狀態(tài)不穩(wěn)定時(shí)，隊(duì)列依舊會(huì)發(fā)生較大的振蕩．基于此，很多學(xué)者從不同的方面對(duì)BLUE算法進(jìn)行了改進(jìn)[2-4]:文獻(xiàn)[2]依據(jù)平均隊(duì)列長(zhǎng)度，動(dòng)態(tài)調(diào)整BLUE算法丟包率的控制參數(shù)d1和d2，同時(shí)在tcp連接數(shù)不斷突變的情況下，動(dòng)態(tài)調(diào)整P的值和提高算法的刷新速度，降低了丟包率；文獻(xiàn)[3]依據(jù)模糊控制理論，細(xì)化了丟包概率控制步長(zhǎng)d的值，提高了帶寬利用率，維持了隊(duì)列長(zhǎng)度；文獻(xiàn)[4]根據(jù)隊(duì)列負(fù)載因子控制丟包步長(zhǎng)，穩(wěn)定隊(duì)列長(zhǎng)度在一定的范圍內(nèi)，從而使丟包率能夠自適應(yīng)并調(diào)節(jié)，隊(duì)列收斂時(shí)間短，丟包率?。@些算法都有效提高了算法的魯棒性和實(shí)用性．本文引入M/M/m(n)排隊(duì)系統(tǒng)模型的思想，解決系統(tǒng)的服務(wù)質(zhì)量與系統(tǒng)效率之間的矛盾，以期能壓縮排隊(duì)長(zhǎng)度、減小等待時(shí)間．通常采用2種措施：一是增加路由結(jié)點(diǎn)(窗口)，可提高總服務(wù)率但意味著投資加大；二是穩(wěn)定排隊(duì)長(zhǎng)度，提高系統(tǒng)效率和穩(wěn)定性．

1 BLUE算法簡(jiǎn)析

1.1BLUE算法

BLUE算法提出了用丟包概率P來(lái)標(biāo)記數(shù)據(jù)包．如果鏈路空閑導(dǎo)致隊(duì)列空或者隊(duì)列長(zhǎng)度較小，BLUE就減小概率P的值．相反，如果隊(duì)列有較大溢出導(dǎo)致數(shù)據(jù)持續(xù)的丟失，BLUE算法就增加概率P的值，同時(shí)增加了向發(fā)送端反饋擁塞狀態(tài)的速度．這樣BLUE就能有效地控制反饋擁塞通知信息的速度．其具體算法如下所示[1]：

Upon the queue overflows lead to greater sustained loss of data:

if ((now-last_update)>f_time)

{P = P+d1;last_update = now;}

Upon link idle event lead to queue empty or queue length smaller:

if ((now-last_update)>f_time)

{P = P-d2;last_update = now;}

BLUE的主要參數(shù)有d1、d2和f_time．其中，d1決定了當(dāng)隊(duì)列溢出時(shí)P增加的量，d2決定了當(dāng)鏈路空閑時(shí)P減少的量．f_time決定了連續(xù)改變P的最小時(shí)間間隔，使得P改變之后在再次變化之前能有效發(fā)揮作用，是一個(gè)控制周期．一般來(lái)說(shuō)，d1要比d2大，因?yàn)閬G包只發(fā)生在擁塞管理太保守時(shí)．這樣，通過(guò)賦予丟包事件更大的比重，BLUE能夠?qū)α髁垦杆俚脑黾雍芸斓刈鞒龇磻?yīng)．

1.2Blue算法的優(yōu)缺點(diǎn)

BLUE基于丟包事件和鏈路空閑事件的擁塞管理，能夠較好地估計(jì)擁塞程度，作出適當(dāng)?shù)姆磻?yīng)．因?yàn)闃?biāo)記數(shù)據(jù)包的丟包概率P相對(duì)較穩(wěn)定，使得隊(duì)長(zhǎng)也相對(duì)穩(wěn)定，從而減小了延遲抖動(dòng)．而RED基于平均隊(duì)長(zhǎng)的擁塞管理，由于不能正確及時(shí)地估計(jì)擁塞嚴(yán)重性，特別是在負(fù)荷很重、變化很快的情況下，常常導(dǎo)致隊(duì)長(zhǎng)波動(dòng)很大，增加了丟包數(shù)和延遲抖動(dòng)，甚至產(chǎn)生全局同步現(xiàn)象，降低鏈路使用率．但是BLUE算法仍然存在以下缺點(diǎn)：一是由于發(fā)生丟包事件后BLUE會(huì)相對(duì)大的增加丟包概率，從而會(huì)產(chǎn)生連續(xù)丟包，導(dǎo)致TCP陷入超時(shí)，嚴(yán)重時(shí)會(huì)降低鏈路利用率．二是參數(shù)f_time的設(shè)置問(wèn)題．如果f_time太小，會(huì)導(dǎo)致P的變化過(guò)于頻繁，使得擁塞管理很激進(jìn)；如果f_time太大，P的變化很緩慢，從而使得擁塞管理很保守，不能適應(yīng)流量的快速變化．

2 M/M/m(n)排隊(duì)系統(tǒng)模型

2.1模型簡(jiǎn)介

圖1 M/M/1/K排隊(duì)系統(tǒng)模型

圖2 M/M/1/K的排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移

2.2瞬態(tài)方程及其解

現(xiàn)考察區(qū)間(0，t+△t),它可看成(0,t]∪(t,t+△t)．于是，可以把n個(gè)數(shù)據(jù)包的到達(dá)這個(gè)事件分解為以下事件的合并:在(0,t]內(nèi)到達(dá)n+1個(gè)數(shù)據(jù)包,在(t,t+△t)內(nèi)離開(kāi)一個(gè)數(shù)據(jù)包；在(0,t]內(nèi)到達(dá)n-1個(gè)數(shù)據(jù)包,在(t,t+△t)又到達(dá)一個(gè)數(shù)據(jù)包；在(0,t]內(nèi)到達(dá)n個(gè)數(shù)據(jù)包,在(t,t+△t)內(nèi)數(shù)據(jù)包的到達(dá)數(shù)為0．時(shí)間間隔t(不失一般性,可設(shè)為(0,t]區(qū)間)內(nèi)有n個(gè)數(shù)據(jù)包到達(dá)的概率記為Pn(t)．故而可列出以下瞬態(tài)方程[5]:

(1)

M/M/1/n的穩(wěn)態(tài)解為：

Pn=(1-ρ)ρn(n=0,1,2,…),

(2)

平均隊(duì)長(zhǎng)為：

(3)

由Little定理,時(shí)延為：

(4)

2.3穩(wěn)定狀態(tài)下的平衡關(guān)系

設(shè)所有到達(dá)間隔和服務(wù)時(shí)間都是服從泊松(指數(shù))分布的,那么從任何時(shí)刻直到狀態(tài)變化的這段時(shí)間也是泊松(指數(shù))分布的．對(duì)于M/M/1，表1展示了平衡方程的進(jìn)入率與離開(kāi)率的對(duì)應(yīng)關(guān)系．

表1 平衡對(duì)應(yīng)關(guān)系Table 1 Balance correspondence relationship

3 改進(jìn)的算法—PBLUE

3.1算法基本思想

采用多次排隊(duì)-多窗口串列排隊(duì)系統(tǒng)．該系統(tǒng)中，設(shè)數(shù)據(jù)流是參數(shù)為的泊松流(指數(shù)流)，表示單位時(shí)間到達(dá)的數(shù)據(jù)包個(gè)數(shù)(到達(dá)率)，從而數(shù)據(jù)包到達(dá)間隔時(shí)間服從參數(shù)為的負(fù)指數(shù)分布，平均到達(dá)間隔時(shí)間為1/，到達(dá)的數(shù)據(jù)能全部進(jìn)入系統(tǒng)接受服務(wù)．處理一個(gè)數(shù)據(jù)包的服務(wù)時(shí)間V服從參數(shù)為μ的負(fù)指數(shù)分布，平均服務(wù)時(shí)間為1/μ．且設(shè)服務(wù)時(shí)間與到達(dá)間隔時(shí)間相互獨(dú)立，ρ=/μ稱為服務(wù)強(qiáng)度．

下面考慮中間系統(tǒng)(圖3)構(gòu)成的排隊(duì)系統(tǒng)．

圖3 多次排隊(duì)-多窗口串列

Figure 3 Multiple queue - multiple window series

在原有BLUE算法機(jī)制基礎(chǔ)上，本文提出基于排隊(duì)論的改進(jìn)算法——PBLUE．該算法的核心思想是針對(duì)服務(wù)強(qiáng)度、路由器緩沖區(qū)和鏈路環(huán)回時(shí)間等3方面進(jìn)行改進(jìn)的，具體做法如下：

第一：根據(jù)穩(wěn)定狀態(tài)下的平衡方程，用ρ來(lái)表征對(duì)系統(tǒng)穩(wěn)定性的影響：若ρ<1，即<μ時(shí)，說(shuō)明平均到達(dá)系統(tǒng)的數(shù)據(jù)包數(shù)小于平均離開(kāi)系統(tǒng)的數(shù)據(jù)包數(shù)．這時(shí)系統(tǒng)是穩(wěn)定的，可以采取遞增方式．若ρ≥1，即≥μ時(shí)，說(shuō)明平均到達(dá)系統(tǒng)的數(shù)據(jù)包數(shù)多于平均離開(kāi)系統(tǒng)的數(shù)據(jù)包數(shù)．這時(shí)應(yīng)該采用擁塞控制方式，即提高向發(fā)送端反饋擁塞狀態(tài)的速度，限制系統(tǒng)內(nèi)的數(shù)據(jù)包數(shù)量，保證系統(tǒng)的穩(wěn)定性．

第二：增加擴(kuò)充因子△n調(diào)節(jié)路由器緩沖區(qū)的空間，根據(jù)數(shù)據(jù)包序列號(hào)進(jìn)行判斷，如果當(dāng)前收到的數(shù)據(jù)包序列號(hào)不是上個(gè)數(shù)據(jù)包序列號(hào)加1,并且當(dāng)前數(shù)據(jù)包序列號(hào)小于上個(gè)數(shù)據(jù)包序列號(hào)加△n，那么就空出緩沖位置重新接收2個(gè)序列號(hào)之間的數(shù)據(jù)；反之如果當(dāng)前數(shù)據(jù)包序列號(hào)大于上個(gè)數(shù)據(jù)包序列號(hào)加△n，那么就丟棄該數(shù)據(jù)包[6]．△n的大小設(shè)置采用下式所示:

(5)

3.2算法代碼描述

(1)擁塞控制的調(diào)整.

當(dāng)隊(duì)列增加新的數(shù)據(jù)包后：

//認(rèn)為是隊(duì)列緩存嚴(yán)重溢出

P=P+d1; //增加丟包率

cwnd=cwnd*m; //通過(guò)調(diào)控因子m減小發(fā)送窗口的值

end if

P=P+d1/2;cwnd=cwnd+(1/cwnd)*m;

end if

P=P-d2; //減小丟包率

cwnd=cwnd^2; //保持發(fā)送窗口指數(shù)增長(zhǎng)

end if

(2)對(duì)路由器緩存和隊(duì)列長(zhǎng)度的調(diào)整.

當(dāng)有新的數(shù)據(jù)包進(jìn)入隊(duì)列后：

//j為當(dāng)前數(shù)據(jù)包的序列號(hào)，i為上一個(gè)數(shù)據(jù)包的序列號(hào)，p_len為緩存區(qū)長(zhǎng)度

end if

p_len=p_len; //保持緩存長(zhǎng)度，丟棄該數(shù)據(jù)包

end if

4 仿真實(shí)驗(yàn)

采用NS-2仿真平臺(tái)對(duì)以上改進(jìn)做仿真實(shí)驗(yàn)．記錄瓶頸鏈路的帶寬利用率、丟包率和隊(duì)列長(zhǎng)度,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖4所示．網(wǎng)絡(luò)相關(guān)參數(shù)為：發(fā)送端和接收端的帶寬為1 Gb/s，時(shí)間延遲為10 ms．瓶頸鏈路帶寬為100 Mb/s，時(shí)間延遲為20 ms，模擬時(shí)間為50～100 s．PBLUE算法中的參數(shù)設(shè)置如下：R1到R2之間的隊(duì)列緩存初始長(zhǎng)度為100個(gè)數(shù)據(jù)包，d1=0.000 15，d2=0.000 015，f_time=10 ms[3],m=0.5或m=0.4[7]，模擬時(shí)間50～100 s．

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

實(shí)驗(yàn)一：3個(gè)協(xié)議流共享瓶頸帶寬．它們分別是2個(gè)中間隊(duì)列算法為BLUE的TCP協(xié)議流和1個(gè)UDP流；2個(gè)中間隊(duì)列算法為PEBLUE[2]的TCP協(xié)議流和1個(gè)UDP協(xié)議流；2個(gè)中間隊(duì)列算法為PBLUE的TCP協(xié)議流和1個(gè)UDP協(xié)議流．由圖5可以看出新算法每條TCP流的帶寬利用率比PEBLUE有所提高，與BLUE算法相比有較大的提高．由表2可以看出2條PBLUE流的帶寬利用率比2條BLUE流的利用率高出大約12%.

由表3看出，新算法PBLUE在瓶頸鏈路的丟包率大大降低．BLUE算法的丟包率為0.545%，而PBLUE算法的丟包率是0.281%，新協(xié)議丟包率降低了46.2%．

圖5 BLUE/PEBLUE/PBLUE的帶寬利用率比較

Figure 5 BLUE/PEBLUE /PBLUE bandwidth utilization comparison

表2 BLUE、PEBLUE和PBLUE的平均帶寬利用率的比較

Table 2 BLUE、PEBLUE、PBLUE comparison of the average bandwidth utilization

AQMBLUEPEBLUEPBLUE帶寬利用率/%74.5076.4486.28

表3 BLUE/PBLUE在瓶頸鏈路上的丟包率比較

Table 3 BLUE/PBLUE packet loss rate comparison on the bottleneck link

AQMBLUEPBLUE發(fā)送包數(shù)1430613163丟包數(shù)7837丟包率/%0.5450.281

實(shí)驗(yàn)二：設(shè)置瓶頸帶寬為100 M，分別讓BLUE流、PEBLUE流和PBLUE流通過(guò)，測(cè)得BLUE算法、PEBLUE算法和PBLUE算法瞬時(shí)隊(duì)列長(zhǎng)度如圖6、圖7和圖8所示(通過(guò)計(jì)算BLUE算法的隊(duì)列長(zhǎng)度方差為447.83，而PBLUE算法的隊(duì)列長(zhǎng)度的方差為125.26),顯然BLUE算法隊(duì)列長(zhǎng)度抖動(dòng)大，隊(duì)列保持不穩(wěn)定狀態(tài)；觀察PEBLUE算法前期隊(duì)列長(zhǎng)度集中收斂，隨著擁塞的發(fā)生，隊(duì)列波動(dòng)偏大；而PBLUE算法隊(duì)列長(zhǎng)度相對(duì)穩(wěn)定集中，這樣有利于中間路由的存儲(chǔ)和轉(zhuǎn)發(fā)，也有效避免擁塞的發(fā)生．

圖6 BLUE流的瞬時(shí)隊(duì)列長(zhǎng)度

圖7 PEBLUE流的瞬時(shí)隊(duì)列長(zhǎng)度

圖8 PBLUE流的瞬時(shí)隊(duì)列長(zhǎng)度

5 結(jié)束語(yǔ)

本文借助排隊(duì)論的一些思想，結(jié)合BLUE算法原有的機(jī)制，對(duì)算法進(jìn)行改進(jìn)．實(shí)驗(yàn)結(jié)果表明新算法在帶寬利用率和丟包率方面有所改善，并保持排隊(duì)長(zhǎng)度相對(duì)穩(wěn)定，但在算法的友好性和公平性方面仍需加強(qiáng)．總之，引入排隊(duì)論理論[8]、模糊控制理論[3]、非線性動(dòng)力學(xué)理論等方面的知識(shí)來(lái)改善網(wǎng)絡(luò)擁塞控制算法是一個(gè)值得努力的方向．

[1] FENG W C，SHIN Kang G，KANDLUR D, et al.The blue active queue management algorithms IEEE /ACM transactions on networking[J].August，2002，10(4)：513-528．

[2] 楊云，徐佳，王秋平，等.一種精確度加強(qiáng)的主動(dòng)隊(duì)列管理算法PEBLUE[J].小型微型計(jì)算機(jī)系統(tǒng)，2006,27(4).592-595.

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

[4] 陳偉杰，王萬(wàn)良，蔣一波, 等. SABlue：一種帶加速因子的自適應(yīng)AQM算法[J]，電子與信息學(xué)報(bào)，2011，33(2)，479-484.

[5] 盛友招. 排隊(duì)論及其在現(xiàn)代通信中的應(yīng)用[M]. 北京：人民郵電出版社，2007.

[6] 趙躍華，徐勝芹. 排隊(duì)論在AQM網(wǎng)絡(luò)傳輸中的應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2008,29(15):3870-3871; 4085.

[7] 張瑞，洪佩琳，李津生，等. 無(wú)線網(wǎng)絡(luò)中一種改進(jìn)的TCP 擁塞控制機(jī)制 [J]. 電路與系統(tǒng)學(xué)報(bào)，2006:7-13.

[8] 于國(guó)防，王耀才，莊立運(yùn)，等.基于分配器隊(duì)列模糊控制的集群負(fù)載平衡[J].計(jì)算機(jī)工程，2008,34(6):129-130;136.

Keywords： queuing theory； AQM； BLUE; bandwidth utilization; packet loss rate； queue length

ANewCongestionControlAlgorithmforActiveQueueBasedonQueuingTheory

YAN Yingzhan*, TIAN Liwei

(Department of Computer, Guangdong University of Science and Technology，Dongguan, Gunagdong 523083, China)

AQM algorithm has many deficiencies, such as a large queuing delay, strong delay jitter, the rate of the data into and out the team not matched, and thus it always leads to data retention, loss and oscillation. Based on this, the M/M/m (n) queuing system thought based on the BLUE algorithm is introduced which is called PBLUE. The algorithm ensures the stability of the queue length according to equilibrium equation under stable state. Meanwhile, it increases the expansion factor and adjusts the router’s cache for quickly recovering of the lost data. In the simulation, the improved algorithm reduced the packet loss rate and increased the bandwidth utilization and stabled the queue length.

2011-04-29

國(guó)家自然科學(xué)基金項(xiàng)目(70571017)；廣西壯族自治區(qū)自然科學(xué)基金項(xiàng)目 (0728099)

*通訊作者, 749284297@qq.com

1000-5463(2012)01-0063-04

TP393

A

【責(zé)任編輯 莊曉瓊】