各种红队纪律措施/类型

随机早期检测（Random Early Detection, RED），也被称为随机早期丢弃或随机早期释放，是一种适用于网络调度器的排队策略，旨在避免网络拥塞现象。这种排队策略有多种类型。

• 温和的红色
• 非线性RED
• 自配置型 RED
• 自适应RED队列调度机制

温和的红色：

随机早期检测算法在平均队列长度从最低阈值线性增加到最高阈值时，数据包丢失的概率会从0.05增加到0.50。但当平均队列长度略微超过最高阈值时，数据包丢失的概率则直接从0.50上升到1。这种突然的上升并不平滑。不过，这种突然的上升可以通过“温和的RED算法”来加以调整。

这种行为会导致数据包的丢弃现象。也就是说，当平均队列长度超过最大值时，数据包被丢弃的概率会急剧上升到100%。

温和的RED的工作原理：

Gentle RED试图以一种与原始RED类似的斜率来平缓这条曲线，当平均排队长度介于maxth和maxth的两倍之间时，就可以实现这一点。我们可以轻松计算出RED曲线和Gentle RED曲线的斜率。RED的斜率约为79度，而Gentle RED的斜率则约为73度。Gentle RED的工作原理与RED相同，它只是将下降概率从0.5线性地提高到1。

平均队列长度的计算：

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

=> newavg = (1 - wq) × oldavg + wq × current_queue_len 方程(1)

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

=> oldavg = 之前采样过程中得到的平均排队长度

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

=> wq = 与‘current_queue_len’相关的权重。

=> 默认值：0.002

滴落概率的计算：

一旦“newavg”被计算出来之后，RED就会使用以下逻辑来计算下降概率（Pd）。其中，minth表示“平均队列长度”的最低阈值，而maxth则代表“平均队列长度”的最高阈值。minth和maxth都是针对平均队列长度的，而不是瞬时队列长度的。在进一步深入讨论之前，这一点非常重要。

=> 论文中，minth的默认值为5个数据包。

=> 如果 (newavg ≤ minth)，则将传入的数据包插入到队列中。

=> 论文中，maxth的默认值为15个数据包。

=> 否则，如果 newavg > 2*maxth，那么意味着 Pd=1。

=> 丢弃传入的数据包

=> else if (minth < newavg < maxth)

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

=> else if (maxth < newavg < 2*maxth)

Pd = maxp + (1 – maxp) × [(newavg – maxth) ÷ maxth] 其中，maxp表示最大下降概率。

默认值为 0.5（之前的值为 0.02）。

非线性RED与自配置型RED：

与其线性地增加Pd的含量，不如在接近最小值时逐渐增加Pd的用量，而在接近最大值时则急剧增加Pd的用量。这样可能会更合适。 如果数据包被丢弃的概率在最小阈值和最大阈值之间呈线性增长，那么即使平均队列长度并不大，数据包仍然有很大可能被丢弃。 因此，为了获得在平均队列长度接近最大阈值时数据包丢失的概率较高的结果，研究人员继续进行实验，最终得出了计算数据包丢失概率的二次方程式。该方程式适用于当平均队列长度介于最小值和最大阈值之间的情况。

非线性RED的工作原理：

=> 当 newavg <= minth 时，Pd=0。

=> 当 newavg < maxth 时，Pd = 1

=> Pd = (maxp’)² * [(newavg – minth) / (maxth – minth)]，其中 maxp’ = 1.5 * maxp = 0.75

自配置RED的工作原理：

如下面的伪代码所示，它会对 maxp 进行调整。在每次更新 ‘newavg’ 时，都会执行这样的操作。

=> 如果 (minth < newavg < maxth)

=> 状态 = 介于两者之间；

=> else if (newavg < minth && status!= below)

=> 状态 = 低于

=> maxp = maxp ÷?

=> else if (newavg > maxth && status!= above)

=> 状态 = 以上

=> maxp = maxp ×?

在这个算法中，maxp是否存在上限和下限呢？在原始论文中，所使用的下限是0.02，而上限则是1。

自适应RED队列调度机制：

自适应RED的动机与自配置RED的动机是相同的。 自配置式的RED系统会努力保持队列的平均长度在最小和最大阈值之间。 但是，Sally Floyd认为，为什么不将平均排队长度控制在最小值和最大值之间的一个合理的范围内呢？ 此外，Adaptive RED还能自动移除那些旋钮，并对其进行自动设置。 最大下降概率是根据网络的可用性来调整的。与之前版本的RED相比，它不再是一个固定的数值了。

在自适应RED领域的主要贡献

• 自动设置最小阈值（minth）。该阈值的设定取决于连接容量（C）以及目标队列的延迟时间。
• 自动设置最大阈值（maxth）。该阈值的设定取决于minth的值。
• wq的自动设置功能是根据链接的容量(C)来进行的。
• maxp的设定是自适应式的。它会根据当前的平均排队长度来进行调整。

自适应式 RED 与自配置式 RED

1. maxp的设计目的不仅仅是保持队列的平均长度在minth和maxth之间，而是让队列的平均长度始终处于一个“目标范围内”。由于自我配置机制的存在，队列的平均长度可能会有很大的波动，从而导致数据包丢失的情况频繁发生。而自适应RED则能够确保队列的平均长度保持在一个相对稳定的水平，因为其波动范围非常小，仅为最小和最大阈值的二分之一左右。

示例：

=> 如果 minth = 5个数据包，而 maxth = 15个数据包的话，

那么，目标范围就是：[minth + 0.4 × (maxth – minth)，minth + 0.6 × (maxth – minth)]

