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

## 參考資料

 

## 外部連結