基于NS-2的主動(dòng)隊(duì)列管理算法的仿真研究

楊　媛，王曉喃

（常熟理工學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500）

基于NS-2的主動(dòng)隊(duì)列管理算法的仿真研究

楊媛，王曉喃

（常熟理工學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500）

主動(dòng)式隊(duì)列管理技術(shù)是IETF為了解決Internet擁塞控制問題而提出的一種路由器緩存管理技術(shù).本文使用了目前應(yīng)用較為廣泛的網(wǎng)絡(luò)仿真器NS-2，對(duì)AQM算法RED和BLUE的性能在基于NS-2仿真實(shí)驗(yàn)的基礎(chǔ)上進(jìn)行了比較研究，研究的性能包括在突發(fā)流情況下平均隊(duì)列長(zhǎng)度、丟包率和吞吐量等，并在此基礎(chǔ)上對(duì)BLUE算法在突發(fā)流情況下隊(duì)列穩(wěn)定性進(jìn)行改進(jìn).仿真結(jié)果表明在應(yīng)對(duì)突發(fā)流方面，BLUE算法的性能優(yōu)于RED算法，改進(jìn)的BLUE算法能夠更好地保持隊(duì)列的穩(wěn)定性.

網(wǎng)絡(luò)擁塞控制；主動(dòng)隊(duì)列管理（AQM）；隨機(jī)早檢測(cè)算法（RED）；（BLUE）；網(wǎng)絡(luò)仿真

隨著互聯(lián)網(wǎng)技術(shù)的高速發(fā)展，互聯(lián)網(wǎng)用戶的規(guī)模日益增大，對(duì)網(wǎng)絡(luò)擁塞控制技術(shù)的要求也越來越高.單純的依靠早期的擁塞控制（即基于源端的擁塞控制）已經(jīng)不能夠滿足當(dāng)今網(wǎng)絡(luò)的需求，必須要網(wǎng)絡(luò)本身也參與到擁塞控制中去.在Internet網(wǎng)絡(luò)中，擁塞來源于網(wǎng)絡(luò)資源和網(wǎng)絡(luò)流量分布的不均衡性，而且這種不均衡性是不可避免的.擁塞一般發(fā)生在數(shù)據(jù)傳輸路徑的中間節(jié)點(diǎn)，通常是由緩沖區(qū)溢出造成的.因此，網(wǎng)絡(luò)節(jié)點(diǎn)的隊(duì)列管理成為避免網(wǎng)絡(luò)擁塞的關(guān)鍵技術(shù)，尋求一種合理有效的隊(duì)列管理算法成為研究的一個(gè)熱點(diǎn).

1　隊(duì)列管理概述

隊(duì)列管理是網(wǎng)絡(luò)擁塞控制和服務(wù)質(zhì)量（Qos）保證的基石.Internet網(wǎng)絡(luò)主要基于存儲(chǔ)轉(zhuǎn)發(fā)和統(tǒng)計(jì)復(fù)用技術(shù).由于Internet數(shù)據(jù)流量本質(zhì)上具有突發(fā)性，因此允許傳輸突發(fā)的數(shù)據(jù)包非常必要，而路由器中隊(duì)列的重要作用就是吸收突發(fā)的數(shù)據(jù)包.較長(zhǎng)的隊(duì)列能夠吸收更多的突發(fā)數(shù)據(jù)，提高吞吐量.TCP機(jī)制往往會(huì)保持較高的隊(duì)列占用率，因而增加了數(shù)據(jù)包的排隊(duì)延遲，這就需要路由器對(duì)隊(duì)列進(jìn)行管理，維持較小的隊(duì)列長(zhǎng)度.目前，路由器有兩類與網(wǎng)絡(luò)擁塞控制相關(guān)的隊(duì)列算法：隊(duì)列管理算法和隊(duì)列調(diào)度算法.隊(duì)列管理算法主要管理網(wǎng)絡(luò)節(jié)點(diǎn)的緩存序列，決定何時(shí)接受和丟棄某一個(gè)包.隊(duì)列調(diào)度位于隊(duì)列管理之后，主要解決多個(gè)隊(duì)列中的數(shù)據(jù)包誰先輸出的問題.對(duì)隊(duì)列長(zhǎng)度進(jìn)行管理，直接影響到路由器的擁塞控制能力和Qos能力.目前，隊(duì)列管理機(jī)制主要分為兩大類，一類是以DropTail為代表的被動(dòng)式隊(duì)列管理機(jī)制（Passive Queue Manage?ment，PQM），另一類是以RED（Random Early Detection）為代表的主動(dòng)式隊(duì)列管理機(jī)制（Active Queue Man?agement，AQM）.

