基于NS-2的主動隊列管理算法的仿真研究

楊　媛，王曉喃

（常熟理工學院 計算機科學與工程學院，江蘇 常熟 215500）

基于NS-2的主動隊列管理算法的仿真研究

楊媛，王曉喃

（常熟理工學院 計算機科學與工程學院，江蘇 常熟 215500）

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

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

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

1　隊列管理概述

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

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

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

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

2　主動式隊列管理算法

2.1隨機早期檢測算法RED

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

RED主要由兩個算法組成：

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

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

當avgq＜thmin時，允許所有的數(shù)據(jù)包進入隊列；

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

當thmin≤avgq≤thmax時，首先計算一個過渡的丟包概率 pb，如公式（2）所示.其中 pmax是最大丟包率.

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

2.2BLUE算法

隨機早檢測（RED）算法的一個主要目標是使用平均隊列長度和擁塞早通知來實現(xiàn)低時延和高帶寬.但是RED存在兩個缺陷：

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

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

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

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

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

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

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

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

2.3改進BLUE算法

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

具體改進如下：

3　仿真與性能分析

3.1仿真配置參數(shù)

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

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

3.2性能分析

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

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

圖1　仿真網(wǎng)絡(luò)拓撲圖

圖2　（a）RED和（b）BLUE平均隊列長度變化圖

圖3　RED和BLUE丟包率變化圖

圖4　RED和BLUE吞吐量變化圖

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

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

圖5　改進的BLUE的平均隊列長度

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

4　總結(jié)

本文通過NS-2實驗對RED和BLUE兩種算法進行了性能比較，由仿真結(jié)果分析，BLUE算法在應(yīng)對突變流方面，性能明顯優(yōu)于RED算法.RED算法由于不能夠很好控制隊列長度，使得平均隊長在遭遇突變流時波動很大，從而導致出現(xiàn)相對較高的丟包率，進而影響鏈路利用率.BLUE算法基于記錄過去的丟包率和鏈路利用狀態(tài)進行擁塞管理，能夠較好地估計擁塞程度，進而做出適當?shù)姆磻?yīng)，所以，BLUE算法的丟包率相對較低，雖然在有突發(fā)流出現(xiàn)時丟包率增大，但是比RED算法丟包率變化幅度小.在此基礎(chǔ)上，對BLUE算法進行改進，仿真結(jié)果表明，改進的BLUE算法在TCP流突變時，能夠更好地保持隊列長度的穩(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的隊列管理算法研究［J］.信息安全與技術(shù)，2011（11）：16-19.

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

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

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

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

［9］張義良.IBLUE：一種新的主動隊列管理算法［J］.微電子學與計算機，2013，30（10）：81-84.

［10］毛鵬軒.下一代網(wǎng)絡(luò)擁塞控制關(guān)鍵算法的研究［D］.北京：北京交通大學，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

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

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