一种改进的主动队列调度RED算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种改进的主动队列调度RED算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

[摘 要] 本文在分析RED利用EWMA形式计算平均队列长度的局限性的基础上,提出了一种改进的RED算法。该改进RED算法在计算平均队列长度时考虑了当前队列长度的真实情况,并将两者结合起来进行丢弃决策。仿真结果表明改进RED算法在分组丢弃比例和链路利用率上都优于RED。

[关键词] 网络拥塞 RED

[中图分类号]TP273.2[文献标识码]A[文章编号]1007-9416(2010)03-0105-02

引言

随着互联网规模的增长,互联网上的用户和应用都在快速的增长,拥塞已经成为一个十分重要的问题。根据算法的实现位置,可以将拥塞控制算法分为两大类:链路算法 (Link Algorithm)和源算法(Source Algorithm). 拥塞控制算法设计中的一个关键问题是如何生成反馈信息和如何对反馈信息进行响应。在拥塞控制的源算法方面,大量的工作集中在对TCP协议的研究上,主要针对对目前广泛使用的主动队列管理算法中的RED进行了研究。然而RED算法在响应速度、稳定性等方面仍有缺陷。

1 随机早期检测算法(RED)其算法实现设计

1.1 RED算法的基本思想

RED拥塞控制机制的基本思想是通过监控路由器缓冲区队列的平均长度来探测拥塞,一旦发现拥塞逼近,就随机地选择连接来通知拥塞,使他们在队列溢出导致丢包之前减小拥塞窗口,降低发送数据速度,从而缓解网络拥塞。由于RED算法是基于FIFO队列调度策略的,并且只是丢弃正进入路由器的分组,因此其实施起来也较为简单。red算法按照指数权值移动均值EWMA(Exponential weighted Moving Average)的方法来计算平均队列长度,并且随机地选择正进入路由器的包进行丢弃。这种方法能被有效地实施而无需在路由器中维持每个流(Per-Flow)的状态信息。

RED算法主要分为两个部分。首先是计算平均队列长度,以此作为对拥塞程度的估计。另一个就是计算丢弃包的概率。

(1)计算平均队列长度。

由于Internet数据的突发性,如果一个队列在很多时候是空的,然后迅速被充满,又很快被取空,这时就不能判定路由器发生拥塞而向源端发送拥塞指示。因此,RED算法在计算平均队长时采用了类似低通滤波器(Low Pass Filter)带权值的方法:

(1)

其中,为权值,为队列采样数据。

由于Internet数据的突发本质或者短期拥塞导致的实际队列长度暂时的增长将不会使平均队长有明显变化,从而“过滤”掉短期瞬间的队长变化,尽量反映长期的拥塞变化。在计算平均队长的公式中,权值相当于低通滤波器的时间常数,它决定了路由器对输入流量变化的反应程度。因此对的选择非常重要,如果过大,那么RED算法就不能有效地过虑短暂的拥塞;如果太小,那么就会对实际队列长度的变化反应过慢,不能合理地反映拥塞状况,在这种情况下,路由器就不能有效检测到早期的拥塞。的值应根据不同情况预先设置,一般来说,它是由路由器允许发生的突发业务的大小和持续的时间所决定的。

(2)计算丢包概率

计算平均队长的目的就是为了反映拥塞状况,根据拥塞的程度来计算丢弃包的概率,从而有效地控制平均队列长度。RED算法有两个和队列长度相关的闭值:和。当有包到达路由器时,RED算法计算出平均队长。计算丢包概率Pa的方法如式(2)、公式(3)。

(2)

(3)

算法的第一部分决定了所允许的突发长度,而算法的第二部分决定了在给定的当前拥塞级别时分组的丢弃频度。丢包概率的计算很大程度上是依赖于平均队列长度的计算,而从下一节的分析将会发现这种计算方式的性能并不理想。

1.2 对RED中EWMA的分析

