[要約] RFC 8290は、Flow Queue CoDelパケットスケジューラとアクティブキューマネジメントアルゴリズムに関するものであり、パケットのキューイングと遅延の管理を改善するための手法を提案しています。このRFCの目的は、ネットワークのパフォーマンスを向上させるために、適切なキューイングとアクティブキューマネジメントの実装を促進することです。
Internet Engineering Task Force (IETF) T. Hoeiland-Joergensen
Request for Comments: 8290 Karlstad University
Category: Experimental P. McKenney
ISSN: 2070-1721 IBM Linux Technology Center
D. Taht
Teklibre
J. Gettys
E. Dumazet Google, Inc. January 2018
E. Dumazet Google、Inc. 2018年1月
The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm
フローキューCoDelパケットスケジューラとアクティブキュー管理アルゴリズム
Abstract
概要
This memo presents the FQ-CoDel hybrid packet scheduler and Active Queue Management (AQM) algorithm, a powerful tool for fighting bufferbloat and reducing latency.
このメモは、FQ-CoDelハイブリッドパケットスケジューラとアクティブキュー管理（AQM）アルゴリズムを示しています。
FQ-CoDel mixes packets from multiple flows and reduces the impact of head-of-line blocking from bursty traffic. It provides isolation for low-rate traffic such as DNS, web, and videoconferencing traffic. It improves utilisation across the networking fabric, especially for bidirectional traffic, by keeping queue lengths short, and it can be implemented in a memory- and CPU-efficient fashion across a wide range of hardware.
FQ-CoDelは、複数のフローからのパケットを混合し、バースト性トラフィックによるヘッドオブラインブロッキングの影響を軽減します。 DNS、Web、ビデオ会議トラフィックなどの低レートトラフィックを分離します。特に双方向トラフィックの場合、キューの長さを短く保つことにより、ネットワーキングファブリック全体の使用率が向上し、幅広いハードウェアにわたってメモリとCPU効率の高い方法で実装できます。
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/rfc8290.
このドキュメントの現在のステータス、正誤表、およびフィードバックの提供方法に関する情報は、https：//www.rfc-editor.org/info/rfc8290で入手できます。
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 . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Conventions Used in This Document . . . . . . . . . . . . 4
1.2. Terminology and Concepts . . . . . . . . . . . . . . . . 5
1.3. Informal Summary of FQ-CoDel . . . . . . . . . . . . . . 5
2. CoDel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. Flow Queueing . . . . . . . . . . . . . . . . . . . . . . . . 7
4. The FQ-CoDel Scheduler . . . . . . . . . . . . . . . . . . . 8
4.1. Enqueue . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1.1. Alternative Classification Schemes . . . . . . . . . 9
4.2. Dequeue . . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Implementation Considerations . . . . . . . . . . . . . . . . 11
5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 11
5.2. Parameters . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.1. Interval . . . . . . . . . . . . . . . . . . . . . . 12
5.2.2. Target . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.3. Packet Limit . . . . . . . . . . . . . . . . . . . . 13
5.2.4. Quantum . . . . . . . . . . . . . . . . . . . . . . . 13
5.2.5. Flows . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2.6. Explicit Congestion Notification (ECN) . . . . . . . 14
5.2.7. CE Threshold . . . . . . . . . . . . . . . . . . . . 14
5.3. Probability of Hash Collisions . . . . . . . . . . . . . 14
5.4. Memory Overhead . . . . . . . . . . . . . . . . . . . . . 15
5.5. Per-Packet Timestamping . . . . . . . . . . . . . . . . . 16
5.6. Limiting Queueing in Lower Layers . . . . . . . . . . . . 16
5.7. Other Forms of Fair Queueing . . . . . . . . . . . . . . 17
5.8. Differences between CoDel and FQ-CoDel Behaviour . . . . 17
6. Limitations of Flow Queueing . . . . . . . . . . . . . . . . 18
6.1. Fairness between Things Other Than Flows . . . . . . . . 18
6.2. Flow Bunching by Opaque Encapsulation . . . . . . . . . . 18
6.3. Low-Priority Congestion Control Algorithms . . . . . . . 19
7. Deployment Status and Future Work . . . . . . . . . . . . . . 19
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
10.1. Normative References . . . . . . . . . . . . . . . . . . 21
10.2. Informative References . . . . . . . . . . . . . . . . . 21
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25
The Flow Queue CoDel (FQ-CoDel) algorithm is a combined packet scheduler and Active Queue Management (AQM) [RFC3168] algorithm developed as part of the bufferbloat-fighting community effort [BLOATWEB]. It is based on a modified Deficit Round Robin (DRR) queue scheduler [DRR] [DRRPP] with the CoDel AQM [RFC8289] algorithm operating on each queue. This document describes the combined algorithm; reference implementations are available for the ns-2 [NS2] and ns-3 [NS3] network simulators, and the algorithm is included in the mainline Linux kernel as the fq_codel queueing discipline [LINUXSRC].
フローキューCoDel（FQ-CoDel）アルゴリズムは、パケットスケジューラとアクティブキュー管理（AQM）[RFC3168]アルゴリズムを組み合わせたもので、バッファブロートファイティングコミュニティの取り組み[BLOATWEB]の一部として開発されました。これは、各キューで動作するCoDel AQM [RFC8289]アルゴリズムを備えた修正済み赤字ラウンドロビン（DRR）キュースケジューラ[DRR] [DRRPP]に基づいています。このドキュメントでは、組み合わせたアルゴリズムについて説明します。リファレンス実装はns-2 [NS2]およびns-3 [NS3]ネットワークシミュレータで利用可能であり、アルゴリズムはfq_codelキューイング規則[LINUXSRC]としてメインラインLinuxカーネルに含まれています。
FQ-CoDel is a general, efficient, nearly parameterless queue management approach combining flow queueing with CoDel. It is a powerful tool for solving bufferbloat [BLOAT] and has already been turned on by default in a number of Linux distributions. In this document, we describe the Linux implementation in sufficient detail for others to independently implement the algorithm for deployment outside the Linux ecosystem.
FQ-CoDelは、フローキューイングとCoDelを組み合わせた、一般的で効率的な、ほぼパラメーターレスのキュー管理アプローチです。これはbufferbloat [BLOAT]を解決するための強力なツールであり、多くのLinuxディストリビューションではすでにデフォルトでオンになっています。このドキュメントでは、他の人がLinuxエコシステムの外に展開するためのアルゴリズムを独立して実装できるように、Linuxの実装について詳しく説明します。
Since the FQ-CoDel algorithm was originally developed in the Linux kernel, that implementation is still considered canonical. This document describes the algorithm in the abstract in Sections 1-4 and separates out most implementation details in subsequent sections; however, the Linux implementation is used as a reference for default behaviour in the abstract algorithm description.
FQ-CoDelアルゴリズムは元々Linuxカーネルで開発されたため、その実装はまだ正規と見なされています。このドキュメントでは、セクション1〜4の要約でアルゴリズムを説明し、後続のセクションでほとんどの実装の詳細を分離しています。ただし、Linux実装は、抽象アルゴリズムの説明ではデフォルトの動作の参照として使用されます。
This document is structured as follows. This section gives some concepts and terminology used in the rest of the document and gives a short informal summary of the FQ-CoDel algorithm. Section 2 gives an overview of the CoDel algorithm. Section 3 covers the flow hashing and DRR portion. Section 4 then describes the working of the algorithm in detail, while Section 5 describes implementation details and considerations. Section 6 lists some of the limitations of using flow queueing. Section 7 outlines the current status of FQ-CoDel deployment and lists some possible future areas of inquiry. Finally, Section 8 reiterates some important security points that must be observed in the implementation.
このドキュメントは次のように構成されています。このセクションでは、ドキュメントの残りの部分で使用されるいくつかの概念と用語を示し、FQ-CoDelアルゴリズムの短い非公式の要約を示します。セクション2では、CoDelアルゴリズムの概要を説明します。セクション3では、フローハッシングとDRRの部分について説明します。次に、セクション4ではアルゴリズムの動作について詳しく説明し、セクション5では実装の詳細と考慮事項について説明します。セクション6では、フローキューイングの使用に関するいくつかの制限を示します。セクション7では、FQ-CoDel展開の現在のステータスを概説し、調査の可能性のある将来の領域をいくつかリストします。最後に、セクション8では、実装で順守する必要があるいくつかの重要なセキュリティポイントを繰り返します。
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]で説明されているように解釈されます。
Flow: A flow is typically identified by a 5-tuple of source IP address, destination IP address, source port number, destination port number, and protocol number. It can also be identified by a superset or subset of those parameters, by Media Access Control (MAC) address, or by other means. FQ-CoDel hashes flows into a configurable number of buckets to assign packets to internal queues.
フロー：フローは通常、送信元IPアドレス、宛先IPアドレス、送信元ポート番号、宛先ポート番号、およびプロトコル番号の5タプルで識別されます。また、これらのパラメーターのスーパーセットまたはサブセット、メディアアクセス制御（MAC）アドレス、またはその他の手段によっても識別できます。 FQ-CoDelは、フローを構成可能な数のバケットにハッシュして、パケットを内部キューに割り当てます。
Queue: A queue of packets represented internally in FQ-CoDel. In most instances, each flow gets its own queue; however, because of the possibility of hash collisions, this is not always the case. In an attempt to avoid confusion, the word "queue" is used to refer to the internal data structure, and "flow" is used to refer to the actual stream of packets being delivered to the FQ-CoDel algorithm.
キュー：FQ-CoDelで内部的に表現されるパケットのキュー。ほとんどの場合、各フローは独自のキューを取得します。ただし、ハッシュの衝突の可能性があるため、これが常に当てはまるわけではありません。混乱を避けるために、「キュー」という語は内部データ構造を指すために使用され、「フロー」はFQ-CoDelアルゴリズムに配信されるパケットの実際のストリームを指すために使用されます。
Scheduler: A mechanism to select which queue a packet is dequeued from.
スケジューラ：パケットがどのキューからデキューされるかを選択するメカニズム。
CoDel AQM: The Active Queue Management algorithm employed by FQ-CoDel as described in [RFC8289].
CoDel AQM：[RFC8289]で説明されているようにFQ-CoDelによって使用されるアクティブキュー管理アルゴリズム。
DRR: Deficit Round Robin scheduling [DRR].
DRR：赤字ラウンドロビンスケジューリング[DRR]。
Quantum: The maximum amount of bytes to be dequeued from a queue at once.
量子：キューから一度にデキューされる最大バイト数。
Interval: Characteristic time period used by the control loop of CoDel to detect when a persistent queue is developing (see Section 4.2 of [RFC8289]).
間隔：CoDelの制御ループが永続キューが発生していることを検出するために使用する特徴的な時間（[RFC8289]のセクション4.2を参照）。
Target: Setpoint value of the minimum sojourn time of packets in a queue used as the target of the control loop in CoDel (see Section 4.3 of [RFC8289]).
ターゲット：CoDelの制御ループのターゲットとして使用されるキュー内のパケットの最小滞在時間のセットポイント値（[RFC8289]のセクション4.3を参照）。
FQ-CoDel is a hybrid of DRR [DRR] and CoDel [RFC8289], with an optimisation for sparse flows similar to Shortest Queue First (SQF) [SQF] and DRR++ [DRRPP]. We call this "flow queueing" rather than "fair queueing", as flows that build a queue are treated differently from flows that do not.
FQ-CoDelは、DRR [DRR]とCoDel [RFC8289]のハイブリッドで、Shortest Queue First（SQF）[SQF]およびDRR ++ [DRRPP]と同様のスパースフローを最適化します。キューを構築するフローは、そうでないフローとは異なる方法で処理されるため、これを「フェアキューイング」ではなく「フローキューイング」と呼びます。
By default, FQ-CoDel stochastically classifies incoming packets into different queues by hashing the 5-tuple of protocol number, source and destination IP addresses, and source and destination port numbers, perturbed with a random number selected at initiation time (although other flow classification schemes can optionally be configured instead; see Section 4.1.1). Each queue is managed by the CoDel AQM algorithm [CODEL] [RFC8289]. Packet ordering within a queue is preserved, since queues have FIFO ordering.
デフォルトでは、FQ-CoDelは、プロトコル番号、送信元と宛先のIPアドレス、および送信元と宛先のポート番号の5タプルをハッシュすることにより、着信パケットを確率的に異なるキューに分類し、開始時に選択された乱数で摂動します（他のフロー分類は代わりにスキームをオプションで構成できます（セクション4.1.1を参照）。各キューは、CoDel AQMアルゴリズム[CODEL] [RFC8289]によって管理されます。キューにはFIFO順序があるため、キュー内のパケット順序は保持されます。
The FQ-CoDel algorithm consists of two logical parts: (1) the scheduler, which selects which queue to dequeue a packet from, and (2) the CoDel AQM, which works on each of the queues. The subtleties of FQ-CoDel are mostly in the scheduling part, whereas the interaction between the scheduler and the CoDel algorithm are fairly straightforward.
FQ-CoDelアルゴリズムは、（1）パケットをデキューするキューを選択するスケジューラと、（2）各キューで機能するCoDel AQMの2つの論理部分で構成されます。 FQ-CoDelの微妙な部分はほとんどスケジューリングの部分にありますが、スケジューラとCoDelアルゴリズムの間の相互作用はかなり単純です。
At initialisation, each queue is set up to have a separate set of CoDel state variables. By default, 1024 queues are created. The Linux implementation at the time of writing supports anywhere from one to 65535 separate queues, and each queue maintains the state variables throughout its lifetime, and so acts the same as the non-FQ variant of CoDel would. This means that with only one queue, FQ-CoDel behaves essentially the same as CoDel by itself.
初期化時に、各キューはCoDel状態変数の個別のセットを持つように設定されます。デフォルトでは、1024個のキューが作成されます。執筆時点でのLinuxの実装は、1〜65535の個別のキューをサポートし、各キューは存続期間を通じて状態変数を維持するため、CoDelの非FQバリアントと同じように動作します。これは、キューが1つだけの場合、FQ-CoDelはそれ自体がCoDelと本質的に同じように動作することを意味します。
On dequeue, FQ-CoDel selects a queue from which to dequeue by a two-tier, round-robin scheme, in which each queue is allowed to dequeue up to a configurable quantum of bytes for each iteration. Deviations from this quantum are maintained as byte credits for the queue, which serves to make the fairness scheme byte-based rather than packet-based. The two-tier, round-robin mechanism distinguishes between "new" queues (which don't build up a standing queue) and "old" queues (which have queued enough data to be active for more than one iteration of the round-robin scheduler).
デキュー時に、FQ-CoDelは、2層のラウンドロビン方式でデキューするキューを選択します。各キューは、反復ごとに構成可能なバイト数までデキューできます。このクォンタムからの逸脱は、キューのバイトクレジットとして維持されます。これは、公平方式をパケットベースではなくバイトベースにする働きをします。 2層のラウンドロビンメカニズムは、「新しい」キュー（スタンディングキューを構築しない）と「古い」キュー（ラウンドロビンの1回以上の反復でアクティブになるのに十分なデータをキューに入れている）を区別しますスケジューラー）。
This new/old queue distinction has a particular consequence for queues that don't build up more than a quantum of bytes before being visited by the scheduler: such a queue will be removed from the list after it empties and then re-added as a new queue the next time a packet arrives for it. This means it will effectively get priority over queues that do not empty out each round (a minor caveat is required here to protect against starvation, see below). Exactly how little data a flow has to send to keep its queue in this state is somewhat difficult to reason about, because it depends on both the egress link speed and the number of concurrent flows. However, in practice, many things that are beneficial to have prioritised for typical internet use (ACKs, DNS lookups, interactive Secure Shell (SSH), HTTP requests, Voice over IP (VoIP)) _tend_ to fall in this category, which is why FQ-CoDel performs so well for many practical applications. However, the implicitness of the prioritisation means that for applications that require guaranteed priority (for instance, multiplexing the network control plane over the network itself), explicit classification is still needed.
この新しい/古いキューの区別は、スケジューラーによって訪問される前にバイトの量子を超えて構築されないキューに特定の結果をもたらします。そのようなキューは、空になった後にリストから削除され、次にとして追加されますパケットが次に到着したときに新しいキュー。これは、各ラウンドが空にならないキューよりも効果的に優先されることを意味します（飢餓から保護するために、ここで小さな注意が必要です。以下を参照）。キューがこの状態を維持するためにフローが送信する必要があるデータが正確にどれだけあるかは、出力リンク速度と同時フローの数の両方に依存するため、推論するのがやや困難です。ただし、実際には、一般的なインターネットの使用（ACK、DNSルックアップ、インタラクティブセキュアシェル（SSH）、HTTPリクエスト、Voice over IP（VoIP））を優先することが有益である多くのことは、このカテゴリに分類されるため、この理由ですFQ-CoDelは、多くの実用的なアプリケーションで非常に優れた性能を発揮します。ただし、優先順位付けの暗黙性は、保証された優先順位を必要とするアプリケーション（たとえば、ネットワーク自体へのネットワークコントロールプレーンの多重化）の場合、明示的な分類が依然として必要であることを意味します。
This scheduling scheme has some subtlety to it, which is explained in detail in the remainder of this document.
このスケジューリングスキームには微妙な点がいくつかあります。これについては、このドキュメントの残りの部分で詳しく説明します。
CoDel is described in the Communications of the ACM paper [CODEL] and the IETF document [RFC8289]. The basic idea is to control queue length, maintaining sufficient queueing to keep the outgoing link busy but avoiding building up the queue beyond that point. This is done by preferentially dropping packets that remain in the queue for "too long". Packets are dropped by head drop, which lowers the time for the drop signal to propagate back to the sender by the length of the queue and helps trigger TCP fast retransmit sooner.
CoDelは、Communications of the ACMペーパー[CODEL]およびIETFドキュメント[RFC8289]で説明されています。基本的な考え方は、キューの長さを制御し、発信リンクをビジー状態に保つのに十分なキューイングを維持しながら、そのポイントを超えてキューが構築されるのを回避することです。これは、「長すぎる」キューに残っているパケットを優先的にドロップすることによって行われます。パケットはヘッドドロップによってドロップされます。これにより、ドロップ信号が送信者に伝播するまでの時間がキューの長さだけ短くなり、TCP高速再送信をより早くトリガーするのに役立ちます。
The CoDel algorithm itself will not be described here; instead, we refer the reader to the CoDel document [RFC8289].
CoDelアルゴリズム自体はここでは説明しません。代わりに、読者にCoDelドキュメント[RFC8289]を紹介します。
The intention of FQ-CoDel's scheduler is to give each flow its own queue, hence the term "flow queueing". Rather than a perfect realisation of this, a hashing-based scheme is used, where flows are hashed into a number of buckets, each of which has its own queue. The number of buckets is configurable and presently defaults to 1024 in the Linux implementation. This is enough to avoid hash collisions on a moderate number of flows as seen, for instance, in a home gateway. Depending on the characteristics of the link, this can be tuned to trade off memory for a lower probability of hash collisions. See Sections 5.3 and 5.4 for a more in-depth discussion of this.
FQ-CoDelのスケジューラの目的は、各フローに独自のキューを提供することです。そのため、「フローキューイング」という用語が使用されます。これを完全に実現するのではなく、ハッシングベースのスキームが使用されます。この場合、フローはいくつかのバケットにハッシュされ、それぞれに独自のキューがあります。バケットの数は設定可能であり、現在Linuxの実装ではデフォルトで1024に設定されています。これは、たとえばホームゲートウェイで見られるような、適度な数のフローでのハッシュ衝突を回避するのに十分です。リンクの特性に応じて、ハッシュコリジョンの確率を下げるためにメモリをトレードオフするように調整できます。この詳細については、セクション5.3および5.4を参照してください。
By default, the flow hashing is performed on the 5-tuple of source and destination IP addresses, source and destination port numbers, and protocol number. While the hashing can be customised to match on arbitrary packet bytes, care should be taken when doing so; much of the benefit of the FQ-CoDel scheduler comes from this per-flow distinction. However, the default hashing does have some limitations, as discussed in Section 6.
デフォルトでは、フローハッシュは送信元と宛先のIPアドレス、送信元と宛先のポート番号、およびプロトコル番号の5タプルで実行されます。ハッシングは任意のパケットバイトに一致するようにカスタマイズできますが、その際は注意が必要です。 FQ-CoDelスケジューラの利点の多くは、このフローごとの違いから得られます。ただし、セクション6で説明するように、デフォルトのハッシュにはいくつかの制限があります。
FQ-CoDel's DRR scheduler is byte-based, employing a deficit round-robin mechanism between queues. This works by keeping track of the current number of "byte credits" of each queue. This number is initialised to the configurable quantum; each time a queue gets a dequeue opportunity, it gets to dequeue packets, thus decreasing the number of credits by the packet size for each packet. This continues until the value of the byte credits counter becomes zero or less, at which point the counter is increased by one quantum, and the dequeue opportunity ends.
FQ-CoDelのDRRスケジューラはバイトベースであり、キュー間で不足したラウンドロビンメカニズムを採用しています。これは、各キューの「バイトクレジット」の現在の数を追跡することで機能します。この数は構成可能なクォンタムに初期化されます。キューがデキューの機会を得るたびに、パケットをデキューし、各パケットのパケットサイズによってクレジット数を減らします。これは、バイトクレジットカウンターの値がゼロ以下になるまで続きます。その時点でカウンターは1クォンタム増加し、デキューの機会が終了します。
This means that if one queue contains packets of, for instance, size quantum/3, and another contains quantum-sized packets, the first queue will dequeue three packets each time it gets a turn, whereas the second only dequeues one. This means that flows that send small packets are not penalised by the difference in packet sizes; rather, the DRR scheme approximates a byte-based fairness queueing scheme. The size of the quantum determines the scheduling granularity, with the trade-off from too small a quantum being scheduling overhead. For small bandwidths, lowering the quantum from the default MTU size can be advantageous.
つまり、1つのキューに、たとえば、quantum / 3サイズのパケットが含まれ、別のキューに量子サイズのパケットが含まれている場合、最初のキューは順番が回るたびに3つのパケットをデキューし、2番目のキューは1つだけデキューします。つまり、小さなパケットを送信するフローは、パケットサイズの違いによるペナルティを受けません。むしろ、DRRスキームは、バイトベースの公平キューイングスキームに近似しています。クォンタムのサイズはスケジューリングの細分性を決定し、小さすぎるクォンタムからのトレードオフがスケジューリングのオーバーヘッドになります。帯域幅が小さい場合、クォンタムをデフォルトのMTUサイズから下げると効果的です。
Unlike plain DRR, there are two sets of flows: a "new" list for flows that have not built a queue recently and an "old" list for queues that build a backlog. This distinction is an integral part of the FQ-CoDel scheduler and is described in more detail in Section 4.
プレーンDRRとは異なり、フローには2つのセットがあります。最近キューを作成していないフローの「新しい」リストと、バックログを作成するキューの「古い」リストです。この違いはFQ-CoDelスケジューラーの不可欠な部分であり、セクション4でより詳細に説明されています。
To make its scheduling decisions, FQ-CoDel maintains two ordered lists of active queues: new and old queues. When a packet is added to a queue that is not currently active, that queue becomes active by being added to the list of new queues. Later on, it is moved to the list of old queues, from which it is removed when it is no longer active. This behaviour is the source of some subtlety in the packet scheduling at dequeue time, as explained below.
FQ-CoDelは、スケジューリングを決定するために、アクティブキューの2つの順序付けられたリスト（新しいキューと古いキュー）を維持します。現在アクティブではないキューにパケットが追加されると、そのキューは新しいキューのリストに追加されることによってアクティブになります。その後、古いキューのリストに移動され、アクティブでなくなると削除されます。この動作は、以下で説明するように、デキュー時のパケットスケジューリングの微妙な原因です。
The packet enqueue mechanism consists of three stages: classifying into a queue, timestamping and bookkeeping, and optionally dropping a packet when the total number of enqueued packets goes over the maximum.
パケットエンキューメカニズムは、キューへの分類、タイムスタンプおよびブックキーピングの3つの段階で構成され、オプションで、エンキューされたパケットの総数が最大値を超えたときにパケットをドロップします。
When a packet is enqueued, it is first classified into the appropriate queue. By default, this is done by hashing (using a Jenkins hash function [JENKINS]) on the 5-tuple of IP protocol, source and destination IP addresses, and source and destination port numbers (if they exist) and then taking the hash value modulo the number of queues. The hash is salted by modulo addition of a random value selected at initialisation time to prevent possible DoS attacks if the hash is predictable ahead of time (see Section 8). The Linux
パケットがエンキューされると、最初に適切なキューに分類されます。デフォルトでは、これは、IPプロトコル、送信元と宛先のIPアドレス、および送信元と宛先のポート番号（存在する場合）の5タプルでハッシュし（Jenkinsハッシュ関数[JENKINS]を使用）、ハッシュ値を取得することで行われます。キューの数を法として。ハッシュは、初期化時に選択されたランダムな値をモジュロ加算することでソルトされ、ハッシュが事前に予測可能な場合にDoS攻撃の可能性を防ぎます（セクション8を参照）。 Linux
kernel implements the Jenkins hash function by mixing three 32-bit values into a single 32-bit output value. Inputs larger than 96 bits are reduced by additional mixing steps, 96 bits at a time.
カーネルは、3つの32ビット値を単一の32ビット出力値に混合することにより、Jenkinsハッシュ関数を実装します。 96ビットを超える入力は、追加の混合ステップにより、一度に96ビット削減されます。
Once the packet has been successfully classified into a queue, it is handed over to the CoDel algorithm for timestamping. It is then added to the tail of the selected queue, and the queue's byte count is updated by the packet size. Then, if the queue is not currently active (i.e., if it is not in either the list of new queues or the list of old queues), it is added to the end of the list of new queues, and its number of credits is initiated to the configured quantum. Otherwise, the queue is left in its current queue list.
パケットがキューに正常に分類されると、タイムスタンプのためにCoDelアルゴリズムに渡されます。次に、選択されたキューの末尾に追加され、キューのバイト数がパケットサイズによって更新されます。次に、キューが現在アクティブでない場合（つまり、新しいキューのリストまたは古いキューのリストのいずれにもない場合）、新しいキューのリストの最後に追加され、そのクレジット数は構成されたクォンタムに対して開始されました。それ以外の場合、キューは現在のキューリストに残ります。
Finally, to protect against overload, the total number of enqueued packets is compared with the configured limit. If the limit is exceeded (which can happen since a packet was just enqueued), the queue with the largest current byte count is selected and half the number of packets from this queue (up to a maximum of 64 packets) are dropped from the head of that queue. Dropping several packets at once helps amortise the cost of finding the longest queue, significantly lowering CPU usage in an overload situation.
最後に、過負荷から保護するために、エンキューされたパケットの総数が、構成された制限と比較されます。制限を超えた場合（パケットがキューに追加された直後に発生する可能性があります）、現在のバイトカウントが最大のキューが選択され、このキューからのパケット数の半分（最大64パケット）が先頭から削除されますそのキューの。一度に複数のパケットをドロップすると、最長のキューを見つけるコストが分散され、過負荷状態でのCPU使用率が大幅に低下します。
As mentioned previously, it is possible to modify the classification scheme to provide a different notion of a flow. The Linux implementation provides this option in the form of the "tc filter" command. While this can add capabilities (for instance, matching on other possible parameters such as MAC address, Diffserv code point values, firewall rules, flow-specific markings, IPv6 flow label, etc.), care should be taken to preserve the notion of flow because much of the benefit of the FQ-CoDel scheduler comes from keeping flows in separate queues.
前述のように、フローの異なる概念を提供するために分類スキームを変更することが可能です。 Linuxの実装では、このオプションを「tc filter」コマンドの形式で提供しています。これにより機能が追加される可能性があります（たとえば、MACアドレス、Diffservコードポイント値、ファイアウォールルール、フロー固有のマーキング、IPv6フローラベルなどの他の可能なパラメーターでのマッチング）、フローの概念を保持するように注意する必要がありますFQ-CoDelスケジューラの利点の多くは、フローを別々のキューに保持することから得られるためです。
For protocols that do not contain a port number (such as ICMP), the Linux implementation simply sets the port numbers to zero and performs the hashing as usual. In practice, this results in such protocols each getting their own queue (except in the case of hash collisions). An implementation can perform other classifications for protocols that have their own notion of a flow but SHOULD fall back to simply hashing on source and destination IP address and protocol number in the absence of other information.
ポート番号を含まないプロトコル（ICMPなど）の場合、Linux実装はポート番号をゼロに設定し、通常どおりハッシュを実行します。実際には、その結果、このようなプロトコルはそれぞれ独自のキューを取得します（ハッシュ衝突の場合を除く）。実装は、独自のフローの概念を持つプロトコルに対して他の分類を実行できますが、他の情報がない場合は、送信元と宛先のIPアドレスとプロトコル番号のハッシュに単純にフォールバックする必要があります。
The default classification scheme can additionally be improved by performing decapsulation of tunnelled packets prior to hashing on the 5-tuple in the encapsulated payload. The Linux implementation does this for common encapsulations known to the kernel, such as 6in4 [RFC4213], IP-in-IP [RFC2003], and Generic Routing Encapsulation (GRE) [RFC2890]. This helps to distinguish between flows that share the same (outer) 5-tuple but, of course, is limited to unencrypted tunnels (see Section 6.2 for a discussion of encrypted tunnels).
カプセル化されたペイロードの5タプルでハッシュする前に、トンネル化されたパケットのカプセル化解除を実行することにより、デフォルトの分類スキームをさらに改善できます。 Linux実装は、6in4 [RFC4213]、IP-in-IP [RFC2003]、Generic Routing Encapsulation（GRE）[RFC2890]など、カーネルに既知の一般的なカプセル化に対してこれを行います。これは、同じ（外部）5タプルを共有するフローを区別するのに役立ちますが、もちろん暗号化されていないトンネルに制限されます（暗号化されたトンネルの説明については、セクション6.2を参照してください）。
Most of FQ-CoDel's work is done at packet dequeue time. It consists of three parts: selecting a queue from which to dequeue a packet, actually dequeueing it (employing the CoDel algorithm in the process), and some final bookkeeping.
FQ-CoDelのほとんどの作業は、パケットのデキュー時に行われます。これは3つの部分で構成されています。パケットをデキューするキューの選択、実際のデキュー（プロセスでCoDelアルゴリズムを使用）、および最終的なブックキーピングです。
For the first part, the scheduler first looks at the list of new queues; for the queue at the head of that list, if that queue has a negative number of credits (i.e., it has already dequeued at least a quantum of bytes), it is given an additional quantum of credits, the queue is put onto _the end of_ the list of old queues, and the routine selects the next queue and starts again.
最初の部分では、スケジューラは最初に新しいキューのリストを調べます。そのリストの先頭にあるキューについて、そのキューに負の数のクレジットがある場合（つまり、すでに少なくとも1バイトのキューがデキューされている場合）、追加のクレジットが与えられ、キューは_the endに置かれますof_古いキューのリスト。ルーチンは次のキューを選択して、再び開始します。
Otherwise, that queue is selected for dequeue. If the list of new queues is empty, the scheduler proceeds down the list of old queues in the same fashion (checking the credits and either selecting the queue for dequeueing or adding credits and putting the queue back at the end of the list).
それ以外の場合、そのキューはデキュー用に選択されます。新しいキューのリストが空の場合、スケジューラーは同じ方法で古いキューのリストを下に進みます（クレジットを確認し、デキューするキューを選択するか、クレジットを追加して、リストの最後にキューを戻します）。
After having selected a queue from which to dequeue a packet, the CoDel algorithm is invoked on that queue. This applies the CoDel control law, which is the mechanism CoDel uses to determine when to drop packets (see [RFC8289]). As a result of this, one or more packets may be discarded from the head of the selected queue before the packet that should be dequeued is returned (or nothing is returned if the queue is or becomes empty while being handled by the CoDel algorithm).
パケットをデキューするキューを選択した後、そのキューでCoDelアルゴリズムが呼び出されます。これはCoDel制御法則を適用します。これは、CoDelがパケットをドロップするタイミングを決定するために使用するメカニズムです（[RFC8289]を参照）。この結果、デキューする必要のあるパケットが返される前に、選択したキューの先頭から1つ以上のパケットが破棄される可能性があります（または、CoDelアルゴリズムによる処理中にキューが空になるか空になると、何も返されません）。
Finally, if the CoDel algorithm does not return a packet, then the queue must be empty, and the scheduler does one of two things. If the queue selected for dequeue came from the list of new queues, it is moved to _the end of_ the list of old queues. If instead it came from the list of old queues, that queue is removed from the list, to be added back (as a new queue) the next time a packet arrives that hashes to that queue. Then (since no packet was available for dequeue), the whole dequeue process is restarted from the beginning.
最後に、CoDelアルゴリズムがパケットを返さない場合、キューは空でなければならず、スケジューラーは2つのことのいずれかを行います。デキュー用に選択されたキューが新しいキューのリストからのものである場合、古いキューのリストの最後に移動されます。代わりに古いキューのリストから来た場合、そのキューはリストから削除され、次にそのキューにハッシュされるパケットが到着したときに（新しいキューとして）追加されます。次に（デキューに使用できるパケットがなかったため）、デキュープロセス全体が最初から再開されます。
If, instead, the scheduler _did_ get a packet back from the CoDel algorithm, it subtracts the size of the packet from the byte credits for the selected queue and returns the packet as the result of the dequeue operation.
代わりに、スケジューラ_did_がCoDelアルゴリズムからパケットを取得すると、選択したキューのバイトクレジットからパケットのサイズが差し引かれ、デキュー操作の結果としてパケットが返されます。
The step that moves an empty queue from the list of new queues to the end of the list of old queues before it is removed is crucial to prevent starvation. Otherwise, the queue could reappear (the next time a packet arrives for it) before the list of old queues is visited; this can go on indefinitely, even with a small number of active flows, if the flow providing packets to the queue in question transmits at just the right rate. This is prevented by first moving the queue to the end of the list of old queues, forcing the scheduler to service all old queues before the empty queue is removed and thus preventing starvation.
空のキューを削除する前に、新しいキューのリストから古いキューのリストの最後に空のキューを移動する手順は、枯渇を防ぐために重要です。そうしないと、古いキューのリストにアクセスする前に、キューが（次にパケットが到着したときに）再表示される可能性があります。問題のキューにパケットを提供するフローが適切なレートで送信する場合、アクティブなフローの数が少ない場合でも、これは無期限に続行できます。これは、最初にキューを古いキューのリストの最後に移動し、空のキューが削除される前にスケジューラがすべての古いキューを処理するように強制することで防止され、飢餓を防ぎます。
The resulting migration of queues between the different states is summarised in the state diagram shown in Figure 1. Note that both the new and old queue states can additionally have arrival and dequeue events that do not change the state; these are omitted in the figure.
異なる状態間でのキューの移行の結果は、図1に示す状態図に要約されています。新しいキュー状態と古いキュー状態の両方に、状態を変更しない到着イベントとデキューイベントが追加される可能性があることに注意してください。これらは図では省略されています。
+-----------------+ +------------------+
| | Empty | |
| Empty |<---------------+ Old +----+
| | | | |
+-------+---------+ +------------------+ |
| ^ ^ |Credits
|Arrival | | |Exhausted
v | | |
+-----------------+ | | |
| | Empty or | | |
| New +-------------------+ +-------+
| | Credits Exhausted
+-----------------+
Figure 1: Partial State Diagram for Queues between Different States
図1：異なる状態間のキューの部分的な状態図
This section contains implementation details for the FQ-CoDel algorithm. This includes the data structures and parameters used in the Linux implementation, as well as discussion of some required features of the target platform and other considerations.
このセクションには、FQ-CoDelアルゴリズムの実装の詳細が含まれています。これには、Linux実装で使用されるデータ構造とパラメーター、およびターゲットプラットフォームに必要ないくつかの機能とその他の考慮事項の説明が含まれます。
The main data structure of FQ-CoDel is the array of queues, which is instantiated with the number of queues specified by the "flows" parameter at instantiation time. Each queue consists simply of an ordered list of packets with FIFO semantics, two state variables tracking the queue credits and total number of bytes enqueued, and the set of CoDel state variables. Other state variables to track queue statistics can also be included; for instance, the Linux implementation keeps a count of dropped packets.
FQ-CoDelの主なデータ構造はキューの配列であり、インスタンス化時に「flows」パラメーターで指定されたキューの数でインスタンス化されます。各キューは、FIFOセマンティクスを備えたパケットの順序付きリスト、キュークレジットとエンキューされたバイトの総数を追跡する2つの状態変数、およびCoDel状態変数のセットで構成されています。キュー統計を追跡する他の状態変数も含めることができます。たとえば、Linuxの実装では、ドロップされたパケットの数が保持されます。
In addition to the queue structures themselves, FQ-CoDel maintains two ordered lists containing references to the subset of queues that are currently active. These are the lists of new and old queues, as explained in Section 4 above.
キュー構造自体に加えて、FQ-CoDelは、現在アクティブなキューのサブセットへの参照を含む2つの順序付きリストを維持します。上記のセクション4で説明したように、これらは新しいキューと古いキューのリストです。
In the Linux implementation, queue space is shared: there's a global limit on the number of packets the queues can hold, but not a limit for each queue.
Linuxの実装では、キュースペースは共有されます。キューが保持できるパケット数にはグローバルな制限がありますが、各キューの制限はありません。
The following are the user configuration parameters exposed by the Linux implementation of FQ-CoDel.
以下は、FQ-CoDelのLinux実装によって公開されるユーザー構成パラメーターです。
The "interval" parameter has the same semantics as CoDel and is used to ensure that the minimum sojourn time of packets in a queue used as an estimator by the CoDel control algorithm is a relatively up-to-date value. That is, CoDel only reacts to delay experienced in the last epoch of length interval. It SHOULD be set to be on the order of the worst-case RTT through the bottleneck to give end points sufficient time to react.
「間隔」パラメータは、CoDelと同じセマンティクスを持ち、CoDel制御アルゴリズムによって推定器として使用されるキュー内のパケットの最小滞在時間を比較的最新の値にするために使用されます。つまり、CoDelは、長さ間隔の最後のエポックで発生した遅延にのみ反応します。エンドポイントが反応するのに十分な時間を与えるために、ボトルネック全体でワーストケースのRTTのオーダーになるように設定する必要があります。
The default interval value is 100 ms.
デフォルトの間隔値は100ミリ秒です。
The "target" parameter has the same semantics as CoDel. It is the acceptable minimum standing/persistent queue delay for each FQ-CoDel queue. This minimum delay is identified by tracking the local minimum queue delay that packets experience.
「ターゲット」パラメーターの意味はCoDelと同じです。これは、各FQ-CoDelキューの許容可能な最小の待機/永続キュー遅延です。この最小遅延は、パケットで発生するローカルの最小キュー遅延を追跡することによって識別されます。
The default target value is 5 ms, but this value should be tuned to be at least the transmission time of a single MTU-sized packet at the prevalent egress link speed (which, for example, is ~15 ms for 1 Mbps and MTU 1500). This prevents CoDel from being too aggressive at low bandwidths. It should otherwise be set to 5-10% of the configured interval.
デフォルトのターゲット値は5ミリ秒ですが、この値は、少なくとも一般的な出力リンク速度での単一のMTUサイズのパケットの伝送時間になるように調整する必要があります（たとえば、1 MbpsおよびMTU 1500の場合は〜15ミリ秒です） ）。これにより、低帯域幅でCoDelが過度に攻撃的になるのを防ぎます。それ以外の場合は、構成された間隔の5〜10％に設定する必要があります。
Routers do not have infinite memory, so some packet limit MUST be enforced.
ルーターには無限のメモリがないため、パケット制限を強制する必要があります。
The "limit" parameter is the hard limit on the real queue size, measured in number of packets. This limit is a global limit on the number of packets in all queues; each individual queue does not have an upper limit. When the limit is reached and a new packet arrives for enqueue, packets are dropped from the head of the largest queue (measured in bytes) to make room for the new packet.
「制限」パラメータは、パケット数で測定される実際のキューサイズのハード制限です。この制限は、すべてのキュー内のパケット数に対するグローバルな制限です。個々のキューには上限がありません。制限に達し、エンキュー用の新しいパケットが到着すると、パケットは最大のキュー（バイト単位）の先頭からドロップされ、新しいパケット用のスペースが確保されます。
In Linux, the default packet limit is 10240 packets, which is suitable for up to 10-Gigabit Ethernet speeds. In practice, the hard limit is rarely (if ever) hit, as drops are performed by the CoDel algorithm long before the limit is hit. For platforms that are severely memory constrained, a lower limit can be used.
Linuxでは、デフォルトのパケット制限は10240パケットで、これは最大10ギガビットイーサネット速度に適しています。ドロップは制限に達する前にCoDelアルゴリズムによって実行されるため、実際にはハード制限に達することはほとんどありません。メモリーの制約が厳しいプラットフォームでは、下限を使用できます。
The "quantum" parameter is the number of bytes each queue gets to dequeue on each round of the scheduling algorithm. The default is set to 1514 bytes, which corresponds to the Ethernet MTU plus the hardware header length of 14 bytes.
「quantum」パラメータは、スケジューリングアルゴリズムの各ラウンドで各キューがデキューするために取得するバイト数です。デフォルトは1514バイトに設定されています。これは、イーサネットMTUにハードウェアヘッダー長の14バイトを加えたものに相当します。
In systems employing TCP Segmentation Offload (TSO), where a "packet" consists of an offloaded packet train, it can presently be as large as 64 kilobytes. In systems using Generic Receive Offload (GRO), they can be up to 17 times the TCP max segment size (or 25 kilobytes). These mega-packets severely impact FQ-CoDel's ability to schedule traffic, and they hurt latency needlessly. There is ongoing work in Linux to make smarter use of offload engines.
TCPセグメンテーションオフロード（TSO）を採用しているシステムでは、「パケット」はオフロードされたパケットトレインで構成され、現在64キロバイトにもなる可能性があります。 Generic Receive Offload（GRO）を使用するシステムでは、TCP最大セグメントサイズの最大17倍（または25キロバイト）になる可能性があります。これらのメガパケットは、FQ-CoDelのトラフィックをスケジュールする機能に深刻な影響を与え、待ち時間を不必要に損ないます。 Linuxでは、オフロードエンジンをよりスマートに利用するための作業が進行中です。
The "flows" parameter sets the number of queues into which the incoming packets are classified. Due to the stochastic nature of hashing, multiple flows may end up being hashed into the same slot.
「フロー」パラメータは、着信パケットが分類されるキューの数を設定します。ハッシュの確率的性質により、複数のフローが同じスロットにハッシュされる可能性があります。
This parameter can be set only at initialisation time in the current implementation, since memory has to be allocated for the hash table.
現在の実装では、初期化時にのみこのパラメーターを設定できます。これは、ハッシュテーブルにメモリを割り当てる必要があるためです。
The default value is 1024 in the current Linux implementation.
現在のLinux実装では、デフォルト値は1024です。
ECN [RFC3168] is enabled by default. Rather than do anything special with misbehaved ECN flows, FQ-CoDel relies on the packet scheduling system to minimise their impact; thus, the number of unresponsive packets in a flow being marked with ECN can grow to the overall packet limit but will not otherwise affect the performance of the system.
ECN [RFC3168]はデフォルトで有効になっています。 FQ-CoDelは、正しく動作しないECNフローで特別なことをするのではなく、パケットスケジューリングシステムに依存して影響を最小限に抑えます。したがって、ECNでマークされているフロー内の応答しないパケットの数は、全体のパケット制限まで増加する可能性がありますが、システムのパフォーマンスに影響を与えることはありません。
ECN can be disabled by specifying the "noecn" parameter.
「noecn」パラメーターを指定することにより、ECNを無効にできます。
This parameter enables DCTCP-like processing resulting in Congestion Encountered (CE) marking on ECN-Capable Transport (ECT) packets [RFC3168] starting at a lower sojourn delay setpoint than the default CoDel target. Details of Data Center TCP (DCTCP) can be found in [RFC8257].
このパラメーターは、DCTCPのような処理を有効にし、ECN対応トランスポート（ECT）パケットの輻輳検出（CE）マーキング[RFC3168]をデフォルトのCoDelターゲットよりも低い滞在遅延セットポイントで開始します。データセンターTCP（DCTCP）の詳細は[RFC8257]にあります。
The "ce_threshold" parameter is disabled by default; it can be enabled by setting it to a number of microseconds.
「ce_threshold」パラメータはデフォルトで無効になっています。マイクロ秒数に設定することで有効にできます。
Since the Linux FQ-CoDel implementation by default uses 1024 hash buckets, the probability that (say) 100 flows will all hash to the same bucket is something like ten to the power of minus 300. Thus, at least one of the flows will almost certainly hash to some other queue.
Linux FQ-CoDel実装はデフォルトで1024ハッシュバケットを使用するため、100のフローがすべて同じバケットにハッシュされる確率は、10のマイナス300乗のようなものです。したがって、少なくとも1つのフローはほぼ確かに他のキューにハッシュします。
Expanding on this, based on analytical equations for hash collision probabilities, for 100 flows, the probability of no collision is 90.78%; the probability that no more than two of the 100 flows will be involved in any given collision is 99.57%; and the probability that no more than three of the 100 flows will be involved in any given collision is 99.99%. These probabilities assume a hypothetical perfect hashing function, so in practice, they may be a bit lower. We have not found this difference to matter in practice.
これを拡張すると、ハッシュ衝突確率の分析方程式に基づいて、100フローの場合、衝突がない確率は90.78％になります。 100のフローのうち2つ以下が特定の衝突に関与する確率は99.57％です。 100のフローのうち3つ以下が特定の衝突に関与する確率は99.99％です。これらの確率は、仮想の完全なハッシュ関数を想定しているため、実際には少し低い可能性があります。実際にこの違いが問題になることはありません。
These probabilities can be improved upon by using set-associative hashing, a technique used in the Cake algorithm currently being developed as a further refinement of the FQ-CoDel principles [CAKE]. For a 4-way associative hash with the same number of total queues, the probability of no collisions for 100 flows is 99.93%, while for an 8-way associative hash, it is ~100%.
これらの確率は、FQ-CoDel原理[CAKE]のさらなる改良として現在開発されているCakeアルゴリズムで使用されている手法である、セットアソシアティブハッシュを使用することで改善できます。キューの合計数が同じ4ウェイの連想ハッシュの場合、100フローの衝突がない確率は99.93％ですが、8ウェイの連想ハッシュの場合は100％以下です。
FQ-CoDel can be implemented with a low memory footprint (less than 64 bytes per queue on 64-bit systems). These are the data structures used in the Linux implementation:
FQ-CoDelは、低メモリフットプリント（64ビットシステムのキューあたり64バイト未満）で実装できます。 Linux実装で使用されるデータ構造は次のとおりです。
<CODE BEGINS>
<コード開始>
struct codel_vars {
u32 count; /* number of dropped packets */
u32 lastcount; /* count entry to dropping state */
bool dropping; /* currently dropping? */
u16 rec_inv_sqrt; /* reciprocal sqrt computation */
codel_time_t first_above_time; /* when delay above target */
codel_time_t drop_next; /* next time to drop */
codel_time_t ldelay; /* sojourn time of last dequeued packet */
};
struct fq_codel_flow {
struct sk_buff *head;
struct sk_buff *tail;
struct list_head flowchain;
int credits; /* current number of queue credits */
u32 dropped; /* # of drops (or ECN marks) on flow */
struct codel_vars cvars;
};
<CODE ENDS> The master table managing all queues looks like this:
<コード終了>すべてのキューを管理するマスターテーブルは次のようになります。
<CODE BEGINS>
<コード開始>
struct fq_codel_sched_data {
struct tcf_proto *filter_list; /* optional external classifier */
struct fq_codel_flow *flows; /* Flows table [flows_cnt] */
u32 *backlogs; /* backlog table [flows_cnt] */
u32 flows_cnt; /* number of flows */
u32 perturbation; /* hash perturbation */
u32 quantum; /* psched_mtu(qdisc_dev(sch)); */
struct codel_params cparams;
struct codel_stats cstats;
u32 drop_overlimit;
u32 new_flow_count;
struct list_head new_flows; /* list of new flows */
struct list_head old_flows; /* list of old flows */
};
<CODE ENDS>
<コード終了>
The CoDel portion of the algorithm requires per-packet timestamps be stored along with the packet. While this approach works well for software-based routers, it may be impossible to retrofit devices that do most of their processing in silicon and lack the space or mechanism for timestamping.
アルゴリズムのCoDel部分では、パケットごとにタイムスタンプをパケットとともに保存する必要があります。このアプローチはソフトウェアベースのルーターではうまく機能しますが、ほとんどの処理をシリコンで行い、タイムスタンプのスペースやメカニズムがないデバイスを後付けすることは不可能かもしれません。
Also, while perfect resolution is not needed, timestamp resolution finer than the CoDel target setting is necessary. Furthermore, timestamping functions in the core OS need to be efficient, as they are called at least once on each packet enqueue and dequeue.
また、完全な解像度は必要ありませんが、CoDelターゲット設定よりも細かいタイムスタンプの解像度が必要です。さらに、コアOSのタイムスタンプ機能は、各パケットのエンキューおよびデキューで少なくとも1回呼び出されるため、効率的である必要があります。
When deploying a queue management algorithm such as FQ-CoDel, it is important to ensure that the algorithm actually runs in the right place to control the queue. In particular, lower layers of the operating system networking stack can have queues of their own, as can device drivers and hardware. Thus, it is desirable that the queue management algorithm runs as close to the hardware as possible. However, scheduling such complexity at interrupt time is difficult, so a small standing queue between the algorithm and the wire is often needed at higher transmit rates.
FQ-CoDelなどのキュー管理アルゴリズムを展開する場合、キューを制御するためにアルゴリズムが実際に適切な場所で実行されるようにすることが重要です。特に、オペレーティングシステムのネットワーキングスタックの下位層は、デバイスドライバーやハードウェアと同様に、独自のキューを持つことができます。したがって、キュー管理アルゴリズムはハードウェアのできるだけ近くで実行することが望ましい。ただし、割り込み時にそのような複雑さをスケジュールすることは困難であるため、より高い送信レートでは、アルゴリズムとワイヤの間に小さなスタンディングキューが必要になることがよくあります。
In Linux, the mechanism to ensure these different needs are balanced is called "Byte Queue Limits" [BQL]; it controls the device driver ring buffer (for physical line rates). For cases where this functionality is not available, the queue can be controlled by means of a software rate limiter such as Hierarchical Token Bucket [HTB] or Hierarchical Fair-Service Curve [HFSC]. The Cake algorithm [CAKE] integrates a software rate limiter for this purpose.
Linuxでは、これらのさまざまなニーズのバランスをとるメカニズムを「バイトキュー制限」[BQL]と呼びます。デバイスドライバーのリングバッファーを制御します（物理的なラインレート用）。この機能が利用できない場合、キューは、階層型トークンバケット[HTB]や階層型フェアサービスカーブ[HFSC]などのソフトウェアレートリミッターを使用して制御できます。 Cakeのアルゴリズム[CAKE]は、この目的のためにソフトウェアレートリミッターを統合しています。
Other issues with queues at lower layers are described in [CODEL].
下位層のキューに関するその他の問題は、[CODEL]で説明されています。
Much of the scheduling portion of FQ-CoDel is derived from DRR and is substantially similar to DRR++. Versions based on Stochastic Fair Queueing [SFQ] have also been produced and tested in ns2. Other forms of fair queueing, such as Weighted Fair Queueing [WFQ] or Quick Fair Queueing [QFQ], have not been thoroughly explored, but there's no a priori reason why the round-robin scheduling of FQ-CoDel couldn't be replaced with something else.
FQ-CoDelのスケジューリング部分の多くはDRRから派生し、DRR ++と実質的に類似しています。 Stochastic Fair Queuing [SFQ]に基づくバージョンもns2で作成およびテストされています。ウェイトフェアキューイング[WFQ]やクイックフェアキューイング[QFQ]など、他の形式のフェアキューイングは完全には調査されていませんが、FQ-CoDelのラウンドロビンスケジューリングを置き換えられなかった先験的な理由はありません他の何か。
For a comprehensive discussion of fairness queueing algorithms and their combination with AQM, see [RFC7806].
フェアネスキューイングアルゴリズムとそれらのAQMとの組み合わせの包括的な説明については、[RFC7806]を参照してください。
CoDel can be applied to a single queue system as a straight AQM, where it converges towards an "ideal" drop rate (i.e., one that minimises delay while keeping a high link utilisation) and then optimises around that control point.
CoDelは、単一のキューシステムにストレートAQMとして適用でき、「理想的な」ドロップレート（つまり、高いリンク使用率を維持しながら遅延を最小限に抑えるもの）に収束し、その制御点を中心に最適化します。
The scheduling of FQ-CoDel mixes packets of competing flows, which acts to pace bursty flows to better fill the pipe. Additionally, a new flow gets substantial leeway over other flows until CoDel finds an ideal drop rate for it. However, for a new flow that exceeds the configured quantum, more time passes before all of its data is delivered (as packets from it, too, are mixed across the other existing queue-building flows). Thus, FQ-CoDel takes longer (as measured in time) to converge towards an ideal drop rate for a given new flow but does so within fewer delivered _packets_ from that flow.
FQ-CoDelのスケジューリングは、競合するフローのパケットを混合します。これは、バーストフローのペースを調整してパイプをよりよく満たすように機能します。さらに、CoDelが理想的なドロップ率を見つけるまで、新しいフローは他のフローよりもかなり余裕があります。ただし、構成されたクォンタムを超える新しいフローの場合、すべてのデータが配信されるまでの時間が長くなります（フローからのパケットも他の既存のキュー構築フロー全体で混合されるため）。したがって、FQ-CoDelは、所定の新しいフローの理想的なドロップレートに収束するのに（時間で測定して）より長くかかりますが、そのフローから配信される_packets_が少ない範囲内で収束します。
Finally, the flow isolation provided by FQ-CoDel means that the CoDel drop mechanism operates on the flows actually building queues; this results in packets being dropped more accurately from the largest flows than when only CoDel is used. Additionally, flow isolation radically improves the transient behaviour of the network when traffic or link characteristics change (e.g., when new flows start up or the link bandwidth changes); while CoDel itself can take a while to respond, FQ-CoDel reacts almost immediately.
最後に、FQ-CoDelによって提供されるフロー分離は、CoDelドロップメカニズムが実際にキューを構築するフローで動作することを意味します。これにより、CoDelのみを使用する場合よりも、最大のフローからより正確にパケットがドロップされます。さらに、フロー分離は、トラフィックやリンクの特性が変化したとき（たとえば、新しいフローが起動したときやリンクの帯域幅が変化したとき）のネットワークの一時的な動作を根本的に改善します。 CoDel自体は応答に時間がかかることがありますが、FQ-CoDelはほとんどすぐに反応します。
While FQ-CoDel has been shown in many scenarios to offer significant performance gains compared to alternative queue management strategies, there are some scenarios where the scheduling algorithm in particular is not a good fit. This section documents some of the known cases in which either the default behaviour may require tweaking or alternatives to flow queueing should be considered.
FQ-CoDelは多くのシナリオで示され、代替のキュー管理戦略と比較して大幅なパフォーマンスの向上を提供していますが、一部のシナリオでは、特にスケジューリングアルゴリズムが適切ではありません。このセクションでは、デフォルトの動作で微調整が必要になるか、フローキューイングの代替手段を検討する必要がある既知のケースのいくつかを説明します。
In some parts of the network, enforcing flow-level fairness may not be desirable, or some other form of fairness may be more important. Some examples of this include an ISP that may be more interested in ensuring fairness between customers than between flows or a hosting or transit provider that wishes to ensure fairness between connecting Autonomous Systems or networks. Another issue can be that the number of simultaneous flows experienced at a particular link can be too high for flow-based fairness queueing to be effective.
ネットワークの一部の部分では、フローレベルの公平性を強制することが望ましくない場合や、他の形式の公平性がより重要な場合があります。このいくつかの例には、接続する自律システムまたはネットワーク間の公平性を確保したいフロー間またはホスティングまたはトランジットプロバイダー間よりも顧客間の公平性を確保することに関心があるISPが含まれます。別の問題として、特定のリンクで同時に発生するフローの数が多すぎて、フローベースのフェアネスキューイングが効果的でない場合があります。
Whatever the reason, in a scenario where fairness between flows is not desirable, reconfiguring FQ-CoDel to match on a different characteristic can be a way forward. The implementation in Linux can leverage the packet matching mechanism of the "tc" subsystem to use any available packet field to partition packets into virtual queues, for instance, to match on address or subnet source/destination pairs, application-layer characteristics, etc.
理由が何であれ、フロー間の公平性が望ましくないシナリオでは、FQ-CoDelを再構成して別の特性に一致させることで、前進することができます。 Linuxでの実装では、「tc」サブシステムのパケットマッチングメカニズムを利用して、任意の利用可能なパケットフィールドを使用して、パケットを仮想キューに分割します。たとえば、アドレスまたはサブネットの送信元/宛先のペア、アプリケーションレイヤーの特性などをマッチングします。
Furthermore, as commonly deployed today, FQ-CoDel is used with three or more tiers of service classification, based on Diffserv markings: priority, best effort, and background. Some products do more detailed classification, including deep packet inspection and destination-specific filters to achieve their desired result.
さらに、FQ-CoDelは、今日一般的に展開されているように、Diffservマーキングに基づいて、優先度、ベストエフォート、バックグラウンドの3層以上のサービス分類で使用されます。一部の製品は、詳細なパケット検査や宛先固有のフィルターなど、より詳細な分類を行って、目的の結果を達成します。
Where possible, FQ-CoDel will attempt to decapsulate packets before matching on the header fields for the flow hashing. However, for some encapsulation techniques, most notably encrypted VPNs, this is not possible. If several flows are bunched into one such encapsulated tunnel, they will be seen as one flow by the FQ-CoDel algorithm. This means that they will share a queue and drop behaviour, so flows inside the encapsulation will not benefit from the implicit prioritisation of FQ-CoDel but will continue to benefit from the reduced overall queue length from the CoDel algorithm operating on the queue. In addition, when such an encapsulated bunch competes against other flows, it will count as one flow and not assigned a share of the bandwidth based on how many flows are inside the encapsulation.
可能な場合、FQ-CoDelは、フローハッシングのヘッダーフィールドで照合する前に、パケットのカプセル化を解除しようとします。ただし、一部のカプセル化技術、特に暗号化されたVPNでは、これは不可能です。複数のフローがそのようなカプセル化されたトンネルにまとめられている場合、FQ-CoDelアルゴリズムでは1つのフローと見なされます。つまり、それらはキューを共有して動作をドロップするため、カプセル化内のフローはFQ-CoDelの暗黙的な優先順位付けのメリットを享受しませんが、キューで動作するCoDelアルゴリズムにより全体的なキューの長さを短縮することでメリットを継続します。さらに、そのようなカプセル化されたバンチが他のフローと競合する場合、それは1つのフローとしてカウントされ、カプセル化内にあるフローの数に基づいて帯域幅のシェアは割り当てられません。
Depending on the application, this may or may not be desirable behaviour. In cases where it is not, changing FQ-CoDel's matching to not be flow-based (as detailed in the previous subsection above) can be a mitigation. Going forward, having some mechanism for opaque encapsulations to express to the outer layer which flow a packet belongs to could be a way to mitigate this. Naturally, care needs to be taken when designing such a mechanism to ensure no new privacy and security issues are raised by exposing information from inside the encapsulation to the outside world. Keeping the extra information out of band and dropping it before it hits the network could be one way to achieve this.
アプリケーションによっては、これは望ましい動作である場合とそうでない場合があります。そうでない場合は、FQ-CoDelのマッチングをフローベースではないように変更する（上記の前のサブセクションで詳細を説明したように）と、軽減することができます。今後、不透明なカプセル化がパケットが属するフローを外側のレイヤーに表現するための何らかのメカニズムを持つことは、これを軽減する方法になる可能性があります。当然のことながら、カプセル化の内側から外部の世界に情報を公開することによって新しいプライバシーとセキュリティの問題が発生しないように、このようなメカニズムを設計するときは注意が必要です。追加情報を帯域外に保ち、ネットワークに到達する前に削除することは、これを達成する1つの方法である可能性があります。
In the presence of queue management schemes that limit latency under load, low-priority congestion control algorithms such as Low Extra Delay Background Transport (LEDBAT) [RFC6817] (or, in general, algorithms that try to voluntarily use up less than their fair share of bandwidth) experience little added latency when the link is congested. Thus, they lack the signal to back off that added latency previously afforded them. This effect is seen with FQ-CoDel as well as with any effective AQM [GONG2014].
負荷下での待ち時間を制限するキュー管理スキームが存在する場合、低エクストラ遅延バックグラウンドトランスポート（LEDBAT）[RFC6817]などの低優先度の輻輳制御アルゴリズム（または、一般的に、フェアシェアよりも少ない量を自発的に使用しようとするアルゴリズム）帯域幅）リンクが混雑している場合、追加の遅延はほとんど発生しません。そのため、以前は追加されていたレイテンシが原因であった遅延を後退させる信号がありません。この効果は、FQ-CoDelだけでなく、有効なAQM [GONG2014]でも見られます。
As such, these delay-based algorithms tend to revert to loss-based congestion control and will consume the fair share of bandwidth afforded to them by the FQ-CoDel scheduler. However, low-priority congestion control mechanisms may be able to take steps to continue to be low priority, for instance, by taking into account the vastly reduced level of delay afforded by an AQM or by using a coupled approach to observing the behaviour of multiple flows.
そのため、これらの遅延ベースのアルゴリズムは、損失ベースの輻輳制御に戻る傾向があり、FQ-CoDelスケジューラによって提供される帯域幅の公平なシェアを消費します。ただし、低優先度の輻輳制御メカニズムは、たとえば、AQMによってもたらされる大幅に削減された遅延レベルを考慮することによって、または複数の動作を観察するための結合アプローチを使用することによって、低優先度であり続けるための措置を講じることができる場合があります流れ。
The FQ-CoDel algorithm as described in this document has been shipped as part of the Linux kernel since version 3.5 (released on the 21st of July, 2012), with the ce_threshold being added in version 4.2. The algorithm has seen widespread testing in a variety of contexts and is configured as the default queueing discipline in a number of mainline Linux distributions (as of this writing, at least OpenWRT, Arch Linux, and Fedora). In addition, a BSD implementation is available. All data resulting from these trials have shown FQ-CoDel to be a massive improvement over the previous default FIFO queue, and people are encouraged to turn it on.
このドキュメントで説明されているFQ-CoDelアルゴリズムは、バージョン3.5（2012年7月21日にリリース）からLinuxカーネルの一部として出荷されており、ce_thresholdはバージョン4.2で追加されています。このアルゴリズムはさまざまな状況で広範囲にテストされており、多くの主要なLinuxディストリビューション（これを書いている時点では、少なくともOpenWRT、Arch Linux、およびFedora）のデフォルトのキューイング規則として構成されています。さらに、BSD実装が利用可能です。これらの試験から得られたすべてのデータは、FQ-CoDelが以前のデフォルトのFIFOキューよりも大幅に改善されていることを示しており、これをオンにすることをお勧めします。
Of course, there is always room for improvement, and this document has listed some of the known limitations of the algorithm. As such, we encourage further research into algorithm refinements and addressing of limitations. One such effort has been undertaken by the bufferbloat community in the form of the Cake queue management scheme [CAKE]. In addition to this, we believe the following (non-exhaustive) list of issues to be worthy of further enquiry:
もちろん、改善の余地は常にあります。このドキュメントでは、アルゴリズムの既知の制限のいくつかをリストしています。そのため、アルゴリズムの改良と制限の対処についてさらに調査することをお勧めします。そのような取り組みの1つは、Cakeキュー管理スキーム[CAKE]の形でbufferbloatコミュニティによって行われています。これに加えて、次の（網羅的ではない）問題のリストは、さらに調査する価値があると考えています。
o Variations on the flow classification mechanism to fit different notions of flows. For instance, an ISP might want to deploy per-subscriber scheduling, while in other cases, several flows can share a 5-tuple, as exemplified by the RTCWEB QoS recommendations [WEBRTC-QOS].
o フローのさまざまな概念に適合するためのフロー分類メカニズムのバリエーション。たとえば、ISPはサブスクライバごとのスケジューリングを導入したいかもしれませんが、RTCWEB QoS推奨[WEBRTC-QOS]で例示されているように、他の場合では、いくつかのフローが5タプルを共有できます。
o Interactions between flow queueing and delay-based congestion control algorithms and scavenger protocols.
o フローキューイングと遅延ベースの輻輳制御アルゴリズムとスカベンジャープロトコル間の相互作用。
o Other scheduling mechanisms to replace the DRR portion of the algorithm, e.g., QFQ or WFQ.
o アルゴリズムのDRR部分を置き換える他のスケジューリングメカニズム（QFQやWFQなど）。
o Sensitivity of parameters, most notably, the number of queues and the CoDel parameters.
o パラメータの感度、特にキューの数とCoDelパラメータ。
There are no specific security exposures associated with FQ-CoDel that are not also present in current FIFO systems. On the contrary, some vulnerabilities of FIFO systems are reduced with FQ-CoDel (e.g., simple minded packet floods). However, some care is needed in the implementation to ensure this is the case. These are included in the description above, but we reiterate them here:
現在のFIFOシステムにも存在しないFQ-CoDelに関連する特定のセキュリティ上の危険性はありません。逆に、FQ-CoDelを使用すると、FIFOシステムの一部の脆弱性が減少します（たとえば、単純なパケットフラッド）。ただし、これが事実であることを保証するために、実装ではいくつかの注意が必要です。これらは上記の説明に含まれていますが、ここでは繰り返し説明します。
o To prevent packets in the new queues from starving old queues, it is important that when a queue on the list of new queues empties, it is moved to _the end of_ the list of old queues. This is described at the end of Section 4.2.
o 新しいキューのパケットが古いキューを使い果たしてしまうのを防ぐには、新しいキューのリストにあるキューが空になったときに、古いキューのリストの最後に移動することが重要です。これについては、セクション4.2の最後で説明します。
o To prevent an attacker targeting a specific flow for a denial-of-service attack, the hash that maps packets to queues should not be predictable. To achieve this, FQ-CoDel salts the hash, as described in the beginning of Section 4.1. The size of the salt and the strength of the hash function is obviously a trade-off between performance and security. The Linux implementation uses a 32-bit random value as the salt and a Jenkins hash function. This makes it possible to achieve high throughput, and we consider it sufficient to ward off the most obvious attacks.
o 攻撃者がサービス拒否攻撃の特定のフローを標的とすることを防ぐために、パケットをキューにマッピングするハッシュは予測可能であってはなりません。これを実現するために、セクション4.1の冒頭で説明したように、FQ-CoDelはハッシュをソルトします。ソルトのサイズとハッシュ関数の強さは、明らかにパフォーマンスとセキュリティのトレードオフです。 Linuxの実装では、ソルトおよびJenkinsハッシュ関数として32ビットのランダム値を使用します。これにより、高いスループットを達成することが可能になり、最も明白な攻撃を防ぐのに十分であると考えています。
o Packet fragments without a Layer 4 header can be hashed into different bins than the first fragment with the header intact. This can cause reordering and/or adversely affect the performance of the flow. Keeping state to match the fragments to the beginning of the packet or simply putting all packet fragments (including the first fragment of each fragmented packet) into the same queue are two ways to alleviate this.
o レイヤ4ヘッダーのないパケットフラグメントは、ヘッダーが損なわれていない最初のフラグメントとは異なるビンにハッシュできます。これにより、並べ替えが発生したり、フローのパフォーマンスに悪影響を及ぼす可能性があります。フラグメントをパケットの先頭に一致させる状態を維持すること、またはすべてのパケットフラグメント（フラグメント化された各パケットの最初のフラグメントを含む）を同じキューに入れることは、これを緩和する2つの方法です。
This document does not require any IANA actions.
このドキュメントでは、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>。
[RFC7806] Baker, F. and R. Pan, "On Queuing, Marking, and Dropping", RFC 7806, DOI 10.17487/RFC7806, April 2016, <https://www.rfc-editor.org/info/rfc7806>.
[RFC7806]ベイカー、F。およびR.パン、「キューイング、マーキング、およびドロップ時」、RFC 7806、DOI 10.17487 / RFC7806、2016年4月、<https://www.rfc-editor.org/info/rfc7806> 。
[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>。
[RFC8289] Nichols, K., Jacobson, V., McGregor, A., Ed., and J. Iyengar, Ed., "Controlled Delay Active Queue Management", RFC 8289, DOI 10.17487/RFC8289, January 2018, <https://www.rfc-editor.org/info/rfc8289>.
[RFC8289] Nichols、K.、Jacobson、V.、McGregor、A。、編、およびJ. Iyengar、編、「Controlled Delay Active Queue Management」、RFC 8289、DOI 10.17487 / RFC8289、2018年1月、<https ：//www.rfc-editor.org/info/rfc8289>。
[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月。
[BLOATWEB] "Bufferbloat", <https://www.bufferbloat.net>.
[BLOATWEB]「Bufferbloat」、<https://www.bufferbloat.net>。
[BQL] Herbert, T., "bql: Byte Queue Limits", August 2011, <https://lwn.net/Articles/454378/>.
[BQL] Herbert、T。、「bql：Byte Queue Limits」、2011年8月、<https://lwn.net/Articles/454378/>。
[CAKE] "Cake - Common Applications Kept Enhanced", <http://www.bufferbloat.net/projects/codel/wiki/Cake>.
[CAKE] "Cake-Common Applications Kept Enhanced"、<http://www.bufferbloat.net/projects/codel/wiki/Cake>。
[CODEL] Nichols, K. and V. Jacobson, "Controlling Queue Delay", ACM Queue, Volume 10, Issue 5, DOI 10.1145/2208917.2209336, May 2012, <http://queue.acm.org/detail.cfm?id=2209336>.
[コード] Nichols、K。およびV. Jacobson、「Controlling Queue Delay」、ACM Queue、Volume 10、Issue 5、DOI 10.1145 / 2208917.2209336、2012年5月、<http://queue.acm.org/detail.cfm？ id = 2209336>。
[DRR] Shreedhar, M. and G. Varghese, "Efficient Fair Queueing Using Deficit Round Robin", IEEE/ACM Transactions on Networking, Volume 4, Issue 3, DOI 10.1109/90.502236, June 1996.
[DRR] Shreedhar、M。およびG. Varghese、「赤字ラウンドロビンを使用した効率的なフェアキューイング」、IEEE / ACM Transactions on Networking、Volume 4、Issue 3、DOI 10.1109 / 90.502236、1996年6月。
[DRRPP] MacGregor, M. and W. Shi, "Deficits for Bursty Latency-Critical Flows: DRR++", Proceedings of the IEEE International Conference on Networks 2000 (ICON 2000), DOI 10.1109/ICON.2000.875803, September 2000, <http://ieeexplore.ieee.org/xpls/ abs_all.jsp?arnumber=875803>.
[DRRPP] MacGregor、M。およびW. Shi、「バースト性レイテンシクリティカルフローの赤字：DRR ++」、IEEE International Conference on Networks 2000（ICON 2000）、DOI 10.1109 / ICON.2000.875803、2000年9月、<http ：//ieeexplore.ieee.org/xpls/ abs_all.jsp？arnumber = 875803>。
[GONG2014] Gong, Y., Rossi, D., Testa, C., Valenti, S., and D. Taht, "Fighting the bufferbloat: On the coexistence of AQM and low priority congestion control", Elsevier Computer Networks, Volume 65, DOI 10.1016/j.bjp.2014.01.009, June 2014, <https://www.sciencedirect.com/science/article/pii/ S1389128614000188>.
[GONG2014] Gong、Y.、Rossi、D.、Testa、C.、Valenti、S。、およびD. Taht、「バッファブロートとの戦い：AQMと低優先度の輻輳制御の共存について」、Elsevier Computer Networks、Volume 65、DOI 10.1016 / j.bjp.2014.01.009、2014年6月、<https://www.sciencedirect.com/science/article/pii/ S1389128614000188>。
[HFSC] Stoica, I., Zhang, H., and T. Eugene Ng, "A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services", Proceedings of ACM SIGCOMM, DOI 10.1145/263105.263175, September 1997, <http://conferences.sigcomm.org/sigcomm/1997/papers/ p011.pdf>.
[HFSC] Stoica、I.、Zhang、H。、およびT. Eugene Ng、「リンク共有、リアルタイム、優先サービスのための階層的公正サービス曲線アルゴリズム」、ACM SIGCOMMの議事録、DOI 10.1145 / 263105.263175、9月1997、<http://conferences.sigcomm.org/sigcomm/1997/papers/ p011.pdf>。
[HTB] Wikipedia, "Token Bucket: Variations", October 2017, <https://en.wikipedia.org/w/ index.php?title=Token_bucket&oldid=803574657>.
[HTB] Wikipedia、「Token Bucket：Variations」、2017年10月、<https://en.wikipedia.org/w/ index.php？title = Token_bucket＆oldid = 803574657>。
[JENKINS] Jenkins, B., "A Hash Function for Hash Table Lookup", <http://www.burtleburtle.net/bob/hash/doobs.html>.
[JENKINS] Jenkins、B。、「ハッシュテーブルルックアップ用のハッシュ関数」、<http://www.burtleburtle.net/bob/hash/doobs.html>。
[LINUXSRC] "Linux Kernel Source Tree", <https://git.kernel.org/cgit/l inux/kernel/git/torvalds/linux.git/tree/net/sched/ sch_fq_codel.c>.
[LINUXSRC]「Linuxカーネルソースツリー」、<https://git.kernel.org/cgit/l inux / kernel / git / torvalds / linux.git / tree / net / sched / sch_fq_codel.c>。
[NS2] "ns-2", December 2014, <http://nsnam.sourceforge.net/wiki/ index.php?title=Main_Page&oldid=8076>.
[NS2]「ns-2」、2014年12月、<http://nsnam.sourceforge.net/wiki/ index.php？title = Main_Page＆oldid = 8076>。
[NS3] "ns-3", February 2016, <https://www.nsnam.org/mediawiki/ index.php?title=Main_Page&oldid=9883>.
[NS3]「ns-3」、2016年2月、<https://www.nsnam.org/mediawiki/ index.php？title = Main_Page＆oldid = 9883>。
[QFQ] Checconi, F., Rizzo, L., and P. Valente, "QFQ: Efficient Packet Scheduling with Tight Guarantees", IEEE/ACM Transactions on Networking (TON), Volume 21, Issue 3, pp. 802-816, DOI 10.1109/TNET.2012.2215881, June 2013, <http://dl.acm.org/citation.cfm?id=2525552>.
[QFQ] Checconi、F.、Rizzo、L。、およびP. Valente、「QFQ：タイトな保証による効率的なパケットスケジューリング」、IEEE / ACM Transactions on Networking（TON）、Volume 21、Issue 3、pp。802-816 、DOI 10.1109 / TNET.2012.2215881、2013年6月、<http://dl.acm.org/citation.cfm?id=2525552>。
[RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, DOI 10.17487/RFC2003, October 1996, <https://www.rfc-editor.org/info/rfc2003>.
[RFC2003]パーキンス、C。、「IP内のIPカプセル化」、RFC 2003、DOI 10.17487 / RFC2003、1996年10月、<https://www.rfc-editor.org/info/rfc2003>。
[RFC2890] Dommety, G., "Key and Sequence Number Extensions to GRE", RFC 2890, DOI 10.17487/RFC2890, September 2000, <https://www.rfc-editor.org/info/rfc2890>.
[RFC2890] Dommety、G。、「Key and Sequence Number Extensions to GRE」、RFC 2890、DOI 10.17487 / RFC2890、2000年9月、<https://www.rfc-editor.org/info/rfc2890>。
[RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition of Explicit Congestion Notification (ECN) to IP", RFC 3168, DOI 10.17487/RFC3168, September 2001, <https://www.rfc-editor.org/info/rfc3168>.
[RFC3168]ラマクリシュナン、K。、フロイド、S。、およびD.ブラック、「IPへの明示的輻輳通知（ECN）の追加」、RFC 3168、DOI 10.17487 / RFC3168、2001年9月、<https：// www。 rfc-editor.org/info/rfc3168>。
[RFC4213] Nordmark, E. and R. Gilligan, "Basic Transition Mechanisms for IPv6 Hosts and Routers", RFC 4213, DOI 10.17487/RFC4213, October 2005, <https://www.rfc-editor.org/info/rfc4213>.
[RFC4213] Nordmark、E。およびR. Gilligan、「IPv6ホストおよびルーターの基本的な移行メカニズム」、RFC 4213、DOI 10.17487 / RFC4213、2005年10月、<https://www.rfc-editor.org/info/rfc4213 >。
[RFC6817] Shalunov, S., Hazel, G., Iyengar, J., and M. Kuehlewind, "Low Extra Delay Background Transport (LEDBAT)", RFC 6817, DOI 10.17487/RFC6817, December 2012, <https://www.rfc-editor.org/info/rfc6817>.
[RFC6817] Shalunov、S.、Hazel、G.、Iyengar、J。、およびM. Kuehlewind、「Low Extra Delay Background Transport（LEDBAT）」、RFC 6817、DOI 10.17487 / RFC6817、2012年12月、<https：// www.rfc-editor.org/info/rfc6817>。
[RFC8257] Bensley, S., Thaler, D., Balasubramanian, P., Eggert, L., and G. Judd, "Data Center TCP (DCTCP): TCP Congestion Control for Data Centers", RFC 8257, DOI 10.17487/RFC8257, October 2017, <https://www.rfc-editor.org/info/rfc8257>.
[RFC8257]ベンズリー、S。、ターラー、D。、バラブラマニアン、P。、エガート、L。、およびG.ジャッド、「Data Center TCP（DCTCP）：TCP Congestion Control for Data Centers」、RFC 8257、DOI 10.17487 / RFC8257、2017年10月、<https://www.rfc-editor.org/info/rfc8257>。
[SFQ] McKenney, P., "Stochastic Fairness Queueing", Proceedings of IEEE INFOCOM, DOI 10.1109/INFCOM.1990.91316, June 1990, <http://perso.telecom-paristech.fr/~bonald/Publications_files/BMO2011.pdf>.
[SFQ] McKenney、P。、「Stochastic Fairness Queueing」、Proceedings of IEEE INFOCOM、DOI 10.1109 / INFCOM.1990.91316、June 1990、<http://perso.telecom-paristech.fr/~bonald/Publications_files/BMO2011.pdf >。
[SQF] Carofiglio, G. and L. Muscariello, "On the Impact of TCP and Per-Flow Scheduling on Internet Performance", IEEE/ACM Transactions on Networking, Volume 20, Issue 2, DOI 10.1109/TNET.2011.2164553, August 2011.
[SQF] Carofiglio、G。およびL. Muscariello、「TCPおよびフローごとのスケジューリングがインターネットのパフォーマンスに与える影響について」、IEEE / ACM Transactions on Networking、Volume 20、Issue 2、DOI 10.1109 / TNET.2011.2164553、2011年8月。
[WEBRTC-QOS] Jones, P., Dhesikan, S., Jennings, C., and D. Druta, "DSCP Packet Markings for WebRTC QoS", Work in Progress, draft-ietf-tsvwg-rtcweb-qos-18, August 2016.
[WEBRTC-QOS]ジョーンズ、P。、デシカン、S。、ジェニングス、C。、およびD.ドルタ、「WebRTC QoSのDSCPパケットマーキング」、作業中、draft-ietf-tsvwg-rtcweb-qos-18、 2016年8月。
[WFQ] Demers, A., Keshav, S., and S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm", ACM SIGCOMM Computer Communication Review, Volume 19, Issue 4, pp. 1-12, DOI 10.1145/75247.75248, September 1989, <http://doi.acm.org/10.1145/75247.75248>.
[WFQ] Demers、A.、Keshav、S。、およびS. Shenker、「フェアキューイングアルゴリズムの分析とシミュレーション」、ACM SIGCOMM Computer Communication Review、Volume 19、Issue 4、pp。1-12、DOI 10.1145 / 75247.75248、1989年9月、<http://doi.acm.org/10.1145/75247.75248>。
Acknowledgements
謝辞
Our deepest thanks to Kathie Nichols, Van Jacobson, and all the members of the bufferbloat.net effort for all the help on developing and testing the algorithm. In addition, our thanks to Anil Agarwal for his help with getting the hash collision probabilities in this document right.
アルゴリズムの開発とテストに関するすべての支援を提供してくれたKathie Nichols、Van Jacobson、およびbufferbloat.netのすべてのメンバーに深く感謝します。さらに、このドキュメントでハッシュの衝突確率を正しく取得するために協力してくれたAnil Agarwalに感謝します。
Authors' Addresses
著者のアドレス
Toke Hoeiland-Joergensen Karlstad University Dept. of Computer Science Karlstad 65188 Sweden Email: toke@toke.dk
Toke Hoeiland-Joergensenカールスタード大学学部of Computer Science Karlstad 65188スウェーデンメール：toke@toke.dk
Paul McKenney
IBM Linux Technology Center
1385 NW Amberglen Parkway
Hillsboro, OR 97006
United States of America
Email: paulmck@linux.vnet.ibm.com
URI: http://www2.rdrop.com/~paulmck/
Dave Taht Teklibre 2104 W First street Apt 2002 FT Myers, FL 33901 United States of America Email: dave.taht@gmail.com URI: http://www.teklibre.com/
Dave That Take Libre 2104 W First street Apt 2002 FORT Myers、FL 33901 United States of Email Email：dave.taht@gmail.com URI：http://www.teklibre.com/
Jim Gettys
21 Oak Knoll Road
Carlisle, MA 993
United States of America
Email: jg@freedesktop.org
URI: https://en.wikipedia.org/wiki/Jim_Gettys
Eric Dumazet Google, Inc. 1600 Amphitheatre Pkwy Mountain View, CA 94043 United States of America Email: edumazet@gmail.com
Eric Dumazet Google、Inc. 1600 Amphitheatre Pkwy Mountain View、CA 94043 United States of Email Email：edumazet@gmail.com