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