路由器队列管理算法DropTail和RED的实验仿真与分析

张 奎

（喀什大学 计算机科学与技术学院，新疆 喀什 844000）

0 引言

随着因特网的快速发展以及“互联网+”思维的广泛深入，新型网络应用不断出现，由此引发的客户端的增加以及网络数据量爆炸式的增长给网络运维带来了巨大压力.特别是语音、视频、图像等多媒体流量的增加，使现有的网络资源变得愈加紧张，拥塞问题更加严重，进而导致网络性能变坏.此外，大量用户的负载请求，对QoS（Quality of Service，网络服务质量）提出了更高的要求.如何在满足用户QoS 需求的前提下预防和控制网络拥塞，成为亟待解决的问题，而传统仅仅依靠源点的TCP 控制协议远远不够[1-2].因此，基于路由器的拥塞控制机制成为该问题研究的热点.

路由器的拥塞控制即路由器采用队列管理算法来监控实时队列长度，进而审视各个数据包对产生拥塞的影响，从而进行队列管理，以此来避免网络拥塞.常见的队列管理算法分为被动队列管理（Passive Queue Management，PQM）和主动队列管理（Active Queue Management，AQM）.文献[3-4]利用NS2 软件对不同网络环境下的TCP 控制协议进行实验仿真，对比分析各算法在无丢包、高时延、低带宽和一般拥塞环境下的网络适用情况；文献[2，5]从多角度统计分析主动队列管理RED 算法的网络性能情况，在此基础上提出了非线性自适应算法，进行实验仿真进而得出改进后的算法在复杂网络环境下的适用情况.然而，如何突出队列管理算法的综合性能情况，以上文献并未给出明确结论.本文拟借助NS2 仿真软件，对DropTail 和RED 算法进行实验仿真[6]，从多个角度对比分析网络性能，得出算法综合性能结论，以期加深对网络拥塞控制知识点的理解和掌握.

1 队列管理算法DropTail 与RED 简介

1 DropTail 算法

DropTail 算法是采用尾部丢弃策略来缓解网络拥塞.其算法思想是：路由器对每一个缓存队列设置一个最大值，当数据包进入队列的长度小于最大值时，接收数据包；当进入队列的长度大于最大值时，丢弃数据包，直至缓存队列出现空闲时再接收后面送达的数据包[2，6].DropTail 算法由于原理简单、易于控制等特性，目前在因特网上使用广泛.但是队尾丢弃策略在队列满时才丢弃后面进入的所有数据包，这样很容易造成死锁、满队列、全局同步以及持续队列满造成的较大延迟等.

1.2 RED 算法

RED 算法是通过一定概率丢失或标记报文来通知端系统网络的拥塞情况.其算法思想是：采用平均队列长度来反映网络拥塞的变化情况，用平均队列长度LAV与设定的阈值（最大门限THmax和最小门限THmin）进行对比，判定网络拥塞的发生情况，并采用随机概率p 丢弃数据包，避免网络发生全局性的拥塞控制[7-9].当平均队列长度小于最小门限值时，所有数据包都被接收；当平均队列长度大于最大门限值时，所有数据包都被丢弃；而当平均队列长度介于最大门限值与最小门限值之间时，以随机概率p 丢弃数据包.RED 算法核心在于丢弃概率p 的选择，其值计算公式如下式[2，10]：

其中，count 代表新到达且已进入队列中的数据包数；而ptemp是过渡的数据包丢弃概率，其作用在于促使数据包丢弃概率p 分布更加均匀，其值计算公式为

2 实验系统设计

采用NS2 仿真软件[6，9，11]搭建如图1 所示的拓扑结构，其中S（ii=1，2，3，4）为数据源节点，r1 为发送方路由器，r2 为接收方路由器.其中Si与r1 建立有线链路，链路队列大小为20，带宽为10 Mb/s、延时（$）i10 ms.r1 与r2 之间建立瓶颈链路，链路队列大小为100，带宽为0.7 Mb/s、延时20 ms.Si通过随机数产生器产生FTP 数据流经过r1 存储转发至r2，Si的FTP 数据流事件发生的时间在0～50 s 之间，第50 s 结束网络模拟.r1 与r2 存储转发的队列管理分别采用DropTail 和RED 算法，其中DropTail 的发送窗口最大值为100，RED 算法的最小门限THmin=80、最大门限THmax=120、控制参数δ=0.04.通过编写脚本文件实现：（1） 两种算法对于拥塞控制的动画模拟；（2）从丢包率、时延、吞吐量以及平均队列长度方面分析两种算法的网络适用情况.

