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

吉祖勤， 黄津津

(盐城师范学院 信息科学与技术学院，江苏 盐城 224002)

0 引 言

随着Internet的快速发展网络拥塞问[1]题随之产生，拥塞控制[2]行之有效的手段是在网络层实现队列管理。队列管理是指管理网络传输节点中队列缓冲资源，通过选取什么时候丢弃哪种业务流以达到控制队列长度目的。在传输过程中，数据包经过的网络节点为了提高输出链路的带宽利用率，多使用延迟转发、队列缓存的服务方式。在数据包到达队列前端时队列管理机制通过一定的信息和策略判断是否同意让该数据包进入缓冲队列。

队列管理算法可以分为主动队列管理(AQM)和被动队列管理(PQM)两种。为了对典型的主动队列管理算法RED、被动管理算法DropTail之间的性能进行比较，在NS2平台上进行了一系列的仿真。仿真实验对平均队列长度、吞吐量、丢包率、时延四个主要性能指标进行了比较。对得到的仿真数据进行分析,得出在队列管理算法中采用RED比采用DropTail更有效。

1 DropTail与RED算法简介

1.1 DropTail算法

DropTail是现在被广泛使用的的将数据包进行排队和丢弃处理的算法[3-5]。算法原理：数据包传送到路由器时，需要在输出端口缓冲区中排队；若缓冲区的容量设置足够大，当产生网络拥塞时，所有新传到却没来得及处理的数据包都将在缓冲区中被保存起来，当系统空闲时这些保存起来的数据包再被处理；如网络拥塞一直持续，缓冲区就有可能被填满，此后所有新传到的数据包会被丢弃。当数据包被丢弃的现象被发送端TCP检测到时，就把数据发送速率降低，以消除拥塞。

1.2 RED算法

随机早期检测(Random Early Detection,RED)[6-8]算法的原理：RED路由器通过指数加权平均方法(EWMA)算出平均队列长度。再将平均队列长度和两个阈值(最大门限和最小门限)进行比较。如果平均队长比最小门限值小时，任何数据分组都不会被丢失；如果平均队长比最大门限值大时，每一个到达的数据分组都会被丢失；如果平均队长在最小与最大门限值之间时，依据概率p丢弃到达路由器的数据分组，这个概率是平均队列长度的函数。

2 仿真实验设置

2.1 仿真实验网络拓扑结构

采用了研究AQM算法的典型网络拓扑结构[9-11]：哑铃型的单一瓶颈链路多源多汇的网络，如图1所示。其中Tcp0和Tcp4为使用TCP协议发送数据的代理，Sink2和Sink5是接收使用TCP协议发送数据的代理，作为TCP的应答代理，Udp1和Udp5作为使用UDP协议发送数据的代理，Null0和Null3是UDP协议发送数据的接受代理。其中，N0和N5节点中既有发送代理也有接收代理。仿真实验中定义的链接如表1所示。

图1 网络拓补结构

2.2 仿真参数的设定

(1) 确定网络流量大小与链路带宽之间的关系。很多情况下，将各条非瓶颈链路的流量与其带宽设定为一致，即满负荷；为研究算法鲁棒性而进行实验仿真时，可设定流量在仿真过程中可发生变化；在本实验中流量的取值还应确保在瓶颈链路上可以发生拥塞，即所有数据源端的发送速率之和要大于或以一定概率大于瓶颈链路的带宽。

(2) 确定缓冲区容量与链路带宽及RTT的范围要求之间的关系。如下式所示。

(1)

式中：C为以分组/s为单位的源端链路带宽；Ds为路由器上各段非瓶颈链路的传播延迟(i=1，2,…)；下标b代表瓶颈链路；Tq表示在瓶颈链路上的排队延迟。式(1)右端前两项表示数据包发送时间，前3项都是相对固定的量，对RTT时间的要求，就体现在对排队延迟时间的要求上，而缓冲区容量就决定了排队延迟时间的上限，若缓冲区容量为B packets，则Tq≤B/Cb。

设置缓冲区最初是为了缓解路由器因突发流量而造成的拥塞，但它本身也带来了排队延迟，所以设定其大小时就要考虑不使排队延迟在RTT时间中占太大的比例。按照大量仿真实验的经验来看，缓冲区容量设置的准则应为

(2)

按式(2)所示进行设置，既使缓冲区发挥缓解拥塞的作用，又不会使网络延迟增加到不能接受的程度。

对于数据流产生的分布，现在普遍的观点认为，源端(用户)发起网络会话的随机过程服从泊松分布，而每次会话所传输的流量大小则服从Parelo分布。

由此，仿真中，瓶颈链路即N6～N7的缓冲区容量设置为540，产生数据包的方式为Parelo，Parelo打开时间为500 ms，关闭时间为100 ms，产生率为1 000 k，包大小为500，生成形态参数为1.5。仿真中其他参数设置为Wq=0.02，minth=5，maxth=15，maxp=0.02。

