RED算法

11、REDRED拥塞控制机制的基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。由于RED是基于FIFO队列调度策略的，并且只是丢弃正进入路由器的数据包，因此其实施起来也较为简单。RED主要试图达到以下目标：(1)最小化包丢失率(2)最小化排队延迟(3)避免全局同步现象(4)避免对突发流的偏见：网络中含有大量的突发数据，而传统的去尾算法对突发流有很大的偏见。在采用去尾算法的路由器中，如果某个流的突发性越高，则当该流的包进入队列时越容易造成队列溢出，从而导致连续地丢弃大量的该流的包。即使在缺乏传输层协议有效配合的情况下也能控制平均队列长度，从而避免拥塞。为了达成以上目标，RED采用了基于时间的平均队列长度，并且随机地选择正进入路由器地包进行丢弃。这种方法能被有效地实施而无需在路由器中维持每个流（per-flow）的状态信息。RED算法主要分为两个部分。首先是计算平均队列长度，以此作为对拥塞程度的估计。另一个就是计算丢弃包的概率。计算平均队列长度：qwavgwavgqq)1(其中，qw为权值，q为采样测量时实际队列长度。这样由于网络数据的突发本质或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队长有明显的变化，从而过虑掉短期的队长变化，尽量反映长期的拥塞变化。在计算平均队长的公式中，qw权值相当于低通滤波器的时间常数，它决定了路由器对输入流量变化的反应程度。因此对qw的选择非常重要，如果qw过大，那么RED就不能有效地过虑短暂的拥塞；如果qw太小，那么就会avg对实际队列长度的变化反应过慢，不能合理地反映拥塞状况，在这种情况下，路由器就不能有效检测到早期的拥塞。qw的值应根据不同情况预先设置，一般来说，它是由路由器允许发生的突发业务的大小和持续的时间所决定的。计算丢弃包的概率：计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃包的概率，从而有效地控制平均队列长度。RED有两个和队列长度相关的阈值：thmin和thmax。当有包达到路由器时，RED计算出平均队长avg。若avg小2于thmin，则没有包需要丢弃；当thminavgthmax时，计算出概率P，并以此概率丢弃包；当avgthmax时，所有的包都被丢弃。由于RED使用的是基于时间的平均队长，就有可能会发生实际队长大于平均队长的情况，如果队列已满，则到达的包只能被丢弃。计算概率ap的方法如下：)min/(max)min(maxthththpbavgp)1(bbapcounpp我们注意到ap不仅和avg有关，而且还和从上一次丢包开始到现在进入队列的包的数量cout有关。随着cout的增加，下一个包被丢弃的可能性也在缓慢增加。这主要是为了在到来的包之间均匀间隔地丢包，避免连续丢包，从而避免对突发流的偏见和产生全局同步现象。下图一显示了RED算法的丢包概率与平均队列长度之间的关系。从图中,我们可以看出丢包概率在两个阂值之间时先缓慢地增加,而一旦到达最大阈值thmax时,会达到最大值pmax。当然,也有研究者建议从随机丢弃到完全丢弃的过度应该更“平滑”,文献[27]提出一种改进的“Genile一RED”算法,该算法在计算丢包概率时引入了一个新的参数thmax2,如果平均队列长度ththavgmax2max,丢包概率按下面的公式计算：thppaavgpmax/)max1(1max2图一对队列管理而言，吞吐量和排队延迟始终是一对矛盾的关系。如果平均队长能够充分权衡吞吐量最大化和延迟最小化之间的矛盾，从而在总体性能上得到较为理想的结果，则该队长称为理想的平均队长。阈值thmin和thmax就是由理想3的平均队长决定的。一般来说，ththminmax应大于一个回路响应时间内平均队长的增加值，以避免由于路由器丢弃过多的包而导致全局同步。根据目前网络上数据流的特点，可以将thmax设为thmin的两倍。这样在高负载的情况下,平均队列长度会介于两个阈值之间,在出现突发流量时,仍有超过thmax的缓存可以容纳突发流量,路由器不至于因此而丢包进入“去尾”的方式,因此RED对于突发数据流有较强的适应性。RED具体实现算法如下：4图：RED算法实现图尽管大量的实践证明RED算法能够有效地降低平均排队延时和提高吞吐量,但RED算法依旧存在一些缺陷。研究者在文献中指出RED的性能与其参数设置和网络负载密切相关,在特定的网络状况下RED仍然会导致多个TCP的同步,造成队列振荡、吞吐量降低和延时抖动加剧。实际上,RED的参数设置一直以来都是一个难点问题,众多研究者针对这一问题提出了不同的指导和建议,同时也产5生了许多RED的变种算法,例如Self-ConfiguringRED、ARED(AdativeRED)、FRED、WRED等。他们从RED算法的稳定性和公平性角度对RED算法做出了相应的改进。本章的后面部分将对其中几种算法进行简单的介绍。2、FREDFRED算法被提出的初衷是为了解决RED算法中的公平性问题，即各个TCP流之间以及TCP和UDP混合流之间能公平的共享带宽。其基本思想是在路由器节点处记录每个活动流（在缓冲区队列中有分组存在的流）的状态信息，当拥塞发生时，FRED综合考虑各流的状态、在缓冲区中存在的分组的数量、队列长度以及距离上次丢弃分组的时间等信息来确定丢弃概率和将要被丢弃的分组所在的数据流。FRED将在网络中传输的数据流分成三类：Fragile流、Robust流、Non-adacptive流。Fragile流一般指那些RTT较大，发送窗口较小，能对拥塞通知做出响应，但或者对分组丢弃过于敏感，或者对可用带宽的适应性慢的TCP流；Robust流是指那些RTT较小，发送窗口较大，能对拥塞通知做出响应并能充分利用现有的网络条件发送数据的TCP流；Non-adaptive流一般指不能对拥塞通知做出响应的UDP流。FRED在RED的基础上做了些扩展，新引入参数thmin和thmax,分别表示每个Flow的允许缓存的最小分组数和最大分组，引入一个表示所有Flow的平均队列长度的全局变量avgcq；为每个Flow设置两个保存状态的变量iqlen和istrike，iqlen表示第i个Flow在缓冲区中的分组数，istrike表示第i个流过度占用带宽的次数，该变量主要用来鉴别Non-adaptive流。当一个数据分组进入路由器时，比较iqlen和thmin、thmax，按照RED算法决定如何处理iFlow的的分组，当iqlenjqlen时,标记第j个Flow的概率大于标记第i个流的概率，当iqlenthmax时，标记第i个Flow的概率就会大大增加，这样就保护了Fragile流。如果某个Flow的strike大于1，则说明该流为Non-adaptive流，那么将不允许该流的qlen超过avgcq，从而达到对响应流的保护。同时,FRED不仅在有数据分组到达时计算平均队列长度，在数据分组离开时也会计算平均队列长度，这样使得平均队列长度更加及时准确地反映了队列的变化情况。FRED有效的鉴别和限制非响应流，保护了脆弱流，平均传输时间更为公平，但它需要在路由器中维护每个流的状态信息，增加的路由器的计算开销和存储开销。FRED有效的鉴别和限制非响应流，保护了脆弱流,平均传输时间更为公平，但它需要在路由器中维护每个流的状态信息,增加的路由器的计算开销和存储开销。3、Self-ConfiguringRED6所有的AQM算法的基本原则是为源端提供早期拥塞预警,防止因缓存溢出而导致的丢包。在拥塞严重的网路中,拥塞信息必须要通知到足够多的源端,以充分降低负载。另一方也要避免拥塞信息通知了过多的源端,导致资源利用率下降。因此，AQM算法需要恰当地调节拥塞信息通知的速率,从而有效地在降低丢包率和提高网络利用率之间取得平衡。基于这一思想，self-configuringRED提出了一中自动调节机制,根据流量的变化来适当地配置RED参数。RED中,参数pmax体现了拥塞指示的发送速度。对于较小pmax值,不能提供有效地早期拥塞提示，丢包主要是因队列溢出造成的；而当pmax太大时，丢包主要是由早期拥塞检测产生的。RED的一个缺陷是平均队列长度对拥塞程度和参数设置敏感。如果拥塞严重或pmax很小，avg将接近或超过thmax；如果拥塞不严重或pmax很大，则avg会接近thmin。这使得平均排队延时对流量负载和参数设置很敏感。研究表明[29一32],对于给定的丢包率p,一条TcP连接的带宽上限可以用下面公式估计:PCRTTMSSBW其中,MSS是最大段长(Maxi~segmeniSize),RTT是往返时间,C是一个常量。在N个TCP流竞争带宽为L的瓶颈链路的情况下,有:PCRTTMSSNL那么，可得：2)(RTTCMSSLNp当所有的连接都使用TCP拥塞避免机制,丢包率上限与连接数的平方成正比。因此,激进的方法或者说pmax较大时，适合流较多的情况；而保守的方法或者说pmax较小时，适合流较少的情况。Self-ConfiguringRED算法的思想是通过检测平均队列长度的变化来判断RED是否需要增加或者减少其侵略性(增大或者减小pmax)。如果平均队列长度保持在thmin附近摆动，说明RED的侵略性太强，减小pmax；另一方面，当平均队列保持在thmax附近摆动，说明RED的侵略行太保守，应增加pmax。其算法如下图：7图：Self-ConfiguringRED算法实现图Self-ConfiguringRED算法采用积式增加积式减小(MultiplieativeIncreaseMultiplicativeDecrease,MIMD)的方式调整参数pmax，使得avg尽量保持在thmin和thmax之间，消除了RED算法的队列延时问题和参数敏感性问题，thmax一般初始值设为不宜太大。另一方面,虽然Self-ConfiguringRED解决了RED的参数敏感性问题，但其自身参数的设置也是一个复杂的事情。α和β设置过大，pmax振荡会过于频繁，不利于网络性能的稳定;如果设置太小,就需要多次调整才能将pmax调整到期望值。4、ARED基于Self-ConfiguringRED的思想，S.Floyd等在文献[33]中提出一种新的ARED(AdaptiveRED)算法。ARED算法区别于Self-ConfiguringRED表现在以下四个方面：（1）调节pmax的目标并不是使avg保持在thmin和thmax之间,而是使avg保持在[thmin+0.4(thmax一thmin，thmin+0.6(thmax-thmin)]内；8（2）ARED并不是每一个包到达都会调节pmax，而是以一定的时间间隔，步骤地缓慢调节pmax；（3）pmax限制在范围[0.01,0.5]之内；（4）pmax采用的是和式增加积式减少(AdditiveIncreaseMultiplieativeDecrease，AIMD)的方式调节,而非MIMD。算法如下图：图：ARED算法图ARED算法中pmax的调节不像Self-ConfiguringRED中那么频繁,因此相对于后，ARED有着更好的鲁棒性。但ARED算法需要经过一段时间才能适应网络拥塞的急剧变化。ARED将pmax限制在[0.01，0.5]范围内，这保证了在调节的过程中，即使平均队列长度不在目标队长范围内,其总体性能仍是可以接受的。9