一种改进ARED拥塞控制算法的实现

薛 礼

(湖北汽车工业学院 电信学院，湖北 十堰 442002)

0 引 言

进入二十一世纪以来，基于互联网的应用越来越广泛，网络数据流量急剧增加，带来的一个严重问题就是网络拥塞。当网络上出现拥塞时，会造成通信双方数据包传输时延增大、数据包容易丢失并重发、网络吞吐量降低等问题，严重的情况下会导致网络死锁和瘫痪，因此TCP/IP网络体系结构实现的过程中在运输层中引入了拥塞控制策略。目前运输层中最重的TCP协议各版本实现机制中均引入了慢启动、拥塞避免、快速重传等一系列算法来实现可靠的拥塞控制[1]。这种拥塞控制机制是建立在端到端的基础上，在早期互联网运行过程中能够很好地保障网络的可靠性和稳定性，提升服务质量QoS，因此传输控制协议TCP成为一种可靠的运输层协议[2]。但随着互联网规模的激增，通信子网的结构越来越复杂，大量数据包涌入到通信子网的节点路由器上，造成网络层的数据拥塞，这样仅仅依靠端到端的拥塞控制机制已经无法满足需求[3]。于是近些年来路由器上的拥塞控制机制也逐渐部署起来，称为节点拥塞控制机制，对于这类研究主要以主动队列管理AQM算法为主[4]。主动队列管理是一种基于先进先出(first input first output)调度策略的队列管理，能够控制路由器丢弃数据包的时间和数量。其核心思想是通过对网络拥塞实施早期监测，一旦发现拥塞的可能性，便主动向发送端发出拥塞信号，这时发送端便会降低数据包的发送速率，从而减少网络中数据包的数量，达到降低数据包丢失率和提高通信链路吞吐量的目的。在AQM算法控制下，路由器缓冲区出现溢出之前以一定的策略丢弃数据包，避免了队列溢出，解决了满队列问题。从拥塞控制的角度看，传统的队列管理算法只包含拥塞恢复机制，而AQM算法既包含拥塞恢复机制又包括拥塞避免机制，因此AQM算法对于提高拥塞控制的性能具有比较重要的作用，在路由器中使用AQM算法可以带来的好处包括：

(1)降低路由器中被丢弃数据包的数量。互联网中数据包的突发性从根本上是不可避免的，而AQM算法通过使路由器保持较短的平均队列长度(average queue length)，从而能够解决吸收突发数据包的问题，大大降低了突发数据包丢失的可能性。

(2)交互式应用实现更低的延时。AQM算法中路由器可以保持较短的平均队列长度，因此能够降低数据包的排队时延(queuing delay)，而排队时延是端到端时延的重要组成部分，这对交互式应用(如WEB浏览、Telnet和视频会议等)有重要帮助。

(3)避免网络“死锁”现象。“死锁”是指当拥塞严重到网络无吞吐量的现象，AQM算法能够确保路由器几乎总有可用的队列空间来容纳到达的数据包，从而可以防止“死锁”情况的发生。同时因为这个原因，AQM算法也能防止路由器对突发数据流的偏见。

随机早期丢弃算法(random early detection，RED)是AQM算法的一个代表，相比队尾丢弃算法DropTail，RED算法具有网络链路利用率较高、吞吐量较大、网络时延和丢包率较小的优点[5-6]。因此互联网工程任务组IETF将其作为唯一拥塞控制候选算法极力推荐使用，希望达到良好的节点拥塞机制的效果。

1 RED及ARED算法原理

1.1 RED算法概述

当节点路由器实施了RED算法，它会实时监控缓冲区平均队列长度，因为其作为一个重要指标用来判断网络是否出现拥塞。如果发现网络有出现拥塞的可能性，那么路由器便会以一定的概率丢弃接收到的数据包，并向发送端发送通知，发送端收到通知后会降低数据包的发送速率，这样进入网络的数据包便会减缓，使路由器队列长度维持在一个良性的状态，从而降低了网络传输延迟和丢包率，提高了网络资源的利用率，达到有效缓解网络拥塞的目的[7-8]。与传统DropTail算法相比，RED算法改进点主要体现在两个方面：第一，路由器不是等队列全部填满后再丢弃随后到来的数据包，而是在有可能出现拥塞之前通过计算概率随机丢弃部分数据包来预防可能出现的拥塞；第二，计算数据包随机丢弃概率时采纳平均队列长度而不是瞬时队列长度，因此能尽量满足突发数据流对路由器缓冲区空间的需求，降低产生网络全局同步现象的可能性。