EWMA滤波器的性能取决于权值的选择。如果太大,则短期内的拥塞影响将不能被滤去;反之,如果太小,则平均队列长度就不能很好地跟踪当前队列长度q的变化。另一方面,太大也会造成队列长度的剧烈振荡。的上限由下式给出:

(4)

而的下限值通常由观测值给出,即:当前队列长度q保持为1个分组时,需要个分组使得平均队列长度从0变为0.63。(实际中,通常取为0.002左右,以避免对突发流的偏见)。

文献[4]中指出,自适应RED算法中,对于容量为C,RTT时间为R的瓶颈链路,按下式取值:

(5)

这样,将根据网络环境自动调节其值。考虑一条容量为C的瓶颈链路,RED路由器的发送速率小于C,权值取比较小的值。此时当前队列长度不会增加,平均队列长度也会比较小。加入另一业务流,使得路由器上总的分组到达速率大于C。这时q很大,而平均队列长度只在分组到达时计算,这就使得远远超过最大门限,随后到达的分组将全部被丢弃。

由于平均队列长度将经历一段时间才能变为低于,所以对到达分组的丢弃也将持续一段时间,即使当前队列已经为空了,分组丢弃可能还在进行中。另一方面,由于在这段时间内到达的分组都将被丢弃,所以分组发送率也会很低。

只有当平均队列长度降到低于时,对到达分组的操作才会转为正常。另一方面,分组的丢弃将造成发端的重传,这样分组到达速率的增加又导致的再次增加,这样反复下去,将在附近振荡,并且到达的分组又将再次被丢弃。因此,在特定的分组到达速率、瓶颈链路传送速率和业务流响应速度下,在较长的一段时期内,即使当前缓存为空,所有到达路由器的分组都将被丢弃。

从上面的分析可以明显看出和时,虽然当前队列长度q远低于,但由于丢弃决策是根据给出的,所以仍有大量不必要的分组丢弃。这表明,用EWMA形式计算并不能反映缓存中RED队列的真实变化情况。有时,由于这种计算方式得到的错误地给出了当前缓存的占用情况,会导致宝贵网络资源的浪费。

根据上面的分析,可以将EWMA计算并由此决定分组丢弃的局限性分析归纳如下:

(1)由于的EWMA计算只在分组到达时进行,所以随着分组的到达它可能以任何速率增加。另一方面,这也使得平均队列长度的下降速率将受限于瓶颈链路的带宽。因此,平均队列长度的计算反映的是分组到达速率而不是缓存的真实占用情况。

(2)如果有突发流到达,则在瓶颈路由器上,分组到达速率远大于分组离开速率。两个速率的差异使得式(1)更像一个峰值检测器而不是EWMA滤波器了。因此,这种平均队列长度的计算对较大的队列长度值有一定的偏见。

文献[5]中对该问题也进行了讨论,并提出了一种新算法――FRED(Flow Random Early Detection,流随机早期检测)。但是FRED在性能上有一定的局限性,它要为每个活动流保留状态变量,降低了其适用性。为解决上述EWMA形式计算平均队列长度带来的问题,下面将提出改进的RED算法,该算法将当前瞬时队列长度结合到分组丢弃的计算中。

2 改进RED算法

2.1 减小

RED对当前队列长度采用EWMA形式计算平均队列长度,并由所得到的来决定丢弃概率,该方式不能很好地反映当前队列的真实变化情况,所以可以考虑将当前队列长度结合到平均队列长度的计算中,并结合当前队列长度和来决定丢包概率,而不是仅仅由平均队列长度来决定丢包。具体为:在当前队列长度时调节的计算;在将到达分组放入队列时考虑当前队列长度的实际情况。

对式子(1)式进行离散,并将赋值改为等于,则在n时刻,(1)式改写为:

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文

(6)

进行移项,可得:

(7)

式子(7)和(8)体现了q和之间的相互依赖关系。

平均队列长度由0增加到缓存大小B的过程它必须先后经过上下门限值和。如果在个分组连续到达后,当前队列长度仍小于,则通过引入一个因子()来减小式(6)第一项的贡献,这样平均队列长度将很快降到低于或是在附近。该算法的离散形式如下:

