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

杨　媛，王晓喃

（常熟理工学院 计算机科学与工程学院，江苏 常熟 215500）

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

杨媛，王晓喃

（常熟理工学院 计算机科学与工程学院，江苏 常熟 215500）

主动式队列管理技术是IETF为了解决Internet拥塞控制问题而提出的一种路由器缓存管理技术.本文使用了目前应用较为广泛的网络仿真器NS-2，对AQM算法RED和BLUE的性能在基于NS-2仿真实验的基础上进行了比较研究，研究的性能包括在突发流情况下平均队列长度、丢包率和吞吐量等，并在此基础上对BLUE算法在突发流情况下队列稳定性进行改进.仿真结果表明在应对突发流方面，BLUE算法的性能优于RED算法，改进的BLUE算法能够更好地保持队列的稳定性.

网络拥塞控制；主动队列管理（AQM）；随机早检测算法（RED）；（BLUE）；网络仿真

随着互联网技术的高速发展，互联网用户的规模日益增大，对网络拥塞控制技术的要求也越来越高.单纯的依靠早期的拥塞控制（即基于源端的拥塞控制）已经不能够满足当今网络的需求，必须要网络本身也参与到拥塞控制中去.在Internet网络中，拥塞来源于网络资源和网络流量分布的不均衡性，而且这种不均衡性是不可避免的.拥塞一般发生在数据传输路径的中间节点，通常是由缓冲区溢出造成的.因此，网络节点的队列管理成为避免网络拥塞的关键技术，寻求一种合理有效的队列管理算法成为研究的一个热点.

1　队列管理概述

队列管理是网络拥塞控制和服务质量（Qos）保证的基石.Internet网络主要基于存储转发和统计复用技术.由于Internet数据流量本质上具有突发性，因此允许传输突发的数据包非常必要，而路由器中队列的重要作用就是吸收突发的数据包.较长的队列能够吸收更多的突发数据，提高吞吐量.TCP机制往往会保持较高的队列占用率，因而增加了数据包的排队延迟，这就需要路由器对队列进行管理，维持较小的队列长度.目前，路由器有两类与网络拥塞控制相关的队列算法：队列管理算法和队列调度算法.队列管理算法主要管理网络节点的缓存序列，决定何时接受和丢弃某一个包.队列调度位于队列管理之后，主要解决多个队列中的数据包谁先输出的问题.对队列长度进行管理，直接影响到路由器的拥塞控制能力和Qos能力.目前，队列管理机制主要分为两大类，一类是以DropTail为代表的被动式队列管理机制（Passive Queue Manage⁃ment，PQM），另一类是以RED（Random Early Detection）为代表的主动式队列管理机制（Active Queue Man⁃agement，AQM）.

在Internet中，最普遍的队列管理机制就是DropTail.其主要原理是，当一个数据包到达队列时，就把数据包放入队列中等待被发送，但是由于队列长度有限，所以当数据流很大时，队列没有空间暂存这些新来的数据包，就会把队列最末端的数据包进行丢弃.DropTail队列管理机制的优点在于，操作简单，处理速度最快，几乎所有的平台都支持这种队列算法.但是，DropTail存在着诸如死锁，满队列和全局同步等一系列问题.这就促使研究人员去探寻更有效的队列管理机制.

从90年代开始，业界对AQM进行了研究.相对于被动式队列管理机制，主动式队列管理机制会在队列满之前就开始把封包丢弃，以便及时地对具有拥塞控制的传送端进行传送速度的管制，有效避免满队列状态所带来的较长延迟时间以及链路利用率低的负面效应.目前，主要流行两种AQM算法，即RED和BLUE.

本文对RED算法和BLUE算法的性能进行了分析研究，通过仿真实验对两种算法的平均队列长度，丢包率以及吞吐量等几个方面的性能参数进行分析比较，进一步改进了BLUE算法，并进行仿真分析.

2　主动式队列管理算法

2.1随机早期检测算法RED