在Internet中，最普遍的隊(duì)列管理機(jī)制就是DropTail.其主要原理是，當(dāng)一個(gè)數(shù)據(jù)包到達(dá)隊(duì)列時(shí)，就把數(shù)據(jù)包放入隊(duì)列中等待被發(fā)送，但是由于隊(duì)列長(zhǎng)度有限，所以當(dāng)數(shù)據(jù)流很大時(shí)，隊(duì)列沒有空間暫存這些新來的數(shù)據(jù)包，就會(huì)把隊(duì)列最末端的數(shù)據(jù)包進(jìn)行丟棄.DropTail隊(duì)列管理機(jī)制的優(yōu)點(diǎn)在于，操作簡(jiǎn)單，處理速度最快，幾乎所有的平臺(tái)都支持這種隊(duì)列算法.但是，DropTail存在著諸如死鎖，滿隊(duì)列和全局同步等一系列問題.這就促使研究人員去探尋更有效的隊(duì)列管理機(jī)制.

從90年代開始，業(yè)界對(duì)AQM進(jìn)行了研究.相對(duì)于被動(dòng)式隊(duì)列管理機(jī)制，主動(dòng)式隊(duì)列管理機(jī)制會(huì)在隊(duì)列滿之前就開始把封包丟棄，以便及時(shí)地對(duì)具有擁塞控制的傳送端進(jìn)行傳送速度的管制，有效避免滿隊(duì)列狀態(tài)所帶來的較長(zhǎng)延遲時(shí)間以及鏈路利用率低的負(fù)面效應(yīng).目前，主要流行兩種AQM算法，即RED和BLUE.

本文對(duì)RED算法和BLUE算法的性能進(jìn)行了分析研究，通過仿真實(shí)驗(yàn)對(duì)兩種算法的平均隊(duì)列長(zhǎng)度，丟包率以及吞吐量等幾個(gè)方面的性能參數(shù)進(jìn)行分析比較，進(jìn)一步改進(jìn)了BLUE算法，并進(jìn)行仿真分析.

2　主動(dòng)式隊(duì)列管理算法

2.1隨機(jī)早期檢測(cè)算法RED

Floyd在1993年提出了著名的隨機(jī)早期檢測(cè)擁塞控制機(jī)制，有效地改進(jìn)了傳統(tǒng)棄尾算法.這也是目前最常用的一種主動(dòng)式隊(duì)列管理算法.RED算法是使用平均隊(duì)列長(zhǎng)度來預(yù)測(cè)即將要發(fā)生的網(wǎng)絡(luò)擁塞，并采用隨機(jī)選擇的方式對(duì)封包進(jìn)行丟棄，使得在擁塞尚未發(fā)生之前就會(huì)有擁塞控制的傳送端提示要進(jìn)行流量速度管制，以避免擁塞發(fā)生.

RED主要由兩個(gè)算法組成：

1）通過指數(shù)加權(quán)移動(dòng)平均（exponential weighted moving average）算法計(jì)算平均隊(duì)列長(zhǎng)度avgq，如公式（1）所示.其中wq為低通濾波器長(zhǎng)度，curq表示當(dāng)前實(shí)際隊(duì)列長(zhǎng)度，oldavgq表示上一時(shí)刻的平均隊(duì)列長(zhǎng)度.

2）計(jì)算丟包概率 p.RED設(shè)置了兩個(gè)平均隊(duì)列的閾值，最小丟棄門限thmin和最大丟棄門限thmax.隨著數(shù)據(jù)包到達(dá)路由器，RED計(jì)算出平均隊(duì)列長(zhǎng)度avgq.

當(dāng)avgq＜thmin時(shí)，允許所有的數(shù)據(jù)包進(jìn)入隊(duì)列；

當(dāng)avgq＞thmax時(shí)，所有的數(shù)據(jù)包均被丟棄；

