red （随机早期检测(Random Early Detection )）

基本思想

Random Early Detection，为避免发生网络中的全局同步现象，在路由器采用的一种措施。

基本思想上：通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。由于RED是基于FIFO队列调度策略的，并且只是丢弃正进入路由器的数据包，因此其实施起来也较为简单。

随机早期检测的设计目标

1）最小化数据包丢失率和排队延迟；

2）避免全局同步现象；

3）避免对突发业务的偏见：网络中含有大量的突发数据，而传统的“去尾”算法对突发业务有很大的偏见。偏见就是在采用“去尾”算法的路由器中，如果某个流的突发性越高，则当该流的数据包进入队列时越容易造成队列溢出，从而导致连续地丢弃大量的该流的包；

4）即使在缺乏传输层协议有效配合的情况下，算法也能控制平均队列长度，从而避免拥塞。为了达成以上目标，RED采用了基于时间的平均队列长度，并且随机地选择正进入路由器地分组进行丢弃。这种方法能被有效地实施而无需在路由器中维持每个流（per-flow）的状态信息。

RED算法

首先是计算平均队列长度，以此作为对拥塞程度的估计。另一个就是计算丢弃分组的概率。

计算平均队列长度

由于Internet数据的突发性，如果一个队列很多时候是空的，然后迅速被充满，又很快被取空，这时就不能说路由器发生拥塞而需要向源端发送拥塞指示。因此，RED在计算平均队长avgQ时，采用了类似低通滤波器（Low—pass filter）带权值的方法：

avgQ=(1-Wq)*avgQ+ Wq* q。

其中，Wq为权值，q为采样测量时实际队列长度。这样由于Internet数据的突发本质或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队长有明显的变化，从而“过虑"掉短期的队长变化，尽量反映长期的拥塞变化。

在计算平均队长的公式中，权值Wq相当于低通滤波器的时间常数，它决定了路由器对输入流量变化的反应程度。因此对Wq的选择非常重要，如果Wq过大，那么RED就不能有效地过虑短暂的拥塞；如果Wq太小，那么avgQ就会对实际队列长度的变化反应过慢，

不能合理地反映拥塞状况，在这种情况下，路由器就不能有效检测到早期的拥塞。Wq的值应根据不同情况预先设置，一般来说，它是由路由器允许发生的突发业务的大小和持续的时间所决定的。

计算丢弃分组的概率

计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃分组的概率，从而有效地控制平均队列长度。

RED有两个和队列长度相关的阈值：MINth。和MAXth。当有分组达到路由器时，RED计算出平均队长avgQ。若avgQ< MINth，则没有分组需要丢弃；当MINth≤avgQ≤MAXth时，计算出概率P，并以此概率丢弃分组；当avgQ>MAXth时，所有的分组都被丢弃。由于RED使用的是基于时间的平均队长度，就有可能会发生实际队长大于平均队长的情况，如果队列已满，则到达的分组只能被丢弃。

实例

下图是一个RED丢弃概率函数的例子

当队列长度小于低的门限值Tmin时，不丢弃新到达的分组；当队列长度介于Tmin和Tmax之间时，以一定的概率丢弃分组，且分组概率随着队列长度的增长线性增加，队列长度达到Tmax时，到达的分组全部被丢弃。这3个阶段分别被称作正常、拥塞避免和拥塞控制三个阶段。最坏情况的最大队列大小被限制为Tmax。RED在队列满之前提前开始触发拥塞标识。路由器可对不同的队列支持不同的Tmin、Tmax和Pmax值以平衡队列可用空间、要求的队列数和使用每一个队列的业务类的延迟/抖动范围。

RED最初是作为IntServ中的一种拥塞避免机制提出来的，当用在DiffServ中时，为了获得更好的性能，为一致的分组和不一致的分组提供不同的待遇，产生了一些改进的算法，如WEED、RIO等。

算法优缺点

1993年，Floyd 和Jacobson就提出了RED，当时的主要目的是克服“早期随机丢弃”（Early Random Drop,ERD）网关偏袒突发业务而造成的不公平问题. RED为队列管理增添了两种新机制，其一，不是等队列全满后再丢弃到来的分组，而是利用概率判定机制事先丢掉部分分组来预防可能发生的拥塞；其二，通过平均队列而非即时队列调整分组丢弃概率，由此来尽可能地吸收部分短暂的突发流量。RED算法的性能敏感于设计参数和网络状况，在特定的网络负载状况下依然会导致多个TCP的同步，造成队列震荡，吞吐量降低和时延抖动加剧。RED算法的公平性和稳定性也存在问题。自RED被首次提出来之后，它的参数配置就是一个没有彻底解决的问题。

虽然RED能够有效避免拥塞，但是该算法仍然存在以下主要缺陷：

（1）公平性问题

对于不响应拥塞通知的连接，RED算法无法有效处理，因此这样的连接经常会挤占大量的网络带宽，导致了各种连接不公平地共享带宽。

（2）参数设置问题

RED算法对参数设置很敏感，两个门限值和最大丢包概率的细微变化经常是对网络性能造成很大影响，如果根据具体业务环境选择最合适的参数是RED存在的一个重要问题。另外，一组参数可能会获得较高的吞吐量，但是可能也会造成较高的丢包率和较长的时间延迟。如何配置参数，使得算法在吞吐量、时间延迟和丢包率等各方面均获得较好的性能也有待解决。

（3）网路性能问题

RED算法控制的平均队列长度经常会随着连接数目的增加而不断增大，造成传输时延抖动，引起网络性能不稳定。