当路由器实施RED算法控制机制时，其针对缓冲区队列事先设置了两个重要参数，即最小队列长度阈值THmin和最大队列长度阈值THmax。路由器接收到一个新到达的数据包时，首先计算缓冲区队列平均长度Lav，如果Lav小于阈值THmin，则丢弃概率为0，允许新到的数据包进入队列排队；如果Lav大于最大阈值THmax，则丢弃概率为1，将新到的数据包丢弃；如果Lav在阈值THmin和THmax之间，则会依据控制策略中的相关机制计算丢包概率P，并将新收到的该数据包按此概率实施丢弃。RED控制策略中计算平均队列长度Lav的方法是将瞬时队列长度Lsa和旧的平均队列长度Lav进行加权计算，其中权值Wq根据实际情况取[0,1]之间的值[9]，Lav的计算如式(1)所示。

Lav=(1-Wq)×Lav+Wq×Lsa

(1)

根据式(1)计算出平均队列长度Lav，与预先设定好的最小队列长度阈值THmin、最大队列长度阈值THmax进行比较，通过比较结果来判定网络拥塞的程度，以此作为决定数据包丢弃概率P的依据。具体来说就是：如果LavTHmax，则丢弃概率P为1，不允许新到的数据包进入缓冲区排队，直接丢弃；若THmin≤Lav≤THmax，会利用线性函数计算出丢弃概率P，并以此概率丢弃新到的数据包。其中计算丢弃概率P会涉及到预先设定的最大丢弃概率Pmax、上一次丢包之后新进入队列的数据包数量count以及相关的计算函数，式(2)和式(3)为采用线性函数计算所得从0到Pmax变化的Pb和丢弃概率P。

(2)

(3)

从以上公式可以看出，丢弃概率P的值不仅和路由器缓冲区平均队列长度Lav有关，同时也会随着进入缓冲区队列数据包数量count的增加而平缓增大，这样会使新到数据包的丢弃时间间隔相对平滑，避免密集地产生丢包现象[10]。

算法RED的劣势在于前面提到的各种参数的预置上，网络拥塞情况影响因素很多，是动态变化的，而相对固定的参数值不能很好地满足网络拥塞情况动态变化的需求[11]，因此对于RED算法的各种改进研究便集中在这点上面。

1.2 ARED算法概述

针对上面提到的RED算法中固定参数无法适应动态网络需求的缺点，相关研究提出了一些改进方法，其中最具有代表性的就是自适应RED算法，简称为ARED。在ARED算法中，最大丢弃概率Pmax不是使用事先设定好的固定值，而是根据平均队列长度的动态变化来调整Pmax。具体检测策略就是如果缓冲区平均队列长度在THmin附近波动，说明数据包丢失过多，拥塞控制策略过于激进，应减小Pmax；如果缓冲区平均队列长度在THmax附近波动，说明数据包丢失过少，拥塞控制策略有点保守，应增大Pmax。动态调整算法的具体伪代码如下：

every intertime

if(Lav>targetl &&Pmax≤0.5)

Pmax=Pmax+α;

