[要約] RFC 8289は、制御された遅延アクティブキューマネジメント（CoDel）に関するものであり、ネットワークの遅延を制御するためのアルゴリズムを提案しています。その目的は、ネットワークのパフォーマンスを向上させ、遅延の問題を解決することです。
Internet Engineering Task Force (IETF) K. Nichols
Request for Comments: 8289 Pollere, Inc.
Category: Experimental V. Jacobson
ISSN: 2070-1721 A. McGregor, Ed.
J. Iyengar, Ed.
Google
January 2018
Controlled Delay Active Queue Management
制御された遅延アクティブキュー管理
Abstract
概要
This document describes CoDel (Controlled Delay) -- a general framework that controls bufferbloat-generated excess delay in modern networking environments. CoDel consists of an estimator, a setpoint, and a control loop. It requires no configuration in normal Internet deployments.
このドキュメントでは、CoDel（制御された遅延）について説明します。これは、最新のネットワーク環境でバッファブロートによって生成された過剰な遅延を制御する一般的なフレームワークです。 CoDelは、推定器、設定点、および制御ループで構成されています。通常のインターネット展開では設定は必要ありません。
Status of This Memo
本文書の状態
This document is not an Internet Standards Track specification; it is published for examination, experimental implementation, and evaluation.
このドキュメントはInternet Standards Trackの仕様ではありません。試験、実験、評価のために公開されています。
This document defines an Experimental Protocol for the Internet community. This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not all documents approved by the IESG are a candidate for any level of Internet Standard; see Section 2 of RFC 7841.
このドキュメントでは、インターネットコミュニティの実験プロトコルを定義します。このドキュメントは、IETF（Internet Engineering Task Force）の製品です。これは、IETFコミュニティのコンセンサスを表しています。公開レビューを受け、インターネットエンジニアリングステアリンググループ（IESG）による公開が承認されました。 IESGによって承認されたすべてのドキュメントが、あらゆるレベルのインターネット標準の候補になるわけではありません。 RFC 7841のセクション2をご覧ください。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at https://www.rfc-editor.org/info/rfc8289.
このドキュメントの現在のステータス、正誤表、およびフィードバックの提供方法に関する情報は、https：//www.rfc-editor.org/info/rfc8289で入手できます。
Copyright Notice
著作権表示
Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved.
Copyright（c）2018 IETF Trustおよびドキュメントの作成者として識別された人物。全著作権所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
この文書は、BCP 78およびIETF文書に関するIETFトラストの法的規定（https://trustee.ietf.org/license-info）の対象であり、この文書の発行日に有効です。これらのドキュメントは、このドキュメントに関するあなたの権利と制限について説明しているため、注意深く確認してください。このドキュメントから抽出されたコードコンポーネントには、Trust Legal Provisionsのセクション4.eに記載されているSimplified BSD Licenseのテキストが含まれている必要があり、Simplified BSD Licenseに記載されているように保証なしで提供されます。
Table of Contents
目次
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Conventions and Terms Used in This Document . . . . . . . . . 4
3. Understanding the Building Blocks of Queue Management . . . . 5
3.1. Estimator . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Target Setpoint . . . . . . . . . . . . . . . . . . . . . 8
3.3. Control Loop . . . . . . . . . . . . . . . . . . . . . . 10
4. Overview of the CoDel AQM . . . . . . . . . . . . . . . . . . 13
4.1. Non-starvation . . . . . . . . . . . . . . . . . . . . . 14
4.2. Setting INTERVAL . . . . . . . . . . . . . . . . . . . . 14
4.3. Setting TARGET . . . . . . . . . . . . . . . . . . . . . 14
4.4. Use with Multiple Queues . . . . . . . . . . . . . . . . 15
4.5. Setting Up CoDel . . . . . . . . . . . . . . . . . . . . 16
5. Annotated Pseudocode for CoDel AQM . . . . . . . . . . . . . 16
5.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 17
5.2. Per-Queue State (codel_queue_t Instance Variables) . . . 17
5.3. Constants . . . . . . . . . . . . . . . . . . . . . . . . 17
5.4. Enqueue Routine . . . . . . . . . . . . . . . . . . . . . 18
5.5. Dequeue Routine . . . . . . . . . . . . . . . . . . . . . 18
5.6. Helper Routines . . . . . . . . . . . . . . . . . . . . . 19
5.7. Implementation Considerations . . . . . . . . . . . . . . 21
6. Further Experimentation . . . . . . . . . . . . . . . . . . . 21
7. Security Considerations . . . . . . . . . . . . . . . . . . . 21
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 22
9.1. Normative References . . . . . . . . . . . . . . . . . . 22
9.2. Informative References . . . . . . . . . . . . . . . . . 22
Appendix A. Applying CoDel in the Data Center . . . . . . . . . 24
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25
The "persistently full buffer" problem has been discussed in the IETF community since the early 80s [RFC896]. The IRTF's End-to-End Research Group called for the deployment of Active Queue Management (AQM) to solve the problem in 1998 [RFC2309]. Despite this awareness, the problem has only gotten worse as growth in memory density per Moore's Law fueled an exponential increase in buffer pool size. Efforts to deploy AQM have been frustrated by difficult configuration and negative impact on network utilization. This "bufferbloat" problem [BLOAT] has become increasingly important throughout the Internet but particularly at the consumer edge. Queue management has become more critical due to increased consumer use of the Internet, mixing large video transactions with time-critical VoIP and gaming.
「永続的にフルバッファ」の問題は、80年代初頭以来、IETFコミュニティで議論されてきました[RFC896]。 IRTFのEnd-to-End Research Groupは、1998年に問題を解決するためにActive Queue Management（AQM）の導入を要求しました[RFC2309]。この認識にもかかわらず、ムーアの法則によるメモリ密度の増加がバッファプールサイズの指数関数的な増加を助長したため、問題は悪化しました。 AQMを展開する取り組みは、構成が困難であり、ネットワーク使用率に悪影響を及ぼしていることに苛立ちを感じてきました。この「バッファブロート」問題[BLOAT]は、インターネット全体、特に消費者のエッジでますます重要になっています。大規模なビデオトランザクションとタイムクリティカルなVoIPおよびゲームが混在し、インターネットの消費者の使用が増加したため、キュー管理はより重要になっています。
An effective AQM remediates bufferbloat at a bottleneck while "doing no harm" at hops where buffers are not bloated. However, the development and deployment of AQM are frequently subject to misconceptions about the cause of packet queues in network buffers. Network buffers exist to absorb the packet bursts that occur naturally in statistically multiplexed networks. Buffers helpfully absorb the queues created by reasonable packet network behavior such as short-term mismatches in traffic arrival and departure rates that arise from upstream resource contention, transport conversation startup transients, and/or changes in the number of conversations sharing a link. Unfortunately, other less useful network behaviors can cause queues to fill, and their effects are not nearly as benign. Discussion of these issues and the reason why the solution is not simply "smaller buffers" can be found in [RFC2309], [VANQ2006], [REDL1998], and [CODEL2012]. To understand queue management, it is critical to understand the difference between the necessary, useful "good" queue and the counterproductive "bad" queue.
効果的なAQMは、バッファーが膨らんでいないホップで「害を及ぼさない」一方で、ボトルネックでバッファー膨らみを修正します。ただし、AQMの開発と展開は、ネットワークバッファー内のパケットキューの原因について誤解されることがよくあります。ネットワークバッファは、統計的に多重化されたネットワークで自然に発生するパケットバーストを吸収するために存在します。バッファは、上流のリソースの競合、トランスポート会話の起動の一時的な状態、リンクを共有する会話の数の変化から生じるトラフィックの到着率と出発率の短期的な不一致など、妥当なパケットネットワークの動作によって作成されたキューを効果的に吸収します。残念ながら、他のあまり役に立たないネットワークの動作によりキューがいっぱいになる可能性があり、それらの影響はほとんど無害です。これらの問題とその解決策が単に「小さいバッファー」ではない理由についての議論は、[RFC2309]、[VANQ2006]、[REDL1998]、および[CODEL2012]にあります。キュー管理を理解するには、必要で有用な「良い」キューと逆効果の「悪い」キューの違いを理解することが重要です。
Several approaches to AQM have been developed over the past two decades, but none have been widely deployed due to performance problems. When designed with the wrong conceptual model for queues, AQMs have limited operational range, require a lot of configuration tweaking, and frequently impair rather than improve performance. Learning from this past history, the CoDel approach is designed to meet the following goals:
AQMへのいくつかのアプローチが過去20年間に開発されてきましたが、パフォーマンスの問題のために広く展開されたものはありません。キューの誤った概念モデルを使用して設計すると、AQMの動作範囲が制限され、多くの構成の微調整が必要になり、パフォーマンスを向上させるのではなく、しばしば機能を低下させます。この過去の歴史から学んだCoDelアプローチは、次の目標を満たすように設計されています。
o Make AQM parameterless for normal operation, with no knobs for operators, users, or implementers to adjust.
o オペレーター、ユーザー、または実装者が調整するためのノブなしで、AQMを通常の操作用にパラメーターなしにします。
o Be able to distinguish "good" queue from "bad" queue and treat them differently, that is, keep delay low while permitting necessary bursts of traffic.
o 「良い」キューと「悪い」キューを区別し、それらを異なる方法で処理できるようにします。つまり、必要なトラフィックのバーストを許可しながら、遅延を低く抑えます。
o Control delay while insensitive (or nearly so) to round-trip delays, link rates, and traffic loads; this goal is to "do no harm" to network traffic while controlling delay.
o ラウンドトリップ遅延、リンクレート、およびトラフィック負荷の影響を受けない（またはそれに近い）遅延を制御します。この目標は、遅延を制御しながらネットワークトラフィックに「害を及ぼさない」ことです。
o Adapt to dynamically changing link rates with no negative impact on utilization.
o 使用率に悪影響を与えることなく、動的に変化するリンクレートに適応します。
o Allow simple and efficient implementation (can easily span the spectrum from low-end access points and home routers up to high-end router hardware).
o シンプルで効率的な実装を可能にします（ローエンドのアクセスポイントやホームルーターからハイエンドのルーターハードウェアまで、さまざまな範囲を簡単にカバーできます）。
CoDel has five major differences from prior AQMs: use of the local queue minimum to track congestion ("bad" queue), use of an efficient single state variable representation of that tracked statistic, use of packet sojourn time as the observed datum (rather than packets, bytes, or rates), use of a mathematically determined setpoint derived from maximizing network power [KLEIN81], and a modern state-space controller.
CoDelは、以前のAQMと5つの大きな違いがあります。ローカルキューの最小値を使用して輻輳（「不良」キュー）を追跡する、追跡された統計の効率的な単一状態変数表現を使用する、観測されたデータとしてパケット滞留時間を使用する（ではなく）パケット、バイト、またはレート）、ネットワーク電力の最大化[KLEIN81]から導出された数学的に決定されたセットポイントの使用、および最新の状態空間コントローラー。
CoDel configures itself based on a round-trip time metric that can be set to 100 ms for the normal, terrestrial Internet. With no changes to parameters, CoDel is expected to work across a wide range of conditions, with varying links and the full range of terrestrial round-trip times.
CoDelは、通常の地上インターネットでは100ミリ秒に設定できる往復時間メトリックに基づいて自身を構成します。パラメータを変更することなく、CoDelは、さまざまなリンクと全範囲の地上ラウンドトリップ時間で、幅広い条件で機能することが期待されています。
CoDel is easily adapted to multiple queue systems as shown by [RFC8290]. Implementers and users SHOULD use the fq_codel multiple-queue approach as it deals with many problems beyond the reach of an AQM on a single queue.
CoDelは、[RFC8290]で示されているように、複数のキューシステムに簡単に適応できます。実装者とユーザーは、fq_codelの複数キューアプローチを使用する必要があります。これは、単一キューでのAQMの到達範囲を超える多くの問題に対処するためです。
CoDel was first published in [CODEL2012] and has been implemented in the Linux kernel.
CoDelは[CODEL2012]で最初に公開され、Linuxカーネルに実装されています。
Note that while this document refers to dropping packets when indicated by CoDel, it may be reasonable to ECN-mark packets instead.
このドキュメントではCoDelによって示される場合のパケットのドロップについて言及していますが、代わりにパケットにECNマークを付けるのが妥当な場合があります。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.
キーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「NOT RECOMMENDED」、「MAY」、「OPTIONALこのドキュメントの「」は、BCP 14 [RFC2119] [RFC8174]で説明されているように解釈されます。
The following terms are used in this document and are defined as follows:
このドキュメントでは次の用語が使用され、次のように定義されています。
sojourn time: the amount of time a packet has spent in a particular buffer, i.e., the time a packet departs the buffer minus the time the packet arrived at the buffer. A packet can depart a buffer via transmission or drop.
滞留時間：パケットが特定のバッファで費やした時間、つまりパケットがバッファを出発する時間からパケットがバッファに到着する時間を引いた時間。パケットは、送信またはドロップを介してバッファを出発できます。
standing queue: a queue (in packets, bytes, or time delay) in a buffer that persists for a "long" time, where "long" is on the order of the longer round-trip times through the buffer, as discussed in Section 4.2. A standing queue occurs when the minimum queue over the "long" time is non-zero and is usually tolerable and even desirable as long as it does not exceed some target delay.
スタンディングキュー：「長い」時間持続するバッファ内のキュー（パケット、バイト、または時間遅延）。「長い」は、セクションで説明したように、バッファを通る長い往復時間のオーダーです。 4.2。スタンディングキューは、「長い」時間の最小キューがゼロ以外の場合に発生し、ある程度のターゲット遅延を超えない限り、通常は許容可能であり、望ましいことです。
bottleneck bandwidth: the limiting bandwidth along a network path.
ボトルネック帯域幅：ネットワークパスに沿った帯域幅の制限。
At the heart of queue management is the notion of "good" queue and "bad" queue and the search for ways to get rid of the "bad" queue (which only adds delay) while preserving the "good" queue (which provides for good utilization). This section explains queueing, both good and bad, and covers the CoDel building blocks that can be used to manage packet buffers to keep their queues in the "good" range.
キュー管理の中心となるのは、「良い」キューと「悪い」キューの概念と、「良い」キューを保持しながら（遅延を追加するだけ）「悪い」キューを取り除く方法の検索です。良好な使用率）。このセクションでは、キューイングについて説明し、キューを「良い」範囲に保つためにパケットバッファを管理するために使用できるCoDelビルディングブロックについて説明します。
Packet queues form in buffers facing bottleneck links, i.e., where the line rate goes from high to low or where many links converge. The well-known bandwidth-delay product (sometimes called "pipe size") is the bottleneck's bandwidth multiplied by the sender-receiver-sender round-trip delay; it is the amount of data that has to be in transit between two hosts in order to run the bottleneck link at 100% utilization. To explore how queues can form, consider a long-lived TCP connection with a 25-packet window sending through a connection with a bandwidth-delay product of 20 packets. After an initial burst of packets, the connection will settle into a 5-packet (+/-1) standing queue; this standing queue size is determined by the mismatch between the window size and the pipe size and is unrelated to the connection's sending rate. The connection has 25 packets in flight at all times, but only 20 packets arrive at the destination over a round-trip time. If the TCP connection has a 30-packet window, the queue will be 10 packets with no change in sending rate. Similarly, if the window is 20 packets, there will be no queue, but the sending rate is the same. Nothing can be inferred about the sending rate from the queue size, and any queue other than transient bursts only creates delays in the network. The sender needs to reduce the number of packets in flight rather than the sending rate.
パケットキューは、ボトルネックリンクに面するバッファ内に形成されます。つまり、ラインレートが高から低に変化したり、多くのリンクが収束したりします。よく知られている帯域幅遅延積（「パイプサイズ」と呼ばれることもあります）は、ボトルネックの帯域幅に送信者と受信者と送信者の往復遅延を掛けたものです。これは、ボトルネックリンクを100％の使用率で実行するために2つのホスト間で転送される必要があるデータの量です。キューがどのように形成されるかを調べるために、20パケットの帯域幅遅延積を持つ接続を介して送信する25パケットウィンドウを使用した、長寿命のTCP接続を検討してください。パケットの最初のバーストの後、接続は5パケット（+/- 1）スタンディングキューに落ち着きます。このスタンディングキューのサイズは、ウィンドウサイズとパイプサイズの不一致によって決まり、接続の送信レートとは関係ありません。接続では常に25個のパケットが処理中ですが、往復時間で宛先に到着するのは20個のパケットだけです。 TCP接続に30パケットのウィンドウがある場合、キューは10パケットになり、送信速度は変わりません。同様に、ウィンドウが20パケットの場合、キューはありませんが、送信レートは同じです。キューサイズから送信レートを推測することはできず、一時的なバースト以外のキューはネットワークに遅延を生じさせるだけです。送信側は、送信速度ではなく、送信中のパケット数を減らす必要があります。
In the above example, the 5-packet standing queue can be seen to contribute nothing but delay to the connection and thus is clearly "bad" queue. If, in our example, there is a single bottleneck link and it is much slower than the link that feeds it (say, a high-speed Ethernet link into a limited DSL uplink), then a 20-packet buffer at the bottleneck might be necessary to temporarily hold the 20 packets in flight to keep the bottleneck link's utilization high. The burst of packets should drain completely (to 0 or 1 packets) within a round-trip time, and this transient queue is "good" queue because it allows the connection to keep the 20 packets in flight and the bottleneck link to be fully utilized. In terms of the delay experienced, the "good" queue goes away in about a round-trip time, while "bad" queue hangs around for longer, causing delays.
上記の例では、5パケットのスタンディングキューは接続に遅延をもたらすだけで、明らかに「不良」キューです。この例では、単一のボトルネックリンクがあり、それを供給するリンク（たとえば、高速イーサネットリンクから制限付きDSLアップリンクへのリンク）よりもはるかに遅い場合、ボトルネックの20パケットバッファーはボトルネックリンクの使用率を高く保つために、一時的に20個のパケットを保持する必要があります。パケットのバーストは、往復時間内に完全に（0または1パケットに）排出する必要があります。この一時的なキューは、接続が20パケットを継続して保持し、ボトルネックリンクを完全に利用できるため、「良好」なキューです。 。発生する遅延に関しては、「良好な」キューは往復時間で消えますが、「不良な」キューは長時間滞留し、遅延を引き起こします。
Effective queue management detects "bad" queue while ignoring "good" queue and takes action to get rid of the "bad" queue when it is detected. The goal is a queue controller that accomplishes this objective. To control a queue, we need three basic components:
効果的なキュー管理は、「良い」キューを無視しながら「悪い」キューを検出し、検出されたときに「悪い」キューを取り除くアクションを実行します。目標は、この目的を達成するキューコントローラです。キューを制御するには、3つの基本コンポーネントが必要です。
o Estimator - To figure out what we've got.
o Estimator-私たちが持っているものを理解するため。
o Target setpoint - To know what we want.
o 目標設定値-何が欲しいかを知るため。
o Control loop - If what we've got isn't what we want, we need a way to move it there.
o 制御ループ-取得したものが必要なものと異なる場合は、そこに移動する方法が必要です。
The estimator both observes the queue and detects when "good" queue turns to "bad" queue and vice versa. CoDel has two parts to its estimator: what is observed as an indicator of queue and how the observations are used to detect "good"/"bad" queue.
推定器は、キューを監視し、「良い」キューが「悪い」キューに変わるとき、およびその逆のときを検出します。 CoDelは、その推定器に2つの部分があります。キューのインジケーターとして観測されるものと、「良好」/「不良」キューを検出するために観測がどのように使用されるかです。
Queue length has been widely used as an observed indicator of congestion and is frequently conflated with sending rate. Use of queue length as a metric is sensitive to how and when the length is observed. A high-speed arrival link to a buffer serviced at a much lower rate can rapidly build up a queue that might disperse completely or down to a single packet before a round-trip time has elapsed. If the queue length is monitored at packet arrival (as in original Random Early Detection (RED)) or departure time, every packet will see a queue with one possible exception. If the queue length itself is time sampled (as recommended in [REDL1998]), a truer picture of the queue's occupancy can be gained at the expense of considerable implementation complexity.
キューの長さは、輻輳の観察された指標として広く使用されており、送信速度と頻繁に混同されます。メトリックとしてのキューの長さの使用は、長さを監視する方法とタイミングに敏感です。非常に低いレートで処理されるバッファへの高速到着リンクは、ラウンドトリップ時間が経過する前に、完全に分散するか、単一のパケットに分散する可能性があるキューを急速に構築します。パケットの到着時（元のランダム早期検出（RED）のように）または出発時にキューの長さが監視されている場合、すべてのパケットは1つの可能性のある例外を持つキューを参照します。キューの長さ自体が時間サンプリングされている場合（[REDL1998]で推奨）、かなり複雑な実装を犠牲にして、キューの占有率をより正確に把握できます。
The use of queue length is further complicated in networks that are subject to both short- and long-term changes in available link rate (as in WiFi). Link rate drops can result in a spike in queue length that should be ignored unless it persists. It is not the queue length that should be controlled but the amount of excess delay packets experience due to a persistent or standing queue, which means that the packet sojourn time in the buffer is exactly what we want to track. Tracking the packet sojourn times in the buffer observes the actual delay experienced by each packet. Sojourn time allows queue management to be independent of link rate, gives superior performance to use of buffer size, and is directly related to user-visible performance. It works regardless of line rate changes or link sharing by multiple queues (which the individual queues may experience as changing rates).
キューの長さの使用は、（WiFiのように）利用可能なリンクレートの短期および長期の両方の変化の影響を受けるネットワークではさらに複雑です。リンク速度の低下により、キューの長さが急上昇する可能性があり、それが持続しない限り無視する必要があります。制御する必要があるのはキューの長さではありませんが、永続的または永続的なキューが原因でパケットに発生する過剰な遅延の量です。つまり、バッファ内のパケット滞留時間は、まさに追跡したいものです。バッファ内のパケット滞留時間を追跡すると、各パケットで発生する実際の遅延が観察されます。滞留時間により、キュー管理をリンクレートに依存せず、バッファサイズの使用に優れたパフォーマンスを提供し、ユーザーに見えるパフォーマンスに直接関係します。ラインレートの変更や、複数のキューによるリンク共有（個々のキューがレートの変化として経験する可能性があります）に関係なく機能します。
Consider a link shared by two queues with different priorities. Packets that arrive at the high-priority queue are sent as soon as the link is available, while packets in the other queue have to wait until the high-priority queue is empty (i.e., a strict priority scheduler). The number of packets in the high-priority queue might be large, but the queue is emptied quickly, and the amount of time each packet spends enqueued (the sojourn time) is not large. The other queue might have a smaller number of packets, but packet sojourn times will include the waiting time for the high-priority packets to be sent. This makes the sojourn time a good sample of the congestion that each separate queue is experiencing. This example also shows how the metric of sojourn time is independent of the number of queues or the service discipline used and is instead indicative of congestion seen by the individual queues.
優先度の異なる2つのキューで共有されているリンクを考えます。高優先度キューに到着したパケットは、リンクが利用可能になるとすぐに送信されますが、他のキュー内のパケットは、高優先度キューが空になるまで待機する必要があります（つまり、完全優先スケジューラー）。高優先度キューのパケット数は多いかもしれませんが、キューはすぐに空になり、各パケットがキューに入れられるのに費やす時間（滞在時間）は大きくありません。他のキューのパケット数は少ないかもしれませんが、パケットの滞留時間には、優先度の高いパケットが送信されるまでの待機時間が含まれます。これにより、滞留時間は、個別の各キューで発生している輻輳の良いサンプルになります。この例は、滞在時間のメトリックがキューの数や使用されているサービス規則に依存せず、代わりに個々のキューで見られる輻輳を示していることも示しています。
How can observed sojourn time be used to separate "good" queue from "bad" queue? Although averages, especially of queue length, have previously been widely used as an indicator of "bad" queue, their efficacy is questionable. Consider the burst that disperses every round-trip time. The average queue will be one-half the burst size, though this might vary depending on when the average is computed and the timing of arrivals. The average queue sojourn time would be one-half the time it takes to clear the burst. The average then would indicate a persistent queue where there is none. Instead of averages, we recommend tracking the minimum sojourn time; then, if there is one packet that has a zero sojourn time, there is no persistent queue.
観察された滞在時間を使用して、「良い」キューと「悪い」キューを区別するにはどうすればよいですか？特にキューの長さの平均は、以前は「不良」キューの指標として広く使用されてきましたが、その有効性には疑問があります。すべての往復時間に分散するバーストを考えてみましょう。平均キューはバーストサイズの半分になりますが、平均が計算されるタイミングと到着のタイミングによって異なる場合があります。キューの平均滞在時間は、バーストをクリアするのにかかる時間の半分です。平均値は、永続的なキューがないことを示します。平均ではなく、最短滞在時間を追跡することをお勧めします。滞留時間がゼロのパケットが1つある場合、永続的なキューはありません。
A persistent queue can be detected by tracking the (local) minimum queue delay packets experience. To ensure that this minimum value does not become stale, it has to have been experienced recently, i.e., during an appropriate past time interval. This interval is the maximum amount of time a minimum value is considered to be in effect and is related to the amount of time it takes for the largest expected burst to drain. Conservatively, this interval SHOULD be at least a round-trip time to avoid falsely detecting a persistent queue and not a lot more than a round-trip time to avoid delay in detecting the persistent queue. This suggests that the appropriate interval value is the maximum round-trip time of all the connections sharing the buffer.
永続的なキューは、（ローカル）最小キュー遅延パケットエクスペリエンスを追跡することで検出できます。この最小値が古くならないようにするには、最近、つまり過去の適切な時間間隔でこの値を経験している必要があります。この間隔は、最小値が有効であると見なされる最大時間であり、予想される最大のバーストが排出されるまでにかかる時間に関連しています。控えめに言っても、この間隔は、永続キューの誤った検出を回避するために少なくとも往復時間である必要があり、永続キューの検出の遅延を回避するために往復時間を超えてはなりません。これは、適切な間隔値が、バッファーを共有するすべての接続の最大往復時間であることを示唆しています。
Note that the following key insight makes computation of the local minimum efficient: it is sufficient to keep a single state variable that indicates how long the minimum has been above or below the target value rather than retaining all the local values to compute the minimum, which leads to both storage and computational savings. We use this insight in the pseudocode for CoDel later in the document.
次の重要な洞察は、ローカル最小値の計算を効率的にすることに注意してください。最小値を計算するためにすべてのローカル値を保持するのではなく、最小値がターゲット値の上または下にある時間を示す単一の状態変数を保持することで十分です。ストレージと計算の両方の節約につながります。この洞察は、ドキュメントの後半でCoDelの疑似コードに使用されます。
These two parts, use of sojourn time as the observed value and the local minimum as the statistic to monitor queue congestion, are key to CoDel's estimator building block. The local minimum sojourn time provides an accurate and robust measure of standing queue and has an efficient implementation. In addition, use of the minimum sojourn time has important advantages in implementation. The minimum packet sojourn can only be decreased when a packet is dequeued, which means that all the work of CoDel can take place when packets are dequeued for transmission and that no locks are needed in the implementation. The minimum is the only statistic with this property.
これらの2つの部分、観測値としての滞在時間の使用、およびキューの輻輳を監視する統計としての局所最小値の使用は、CoDelの推定器構築ブロックの鍵となります。ローカル最小滞在時間は、スタンディングキューの正確で堅牢な測定を提供し、効率的な実装を備えています。さらに、最短滞在時間の使用は、実装において重要な利点があります。最小パケット滞留時間は、パケットがキューから取り出されたときにのみ減らすことができます。つまり、パケットが送信のためにキューから取り出されたときにCoDelのすべての作業を行うことができ、実装でロックは必要ありません。最小値は、このプロパティを持つ唯一の統計です。
A more detailed explanation with many pictures can be found in [TSV84].
多くの写真を使ったより詳細な説明は[TSV84]にあります。
Now that we have a robust way of detecting standing queue, we need a target setpoint that tells us when to act. If the controller is set to take action as soon as the estimator has a non-zero value, the average drop rate will be maximized, which minimizes TCP goodput [MACTCP1997]. Also, this policy results in no backlog over time (no persistent queue), which negates much of the value of having a buffer, since it maximizes the bottleneck link bandwidth lost due to normal stochastic variation in packet interarrival time. We want a target that maximizes utilization while minimizing delay. Early in the history of packet networking, Kleinrock developed the analytic machinery to do this using a quantity he called "power", which is the ratio of a normalized throughput to a normalized delay [KLEIN81].
スタンディングキューを検出するための堅牢な方法が用意できたので、いつ行動するかを指示するターゲットセットポイントが必要です。推定量がゼロ以外の値になるとすぐにコントローラーがアクションを実行するように設定されている場合、平均ドロップ率は最大化され、TCPグッドプットを最小化します[MACTCP1997]。また、このポリシーは、パケットの到着時間の通常の確率的変動により失われるボトルネックリンク帯域幅を最大化するため、時間の経過に伴うバックログなし（永続的なキューなし）となり、バッファーを持つことの価値の多くを打ち消します。遅延を最小限に抑えながら、使用率を最大化するターゲットが必要です。パケットネットワーキングの歴史の早い段階で、Kleinrockは「電力」と呼ばれる量を使用してこれを行う分析機械を開発しました。これは、正規化スループットと正規化遅延の比率です[KLEIN81]。
It is straightforward to derive an analytic expression for the average goodput of a TCP conversation at a given round-trip time r and target f (where f is expressed as a fraction of r). Reno TCP, for example, yields:
与えられた往復時間rとターゲットf（fはrの分数として表される）でのTCP会話の平均グッドプットの分析式を導き出すのは簡単です。たとえば、Reno TCPの結果は次のとおりです。
goodput = r (3 + 6f - f^2) / (4 (1+f))
Since the peak queue delay is simply the product of f and r, power is solely a function of f since the r's in the numerator and denominator cancel:
ピークキュー遅延は単にfとrの積であるため、分子と分母のrが相殺されるため、電力は単にfの関数になります。
power is proportional to (1 + 2f - 1/3 f^2) / (1 + f)^2
As Kleinrock observed, the best operating point (in terms of bandwidth/delay trade-off) is the peak power point, since points off the peak represent a higher cost (in delay) per unit of bandwidth. The power vs. f curve for any Additive Increase Multiplicative Decrease (AIMD) TCP is monotone decreasing. But the curve is very flat for f < 0.1, followed by an increasing curvature with a knee around f = 0.2, then a steep, almost linear fall off [TSV84]. Since the previous equation showed that goodput is monotone increasing with f, the best operating point is near the right edge of the flat top, since that represents the highest goodput achievable for a negligible increase in delay. However, since the r in the model is a conservative upper bound, a target of 0.1r runs the risk of pushing shorter RTT connections over the knee and giving them higher delay for no significant goodput increase. Generally, a more conservative target of 0.05r offers a good utilization vs. delay trade-off while giving enough headroom to work well with a large variation in real RTT.
クラインロックが観察したように、（帯域幅/遅延のトレードオフの観点から）最高の動作点はピーク電力点です。ピークから離れた点は、帯域幅の単位あたりのコスト（遅延）が高いためです。加法的増加乗法的減少（AIMD）TCPの電力対f曲線は単調減少です。しかし、曲線はf <0.1の場合は非常に平坦であり、f = 0.2付近で膝が曲がり始めて急勾配で、ほぼ線形に落ちます[TSV84]。前の式はグッドプットがfとともに単調増加することを示したため、遅延の無視できるほどの増加に対して達成可能な最高のグッドプットを表すため、最良の動作点はフラットトップの右端近くにあります。ただし、モデルのrは控えめな上限であるため、0.1rのターゲットは、膝を介して短いRTT接続をプッシュし、大幅なグッドプットの増加なしにそれらに高い遅延を与えるリスクがあります。一般に、より保守的な0.05rのターゲットは、実際のRTTの大きな変動で十分に機能するのに十分なヘッドルームを提供しながら、使用率と遅延のトレードオフが優れています。
As the above analysis shows, a very small standing queue gives close to 100% utilization of the bottleneck link. While this result was for Reno TCP, the derivation uses only properties that must hold for any "TCP friendly" transport. We have verified by both analysis and simulation that this result holds for Reno, Cubic, and Westwood [TSV84]. This results in a particularly simple form for the target: the ideal range for the permitted standing queue, or the target setpoint, is between 5% and 10% of the TCP connection's RTT.
上記の分析が示すように、非常に小さなスタンディングキューでは、ボトルネックリンクの使用率がほぼ100％になります。この結果はReno TCPに対するものでしたが、派生では、「TCP対応」のトランスポートのために保持する必要があるプロパティのみを使用しています。分析とシミュレーションの両方で、この結果がリノ、キュービック、ウェストウッド[TSV84]に当てはまることを確認しました。これにより、ターゲットの形式が特にシンプルになります。許可されたスタンディングキューまたはターゲットセットポイントの理想的な範囲は、TCP接続のRTTの5％〜10％です。
We used simulation to explore the impact when TCPs are mixed with other traffic and with connections of different RTTs. Accordingly, we experimented extensively with values in the 5-10% of RTT range and, overall, used target values between 1 and 20 milliseconds for RTTs from 30 to 500 ms and link bandwidths of 64 Kbps to 100 Mbps to experimentally explore a value for the target that gives consistently high utilization while controlling delay across a range of bandwidths, RTTs, and traffic loads. Our results were notably consistent with the mathematics above.
シミュレーションを使用して、TCPが他のトラフィックやさまざまなRTTの接続と混在する場合の影響を調査しました。したがって、RTT範囲の5〜10％の値で広範囲に実験を行い、全体として、RTTの30〜500ミリ秒の1〜20ミリ秒のターゲット値と64 Kbps〜100 Mbpsのリンク帯域幅を使用して、帯域幅、RTT、およびトラフィック負荷の範囲全体で遅延を制御しながら、一貫して高い使用率を提供するターゲット。私たちの結果は特に上記の数学と一致していた。
A congested (but not overloaded) CoDel link with traffic composed solely or primarily of long-lived TCP flows will have a median delay through the link that will tend to the target. For bursty traffic loads and for overloaded conditions (where it is difficult or impossible for all the arriving flows to be accommodated), the median queues will be longer than the target.
混雑した（ただし過負荷ではない）CoDelリンクは、トラフィックが単独で、または主に長命のTCPフローで構成されている場合、リンクを通過する中央遅延が発生し、ターゲットに向かう傾向があります。バースト性のあるトラフィック負荷および過負荷状態（到着するすべてのフローに対応することが困難または不可能）の場合、キューの中央値はターゲットより長くなります。
The non-starvation drop inhibit feature dominates where the link rate becomes very small. By inhibiting drops when there is less than an (outbound link) MTU worth of bytes in the buffer, CoDel adapts to very low bandwidth links, as shown in [CODEL2012].
非枯渇ドロップ抑制機能は、リンクレートが非常に小さくなる場所を支配します。 [CODEL2012]に示すように、バッファ内に（アウトバウンドリンク）MTUに相当するバイト未満のバイトがある場合にドロップを禁止することにより、CoDelは非常に低い帯域幅のリンクに適応します。
Section 3.1 describes a simple, reliable way to measure "bad" (persistent) queue. Section 3.2 shows that TCP congestion control dynamics gives rise to a target setpoint for this measure that's a provably good balance between enhancing throughput and minimizing delay. Section 3.2 also shows that this target is a constant fraction of the same "largest average RTT" interval used to distinguish persistent from transient queue. The only remaining building block needed for a basic AQM is a "control loop" algorithm to effectively drive the queueing system from any "persistent queue above the target" state to a state where the persistent queue is below the target.
セクション3.1では、「不良」（永続的）キューを測定する簡単で信頼性の高い方法について説明します。セクション3.2は、TCPの輻輳制御のダイナミクスが、スループットの向上と遅延の最小化との間の適切なバランスであるこの測定の目標設定値を生み出すことを示しています。セクション3.2では、このターゲットが、永続キューと一時キューを区別するために使用される同じ「最大平均RTT」間隔の一定の割合であることも示しています。基本的なAQMに必要な残りの唯一のビルディングブロックは、「制御ループ」アルゴリズムであり、キューイングシステムを「ターゲットの上の永続的なキュー」状態から永続的なキューがターゲットの下の状態に効果的に駆動します。
Control theory provides a wealth of approaches to the design of control loops. Most of classical control theory deals with the control of linear, time-invariant, Single-Input-Single-Output (SISO) systems. Control loops for these systems generally come from a well-understood class known as Proportional-Integral-Derivative (PID) controllers. Unfortunately, a queue is not a linear system, and an AQM operates at the point of maximum non-linearity (where the output link bandwidth saturates, so increased demand creates delay rather than higher utilization). Output queues are also not time invariant since traffic is generally a mix of connections that start and stop at arbitrary times and that can have radically different behaviors ranging from "open-loop" UDP audio/video to "closed-loop" congestion-avoiding TCP. Finally, the constantly changing mix of connections (which can't be converted to a single "lumped parameter" model because of their transfer function differences) makes the system Multi-Input-Multi-Output (MIMO), not SISO.
制御理論は、制御ループの設計に豊富なアプローチを提供します。古典的な制御理論のほとんどは、線形の時間不変の単一入力単一出力（SISO）システムの制御を扱います。これらのシステムの制御ループは、一般に、Proportional-Integral-Derivative（PID）コントローラーとして知られているよく理解されたクラスから来ています。残念ながら、キューは線形システムではなく、AQMは最大の非線形性のポイントで動作します（出力リンクの帯域幅が飽和するため、需要が増えると使用率が高くなるのではなく遅延が発生します）。トラフィックは通常、任意の時間に開始および停止する接続の混合であり、「オープンループ」UDPオーディオ/ビデオから「クローズドループ」輻輳回避TCPに至るまで根本的に異なる動作をする可能性があるため、出力キューも時間不変ではありません。 。最後に、絶えず変化する接続の組み合わせ（伝達関数の違いのために単一の「集中パラメーター」モデルに変換できない）は、システムをSISOではなくMIMO（Multi-Input-Multi-Output）にします。
Since queueing systems match none of the prerequisites for a classical controller, a better approach is a modern state-space controller with "no persistent queue" and "has persistent queue" states. Since Internet traffic mixtures change rapidly and unpredictably, a noise- and error-tolerant adaptation algorithm like stochastic gradient is a good choice. Since there's essentially no information in the amount of persistent queue [TSV84], the adaptation should be driven by how long it has persisted.
キューシステムは従来のコントローラーの前提条件のどれにも一致しないため、より良いアプローチは、「永続キューなし」と「永続キューあり」の状態を持つ最新の状態空間コントローラーです。インターネットトラフィックの混合は急速に予測不能に変化するため、確率的勾配のようなノイズおよびエラー耐性のある適応アルゴリズムが適しています。永続キューの量[TSV84]には基本的に情報がないので、適応はそれがどれだけ長く存続しているかによって駆動されるべきです。
Consider the two extremes of traffic behavior: a single, open-loop UDP video stream and a single, long-lived TCP bulk data transfer. If the average bandwidth of the UDP video stream is greater than the bottleneck link rate, the link's queue will grow, and the controller will eventually enter "has persistent queue" state and start dropping packets. Since the video stream is open loop, its arrival rate is unaffected by drops, so the queue will persist until the average drop rate is greater than the output bandwidth deficit (= average arrival rate - average departure rate); the job of the adaptation algorithm is to discover this rate. For this example, the adaptation could consist of simply estimating the arrival and departure rates and then dropping at a rate slightly greater than their difference, but this class of algorithm won't work at all for the bulk data TCP stream. TCP runs in closed-loop flow balance [TSV84], so its arrival rate is almost always exactly equal to the departure rate -- the queue isn't the result of a rate imbalance but rather a mismatch between the TCP sender's window and the source-destination-source round-trip path capacity (i.e., the connection's bandwidth-delay product). The sender's TCP congestion avoidance algorithm will slowly increase the send window (one packet per round-trip time) [RFC5681], which will eventually cause the bottleneck to enter "has persistent queue" state. But, since the average input rate is the same as the average output rate, the rate deficit estimation that gave the correct drop rate for the video stream would compute a drop rate of zero for the TCP stream. However, if the output link drops one packet as it enters "has persistent queue" state, when the sender discovers this (via TCP's normal packet loss repair mechanisms), it will reduce its window by a factor of two [RFC5681]; so, one round-trip time after the drop, the persistent queue will go away.
トラフィックの動作の2つの極端を検討してください。単一の開ループUDPビデオストリームと、単一の長命のTCPバルクデータ転送です。 UDPビデオストリームの平均帯域幅がボトルネックリンクレートよりも大きい場合、リンクのキューが大きくなり、コントローラーは最終的に「永続キューを持っている」状態になり、パケットのドロップを開始します。ビデオストリームはオープンループであるため、その到着率はドロップの影響を受けないため、平均ドロップ率が出力帯域幅不足（=平均到着率-平均出発率）を超えるまでキューは存続します。適応アルゴリズムの仕事は、この速度を発見することです。この例では、適応は単に到着率と出発率を推定してから、それらの差よりもわずかに大きい速度で低下することで構成できますが、このクラスのアルゴリズムは、バルクデータTCPストリームに対してまったく機能しません。 TCPは閉ループフローバランス[TSV84]で実行されるため、その到着率はほぼ常に出発率と等しくなります。キューは、レートの不均衡の結果ではなく、TCP送信者のウィンドウとソースの間の不一致の結果です。 -destination-sourceラウンドトリップパス容量（つまり、接続の帯域幅遅延積）。送信者のTCP輻輳回避アルゴリズムは、送信ウィンドウ（往復時間ごとに1パケット）[RFC5681]をゆっくりと増加させ、最終的にボトルネックが「永続的なキューを持っている」状態になる原因となります。ただし、平均入力レートは平均出力レートと同じであるため、ビデオストリームに正しいドロップレートを与えるレート不足の見積もりでは、TCPストリームのドロップレートはゼロになります。ただし、「has persistent queue」状態に入るときに出力リンクが1つのパケットをドロップする場合、送信者がこれを（TCPの通常のパケット損失修復メカニズムを介して）検出すると、ウィンドウを2倍に縮小します[RFC5681]。そのため、ドロップ後の1回のラウンドトリップ時間で、永続キューはなくなります。
If there were N TCP conversations sharing the bottleneck, the controller would have to drop O(N) packets (one from each conversation) to make all the conversations reduce their window to get rid of the persistent queue. If the traffic mix consists of short (<= bandwidth-delay product) conversations, the aggregate behavior becomes more like the open-loop video example since each conversation is likely to have already sent all its packets by the time it learns about a drop so each drop has negligible effect on subsequent traffic.
ボトルネックを共有するN個のTCP会話がある場合、コントローラーはO（N）パケット（各会話から1つ）をドロップして、すべての会話がウィンドウを縮小して永続キューを取り除くようにする必要があります。トラフィックミックスが短い（<=帯域幅遅延製品）会話で構成されている場合、ドロップについて学習するまでに、各会話はすべてのパケットをすでに送信しているため、集約動作はオープンループビデオの例に近くなります。各ドロップは、後続のトラフィックにほとんど影響を与えません。
The controller does not know the number, duration, or kind of conversations creating its queue, so it has to learn the appropriate response. Since single drops can have a large effect if the degree of multiplexing (the number of active conversations) is small, dropping at too high a rate is likely to have a catastrophic effect on throughput. Dropping at a low rate (< 1 packet per round-trip time) and then increasing the drop rate slowly until the persistent queue goes below the target is unlikely to overdrop and is guaranteed to eventually dissipate the persistent queue. This stochastic gradient learning procedure is the core of CoDel's control loop (the gradient exists because a drop always reduces the (instantaneous) queue, so an increasing drop rate always moves the system "down" toward no persistent queue, regardless of traffic mix).
コントローラーは、キューを作成する会話の数、期間、または種類を認識していないため、適切な応答を学習する必要があります。多重化の程度（アクティブな会話の数）が小さい場合、シングルドロップは大きな影響を与える可能性があるため、あまりに高いレートでドロップすると、スループットに壊滅的な影響を与える可能性があります。低速でドロップし（往復時間あたり1パケット未満）、永続キューがターゲットを下回るまでゆっくりとドロップレートを上げても、オーバードロップする可能性は低く、最終的に永続キューが消散することが保証されています。この確率的勾配学習手順はCoDelの制御ループの中核です（勾配はドロップが常に（瞬間的）キューを減らすため、勾配が存在するため、ドロップレートが増加すると、トラフィックミックスに関係なく、常にシステムが永続キューに「ダウン」されます。
The "next drop time" is decreased in inverse proportion to the square root of the number of drops since the drop state was entered, using the well-known non-linear relationship of drop rate to throughput to get a linear change in throughput [REDL1998][MACTCP1997].
「次のドロップ時間」は、ドロップ状態に入ってからのドロップ数の平方根に反比例して減少し、ドロップ率とスループットの非線形関係を使用して、スループットの線形変化を取得します[REDL1998 ] [MACTCP1997]。
Since the best rate to start dropping is at slightly more than one packet per RTT, the controller's initial drop rate can be directly derived from the estimator's interval. When the minimum sojourn time first crosses the target and CoDel drops a packet, the earliest the controller could see the effect of the drop is the round-trip time (interval) + the local queue wait time (the target). If the next drop happens any earlier than this time (interval + target), CoDel will overdrop. In practice, the local queue waiting time tends to vary, so making the initial drop spacing (i.e., the time to the second drop) be exactly the minimum possible also leads to overdropping. Analysis of simulation and real-world measured data shows that the 75th percentile magnitude of this variation is less than the target, so the initial drop spacing SHOULD be set to the estimator's interval (i.e., initial drop spacing = interval) to ensure that the controller has accounted for acceptable congestion delays.
ドロップを開始するのに最適なレートはRTTごとに1パケットをわずかに超えるため、コントローラーの初期ドロップレートは、推定器の間隔から直接導出できます。最小滞在時間が最初にターゲットを通過し、CoDelがパケットをドロップするとき、コントローラーがドロップの影響を確認できる最も早いのは、往復時間（間隔）+ローカルキュー待機時間（ターゲット）です。次のドロップがこの時間より前に発生した場合（間隔+ターゲット）、CoDelはオーバードロップします。実際には、ローカルキューの待機時間は変動する傾向があるため、最初のドロップ間隔（つまり、2番目のドロップまでの時間）を可能な限り最小にすると、オーバードロップも発生します。シミュレーションと実際の測定データの分析は、この変動の75パーセンタイルの大きさが目標よりも小さいことを示しているため、コントローラーが確実に実行されるように、初期の液滴間隔は推定器の間隔（つまり、初期の液滴間隔=間隔）に設定する必要があります（SHOULD）。許容可能な輻輳遅延を考慮しました。
Use of the minimum statistic lets the controller be placed in the dequeue routine with the estimator. This means that the control signal (the drop) can be sent at the first sign of "bad" queue (as indicated by the sojourn time) and that the controller can stop acting as soon as the sojourn time falls below the target. Dropping at dequeue has both implementation and control advantages.
最小統計を使用すると、コントローラーを推定器を使用してデキュールーチンに配置できます。これは、制御信号（ドロップ）が（滞留時間で示される）「不良」キューの最初のサインで送信され、滞留時間が目標を下回るとすぐにコントローラーが動作を停止できることを意味します。デキュー時のドロップには、実装と制御の両方の利点があります。
CoDel was initially designed as a bufferbloat solution for the consumer network edge. The CoDel building blocks are able to adapt to different or time-varying link rates, be easily used with multiple queues, have excellent utilization with low delay, and have a simple and efficient implementation.
CoDelは当初、コンシューマネットワークエッジ用のバッファブロートソリューションとして設計されました。 CoDelビルディングブロックは、異なるリンクレートまたは時変リンクレートに適応でき、複数のキューで簡単に使用でき、低遅延で優れた使用率を実現し、シンプルで効率的な実装を実現します。
The CoDel algorithm described in the rest of this document uses two key variables: TARGET, which is the controller's target setpoint described in Section 3.2, and INTERVAL, which is the estimator's interval described in Section 3.3.
このドキュメントの残りの部分で説明するCoDelアルゴリズムは、2つの主要な変数を使用します。TARGET（セクション3.2で説明するコントローラーのターゲットセットポイント）とINTERVAL（セクション3.3で説明する推定器の間隔）です。
The only setting CoDel requires is the INTERVAL value, and as 100 ms satisfies that definition for normal Internet usage, CoDel can be parameter-free for consumer use. To ensure that link utilization is not adversely affected, CoDel's estimator sets TARGET to one that optimizes power. CoDel's controller does not drop packets when the drop would leave the queue empty or with fewer than a Maximum Transmission Unit (MTU) worth of bytes in the buffer. Section 3.2 shows that an ideal TARGET is 5-10% of the connection round-trip time (RTT). In the open terrestrial-based Internet, especially at the consumer edge, we expect most unbloated RTTs to have a ceiling of 100 ms [CHARB2007]. Using this RTT gives a minimum TARGET of 5 ms and INTERVAL of 100 ms. In practice, uncongested links will see sojourn times below TARGET more often than once per RTT, so the estimator is not overly sensitive to the value of INTERVAL.
CoDelが必要とする唯一の設定はINTERVAL値であり、通常のインターネット使用では100 msがその定義を満たしているため、コンシューマー向けにCoDelをパラメーターなしで使用できます。リンクの使用率が悪影響を受けないようにするために、CoDelの推定器はTARGETを電力を最適化するものに設定します。 CoDelのコントローラーは、ドロップによってキューが空のままになるか、バッファー内のバイト数が最大伝送ユニット（MTU）に満たない場合、パケットをドロップしません。セクション3.2は、理想的なターゲットが接続の往復時間（RTT）の5〜10％であることを示しています。オープンな地上ベースのインターネット、特にコンシューマーエッジでは、ほとんどの肥大していないRTTの上限は100ミリ秒であると予想されます[CHARB2007]。このRTTを使用すると、最小ターゲットは5ミリ秒、間隔は100ミリ秒になります。実際には、輻輳していないリンクでは、RTTごとに1回よりも頻繁にTARGETを下回る滞留時間が発生するため、推定量はINTERVALの値に過度に敏感ではありません。
When the estimator finds a persistent delay above TARGET, the controller enters the drop state where a packet is dropped, and the next drop time is set. As discussed in Section 3.3, the initial next drop spacing is intended to be long enough to give the endpoints time to react to the single drop and therefore SHOULD be set to a value equal to INTERVAL. If the estimator's output falls below TARGET, the controller cancels the next drop and exits the drop state. (The controller is more sensitive than the estimator to an overly short INTERVAL value, since an unnecessary drop would occur and lower link utilization). If the next drop time is reached while the controller is still in drop state, the packet being dequeued is dropped, and the next drop time is recalculated.
EstimatorがTARGETを超える持続的な遅延を検出すると、コントローラーはドロップ状態に入り、パケットがドロップされ、次のドロップ時間が設定されます。セクション3.3で説明したように、最初の次のドロップ間隔は、単一のドロップに反応する時間をエンドポイントに与えるのに十分な長さを意図しているため、INTERVALに等しい値に設定する必要があります。推定器の出力がTARGETを下回ると、コントローラーは次のドロップをキャンセルし、ドロップ状態を終了します。 （コントローラーは、不必要なドロップが発生してリンク使用率が低下するため、極端に短いINTERVAL値に対して推定器よりも敏感です）。コントローラがまだドロップ状態である間に次のドロップ時間に達すると、デキューされるパケットがドロップされ、次のドロップ時間が再計算されます。
Additional logic prevents re-entering the drop state too soon after exiting it and resumes the drop state at a recent control level, if one exists. This logic is described more precisely in the pseudocode below. Additional work is required to determine the frequency and importance of re-entering the drop state.
追加のロジックにより、終了後すぐにドロップ状態に再び入ることが防止され、ドロップ状態が最近の制御レベル（存在する場合）で再開されます。このロジックは、以下の疑似コードでより正確に説明されています。ドロップ状態に戻る頻度と重要性を判断するには、追加の作業が必要です。
Note that CoDel AQM only enters its drop state when the local minimum sojourn delay has exceeded TARGET for a time period long enough for normal bursts to dissipate, ensuring that a burst of packets that fits in the pipe will not be dropped.
CoDel AQMがドロップ状態になるのは、ローカルの最小滞留遅延がTARGETを超えたときに、通常のバーストが消散するのに十分な時間だけであり、パイプに収まるパケットのバーストが確実にドロップされないことに注意してください。
CoDel's goals are to control delay with little or no impact on link utilization and to be deployed on a wide range of link bandwidths, including variable-rate links, without reconfiguration. To keep from making drops when it would starve the output link, CoDel makes another check before dropping to see if at least an MTU worth of bytes remains in the buffer. If not, the packet SHOULD NOT be dropped; therefore, CoDel exits the drop state. The MTU size can be set adaptively to the largest packet seen so far or can be read from the interface driver.
CoDelの目標は、リンク使用率にほとんどまたはまったく影響を与えずに遅延を制御し、再構成することなく、可変レートリンクを含む幅広いリンク帯域幅に展開することです。出力リンクが不足する場合にドロップを行わないようにするために、CoDelはドロップする前に別のチェックを行い、少なくともMTU相当のバイトがバッファーに残っているかどうかを確認します。そうでない場合、パケットはドロップされるべきではない（SHOULD NOT）。したがって、CoDelはドロップ状態を終了します。 MTUサイズは、これまでに見られた最大のパケットに適応的に設定するか、インターフェイスドライバーから読み取ることができます。
The INTERVAL value is chosen to give endpoints time to react to a drop without being so long that response times suffer. CoDel's estimator, TARGET, and control loop all use INTERVAL. Understanding their derivation shows that CoDel is the most sensitive to the value of INTERVAL for single long-lived TCPs with a decreased sensitivity for traffic mixes. This is fortunate, as RTTs vary across connections and are not known a priori. The best policy seems to be to use an INTERVAL value slightly larger than the RTT seen by most of the connections using a link, a value that can be determined as the largest RTT seen if the value is not an outlier (use of a 95-99th percentile value should work). In practice, this value is not known or measured (however, see Appendix A for an application where INTERVAL is measured). An INTERVAL setting of 100 ms works well across a range of RTTs from 10 ms to 1 second (excellent performance is achieved in the range from 10 ms to 300 ms). For devices intended for the normal terrestrial Internet, INTERVAL SHOULD have a value of 100 ms. This will only cause overdropping where a long-lived TCP has an RTT longer than 100 ms and there is little or no mixing with other connections through the link.
INTERVAL値は、応答時間が低下するほど長くなくてもドロップに反応する時間をエンドポイントに与えるように選択されます。 CoDelの推定器、TARGET、および制御ループはすべてINTERVALを使用します。それらの派生を理解すると、CoDelが単一の長期TCPのINTERVALの値に最も敏感であり、トラフィックミックスの感度が低下することがわかります。 RTTは接続によって異なり、アプリオリに知られていないため、これは幸運です。最良のポリシーは、リンクを使用するほとんどの接続で見られるRTTよりも少し大きいINTERVAL値を使用することです。この値は、値が外れ値でない場合に見られる最大のRTTと判断できます（95- 99パーセンタイル値が機能するはずです）。実際には、この値は不明または測定されていません（ただし、INTERVALが測定されるアプリケーションについては、付録Aを参照してください）。 100ミリ秒の間隔設定は、10ミリ秒から1秒までのRTTの範囲で適切に機能します（優れたパフォーマンスは、10ミリ秒から300ミリ秒の範囲で達成されます）。通常の地上インターネット用のデバイスの場合、INTERVAL SHOULDの値は100ミリ秒です。これにより、存続期間の長いTCPのRTTが100ミリ秒を超え、リンクを介した他の接続との混合がほとんどないかまったくない場合にのみ、オーバードロップが発生します。
TARGET is the maximum acceptable persistent queue delay above which CoDel is dropping or preparing to drop and below which CoDel will not drop. TARGET SHOULD be set to 5 ms for normal Internet traffic.
TARGETは、CoDelがドロップまたはドロップの準備をしている状態で、CoDelがドロップしない最大許容永続キュー遅延です。 TARGETは、通常のインターネットトラフィックでは5ミリ秒に設定する必要があります。
The calculations of Section 3.2 show that the best TARGET value is 5-10% of the RTT, with the low end of 5% preferred. Extensive simulations exploring the impact of different TARGET values when used with mixed traffic flows with different RTTs and different bandwidths show that below a TARGET of 5 ms, utilization suffers for some conditions and traffic loads; above 5 ms showed very little or no improvement in utilization.
セクション3.2の計算では、最適なTARGET値はRTTの5〜10％であり、5％の下限が推奨されています。さまざまなRTTとさまざまな帯域幅を持つ混合トラフィックフローで使用した場合のさまざまなTARGET値の影響を調査する広範なシミュレーションでは、5 msのTARGET未満では、一部の条件とトラフィック負荷で使用率が低下することが示されています。 5ミリ秒を超えると、使用率の改善はほとんど、またはまったくありませんでした。
Sojourn times must remain above the TARGET for INTERVAL amount of time in order to enter the drop state. Any packet with a sojourn time less than TARGET will reset the time that the queue was last below TARGET. Since Internet traffic has very dynamic characteristics, the actual sojourn delay experienced by packets varies greatly and is often less than TARGET unless the overload is excessive. When a link is not overloaded, it is not a bottleneck, and packet sojourn times will be small or nonexistent. In the usual case, there are only one or two places along a path where packets will encounter a bottleneck (usually at the edge), so the total amount of queueing delay experienced by a packet should be less than 10 ms even under extremely congested conditions. This net delay is substantially lower than common current queueing delays on the Internet that grow to orders of seconds [NETAL2010] [CHARB2007].
ドロップ状態に入るには、滞在時間はTARGETをINTERVAL時間の間上回っている必要があります。滞在時間がTARGET未満のパケットは、キューが最後にTARGETを下回っていた時間をリセットします。インターネットトラフィックには非常に動的な特性があるため、パケットが経験する実際の滞留遅延は大きく異なり、過負荷が過剰でない限り、TARGETよりも小さいことがよくあります。リンクが過負荷でない場合、それはボトルネックではなく、パケットの滞留時間は短いか、存在しません。通常の場合、パスに沿ってパケットがボトルネック（通常はエッジ）に遭遇する場所は1つか2つしかないため、非常に混雑した状況でも、パケットが経験するキューイング遅延の合計量は10ミリ秒未満である必要があります。 。この正味の遅延は、インターネット上の一般的な現在のキューイング遅延よりも大幅に低く、数秒にまで増加します[NETAL2010] [CHARB2007]。
Regarding the roles of TARGET and the minimum-tracking INTERVAL, note that TARGET SHOULD NOT be increased in response to lower layers that have a bursty nature, where packets are transmitted for short periods interspersed with idle periods where the link is waiting for permission to send. CoDel's estimator will "see" the effective transmission rate over an INTERVAL amount of time, and increasing TARGET only leads to longer queue delays. On the other hand, where a significant additional delay is added to the intrinsic RTT of most or all packets due to the waiting time for a transmission, it is necessary to increase INTERVAL by that extra delay. TARGET SHOULD NOT be adjusted for such short-term bursts, but INTERVAL MAY need to be adjusted if the path's intrinsic RTT changes.
TARGETの役割と最小追跡間隔については、バースト性のある下位層に応じてTARGETを増やしてはいけないことに注意してください。この場合、パケットは、送信の許可を待っているアイドル期間が散在する短い期間送信されます。 。 CoDelの推定器は、時間間隔での有効な伝送速度を「認識」し、TARGETを増やすと、キューの遅延が長くなるだけです。一方、送信の待機時間のために、ほとんどまたはすべてのパケットの固有のRTTに大幅な追加の遅延が追加される場合、その追加の遅延によってINTERVALを増やす必要があります。 TARGETは、このような短期間のバーストに対して調整すべきではありませんが、パスの固有のRTTが変更された場合、間隔を調整する必要があります（MAY）。
CoDel is easily adapted to multiple queue systems. With other approaches, there is always a question of how to account for the fact that each queue receives less than the full link rate over time and usually sees a varying rate over time. This is what CoDel excels at: using a packet's sojourn time in the buffer completely circumvents this problem. In a multiple-queue setting, a separate CoDel algorithm runs on each queue, but each CoDel instance uses the packet sojourn time the same way a single-queue CoDel does. Just as a single-queue CoDel adapts to changing link bandwidths [CODEL2012], so does a multiple-queue CoDel system. As an optimization to avoid queueing more than necessary, when testing for queue occupancy before dropping, the total occupancy of all queues sharing the same output link SHOULD be used. This property of CoDel has been exploited in fq_codel [RFC8290], which hashes on the packet header fields to determine a specific bin, or sub-queue, for the packet and runs CoDel on each bin or sub-queue, thus creating a well-mixed output flow and obviating issues of reverse path flows (including "ack compression").
CoDelは、複数のキューシステムに簡単に適応できます。他のアプローチでは、各キューが時間の経過とともにフルリンクレートよりも少ないレートを受け取り、通常、時間の経過とともに変化するレートが表示されるという事実をどのように説明するかという問題が常にあります。これは、CoDelが得意とするところです。パケットの滞留時間をバッファで使用することで、この問題を完全に回避できます。複数キュー設定では、各キューで個別のCoDelアルゴリズムが実行されますが、各CoDelインスタンスは、単一キューCoDelと同じ方法でパケット滞在時間を使用します。シングルキューCoDelがリンク帯域幅の変化に対応するように[CODEL2012]、マルチキューCoDelシステムも同様です。必要以上にキューイングを回避するための最適化として、ドロップする前にキュー占有率をテストする場合、同じ出力リンクを共有するすべてのキューの占有率の合計を使用する必要があります（SHOULD）。 CoDelのこのプロパティは、fq_codel [RFC8290]で悪用され、パケットヘッダーフィールドをハッシュしてパケットの特定のビンまたはサブキューを決定し、各ビンまたはサブキューでCoDelを実行して、混合出力フローおよびリバースパスフロー（「ack圧縮」を含む）の未然の問題。
CoDel is set for use in devices in the open Internet. An INTERVAL setting of 100 ms is used, TARGET is set to 5% of INTERVAL, and the initial drop spacing is also set to the INTERVAL. These settings have been chosen so that a device, such as a small WiFi router, can be sold without the need for any values to be made adjustable, yielding a parameterless implementation. In addition, CoDel is useful in environments with significantly different characteristics from the normal Internet, for example, in switches used as a cluster interconnect within a data center. Since cluster traffic is entirely internal to the data center, round-trip latencies are low (typically <100 us) but bandwidths are high (1-40 Gbps), so it's relatively easy for the aggregation phase of a distributed computation (e.g., the Reduce part of a Map/Reduce) to persistently fill and then overflow the modest per-port buffering available in most high-speed switches. A CoDel configured for this environment (TARGET and INTERVAL in the microsecond rather than millisecond range) can minimize drops or Explicit Congestion Notification (ECN) marks while keeping throughput high and latency low.
CoDelは、オープンインターネットのデバイスで使用するように設定されています。 100 msの間隔設定が使用され、TARGETは間隔の5％に設定され、初期のドロップ間隔も間隔に設定されます。これらの設定は、小さなWiFiルーターなどのデバイスを、値を調整する必要なく販売できるように選択されているため、パラメーターなしの実装が可能です。さらに、CoDelは、データセンター内のクラスター相互接続として使用されるスイッチなど、通常のインターネットとは大きく異なる特性を持つ環境で役立ちます。クラスタートラフィックは完全にデータセンターの内部にあるため、往復のレイテンシは低く（通常<100 us）、帯域幅は高い（1〜40 Gbps）ため、分散計算の集約フェーズ（たとえば、 Map / Reduceの一部を減らして、ほとんどの高速スイッチで利用できる適度なポートごとのバッファリングを永続的に埋めてオーバーフローさせます。この環境用に構成されたCoDel（ミリ秒単位ではなくマイクロ秒単位のTARGETおよびINTERVAL）は、スループットを高く、レイテンシを低く保ちながら、ドロップまたは明示的輻輳通知（ECN）マークを最小化できます。
Devices destined for these environments MAY use a different value for INTERVAL, where suitable. If appropriate analysis indicates, the TARGET MAY be set to some other value in the 5-10% of INTERVAL, and the initial drop spacing MAY be set to a value of 1.0 to 1.2 times INTERVAL. But these settings will cause problems, such as overdropping and low throughput, if used on the open Internet, so devices that allow CoDel to be configured SHOULD default to the Internet-appropriate values given in this document.
これらの環境を宛先とするデバイスは、必要に応じて、INTERVALに異なる値を使用できます。適切な分析で示された場合、TARGETは間隔の5〜10％で他の値に設定される場合があり、初期のドロップ間隔は間隔の1.0〜1.2倍の値に設定される場合があります。ただし、これらの設定は、オープンインターネットで使用すると、オーバードロップや低スループットなどの問題を引き起こすため、CoDelを構成できるデバイスは、このドキュメントに記載されているインターネットに適した値にデフォルトで設定する必要があります（SHOULD）。
What follows is the CoDel algorithm in C++-like pseudocode. Since CoDel adds relatively little new code to a basic tail-drop FIFO queue, we have attempted to highlight just these additions by presenting CoDel as a sub-class of a basic FIFO queue base class. The reference code is included to aid implementers who wish to apply CoDel to queue management as described here or to adapt its principles to other applications.
以下は、C ++に似た擬似コードのCoDelアルゴリズムです。 CoDelは基本的なテールドロップFIFOキューに比較的新しいコードをほとんど追加しないので、基本的なFIFOキューの基本クラスのサブクラスとしてCoDelを表示することで、これらの追加だけを強調しようとしました。参照コードは、ここで説明するようにCoDelをキュー管理に適用したり、その原理を他のアプリケーションに適用したりする実装者を支援するために含まれています。
Implementors are strongly encouraged to also look at the Linux kernel version of CoDel -- a well-written, well-tested, real-world, C-based implementation. As of this writing, it is available at https://github.com/torvalds/linux/blob/master/net/sched/sch_codel.c.
実装者は、CoDelのLinuxカーネルバージョンも確認することを強くお勧めします。これは、よく記述され、十分にテストされた、実際のCベースの実装です。これを書いている時点では、https：//github.com/torvalds/linux/blob/master/net/sched/sch_codel.cから入手できます。
time_t is an integer time value in units convenient for the system. The code presented here uses 0 as a flag value to indicate "no time set."
time_tは、システムに便利な単位での整数の時間値です。ここに示されているコードは、「時間設定なし」を示すフラグ値として0を使用しています。
packet_t* is a pointer to a packet descriptor. We assume it has a tstamp field capable of holding a time_t and that the field is available for use by CoDel (it will be set by the enqueue routine and used by the dequeue routine).
packet_t *は、パケット記述子へのポインタです。 time_tを保持できるtstampフィールドがあり、そのフィールドがCoDelで使用できると想定します（エンキュールーチンによって設定され、デキュールーチンによって使用されます）。
queue_t is a base class for queue objects (the parent class for codel_queue_t objects). We assume it has enqueue() and dequeue() methods that can be implemented in child classes. We assume it has a bytes() method that returns the current queue size in bytes. This can be an approximate value. The method is invoked in the dequeue() method but shouldn't require a lock with the enqueue() method.
queue_tは、キューオブジェクトの基本クラスです（codel_queue_tオブジェクトの親クラス）。子クラスに実装できるenqueue()およびdequeue()メソッドがあると想定します。現在のキューサイズをバイト単位で返すbytes()メソッドがあると想定します。これは概算値である場合があります。このメソッドはdequeue()メソッドで呼び出されますが、enqueue()メソッドでロックする必要はありません。
flag_t is a Boolean.
flag_tはブール値です。
time_t first_above_time_ = 0; // Time to declare sojourn time above
// TARGET
time_t drop_next_ = 0; // Time to drop next packet
uint32_t count_ = 0; // Packets dropped in drop state
uint32_t lastcount_ = 0; // Count from previous iteration
flag_t dropping_ = false; // Set to true if in drop state
time_t TARGET = MS2TIME(5); // 5 ms TARGET queue delay
time_t INTERVAL = MS2TIME(100); // 100 ms sliding-minimum window
u_int maxpacket = 512; // Maximum packet size in bytes
// (SHOULD use interface MTU)
All the work of CoDel is done in the dequeue routine. The only CoDel addition to enqueue is putting the current time in the packet's tstamp field so that the dequeue routine can compute the packet's sojourn time. Note that packets arriving at a full buffer will be dropped, but these drops are not counted towards CoDel's computations.
CoDelのすべての作業は、デキュールーチンで行われます。エンキューへのCoDelの追加は、デキュールーチンがパケットの滞在時間を計算できるように、パケットのtstampフィールドに現在の時間を入力することだけです。満杯のバッファーに到着したパケットはドロップされますが、これらのドロップはCoDelの計算にカウントされないことに注意してください。
void codel_queue_t::enqueue(packet_t* pkt)
{
pkt->tstamp = clock();
queue_t::enqueue(pkt);
}
This is the heart of CoDel. There are two branches based on whether the controller is in drop state: (i) if the controller is in drop state (that is, the minimum packet sojourn time is greater than TARGET), then the controller checks if it is time to leave drop state or schedules the next drop(s); or (ii) if the controller is not in drop state, it determines if it should enter drop state and do the initial drop.
これがCoDelの心臓部です。コントローラーがドロップ状態にあるかどうかに基づいて、2つのブランチがあります。（i）コントローラーがドロップ状態にある（つまり、最小パケット滞留時間がTARGETよりも大きい）場合、コントローラーは、ドロップを残す時間かどうかを確認します。次のドロップを状態またはスケジュールします。または（ii）コントローラーがドロップ状態でない場合は、コントローラーがドロップ状態に入り、最初のドロップを行うかどうかを決定します。
packet_t* CoDelQueue::dequeue()
{
time_t now = clock();
dodequeue_result r = dodequeue(now);
uint32_t delta;
if (dropping_) {
if (! r.ok_to_drop) {
// sojourn time below TARGET - leave drop state
dropping_ = false;
}
// Time for the next drop. Drop current packet and dequeue
// next. If the dequeue doesn't take us out of dropping
// state, schedule the next drop. A large backlog might
// result in drop rates so high that the next drop should
// happen now, hence the 'while' loop.
while (now >= drop_next_ && dropping_) {
drop(r.p);
++count_;
r = dodequeue(now);
if (! r.ok_to_drop) {
// leave drop state
dropping_ = false;
} else {
// schedule the next drop.
drop_next_ = control_law(drop_next_, count_);
}
}
// If we get here, we're not in drop state. The 'ok_to_drop'
// return from dodequeue means that the sojourn time has been
// above 'TARGET' for 'INTERVAL', so enter drop state.
} else if (r.ok_to_drop) {
drop(r.p);
r = dodequeue(now);
dropping_ = true;
// If min went above TARGET close to when it last went
// below, assume that the drop rate that controlled the
// queue on the last cycle is a good starting point to
// control it now. ('drop_next' will be at most 'INTERVAL'
// later than the time of the last drop, so 'now - drop_next'
// is a good approximation of the time from the last drop
// until now.) Implementations vary slightly here; this is
// the Linux version, which is more widely deployed and
// tested.
delta = count_ - lastcount_;
count_ = 1;
if ((delta > 1) && (now - drop_next_ < 16*INTERVAL))
count_ = delta;
drop_next_ = control_law(now, count_);
lastcount_ = count_;
}
return (r.p);
}
Since the degree of multiplexing and nature of the traffic sources is unknown, CoDel acts as a closed-loop servo system that gradually increases the frequency of dropping until the queue is controlled (sojourn time goes below TARGET). This is the control law that governs the servo. It has this form because of the sqrt(p) dependence of TCP throughput on drop probability. Note that for embedded systems or kernel implementation, the inverse sqrt can be computed efficiently using only integer multiplication.
多重化の程度とトラフィックソースの性質は不明であるため、CoDelはクローズドループサーボシステムとして機能し、キューが制御されるまで（滞留時間がTARGETを下回るまで）ドロップの頻度を徐々に増やします。これは、サーボを制御する制御法則です。ドロップ確率に対するTCPスループットのsqrt（p）依存性のため、この形式になります。組み込みシステムまたはカーネルの実装では、整数の乗算のみを使用して逆sqrtを効率的に計算できることに注意してください。
time_t codel_queue_t::control_law(time_t t, uint32_t count)
{
return t + INTERVAL / sqrt(count);
}
Next is a helper routine that does the actual packet dequeue and
tracks whether the sojourn time is above or below TARGET and, if
above, if it has remained above continuously for at least INTERVAL
amount of time. It returns two values: a Boolean indicating if it is
OK to drop (sojourn time above TARGET for at least INTERVAL) and the
packet dequeued.
typedef struct {
packet_t* p;
flag_t ok_to_drop;
} dodequeue_result;
dodequeue_result codel_queue_t::dodequeue(time_t now)
{
dodequeue_result r = { queue_t::dequeue(), false };
if (r.p == NULL) {
// queue is empty - we can't be above TARGET
first_above_time_ = 0;
return r;
}
// To span a large range of bandwidths, CoDel runs two
// different AQMs in parallel. One is based on sojourn time
// and takes effect when the time to send an MTU-sized
// packet is less than TARGET. The 1st term of the "if"
// below does this. The other is based on backlog and takes
// effect when the time to send an MTU-sized packet is >=
// TARGET. The goal here is to keep the output link
// utilization high by never allowing the queue to get
// smaller than the amount that arrives in a typical
// interarrival time (MTU-sized packets arriving spaced
// by the amount of time it takes to send such a packet on
// the bottleneck). The 2nd term of the "if" does this.
time_t sojourn_time = now - r.p->tstamp;
if (sojourn_time_ < TARGET || bytes() <= maxpacket_) {
// went below - stay below for at least INTERVAL
first_above_time_ = 0;
} else {
if (first_above_time_ == 0) {
// just went above from below. if still above at
// first_above_time, will say it's ok to drop.
first_above_time_ = now + INTERVAL;
} else if (now >= first_above_time_) {
r.ok_to_drop = true;
}
}
return r;
}
time_t is an integer time value in units convenient for the system. Resolution to at least a millisecond is required, and better resolution is useful up to the minimum possible packet time on the output link; 64- or 32-bit widths are acceptable but with 32 bits the resolution should be no finer than 2^{-16} to leave enough dynamic range to represent a wide range of queue waiting times. Narrower widths also have implementation issues due to overflow (wrapping) and underflow (limit cycles because of truncation to zero) that are not addressed in this pseudocode.
time_tは、システムに便利な単位での整数の時間値です。少なくとも1ミリ秒までの解像度が必要であり、より良い解像度は、出力リンクで可能な最小のパケット時間まで有効です。 64ビットまたは32ビットの幅を使用できますが、32ビットでは、解像度を2 ^ {-16}より細かくしないでください。広い範囲のキュー待機時間を表すのに十分なダイナミックレンジを残すことができます。幅を狭くすると、オーバーフロー（ラッピング）およびアンダーフロー（ゼロへの切り捨てによる制限サイクル）が原因で、この疑似コードで対処されない実装の問題も発生します。
Since CoDel requires relatively little per-queue state and no direct communication or state sharing between the enqueue and dequeue routines, it is relatively simple to add CoDel to almost any packet processing pipeline, including forwarding engines based on Application-Specific Integrated Circuits (ASICs) or Network Processors (NPUs). One issue to consider is dodequeue()'s use of a 'bytes()' function to determine the current queue size in bytes. This value does not need to be exact. If the enqueue part of the pipeline keeps a running count of the total number of bytes it has put into the queue, and the dequeue routine keeps a running count of the total bytes it has removed from the queue, 'bytes()' is simply the difference between these two counters (32-bit counters should be adequate). Enqueue has to update its counter once per packet queued, but it does not matter when (before, during, or after the packet has been added to the queue). The worst that can happen is a slight, transient underestimate of the queue size, which might cause a drop to be briefly deferred.
CoDelは比較的キューごとの状態を必要とせず、エンキュールーチンとデキュールーチン間の直接通信や状態共有を必要としないため、アプリケーション固有の集積回路（ASIC）に基づく転送エンジンを含むほとんどすべてのパケット処理パイプラインにCoDelを追加することは比較的簡単ですまたはネットワークプロセッサ（NPU）。考慮すべき1つの問題は、現在のキューサイズをバイト単位で決定するためにdodequeue()が「bytes()」関数を使用することです。この値は正確である必要はありません。パイプラインのエンキュー部分がキューに入れた合計バイト数の実行カウントを保持し、デキュールーチンがキューから削除した合計バイト数の実行カウントを保持する場合、 'bytes()'は単にこれら2つのカウンターの違い（32ビットカウンターで十分です）。エンキューは、キューに入れられたパケットごとに1回カウンターを更新する必要がありますが、いつ（パケットがキューに追加される前、最中、または後に）重要ではありません。発生する可能性がある最悪の事態は、キューのサイズが一時的にわずかに過小評価されるため、ドロップが一時的に遅延する可能性があります。
We encourage experimentation with the recommended values of TARGET and INTERVAL for Internet settings. CoDel provides general, efficient, parameterless building blocks for queue management that can be applied to single or multiple queues in a variety of data networking scenarios. CoDel's settings may be modified for other special-purpose networking applications.
インターネット設定のTARGETおよびINTERVALの推奨値を試してみることをお勧めします。 CoDelは、さまざまなデータネットワーキングシナリオで単一または複数のキューに適用できるキュー管理用の一般的で効率的なパラメーターなしのビルディングブロックを提供します。 CoDelの設定は、他の専用ネットワークアプリケーション用に変更される場合があります。
This document describes an active queue management algorithm for implementation in networked devices. There are no known security exposures associated with CoDel at this time.
このドキュメントでは、ネットワークデバイスに実装するためのアクティブキュー管理アルゴリズムについて説明します。現時点では、CoDelに関連する既知の機密漏れはありません。
This document does not require actions by IANA.
このドキュメントでは、IANAによるアクションは必要ありません。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.
[RFC2119] Bradner、S。、「要件レベルを示すためにRFCで使用するキーワード」、BCP 14、RFC 2119、DOI 10.17487 / RFC2119、1997年3月、<https://www.rfc-editor.org/info/ rfc2119>。
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8174] Leiba、B。、「RFC 2119キーワードの大文字と小文字のあいまいさ」、BCP 14、RFC 8174、DOI 10.17487 / RFC8174、2017年5月、<https://www.rfc-editor.org/info/ rfc8174>。
[BLOAT] Gettys, J. and K. Nichols, "Bufferbloat: Dark Buffers in the Internet", Communications of the ACM, Volume 55, Issue 1, DOI 10.1145/2063176.2063196, January 2012.
[BLOAT] Gettys、J。およびK. Nichols、「Bufferbloat：Dark Buffers in the Internet」、Communications of the ACM、Volume 55、Issue 1、DOI 10.1145 / 2063176.2063196、2012年1月。
[CHARB2007] Dischinger, M., Haeberlen, A., Gummadi, K., and S. Saroiu, "Characterizing Residential Broadband Networks", Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, DOI 10.1145/1298306.1298313, October 2007.
[CHARB2007] Dischinger、M.、Haeberlen、A.、Gummadi、K。、およびS. Saroiu、「Charactizingizing Residential Broadband Networks」、Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement、DOI 10.1145 / 1298306.1298313、2007年10月。
[CODEL2012] Nichols, K. and V. Jacobson, "Controlling Queue Delay", ACM Queue, Volume 10, Issue 5, DOI 10.1145/2208917.2209336, May 2012.
[CODEL2012] Nichols、K。およびV. Jacobson、「Controlling Queue Delay」、ACM Queue、Volume 10、Issue 5、DOI 10.1145 / 2208917.2209336、2012年5月。
[KLEIN81] Kleinrock, L. and R. Gail, "An Invariant Property of Computer Network Power", Proceedings of the International Conference on Communications, June 1981, <http://www.lk.cs.ucla.edu/data/files/Gail/power.pdf>.
[KLEIN81]クラインロックL.およびR.ゲイル、「コンピュータネットワークパワーの不変の特性」、1981年6月の国際通信会議の議事録、<http://www.lk.cs.ucla.edu/data/ files / Gail / power.pdf>。
[MACTCP1997] Mathis, M., Semke, J., Mahdavi, J., and T. Ott, "The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm", ACM SIGCOMM Computer Communications Review, Volume 27, Issue 3, pp. 67-82, DOI 10.1145/263932.264023, July 1997.
[MACTCP1997] Mathis、M.、Semke、J.、Madhavi、J。、およびT. Ott、「TCP輻輳回避アルゴリズムの巨視的な動作」、ACM SIGCOMM Computer Communications Review、Volume 27、Issue 3、67ページ-82、DOI 10.1145 / 263932.264023、1997年7月。
[NETAL2010] Kreibich, C., Weaver, N., Paxson, V., and B. Nechaev, "Netalyzr: Illuminating the Edge Network", Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, DOI 10.1145/1879141.1879173, November 2010.
[NETAL2010] Kreibich、C.、Weaver、N.、Paxson、V。、およびB. Nechaev、「Netalyzr：Illuminating the Edge Network」、Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement、DOI 10.1145 / 1879141.1879173、2010年11月。
[REDL1998] Nichols, K., Jacobson, V., and K. Poduri, "RED in a Different Light", Technical Report, Cisco Systems, September 1999, <http://citeseerx.ist.psu.edu/viewdoc/ summary?doi=10.1.1.22.9406>.
[REDL1998] Nichols、K.、Jacobson、V。、およびK. Poduri、「RED in a Different Light」、テクニカルレポート、Cisco Systems、1999年9月、<http://citeseerx.ist.psu.edu/viewdoc/ summary？doi = 10.1.1.22.9406>。
[RFC896] Nagle, J., "Congestion Control in IP/TCP Internetworks", RFC 896, DOI 10.17487/RFC0896, January 1984, <https://www.rfc-editor.org/info/rfc896>.
[RFC896] Nagle、J。、「IP / TCP Internetworksの輻輳制御」、RFC 896、DOI 10.17487 / RFC0896、1984年1月、<https://www.rfc-editor.org/info/rfc896>。
[RFC2309] Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, S., Wroclawski, J., and L. Zhang, "Recommendations on Queue Management and Congestion Avoidance in the Internet", RFC 2309, DOI 10.17487/RFC2309, April 1998, <https://www.rfc-editor.org/info/rfc2309>.
[RFC2309]ブレーデン、B。、クラーク、D。、クロウクロフト、J。、デイビー、B。、ディアリング、S。、エストリン、D。、フロイド、S。、ジェイコブソン、V。、ミンシャル、G。、パートリッジ、 C.、Peterson、L.、Ramakrishnan、K.、Shenker、S.、Wroclawski、J。、およびL. Zhang、「インターネットでのキュー管理と輻輳回避に関する推奨事項」、RFC 2309、DOI 10.17487 / RFC2309、4月1998、<https://www.rfc-editor.org/info/rfc2309>。
[RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion Control", RFC 5681, DOI 10.17487/RFC5681, September 2009, <https://www.rfc-editor.org/info/rfc5681>.
[RFC5681] Allman、M.、Paxson、V。、およびE. Blanton、「TCP Congestion Control」、RFC 5681、DOI 10.17487 / RFC5681、2009年9月、<https://www.rfc-editor.org/info/ rfc5681>。
[RFC8290] Hoeiland-Joergensen, T., McKenney, P., Taht, D., Gettys, J., and E. Dumazet, "The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm", RFC 8290, DOI 10.17487/RFC8290, January 2018, <https://www.rfc-editor.org/info/rfc8290>.
[RFC8290] Hoeiland-Joergensen、T.、McKenney、P.、Taht、D.、Gettys、J.、and E. Dumazet、 "The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm"、RFC 8290、DOI 10.17487 / RFC8290、2018年1月、<https://www.rfc-editor.org/info/rfc8290>。
[TSV84] Jacobson, V., "CoDel", IETF 84, Transport Area Open Meeting, July 2012, <http://www.ietf.org/proceedings/84/slides/ slides-84-tsvarea-4.pdf>.
[TSV84] Jacobson、V。、「CoDel」、IETF 84、トランスポートエリアオープンミーティング、2012年7月、<http://www.ietf.org/proceedings/84/slides/ slides-84-tsvarea-4.pdf> 。
[VANQ2006] Jacobson, V., "A Rant on Queues", Talk at MIT Lincoln Labs, Lexington, MA, July 2006, <http://www.pollere.net/Pdfdocs/QrantJul06.pdf>.
[VANQ2006] Jacobson、V。、「A Rant on Queues」、マサチューセッツ州レキシントン、MITリンカーン研究所での講演、2006年7月、<http://www.pollere.net/Pdfdocs/QrantJul06.pdf>。
Nandita Dukkipati and her group at Google realized that the CoDel building blocks could be applied to bufferbloat problems in data-center servers, not just to Internet routers. The Linux CoDel queueing discipline (qdisc) was adapted in three ways to tackle this bufferbloat problem.
Nandita DukkipatiとGoogleの彼女のグループは、CoDelビルディングブロックが、インターネットルーターだけでなく、データセンターサーバーのバッファブロート問題に適用できることを認識しました。 Linux CoDelキューイング規則（qdisc）は、このバッファブロート問題に取り組むために3つの方法で適応されました。
1. The default CoDel action was modified to be a direct feedback from qdisc to the TCP layer at dequeue. The direct feedback simply reduces TCP's congestion window just as congestion control would do in the event of drop. The scheme falls back to ECN marking or packet drop if the TCP socket lock could not be acquired at dequeue.
1. デキュー時にデフォルトのCoDelアクションが変更され、qdiscからTCPレイヤーに直接フィードバックされるようになりました。直接のフィードバックは、ドロップ時に輻輳制御が行うのと同じように、TCPの輻輳ウィンドウを単純に減らします。デキュー時にTCPソケットロックを取得できなかった場合、スキームはECNマーキングまたはパケットドロップにフォールバックします。
2. Being located in the server makes it possible to monitor the actual RTT to use as CoDel's interval rather than making a "best guess" of RTT. The CoDel interval is dynamically adjusted by using the maximum TCP round-trip time (RTT) of those connections sharing the same qdisc/bucket. In particular, there is a history entry of the maximum RTT experienced over the last second. As a packet is dequeued, the RTT estimate is accessed from its TCP socket. If the estimate is larger than the current CoDel interval, the CoDel interval is immediately refreshed to the new value. If the CoDel interval is not refreshed for over a second, it is decreased to the history entry, and the process is repeated. The use of the dynamic TCP RTT estimate allows the interval to adapt to the actual maximum value currently seen and thus lets the controller space its drop intervals appropriately.
2. サーバーに配置されていると、RTTの「最良の推測」を行うのではなく、実際のRTTを監視してCoDelの間隔として使用できます。 CoDel間隔は、同じqdisc / bucketを共有する接続の最大TCPラウンドトリップ時間（RTT）を使用して動的に調整されます。特に、過去1秒間に経験した最大RTTの履歴エントリがあります。パケットがキューから取り出されると、RTT見積もりはそのTCPソケットからアクセスされます。推定値が現在のCoDel間隔よりも大きい場合、CoDel間隔はすぐに新しい値に更新されます。 CoDel間隔が1秒以上更新されない場合は、履歴エントリまで減少し、プロセスが繰り返されます。動的TCP RTT推定を使用すると、現在表示されている実際の最大値に間隔を合わせることができるため、コントローラーはドロップ間隔を適切に間隔を空けることができます。
3. Since the mathematics of computing the setpoint are invariant, a TARGET of 5% of the RTT or CoDel interval was used here.
3. セットポイントを計算する数学は不変なので、RTTまたはCoDel間隔の5％のTARGETがここで使用されました。
Non-data packets were not dropped, as these are typically small and sometimes critical control packets. Being located on the server, there is no concern with misbehaving users as there would be on the public Internet.
非データパケットは、通常は小さく、場合によっては重要な制御パケットであるため、ドロップされませんでした。サーバー上に配置されているため、パブリックインターネット上にあるようなユーザーの誤動作の心配はありません。
In several data-center workload benchmarks, which are typically bursty, CoDel reduced the queueing latencies at the qdisc and thereby improved the mean and 99th-percentile latencies from several tens of milliseconds to less than one millisecond. The minimum tracking part of the CoDel framework proved useful in disambiguating "good" queue versus "bad" queue, which is particularly helpful in controlling qdisc buffers that are inherently bursty because of TCP Segmentation Offload (TSO).
CoDelは、通常バースト性の高いいくつかのデータセンターのワークロードベンチマークで、qdiscでのキュー待機待ち時間を削減し、それによって平均および99パーセンタイルの待ち時間を数十ミリ秒から1ミリ秒未満に改善しました。 CoDelフレームワークの最小追跡部分は、「良い」キューと「悪い」キューのあいまいさを解消するのに役立ちます。これは、TCPセグメンテーションオフロード（TSO）のために本質的にバースト性であるqdiscバッファーを制御するのに特に役立ちます。
Acknowledgments
謝辞
The authors thank Jim Gettys for the constructive nagging that made us get the work "out there" before we thought it was ready. We thank Dave Taht, Eric Dumazet, and the open source community for showing the value of getting it "out there" and for making it real. We thank Nandita Dukkipati for contributions to Section 6 and for comments that helped to substantially improve this document. We thank the AQM Working Group and the Transport Area Shepherd, Wes Eddy, for patiently prodding this document all the way to publication as an RFC.
著者は、準備ができていると私たちが考える前に、作品を「そこに」出してくれた建設的なしつこいものについて、Jim Gettysに感謝します。 Dave Taht氏、Eric Dumazet氏、そしてオープンソースコミュニティに、「そこから」それを実現することの価値を示してくれたことに感謝します。セクション6への貢献と、このドキュメントの大幅な改善に役立つコメントを提供してくれたNandita Dukkipatiに感謝します。 AQMワーキンググループとトランスポートエリアシェパードのWes Eddyに、このドキュメントをRFCとして発行するまで根気よく提案してくれたことに感謝します。
Authors' Addresses
著者のアドレス
Kathleen Nichols Pollere, Inc. PO Box 370201 Montara, CA 94037 United States of America
キャスリーン・ニコルズ・ポレール社PO Box 370201 Montara、CA 94037アメリカ合衆国
Email: nichols@pollere.com
Van Jacobson Google
ジェイコブソングーグルから
Email: vanj@google.com
Andrew McGregor (editor) Google
アンドリュー・マクレガー（編集者）グーグル
Email: andrewmcgr@google.com
Janardhan Iyengar (editor) Google
Janardhan Iyengar（編集者）Google
Email: jri@google.com