主动队列管理机制-RED

主动队列管理机制-RED

        主动队列管理机制-RED
       为了解决全局同步等问题，RED (Random Early Detection，随机早期检测)应运而生}3u}与DropTail策略相比，RED为队列管理添加了两种新机制，其一，不是等队列全满后再丢弃到来 的分组，而是利用概率判定机制事先去弃部分分组来预防可能发生的拥塞;其二，通过平均队列而非瞬时队列调整分组丢弃概率，以此来尽可能地吸收部分短暂的突 发流量。RED的基本思想就是对拥塞进行提前预测，在拥塞真正发生之前，就按照一定的概率丢弃分组，通过包的丢弃来通知发送端减少进入网络链路的数据量。
    这意味着路由器以后不必丢弃更多的分组，对面向连接的TCP数据流来说，RED有可能避免丢弃属于同一连接的连续分组，从而提高链路的吞吐量。RED不像 DropTail那样必须等到队列完全占满，才被迫丢弃所有新到达的分组，而是当网关察觉到队列长度超过了某个门限值(threshold)之后，就开始 决定丢弃分组的概率，然后按这个概率丢弃到达的分组。这也正是随机早期检测的含义。
      (1) RED的重要配置参数
    在详细讨论RED之前，我们介绍一下该算法涉及到的几个重要参数，这些参数
的名称及意义见表2.10
 

 2) RED算法
    对新到达的分组，RED路由器首先计算平均队列长度，将它与最大门限值和最小门限值作比较。如果平均队列长度小于最小门限值，则没有分组被丢弃;如果该值 大于最大门限值，则丢弃所有新到达的分组;而当该值介于两个门限值之间时，每个新到达的分组都按照概率P。被丢弃。其中，P。是平均队列长度的函数。事实 上，连接中分组丢弃的概率大致和该连接占用的带宽成正比。这是因为对一个发送量较大的数据流来说，可供随机丢弃的分组的数量也相对较多。

 

    图2.1给出了RED的粗略算法。
    由上可见，RED路由器有2个独立的算法组成。其中，计算平均队列长度的算
法决定了路由器队列容纳突发性数据流的程度;计算丢弃概率的算法决定了在当前拥
塞程度下，路由器丢弃分组的频率。
    这里算法考虑了队列为空的情况。它通过时间函数f (t)，估算路由器在空闲阶
段可以有m个小分组被传输。空闲过程结束以后，路由器假定在这段过程中有m个
分组到达，然后计算平均队列长度。图2.2给出了RED丢弃概率与平均队列长度的
关系。

    而一旦avg的值超过max }h，则所有到达路由器的分组都将被丢弃。
此外，在RED中，使用的是平均队列长度。这比使用瞬时值更能精确“捕捉”拥塞情况。由于Internet上数据的突发本质，队列往往很快被充满，然后又很快被取空。
用权值w。计算平均队列长度，可以过滤短期的队列长度变化而尽量检测长期的拥塞。权值则决定算法抗突发流的能力。
    正因为RED是基于时间平均队列长度的，所以有瞬时值大于平均值的情况发生，到达的分组找不到地方缓存而不得不丢弃，这时RED就工作在Drop Tail方式。因此，RED设计的目标之一就是要尽量避免“Drop Tail"的发生。
    RED有助于减少链路中的不公平现象，避免全局同步，并且可以通过控制丢弃分组多少来控制平均队列长度。1998年，RED被推荐为路由器端拥塞避免机制 的首要方案。但是这个方法也存在一定的问题。RED算法的主要弱点是平均队列长度随着拥塞的程度与参数的设置而改变，RED算法的另一个弱点是输出量同样 受流量负载和参数设置的影响。而在实际应用中，RED参数都是根据经验进行配置。这些控制参数对网络行为的影响并不是显而易见的。现在，关于如何配置这些 参数，还没有一个统一意见。
    上面的两种拥塞控制算法都是用包丢失作为告诉端系统网络发生拥塞的指示。这种方式对一次性大批量数据传输的效果比较理想。但对时延有一定要求的应用，例如 音频(Audio ), Web服务、远程登陆telnet等效果并不是很理想，会导致大量的包丢失。为此，推出了显式拥塞指示(Explicit Congestion Notification,  ECN)，用在包头标记来指示拥塞取代以丢包指示拥塞的方法[2"] o ECN从以前DECbit算法得到启发，在源端数据包中嵌入ECN使能发送比特位，由路由器根据网络情况设置CE  ( Congetion Experienced)比特位。源端接收从网络中反馈回的这种CE置位的数据包，然后将随后发出的数据包标记为可丢弃的数据包。ECN的优势在于不需要 重传超时，也不依赖于粗粒度的TCP定时，所以对时延有一定要求的应用效果较好。文献又给出了一种改进算法(New-ECN )，它通过调整拥塞窗口cwnd大小，纠正了有长时间RTT的TCP连接的偏差，改进了共享瓶颈处带宽的公平性。