CoDel

在网络路由中，CoDel（Controlled Delay，英語發音：/ˈkɒdəl/）是Van Jacobson和Kathleen Nichols开发的网络调度器中使用的调度算法 。 它旨在通过设置缓冲区中网络数据包的延迟限制来克服网络硬件（如路由器）中的缓冲膨胀 ，改善了随机早期检测（RED）算法的整体性能，解决了Jacobson 开发 RED 时抱有的一些误解，设计上 CoDel 比 RED 更容易管理和配置。

2012年，DaveTäht和Eric Dumazet为Linux内核编写了CoDel的实现，并以GNU通用公共许可证和3条款BSD许可证双重许可发布。 Dumazet的CoDel变体称为fq_codel，代表“公平队列控制延迟”。它在OpenWrt版本“ Barrier Breaker”中被用作标准主动队列管理（AQM）和数据包调度解决方案。自这之后，CoDel和fq_codel 迁移到了各种下游项目，例如Tomato ，dd-wrt和OPNsense 。

理论基础

CoDel背后的理论基于对缓冲区影响下分组交换网络中数据包行为的观察。 这些观察中的一些与排队的基本性质和缓冲膨胀的原因有关，另一些与队列管理算法的弱点有关。 CoDel的开发旨在解决缓冲膨胀问题。

缓冲膨胀

数据包在快速网络和慢速网络之间的网络链路传输时速度会变慢，尤其是在TCP会话开始时，突然出现数据包激增并且较慢的网络可能无法快速接受该突发时足够。缓冲区的存在是为了缓解这个问题，它给了快速网络一个存储数据包的地方，让慢速网络以自己的速度读取数据包。 。换句话说，缓冲区的作用就像减震器一样，将突发到达信号转换为平稳平稳的信号。但是，缓冲区的容量有限。理想的缓冲区大小可以处理突发的通信，并使突发的速度与较慢网络的速度相匹配。理想情况下，冲击吸收情况的特征是在传输突发期间缓冲器中的分组的暂时延迟，之后延迟迅速消失，并且网络在提供和处理分组方面达到平衡。

TCP拥塞控制算法依赖于数据包丢弃来确定两个通信设备之间的可用带宽 。 它可以加快数据传输速度，直到数据包开始丢失为止，然后降低传输速率。 理想情况下，当它在链接速度上找到平衡时，它会继续加速和减速。 为此，必须及时发生丢包，以便算法可以响应地选择合适的传输速度。 如果数据包保存在一个过大的缓冲区中，则数据包将到达其目的地，但具有较高的延迟，但不会丢弃任何数据包，因此TCP不会减慢速度。 在这种情况下，TCP甚至可能确定连接的路径已更改，并重复搜索新的平衡点。

拥有一个大而不断的缓冲区，这会导致传输延迟增加和交互性降低，尤其是在查看同一通道上的两个或多个同时传输时，这种情况称为缓冲区膨胀。 可用的通道带宽也可能最终未被使用，因为某些缓冲区可能被缓冲区阻塞，等待数据传送到较慢的目的地，因此可能无法到达某些快速的目的地。

好队列和坏队列

CoDel区分两种队列：

好队列

定义为不显示缓冲膨胀的队列。 通信突发只会导致队列延迟的暂时增加。 网络链接利用率最大化。

坏队列

定义为显示缓冲区膨胀的队列。 通信突发会导致缓冲区填满并保持填满，从而导致利用率低和缓冲区延迟不断增加。

为了有效地防止缓冲区膨胀， 主动队列管理 （AQM）算法形式的解决方案必须能够识别缓冲区膨胀的发生并通过部署有效的对策进行反应。

范雅各布森（Van Jacobson）在2006年断言，现有算法一直在使用错误的方法来识别缓冲区膨胀。 诸如RED之类的算法会测量平均队列长度，如果平均长度过大，则将其视为缓冲膨胀的情况。 雅各布森（Jacobson）在2006年证明，此度量不是一个好的指标，因为在通信突发情况下，平均队列长度会急剧增加。 然后，队列可以快速消散（好队列）或变为站立队列（坏队列）。 网络流量中的其他因素也可能导致误报或误报，从而导致不必要地部署了对策。 Jacobson建议，平均队列长度实际上根本不包含有关数据包需求或网络负载的信息。 他建议，更好的指标可能是滑动时间窗口内的最小队列长度。

