队列管理RED算法的性能研究.pdf

队列管理 RED 算法的性能研究 汪琼1，吴斌2 1北京邮电大学，北京 2南京邮电大学，南京 wangqiongyeye@ 摘 要：摘 要： RED 算法是一种非常有效的避免拥塞和维持网络高链路利用率的队列管理机制 RED算法的实际性能主要取决于四个控制参数的设置 然而， 关于 RED 算法的设置至今还没有一个很好的指导方针；针对各种异构网络，还未能提出设置其参量的有效方法，以维持各网络更高的链路利用率本论文在对 RED 算法及其参数设置进行深入研究的基础上，使用 NS 模拟工具模拟网络环境， 根据仿真结果详尽地分析了 RED 算法四个参数设置对网关中各个性能指标的影响，提供了对不同网络设置不同 RED 参数的参考方案 关键词：关键词：RED 算法； 参数设置； NS 模拟 1. 引言 1. 引言 网络中采用的调度机制与网络的服务质量 QoS 有着密切的关系随着 Internet 的迅速发展，网络规模越来越庞大，结构日趋复杂，仅仅依靠端到端的拥塞控制还不够，网络本身也必须参与资源的控制和管理，在网络发生拥塞时，网络节点必须丢弃一些分组，这个问题的解决首先必须实施有效的队列管理机制[1]。

之前的研究已经提出许多有效的队列管理机制，如：随机丢弃算法(Random Drop gateways)算法、尾部丢弃策略（Drop Tail gateways） 、DECbit 算法和 ERD（Early Random Drop）算法等算法但它们都有一定的缺陷，RED 算法就是在弥补这些缺陷的基础上提出来的 随机早期检测算法（Random Early Detection）[2,3]：采用低通滤波器模型来计算平均队长，支持突发业务，使得网关处理算法实现的更为合理，避免了网关因根据变化的实际队列长度而不断的变更处理方法， 该算法因其具有较低的时延， 较高的吞吐量和较好的公平性而被广泛采用它通过在拥塞即将发生时丢弃，能够有效地避免全局同步 RED 算法已成为路由器中的默认拥塞控制机制RED 工作性能的优劣很大长度上是由其预先设置的参数、mi、ma和ma决定的一组 RED 参数也许是给定业务吞吐量的最优化参数，但对于连续丢包、延迟等就未必是最优参数因此如何权衡它们（吞吐量、延迟等）之间的关系，有针对性地找到最优的参数，仍然有待进一步研究RED 参数的微小变化会给总体性能带来很大的影响 qwnthxthxp本论文主要目标是研究讨论 RED 算法参数， 明确其与网络中各项指标的关系， 提出一个可行的针对不同网络环境调节算法参数的参考方案， 使 RED 算法发挥更好的性能。

本论文结构如下： 先介绍了 RED 算法及其较之其他算法的优越性， 并理论上分析了其参数对不同性能指标的敏感性然后通过设计大量的仿真实验，分析了包括拥塞控制、平均队长、丢包和吞吐量等指标，确定 RED 算法参数与调节特定的性能指标之间的关系 1（100876） （210003） 2. RED 算法原理及其参数 2. RED 算法原理及其参数 由于以往使用的算法存在许多不足之处， 如： 持续的满队列状态、 业务流对缓存的死锁、业务流的全局同步、对突发流的不公、平均队长计算不合理等所以 RED 算法设计必须避免或改进这些不足，实现以下目标： （1）通过控制平均队长来避免拥塞； （2）避免全局同步问题； （3）允许突发业务 2.1 RED 算法的原理 2.1 RED 算法的原理 RED 算法使用一个指数权值平均的低通滤波器计算平均队列长度平均队列长度和两个门限值比较：一个下限（）和一个上限（） ；当平均队列长度在上限和下限之间时，每个到来的分组以概率minthmaxthap标记，ap是队列平均长度avg的函数，每当有个分组被标记时， 该分组被标记的可能性与该特定节点所要求占用的带宽成比例。