因此，目标范围即为：[9, 11]。

=> 平均队列大小始终会保持在9、10和11这三个数值之间。不会出现太大的波动。

2. Maxp的更新是逐步进行的，其更新时间跨度大于一般的往返时间，而且每次更新的幅度很小。Max drop概率的更新频率并不高，通常每500毫秒才进行一次更新，这相当于4到5个RTT的时间间隔。

3. maxp的值被限制在[0.01, 0.5]的范围内，即1%到50%之间。而自配置的RED则能够确保最大丢包概率保持在0.02到1的范围内。

4. 与在Self Configuring RED中使用的MIMD策略不同，AIMD策略用于调整maxp的值。在AIMD策略中，最大丢包概率是以加法方式增加的，而同时以乘法方式减少的。而在Self Configuring中，这两种方式都是以乘法方式进行的。

自动设置最小阈值（minth）

• 如果最小阈值被设定为较低的值，会发生什么情况呢？吞吐量将会下降。RED的主要目标就是最大化吞吐量，同时尽量减少排队时间。如果最小阈值被设定得过低，那么链路就无法得到充分利用，从而导致吞吐量降低，这就违背了RED算法的基本目标。
• 如果最小阈值被设定为较高的数值，那么排队延迟就会增加。如果使用较大的最小值，那么队列通常会一直处于满状态，这又会进一步增加数据包的排队延迟。显然，这种做法违背了RED的目标。因此，Sally Floyd认为，最小阈值必须经过仔细选择，并且应该符合RED的目标要求。
• 那么，估算出合适的“minth”值的最佳方法是什么呢？可以将“minth”设置为与链路容量（C）相关的函数。 为什么？如果我们把最小阈值设定为5，那么如果连接速度较慢的话，那么传输这5个数据包所需的时间就会增加，从而会导致排队延迟的加剧。 如果链接的利用率很高，那么这5个数据包很快就能被处理完毕。这样一来，队列中的等待时间就会减少，或者几乎不需要等待了。 因此，这会导致吞吐量下降。 这个最低阈值应该根据可用的链接情况来设定。 因此，如果连接速度较慢，那么错误的“minth”设置会导致排队时间延长；而如果连接速度较快，那么错误的“minth”设置则可能导致吞吐量下降。

需要确定合适的“目标队列延迟”值，即可以接受的队列延迟时间。网络管理员知道可用的带宽，因此我们可以决定能够容忍多少延迟。假设为5毫秒，这意味着一旦数据包被加入队列后，它必须在5毫秒之内离开队列。因此，可以将最小延迟时间设置为与目标队列延迟相关的函数。

=> 最小值的计算方式如下：

=> minth = (目标队列延迟 × C) ÷ 2

=> 其中，C表示链接在数据包传输时的处理能力（可以通过“带宽”除以“数据包大小”来计算）。而target_queue_delay的值为5毫秒，这是一个用户可以自行配置的参数。

萨莉·弗洛德建议，应该自动设定最小时间。

=> minth = max[5, (目标队列延迟 × C) ÷ 2]

=> 在链路容量较低或中等的情况下，使用至少5个数据包的配置效果较好。因此，为了确保吞吐量不受影响，建议至少使用5个数据包。

自动设置最大阈值（maxth）：

=> maxth的计算方式如下：

=> maxth = 3 × minth

这样就能确保平均队列大小的“目标范围”为 2 × minth。

假设，minth为5包，maxth为15包。

那么，目标范围就是：[minth + 0.4 × (maxth – minth), minth + 0.6 × (maxth – minth)]

因此，目标范围即为：[5 + 0.4×(15 – 5)，5 + 0.6×(15 – 5)]，即[9, 11]。

自动设置wq：

• wq可以被定义为链接容量(C)的一个函数。

wq= 1 - e(-1/C)

其中，C表示每秒内的连接容量，即带宽除以数据包的大小。如果C的值很大，那么Wq的值就会偏小。相反，如果C的值较小，那么Wq的值就会较大。

Wq的重要性在于：

=> 如果队列的大小从一个数值变为另一个数值，比如从旧的数值变为新的数值，那么……

如果数值在60到61之间，或者0到1之间，又或者50到55之间，那么，需要“-1 / ln(1 - wq)”个数据包的传输，才能使“平均队列大小”达到“新队列大小的63%”。

=> 如果当前队列的大小从60变为61，而Wq的值为0.002，那么……

即，当有500个数据包被接收时，当前队列的大小保持不变。此时，平均队列大小将会是当前队列大小的63%，也就是38个数据包。

• 因此，“-1 / ln(1 - wq)”被视作估计平均队列大小的“时间常数”。不过，这个参数实际上是以数据包的到达时间来衡量的，而不是以时间本身来衡量的。
• 例如，如果 wq 的值为 0.002，那么相当于有 500 个数据包到达。但假设可用的带宽为 1Gbps，那么 500 个数据包的到达其实只发生在很短的时间内。因此，wq 的值越小越好。

调整 maxp：

=> 它每500毫秒就会进行一次调整/更新。

=> 每间隔几秒钟：如果平均队列大小大于目标范围，且maxp小于0.5。

=> 增加最大数值。

=> maxp <- maxp + α

=> else if (平均队列大小小于目标范围，且maxp大于0.01)

=> 减少最大值。

=> maxp <- maxp * β

=> 时间间隔：0.5秒

=> 目标范围：[最小时间 + 0.4, 最大时间 - 最小时间]

=> minth + 0.6 × (maxth – minth)

=> α：增量因子，α = min(0.01, maxp/4)

=>β：减少因子，β = 0.9