算法

根据2006年Jacobson的观点，CoDel旨在将CoDel管理的缓冲区队列中的数据包延迟控制在最小延迟下。目标是将此最小延迟保持在5毫秒以下。 如果最小延迟上升到一个太大的值，则将数据包从队列中丢弃，直到延迟降至最大级别以下。

Nichols和Jacobson引用了仅使用此度量标准的几个优点：

• CoDel是无参数的。 RED算法（根据Jacobson）的弱点之一是，它太难配置，尤其是在具有动态链接速率的环境中。 CoDel根本没有要设置的参数。
• CoDel区分好队列和坏队列。 好的队列本质上具有较低的延迟，因此管理算法可以忽略它，而坏的队列则受到丢包形式的管理干预。
• CoDel的工作原理是完全由本地决定的，因此它与往返延迟，链接速率，流量负载以及其他无法由本地缓冲区控制或预测的因素无关。
• 本地最小延迟只能在数据包离开缓冲区时确定，因此不需要额外的延迟来运行队列以收集统计信息来管理队列。
• CoDel适应动态变化的链路速率，而不会对利用率产生负面影响。
• CoDel可以相对简单地实现，因此可以涵盖从低端家用路由器到高端路由解决方案的整个范围。

如果缓冲区窗口的最小延迟低于最大允许值，则CoDel不执行任何管理缓冲区的操作。 如果缓冲区相对为空（如果缓冲区中的字节数少于一个MTU），则它也不执行任何操作 。如果不满足这些条件，则CoDel可能会丢弃数据包。

算法的描述

该算法是在网络的每一跳上独立计算的。该算法在一个间隔 （最初为100毫秒）内运行。 通过跳监控每个数据包的排队延迟。 每个数据包出队的时候会被转发。先计算每个包的排队延迟（数据包在队列中等待了多少时间）。在这个时间间隔内的最小 排队延迟 要存储下来。当这个时间间隔内的最后一个数据包出队时，如果该间隔的最小 排队延迟 大于5毫秒，则会丢弃此单个数据包，并缩短用于下一组数据包的时间间隔。 如果该时间间隔的最低排队延迟小于5毫秒，则转发数据包并将该时间间隔重置为100毫秒。

当缩短间隔时，将根据由于过多排队延迟而丢包的连续间隔数的倒数平方根来执行此操作。 间隔的顺序是$100$ ， ${100 \over {\sqrt {2}}}$ ， ${100 \over {\sqrt {3}}}$ ， ${100 \over {\sqrt {4}}}$ ， ${100 \over {\sqrt {5}}}$ ……

仿真结果

Nichols和Jacobson已在不同的MTU，链路速率和其他条件变化的模拟测试中对CoDel进行了测试。 通常，结果表明：

• 与RED相比，CoDel在整个带宽范围（从3到100Mbit/s）中使数据包延迟更接近目标值。 测得的链路利用率始终接近链路带宽的100％。
• MTU较低时，数据包延迟比MTU较高时低。 MTU越高，链路利用率就越高，而MTU越低，带宽越低，链路利用率就越好，从而降低了高带宽的公平利用率。

CableLabs的 Greg White和Joey Padden也进行了仿真。

实现

CoDel 2012年5月就出现了完整实现，并已作为开源软件提供 。 它是在Linux内核中实现的（从3.5主线开始）。 DaveTäht将CoDel移植到了CeroWrt项目的Linux内核3.3中，这个项目涉及缓冲膨胀， CoDel 在此进行了详尽的测试。 2013年，CoDel开始在某些专有软件/turnkey带宽管理平台中作为选件出现。 FreeBSD在2016年将CoDel集成到11.x 和10.x 代码分支中。 从6.2版开始，实现随OpenBSD一起分发。