受控延迟队列调度机制

AQM指的是主动队列管理算法。这些算法负责处理路由器中的队列问题。RED及其各种变体就是这类主动队列管理算法。此外，还有其他一些用于有效处理路由器中队列的算法。其中，Controlled Delay就是一种这样的算法。CoDel是由Van Jacobson和谷歌团队在RFC 8289中提出的。这是目前最新的主动队列管理算法。

CoDel是一种首款将“队列延迟”作为拥塞度量指标的AQM算法。 之前的算法（如 RED 及其变体）并没有将“队列延迟”作为衡量拥塞情况的指标。 CoDel的主要目标是尽量减少“缓冲溢出”所带来的影响。 缓冲溢出现象指的是，当大量数据包同时到达时，路由器的队列变得过于拥挤，从而导致数据包无法被正确处理，最终丢失。 与其他AQM算法相比，它的节点数量较少。 RED有4个旋钮，而CoDel只有2个旋钮。 所谓“旋钮”，其实就是用户需要自行配置的参数。 CoDel算法在RFC 8289中有详细描述。 CoDel被实现在Linux内核中。

此外，还有几种不同的CoDel实现方式。其中，Flow Queue CoDel（FQ-CoDel）是一种在Linux内核中实现的常见CoDel实现方式。在许多操作系统中，FQ-CoDel被用作默认的队列调度方式。

CoDel-BLUE Alternate (COBALT)是一种队列调度机制。它实际上是原始CoDel的改进版本。作为Linux系统中CAKE队列调度的一部分而实现。

CoDel的工作原理：

CoDel在“出列”时刻进行操作。 注意：CoDel在“出列”时刻时运行于“输出端口”上；而RED则在“入列”时刻时运行于输出端口上。 CoDel在从输出端口队列中移除每个数据包之后才开始执行操作。 因此，不存在一个固定的时间间隔来调用CoDel。 并不是说 CoDel 会每隔 100 毫秒或者某个固定的时间间隔就执行一次操作。 它仅在数据包从输出端口发送出去时才会被触发。 如果数据包未能送达（即没有发送出去），那么CoDel算法就不会被调用。

CoDel算法分为两个阶段来执行。 这两个阶段分别被称为“投放阶段”和“非投放阶段”。 CoDel负责决定，该数据包应该被从队列中移除，还是直接丢弃。 “Dequeue”意味着CoDel成功地将数据包传输到了下一个设备。 这种丢失意味着，该数据包不会被转发，而是会被丢弃。此时，发送方必须重新发送该数据包。 那么，CoDel究竟是如何以及为何会释放那个数据包的呢？ 基本上，当CoDel检测到网络中的拥塞现象时，由于数据包的排队问题，该数据包就会被丢弃。

=> CoDel的两个主要组成部分：

=> “瞬时排队延迟”的计算。

=> 决策逻辑（即是否要从队列中移除该数据包）

CoDel算法中的两个可配置参数：

RED拥有4个可配置的参数，而CoDel则只有2个这样的参数。其中一个参数是目标队列延迟，另一个参数是“时间间隔”。

• 目标时间（默认：5毫秒）【注意：这与Adaptive RED中的“目标队列延迟”相同。所谓“目标队列延迟”，指的是允许的最大队列延迟时间。该目标值为5毫秒，这意味着被放入队列中的数据包在队列中停留的时间不得超过5毫秒，否则必须在该时间内被从队列中移除。】
• 间隔（默认值为100毫秒）【注意：假设互联网中的平均RTT为100毫秒。】该间隔表示CoDel控制器需要等待的时间，以便网络拥塞能够自行缓解。如果这种情况没有发生，那么控制器将自行处理网络拥塞问题。

算法：

步骤1：在数据包被加入队列时，需要附上“时间戳”（以表示该数据包的加入时间）。这就像任何正式建筑中的入口登记处一样。

步骤2：计算每个即将被发送的数据包当前的排队延迟：cur_qdelay = dequeue_time - enqueue_time。公式（1）

步骤3：当 cur_qdelay 首次大于目标值时，就会启动“间隔”计时器。如果当前队列的延迟超过了目标队列延迟值，那就意味着路由器上的队列已经变得过于拥挤，导致队列延迟超过目标值。

步骤4：如果后续数据包的排队延迟始终大于目标值（5毫秒），那么进入丢弃阶段。不过，只有当整个“间隔时间”内cur_qdelay大于目标值时，才会进入丢弃阶段。

• 步骤 4A：如果 cur_qdelay 小于 100 毫秒，那么仍然处于非降级阶段，因为这种情况只是短暂出现的。如果当前队列的延迟在较短的时间内超过了某个阈值（例如 20 毫秒、40 毫秒或 99 毫秒），那么就不必担心拥塞问题了。
• 步骤 4B：如果 cur_qdelay 大于目标值超过 100 毫秒，那么就会进入丢弃阶段。此时会丢弃所有数据包，直到 cur_qdelay 再次大于目标值为止。不过，数据包被丢弃的时间是由控制器来控制的。计算公式如下：next_drop_time = current_time + interval/sqrt(count)。其中，count 表示在丢弃阶段中被丢弃的数据包数量。

步骤5：当当前队列的延迟再次低于目标值时，那么就会离开掉队阶段。此时，“interval”计时器会被重置，只有当cur_qdelay大于目标值时，计时器才会重新开始计时。

在下降阶段会发生什么：

