基于NS2的隊列管理算法DropTail和RED仿真與研究

吉祖勤， 黃津津

(鹽城師范學(xué)院 信息科學(xué)與技術(shù)學(xué)院，江蘇 鹽城 224002)

0 引 言

隨著Internet的快速發(fā)展網(wǎng)絡(luò)擁塞問[1]題隨之產(chǎn)生，擁塞控制[2]行之有效的手段是在網(wǎng)絡(luò)層實現(xiàn)隊列管理。隊列管理是指管理網(wǎng)絡(luò)傳輸節(jié)點中隊列緩沖資源，通過選取什么時候丟棄哪種業(yè)務(wù)流以達(dá)到控制隊列長度目的。在傳輸過程中，數(shù)據(jù)包經(jīng)過的網(wǎng)絡(luò)節(jié)點為了提高輸出鏈路的帶寬利用率，多使用延遲轉(zhuǎn)發(fā)、隊列緩存的服務(wù)方式。在數(shù)據(jù)包到達(dá)隊列前端時隊列管理機制通過一定的信息和策略判斷是否同意讓該數(shù)據(jù)包進入緩沖隊列。

隊列管理算法可以分為主動隊列管理(AQM)和被動隊列管理(PQM)兩種。為了對典型的主動隊列管理算法RED、被動管理算法DropTail之間的性能進行比較，在NS2平臺上進行了一系列的仿真。仿真實驗對平均隊列長度、吞吐量、丟包率、時延四個主要性能指標(biāo)進行了比較。對得到的仿真數(shù)據(jù)進行分析,得出在隊列管理算法中采用RED比采用DropTail更有效。

1 DropTail與RED算法簡介

1.1 DropTail算法

DropTail是現(xiàn)在被廣泛使用的的將數(shù)據(jù)包進行排隊和丟棄處理的算法[3-5]。算法原理：數(shù)據(jù)包傳送到路由器時，需要在輸出端口緩沖區(qū)中排隊；若緩沖區(qū)的容量設(shè)置足夠大，當(dāng)產(chǎn)生網(wǎng)絡(luò)擁塞時，所有新傳到卻沒來得及處理的數(shù)據(jù)包都將在緩沖區(qū)中被保存起來，當(dāng)系統(tǒng)空閑時這些保存起來的數(shù)據(jù)包再被處理；如網(wǎng)絡(luò)擁塞一直持續(xù)，緩沖區(qū)就有可能被填滿，此后所有新傳到的數(shù)據(jù)包會被丟棄。當(dāng)數(shù)據(jù)包被丟棄的現(xiàn)象被發(fā)送端TCP檢測到時，就把數(shù)據(jù)發(fā)送速率降低，以消除擁塞。

1.2 RED算法

隨機早期檢測(Random Early Detection,RED)[6-8]算法的原理：RED路由器通過指數(shù)加權(quán)平均方法(EWMA)算出平均隊列長度。再將平均隊列長度和兩個閾值(最大門限和最小門限)進行比較。如果平均隊長比最小門限值小時，任何數(shù)據(jù)分組都不會被丟失；如果平均隊長比最大門限值大時，每一個到達(dá)的數(shù)據(jù)分組都會被丟失；如果平均隊長在最小與最大門限值之間時，依據(jù)概率p丟棄到達(dá)路由器的數(shù)據(jù)分組，這個概率是平均隊列長度的函數(shù)。

2 仿真實驗設(shè)置

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

采用了研究AQM算法的典型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[9-11]：啞鈴型的單一瓶頸鏈路多源多匯的網(wǎng)絡(luò)，如圖1所示。其中Tcp0和Tcp4為使用TCP協(xié)議發(fā)送數(shù)據(jù)的代理，Sink2和Sink5是接收使用TCP協(xié)議發(fā)送數(shù)據(jù)的代理，作為TCP的應(yīng)答代理，Udp1和Udp5作為使用UDP協(xié)議發(fā)送數(shù)據(jù)的代理，Null0和Null3是UDP協(xié)議發(fā)送數(shù)據(jù)的接受代理。其中，N0和N5節(jié)點中既有發(fā)送代理也有接收代理。仿真實驗中定義的鏈接如表1所示。

圖1 網(wǎng)絡(luò)拓補結(jié)構(gòu)