(8)

可以看出公式(8)的有效性依赖于参数对的恰当取值,否则它会降低该改进算法的性能,而且会造成平均队列长度的剧烈振荡从而导致稳定性问题。并且为取得性能上的改善,在和的取值上应该权衡考虑。对于大的值,也应该较大;反之,取较小值时,也应该较小。

如果的取值可以使在时,,则随后到达的分组将以一定的概率丢弃,而不是全部丢弃,该概率由式(2)并结合(3)给出。这样,丢弃的分组数将大大减少,从而减少了网络带宽资源的浪费,提高链路利用率。

2.2 分组丢弃计算

在改进的RED算法中,分组丢弃决策不仅仅由决定,而是结合考虑当前队列长度和。新的丢弃关系如图1中的1～11区域所示。区域1和11对应于强制丢弃,2、3、4、6、7对应于随机概率丢弃。按照RED算法,当时(对应图3中的区域4,7和10)到达的分组都将被丢弃。而相比之下,改进的RED算法在区域7()和10()仍可以将到达的分组入队。更保守点的做法可以在时,只在区域10才将到达分组入队。反之,如果区域10也被去掉,则就是原始的RED算法了。

3 仿真

3.1 仿真环境设计

本文仿真所采用的网络拓扑结构为一典型的(单边)哑铃结构,如图5所示。其中路由器R1和R2之间的链路为网络瓶颈,带宽为10Mbps,延迟为5ms。各节点与路由器之间的链路带宽为100Mbps。仿真时间为50s,节点S1、S2和S3发送FTP业务流。仿真使用的分组长度设定为1000字节。瓶颈链路上使用本文中的改进RED,其余链路均采用“弃尾”算法。各路由器的缓存大小均为50个分组。改进RED中的参数取值和RED一样:,,。

为同RED进行性能上的比较,本文采用的度量标准是平均队列长度的变化图,链路丢包率比例和链路利用率,其中和由下式给出:

(9)

(10)

3.2 仿真结果与分析

首先我们给出了RED和改进RED在链路分组丢失比例和链路利用率上的比较。图3和4给出了,各种取值组合下的和的变化情况。

根据图3可看出,在图中给出的和的各种取值组合下,改进RED的丢包率都低于RED。

根据图4可看出,改进RED在上面给出的和的取值组合中其链路利用率都明显高于RED。除了时的最大值出现在附近,其余的取值情况下的最大值都出现在内。对和的取值应结合网络实际情况和用户需求在链路利用率和链路分组丢失比例之间进行权衡考虑。总之,改进RED在总体性能上优于RED。

4 结语

在分析RED利用EWMA形式计算平均队列长度的局限性的基础上,提出了一种改进的RED算法。改进RED算法由于在计算平均队列长度的时候结合考虑当前队列的实际情况,大大减少了分组丢弃数,从而减少了网络带宽资源的浪费,在分组丢弃比例和链路利用率上都优于RED。

[参考文献]

[1] Bruce Eckel著,刘宗田,袁兆山,潘秋菱等译,C++编程思想 第一卷:标准C++引导.北京:机械工业出版社,2002.

[2] 任丰原,林闯,刘卫东,IP网络中的拥塞控制,计算机学报,2003,26(9):1025～1034.

[3] S. Floyd,V.Jacobson,Random early detection gateways for congestion avoidance, IEEE/ACM work.1(4)(1993):397-413.

[4] Harsha Sirisena, Aun Haider, and Krzyszt of Pawlikowski. Auto-Tuning RED for Accurate Queue Control. IEEE Globecom,2002.

[5] 徐雷鸣,庞博等.NS与网络模拟.北京:人民邮电出版社,2003.

[6] 吴春明,姜明.几种主动式队列管理算法的比较研究.电子学报,2004,32(3):429-434.

[7] 李春燕,梁述海,马军.拥塞控制机制――RED的研究.计算机应用与软件,2003,vol20:35～37.

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文