在进入丢弃阶段时，算法将会丢弃那些正在发送中的数据包。 一旦算法进入丢弃阶段，该数据包就会立即被丢弃，而不是被从队列中移除。 那么，下一个要被丢弃的数据包是什么时候呢？与DropHead或DropTail这样的被动队列管理算法不同，CODEL在处于丢弃阶段时，不会继续丢弃后续的数据包。 相反，它计算出下一个数据包被发送的确切时间。 为了计算下一个数据包被丢弃的确切时间，CoDel使用了一个名为“count”的局部变量。这个变量表示在丢弃阶段中已经被丢弃的数据包数量。 因此，当第一个数据包被丢弃时，变量“count”的值就会增加1（表示在“当前”丢弃阶段中丢失的数据包数量）。

使用控制律来计算下一个数据包传输所需的时间。

next_drop_time = current_time + interval/sqrt(count)

在传输阶段，CoDel继续通过方程式来发送数据包。 (2) 直到 cur_qdelay > target。 所以，我们想知道“丢包阶段”何时会结束？数据包什么时候会停止被丢弃呢？CoDel会继续继续丢弃数据包，直到当前队列的延迟大于目标延迟值为止。 当当前排队时间超过目标值时，CoDel就会判断出拥塞现象已经结束。 因此，当 cur_qdelay < target 时，就结束下降阶段。 当下降落阶段结束后，局部变量会被重置为它们的默认值。 将计数的值重置为0。 该计数仅在特定的卸载阶段时才会增加，当卸载阶段结束后，该计数会重新重置。 进入非掉落阶段。

例如：假设数据包始终以固定的频率被放入队列中，同时也会以相同的频率从队列中移除。

目标时间：5毫秒，间隔：100毫秒。队列状态：从入队操作开始，队列中的元素为：[11,10,9,8,7,6,5,4,3,2,1]——之后进行出队操作。

=> 第一个数据包的当前排队延迟为4毫秒，请删除该数据包。

=> 第二个数据包的当前排队延迟为6毫秒。此时，启动一个100毫秒的计时器，并等待100毫秒。当计时器归零后，该数据包不会被丢弃，而是会被转发到下一个设备。

在定时器为8时，第三个数据包的当前排队延迟为10毫秒。不过，100毫秒的定时器仍然在运行。因此，这个数据包不会被丢弃，而是会被转发到下一个设备上。

在定时器为42时，第4个数据包的当前排队延迟为44毫秒。不过，100毫秒的定时器仍然在运行。因此，这个数据包不会被丢弃，而是会被转发到下一个设备。

在计时器为82时，第5个数据包的当前排队延迟为41毫秒。不过，100毫秒的计时器仍然在运行。因此，这个数据包不会被丢弃，而是会被转发到下一个设备。

当计时器的值为100时，第6个数据包的当前排队延迟为25毫秒。不过，由于计时器已经到期，该数据包将被丢弃。该数据包将会立即被丢弃。

CoDel正在执行投放阶段的工作。

假设：current_time = 1000毫秒，count = 1。那么，nextDropTime = currentTime + interval / sqrt(count)。公式(2)

• next_drop_time = 1000毫秒 + 100毫秒/根号下1
• 下一个下降时间 = 1100毫秒

在时间1100毫秒时，丢弃下一个数据包，同时将计数加1，此时计数为2。直到时间1100毫秒为止，不再丢弃任何数据包，只是将其从队列中移除而已。

在时间1050时，第7个数据包已经准备好被取出。此时，当前队列的延迟为60毫秒（60毫秒大于5毫秒），因此该数据包仍然处于被丢弃的阶段。不过，该数据包不会被丢弃，而是会被成功转发。

在时间1090时，第8个数据包已经准备好可以被取出。此时，当前队列的延迟为52毫秒。（因为52毫秒大于5毫秒，所以数据包仍然处于被丢弃的阶段。）不过，该数据包不会被丢弃，而是会被成功转发。

假设第9个数据包在1100毫秒时仍然无法被取出，那么在时间等于1100毫秒的时候，第9个数据包就会被丢弃。此时，current_time为1100毫秒，count为2。

• next_drop_time = 1100毫秒 + 100毫秒 / √2
• 下一个下降时间 = 1100毫秒 + 71毫秒 = 1171毫秒

在时间1171毫秒时，丢弃下一个数据包，同时将计数加1，此时计数为3。

在时间1160时，第10个数据包已经准备好可以被取出。此时，该数据包的当前排队延迟为70毫秒。（因为70毫秒大于5毫秒，所以该数据包仍然处于被丢弃的阶段。）不过，该数据包不会被丢弃，而是会被成功转发。

假设第11个数据包在1171毫秒时仍未准备好被取出，那么在时间点为1171毫秒时，第11个数据包将被丢弃。

• 当前时间：1171毫秒，计数：3次。
• 下一个下降时间 = 1100毫秒 + 100毫秒 / 根号3
• 下一个触发时间 = 1100毫秒 + 58毫秒 = 1229毫秒

在时间1229毫秒时，丢弃下一个数据包，同时增加计数，此时计数为4。

CoDel存在的一些已知问题：

当某些数据流无法响应时，队列控制功能就会失效。 响应式流属于UDP流。 为了管理这类流量的排队问题，人们正在提出另一种算法。 它被称为FQ-CoDel。 它代表的是Flow Queue CoDel。 FQ-CoDel系统通过为每个流提供独立的队列来处理这些流。 我们知道，这些AQM算法是在路由器上运行的。 路由器为每个数据流都维护一个独立的队列。 这个路由器非常智能，它能够轻松地将每个数据流进行唯一标识。 流量的识别依据包括：源IP地址、源端口、目标IP地址、目标端口以及协议号。