2.2 仿真參數(shù)的設(shè)定

(1) 確定網(wǎng)絡(luò)流量大小與鏈路帶寬之間的關(guān)系。很多情況下，將各條非瓶頸鏈路的流量與其帶寬設(shè)定為一致，即滿負(fù)荷；為研究算法魯棒性而進行實驗仿真時，可設(shè)定流量在仿真過程中可發(fā)生變化；在本實驗中流量的取值還應(yīng)確保在瓶頸鏈路上可以發(fā)生擁塞，即所有數(shù)據(jù)源端的發(fā)送速率之和要大于或以一定概率大于瓶頸鏈路的帶寬。

(2) 確定緩沖區(qū)容量與鏈路帶寬及RTT的范圍要求之間的關(guān)系。如下式所示。

(1)

式中：C為以分組/s為單位的源端鏈路帶寬；Ds為路由器上各段非瓶頸鏈路的傳播延遲(i=1，2,…)；下標(biāo)b代表瓶頸鏈路；Tq表示在瓶頸鏈路上的排隊延遲。式(1)右端前兩項表示數(shù)據(jù)包發(fā)送時間，前3項都是相對固定的量，對RTT時間的要求，就體現(xiàn)在對排隊延遲時間的要求上，而緩沖區(qū)容量就決定了排隊延遲時間的上限，若緩沖區(qū)容量為B packets，則Tq≤B/Cb。

設(shè)置緩沖區(qū)最初是為了緩解路由器因突發(fā)流量而造成的擁塞，但它本身也帶來了排隊延遲，所以設(shè)定其大小時就要考慮不使排隊延遲在RTT時間中占太大的比例。按照大量仿真實驗的經(jīng)驗來看，緩沖區(qū)容量設(shè)置的準(zhǔn)則應(yīng)為

(2)

按式(2)所示進行設(shè)置，既使緩沖區(qū)發(fā)揮緩解擁塞的作用，又不會使網(wǎng)絡(luò)延遲增加到不能接受的程度。

對于數(shù)據(jù)流產(chǎn)生的分布，現(xiàn)在普遍的觀點認(rèn)為，源端(用戶)發(fā)起網(wǎng)絡(luò)會話的隨機過程服從泊松分布，而每次會話所傳輸?shù)牧髁看笮t服從Parelo分布。

由此，仿真中，瓶頸鏈路即N6～N7的緩沖區(qū)容量設(shè)置為540，產(chǎn)生數(shù)據(jù)包的方式為Parelo，Parelo打開時間為500 ms，關(guān)閉時間為100 ms，產(chǎn)生率為1 000 k，包大小為500，生成形態(tài)參數(shù)為1.5。仿真中其他參數(shù)設(shè)置為Wq=0.02，minth=5，maxth=15，maxp=0.02。

3 仿真結(jié)果分析

為了對各算法之間的性能進行比較，在NS2[12-13]平臺上進行了一系列的仿真，仿真實驗在Core2 DUO T7500 2.2 GHz，2 GB內(nèi)存的機器上進行，環(huán)境為Windows XP/Cygwin。仿真實驗對平均隊列長度、吞吐量、丟包率、時延四個主要性能指標(biāo)進行了比較。使用awk腳本語言對仿真后產(chǎn)生的trace文件信息進行統(tǒng)計處理，將處理的結(jié)果用gnuplot工具輸出顯示出來[14-15]。

圖2與圖3顯示了DropTail與RED算法在模擬實驗中時延的變化過程以及兩者比較?？梢钥闯?，RED隊列算法始終保持在0.25 s以下，相比DropTail算法的時延峰值達(dá)到了2.25 s左右，且始終保持在較高值，平均時延方面，UDP數(shù)據(jù)包的時延RED算法僅為DropTail算法的6.448%, TCP數(shù)據(jù)包的時延RED算法僅為DropTail算法的9.1217%,可以明顯看出RED隊列算法在時延方面優(yōu)于DropTail隊列算法。

圖2 兩種算法的TCP數(shù)據(jù)包時延

圖3 兩種算法的UDP數(shù)據(jù)包時延

