CoDel

✍ dations ◷ 2024-09-20 11:40:29 #计算机编程

在网络路由中,CoDel(Controlled Delay,发音为“ coddle ”)是Van Jacobson和Kathleen Nichols开发的网络调度程序中使用的调度算法 。 它旨在通过设置缓冲区中网络数据包的延迟限制来克服网络硬件(如路由器)中的 缓冲膨胀 ,改善了随机早期检测(random early detection(英语:random early detection),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不执行任何管理缓冲区的操作。 如果缓冲区相对为空(如果缓冲区中的字节数少于一个MTU),则它也不执行任何操作 。如果不满足这些条件,则CoDel可能会丢弃数据包。

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

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

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

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一起分发。



相关

  • 阴茎人类阴茎是男性人类交配和排尿的器官。人的阴茎由三个主要部分组成:根部、体部,以及用以覆盖龟头的上皮部分(包括阴茎体部两侧的皮肤和包皮)。阴茎的主体主要由两个位于背侧的阴
  • 禁忌禁忌或忌讳是指在一些特定的文化或是在生活起居中被禁止的行为和思想;如果被禁止的是某些词汇或物品的话,则称为禁忌语、禁忌物或禁忌品。有关的行为或词汇之所以会被禁止,可能
  • 220110 数学 120 信息科学与系统科学 130 力学 140 物理学 150 化学 160 天文学 170 地球科学 180 生物学210 农学 220 林学 230 畜牧、兽医科学 240 水产学310 
  • 增透膜增透膜(英语:Anti-reflective coating,AR)是一种表面光学镀层,它通过减少光的反射而增加透过率。在复杂的光学系统中,它可以通过减少系统中的散射光来提高对比度,例如望远镜,这对天
  • 六堆六堆(台湾客语南四县腔:liugˋ doiˊ/客语白话字:Liuk-tôi)始自台湾朱一贵事件发生后,原籍潮州府之镇平县(今蕉岭)、程乡县(今梅县)、平远县、大埔县,和汀州府之永定县、武平县、上杭
  • 东港区东港区是中国山东省日照市所辖的一个市辖区。总面积为1507平方千米,2004年人口为84万。东港区辖:7个街道,7个镇。(截止2019年12月31日)
  • 环境社会科学环境社会科学是人类与自然环境之间相互关系的广泛的跨学科研究课题。环境社会科学家在人类学、传播学、经济学、地理学、历史学、政治学、心理学和社会学等学术领域中开展研
  • 北京市第四十一中学坐标:39°55′34″N 116°22′01″E / 39.9261995°N 116.3670522°E / 39.9261995; 116.3670522北京市第四十一中学是中国北京市西城区的一所普通完全中学,位于西四北二条58
  • 周春 (乾隆进士)周春(1729年-1815年),字芚兮,号松霭,晚号黍谷居士,浙江海宁盐官人。周春为乾隆十九年(1754年)进士,在家候职十余年。后授广西岑溪知县。因父死丁忧离任。归家后,不再出仕,专心著述。嘉庆
  • 非洲各国人类发展指数列表人类发展指数是联合国开发计划署为衡量各国社会经济发展程度而制定的标准,该指数为根据国家人民出生时预期寿命、受教育年限、人均国民总收入计算出。各国家(大多为联合国会员