當(dāng)thmin≤avgq≤thmax時(shí)，首先計(jì)算一個(gè)過渡的丟包概率 pb，如公式（2）所示.其中 pmax是最大丟包率.

其中count是上一次丟包開始到現(xiàn)在連續(xù)進(jìn)入隊(duì)列的包的數(shù)量.隨著count的增加，到達(dá)數(shù)據(jù)包被丟棄的概率也在增加，這樣做的目的是實(shí)現(xiàn)丟包間隔均勻，避免連續(xù)丟包，導(dǎo)致扼殺突發(fā)數(shù)據(jù)流和數(shù)據(jù)流同步.

2.2BLUE算法

隨機(jī)早檢測(cè)（RED）算法的一個(gè)主要目標(biāo)是使用平均隊(duì)列長(zhǎng)度和擁塞早通知來實(shí)現(xiàn)低時(shí)延和高帶寬.但是RED存在兩個(gè)缺陷：

1）對(duì)參數(shù)的設(shè)置較為敏感，改變參數(shù)的設(shè)置對(duì)性能會(huì)產(chǎn)生很大的影響.到目前為止，對(duì)RED中使用的參數(shù)還沒有明確的設(shè)定方法.

2）隨著網(wǎng)絡(luò)中“流”（Flow）數(shù)目的增加，平均隊(duì)列長(zhǎng)度也會(huì)逐漸增加.

為了解決這些問題，研究人員提出了BLUE算法.

BLUE算法的主要原理在于記錄過去的丟包率和鏈路利用狀態(tài)來管理擁塞.BLUE算法與RED算法最

然后對(duì)丟包率 p做進(jìn)一步的調(diào)整，如公式（3）所示.大的區(qū)別在于，BLUE算法使用實(shí)際隊(duì)長(zhǎng)來反應(yīng)擁塞狀況，并且使用丟包時(shí)間和鏈路空閑事件來管理擁塞，而RED算法則使用平均隊(duì)長(zhǎng)來管理擁塞.BLUE算法設(shè)定了概率prob來標(biāo)記/丟棄隊(duì)列中的包，為了避免丟包過于激進(jìn)，還設(shè)定了一個(gè)最小時(shí)間間隔freeze_time，在 freeze_time間隔內(nèi)，概率prob只能改變一次.具體算法實(shí)現(xiàn)如下：

其中qlen表示瞬時(shí)隊(duì)列長(zhǎng)度，qlim表示緩沖區(qū)隊(duì)列大小，now表示當(dāng)前時(shí)刻，last_update表示上次更新概率的時(shí)間，d1表示增加量，d2表示減少量.

一般為了能夠?qū)α髁康难杆僭黾雍芸熳龀龇磻?yīng)，需要設(shè)定d1比d2大得多.

相對(duì)于RED來說，在TCP流聚集而使得網(wǎng)絡(luò)負(fù)荷急劇變化時(shí)，BLUE的標(biāo)記概率能保持平穩(wěn)，即在一定的時(shí)間內(nèi)能隨機(jī)均勻地標(biāo)記包，因此能夠更有效地避免全局同步.

2.3改進(jìn)BLUE算法

在上述BLUE算法中，隊(duì)列長(zhǎng)度的穩(wěn)定性受到初始設(shè)定的丟包概率變化量的影響，這就使得BLUE算法無法更好地適應(yīng)多變的網(wǎng)絡(luò)環(huán)境.當(dāng)TCP流數(shù)量突增，隊(duì)列很容易出現(xiàn)溢出或者空閑的缺陷.為了解決這個(gè)問題，本文對(duì)BLUE算法進(jìn)行了改進(jìn)，使得丟包概率變化量不再是一個(gè)常量，而是隨著網(wǎng)絡(luò)環(huán)境的變化而變化.根據(jù)文獻(xiàn)［3］，丟包概率和TCP流數(shù)量之間存在著非線性的關(guān)系，因而當(dāng)TCP流數(shù)量很大時(shí)，丟包概率prob也應(yīng)該隨之增大.該算法主要是根據(jù)平均隊(duì)列長(zhǎng)度avgq大于隊(duì)列最大閾值thmax時(shí)對(duì)丟包概率變化量進(jìn)行調(diào)整.