3 仿真结果分析

为了对各算法之间的性能进行比较，在NS2[12-13]平台上进行了一系列的仿真，仿真实验在Core2 DUO T7500 2.2 GHz，2 GB内存的机器上进行，环境为Windows XP/Cygwin。仿真实验对平均队列长度、吞吐量、丢包率、时延四个主要性能指标进行了比较。使用awk脚本语言对仿真后产生的trace文件信息进行统计处理，将处理的结果用gnuplot工具输出显示出来[14-15]。

图2与图3显示了DropTail与RED算法在模拟实验中时延的变化过程以及两者比较。可以看出，RED队列算法始终保持在0.25 s以下，相比DropTail算法的时延峰值达到了2.25 s左右，且始终保持在较高值，平均时延方面，UDP数据包的时延RED算法仅为DropTail算法的6.448%, TCP数据包的时延RED算法仅为DropTail算法的9.1217%,可以明显看出RED队列算法在时延方面优于DropTail队列算法。

图2 两种算法的TCP数据包时延

图3 两种算法的UDP数据包时延

图4与图5显示了DropTail与RED算法在模拟实验中队列长度的变化过程以及两者比较。途中显示DropTail算法中平均队列长度远大于RED算法中的平均队列长度，且变化幅度也远大于RED算法。平均队列长度方面，UDP数据包的队列长度RED算法仅为DropTail算法的4.389%, TCP数据包的时延RED算法仅为DropTail算法的13.6%。DropTail算法队列长度变化幅度大于RED算法的原因是：DropTail算法总是在队列满时才进行丢包，发送拥塞通知，从而所有的发送端同时降低发送速率，队列长度急速减少，接着各发送端又同时提高发送速率，队列长度增加，从而产生“TCP全局同步”现象。而RED算法提前对队列进行丢包，使队列长度在达到一定阈值时就通知发送端降低发送速率，从而使队列总保持一定长度，在一定程度上避免了全局同步现象，提高了链路利用率。

图4 两种算法的TCP数据包队列长度

图5 两种算法的UDP数据包队列长度

图6与图7显示了DropTail与RED算法在模拟实验中丢包率的变化过程以及两者比较。平均丢包中，UDP数据包的丢包RED算法为DropTail算法的1.8倍, TCP数据包的丢包RED算法为DropTail算法的5.44倍，可以看出由于RED算法使用的是随机早检测原理，为了保证整个队列长度、链路时延不超出合理范围，采取了主动丢包策略，在丢包率上始终高于DropTail算法。

图8与图9显示了DropTail与RED算法在模拟实验中吞吐量的变化过程以及两者比较。可以看出，虽然RED算法在平均队列长度、吞吐量和延迟上都好于DropTail算法。但是RED算法的吞吐量与DropTail算法吞吐量基本相当，平均吞吐量方面，UDP数据包的平均吞吐量RED算法为DropTail算法的91%, TCP数据包的时延RED算法为DropTail算法的110.6% 。

由仿真实验可以得出结论，RED算法比起DropTail算法在队列长度、时延、丢包率方面有着绝对的优势，在吞吐量方面，两种算法相差不大。总体来说，RED优于DropTail算法。

图6 两种算法的TCP数据包丢包率

图7 两种算法的UDP数据包丢包率

图8 两种算法的TCP数据包吞吐量

图9 两种算法的UDP数据包吞吐量

4 结 语

随着Internet的快速发展，网络中的拥塞控制问题成为近几年来网络发展中的焦点问题。队列管理是指管理网络传输节点中队列缓冲资源，通过选取什么时候丢弃哪种业务流来实现控制队列长度目的。本文在简介了传统的被动队列管理算法DropTail与主动队列管理算法RED之后，描述了如何在NS 平台下建立队列管理算法的仿真实验，并对跟踪结果进行了分析，结果表明RED 算法能够消除传统的DropTail算法引起的"全局同步"现象，提高网络的链路利用率，减小网络时延。得出在队列管理算法中采用RED比采用DropTail更有效,为进一步研究拥塞控制算法提供依据。

[1] 蔡小玲，范新丽．不同队列管理机制对多媒体传输品质的影响[J]．计算机应用， 2009， 29(29): 24-26．

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

[2] 章 淼，吴建平，林 闯．互联网端到端拥塞控制研究综述[J]．软件学报， 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的仿真实现与比较[J]．常州工学院学报， 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]．郑州轻工业学院学报，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] 石 萍，杨 波，陈贞翔．不同服务类型的队列管理及性能比较[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]．计算机应用与软件，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]．计算机工程与科学，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]．计算机系统应用，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网络仿真平台及其在TCP拥塞控制研究中的应用[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构建计算机网络实验课程体系[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的无线网络仿真研究[J]．计算机与数字工程，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仿真实验-多媒体和无线网络通信[M]．北京：电子工业出版社，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.