当平均队列长度低于下限时，不丢弃（即丢弃概率为 0）到来的分组；当平均队长在下限和上限之间时，以概率ap丢弃到来的分组；当平均队长超过上限时，则丢弃到来的全部分组（即丢弃概率为 1） 可以看出，RED 算法分两部分：一是计算平均队长，一是计算标记概率平均队长的设定影响到网关队列突发度；标记概率则决定网关标记数据包的频度，表明网关当前拥塞程度 2.1.12.1.1 平均队长的计算 平均队长的计算 RED 算法用低通滤波器来计算平均队长，所以由突发业务或者瞬时拥塞导致的队长短期增长，并不会过大的影响平均队长低通滤波器是指数加权动态均值，平均值计算如下： (1)qavgw avgw q=−+q)(1) 即 (2) (qavgavgw qavg=+−式中为平均队列长度;为权值， 对应于低通滤波器时间常数；q为当前队列长度 avgqw2.1.22.1.2 标记概率的计算 标记概率的计算 初始的分组标记概率bp是平均队列长度的线性函数标记概率有两种方法：其一，当平均队列长度是常量时，两次标记之间的分组数是几何随机变量；其二，两次标记之间的分组数是统一随机变量。

最初的标记概率计算方法如下： max (min )/(maxmin )bpthththpavg=−− (3) 参量是标记概率的最大值，当平均队列长度到达上限时取 maxp方法一：几何随机变量法此法每个分组以概率bp标记，设X为两次被标记分组之间的分组数，由于每个分组均以概率bp标记，则： 1Pr[](1)nbob Xnpp−==−b (4) 因此，X是一个几何随机变量，并有：[]1/bE Xp= 2平均队列长度是常数时， 如果以一定时间间隔标记分组， 则短时间内标记太多的分组是不能接受的， 两个标记分组之间间隔太久也是不能接受的； 因为这些情况都能引起许多节点同时减小发送窗口，从而导致全局同步 方法二： 统一随机变量法 此法是把X设为统一的随机变量， 取值范围是{1,2,...1/}bp（简单的假设1/bp是一个整数） ；每个到来的分组以/(1*)bbpcountp−的概率被标记，其中的是自上一个分组被标记以来的分组数在这种情况下： count20Pr[](1)1 (1)111/n bbibbbppob Xnnpippfornp−===−−−−=≤≤∏ b(5) 且， Pr[]0 1/bob Xnfor np==>；可有：[]1/(2) 1/2bE Xp=+。

文献[4]中，实验得出方法二标记的包比方法一更均匀，RED 算法采用标记方法二 2.2 RED 算法的参数设置 2.2 RED 算法的参数设置 RED 算法在实践中性能的好坏取决于参数的设置， RED 算法中有如下几个参数需要设置：平均队长的权值，最大丢包概率，下限和上限ma qwmaxpminthxth2.2.1 权值 2.2.1 权值 qwqw影响平均队长的计算，当取值比较大时，平均队长容易受瞬时队长的影响，此时平均队长增长较快，相应的允许突发能力较弱；如果取值较小，平均队长变化很小，可能导致发生拥塞却检测不到，达不到控制的目的参数还决定路由器中数据包在队列中的延迟在文献[4]中给出的参考取值为 0.002 qwqwqwqw（1）的上限范围 qw如果太大，计算平均队列长度的程序将不能滤出网关中的拥塞，假设队列开始为空，即平均队列长度是 0，当L个分组到来后，队列长度从 0 变到L；在第L个分组到达网关后，平均队长和、L的关系如图 1 所示： qwLavgqw图1 是和L 的函数 Lavgqw 3图中， X轴表示从0.001变化到0.005， Y轴表示L从10变化到100 例如： 当=0.001时，在队列长度从 0 变到 100 时，平均队列长度大概是 5 个分组。

qwqwLavg假设一个下限和网关中允许的突发长度L个分组，那么应该满足下面的不等式： minthqwminLtavg

可以根据需要来设置，但要求不能设置太大一般设置在 0.02 或稍大一些，在文献[4]中给出的取值不能大于 0.1，如果过大，容易使丢包严重拥塞比较严重时，当平均队长超过最大门限时会自动丢包，所以也不能设置过大 maxpmaxpmaxp2.2.3 下限2.2.3 下限mi和上限 和上限 nthmaxth下限和上限的设置取决于所允许的突发业务[5] 如果业务突发性比较强， 可以将设置得偏大些；ma的设置和允许的最大延时相关，如果对延时不敏感，max可以设置偏大；对延时敏感的业务，则不能过大和的设置会影响链路利用率，设置成往返时间内的平均队长比较合适；通常ma不能小于的两倍 minthxththmaxthmaxthminthmaxminthth−xthminth2.3 参数敏感性 2.3 参数敏感性 不同于只有一个自由参数 （缓冲器长度） 的尾部丢弃策略， RED 算法有一些附加的参数拥塞避免机制应有较低的参数敏感性，且参数应该在带宽变化很大的网络中都适用RED 算法参数，，和是必须设置的，便于网络设计者可以考虑平均队列长度和队qwminthmaxth 4列中容许突发流的长度及其持续时间参数可以设置在一个相当大的范围内，用于标记概率maxpbp的上限，如果拥塞严重，以至于网关通过以概率标记分组不能控制平均队列长度，则平均队列长度将超过上限，网关将标记每个到来的分组，直到拥塞被控制。

maxp针对特定的通信环境和网络参数，我们为 RED 算法设定一些标准以发挥更好的性能： 1． 保证恰当的计算平均队列长度：设0.001，网关中的平均队列长度受所限，计算得到的平均队列长度准确地反应了实际队列的平均长度，权重不能被设置的太小，这样计算得到的平均队列长度才能及时反应在实际队列长度的增加 qw≥maxthavgqw2． 足够大以保证网络的利用率；由于网络流量常是突发的，如平均队列长度设置太小，链路不能充分利用此外，还须设定不同网络环境下的最佳平均队列长度 minth3．设置maxminthth−充分大以避免全局同步：设置maxminthth−大于在一个周期内增加的平均队列长度， 以避免由同一时间内标记过多分组而引起全局同步； 一个首要的规定是设置是的两倍 maxthminth3. RED 算法参数的仿真和设计 3. RED 算法参数的仿真和设计 仿真主要目标是研究讨论 RED 算法参数， 提出一个可行的参数设计参考方案， 使在不同的网络环境下，可以根据不同需要调节。