具體改進(jìn)如下：

3　仿真與性能分析

3.1仿真配置參數(shù)

為了對(duì)上述兩種算法進(jìn)行性能分析比較，使用NS-2工具進(jìn)行了仿真.仿真實(shí)驗(yàn)中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示.假定R1到R2之間的鏈路為瓶頸鏈路，圖中所有的鏈路帶寬均為25 Mbps，延遲為10 ms.S1…Sn為發(fā)送端，D1…Dn為接收端.其中n為發(fā)送和接收節(jié)點(diǎn)的個(gè)數(shù).

仿真實(shí)驗(yàn)中用到的參數(shù)采用如下代碼設(shè)定.所有實(shí)驗(yàn)時(shí)間均為20 s，每0.5 s記錄一次數(shù)據(jù).

3.2性能分析

場(chǎng)景：TCP流從15個(gè)突變到100個(gè)，在第10秒時(shí)發(fā)生突變，仿真時(shí)間總共為20秒.

從圖2（a）可以看出，RED算法在第10秒前后平均隊(duì)列長(zhǎng)度震蕩變得更強(qiáng)烈，而且平均隊(duì)列長(zhǎng)度整體變大，這主要是由于RED算法主要使用平均隊(duì)列長(zhǎng)度來預(yù)測(cè)將要發(fā)生的擁塞狀況，如果擁塞不太嚴(yán)重，則平均隊(duì)列接近thmin，本實(shí)驗(yàn)為20；如果擁塞比較嚴(yán)重，則平均隊(duì)列接近thmax，本實(shí)驗(yàn)為80.從圖2（b）可以看出，BLUE算法在第10秒前后平均隊(duì)列長(zhǎng)度震蕩變小，而且平均隊(duì)列長(zhǎng)度整體仍然維持在突變之前的長(zhǎng)度.這說明BLUE在應(yīng)對(duì)突變方面，穩(wěn)定性比RED好.可以觀察到開始時(shí)隊(duì)列有很大的波動(dòng)，這主要是對(duì)FTP起始連接的反映.通過圖2比較這兩種算法平均隊(duì)列長(zhǎng)度，可以看出BLUE算法的平均隊(duì)列長(zhǎng)度最大，而且一直處于thmax，鏈路利用率很高，這主要是由于在BLUE算法中設(shè)置d1要比d2大很多，因此能夠?qū)α髁看罅垦杆俚卦黾雍芸熳龀龇磻?yīng)，使得平均隊(duì)列震蕩幅度較10秒之前變化不大.

圖1　仿真網(wǎng)絡(luò)拓?fù)鋱D

圖2?。╝）RED和（b）BLUE平均隊(duì)列長(zhǎng)度變化圖

圖3　RED和BLUE丟包率變化圖

圖4　RED和BLUE吞吐量變化圖

從圖3可以看出，在第10秒前后，丟包率明顯增大，而且BLUE算法有更低的丟包率.這主要是由于TCP流突然大量增加，使得隊(duì)列發(fā)生擁塞，導(dǎo)致了丟包率增大.而BLUE算法有更好的方法處理突發(fā)流現(xiàn)象.

從圖4可以看出，在相同的網(wǎng)絡(luò)環(huán)境下，BLUE算法的吞吐量比RED算法要大.還可以看出在第10秒前后，TCP流突變后RED算法的吞吐量有明顯的轉(zhuǎn)折點(diǎn)，而BLUE算法則保持一種平滑的曲線.這說明在應(yīng)對(duì)突發(fā)流方面，BLUE算法更能保持系統(tǒng)的穩(wěn)定性.

圖5　改進(jìn)的BLUE的平均隊(duì)列長(zhǎng)度

從圖5和圖2（b）比較可以看出，在第10秒后，改進(jìn)的BLUE算法應(yīng)對(duì)突發(fā)流反應(yīng)更迅速，平均隊(duì)列長(zhǎng)度較平穩(wěn)，而BLUE算法隊(duì)列相對(duì)于改進(jìn)BLUE算法變化幅度較大，這就有可能引起端到端的抖動(dòng)延遲，因此改進(jìn)的BLUE算法很好地解決了這一問題.

4　總結(jié)