else if(Lav

Pmax=Pmax*β;

其中intertime为检测缓冲区平均队列长度的间隔时间，一般取值为0.5秒；targetl表示缓冲区平均队列长度的目标值，其取值范围是[THmin+0.4*(THmax-THmin)，THmin+0.6*(THmax-THmin)]；α是加法增大Pmax的因子，一般取值为α=min(0.01,0.25*Pmax)，β是乘法减少Pmax的因子，一般取值为β=0.9。

1.3 算法对比

以下将通过仿真网络环境来模拟两种算法，模拟环境的组建采用网络仿真软件NS2[12-13]，对应的网络拓扑结构如图1所示。

图1 仿真实验网络拓扑结构

路由器r1和r2之间的链路为瓶颈链路，带宽设置为45 Mb/s，往返时延设置为20 ms，在路由器r1和r2上依次实施网络拥塞算法RED和ARED。s1到sn为一定数量的发送实体，d1到dn为对应数量的接收实体，发送实体与路由器r1连接，接收实体与路由器r2连接，所有链路的带宽均设置为100 Mb/s，往返时延设置为1 ms。在发送实体sn及对应的接收实体dn之间建立TCP连接，使用FTP协议流量。在两种拥塞控制算法中所用到的参数分别设置为Wq=0.002，Pmax=0.1，intertime=0.5 s，THmin=40 packets，THmax=180 packets，Buffersize=200 packets。建立80个发送实体和接收实体的并发连接，模拟运行时间100 s，在此过程中分别跟踪实施RED和ARED算法的路由器平均队列长度[14]，并绘制其变化如图2和图3所示。通过比较可以发现，ARED算法的平均队列长度振荡平缓，稳定性优于RED算法。

图2 RED算法平均队列长度变化

图3 ARED算法平均队列长度变化

2 ARED算法的优化

2.1 QARED算法概述

ARED算法在控制策略上增加了对Pmax参数的动态修订，这使得丢包概率能够随着网络数据流量的变化而动态调整，但随之又引入了三个新的参数intertime、α、β，造成ARED算法与RED算法一样存在着预置参数值选取的问题，不同参数值的选取会影响Pmax动态调整的效果。因此以下提出一种改进算法，称为QARED算法，主要目的是希望通过优化丢弃概率Pb的计算方式来提高路由器缓冲区平均队列长度的稳定性，以减少算法中固定参数值设定所带来的影响[15]。

在式(2)中计算Pb所采用的是线性函数，而QARED算法提出采用平方函数来进行计算，如式(4)所示，两种计算函数的曲线如图4所示。

(4)

图4 两种算法丢弃概率计算函数曲线

通过平方函数曲线可以看到，当缓冲区平均队列长度比较接近THmin时，丢弃概率Pb变化比较平缓；而当超过0.5*(THmin+THmax)，丢弃概率Pb变化加剧。这种处理方式带来的好处是在缓冲区平均队列长度较小时降低丢包率，从而提高包转发效率；而接近THmax时加大丢包率，减少拥塞的可能，最终维持缓冲区平均队列长度在一个稳定值，保证了网络的吞吐量。

2.2 QARED算法模拟实验及对比

在NS2网络仿真软件中，通过路径ns-allinone-2.29 s-2.29queue打开ARED算法实现C++源程序red.cc，其中calculate_p_new()便是Pb的计算函数，对应的语句为：

p=v_a * v_ave + v_b;

p*=max_p;

将计算方式改为：

p=(v_a * v_ave+v_b)*(v_a * v_ave+v_b);

p=0.5 * max_p+0.5*max_p*p;

然后重新编译NS2：

cd ns-allinone-2.29

cd ns-2.29

make clean

make

模拟QARED算法运行时设置与1.3小节中相同的参数，跟踪获得路由器缓冲区平均队列长度变化如图5所示。通过与ARED算法进行对比可以发现，在改进算法中缓冲区平均队列长度振荡更趋于平缓，其长度值差不多维持在0.5*(THmin+THmax)附近，这进一步证实了其稳定性要优于ARED算法，从而更有效地保证路由器缓冲区队列有空间来处理突发数据流，不会造成数据包的大量丢失，提高了数据包转发的效率。

图5 QARED算法平均队列长度

2.3 三种算法的时延和丢包率对比

在QARED算法中，由于缓冲区平均队列长度更加平稳，从而达到了降低数据包丢失率和网络平均往返时延的目的。在模拟实验定量分析中，通过NS2系统中的数据流监控对象Flowmon和分类器对象Classifier/Hash/Fid来对各种算法下链路的平均往返时延、路由器到达数据包数量和被丢弃数据包数量分别进行跟踪并记录，相关程序如下：

set fmon [$ns makeflowmon Fid];

$ns attach-fmon $link_r1r2 $fmon;

set redq [[$ns link $r1 $r2] queue];

set traceq [open red-tra($minthresh).tr w];

$redq trace curq;

$redq trace ave;

$redq attach $traceq;

然后利用绘图工具plot基于上面的跟踪数据绘制平均队列长度变化图。

plot 'red-cur(15).tr' using 2:3 title 'RED Buffersize=48' with lines

最后分别统计三种算法模拟实验中的平均往返时延、到达数据包数量、被丢弃数据包数量，以及计算丢包率，如表1所示。通过表中数据可以看出，QARED算法是最优的，证明了这种改进思路的有效性。

表1 三种算法数据对比

3 结束语

RED及其改进算法是更为有效的节点拥塞控制策略，通过模拟实验对比可以发现，当网络流量动态变化时，RED算法在控制平均队列长度稳定性上是成功的，因为当路由器平均队列长度超过了最大阈值后就采用均匀随机丢弃数据包的策略，有效控制了平均队列长度，降低了平均时延，消除了对突发数据流的偏见；同时也在很大程度上缓解了TCP数据流的“全局同步”现象。由于RED算法在不降低吞吐量的情况下可以大大降低传输延时，因此其综合性能要优于传统的DropTail算法。

基于RED及ARED算法，文中提出了一种调整丢弃概率计算函数的思路，并利用网络模拟软件NS2模拟算法的运行并跟踪收集相关数据，通过三种算法的对比分析验证了改进算法QARED相对于ARED算法在控制路由器缓冲区平均队列长度稳定性上的优势，QARED算法能够支持更低的网络时延和丢包率，提升网络动态变化下拥塞控制策略的稳定性。但不管是ARED还是QARED算法，在其运行过程中相关参数的预置仍然是基于常规的网络情况，如何更好地动态调整相关参数的设置来满足不同的网络情况是这类算法后续改进的研究点。