fbpx
维基百科

CoDel

十一月 04, 2023

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

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

理论基础 编辑

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

缓冲膨胀 编辑

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

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

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

好队列和坏队列 编辑

CoDel区分两种队列： [2] [5]

好队列

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

坏队列

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

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

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

算法 编辑

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

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

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

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

算法的描述 编辑

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

当缩短间隔时，将根据由于过多排队延迟而丢包的连续间隔数的倒数平方根来执行此操作。 间隔的顺序是  ，   ，   ，   ，   ……

仿真结果 编辑

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

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

CableLabs（英语：CableLabs）的 Greg White和Joey Padden也进行了仿真。 [9]

实现 编辑

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

參考資料 编辑

  1. ^ Joe Brockmeier. Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution. ReadWriteWeb. 2012-05-08 [2012-08-16]. （原始内容于2012-07-12）. 
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Nichols, Kathleen. . ACM Queue. ACM Publishing. 6 May 2012 [12 August 2012]. doi:10.1145/2209249.2209264. （原始内容存档于2020-02-27）. 
  3. ^ Jacobson, Van; Karels, MJ. (PDF). ACM SIGCOMM Computer Communication Review. 1988, 18 (4) [2020-02-26]. （原始内容 (PDF)存档于2004-06-22）. 
  4. ^ Jacobson, Van. A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA (PDF). 2006 [12 August 2012]. （原始内容 (PDF)于2020-02-27）. 
  5. ^ Iljitsch van Beijnum. CoDel buffer management could solve the Internet’s bufferbloat jams. Ars Technica. 2012-05-10 [2012-08-16]. （原始内容于2012-08-28）. 
  6. ^ 6.0 6.1 Jacobson, Van. A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA (PDF). 2006 [12 August 2012]. （原始内容 (PDF)于2020-02-27）. 
  7. ^ Nichols, Kathleen. Controlling Queue Delay. ACM Queue. ACM Publishing. 6 May 2012 [12 August 2012]. doi:10.1145/2209249.2209264. （原始内容于2020-02-27）. 
  8. ^ Nichols, Kathleen. Controlled Delay (CoDel) Active Queue Management. Pollere Inc. July 2012 [12 August 2012]. （原始内容于2012-08-22）. 
  9. ^ Greg White; Joey Padden. Preliminary Study of Codel AGM in a Docsis Network (PDF). November 2012 [2015-06-14]. （原始内容 (PDF)于2015-09-23）. 
  10. ^ Nichols, Kathleen. Controlling Queue Delay. ACM Queue. ACM Publishing. 6 May 2012 [12 August 2012]. doi:10.1145/2209249.2209264. （原始内容于2020-02-27）. 
  11. ^ Gettys, Jim. A Milestone Reached: CoDel is in Linux!. jg's Ramblings. 22 May 2012 [12 August 2012]. （原始内容于2020-02-26）. 
  12. ^ Cerowrt - Overview. Bufferbloat. [2014-01-24]. （原始内容于2014-01-19）. 
  13. ^ Procera Packetlogic Changelog. proceranetworks.com. [2013-07-24]. （原始内容存档于2013-07-24）. 
  14. ^ truckman. . 2016-05-26 [2020-02-26]. （原始内容存档于2021-02-25）. 
  15. ^ truckman. MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE).. 2016-06-10 [2020-02-26]. （原始内容于2019-12-18）. 
  16. ^ Al Saadi, Rasool. Implementing AQM in FreeBSD. [2020-02-26]. （原始内容于2020-02-28）. 
  17. ^ OpenBSD 6.2. [13 October 2017]. （原始内容于2017-10-12）. 


外部連結 编辑

