随机早期检测（RED）队列调度机制

更新时间：2026年03月27日作者：spoto 标签(Tag)：

RED属于最早的主动队列管理算法之一。该算法由Sally Floyd在1993年提出。RED有三个不同的名称：随机丢弃、随机丢弃策略以及随机检测。因此，RED实际上可以有三种不同的全名。RED的主要目标是：

避免拥堵：被动队列管理就存在这个问题。AQM能够提前检测到拥塞情况，从而避免其发生。
避免全球同步带来的问题：被动队列管理存在这个问题。而AQM则能够避免这一问题。
避免出现锁定问题：那些持续时间较短的流量在路由器中占据缓冲区时，会面临被阻塞的问题。AQM解决了这个问题，现在，那些持续时间较短的流量也能在缓冲区中获得空间了。
最大化“性能”指标，即吞吐量与延迟的比率。AQM能够正确处理缓冲队列中的数据包，因此不会出现数据包丢失的情况。这样一来，也就不需要对数据包进行重新传输了。数据流将会保持流畅，延迟也会降到最低。

注意：术语“RED”是在1993年提出的，而“Bufferbloat”这一术语则是在2011年才被创造出来的。不过，AQM确实解决了缓冲溢出的问题。不过，RED被认为适合解决Bufferbloat问题，因为它能够控制“队列长度”，使其保持在规定的阈值范围内。它始终不会让缓冲区完全充满。因此，它自然能够解决缓冲溢出的问题。与TCP类似，关于这种算法也已经进行了大量的研究工作。在相关文献中，已经提出了几种不同的 RED 变体：Gentle RED、Nonlinear RED (NLRED)、Adaptive RED (ARED)，以及其他许多变体。

RED算法的运作方式：

RED在“入队”阶段进行操作。它在入站时作用于输出端口。请注意不要将其与路由器架构中的“输入端口”混淆。 RED在“输出端口”上运行，但在“入队”时刻才会开始执行操作。RED会在每个数据包到达时才进行相应的处理。因此，不存在一个固定的时间间隔来调用RED函数。如果数据包的传输速度较慢，那么RED的调用也会以较低的速度进行。如果数据包没有到达，那么就不会触发RED算法。 RED负责决定该到达的数据包是应该被排队等待，还是被丢弃。当新的数据包到达时，RED需要做出决策：该数据包应该被加入队列还是被丢弃？即使队列中有空间，它仍然会做出这个决定。做出这个决定的原因是，如果将该数据包加入队列后，整体的延迟会增加，或者导致队列变得过于拥挤，那么就会引发拥塞现象。如果RED在队列已满之前就丢弃了数据包，那么发送方会间接得知这一情况。这样一来，RED就会降低自己的拥塞窗口大小，从而避免将来再次发生拥塞现象。

RED算法包含以下组成部分：

平均排队长度的计算。
数据包是否会被放入队列或被丢弃，取决于这个概率。
决策逻辑（用于判断是否应该将传入的数据包放入队列中，或者将其丢弃）。

平均队列长度的计算：

每当收到一个数据包时，RED就会使用公式(1)来计算平均排队长度。这个数学模型被称为“指数加权移动平均法”或EWMA。

=> newavg = (1 - wq) × oldavg + wq × current_queue_len 等式(1)

=> 在这里，newavg表示在示例中正在计算的新平均队列长度。

=> oldavg = 之前采样期间所得到的平均排队长度

=> current_queue_len = 路由器当前的队列长度

=> wq = 与‘current_queue_len’相关的权重。默认值：0.002

后来，RED的作者Sally Floyd将wq变量设置为可适应的数值。它不再是一个固定不变的值了。不过，由于我们现在讨论的是原始的RED算法，所以将其值设定为0.002。

滴落概率的计算

在计算出“newavg”之后，RED会采用以下逻辑来计算下降概率（Pd）。其中，minth表示“平均队列长度”的最低阈值，而maxth则代表“平均队列长度”的最高阈值。minth和maxth都是针对平均队列长度的，而不是瞬时队列长度的。这是我们在进一步探讨之前需要记住的重要点。

=> if (newavg ≤ minth) // 论文中，minth的默认值为5个数据包

=> 将传入的数据包放入队列中。这意味着 Pd 的值为 0。

=> else if (newavg > maxth) // 论文中，maxth的默认值应该是15个数据包。

=> 丢弃传入的数据包。// 这意味着Pd=1

=> 否则，按照方程(2)所示的方法计算Pd的值。

=> Pd = maxp × [(newavg – minth) ÷ (maxth – minth)] 方程(2)

=> 线性函数的斜率将取决于这个最大值。

=> 其中，maxp表示最大下降概率。默认值为0.5（之前的值为0.02）。

当队列的新平均长度小于或等于队列大小的最低阈值5时，那么数据包的丢失概率就为0。 0表示该数据包不会被丢弃，而是会被放入队列中。当新的平均排队长度大于队列大小的最大阈值（即15）时，数据包的丢弃概率就为1。 1表示该数据包将被丢弃。现在来看中间情况：当队列的新平均长度处于最小阈值和最大阈值之间时，那么下降概率就会按照上述方程2中的公式来计算。

那么，对于Pd来说，我们接下来要做什么呢？这就是我们在下一步中要执行的步骤。

决策逻辑

一旦“Pd”值被计算出来之后，RED就会根据以下逻辑来决定是否将传入的数据包加入队列或丢弃它：

=> 如果 Pd ≤ R，则将传入的数据包放入队列中。

=> 否则，丢弃传入的数据包。

=> 其中，R表示在[0, 1]区间内均匀分布的随机数。

注意：使用知名的随机数生成器来生成R是非常重要的。如果随机数生成器的实现方式不正确，那么RED的性能可能会受到影响。

左侧的区域被称为“无滴落”区域。如果平均排队长度小于或等于最小阈值，那么该数据包将被加入队列中。右侧的部分就是“取消所有操作”的区域。如果平均排队长度超过最大阈值，那么该数据包将被丢弃。如果平均排队时间介于最小阈值和最大阈值之间，那么该数据包的丢弃概率就会得到计算。根据这一数值，最终会决定是将元素插入队列中还是将其从队列中移除。