Floyd在1993年提出了著名的随机早期检测拥塞控制机制，有效地改进了传统弃尾算法.这也是目前最常用的一种主动式队列管理算法.RED算法是使用平均队列长度来预测即将要发生的网络拥塞，并采用随机选择的方式对封包进行丢弃，使得在拥塞尚未发生之前就会有拥塞控制的传送端提示要进行流量速度管制，以避免拥塞发生.

RED主要由两个算法组成：

1）通过指数加权移动平均（exponential weighted moving average）算法计算平均队列长度avgq，如公式（1）所示.其中wq为低通滤波器长度，curq表示当前实际队列长度，oldavgq表示上一时刻的平均队列长度.

2）计算丢包概率 p.RED设置了两个平均队列的阈值，最小丢弃门限thmin和最大丢弃门限thmax.随着数据包到达路由器，RED计算出平均队列长度avgq.

当avgq＜thmin时，允许所有的数据包进入队列；

当avgq＞thmax时，所有的数据包均被丢弃；

当thmin≤avgq≤thmax时，首先计算一个过渡的丢包概率 pb，如公式（2）所示.其中 pmax是最大丢包率.

其中count是上一次丢包开始到现在连续进入队列的包的数量.随着count的增加，到达数据包被丢弃的概率也在增加，这样做的目的是实现丢包间隔均匀，避免连续丢包，导致扼杀突发数据流和数据流同步.

2.2BLUE算法

随机早检测（RED）算法的一个主要目标是使用平均队列长度和拥塞早通知来实现低时延和高带宽.但是RED存在两个缺陷：

1）对参数的设置较为敏感，改变参数的设置对性能会产生很大的影响.到目前为止，对RED中使用的参数还没有明确的设定方法.

2）随着网络中“流”（Flow）数目的增加，平均队列长度也会逐渐增加.

为了解决这些问题，研究人员提出了BLUE算法.

BLUE算法的主要原理在于记录过去的丢包率和链路利用状态来管理拥塞.BLUE算法与RED算法最

然后对丢包率 p做进一步的调整，如公式（3）所示.大的区别在于，BLUE算法使用实际队长来反应拥塞状况，并且使用丢包时间和链路空闲事件来管理拥塞，而RED算法则使用平均队长来管理拥塞.BLUE算法设定了概率prob来标记/丢弃队列中的包，为了避免丢包过于激进，还设定了一个最小时间间隔freeze_time，在 freeze_time间隔内，概率prob只能改变一次.具体算法实现如下：

其中qlen表示瞬时队列长度，qlim表示缓冲区队列大小，now表示当前时刻，last_update表示上次更新概率的时间，d1表示增加量，d2表示减少量.

一般为了能够对流量的迅速增加很快做出反应，需要设定d1比d2大得多.

相对于RED来说，在TCP流聚集而使得网络负荷急剧变化时，BLUE的标记概率能保持平稳，即在一定的时间内能随机均匀地标记包，因此能够更有效地避免全局同步.

2.3改进BLUE算法

在上述BLUE算法中，队列长度的稳定性受到初始设定的丢包概率变化量的影响，这就使得BLUE算法无法更好地适应多变的网络环境.当TCP流数量突增，队列很容易出现溢出或者空闲的缺陷.为了解决这个问题，本文对BLUE算法进行了改进，使得丢包概率变化量不再是一个常量，而是随着网络环境的变化而变化.根据文献［3］，丢包概率和TCP流数量之间存在着非线性的关系，因而当TCP流数量很大时，丢包概率prob也应该随之增大.该算法主要是根据平均队列长度avgq大于队列最大阈值thmax时对丢包概率变化量进行调整.

具体改进如下：

3　仿真与性能分析

3.1仿真配置参数

为了对上述两种算法进行性能分析比较，使用NS-2工具进行了仿真.仿真实验中网络拓扑结构如图1所示.假定R1到R2之间的链路为瓶颈链路，图中所有的链路带宽均为25 Mbps，延迟为10 ms.S1…Sn为发送端，D1…Dn为接收端.其中n为发送和接收节点的个数.

仿真实验中用到的参数采用如下代码设定.所有实验时间均为20 s，每0.5 s记录一次数据.