十一月 04, 2023
codel, 在网络路由中, controlled, delay, 英語發音, ˈkɒdəl, 是van, jacobson和kathleen, nichols, 英语, kathleen, nichols, 开发的网络调度器, 英语, network, scheduler, 中使用的调度算法, 它旨在通过设置缓冲区中网络数据包的延迟限制来克服网络硬件, 如路由器, 中的缓冲膨胀, 改善了随机早期检测, 英语, random, early, detection, 算法的整体性能, 解决了jacobson, 开发, . 在网络路由中 CoDel Controlled Delay 英語發音 ˈkɒdel 是Van Jacobson和Kathleen Nichols 英语 Kathleen Nichols 开发的网络调度器 英语 Network scheduler 中使用的调度算法 它旨在通过设置缓冲区中网络数据包的延迟限制来克服网络硬件 如路由器 中的缓冲膨胀 改善了随机早期检测 英语 random early detection RED 算法的整体性能 解决了Jacobson 开发 RED 时抱有的一些误解 设计上 CoDel 比 RED 更容易管理和配置 2012年 DaveTaht和Eric Dumazet为Linux内核编写了CoDel的实现 并以GNU通用公共许可证和3条款BSD许可证双重许可发布 Dumazet的CoDel变体称为fq codel 代表 公平队列 英语 Fair queuing 控制延迟 它在OpenWrt版本 Barrier Breaker 中被用作标准主动队列管理 英语 Active queue management AQM 和数据包调度解决方案 自这之后 CoDel和fq codel 迁移到了各种下游项目 例如Tomato dd wrt和OPNsense 目录 1 理论基础 1 1 缓冲膨胀 1 2 好队列和坏队列 2 算法 2 1 算法的描述 2 2 仿真结果 2 3 实现 3 參考資料 4 外部連結理论基础 编辑CoDel背后的理论基于对缓冲区影响下分组交换网络中数据包行为的观察 这些观察中的一些与排队的基本性质和缓冲膨胀的原因有关 另一些与队列管理算法的弱点有关 CoDel的开发旨在解决缓冲膨胀问题 1 缓冲膨胀 编辑 数据包在快速网络和慢速网络之间的网络链路传输时速度会变慢 尤其是在TCP会话开始时 突然出现数据包激增并且较慢的网络可能无法快速接受该突发时足够 缓冲区的存在是为了缓解这个问题 它给了快速网络一个存储数据包的地方 让慢速网络以自己的速度读取数据包 2 换句话说 缓冲区的作用就像减震器一样 将突发到达信号转换为平稳平稳的信号 但是 缓冲区的容量有限 理想的缓冲区大小可以处理突发的通信 并使突发的速度与较慢网络的速度相匹配 理想情况下 冲击吸收情况的特征是在传输突发期间缓冲器中的分组的暂时延迟 之后延迟迅速消失 并且网络在提供和处理分组方面达到平衡 2 TCP拥塞控制算法依赖于数据包丢弃来确定两个通信设备之间的可用带宽 它可以加快数据传输速度 直到数据包开始丢失为止 然后降低传输速率 理想情况下 当它在链接速度上找到平衡时 它会继续加速和减速 为此 必须及时发生丢包 以便算法可以响应地选择合适的传输速度 如果数据包保存在一个过大的缓冲区中 则数据包将到达其目的地 但具有较高的延迟 但不会丢弃任何数据包 因此TCP不会减慢速度 在这种情况下 TCP甚至可能确定连接的路径已更改 并重复搜索新的平衡点 3 4 拥有一个大而不断的缓冲区 这会导致传输延迟增加和交互性降低 尤其是在查看同一通道上的两个或多个同时传输时 这种情况称为缓冲区膨胀 可用的通道带宽也可能最终未被使用 因为某些缓冲区可能被缓冲区阻塞 等待数据传送到较慢的目的地 因此可能无法到达某些快速的目的地 好队列和坏队列 编辑 CoDel区分两种队列 2 5 好队列定义为不显示缓冲膨胀的队列 通信突发只会导致队列延迟的暂时增加 网络链接利用率最大化 坏队列定义为显示缓冲区膨胀的队列 通信突发会导致缓冲区填满并保持填满 从而导致利用率低和缓冲区延迟不断增加 为了有效地防止缓冲区膨胀 主动队列管理 AQM 算法形式的解决方案必须能够识别缓冲区膨胀的发生并通过部署有效的对策进行反应 范雅各布森 Van Jacobson 在2006年断言 现有算法一直在使用错误的方法来识别缓冲区膨胀 6 诸如RED之类的算法会测量平均队列长度 如果平均长度过大 则将其视为缓冲膨胀的情况 雅各布森 Jacobson 在2006年证明 此度量不是一个好的指标 因为在通信突发情况下 平均队列长度会急剧增加 然后 队列可以快速消散 好队列 或变为站立队列 坏队列 网络流量中的其他因素也可能导致误报或误报 从而导致不必要地部署了对策 Jacobson建议 平均队列长度实际上根本不包含有关数据包需求或网络负载的信息 2 6 他建议 更好的指标可能是滑动时间窗口内的最小队列长度 2 算法 编辑根据2006年Jacobson的观点 CoDel旨在将CoDel管理的缓冲区队列中的数据包延迟控制在最小延迟下 目标是将此最小延迟保持在5毫秒以下 如果最小延迟上升到一个太大的值 则将数据包从队列中丢弃 直到延迟降至最大级别以下 2 Nichols和Jacobson引用了仅使用此度量标准的几个优点 2 CoDel是无参数的 RED算法 根据Jacobson 的弱点之一是 它太难配置 尤其是在具有动态链接速率的环境中 CoDel根本没有要设置的参数 CoDel区分好队列和坏队列 好的队列本质上具有较低的延迟 因此管理算法可以忽略它 而坏的队列则受到丢包形式的管理干预 CoDel的工作原理是完全由本地决定的 因此它与往返延迟 链接速率 流量负载以及其他无法由本地缓冲区控制或预测的因素无关 本地最小延迟只能在数据包离开缓冲区时确定 因此不需要额外的延迟来运行队列以收集统计信息来管理队列 CoDel适应动态变化的链路速率 而不会对利用率产生负面影响 CoDel可以相对简单地实现 因此可以涵盖从低端家用路由器到高端路由解决方案的整个范围 如果缓冲区窗口的最小延迟低于最大允许值 则CoDel不执行任何管理缓冲区的操作 如果缓冲区相对为空 如果缓冲区中的字节数少于一个MTU 则它也不执行任何操作 2 如果不满足这些条件 则CoDel可能会丢弃数据包 2 算法的描述 编辑 该算法是在网络的每一跳上独立计算的 该算法在一个间隔 最初为100毫秒 内运行 通过跳监控每个数据包的排队延迟 英语 Queuing delay 每个数据包出队的时候会被转发 先计算每个包的排队延迟 数据包在队列中等待了多少时间 在这个时间间隔内的最小 排队延迟 要存储下来 当这个时间间隔内的最后一个数据包出队时 如果该间隔的最小 排队延迟 大于5毫秒 则会丢弃此单个数据包 并缩短用于下一组数据包的时间间隔 如果该时间间隔的最低排队延迟小于5毫秒 则转发数据包并将该时间间隔重置为100毫秒 当缩短间隔时 将根据由于过多排队延迟而丢包的连续间隔数的倒数平方根来执行此操作 间隔的顺序是100 displaystyle 100 nbsp 100 2 displaystyle 100 over sqrt 2 nbsp 100 3 displaystyle 100 over sqrt 3 nbsp 100 4 displaystyle 100 over sqrt 4 nbsp 100 5 displaystyle 100 over sqrt 5 nbsp 仿真结果 编辑 Nichols和Jacobson已在不同的MTU 链路速率和其他条件变化的模拟测试中对CoDel进行了测试 通常 结果表明 7 8 与RED相比 CoDel在整个带宽范围 从3到100Mbit s 中使数据包延迟更接近目标值 测得的链路利用率始终接近链路带宽的100 MTU较低时 数据包延迟比MTU较高时低 MTU越高 链路利用率就越高 而MTU越低 带宽越低 链路利用率就越好 从而降低了高带宽的公平利用率 CableLabs 英语 CableLabs 的 Greg White和Joey Padden也进行了仿真 9 实现 编辑 CoDel 2012年5月就出现了完整实现 并已作为开源软件提供 10 它是在Linux内核中实现的 从3 5主线开始 11 DaveTaht将CoDel移植到了CeroWrt项目的Linux内核3 3中 这个项目涉及缓冲膨胀 12 CoDel 在此进行了详尽的测试 2013年 CoDel开始在某些专有软件 turnkey带宽管理平台中作为选件出现 13 FreeBSD在2016年将CoDel集成到11 x 14 和10 x 15 代码分支中 16 从6 2版开始 实现随OpenBSD一起分发 17 參考資料 编辑 Joe Brockmeier Good News for Solving Bufferbloat CoDel Provides No Knobs Solution ReadWriteWeb 2012 05 08 2012 08 16 原始内容存档于2012 07 12 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 Nichols Kathleen Controlling Queue Delay ACM Queue ACM Publishing 6 May 2012 12 August 2012 doi 10 1145 2209249 2209264 原始内容存档于2020 02 27 Jacobson Van Karels MJ Congestion avoidance and control PDF ACM SIGCOMM Computer Communication Review 1988 18 4 2020 02 26 原始内容 PDF 存档于2004 06 22 Jacobson Van A rant on queues A talk presented at MIT Lincoln Labs Lexington MA PDF 2006 12 August 2012 原始内容存档 PDF 于2020 02 27 Iljitsch van Beijnum CoDel buffer management could solve the Internet s bufferbloat jams Ars Technica 2012 05 10 2012 08 16 原始内容存档于2012 08 28 6 0 6 1 Jacobson Van A rant on queues A talk presented at MIT Lincoln Labs Lexington MA PDF 2006 12 August 2012 原始内容存档 PDF 于2020 02 27 Nichols Kathleen Controlling Queue Delay ACM Queue ACM Publishing 6 May 2012 12 August 2012 doi 10 1145 2209249 2209264 原始内容存档于2020 02 27 Nichols Kathleen Controlled Delay CoDel Active Queue Management Pollere Inc July 2012 12 August 2012 原始内容存档于2012 08 22 Greg White Joey Padden Preliminary Study of Codel AGM in a Docsis Network PDF November 2012 2015 06 14 原始内容存档 PDF 于2015 09 23 Nichols Kathleen Controlling Queue Delay ACM Queue ACM Publishing 6 May 2012 12 August 2012 doi 10 1145 2209249 2209264 原始内容存档于2020 02 27 Gettys Jim A Milestone Reached CoDel is in Linux jg s Ramblings 22 May 2012 12 August 2012 原始内容存档于2020 02 26 Cerowrt Overview Bufferbloat 2014 01 24 原始内容存档于2014 01 19 Procera Packetlogic Changelog proceranetworks com 2013 07 24 原始内容存档于2013 07 24 truckman Import Dummynet AQM version 0 2 1 CoDel FQ CoDel PIE and FQ PIE 2016 05 26 2020 02 26 原始内容存档于2021 02 25 truckman MFC Import Dummynet AQM version 0 2 1 CoDel FQ CoDel PIE and FQ PIE 2016 06 10 2020 02 26 原始内容存档于2019 12 18 Al Saadi Rasool Implementing AQM in FreeBSD 2020 02 26 原始内容存档于2020 02 28 OpenBSD 6 2 13 October 2017 原始内容存档于2017 10 12 外部連結 编辑 取自 https zh wikipedia org w index php title CoDel amp oldid 79012295, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。