6.2 Random Early Detection
Last updated
Last updated
第二种机制称为 random early detection（RED）。与DECbit方案类似，即每个路由器都被编程来监控自己的队列长度，并且当检测到拥塞即将发生时，通知源主机调整其拥塞窗口。RED由Sally Floyd和Van Jacobson在1990年代初发明，与DECbit方案有两个主要的不同。
更多阅读：S. Floyd and V. Jacobson Random Early Detection (RED) Gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking. August 1993.
首先，RED不会通过明确发送拥塞通知消息给源端，而是通过隐式地 通知源端拥塞，即通过丢弃其数据包。因此，源端通过随后的超时或重复ACK来实际得知拥塞发生。你可能已经猜到了，RED被设计成必须与TCP一起使用，TCP目前通过超时（或通过重复 ACK 等其他方式）来检测拥塞。正如 RED 缩写中的“early”所暗示的，路由器会比必要时更早地丢弃数据包，以此通知源端应该比平常更早地减少其拥塞窗口大小。换句话说，路由器在其缓冲区空间完全耗尽之前就会丢弃少数几个数据包，以此使源端减速，并希望这样做将避免稍后需要丢弃大量数据包的情况。
其次是RED决定何时丢弃数据包以及选择丢弃哪个数据包。为了理解基本思想，假设现在是一个简单的FIFO队列，与其等到队列完全满了然后被迫丢弃每个到达的数据包（第2.1.3节描述的tail drop策略），我们可以决定一旦队列长度超过某个深度（drop level）时，以一定的概率（drop probability）来丢包。这就是 early random drop。RED 算法定义了如何监控队列长度以及何时丢弃一个数据包。
在以下内容中，我们将描述Floyd和Jacobson最初提出的RED算法。我们注意到，RED 算法之后有几个修改，但是所有修改的关键思想与下面介绍的内容相同，且大多数实现都接近于下面的算法。
首先，RED 使用与最早 TCP 中计算超时时间所使用的加权运行平均类似的方法来计算平均队列长度。即，AvgLen 是这样计算的：
其中 0 < Weight < 1，SampleLen 是测量到的队列长度。在大多数软件实现中，每当新的数据包到达路由器时，都会测量队列长度。在硬件中，可能会在某个固定的采样间隔计算它。
使用平均队列长度而不是瞬时队列长度的原因是因为它能更准确地捕捉到拥塞。由于互联网流量的突发性质，队列可能非常快速地填满然后再次变为空。如果一个队列大部分时间都是空的，只是偶然队列被填满，那认为路由器正在拥塞并通知主机减速就不太合适了。因此，加权运行平均计算试图通过过滤掉队列长度的短期变化来检测长期的拥塞，正如图35右侧部分所示。你可以把运行平均看作是一个低通滤波器。现在的问题是我们如何确定低通滤波器的参数 Weight。
其次，RED 有两个阈值：MinThreshold 和 MaxThreshold。 当数据包到达路由器时，RED（Random Early Detection）根据以下规则将当前的AvgLen与这两个阈值进行比较：
如果平均队列长度小于MinThreshold ，则不采取任何行动；如果平均队列长度大于MaxThreshold，则始终丢弃数据包。如果平均队列长度位于两个阈值之间，则新到的数据包会以一定概率 P 丢包。这个过程如图 36 所示。P 和 Avglen 的关系大致如图 37 所示。值得注意的是，当AvgLen处于两个阈值之间时，丢包概率会缓慢增加，到达MaxThreshold时达到MaxP，此时会突然跳转到全丢包。这样做的理由是，如果AvgLen达到MaxThreshold，则温和的方法（丢弃一些数据包）已不起作用，需要采取激烈措施：丢弃所有到达的数据包。但是仍然有一些研究建议，从随机丢包到完全丢包，过渡应更平滑，而不是如此处所示的不连续方式。
虽然图 37 只是将丢包概率 P 描述成 Avglen 的函数，实际情况要更加复杂。事实上，P 是 AvgLen 和自上次丢包以来经过的时间的函数。具体而言，它的计算方式如下：
TempP 是在图 37 中， y 轴上对应的值，count 表示（注，应该是自上次丢包之后）新加入队列（未丢弃）的数据包的数量，AvgLen 一直在两个阈值之间。随着 count 的增加，P 缓慢增加（分母变小），从而使得自上次丢包以来的时间增长时，丢包的可能性逐渐增大。这样的算法，使得间隔很近的包，相比间隔较远的包更不容易被丢弃。RED 的发明者发现，如果不这样计算 P，数据包的丢弃在时间上不会平均的分布，而是会更容易成批的丢包。而来自特定 TCP 连接的包更容易成批的来到路由器，进而导致成批的丢弃单个 TCP 连接的包。这是不可取的，因为每个RTT只要有一个丢包就会导致 TCP 的拥塞窗口减小，而多个丢包甚至可能导致 TCP 重新回到慢启动状态。
举个例子，假设我们将MaxP设置为0.02，并且count初始为 0。如果平均队列长度位于两个阈值之间的中点，那么TempP和P的初始值将是MaxP的一半，即0.01。此时，到来的数据包有99%的概率进入队列。随着每个未被丢弃的数据包的到达，P会慢慢增加，在连续50个数据包到达且未被丢弃后，P会增加到0.02。如果有99个数据包连续到达且未丢失，P会达到1，保证下一个数据包一定被丢弃。这部分算法的重要之处在于，它确保了随时间分布大致均匀的丢包率。
RED 期望的是，当AvgLen超过MinThreshold时，仅丢弃少量数据包，这将导致部分TCP连接减小其窗口大小，进而降低数据包到达路由器的速率。如果一切顺利，AvgLen随后会下降，从而避免了拥塞。队列长度可以保持较短，同时由于丢弃的数据包很少，吞吐量仍然很高。
请注意，由于RED是基于队列长度的时间加权平均进行操作的，因此瞬时队列长度可能远长于AvgLen。在这种情况下，如果数据包到达但没有地方存放，那么就必须丢弃它。当这种情况发生时，RED处于tail-drop模式。RED的一个目标是尽可能防止尾部丢包行为。
RED算法的随机性质赋予了它一个有趣的特性。因为RED随机丢弃数据包，因此RED决定丢弃某个特定数据流的数据包的概率大致与该流在路由器上当前获得的带宽份额成正比。这是因为发送相对较多数据包的数据流提供了更多的随机丢弃的分母。因此，RED包含了一定程度的资源公平分配，尽管这种分配方式毫不精确。虽然可以说是公平的，但因为RED对高带宽数据流的惩罚超过了低带宽数据流，它增加了高带宽TCP流重新进入慢启动的可能性，这对于这些高带宽流来说是双重的打击。
有相当多的分析是关于如何设置各种RED参数（例如MaxThreshold、MinThreshold、MaxP和Weight），旨在优化功率函数（即吞吐量除以延迟）。这些参数的性能也通过模拟得到了确认，而且算法对它们并不过分敏感。然而，需要记住的是，所有这些分析和模拟都基于对网络工作负载的特定描述（并不具备普适性）。RED的真正贡献是一种使得路由器可以更准确地管理其队列长度的机制。准确定义什么构成最优队列长度取决于流量的构成，这是一个正在进行的研究课题。
在设置两个阈值 MinThreshold 和 MaxThreshold 时，如果网络流量非常突发性，则 MinThreshold 应足够大，以保持链路利用率在足够高的水平。同时，两个阈值之间的差距应大于一个 RTT 中AvgLen的通常会增加的量（注，但是 RTT 对于不通的数据流来说不一样啊）。考虑到今天互联网上混合的流量，将 MaxThreshold 设置为 MinThreshold 的两倍似乎是一个合理的经验法则。另外，由于我们期望在高负载期间平均队列长度在两个阈值之间变动，因此在 MaxThreshold 以上 应有足够的空闲缓冲区，以吸收互联网流量中出现的自然突发流量，从而无需使得路由器进入tail drop模式。
之前提到，Weight是计算 AvgLen的低通滤波器的时间常量，我们需要为其选择一个合适的值。回想一下，RED 通过在拥塞时期丢包来向 TCP 流发送信号。假设路由器丢弃了属于某个 TCP 连接的一个数据包，然后立即转发该连接的更多数据包。当这些数据包到达接收端时，它开始向发送端发送重复ACK。当发送端看到足够多的重复ACK时，它将减小其窗口大小。因此，从路由器丢弃数据包到同一路由器开始看到受影响 TCP 连接的窗口大小有所减少至少需要一个RTT 时间。所以看起来没有必要以远小于 RTT 的时间来响应拥塞。如前所述，100ms 是互联网平均RTT的一个还不错的估计。因此，应该按照过滤掉远小于 100ms 时间范围内队列长度的变化，来选取 Weight。
由于RED通过向TCP流发送信号来告诉它们减速，你可能会想，如果这些信号被忽略会发生什么。这类问题通常被称为unresponsive flow。unresponsive flow使用的网络资源超过了它们应有的份额，如果它们数量足够多，就像在TCP拥塞控制出现之前的日子里那样，可能会导致拥塞崩溃。一些队列技术，如WFQ，可以通过将某些类型的流量与其他流量隔离开来来帮助解决这个问题。还有讨论创建一个修改版本的RED，更狠的丢弃那些对于初步提示不响应的数据流中的包。然而，这个方法被证明是具有挑战性的，因为区分unresponsive行为和“正确”的行为可能很难，特别是当数据流具有各种不同的RTT和瓶颈带宽时。
在1998年，15位著名网络研究人员敦促广泛采用基于RED的AQM技术。但是这些建议大部分被忽视了，我们在下文将会介绍原因。然而，在数据中心，基于RED的AQM方法已经取得了一定的成功。
更多阅读：R. Braden, et al. Recommendations on Queue Management and Congestion Avoidance in the Internet. RFC 2309, April 1998.