3.2性能分析

场景：TCP流从15个突变到100个，在第10秒时发生突变，仿真时间总共为20秒.

从图2（a）可以看出，RED算法在第10秒前后平均队列长度震荡变得更强烈，而且平均队列长度整体变大，这主要是由于RED算法主要使用平均队列长度来预测将要发生的拥塞状况，如果拥塞不太严重，则平均队列接近thmin，本实验为20；如果拥塞比较严重，则平均队列接近thmax，本实验为80.从图2（b）可以看出，BLUE算法在第10秒前后平均队列长度震荡变小，而且平均队列长度整体仍然维持在突变之前的长度.这说明BLUE在应对突变方面，稳定性比RED好.可以观察到开始时队列有很大的波动，这主要是对FTP起始连接的反映.通过图2比较这两种算法平均队列长度，可以看出BLUE算法的平均队列长度最大，而且一直处于thmax，链路利用率很高，这主要是由于在BLUE算法中设置d1要比d2大很多，因此能够对流量大量迅速地增加很快做出反应，使得平均队列震荡幅度较10秒之前变化不大.

图1　仿真网络拓扑图

图2　（a）RED和（b）BLUE平均队列长度变化图

图3　RED和BLUE丢包率变化图

图4　RED和BLUE吞吐量变化图

从图3可以看出，在第10秒前后，丢包率明显增大，而且BLUE算法有更低的丢包率.这主要是由于TCP流突然大量增加，使得队列发生拥塞，导致了丢包率增大.而BLUE算法有更好的方法处理突发流现象.

从图4可以看出，在相同的网络环境下，BLUE算法的吞吐量比RED算法要大.还可以看出在第10秒前后，TCP流突变后RED算法的吞吐量有明显的转折点，而BLUE算法则保持一种平滑的曲线.这说明在应对突发流方面，BLUE算法更能保持系统的稳定性.

图5　改进的BLUE的平均队列长度

从图5和图2（b）比较可以看出，在第10秒后，改进的BLUE算法应对突发流反应更迅速，平均队列长度较平稳，而BLUE算法队列相对于改进BLUE算法变化幅度较大，这就有可能引起端到端的抖动延迟，因此改进的BLUE算法很好地解决了这一问题.

4　总结

本文通过NS-2实验对RED和BLUE两种算法进行了性能比较，由仿真结果分析，BLUE算法在应对突变流方面，性能明显优于RED算法.RED算法由于不能够很好控制队列长度，使得平均队长在遭遇突变流时波动很大，从而导致出现相对较高的丢包率，进而影响链路利用率.BLUE算法基于记录过去的丢包率和链路利用状态进行拥塞管理，能够较好地估计拥塞程度，进而做出适当的反应，所以，BLUE算法的丢包率相对较低，虽然在有突发流出现时丢包率增大，但是比RED算法丢包率变化幅度小.在此基础上，对BLUE算法进行改进，仿真结果表明，改进的BLUE算法在TCP流突变时，能够更好地保持队列长度的稳定.

［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］.信息安全与技术，2011（11）：16-19.

［5］陈伟杰.基于主动队列管理的拥塞控制策略及其稳定性研究［D］.杭州：浙江工业大学，2011.

［6］柯志亨，程荣祥，邓德隽.NS2仿真实验：多媒体和无线网络通信［M］.北京：电子工业出版社，2009.

［7］方路平，刘世华，陈盼，等.NS-2网络模拟基础与应用［M］.北京：国防工业出版社，2008.

［8］秦光.计算机网络拥塞的高效控制方法研究［J］.计算机仿真，2012（9）：154-157.

［9］张义良.IBLUE：一种新的主动队列管理算法［J］.微电子学与计算机，2013，30（10）：81-84.

［10］毛鹏轩.下一代网络拥塞控制关键算法的研究［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无线传感器网络关键技术研究”（61202440）

通讯联系人：王晓喃，教授，博士/博士后，硕士生导师，研究方向：计算机网络与应用，E-mail：wxn_2001@163.com.