本文通過NS-2實(shí)驗(yàn)對(duì)RED和BLUE兩種算法進(jìn)行了性能比較，由仿真結(jié)果分析，BLUE算法在應(yīng)對(duì)突變流方面，性能明顯優(yōu)于RED算法.RED算法由于不能夠很好控制隊(duì)列長(zhǎng)度，使得平均隊(duì)長(zhǎng)在遭遇突變流時(shí)波動(dòng)很大，從而導(dǎo)致出現(xiàn)相對(duì)較高的丟包率，進(jìn)而影響鏈路利用率.BLUE算法基于記錄過去的丟包率和鏈路利用狀態(tài)進(jìn)行擁塞管理，能夠較好地估計(jì)擁塞程度，進(jìn)而做出適當(dāng)?shù)姆磻?yīng)，所以，BLUE算法的丟包率相對(duì)較低，雖然在有突發(fā)流出現(xiàn)時(shí)丟包率增大，但是比RED算法丟包率變化幅度小.在此基礎(chǔ)上，對(duì)BLUE算法進(jìn)行改進(jìn)，仿真結(jié)果表明，改進(jìn)的BLUE算法在TCP流突變時(shí)，能夠更好地保持隊(duì)列長(zhǎng)度的穩(wěn)定.

［1］Floyd S,Jacbson V.Random early detection gateways for congestion avoidance［J］.IEEE/ACM Transactions on Networking,1993 （4）:397-413.

［2］Feng W,Kandlur D,Saha K,et al.A Self-configuring RED Gateway［C］.Proc of IEEE INFOCOM.Amsterdam:Elsecier Press, 1999.

［3］Floyd S,Fall K.Promoting the use of end-to-end congestion control in the internet［J］.IEEE/ACM Trans on Networking,1999,7（4）: 458-472.

［4］凌云，韓冬.基于NS2的隊(duì)列管理算法研究［J］.信息安全與技術(shù)，2011（11）：16-19.

［5］陳偉杰.基于主動(dòng)隊(duì)列管理的擁塞控制策略及其穩(wěn)定性研究［D］.杭州：浙江工業(yè)大學(xué)，2011.

［6］柯志亨，程榮祥，鄧德雋.NS2仿真實(shí)驗(yàn)：多媒體和無線網(wǎng)絡(luò)通信［M］.北京：電子工業(yè)出版社，2009.

［7］方路平，劉世華，陳盼，等.NS-2網(wǎng)絡(luò)模擬基礎(chǔ)與應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，2008.

［8］秦光.計(jì)算機(jī)網(wǎng)絡(luò)擁塞的高效控制方法研究［J］.計(jì)算機(jī)仿真，2012（9）：154-157.

［9］張義良.IBLUE：一種新的主動(dòng)隊(duì)列管理算法［J］.微電子學(xué)與計(jì)算機(jī)，2013，30（10）：81-84.

［10］毛鵬軒.下一代網(wǎng)絡(luò)擁塞控制關(guān)鍵算法的研究［D］.北京：北京交通大學(xué)，2013.

A Research into Active Queue Management Algorithms Based on NS-2

YANG Yuan，WANG Xiao-nan
（School of Computer Science and Engineering,Changshu Institute of Technology,Changshu 215500,China）

To address the problems of TCP end-to-end congestion control,IETF proposes deploying active queue management mechanisms in the TCP/IP networks.This paper uses the widely used network simulator NS-2,and analyzes the performance of two classical AQM algorithms RED and BLUE based on the simulation data.The performance metrics include average queue size,packet loss rate and throughput.On this basis,the pa?per proposes an improved BLUE algorithm.The result shows that in the sudden flow,BLUE algorithm has a bet?ter performance than RED algorithm and the improved BLUE algorithm can keep the queue's stabilization bet?ter than BLUE algorithm.

Internet congestion control；AQM；RED；BLUE；network simulation

TP393.04

A

1008-2794（2015）02-0086-05

2014-06-15

國(guó)家自然科學(xué)基金項(xiàng)目“基于IPv6的全I(xiàn)P無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)研究”（61202440）

通訊聯(lián)系人：王曉喃，教授，博士/博士后，碩士生導(dǎo)師，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與應(yīng)用，E-mail：wxn_2001@163.com.