改进ARED拥塞控制算法研究与实现

薛礼　陈利

摘要：为实现基于路由器的拥塞控制算法性能提升，分析了RED与ARED拥塞控制算法，并提出一种改进算法QARED。与传统DropTail算法对比，RED算法具有较高链路利用率、吞吐量及较低网络延迟、丢包率等优点，但存在参数配置无法适应网络动态改变的缺点。ARED算法增加了自适应功能，根据平均队列长度变化动态调整最大丢包概率，稳定平均队列长度在最小阈值与最大阈值之间，但存在瞬时队列长度振荡等稳定性问题。改进算法QARED，通过优化最大丢包概率计算函数，以提高平均队列长度稳定性、降低丢包率、提高吞吐量。通过NS2仿真网络环境对比，改进算法QARED相对ARED算法在控制平均队列长度上更具稳定性，能够实现更低网络延迟与丢包率，提高了动态网络环境下拥塞控制稳定性。

关键词关键词：拥塞控制；ARED；NS2网络模拟

DOIDOI：10.11907/rjdk.171861

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2017）011004103

0引言

随着互联网流量增多，网络拥塞日趋严重。网络出现拥塞，会带来延时增大、丢包、重发增多、吞吐量减少等问题，严重时还会导致网络瘫痪。因此网络拥塞控制成为传输层协议实现的重要功能，在TCP协议Tahoe、Reno等版本中包含了慢启动、拥塞避免、快速重传、快速恢复算法以及改进算法。通过端系统拥塞控制机制能够很好地保证网络可靠性与稳定性，改善服务质量QoS。近年来，拥塞控制机制在路由器中也开始实施，拥塞控制策略研究主要集中于主动队列管理AQM算法[1]。AQM算法一个代表是随机早期丢弃RED，相比传统队尾丢弃Droptail具有较高链路利用率、吞吐量与较低网络延迟、丢包率等优点，IETF推荐其作为唯一候选算法，在目前结点拥塞控制中起到了重要作用[2]。

1算法原理

1.1RED算法思想

RED算法中，路由器通过监测平均队列长度探测拥塞，在拥塞可能出现的时候，按一定概率随机丢弃某些分组，通知发送端降低数据发送速率，维持合适队列长度，降低网络延迟，缓解网络拥塞[3]。RED算法中对瞬时队列长度Lsa采用指数加权计算平均队列长度Lav，权值Wq介于0～1之间，如式（1）所示：

Lav=（1-Wq ）×Lav+Wq×Lsa（1）

對比平均队列长度与事先设置的队列最小阈值THmin、最大阀值THmax，判断网络拥塞程度，决定分组丢弃概率。具体标准是若LavTHmax，则丢弃概率为1，分组被丢弃；若THmin≤Lav≤THmax，则计算出丢弃概率P，并以此概率丢弃分组。其中P的计算会利用事先选用的最大丢弃概率Pmax以及计算函数（例如采用线性增长从0变到Pmax），count代表上一次丢包后新进入队列的包数量。

Pb=Pmax×Lav-THminTHmax-THmin（2）

P=Pb1-count×Pb（3）

从式（2）、式（3）可以看出，丢弃概率P不仅与平均队列长度Lav有关，还随着队列中不被丢弃数据包数目增多而增大，这样可使数据包丢弃间隔相对均匀，避免数据包丢弃过于集中，造成全局同步现象[4]。RED算法缺点在于参数设定，一组固定参数值无法满足网络动态变化需求[5]。

1.2ARED算法思想

研究者针对RED算法提出了改进方案，其中ARED算法是通过检查平均队列长度变化来动态调节最大丢弃概率Pmax，如果平均队列长度是在THmin附近波动，那么拥塞控制就太积极，应减小Pmax值；如果在THmax附近波动，那么拥塞控制就太保守，应增大Pmax值。动态调整Pmax算法如下：

every interval time

if （Lav>target && Pmax≤0. 5）

Pmax=Pmax+α；

else if （Lav

Pmax=Pmax*β；

其中interval time为调整丢弃概率时间间隔，一般取0.5s；target表示平均队列理想区间范围[THmin+0.4*（THmax-THmin） ， THmin+0.6*（THmax-THmin）]；α、β分别表示Pmax增大及减小因子，α=min（0.01，Pmax/4），β= 0.9。

1.32种算法对比

利用网络模拟软件NS2构建仿真环境，网络拓扑如图1所示。

仿真环境中路由器r1与r2之间为瓶颈链路，带宽45Mbps，延迟20ms，队列算法分别采用RED与ARED。s1到sn为源端，d1到dn为目的端，分别与r1、r2相连的链路带宽为100Mbps，延迟1ms。sn与dn依次对应建立TCP连接，使用FTP数据流。算法参数设置为Wq=0.002，Pmax=0.1，interval=0.1，THmin=50packets，THmax=150packets，Buffersize=200packets。图2与图3是构建80个连接，运行100s模拟时间，分别跟踪RED与ARED算法的平均队列长度[6]。通过比较可以发现ARED算法平均队列长度稳定性优于RED算法。

2ARED算法改进及对比

2.1QARED算法思想

ARED算法改进了Pmax的动态调整，但计算过程又引入了3个参数interval、α、β，同样存在参数设置问题，不同设置会影响Pmax调整效果[7]。因此本文提出一种改进的QARED算法，通过修改丢弃概率计算来巩固平均队列长度稳定性[8]。

式（2）中，Pb的计算采用线性函数，而改进算法采用二次方函数计算，如式（4）所示，它们的函数曲线见图4。由图4可知，平均队列长度接近THmin值时，丢弃概率变化相对缓慢，而超过0.5*（THmin+THmax）之后，变化加快，就能够在平均队列较短时降低包的丢弃概率；接近最大门限值时加大丢包概率，平均队列长度维持在合适值，可保证稳定性。