圖4與圖5顯示了DropTail與RED算法在模擬實驗中隊列長度的變化過程以及兩者比較。途中顯示DropTail算法中平均隊列長度遠(yuǎn)大于RED算法中的平均隊列長度，且變化幅度也遠(yuǎn)大于RED算法。平均隊列長度方面，UDP數(shù)據(jù)包的隊列長度RED算法僅為DropTail算法的4.389%, TCP數(shù)據(jù)包的時延RED算法僅為DropTail算法的13.6%。DropTail算法隊列長度變化幅度大于RED算法的原因是：DropTail算法總是在隊列滿時才進行丟包，發(fā)送擁塞通知，從而所有的發(fā)送端同時降低發(fā)送速率，隊列長度急速減少，接著各發(fā)送端又同時提高發(fā)送速率，隊列長度增加，從而產(chǎn)生“TCP全局同步”現(xiàn)象。而RED算法提前對隊列進行丟包，使隊列長度在達(dá)到一定閾值時就通知發(fā)送端降低發(fā)送速率，從而使隊列總保持一定長度，在一定程度上避免了全局同步現(xiàn)象，提高了鏈路利用率。

圖4 兩種算法的TCP數(shù)據(jù)包隊列長度

圖5 兩種算法的UDP數(shù)據(jù)包隊列長度

圖6與圖7顯示了DropTail與RED算法在模擬實驗中丟包率的變化過程以及兩者比較。平均丟包中，UDP數(shù)據(jù)包的丟包RED算法為DropTail算法的1.8倍, TCP數(shù)據(jù)包的丟包RED算法為DropTail算法的5.44倍，可以看出由于RED算法使用的是隨機早檢測原理，為了保證整個隊列長度、鏈路時延不超出合理范圍，采取了主動丟包策略，在丟包率上始終高于DropTail算法。

圖8與圖9顯示了DropTail與RED算法在模擬實驗中吞吐量的變化過程以及兩者比較?？梢钥闯?，雖然RED算法在平均隊列長度、吞吐量和延遲上都好于DropTail算法。但是RED算法的吞吐量與DropTail算法吞吐量基本相當(dāng)，平均吞吐量方面，UDP數(shù)據(jù)包的平均吞吐量RED算法為DropTail算法的91%, TCP數(shù)據(jù)包的時延RED算法為DropTail算法的110.6% 。

由仿真實驗可以得出結(jié)論，RED算法比起DropTail算法在隊列長度、時延、丟包率方面有著絕對的優(yōu)勢，在吞吐量方面，兩種算法相差不大?？傮w來說，RED優(yōu)于DropTail算法。

圖6 兩種算法的TCP數(shù)據(jù)包丟包率

圖7 兩種算法的UDP數(shù)據(jù)包丟包率

圖8 兩種算法的TCP數(shù)據(jù)包吞吐量

圖9 兩種算法的UDP數(shù)據(jù)包吞吐量

4 結(jié) 語

隨著Internet的快速發(fā)展，網(wǎng)絡(luò)中的擁塞控制問題成為近幾年來網(wǎng)絡(luò)發(fā)展中的焦點問題。隊列管理是指管理網(wǎng)絡(luò)傳輸節(jié)點中隊列緩沖資源，通過選取什么時候丟棄哪種業(yè)務(wù)流來實現(xiàn)控制隊列長度目的。本文在簡介了傳統(tǒng)的被動隊列管理算法DropTail與主動隊列管理算法RED之后，描述了如何在NS 平臺下建立隊列管理算法的仿真實驗，并對跟蹤結(jié)果進行了分析，結(jié)果表明RED 算法能夠消除傳統(tǒng)的DropTail算法引起的"全局同步"現(xiàn)象，提高網(wǎng)絡(luò)的鏈路利用率，減小網(wǎng)絡(luò)時延。得出在隊列管理算法中采用RED比采用DropTail更有效,為進一步研究擁塞控制算法提供依據(jù)。

[1] 蔡小玲，范新麗．不同隊列管理機制對多媒體傳輸品質(zhì)的影響[J]．計算機應(yīng)用， 2009， 29(29): 24-26．

CAI Xiao-ling，F(xiàn)AN Xin-li．Effect on multimedia transmission for several queue management mechanisms[J]．Journal of Computer Applications，2009，29(29): 24-26．

[2] 章 淼，吳建平，林 闖．互聯(lián)網(wǎng)端到端擁塞控制研究綜述[J]．軟件學(xué)報， 2002，12(3): 354- 363．