图1 队列管理仿真网络拓扑

3 实验结果分析

DropTail 和RED 算法控制下的拥塞控制动画如图2、图3 所示.观察动画过程可以看出DropTail 网络连续丢包的次数及个数较多，而RED 网络丢包比较均匀，没有出现大量丢包的情况.这说明RED 算法以随机概率p 丢弃数据包，确保了网络吞吐量的稳定性.由于网络数据流量具有突发性的特点，实时丢包情况并不能准确反映队列管理算法的整体性能.为了进一步对比分析两种算法的性能情况，采用awk 语言编写吞吐量、丢包率、时延脚本文件，对两种算法实验仿真后的trace 文件进行数据统计.

图2 DropTail 拥塞控制动画

图3 RED 拥塞控制动画

3.1 吞吐量及丢包率分析

两种算法的网络吞吐量如图4 所示，配合trace 跟踪脚本可以看出两种算法在0.78 s 时网络吞吐量均增大至600.21packages，在0.78～50 s 的时间内网络吞吐量保持在600～700 packages 之间，整体上来看两种算法的吞吐量相差不大.但是RED 算法在0.46 s 时就开始丢弃数据包，在[1.52～1.97]s 区间内大量丢包使网络吞吐量降低至508.72 bps，之后保持均匀上升趋势.在0～50 s 的时间内DropTail 算法共发包7558 个，丢失120 个，丢包率为1.58%；而RED 算法共发包7708 个，丢失385 个，丢包率为4.99%，其丢包率是DropTail 算法的3.4 倍.RED 算法的高丢包率在于在确保网络吞吐量以及链路利用率前期下，采用主动丢包策略，以随机概率p 丢弃到达的数据包，提前规避系统进入拥塞状态.

图4 两种算法的吞吐量

3.2 时延分析

两种算法的平均队列时延情况如图5 所示，配合trace 跟踪脚本可以看出DropTail 算法在1.57 s 和2.39 s 时分别达到队列时延0.69 s 和0.04 s 的峰值，而后队列时延保持在0.39～0.69 s 范围，但是队列时延变化趋势比较剧烈.这说明DropTail 算法长时间处于满队列状态，通过丢弃分组促使队列空闲进而缓解网络拥塞，进而提高发送数据引发再一次的满队列，如此往复，使网络时延处于剧烈变化之中.而RED 算法在0.73 s 时队列时延达到0.41 s 的峰值，而后队列时延逐渐降低，保持在较低水平，后面新到达队列的数据包会尽快得到处理，进而有空闲队列允许更多数据包进入队列，从而提高链路利用率，确保网络时延的稳定性.

图5 两种算法的时延

3.3 平均队列长度

两种算法的网络平均队列长度如图6 所示，配合trace 跟踪脚本可以看出DropTail 算法的平均队列在第11 s 时初次达到97 packages，在仿真时间内多次趋近队列的最大长度，即多次出现队列满的情况；而RED 算法最大平均队列长度仅为队列最大长度的一半，平均队列长度保持在较低的稳定水平.这说明DropTail 算法在队列满时才开始丢弃数据包，通过超时机制控制所有发送方降低发送速率，使系统在同一时间进入拥塞控制状态，引发“TCP 全局同步”现象；全局同步促使网络数据量降低，降低平均队列长度，之后发送方提高发送速率，进而使平均队列长度逐步增大.而RED 算法依据设定好的阈值（最大门限THmax和最小门限THmin），以随机概率p 丢弃分组，使拥塞控制限制在个别TCP 连接上，避免发生全局性的拥塞控制，进而提高网络的链路利用率.

图6 两种算法的平均队列长度

通过实验仿真以及数据统计，可以看出RED 算法在丢包率、时延、平均队列长度方面优于DropTail 算法，在吞吐量方面，两种算法差别不大.整体来看，RED 算法性能优于DropTail算法.

4 结语

在对队列管理算法进行分析的基础上，实验仿真并对比分析了DropTail 和RED 算法，实验结果表明，RED 算法整体性能优于DropTail算法.仿真过程中RED 算法通过随机概率p 提前丢弃数据包，控制队列长度进而提高系统吞吐量以及降低队列时延，这对于避免DropTail算法“TCP 全局同步”的若干问题以及提高链路利用率方面具有至关重要的作用.