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

吉祖勤， 黃津津

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

0 引 言

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

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

1 DropTail與RED算法簡介

1.1 DropTail算法

DropTail是現(xiàn)在被廣泛使用的的將數(shù)據(jù)包進(jìn)行排隊(duì)和丟棄處理的算法[3-5]。算法原理：數(shù)據(jù)包傳送到路由器時，需要在輸出端口緩沖區(qū)中排隊(duì)；若緩沖區(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算法

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

2 仿真實(shí)驗(yàn)設(shè)置

2.1 仿真實(shí)驗(yàn)網(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é)點(diǎn)中既有發(fā)送代理也有接收代理。仿真實(shí)驗(yàn)中定義的鏈接如表1所示。

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

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

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

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

(1)

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

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

(2)

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

對于數(shù)據(jù)流產(chǎn)生的分布，現(xiàn)在普遍的觀點(diǎn)認(rèn)為，源端(用戶)發(fā)起網(wǎng)絡(luò)會話的隨機(jī)過程服從泊松分布，而每次會話所傳輸?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é)果分析

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

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

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

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

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

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

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

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

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

由仿真實(shí)驗(yàn)可以得出結(jié)論，RED算法比起DropTail算法在隊(duì)列長度、時延、丟包率方面有著絕對的優(yōu)勢，在吞吐量方面，兩種算法相差不大。總體來說，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ā)展中的焦點(diǎn)問題。隊(duì)列管理是指管理網(wǎng)絡(luò)傳輸節(jié)點(diǎn)中隊(duì)列緩沖資源，通過選取什么時候丟棄哪種業(yè)務(wù)流來實(shí)現(xiàn)控制隊(duì)列長度目的。本文在簡介了傳統(tǒng)的被動隊(duì)列管理算法DropTail與主動隊(duì)列管理算法RED之后，描述了如何在NS 平臺下建立隊(duì)列管理算法的仿真實(shí)驗(yàn)，并對跟蹤結(jié)果進(jìn)行了分析，結(jié)果表明RED 算法能夠消除傳統(tǒng)的DropTail算法引起的"全局同步"現(xiàn)象，提高網(wǎng)絡(luò)的鏈路利用率，減小網(wǎng)絡(luò)時延。得出在隊(duì)列管理算法中采用RED比采用DropTail更有效,為進(jìn)一步研究擁塞控制算法提供依據(jù)。

[1] 蔡小玲，范新麗．不同隊(duì)列管理機(jī)制對多媒體傳輸品質(zhì)的影響[J]．計(jì)算機(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é)報(bào)， 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的仿真實(shí)現(xiàn)與比較[J]．常州工學(xué)院學(xué)報(bào)， 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é)報(bào)，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ù)類型的隊(duì)列管理及性能比較[J]．計(jì)算機(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] 吳宣耀，林其偉．主動隊(duì)列管理算法的研究[J]．計(jì)算機(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 簇主動隊(duì)列管理算法研究[J]．計(jì)算機(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]．計(jì)算機(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] 陳 軍，劉曉衡．主動隊(duì)列管理算法RED算法改進(jìn)與實(shí)驗(yàn)仿真研究[J]．計(jì)算機(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]．實(shí)驗(yàn)室研究與探索，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)建計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)課程體系[J]．實(shí)驗(yàn)室研究與探索，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]．計(jì)算機(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仿真實(shí)驗(yàn)-多媒體和無線網(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.