查看“︁CoDel”︁的源代码

在[[路由|网络路由中]]，'''CoDel'''（Controlled Delay，{{IPA-en|ˈkɒdəl}}）是[[范·雅各布森|Van Jacobson]]和{{Translink|en|Kathleen Nichols|4=Kathleen Nichols}}开发的{{Translink|en|Network scheduler|4=网络调度器}}中使用的[[调度 (计算机)|调度算法]] 。 它旨在通过设置[[緩衝器|缓冲区]]中网络数据包的延迟限制来克服[[網絡設備|网络硬件]]（如[[路由器]]）中的[[缓冲膨胀]] ，改善了{{Translink|en|random early detection|4=随机早期检测}}（RED）算法的整体性能，解决了Jacobson 开发 RED 时抱有的一些误解，设计上 CoDel 比 RED 更容易管理和配置。

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

== 理论基础 ==

CoDel背后的理论基于对[[緩衝器|缓冲区]]影响下[[分组交换|分组交换网络]]中[[分组交换|数据]]包行为的观察。 这些观察中的一些与排队的基本性质和[[缓冲膨胀]]的原因有关，另一些与队列管理算法的弱点有关。 CoDel的开发旨在解决[[缓冲膨胀]]问题。 <ref>{{Cite web|title=Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution|url=http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php|accessdate=2012-08-16|author=Joe Brockmeier|date=2012-05-08|publisher=[[ReadWriteWeb]]|archiveurl=https://web.archive.org/web/20120712012901/http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php|archivedate=2012-07-12|dead-url=no}}</ref>

=== 缓冲膨胀 ===

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

[[TCP拥塞控制]]算法依赖于数据包丢弃来确定两个通信设备之间的可用[[带宽 (计算机)|带宽]] 。 它可以加快数据传输速度，直到数据包开始丢失为止，然后降低传输速率。 理想情况下，当它在链接速度上找到平衡时，它会继续加速和减速。 为此，必须及时发生丢包，以便算法可以响应地选择合适的传输速度。 如果数据包保存在一个过大的缓冲区中，则数据包将到达其目的地，但具有较高的[[延迟 (工程学)|延迟，]]但不会丢弃任何数据包，因此TCP不会减慢速度。 在这种情况下，TCP甚至可能确定连接的路径已更改，并重复搜索新的平衡点。 <ref>{{Cite journal|title=Congestion avoidance and control|url=http://www.cord.edu/faculty/zhang/cs345/assignments/researchPapers/congavoid.pdf|last=Jacobson|first=Van|last2=Karels, MJ|journal=ACM SIGCOMM Computer Communication Review|issue=4|year=1988|volume=18|archiveurl=https://web.archive.org/web/20040622215331/http://www.cord.edu/faculty/zhang/cs345/assignments/researchPapers/congavoid.pdf|archivedate=2004-06-22|access-date=2020-02-26|dead-url=yes}}</ref> <ref name="Rant_Jacobson">{{Cite web|title=A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA|url=http://www.pollere.net/Pdfdocs/QrantJul06.pdf|accessdate=12 August 2012|author=Jacobson|first=Van|authorlink=Van Jacobson|year=2006|archive-date=2020-02-27|archive-url=https://web.archive.org/web/20200227225846/http://www.pollere.net/Pdfdocs/QrantJul06.pdf|dead-url=no}}</ref>

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

=== 好队列和坏队列 ===

CoDel区分两种队列： <ref name="CoDel_ACMQ" /> <ref>{{Cite web|title=CoDel buffer management could solve the Internet’s bufferbloat jams|url=https://arstechnica.com/information-technology/2012/05/codel-buffer-management-could-solve-the-internets-bufferbloat-jams/|accessdate=2012-08-16|author=Iljitsch van Beijnum|date=2012-05-10|publisher=Ars Technica|archive-date=2012-08-28|archive-url=https://web.archive.org/web/20120828113258/http://arstechnica.com/information-technology/2012/05/codel-buffer-management-could-solve-the-internets-bufferbloat-jams/|dead-url=no}}</ref>

; 好队列

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

; 坏队列

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

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

[[范·雅各布森|范雅各布森（Van Jacobson）]]在2006年断言，现有算法一直在使用错误的方法来识别缓冲区膨胀。 <ref name="Rant_Jacobson2">{{Cite web|title=A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA|url=http://www.pollere.net/Pdfdocs/QrantJul06.pdf|accessdate=12 August 2012|author=Jacobson|first=Van|authorlink=Van Jacobson|year=2006|archive-date=2020-02-27|archive-url=https://web.archive.org/web/20200227225846/http://www.pollere.net/Pdfdocs/QrantJul06.pdf|dead-url=no}}</ref> 诸如[[随机早期检测|RED]]之类的算法会测量平均队列长度，如果平均长度过大，则将其视为缓冲膨胀的情况。 雅各布森（Jacobson）在2006年证明，此度量不是一个好的指标，因为在通信突发情况下，平均队列长度会急剧增加。 然后，队列可以快速消散（好队列）或变为站立队列（坏队列）。 网络流量中的其他因素也可能导致误报或误报，从而导致不必要地部署了对策。 Jacobson建议，平均队列长度实际上根本不包含有关数据包需求或网络负载的信息。 <ref name="CoDel_ACMQ" /> <ref name="Rant_Jacobson2" /> 他建议，更好的指标可能是滑动时间窗口内的最小队列长度。 <ref name="CoDel_ACMQ" />  

== 算法 ==
根据2006年Jacobson的观点，CoDel旨在将CoDel管理的缓冲区队列中的数据包延迟控制在''最小延迟''下。目标是将此''最小延迟''保持在5毫秒以下。 如果最小延迟上升到一个太大的值，则将数据包从队列中丢弃，直到延迟降至最大级别以下。 <ref name="CoDel_ACMQ">{{Cite web|title=Controlling Queue Delay|url=http://queue.acm.org/detail.cfm?id=2209336|accessdate=12 August 2012|author=Nichols|date=6 May 2012|first=Kathleen|authorlink=Kathleen Nichols|work=ACM Queue|publisher=ACM Publishing|doi=10.1145/2209249.2209264|archive-date=2020-02-27|archive-url=https://web.archive.org/web/20200227232857/https://queue.acm.org/detail.cfm?id=2209336}}</ref> 

Nichols和Jacobson引用了仅使用此度量标准的几个优点： <ref name="CoDel_ACMQ" />

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

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

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

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

=== 仿真结果 ===
Nichols和Jacobson已在不同的MTU，链路速率和其他条件变化的模拟测试中对CoDel进行了测试。 通常，结果表明： <ref name="CoDel_ACMQ2">{{Cite web|title=Controlling Queue Delay|url=http://queue.acm.org/detail.cfm?id=2209336|accessdate=12 August 2012|author=Nichols|date=6 May 2012|first=Kathleen|authorlink=Kathleen Nichols|work=ACM Queue|publisher=ACM Publishing|doi=10.1145/2209249.2209264|archive-date=2020-02-27|archive-url=https://web.archive.org/web/20200227232857/https://queue.acm.org/detail.cfm?id=2209336|dead-url=no}}</ref> <ref name="CoDel_sims2">{{Cite web|title=Controlled Delay (CoDel) Active Queue Management|url=http://www.pollere.net/CoDel.html|accessdate=12 August 2012|author=Nichols|date=July 2012|first=Kathleen|publisher=Pollere Inc.|archiveurl=https://web.archive.org/web/20120822123432/http://www.pollere.net/CoDel.html|archivedate=2012-08-22|dead-url=no}}</ref> 

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

{{Translink|en|CableLabs}}的 Greg White和Joey Padden也进行了仿真。 <ref>{{Cite journal|title=Preliminary Study of Codel AGM in a Docsis Network|url=http://www.cablelabs.com/wp-content/uploads/2014/05/PreliminaryStudyOfCoDelAQM_DOCSIS-Network.pdf|last=Greg White|last2=Joey Padden|date=November 2012|accessdate=2015-06-14|format=PDF|journal=|archive-date=2015-09-23|archive-url=https://web.archive.org/web/20150923195748/http://www.cablelabs.com/wp-content/uploads/2014/05/PreliminaryStudyOfCoDelAQM_DOCSIS-Network.pdf|dead-url=no}}</ref>

=== 实现 ===
CoDel 2012年5月就出现了完整实现，并已作为[[开源软件|开源软件提供]] 。 <ref name="CoDel_ACMQ3">{{Cite web|title=Controlling Queue Delay|url=http://queue.acm.org/detail.cfm?id=2209336|accessdate=12 August 2012|author=Nichols|date=6 May 2012|first=Kathleen|authorlink=Kathleen Nichols|work=ACM Queue|publisher=ACM Publishing|doi=10.1145/2209249.2209264|archive-date=2020-02-27|archive-url=https://web.archive.org/web/20200227232857/https://queue.acm.org/detail.cfm?id=2209336|dead-url=no}}</ref> 它是在[[Linux内核|Linux内核中]]实现的（从3.5主线开始）。 <ref name="CoDel_Linux">{{Cite web|title=A Milestone Reached: CoDel is in Linux!|url=http://gettys.wordpress.com/2012/05/22/a-milestone-reached-codel-is-in-linux/|accessdate=12 August 2012|author=Gettys|date=22 May 2012|first=Jim|authorlink=Jim Gettys|work=jg's Ramblings|archive-date=2020-02-26|archive-url=https://web.archive.org/web/20200226115225/https://gettys.wordpress.com/2012/05/22/a-milestone-reached-codel-is-in-linux/|dead-url=no}}</ref> DaveTäht将CoDel移植到了[[OpenWrt|CeroWrt]]项目的Linux内核3.3中，这个项目涉及[[缓冲膨胀]]， <ref>{{Cite web|title=Cerowrt - Overview|url=http://www.bufferbloat.net/projects/cerowrt|accessdate=2014-01-24|publisher=Bufferbloat|archive-date=2014-01-19|archive-url=https://web.archive.org/web/20140119103449/http://www.bufferbloat.net/projects/cerowrt|dead-url=no}}</ref>CoDel 在此进行了详尽的测试。 2013年，CoDel开始在某些[[专有软件]]/[[turnkey]]带宽管理平台中作为选件出现。 <ref name="Procera_PacketLogic_Changelog">{{Cite web|title=Procera Packetlogic Changelog|url=http://download.proceranetworks.com/client-bin/14.0/11/changelog.txt|accessdate=2013-07-24|work=proceranetworks.com|archiveurl=https://archive.today/20130724211528/http://download.proceranetworks.com/client-bin/14.0/11/changelog.txt|archivedate=2013-07-24|dead-url=no}}</ref> FreeBSD在2016年将CoDel集成到11.x <ref>{{Cite web|title=Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE).|url=https://svnweb.freebsd.org/base?view=revision&revision=300779|author=truckman|date=2016-05-26|access-date=2020-02-26|archive-date=2021-02-25|archive-url=https://web.archive.org/web/20210225072959/https://svnweb.freebsd.org/base?view=revision&revision=300779}}</ref>和10.x <ref>{{Cite web|title=MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE).|url=https://svnweb.freebsd.org/base?view=revision&revision=301772|author=truckman|date=2016-06-10|accessdate=2020-02-26|archive-date=2019-12-18|archive-url=https://web.archive.org/web/20191218125213/https://svnweb.freebsd.org/base?view=revision&revision=301772|dead-url=no}}</ref> [[分支 (版本控制)|代码分支]]中。 <ref>{{Cite web|title=Implementing AQM in FreeBSD|url=http://caia.swin.edu.au/freebsd/aqm/|author=Al Saadi|first=Rasool|accessdate=2020-02-26|archive-date=2020-02-28|archive-url=https://web.archive.org/web/20200228143301/http://caia.swin.edu.au/freebsd/aqm/|dead-url=no}}</ref> 从6.2版开始，实现随[[OpenBSD|OpenBSD一起]]分发。 <ref>{{Cite web|title=OpenBSD 6.2|url=https://www.openbsd.org/62.html|accessdate=13 October 2017|archive-date=2017-10-12|archive-url=https://web.archive.org/web/20171012110335/http://www.openbsd.org/62.html|dead-url=no}}</ref> 

== 參考資料 ==
{{Reflist|2}}


== 外部連結 ==

{{Authority control}}
[[Category:封包]]
[[Category:網路排程演算法]]