Zhang Miao，Wu Jian-ping，Lin Chuang．Survey on Internet End-to-End Congestion Control[J]．Journal of Software，2002，12(3):354- 363．

[3] 梁 潘．基于NS2的PQM和AQM的仿真實現(xiàn)與比較[J]．常州工學(xué)院學(xué)報， 2010(Z1):60-63．

Liang Pan．The PQM and AQM Implementations and Comparison Based on NS2[J]．Journal of Changzhou Institute of Technology，2010(Z1):60-63．

[4] 李軍偉，王 云．基于OPNET 的RED和DropTail算法比較與仿真[J]．鄭州輕工業(yè)學(xué)院學(xué)報，2010，25(3):61-65．

Li Jun-wei，Wang Yun．Simulation and Comparison of RED and Droptail Algorithms Base on Opnet[J]．Journal of Zhengzhou University of Light Industry，2010，25(3):61-65．

[5] 石 萍，楊 波，陳貞翔．不同服務(wù)類型的隊列管理及性能比較[J]．計算機工程，2008(23):116-118．

Shi Ping，Yang Bo，Chen Xiang．Queue Management Method and Performance Comparison of Different Servicers[J]．Journal of Computer Engineering，2008(23):116-118．

[6] 吳宣耀，林其偉．主動隊列管理算法的研究[J]．計算機應(yīng)用與軟件，2009(7):48-51．

Wu Xuanyao，Lin Qwei．Research of Active Queue Management Algorithm Based on Ns2[J]．Journal of Computer Applications and Software．2009(07):48-51．

[7] 文 宏，唐玉華，朱培棟．RED 簇主動隊列管理算法研究[J]．計算機工程與科學(xué)，2006，28(5): 66 -69．

WEN Hong，TANG Yu-hua，ZHU Pei-dong．Research on the RED-Family Active Queue Management Algorithms[J]．Journal of Computer Engineering & Science，2006，28(5): 66-69．

[8] 汪華斌．基于NS2的RED算法研究與仿真分析[J]．計算機系統(tǒng)應(yīng)用，2008(12):49-53．

Wang Hua-jian．RED Algorithm and Simulation Analysis Based on NS2[J]．Journal of Computer Systems & Applications，2008(12):49-53．

[9] 陳 軍，劉曉衡．主動隊列管理算法RED算法改進與實驗仿真研究[J]．計算機工程， 2006，32(17): 159-164．

Chen Jun，Liu Xiao-heng．Study on Active Queue Management RED Improvement and Simulation[J]．Journal of Computer Engineering，2006，32(17): 159 -164．

[10] 武志勇．NS-2網(wǎng)絡(luò)仿真平臺及其在TCP擁塞控制研究中的應(yīng)用[J]．實驗室研究與探索，2008(1):166-168．

Wu Zhi-yong．Network Simulation Platform NS-2 and Its Application to TCP Congestion Control[J]．Journal of Research and Exploration in Laboratory，2008(01):166-168．

[11] 謝 慧，吳曉平，李麗華．用NS2構(gòu)建計算機網(wǎng)絡(luò)實驗課程體系[J]．實驗室研究與探索，2010(1):74-76．

Xie Hui，Wu Xiao-ping，Li Li-hua．Using NS2 to Construct Computer Network Experiment Curriculum System[J]．Journal of Research and Exploration in Laboratory，2010(01):74-76．

[12] 鐘 輝，王 鵬．基于NS2的無線網(wǎng)絡(luò)仿真研究[J]．計算機與數(shù)字工程，2008(7):57-60．

Zhong Hui，Wang Peng．Research of the Wireless Network Simulation Based on NS2[J]．Journal of Computer & Digital Engineering，2008(07):57-60．

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

Ke Zhi-heng，Chen Rong-xiang，Deng De-jun．NS2 simulation experiments- multimedia and wireless network communications[M]．BeiJing：Electronic Industry Press，2009．

[14] Fall K,Varadhan K. The NS Manual. [EB /OL]. http: //www.isi.edu/nsnam/ns/doc/index/html

[15] The network simulator NS-2: Documentation[DB /OL]. http://www.isi.edu/nsnam/ns/ns-documentation/html.