[要約] 要約:RFC 8033は、バッファブロート問題に対処するための軽量な制御スキームであるPIE(Proportional Integral Controller Enhanced)について説明しています。 目的:このRFCの目的は、ネットワークの遅延やパケットロスなどの問題を解決するために、効果的なバッファ制御手法であるPIEを提案することです。

Internet Engineering Task Force (IETF)                            R. Pan
Request for Comments: 8033                                  P. Natarajan
Category: Experimental                                     Cisco Systems
ISSN: 2070-1721                                                 F. Baker
                                                            Unaffiliated
                                                                G. White
                                                               CableLabs
                                                           February 2017
        

Proportional Integral Controller Enhanced (PIE): A Lightweight Control Scheme to Address the Bufferbloat Problem

プロポーショナルインテグラルコントローラーエンハンスド(PIE):Bufferbloat問題に対処するための軽量制御スキーム

Abstract

概要

Bufferbloat is a phenomenon in which excess buffers in the network cause high latency and latency variation. As more and more interactive applications (e.g., voice over IP, real-time video streaming, and financial transactions) run in the Internet, high latency and latency variation degrade application performance. There is a pressing need to design intelligent queue management schemes that can control latency and latency variation, and hence provide desirable quality of service to users.

Bufferbloatは、ネットワーク内の過剰なバッファーが原因で、レイテンシとレイテンシの変動が大きくなる現象です。インタラクティブアプリケーション(Voi​​ce over IP、リアルタイムビデオストリーミング、金融取引など)がインターネットで実行されるにつれ、レイテンシとレイテンシの変動が大きくなり、アプリケーションのパフォーマンスが低下します。レイテンシとレイテンシの変動を制御できるインテリジェントなキュー管理スキームを設計し、それによってユーザーに望ましいサービス品質を提供することが急務です。

This document presents a lightweight active queue management design called "PIE" (Proportional Integral controller Enhanced) that can effectively control the average queuing latency to a target value. Simulation results, theoretical analysis, and Linux testbed results have shown that PIE can ensure low latency and achieve high link utilization under various congestion situations. The design does not require per-packet timestamps, so it incurs very little overhead and is simple enough to implement in both hardware and software.

このドキュメントでは、「PIE」(Proportional Integral Controller Enhanced)と呼ばれる軽量のアクティブキュー管理設計を紹介します。これにより、平均キューレイテンシを目標値まで効果的に制御できます。シミュレーション結果、理論的分析、およびLinuxテストベッドの結果は、PIEがさまざまな輻輳状況下で低遅延を保証し、高いリンク使用率を達成できることを示しています。この設計はパケットごとのタイムスタンプを必要としないため、オーバーヘッドはほとんど発生せず、ハードウェアとソフトウェアの両方に実装できるほど単純です。

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 http://www.rfc-editor.org/info/rfc8033.

このドキュメントの現在のステータス、正誤表、およびフィードバックの提供方法に関する情報は、http://www.rfc-editor.org/info/rfc8033で入手できます。

Copyright Notice

著作権表示

Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved.

Copyright(c)2017 IETF Trustおよびドキュメントの作成者として識別された人物。全著作権所有。

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://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トラストの法的規定(http://trustee.ietf.org/license-info)の対象であり、この文書の発行日に有効です。これらのドキュメントは、このドキュメントに関するあなたの権利と制限を説明しているため、注意深く確認してください。このドキュメントから抽出されたコードコンポーネントには、Trust Legal Provisionsのセクション4.eに記載されているSimplified BSD Licenseのテキストが含まれている必要があり、Simplified BSD Licenseに記載されているように保証なしで提供されます。

Table of Contents

目次

   1. Introduction ....................................................3
   2. Terminology .....................................................5
   3. Design Goals ....................................................5
   4. The Basic PIE Scheme ............................................6
      4.1. Random Dropping ............................................7
      4.2. Drop Probability Calculation ...............................7
      4.3. Latency Calculation ........................................9
      4.4. Burst Tolerance ...........................................10
   5. Optional Design Elements of PIE ................................11
      5.1. ECN Support ...............................................11
      5.2. Dequeue Rate Estimation ...................................11
      5.3. Setting PIE Active and Inactive ...........................13
      5.4. Derandomization ...........................................14
      5.5. Cap Drop Adjustment .......................................15
   6. Implementation Cost ............................................15
   7. Scope of Experimentation .......................................17
   8. Incremental Deployment .........................................17
   9. Security Considerations ........................................18
   10. References ....................................................18
      10.1. Normative References .....................................18
      10.2. Informative References ...................................18
   Appendix A. The Basic PIE Pseudocode ..............................21
   Appendix B. Pseudocode for PIE with Optional Enhancement ..........24
   Contributors ......................................................29
   Authors' Addresses ................................................30
        
1. Introduction
1. はじめに

The explosion of smart phones, tablets, and video traffic in the Internet brings about a unique set of challenges for congestion control. To avoid packet drops, many service providers or data-center operators require vendors to put in as much buffer as possible. Because of the rapid decrease in memory chip prices, these requests are easily accommodated to keep customers happy. While this solution succeeds in assuring low packet loss and high TCP throughput, it suffers from a major downside. TCP continuously increases its sending rate and causes network buffers to fill up. TCP cuts its rate only when it receives a packet drop or mark that is interpreted as a congestion signal. However, drops and marks usually occur when network buffers are full or almost full. As a result, excess buffers, initially designed to avoid packet drops, would lead to highly elevated queuing latency and latency variation. Designing a queue management scheme is a delicate balancing act: it not only should allow short-term bursts to smoothly pass but also should control the average latency in the presence of long-running greedy flows.

スマートフォン、タブレット、およびインターネットでのビデオトラフィックの爆発的な増加は、輻輳制御に固有の一連の課題をもたらします。パケットドロップを回避するために、多くのサービスプロバイダーまたはデータセンターオペレーターは、ベンダーにできるだけ多くのバッファーを配置するように要求しています。メモリチップの価格が急速に下がっているので、これらの要求は顧客を満足させるために簡単に対応できます。このソリューションは、パケット損失を少なくし、TCPスループットを高くすることに成功していますが、大きな欠点があります。 TCPは送信レートを継続的に増加させ、ネットワークバッファをいっぱいにします。 TCPは、輻輳信号として解釈されるパケットドロップまたはマークを受信した場合にのみ、レートを削減します。ただし、ドロップとマークは通常、ネットワークバッファがいっぱいまたはほとんどいっぱいのときに発生します。その結果、最初はパケットのドロップを回避するように設計された過剰なバッファが原因で、キューの待機時間と待機時間の変動が非常に高くなります。キュー管理スキームの設計は、微妙なバランスをとる行為です。短期バーストをスムーズに通過させるだけでなく、長時間実行される貪欲なフローが存在する場合の平均レイテンシも制御する必要があります。

Active Queue Management (AQM) schemes could potentially solve the aforementioned problem. AQM schemes, such as Random Early Detection (RED) [RED] as suggested in [RFC2309] (which is now obsoleted by [RFC7567]), have been around for well over a decade. RED is implemented in a wide variety of network devices, both in hardware and software. Unfortunately, due to the fact that RED needs careful tuning of its parameters for various network conditions, most network operators don't turn RED on. In addition, RED is designed to control the queue length, which would affect latency implicitly. It does not control latency directly. Hence, the Internet today still lacks an effective design that can control buffer latency to improve the quality of experience to latency-sensitive applications. The more recently published RFC 7567 calls for new methods of controlling network latency.

アクティブキュー管理(AQM)スキームは、前述の問題を解決できる可能性があります。 [RFC2309]([RFC7567]で廃止された)で提案されているランダム早期検出(RED)[RED]などのAQMスキームは、10年以上前から存在しています。 REDは、ハードウェアとソフトウェアの両方で、さまざまなネットワークデバイスに実装されています。残念ながら、REDはさまざまなネットワーク条件に合わせてパラメーターを注意深く調整する必要があるため、ほとんどのネットワークオペレーターはREDをオンにしません。さらに、REDはキューの長さを制御するように設計されています。これは暗黙的にレイテンシに影響します。レイテンシを直接制御することはありません。したがって、今日のインターネットには、遅延の影響を受けやすいアプリケーションのエクスペリエンス品質を向上させるためにバッファの遅延を制御できる効果的な設計がまだありません。最近公開されたRFC 7567では、ネットワーク遅延を制御する新しい方法が必要です。

New algorithms are beginning to emerge to control queuing latency directly to address the bufferbloat problem [CoDel]. Along these lines, Proportional Integral controller Enhanced (PIE) also aims to keep the benefits of RED, including easy implementation and scalability to high speeds. Similar to RED, PIE randomly drops an incoming packet at the onset of congestion. Congestion detection, however, is based on the queuing latency instead of the queue length (as with RED). Furthermore, PIE also uses the derivative (rate of change) of the queuing latency to help determine congestion levels and an appropriate response. The design parameters of PIE are chosen via control theory stability analysis. While these parameters can be fixed to work in various traffic conditions, they could be made self-tuning to optimize system performance.

新しいアルゴリズムが登場し、キューイングレイテンシを直接制御して、バッファブロート問題に対処します[CoDel]。これらの方針に沿って、プロポーショナルインテグラルコントローラーエンハンスド(PIE)は、簡単な実装や高速へのスケーラビリティなど、REDの利点を維持することも目的としています。 REDと同様に、PIEは輻輳の開始時に着信パケットをランダムにドロップします。ただし、輻輳検出は、キューの長さ(REDと同様)ではなく、キューの待機時間に基づいています。さらに、PIEはキューイングレイテンシの導関数(変化率)も使用して、輻輳レベルと適切な応答を決定します。 PIEの設計パラメータは、制御理論の安定性解析によって選択されます。これらのパラメータは、さまざまな交通状況で機能するように修正できますが、システムパフォーマンスを最適化するために自己調整することができます。

Separately, it is assumed that any latency-based AQM scheme would be applied over a Fair Queuing (FQ) structure or one of its approximate designs, Flow Queuing or Class-Based Queuing (CBQ). FQ is one of the most studied scheduling algorithms since it was first proposed in 1985 [RFC970]. CBQ has been a standard feature in most network devices today [CBQ]. Any AQM scheme that is built on top of FQ or CBQ could benefit from these advantages. Furthermore, these advantages, such as per-flow or per-class fairness, are orthogonal to the AQM design whose primary goal is to control latency for a given queue. For flows that are classified into the same class and put into the same queue, one needs to ensure that their latency is better controlled and that their fairness is not worse than those under the standard DropTail or RED design. More details about the relationship between FQ and AQM can be found in [RFC7806].

これとは別に、レイテンシベースのAQMスキームは、フェアキューイング(FQ)構造またはその近似設計の1つであるフローキューイングまたはクラスベースキューイング(CBQ)に適用されると想定されています。 FQは、1985年に最初に提案されて以来、最も研究されているスケジューリングアルゴリズムの1つです[RFC970]。 CBQは、今日のほとんどのネットワークデバイスの標準機能です[CBQ]。 FQまたはCBQの上に構築されたAQMスキームはすべて、これらの利点の恩恵を受けることができます。さらに、フローごとやクラスごとの公平性などのこれらの利点は、特定のキューのレイテンシを制御することを主な目的とするAQM設計に直交しています。同じクラスに分類され、同じキューに入れられるフローの場合、レイテンシがより適切に制御され、公平性が標準のDropTailまたはRED設計のフローよりも悪くないことを確認する必要があります。 FQとAQMの関係の詳細については、[RFC7806]を参照してください。

In October 2013, CableLabs' Data-Over-Cable Service Interface Specification 3.1 (DOCSIS 3.1) specification [DOCSIS_3.1] mandated that cable modems implement a specific variant of the PIE design as the active queue management algorithm. In addition to cable-specific improvements, the PIE design in DOCSIS 3.1 [RFC8034] has improved the original design in several areas, including derandomization of coin tosses and enhanced burst protection.

2013年10月、CableLabsのData-Over-Cable Service Interface Specification 3.1(DOCSIS 3.1)仕様[DOCSIS_3.1]は、ケーブルモデムがPIE設計の特定のバリアントをアクティブキュー管理アルゴリズムとして実装することを義務付けました。ケーブル固有の改善に加えて、DOCSIS 3.1 [RFC8034]のPIE設計は、コイントスの非ランダム化や強化されたバースト保護など、いくつかの領域で元の設計を改善しました。

This document describes the design of PIE and separates it into basic elements and optional components that may be implemented to enhance the performance of PIE.

このドキュメントでは、PIEの設計について説明し、PIEのパフォーマンスを向上させるために実装できる基本要素とオプションコンポーネントに分けています。

2. Terminology
2. 用語

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

このドキュメントのキーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「MAY」、および「OPTIONAL」は、 RFC 2119 [RFC2119]で説明されているように解釈されます。

3. Design Goals
3. 設計目標

A queue management framework is designed to improve the performance of interactive and latency-sensitive applications. It should follow the general guidelines set by the AQM working group document "IETF Recommendations Regarding Active Queue Management" [RFC7567]. More specifically, the PIE design has the following basic criteria.

キュー管理フレームワークは、対話型で遅延の影響を受けやすいアプリケーションのパフォーマンスを向上させるように設計されています。これは、AQMワーキンググループドキュメント「アクティブキュー管理に関するIETFの推奨事項」[RFC7567]で設定された一般的なガイドラインに従う必要があります。具体的には、PIE設計には次の基本的な基準があります。

* First, queuing latency, instead of queue length, is controlled. Queue sizes change with queue draining rates and various flows' round-trip times. Latency bloat is the real issue that needs to be addressed, as it impairs real-time applications. If latency can be controlled, bufferbloat is not an issue. In fact, once latency is under control, it frees up buffers for sporadic bursts.

* まず、キューの長さではなく、キューの待機時間が制御されます。キューのサイズは、キューの排出速度とさまざまなフローの往復時間によって変化します。レイテンシー膨張は、リアルタイムアプリケーションを損なうため、対処する必要のある実際の問題です。レイテンシを制御できれば、バッファブロートは問題になりません。実際、レイテンシが制御下になると、散発的なバーストのためにバッファが解放されます。

* Secondly, PIE aims to attain high link utilization. The goal of low latency shall be achieved without suffering link underutilization or losing network efficiency. An early congestion signal could cause TCP to back off and avoid queue buildup. On the other hand, however, TCP's rate reduction could result in link underutilization. There is a delicate balance between achieving high link utilization and low latency.

* 次に、PIEは高いリンク使用率を達成することを目的としています。リンクの使用率が低下したり、ネットワーク効率が低下したりすることなく、低遅延の目標を達成する必要があります。初期の輻輳信号により、TCPがバックオフし、キューの増加を回避できます。ただし、その一方で、TCPのレート削減により、リンクの使用率が低下する可能性があります。高いリンク使用率と低遅延の実現には微妙なバランスがあります。

* Furthermore, the scheme should be simple to implement and easily scalable in both hardware and software. PIE strives to maintain design simplicity similar to that of RED, which has been implemented in a wide variety of network devices.

* さらに、このスキームは実装が簡単で、ハードウェアとソフトウェアの両方で簡単に拡張できる必要があります。 PIEは、さまざまなネットワークデバイスに実装されているREDと同様の設計のシンプルさを維持するよう努めています。

* Finally, the scheme should ensure system stability for various network topologies and scale well across an arbitrary number of streams. Design parameters shall be set automatically. Users only need to set performance-related parameters such as target queue latency, not design parameters.

* 最後に、このスキームは、さまざまなネットワークトポロジのシステムの安定性を確保し、任意の数のストリームにわたって適切に拡張する必要があります。設計パラメータは自動的に設定されます。ユーザーは、設計パラメーターではなく、ターゲットキューのレイテンシなどのパフォーマンス関連のパラメーターを設定するだけで済みます。

In the following text, the design of PIE and its operation are described in detail.

次のテキストでは、PIEの設計とその操作について詳しく説明します。

4. The Basic PIE Scheme
4. 基本的なPIEスキーム

As illustrated in Figure 1, PIE is comprised of three simple basic components: a) random dropping at enqueuing, b) periodic drop probability updates, and c) latency calculation. When a packet arrives, a random decision is made regarding whether to drop the packet. The drop probability is updated periodically based on how far the current latency is away from the target value and whether the queuing latency is currently trending up or down. The queuing latency can be obtained using direct measurements or using estimations calculated from the queue length and the dequeue rate.

図1に示すように、PIEは3つの単純な基本コンポーネントで構成されています。a)エンキュー時のランダムドロップ、b)定期的なドロップ確率の更新、c)レイテンシの計算パケットが到着すると、パケットをドロップするかどうかに関してランダムな決定が行われます。ドロップ確率は、現在のレイテンシが目標値からどれだけ離れているか、およびキューイングレイテンシが現在上昇傾向か下降傾向かに基づいて定期的に更新されます。キューイング待ち時間は、直接測定を使用して、またはキューの長さとデキュー率から計算された推定を使用して取得できます。

The detailed definition of parameters can be found in Appendix A of this document ("The Basic PIE Pseudocode"). Any state variables that PIE maintains are noted using "PIE->". For a full description of the algorithm, one can refer to the full paper [HPSR-PIE].

パラメータの詳細な定義は、このドキュメントの付録A(「基本的なPIE擬似コード」)にあります。 PIEが維持するすべての状態変数は、「PIE->」を使用して示されます。アルゴリズムの詳細については、論文[HPSR-PIE]を参照してください。

         Random Drop
              /               --------------
      -------/  -------------->    | | | | | -------------->
             /|\                   | | | | |
              |               --------------
              |             Queue Buffer   \
              |                     |       \
              |                     |Queue   \
              |                     |Length   \
              |                     |          \
              |                    \|/         \/
              |          -----------------    -------------------
              |          |     Drop      |    |                 |
              -----<-----|  Probability  |<---| Latency         |
                         |  Calculation  |    | Calculation     |
                         -----------------    -------------------
        

Figure 1: The PIE Structure

図1:PIE構造

4.1. Random Dropping
4.1. ランダムドロップ

PIE randomly drops a packet upon its arrival to a queue according to a drop probability, PIE->drop_prob_, that is obtained from the drop-probability-calculation component. The random drop is triggered by a packet's arrival before enqueuing into a queue.

PIEは、ドロップ確率計算コンポーネントから取得されるドロップ確率PIE-> drop_prob_に従って、パケットがキューに到着するとランダムにドロップします。ランダムドロップは、キューにエンキューする前のパケットの到着によってトリガーされます。

* Upon a packet enqueue:

* パケットがキューに入ると:

randomly drop the packet with a probability of PIE->drop_prob_.

PIE-> drop_prob_の確率でパケットをランダムにドロップします。

To ensure that PIE is "work conserving", we bypass the random drop if the latency sample, PIE->qdelay_old_, is smaller than half of the target latency value (QDELAY_REF) when the drop probability is not too high (i.e., PIE->drop_prob_ < 0.2), or if the queue has less than a couple of packets.

ドロップ確率が高すぎない場合(つまり、PIE-)、レイテンシサンプルPIE-> qdelay_old_がターゲットレイテンシ値(QDELAY_REF)の半分より小さい場合、PIEが「作業節約」であることを確認するために、ランダムドロップをバイパスします。 > drop_prob_ <0.2)、またはキューのパケット数が少ない場合。

* Upon a packet enqueue, PIE does the following:

* パケットエンキュー時に、PIEは次のことを行います。

//Safeguard PIE to be work conserving if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2) || (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) return ENQUE; else randomly drop the packet with a probability of PIE->drop_prob_.

//((PIE-> qdelay_old_ <QDELAY_REF / 2 && PIE-> drop_prob_ <0.2)||(queue_.byte_length()<= 2 * MEAN_PKTSIZE))return ENQUE;それ以外の場合は、PIE-> drop_prob_の確率でパケットをランダムにドロップします。

PIE optionally supports Explicit Congestion Notification (ECN); see Section 5.1.

PIEはオプションで明示的輻輳通知(ECN)をサポートします。セクション5.1を参照してください。

4.2. Drop Probability Calculation
4.2. ドロップ確率計算

The PIE algorithm periodically updates the drop probability based on the latency samples -- not only the current latency sample but also whether the latency is trending up or down. This is the classical Proportional Integral (PI) controller method, which is known for eliminating steady-state errors. This type of controller has been studied before for controlling the queue length [PI] [QCN]. PIE adopts the PI controller for controlling latency. The algorithm also auto-adjusts the control parameters based on how heavy the congestion is, which is reflected in the current drop probability. Note that the current drop probability is a direct measure of the current congestion level; there is no need to measure the arrival rate and dequeue rate mismatches.

PIEアルゴリズムは、レイテンシサンプル(現在のレイテンシサンプルだけでなく、レイテンシが上昇傾向か下降傾向か)に基づいて定期的にドロップ確率を更新します。これは、定常誤差をなくすことで知られている、古典的な比例積分(PI)コントローラー法です。このタイプのコントローラーは、キューの長さ[PI] [QCN]を制御するために以前に研究されています。 PIEは、レイテンシを制御するためにPIコントローラーを採用しています。アルゴリズムはまた、現在のドロップ確率に反映される輻輳の重さに基づいて制御パラメーターを自動調整します。現在のドロップ確率は、現在の輻輳レベルの直接的な尺度であることに注意してください。到着率とデキュー率の不一致を測定する必要はありません。

When a congestion period ends, we might be left with a high drop probability with light packet arrivals. Hence, the PIE algorithm includes a mechanism by which the drop probability decays exponentially (rather than linearly) when the system is not congested. This would help the drop probability converge to 0 more quickly, while the PI controller ensures that it would eventually reach zero. The decay parameter of 2% gives us a time constant around 50 * T_UPDATE.

輻輳期間が終了すると、パケットの到着が軽く、ドロップ確率が高くなる可能性があります。したがって、PIEアルゴリズムには、システムが輻輳していないときに、ドロップ確率が(線形ではなく)指数関数的に減衰するメカニズムが含まれています。これにより、ドロップ確率がより速く0に収束するのに役立ちますが、PIコントローラーは最終的にゼロに到達することを保証します。減衰パラメータが2%の場合、時定数は約50 * T_UPDATEになります。

Specifically, the PIE algorithm periodically adjusts the drop probability every T_UPDATE interval:

具体的には、PIEアルゴリズムはT_UPDATE間隔ごとに定期的に廃棄確率を調整します。

* calculate drop probability PIE->drop_prob_, and autotune it as follows:

* ドロップ確率PIE-> drop_prob_を計算し、次のように自動調整します。

         p = alpha * (current_qdelay - QDELAY_REF) +
                beta * (current_qdelay - PIE->qdelay_old_);
        
         if (PIE->drop_prob_ < 0.000001) {
             p /= 2048;
         } else if (PIE->drop_prob_ < 0.00001) {
             p /= 512;
         } else if (PIE->drop_prob_ < 0.0001) {
             p /= 128;
         } else if (PIE->drop_prob_ < 0.001) {
             p /= 32;
         } else if (PIE->drop_prob_ < 0.01) {
             p /= 8;
         } else if (PIE->drop_prob_ < 0.1) {
             p /= 2;
         } else {
             p = p;
         }
         PIE->drop_prob_ += p;
        

* decay the drop probability exponentially:

* ドロップ確率を指数関数的に減衰させます。

         if (current_qdelay == 0 && PIE->qdelay_old_ == 0) {
             PIE->drop_prob_ = PIE->drop_prob_ * 0.98;
                                                 //1 - 1/64 is
                                                 //sufficient
         }
        

* bound the drop probability:

* 落下確率の限界:

         if (PIE->drop_prob_ < 0)
                  PIE->drop_prob_ = 0.0
         if (PIE->drop_prob_ > 1)
                  PIE->drop_prob_ = 1.0
        

* store the current latency value:

* 現在のレイテンシ値を保存します。

PIE->qdelay_old_ = current_qdelay.

PIE-> qdelay_old_ = current_qdelay。

The update interval, T_UPDATE, is defaulted to be 15 milliseconds. It MAY be reduced on high-speed links in order to provide smoother response. The target latency value, QDELAY_REF, SHOULD be set to 15 milliseconds. The variables current_qdelay and PIE->qdelay_old_ represent the current and previous samples of the queuing latency, which are calculated by the "latency calculation" component (see Section 4.3). The variable current_qdelay is actually a temporary variable, while PIE->qdelay_old_ is a state variable that PIE keeps. The drop probability is a value between 0 and 1. However, implementations can certainly use integers.

更新間隔T_UPDATEのデフォルトは15ミリ秒です。より高速な応答を提供するために、高速リンクでは削減される場合があります。ターゲットレイテンシ値、QDELAY_REF、は15ミリ秒に設定する必要があります。変数current_qdelayおよびPIE-> qdelay_old_は、「レイテンシ計算」コンポーネントによって計算されるキューイングレイテンシの現在および以前のサンプルを表します(セクション4.3を参照)。変数current_qdelayは実際には一時変数ですが、PIE-> qdelay_old_はPIEが保持する状態変数です。ドロップ確率は0​​〜1の値です。ただし、実装では整数を使用できます。

The controller parameters, alpha and beta (expressed in Hz), are designed using feedback loop analysis, where TCP's behaviors are modeled using the results from well-studied prior art [TCP-Models]. Note that the above adjustment of 'p' effectively scales the alpha and beta parameters based on the current congestion level indicated by the drop probability.

コントローラパラメータのアルファとベータ(Hzで表現)は、フィードバックループ分析を使用して設計されます。TCPの動作は、十分に研究された従来の[TCPモデル]の結果を使用してモデル化されます。上記の「p」の調整は、ドロップ確率によって示される現在の輻輳レベルに基づいてアルファおよびベータパラメーターを効果的にスケーリングすることに注意してください。

The theoretical analysis of PIE can be found in [HPSR-PIE]. As a rule of thumb, to keep the same feedback loop dynamics, if we cut T_UPDATE in half, we should also cut alpha by half and increase beta by alpha/4. If the target latency is reduced, e.g., for data-center use, the values of alpha and beta should be increased by the same order of magnitude by which the target latency is reduced. For example, if QDELAY_REF is reduced and changed from 15 milliseconds to 150 microseconds -- a reduction of two orders of magnitude -- then alpha and beta values should be increased to alpha * 100 and beta * 100.

PIEの理論的分析は[HPSR-PIE]にあります。経験則として、同じフィードバックループのダイナミクスを維持するには、T_UPDATEを半分に削減する場合、アルファを半分に削減し、ベータをalpha / 4だけ増やす必要があります。データセンターで使用する場合など、ターゲットレイテンシが減少する場合、アルファとベータの値は、ターゲットレイテンシが減少するのと同じ桁数だけ増加する必要があります。たとえば、QDELAY_REFが15ミリ秒から150マイクロ秒に減少し、2桁減少すると、アルファ値とベータ値はアルファ* 100とベータ* 100に増加する必要があります。

4.3. Latency Calculation
4.3. 待ち時間の計算

The PIE algorithm uses latency to calculate drop probability in one of two ways:

PIEアルゴリズムはレイテンシを使用して、ドロップ確率を次の2つの方法のいずれかで計算します。

* It estimates the current queuing latency using Little's law (see Section 5.2 for details):

* リトルの法則を使用して、現在のキュー待機時間を推定します(詳細については、セクション5.2を参照)。

         current_qdelay = queue_.byte_length()/dequeue_rate;
        

* It may use other techniques for calculating queuing latency, e.g., time-stamp the packets at enqueue, and use the timestamps to calculate latency during dequeue.

* それは、キューの待ち時間を計算するために他の技術を使用するかもしれません、例えば、エンキューでパケットにタイムスタンプを付け、タイムスタンプを使ってデキューの間の待ち時間を計算します。

4.4. Burst Tolerance
4.4. バースト耐性

PIE does not penalize short-term packet bursts as suggested in [RFC7567]. PIE allows bursts of traffic that create finite-duration events in which current queuing latency exceeds QDELAY_REF without triggering packet drops. This document introduces a parameter called "MAX_BURST"; MAX_BURST defines the burst duration that will be protected. By default, the parameter SHOULD be set to 150 milliseconds. For simplicity, the PIE algorithm MAY effectively round MAX_BURST up to an integer multiple of T_UPDATE.

[RFC7567]で提案されているように、PIEは短期パケットバーストにペナルティを課しません。 PIEは、パケットのドロップをトリガーすることなく、現在のキュー待機時間がQDELAY_REFを超える有限期間イベントを作成するトラフィックのバーストを許可します。このドキュメントでは、「MAX_BURST」と呼ばれるパラメータを紹介しています。 MAX_BURSTは、保護されるバースト期間を定義します。デフォルトでは、パラメータは150ミリ秒に設定する必要があります(SHOULD)。簡単にするために、PIEアルゴリズムは、MAX_BURSTをT_UPDATEの整数倍に効果的に丸める場合があります。

To implement the burst tolerance function, two basic components of PIE are involved: "random dropping" and "drop probability calculation". The PIE algorithm does the following:

バーストトレランス機能を実装するには、PIEの2つの基本コンポーネントである「ランダムドロップ」と「ドロップ確率計算」が関係します。 PIEアルゴリズムは次のことを行います。

* In the "random dropping" block and upon packet arrival, PIE checks the following:

* 「ランダムドロップ」ブロックでパケットが到着すると、PIEは次のことをチェックします。

Upon a packet enqueue: if PIE->burst_allowance_ > 0 enqueue packet; else randomly drop a packet with a probability of PIE->drop_prob_.

パケットエンキュー時:PIE-> burst_allowance_> 0の場合、パケットをエンキューします。それ以外の場合は、確率的にPIE-> drop_prob_の確率でパケットをドロップします。

         if (PIE->drop_prob_ == 0 and current_qdelay < QDELAY_REF/2 and
             PIE->qdelay_old_ < QDELAY_REF/2)
             PIE->burst_allowance_ = MAX_BURST;
        

* In the "drop probability calculation" block, PIE additionally calculates:

* 「ドロップ確率計算」ブロックでは、PIEはさらに以下を計算します。

      PIE->burst_allowance_ = max(0,PIE->burst_allowance_ - T_UPDATE);
        

The burst allowance, noted by PIE->burst_allowance_, is initialized to MAX_BURST. As long as PIE->burst_allowance_ is above zero, an incoming packet will be enqueued, bypassing the random drop process. During each update instance, the value of PIE->burst_allowance_ is decremented by the update period, T_UPDATE, and is bottomed at 0. When the congestion goes away -- defined here as PIE->drop_prob_ equals 0 and both the current and previous samples of estimated latency are less than half of QDELAY_REF -- PIE->burst_allowance_ is reset to MAX_BURST.

PIE-> burst_allowance_で示されるバースト許容値は、MAX_BURSTに初期化されます。 PIE-> burst_allowance_がゼロより大きい限り、着信パケットはランダムドロッププロセスをバイパスしてキューに入れられます。各更新インスタンスの間、PIE-> burst_allowance_の値は更新期間T_UPDATEによって減分され、0でボトムされます。輻輳が解消すると、ここではPIE-> drop_prob_が0に等しく、現在のサンプルと以前のサンプルの両方が定義されます。推定レイテンシの半分はQDELAY_REFの半分未満です-PIE-> burst_allowance_はMAX_BURSTにリセットされます。

5. Optional Design Elements of PIE
5. PIEのオプションのデザイン要素

There are several enhancements that are added to further augment the performance of the basic algorithm. For purposes of clarity, they are included in this section.

基本的なアルゴリズムのパフォーマンスをさらに強化するために追加されたいくつかの機能強化があります。明確にするために、これらはこのセクションに含まれています。

5.1. ECN Support
5.1. ECNサポート

PIE MAY support ECN by marking (rather than dropping) ECN-capable packets [ECN]. This document introduces an additional threshold called "mark_ecnth", which acts as a safeguard: if the calculated drop probability exceeds mark_ecnth, PIE reverts to packet-dropping for ECN-capable packets. The variable mark_ecnth SHOULD be set to 0.1 (10%).

PIEは、ECN対応パケット[ECN]を(ドロップするのではなく)マークすることでECNをサポートする場合があります。このドキュメントでは、安全対策として機能する「mark_ecnth」と呼ばれる追加のしきい値を紹介します。計算された廃棄確率がmark_ecnthを超えると、PIEはECN対応パケットのパケット廃棄に戻ります。変数mark_ecnthは0.1(10%)に設定する必要があります(SHOULD)。

* To support ECN, the "random drop with a probability of PIE->drop_prob_" function in the "random dropping" block is changed to the following:

* ECNをサポートするために、「ランダムドロップ」ブロックの「PIE-> drop_prob_の確率でのランダムドロップ」関数は次のように変更されます。

* Upon a packet enqueue:

* パケットがキューに入ると:

         if rand() < PIE->drop_prob_:
          if PIE->drop_prob_ < mark_ecnth && ecn_capable_packet == TRUE:
             mark packet;
          else
             drop packet;
        
5.2. Dequeue Rate Estimation
5.2. デキュー率の見積もり

Using timestamps, a latency sample can only be obtained when a packet reaches the head of a queue. When a quick response time is desired or a direct latency sample is not available, one may obtain latency through measuring the dequeue rate. The draining rate of a queue in the network often varies either because other queues are sharing the same link or because the link capacity fluctuates. Rate fluctuation is particularly common in wireless networks. One may measure directly at the dequeue operation. Short, non-persistent bursts of packets result in empty queues from time to time; this would make the measurement less accurate. PIE only measures latency when there is sufficient data in the buffer, i.e., when the queue length is over a certain threshold (DQ_THRESHOLD). PIE measures how long it takes to drain DQ_THRESHOLD packets. More specifically, the rate estimation can be implemented as follows:

タイムスタンプを使用すると、パケットがキューの先頭に達したときにのみ遅延サンプルを取得できます。迅速な応答時間が必要な場合、または直接レイテンシサンプルが利用できない場合は、デキュー率を測定することでレイテンシを取得できます。他のキューが同じリンクを共有しているため、またはリンク容量が変動するため、ネットワーク内のキューの排出率はしばしば変動します。レート変動は、ワイヤレスネットワークで特に一般的です。デキュー操作で直接測定できます。パケットの短い非永続的なバーストにより、空のキューが発生することがあります。これにより、測定の精度が低下します。 PIEは、バッファに十分なデータがある場合、つまりキューの長さが特定のしきい値(DQ_THRESHOLD)を超えている場合にのみレイテンシを測定します。 PIEは、DQ_THRESHOLDパケットを排出するのにかかる時間を測定します。より具体的には、レート推定は次のように実装できます。

      current_qdelay = queue_.byte_length() *
                       PIE->avg_dq_time_/DQ_THRESHOLD;
        

* Upon a packet dequeue:

* パケットがキューから取り出されると:

      if PIE->in_measurement_ == FALSE and queue.byte_length() >=
      DQ_THRESHOLD:
         PIE->in_measurement_ = TRUE;
         PIE->measurement_start_ = now;
         PIE->dq_count_ = 0;
        
      if PIE->in_measurement_ == TRUE:
         PIE->dq_count_ = PIE->dq_count_ + deque_pkt_size;
         if PIE->dq_count_ >= DQ_THRESHOLD then
            weight = DQ_THRESHOLD/2^16
            PIE->avg_dq_time_ = (now - PIE->measurement_start_) *
                                weight + PIE->avg_dq_time_ *
                                (1 - weight);
            PIE->dq_count_ = 0;
            PIE->measurement_start_ = now
         else
            PIE->in_measurement_ = FALSE;
        

The parameter PIE->dq_count_ represents the number of bytes departed since the last measurement. Once PIE->dq_count_ is over DQ_THRESHOLD, a measurement sample is obtained. It is recommended that the threshold be set to 16 KB, assuming a typical packet size of around 1 KB or 1.5 KB. This threshold would allow sufficient data to obtain an average draining rate but would also be fast enough (< 64 KB) to reflect sudden changes in the draining rate. If DQ_THRESHOLD is smaller than 64 KB, a small weight is used to smooth out the dequeue time and obtain PIE->avg_dq_time_. The dequeue rate is simply DQ_THRESHOLD divided by PIE->avg_dq_time_. This threshold is not crucial for the system's stability. Please note that the update interval for calculating the drop probability is different from the rate measurement cycle. The drop probability calculation is done periodically per Section 4.2, and it is done even when the algorithm is not in a measurement cycle; in this case, the previously latched value of PIE->avg_dq_time_ is used.

パラメータPIE-> dq_count_は、最後の測定以降に離脱したバイト数を表します。 PIE-> dq_count_がDQ_THRESHOLDを超えると、測定サンプルが取得されます。一般的なパケットサイズが約1 KBまたは1.5 KBであると想定して、しきい値を16 KBに設定することをお勧めします。このしきい値により、平均的な排水速度を取得するのに十分なデータが得られますが、排水速度の突然の変化を反映するのに十分な速さ(<64 KB)になります。 DQ_THRESHOLDが64 KBより小さい場合、小さな重みを使用してデキュー時間を平滑化し、PIE-> avg_dq_time_を取得します。デキュー率は、単にDQ_THRESHOLDをPIE-> avg_dq_time_で除算したものです。このしきい値は、システムの安定性にとって重要ではありません。ドロップ確率を計算するための更新間隔は、レート測定サイクルとは異なることに注意してください。落下確率の計算はセクション4.2に従って定期的に行われ、アルゴリズムが測定サイクルにない場合でも行われます。この場合、以前にラッチされたPIE-> avg_dq_time_の値が使用されます。

            Random Drop
                /                     --------------
        -------/  -------------------->    | | | | | -------------->
               /|\             |           | | | | |
                |              |      --------------
                |              |       Queue Buffer
                |              |             |
                |              |             |Queue
                |              |             |Length
                |              |             |
                |             \|/           \|/
                |          ------------------------------
                |          |     Dequeue Rate           |
                -----<-----|  & Drop Probability        |
                           |        Calculation         |
                           ------------------------------
        

Figure 2: The Enqueue-Based PIE Structure

図2:エンキューベースのPIE構造

In some platforms, enqueuing and dequeuing functions belong to different modules that are independent of each other. In such situations, a pure enqueue-based design can be developed. An enqueue-based design is depicted in Figure 2. The dequeue rate is deduced from the number of packets enqueued and the queue length. The design is based on the following key observation: over a certain time interval, the number of dequeued packets = the number of enqueued packets minus the number of remaining packets in the queue. In this design, everything can be triggered by packet arrival, including the background update process. The design complexity here is similar to the original design.

一部のプラットフォームでは、エンキューおよびデキュー機能は、互いに独立した異なるモジュールに属しています。このような状況では、純粋なエンキューベースの設計を開発できます。エンキューベースの設計を図2に示します。デキュー率は、エンキューされたパケット数とキューの長さから推定されます。設計は、次の重要な観察に基づいています。特定の時間間隔における、デキューされたパケットの数=エンキューされたパケットの数からキュー内の残りのパケットの数を引いたもの。この設計では、バックグラウンド更新プロセスを含め、すべてがパケットの到着によってトリガーされます。ここでの設計の複雑さは、元の設計と似ています。

5.3. Setting PIE Active and Inactive
5.3. PIEをアクティブおよび非アクティブに設定

Traffic naturally fluctuates in a network. It would be preferable not to unnecessarily drop packets due to a spurious uptick in queuing latency. PIE has an optional feature of automatically becoming active/inactive. To implement this feature, PIE may choose to only become active (from inactive) when the buffer occupancy is over a certain threshold, which may be set to 1/3 of the tail drop threshold. PIE becomes inactive when congestion ends; i.e., when the drop probability reaches 0, current and previous latency samples are all below half of QDELAY_REF.

トラフィックはネットワーク内で自然に変動します。キューの待機時間の偽の増加のために、不必要にパケットをドロップしないことが望ましいでしょう。 PIEには、自動的にアクティブ/非アクティブになるオプション機能があります。この機能を実装するために、PIEは、バッファ占有率がテールドロップしきい値の1/3に設定されている可能性がある特定のしきい値を超えている場合にのみ、非アクティブからアクティブになることを選択できます。輻輳が終了すると、PIEは非アクティブになります。つまり、ドロップ確率が0に達すると、現在および以前のレイテンシサンプルはすべてQDELAY_REFの半分未満になります。

Ideally, PIE should become active/inactive based on latency. However, calculating latency when PIE is inactive would introduce unnecessary packet-processing overhead. Weighing the trade-offs, we decided to compare against the tail drop threshold to keep things simple.

理想的には、PIEは遅延に基づいてアクティブ/非アクティブになる必要があります。ただし、PIEが非アクティブのときに待ち時間を計算すると、不要なパケット処理オーバーヘッドが発生します。トレードオフを考慮して、物事を簡単に保つためにテールドロップしきい値と比較することにしました。

When PIE optionally becomes active/inactive, the burst protection logic described in Section 4.4 is modified as follows:

PIEがオプションでアクティブ/非アクティブになると、セクション4.4で説明されているバースト保護ロジックが次のように変更されます。

* "Random dropping" block: PIE adds the following:

* 「ランダムドロップ」ブロック:PIEは以下を追加します。

Upon packet arrival:

パケット到着時:

      if PIE->active_ == FALSE && queue_length >= TAIL_DROP/3:
         PIE->active_ = TRUE;
         PIE->burst_allowance_ = MAX_BURST;
        

if PIE->burst_allowance_ > 0 enqueue packet; else randomly drop a packet with a probability of PIE->drop_prob_.

PIE-> burst_allowance_> 0の場合、パケットをエンキューします。それ以外の場合は、確率的にPIE-> drop_prob_の確率でパケットをドロップします。

      if (PIE->drop_prob_ == 0 and current_qdelay < QDELAY_REF/2 and
          PIE->qdelay_old_ < QDELAY_REF/2)
          PIE->active_ = FALSE;
          PIE->burst_allowance_ = MAX_BURST;
        
   *  "Drop probability calculation" block: PIE does the following:
      if PIE->active_ == TRUE:
         PIE->burst_allowance_ =
            max(0,PIE->burst_allowance_ - T_UPDATE);
        
5.4. Derandomization
5.4. でランド三佐地温

Although PIE adopts random dropping to achieve latency control, independent coin tosses could introduce outlier situations where packets are dropped too close to each other or too far from each other. This would cause the real drop percentage to temporarily deviate from the intended value PIE->drop_prob_. In certain scenarios, such as a small number of simultaneous TCP flows, these deviations can cause significant deviations in link utilization and queuing latency. PIE may use a derandomization mechanism to avoid such situations. A parameter called "PIE->accu_prob_" is reset to 0 after a drop. Upon packet arrival, PIE->accu_prob_ is incremented by the amount of drop probability, PIE->drop_prob_. If PIE->accu_prob_ is less than a low threshold, e.g., 0.85, the arriving packet is enqueued; on the other hand, if PIE->accu_prob_ is more than a high threshold, e.g., 8.5, and the queue is congested, the arrival packet is forced to be dropped. A packet is only randomly dropped if PIE->accu_prob_ falls between the two thresholds. Since PIE->accu_prob_ is reset to 0 after a drop, another drop will not happen until 0.85/PIE->drop_prob_ packets later. This avoids packets being dropped too close to each other. In the other extreme case where 8.5/PIE->drop_prob_ packets have been enqueued without incurring a drop, PIE would force a drop in order to prevent the drops from being spaced too far apart. Further analysis can be found in [RFC8034].

PIEはランダムドロップを採用してレイテンシ制御を実現しますが、独立したコイントスは、パケットが互いに近すぎたり遠すぎたりしてドロップされるという異常な状況を引き起こす可能性があります。これにより、実際のドロップ率が一時的に意図した値PIE-> drop_prob_から逸脱します。少数の同時TCPフローなどの特定のシナリオでは、これらの偏差により、リンクの使用率とキューの待ち時間に大きな偏差が生じる可能性があります。 PIEは、このような状況を回避するために、ランダム化解除メカニズムを使用することがあります。 「PIE-> accu_prob_」というパラメーターは、ドロップ後に0にリセットされます。パケットが到着すると、PIE-> accu_prob_は、ドロップ確率の量、PIE-> drop_prob_だけインクリメントされます。 PIE-> accu_prob_が低いしきい値(0.85など)未満の場合、到着したパケットはキューに入れられます。一方、PIE-> accu_prob_が高しきい値(8.5など)を超えており、キューが混雑している場合、到着パケットは強制的にドロップされます。パケットは、PIE-> accu_prob_が2つのしきい値の間にある場合にのみランダムにドロップされます。ドロップ後、PIE-> accu_prob_は0にリセットされるため、0.85 / PIE-> drop_prob_パケットがなくなるまで、別のドロップは発生しません。これにより、パケットが互いに近づきすぎてドロップされることが回避されます。ドロップが発生せずに8.5 / PIE-> drop_prob_パケットがキューに入れられている他の極端なケースでは、PIEは強制的にドロップして、ドロップの間隔が離れすぎないようにします。さらなる分析は[RFC8034]で見つけることができます。

5.5. Cap Drop Adjustment
5.5. キャップドロップ調整

In the case of a single TCP flow, during the slow-start phase the queue could quickly increase, which could result in a very rapid increase in drop probability. In order to prevent an excessive ramp-up that could negatively impact the throughput in this scenario, PIE can cap the maximum drop probability increase in each step.

単一のTCPフローの場合、スロースタートフェーズ中にキューが急速に増加し、その結果、廃棄確率が非常に急速に増加する可能性があります。このシナリオでスループットに悪影響を与える可能性のある過度のランプアップを防ぐために、PIEは各ステップでの最大ドロップ確率の増加を制限できます。

* "Drop probability calculation" block: PIE adds the following:

* 「ドロップ確率計算」ブロック:PIEは以下を追加します。

      if (PIE->drop_prob_ >= 0.1 && p > 0.02) {
          p = 0.02;
      }
        
6. Implementation Cost
6. 実装コスト

PIE can be applied to existing hardware or software solutions. There are three steps involved in PIE, as discussed in Section 4. Their complexities are examined below.

PIEは、既存のハードウェアまたはソフトウェアソリューションに適用できます。セクション4で説明したように、PIEには3つのステップが含まれます。それらの複雑さを以下で検討します。

Upon packet arrival, the algorithm simply drops a packet randomly, based on the drop probability. This step is straightforward and requires no packet header examination and manipulation. If the implementation doesn't rely on packet timestamps for calculating latency, PIE does not require extra memory. Furthermore, the input side of a queue is typically under software control while the output side of a queue is hardware based. Hence, a drop at enqueuing can be readily retrofitted into existing or software implementations.

パケットが到着すると、アルゴリズムは、ドロップ確率に基づいて、単にパケットをランダムにドロップします。この手順は簡単で、パケットヘッダーの検査と操作は必要ありません。実装がパケットタイムスタンプに依存してレイテンシを計算しない場合、PIEは追加のメモリを必要としません。さらに、キューの入力側は通常ソフトウェア制御下にあり、キューの出力側はハードウェアベースです。したがって、エンキューの低下は、既存の実装またはソフトウェア実装に容易に組み込むことができます。

The drop probability calculation is done in the background, and it occurs every T_UPDATE interval. Given modern high-speed links, this period translates into once every tens, hundreds, or even thousands of packets. Hence, the calculation occurs at a much slower time scale than the packet-processing time -- at least an order of magnitude slower. The calculation of drop probability involves multiplications using alpha and beta. Since PIE's control law is robust to minor changes in alpha and beta values, an implementation MAY choose these values to the closest multiples of 2 or 1/2 (e.g., alpha = 1/8, beta = 1 + 1/4) such that the multiplications can be done using simple adds and shifts. As no complicated functions are required, PIE can be easily implemented in both hardware and software. The state requirement is only three variables per queue: burst_allowance_, PIE->drop_prob_, and PIE->qdelay_old_. Hence, the memory overhead is small.

ドロップ確率の計算はバックグラウンドで実行され、T_UPDATE間隔ごとに発生します。最新の高速リンクを考えると、この期間は数十、数百、または数千のパケットに1回に相当します。したがって、計算はパケット処理時間よりもはるかに遅い時間スケールで発生します-少なくとも1桁遅い。ドロップ確率の計算には、アルファとベータを使用した乗算が含まれます。 PIEの制御法則はアルファ値とベータ値のマイナーな変更に対してロバストであるため、実装はこれらの値を2または1/2の最も近い倍数(たとえば、アルファ= 1/8、ベータ= 1 + 1/4)に選択できます。乗算は、単純な加算とシフトを使用して実行できます。複雑な機能は必要ないため、PIEはハードウェアとソフトウェアの両方で簡単に実装できます。状態要件は、キューごとに3つの変数(burst_allowance_、PIE-> drop_prob_、およびPIE-> qdelay_old_)のみです。したがって、メモリのオーバーヘッドは小さいです。

If one chooses to implement the departure rate estimation, PIE uses a counter to keep track of the number of bytes departed for the current interval. This counter is incremented per packet departure. Every T_UPDATE, PIE calculates latency using the departure rate, which can be implemented using a single multiply operation. Note that many network devices keep track of an interface's departure rate. In this case, PIE might be able to reuse this information and simply skip the third step of the algorithm; hence, it would incur no extra cost. If a platform already leverages packet timestamps for other purposes, PIE can make use of these packet timestamps for latency calculation instead of estimating the departure rate.

逸脱率の推定を実装することを選択した場合、PIEはカウンターを使用して、現在の間隔で出発したバイト数を追跡​​します。このカウンタは、パケットの発信ごとに増分されます。 T_UPDATEごとに、PIEは逸脱率を使用してレイテンシを計算します。これは、単一の乗算演算を使用して実装できます。多くのネットワークデバイスは、インターフェイスの離脱率を追跡していることに注意してください。この場合、PIEはこの情報を再利用して、アルゴリズムの3番目のステップを単にスキップできる可能性があります。したがって、追加費用は発生しません。プラットフォームがすでに他の目的でパケットタイムスタンプを利用している場合、PIEは、逸脱率を推定する代わりに、これらのパケットタイムスタンプをレイテンシ計算に利用できます。

Flow queuing can also be combined with PIE to provide isolation between flows. In this case, it is preferable to have an independent value of drop probability per queue. This allows each flow to receive the most appropriate level of congestion signal and ensures that sparse flows are protected from experiencing packet drops. However, running the entire PIE algorithm independently on each queue in order to calculate the drop probability may be overkill. Furthermore, in the case where departure rate estimation is used to predict queuing latency, it is not possible to calculate an accurate per-queue departure rate upon which to implement the PIE drop probability calculation. Instead, it has been proposed [DOCSIS-AQM] that a single implementation of the PIE drop probability calculation based on the overall latency estimate be used, followed by a per-queue scaling of drop probability based on the ratio of queue depth between the queue in question and the current largest queue. This scaling is reasonably simple and has a couple of nice properties:

フローキューイングをPIEと組み合わせて、フロー間の分離を実現することもできます。この場合、キューごとのドロップ確率の独立した値を持つことが望ましいです。これにより、各フローは最も適切なレベルの輻輳信号を受信でき、スパースフローがパケットドロップの発生から保護されます。ただし、廃棄確率を計算するためにPIEアルゴリズム全体を各キューで個別に実行することは、やり過ぎになる場合があります。さらに、逸脱率推定を使用してキュー待機時間を予測する場合、PIEドロップ確率計算を実装する正確なキューごとの逸脱率を計算することはできません。代わりに、全体的なレイテンシ推定に基づくPIEドロップ確率計算の単一の実装が使用され、その後、キュー間のキュー深度の比率に基づくドロップ確率のキューごとのスケーリングが使用されることが提案されています[DOCSIS-AQM]。問題の現在の最大のキュー。このスケーリングはかなり単純で、いくつかの優れたプロパティがあります。

* If a packet is arriving to an empty queue, it is given immunity from packet drops altogether, regardless of the state of the other queues.

* パケットが空のキューに到着すると、他のキューの状態に関係なく、パケットドロップに対する耐性が完全に与えられます。

* In the situation where only a single queue is in use, the algorithm behaves exactly like the single-queue PIE algorithm.

* 単一キューのみが使用されている状況では、アルゴリズムは単一キューPIEアルゴリズムとまったく同じように動作します。

In summary, PIE is simple enough to be implemented in both software and hardware.

要約すると、PIEはソフトウェアとハ​​ードウェアの両方に実装できるほど単純です。

7. Scope of Experimentation
7. 実験の範囲

The design of the PIE algorithm is presented in this document. The PIE algorithm effectively controls the average queuing latency to a target value. The following areas can be used for further study and experimentation:

このドキュメントでは、PIEアルゴリズムの設計について説明します。 PIEアルゴリズムは、平均キューイングレイテンシをターゲット値に効果的に制御します。次の領域は、さらなる調査と実験に使用できます。

* Autotuning of target latency without losing utilization.

* 使用率を失うことなくターゲットレイテンシを自動調整します。

* Autotuning for the average round-trip time of traffic.

* トラフィックの平均往復時間の自動調整。

* The proper threshold to transition smoothly between ECN marking and dropping.

* ECNマーキングとドロップの間をスムーズに移行するための適切なしきい値。

* The enhancements described in Section 5, which can be used in experiments to see if they would be of more value in the real world. If so, they will be incorporated into the basic PIE algorithm.

* セクション5で説明した拡張機能は、実験で使用して、現実世界でより価値があるかどうかを確認できます。その場合、それらは基本的なPIEアルゴリズムに組み込まれます。

* The PIE design, which is separated into the data path and the control path. The control path can be implemented in software. Field tests of other control laws can be performed to experiment with further improvements to PIE's performance.

* データパスと制御パスに分離されたPIE設計。制御パスはソフトウェアで実装できます。他の制御法則のフィールドテストを実行して、PIEのパフォーマンスをさらに向上させることができます。

Although all network nodes cannot be changed altogether to adopt latency-based AQM schemes such as PIE, a gradual adoption would eventually lead to end-to-end low-latency service for all applications.

すべてのネットワークノードを完全に変更して、PIEなどの遅延ベースのAQMスキームを採用することはできませんが、徐々に採用すると、最終的にすべてのアプリケーションでエンドツーエンドの低遅延サービスが実現します。

8. Incremental Deployment
8. 増分展開

From testbed experiments and large-scale simulations of PIE so far, PIE has been shown to be effective across a diverse range of network scenarios. There is no indication that PIE would be harmful to deploy.

これまでのPIEのテストベッド実験と大規模シミュレーションから、PIEはさまざまなネットワークシナリオで効果的であることが示されています。 PIEの展開が有害であるという兆候はありません。

The PIE scheme can be independently deployed and managed without a need for interoperability between different network devices. In addition, any individual buffer queue can be incrementally upgraded to PIE, as it can coexist with existing AQM schemes such as Weighted RED (WRED).

PIEスキームは、異なるネットワークデバイス間の相互運用性を必要とせずに、独立して展開および管理できます。さらに、個々のバッファキューは、加重RED(WRED)などの既存のAQMスキームと共存できるため、PIEに段階的にアップグレードできます。

PIE is intended to be self-configuring. Users should not need to configure any design parameters. Upon installation, the two user-configurable parameters -- QDELAY_REF and MAX_BURST -- will be defaulted to 15 milliseconds and 150 milliseconds for non-data-center network devices and to 15 microseconds and 150 microseconds for data-center switches, respectively.

PIEは、自己構成を目的としています。ユーザーは設計パラメータを構成する必要はありません。インストール時に、2つのユーザー構成可能なパラメーター(QDELAY_REFとMAX_BURST)は、デフォルトで非データセンターネットワークデバイスの場合は15ミリ秒と150ミリ秒に、データセンタースイッチの場合は15マイクロ秒と150マイクロ秒に設定されます。

Since the data path of the algorithm needs only a simple coin toss and the control-path calculation happens in a much slower time scale, we don't foresee any scaling issues associated with the algorithm as the link speed scales up.

アルゴリズムのデータパスに必要なのは単純なコイントスだけであり、制御パスの計算ははるかに遅いタイムスケールで行われるため、リンク速度の拡大に伴うアルゴリズムに関連するスケーリングの問題は予測されません。

9. Security Considerations
9. セキュリティに関する考慮事項

This document describes PIE, an active queue management algorithm based on implementations in different products. The PIE algorithm introduces no specific security exposures.

このドキュメントでは、さまざまな製品の実装に基づくアクティブなキュー管理アルゴリズムであるPIEについて説明します。 PIEアルゴリズムは、特定の機密漏れをもたらしません。

10. References
10. 参考文献
10.1. Normative References
10.1. 引用文献

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <http://www.rfc-editor.org/info/rfc2119>.

[RFC2119] Bradner、S。、「要件レベルを示すためにRFCで使用するキーワード」、BCP 14、RFC 2119、DOI 10.17487 / RFC2119、1997年3月、<http://www.rfc-editor.org/info/ rfc2119>。

10.2. Informative References
10.2. 参考引用

[RFC970] Nagle, J., "On Packet Switches With Infinite Storage", RFC 970, DOI 10.17487/RFC0970, December 1985, <http://www.rfc-editor.org/info/rfc970>.

[RFC970] Nagle、J。、「On Packet Switches With Infinite Storage」、RFC 970、DOI 10.17487 / RFC0970、1985年12月、<http://www.rfc-editor.org/info/rfc970>。

[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, <http://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、<http://www.rfc-editor.org/info/rfc2309>。

[RFC7567] Baker, F., Ed., and G. Fairhurst, Ed., "IETF Recommendations Regarding Active Queue Management", BCP 197, RFC 7567, DOI 10.17487/RFC7567, July 2015, <http://www.rfc-editor.org/info/rfc7567>.

[RFC7567]ベイカー、F。、エド、およびG.フェアハースト、エド、「アクティブキュー管理に関するIETFの推奨事項」、BCP 197、RFC 7567、DOI 10.17487 / RFC7567、2015年7月、<http://www.rfc -editor.org/info/rfc7567>。

[RFC7806] Baker, F. and R. Pan, "On Queuing, Marking, and Dropping", RFC 7806, DOI 10.17487/RFC7806, April 2016, <http://www.rfc-editor.org/info/rfc7806>.

[RFC7806]ベイカー、F。およびR.パン、「キューイング、マーキング、およびドロップ時」、RFC 7806、DOI 10.17487 / RFC7806、2016年4月、<http://www.rfc-editor.org/info/rfc7806> 。

[RFC8034] White, G. and R. Pan, "Active Queue Management (AQM) Based on Proportional Integral Controller Enhanced (PIE) for Data-Over-Cable Service Interface Specifications (DOCSIS) Cable Modems", RFC 8034, DOI 10.17487/RFC8034, February 2017, <http://www.rfc-editor.org/info/rfc8034>.

[RFC8034]ホワイト、G.、R。パン、「Data-Over-Cable Service Interface Specifications(DOCSIS)Cable Modems用のProportional Integral Controller Enhanced(PIE)に基づくアクティブキュー管理(AQM)」、RFC 8034、DOI 10.17487 / RFC8034、2017年2月、<http://www.rfc-editor.org/info/rfc8034>。

[CBQ] Cisco, "Class-Based Weighted Fair Queueing", <http://www.cisco.com/en/US/docs/ios/12_0t/12_0t5/ feature/guide/cbwfq.html>.

[CBQ] Cisco、「Class-Based Weighted Fair Queueing」、<http://www.cisco.com/en/US/docs/ios/12_0t/12_0t5/ feature / guide / cbwfq.html>。

[CoDel] Nichols, K. and V. Jacobson, "Controlling Queue Delay", Communications of the ACM, Volume 55, Issue 7, pp. 42-50, DOI 10.1145/2209249.2209264, July 2012.

[CoDel] Nichols、K。およびV. Jacobson、「Controlling Queue Delay」、Communications of the ACM、Volume 55、Issue 7、42--50ページ、DOI 10.1145 / 2209249.2209264、2012年7月。

[DOCSIS_3.1] CableLabs, "MAC and Upper Layer Protocols Interface Specification", DOCSIS 3.1, January 2017, <https://apps.cablelabs.com/specification/ CM-SP-MULPIv3.1>.

[DOCSIS_3.1] CableLabs、「MAC and Upper Layer Protocols Interface Specification」、DOCSIS 3.1、2017年1月、<https://apps.cablelabs.com/specification/ CM-SP-MULPIv3.1>。

[DOCSIS-AQM] White, G., "Active Queue Management in DOCSIS 3.x Cable Modems", May 2014, <http://www.cablelabs.com/wp-content/ uploads/2014/06/DOCSIS-AQM_May2014.pdf>.

[DOCSIS-AQM]ホワイト、G。、「DOCSIS 3.xケーブルモデムでのアクティブキュー管理」、2014年5月、<http://www.cablelabs.com/wp-content/uploads/2014/06/DOCSIS-AQM_May2014 .pdf>。

[ECN] Briscoe, B., Kaippallimalil, J., and P. Thaler, "Guidelines for Adding Congestion Notification to Protocols that Encapsulate IP", Work in Progress, draft-ietf-tsvwg-ecn-encap-guidelines-07, July 2016.

[ECN] Briscoe、B.、Kaippallimalil、J。、およびP. Thaler、「IPをカプセル化するプロトコルに輻輳通知を追加するためのガイドライン」、作業中、draft-ietf-tsvwg-ecn-encap-guidelines-07、7月2016。

[HPSR-PIE] Pan, R., Natarajan, P., Piglione, C., Prabhu, M.S., Subramanian, V., Baker, F., and B. Ver Steeg, "PIE: A lightweight control scheme to address the bufferbloat problem", IEEE HPSR, DOI 10.1109/HPSR.2013.6602305, 2013, <https://www.researchgate.net/publication/ 261134127_PIE_A_lightweight_control_scheme_to_address_ the_bufferbloat_problem?origin=mail>.

[HPSR-PIE] Pan、R.、Natarajan、P.、Piglione、C.、Prabhu、MS、Subramanian、V.、Baker、F.、and B. Ver Steeg、 "PIE:a軽量制御スキームに対処するための軽量制御スキームbufferbloat problem」、IEEE HPSR、DOI 10.1109 / HPSR.2013.6602305、2013、<https://www.researchgate.net/publication/ 261134127_PIE_A_lightweight_control_scheme_to_address_ the_bufferbloat_problem?origin = mail>。

[PI] Hollot, C.V., Misra, V., Towsley, D., and W. Gong, "On designing improved controllers for AQM routers supporting TCP flows", INFOCOM 2001, DOI 10.1109/INFCOM.2001.916670, April 2001.

[PI] Hollot、C.V.、Misra、V.、Towsley、D。、およびW. Gong、「TCPフローをサポートするAQMルーター用の改良されたコントローラーの設計について」、INFOCOM 2001、DOI 10.1109 / INFCOM.2001.916670、2001年4月。

[QCN] IEEE, "IEEE Standard for Local and Metropolitan Area Networks--Virtual Bridged Local Area Networks - Amendment: 10: Congestion Notification", IEEE 802.1Qau, <http://www.ieee802.org/1/pages/802.1au.html>.

[QCN] IEEE、「IEEE Standard for Local and Metropolitan Area Networks--Virtual Bridged Local Area Networks-Amendment:10:Congestion Notification」、IEEE 802.1Qau、<http://www.ieee802.org/1/pages/802.1 au.html>。

[RED] Floyd, S. and V. Jacobson, "Random Early Detection (RED) Gateways for Congestion Avoidance", IEEE/ACM Transactions on Networking, Volume 1, Issue 4, DOI 10.1109/90.251892, August 1993.

[RED] Floyd、S.およびV. Jacobson、「Random Early Detection(RED)Gateways for Congestion Avoidance」、IEEE / ACM Transactions on Networking、Volume 1、Issue 4、DOI 10.1109 / 90.251892、1993年8月。

[TCP-Models] Misra, V., Gong, W., and D. Towsley, "Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED", SIGCOMM 2000, Volume 30, Issue 4, pp. 151-160, DOI 10.1145/347057.347421, October 2000.

[TCPモデル] Misra、V.、Gong、W。、およびD. Towsley、「REDへのアプリケーションを使用したTCPフローをサポートするAQMルーターのネットワークの流体ベースの分析」、SIGCOMM 2000、第30巻、第4号pp。151-160、DOI 10.1145 / 347057.347421、2000年10月。

Appendix A. The Basic PIE Pseudocode
付録A.基本的なPIE擬似コード
   Configurable parameters:
      -  QDELAY_REF.  AQM Latency Target (default: 15 milliseconds)
      -  MAX_BURST.  AQM Max Burst Allowance (default: 150 milliseconds)
        
   Internal parameters:
      -  Weights in the drop probability calculation (1/s):
         alpha (default: 1/8), beta (default: 1 + 1/4)
      -  T_UPDATE: a period to calculate drop probability
         (default: 15 milliseconds)
        
   Table that stores status variables (ending with "_"):
      -  burst_allowance_: current burst allowance
      -  drop_prob_: The current packet drop probability.  Reset to 0
      -  qdelay_old_: The previous queue delay.  Reset to 0
        
   Public/system functions:
      -  queue_.  Holds the pending packets
      -  drop(packet).  Drops/discards a packet
      -  now().  Returns the current time
      -  random().  Returns a uniform r.v. in the range 0 ~ 1
      -  queue_.byte_length().  Returns current queue_ length in bytes
      -  queue_.enque(packet).  Adds packet to tail of queue_
      -  queue_.deque().  Returns the packet from the head of queue_
      -  packet.size().  Returns size of packet
      -  packet.timestamp_delay().  Returns timestamped packet latency
        
   ============================
        
   //Called on each packet arrival
     enque(Packet packet) {
          if (PIE->drop_prob_ == 0 && current_qdelay < QDELAY_REF/2
              && PIE->qdelay_old_ < QDELAY_REF/2) {
              PIE->burst_allowance_ = MAX_BURST;
          }
          if (PIE->burst_allowance_ == 0 && drop_early() == DROP) {
                   drop(packet);
          } else {
                   queue_.enque(packet);
          }
     }
        
   ============================
        

drop_early() {

drop_early(){

         //Safeguard PIE to be work conserving
         if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2)
               || (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) {
              return ENQUE;
         }
        
         double u = random();
         if (u < PIE->drop_prob_) {
              return DROP;
         } else {
        
              return ENQUE;
         }
      }
        
   ============================
        
   //We choose the timestamp option of obtaining latency for clarity
   //Rate estimation method can be found in the extended PIE pseudocode
        

deque(Packet packet) {

deque(パケットパケット){

       current_qdelay = packet.timestamp_delay();
     }
        
   ============================
        
   //Update periodically, T_UPDATE = 15 milliseconds
        

calculate_drop_prob() {

calculate_drop_prob(){

//Can be implemented using integer multiply

//整数乗算を使用して実装できます

          p = alpha * (current_qdelay - QDELAY_REF) + \
              beta * (current_qdelay - PIE->qdelay_old_);
        
          if (PIE->drop_prob_ < 0.000001) {
              p /= 2048;
          } else if (PIE->drop_prob_ < 0.00001) {
              p /= 512;
          } else if (PIE->drop_prob_ < 0.0001) {
              p /= 128;
          } else if (PIE->drop_prob_ < 0.001) {
              p /= 32;
          } else if (PIE->drop_prob_ < 0.01) {
              p /= 8;
        
          } else if (PIE->drop_prob_ < 0.1) {
              p /= 2;
          } else {
              p = p;
          }
        
          PIE->drop_prob_ += p;
        
          //Exponentially decay drop prob when congestion goes away
          if (current_qdelay == 0 && PIE->qdelay_old_ == 0) {
              PIE->drop_prob_ *= 0.98;           //1 - 1/64 is
                                                 //sufficient
          }
        
          //Bound drop probability
          if (PIE->drop_prob_ < 0)
                   PIE->drop_prob_ = 0.0
          if (PIE->drop_prob_ > 1)
                   PIE->drop_prob_ = 1.0
        
          PIE->qdelay_old_ = current_qdelay;
        
          PIE->burst_allowance_ =
             max(0,PIE->burst_allowance_ - T_UPDATE);
       }
   }
        
Appendix B. Pseudocode for PIE with Optional Enhancement
付録B.オプションの拡張機能を備えたPIEの疑似コード
   Configurable parameters:
      -  QDELAY_REF.  AQM Latency Target (default: 15 milliseconds)
      -  MAX_BURST.  AQM Max Burst Allowance (default: 150 milliseconds)
      -  MAX_ECNTH.  AQM Max ECN Marking Threshold (default: 10%)
        
   Internal parameters:
      -  Weights in the drop probability calculation (1/s):
         alpha (default: 1/8), beta (default: 1 + 1/4)
      -  DQ_THRESHOLD: (in bytes, default: 2^14 (in a power of 2) )
      -  T_UPDATE: a period to calculate drop probability
         (default: 15 milliseconds)
      -  TAIL_DROP: the tail drop threshold (max allowed queue depth)
         for the queue
        
   Table that stores status variables (ending with "_"):
      -  active_: INACTIVE/ACTIVE
      -  burst_allowance_: current burst allowance
      -  drop_prob_: The current packet drop probability.  Reset to 0
      -  accu_prob_: Accumulated drop probability.  Reset to 0
      -  qdelay_old_: The previous queue delay estimate.  Reset to 0
      -  last_timestamp_: Timestamp of previous status update
      -  dq_count_, measurement_start_, in_measurement_, avg_dq_time_.
         Variables for measuring average dequeue rate
        
   Public/system functions:
      -  queue_.  Holds the pending packets
      -  drop(packet).  Drops/discards a packet
      -  mark(packet).  Marks ECN for a packet
      -  now().  Returns the current time
      -  random().  Returns a uniform r.v. in the range 0 ~ 1
      -  queue_.byte_length().  Returns current queue_ length in bytes
      -  queue_.enque(packet).  Adds packet to tail of queue_
      -  queue_.deque().  Returns the packet from the head of queue_
      -  packet.size().  Returns size of packet
      -  packet.ecn().  Returns whether packet is ECN capable or not
        
   ============================
        
   //Called on each packet arrival
     enque(Packet packet) {
          if (queue_.byte_length() + packet.size() > TAIL_DROP) {
                 drop(packet);
                 PIE->accu_prob_ = 0;
          } else if (PIE->active_ == TRUE && drop_early() == DROP
                     && PIE->burst_allowance_ == 0) {
                 if (PIE->drop_prob_ < MAX_ECNTH && packet.ecn() ==
                     TRUE)
                       mark(packet);
                 else
                       drop(packet);
                       PIE->accu_prob_ = 0;
          } else {
                 queue_.enque(packet);
          }
        
          //If the queue is over a certain threshold, turn on PIE
          if (PIE->active_ == INACTIVE
              && queue_.byte_length() >= TAIL_DROP/3) {
               PIE->active_ = ACTIVE;
               PIE->qdelay_old_ = 0;
               PIE->drop_prob_ = 0;
               PIE->in_measurement_ = TRUE;
               PIE->dq_count_ = 0;
               PIE->avg_dq_time_ = 0;
               PIE->last_timestamp_ = now;
               PIE->burst_allowance_ = MAX_BURST;
               PIE->accu_prob_ = 0;
               PIE->measurement_start_ = now;
          }
        
          //If the queue has been idle for a while, turn off PIE
          //Reset counters when accessing the queue after some idle
          //period if PIE was active before
          if ( PIE->drop_prob_ == 0 && PIE->qdelay_old_ == 0
               && current_qdelay == 0) {
               PIE->active_ = INACTIVE;
               PIE->in_measurement_ = FALSE;
          }
        

}

   ============================
        

drop_early() {

drop_early(){

         //PIE is active but the queue is not congested: return ENQUE
         if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2)
               || (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) {
              return ENQUE;
         }
        
         if (PIE->drop_prob_ == 0) {
                  PIE->accu_prob_ = 0;
         }
        
         //For practical reasons, drop probability can be further scaled
         //according to packet size, but one needs to set a bound to
         //avoid unnecessary bias
        
         //Random drop
         PIE->accu_prob_ += PIE->drop_prob_;
         if (PIE->accu_prob_ < 0.85)
             return ENQUE;
         if (PIE->accu_prob_ >= 8.5)
             return DROP;
                 double u = random();
         if (u < PIE->drop_prob_) {
                      PIE->accu_prob_ = 0;
                      return DROP;
         } else {
                      return ENQUE;
         }
      }
        
   ============================
        
    //Update periodically, T_UPDATE = 15 milliseconds
    calculate_drop_prob() {
        if ( (now - PIE->last_timestamp_) >= T_UPDATE &&
                PIE->active_ == ACTIVE) {
        
          //Can be implemented using integer multiply
          //DQ_THRESHOLD is power of 2 value
          current_qdelay = queue_.byte_length() *
          PIE->avg_dq_time_/DQ_THRESHOLD;
        
          p = alpha * (current_qdelay - QDELAY_REF) + \
              beta * (current_qdelay - PIE->qdelay_old_);
        
          if (PIE->drop_prob_ < 0.000001) {
              p /= 2048;
          } else if (PIE->drop_prob_ < 0.00001) {
              p /= 512;
          } else if (PIE->drop_prob_ < 0.0001) {
              p /= 128;
          } else if (PIE->drop_prob_ < 0.001) {
              p /= 32;
          } else if (PIE->drop_prob_ < 0.01) {
              p /= 8;
          } else if (PIE->drop_prob_ < 0.1) {
              p /= 2;
          } else {
              p = p;
          }
        
          if (PIE->drop_prob_ >= 0.1 && p > 0.02) {
              p = 0.02;
          }
          PIE->drop_prob_ += p;
        
          //Exponentially decay drop prob when congestion goes away
          if (current_qdelay < QDELAY_REF/2 && PIE->qdelay_old_ <
              QDELAY_REF/2) {
                 PIE->drop_prob_ *= 0.98;        //1 - 1/64 is
                                                 //sufficient
          }
        
          //Bound drop probability
          if (PIE->drop_prob_ < 0)
                   PIE->drop_prob_ = 0
          if (PIE->drop_prob_ > 1)
                   PIE->drop_prob_ = 1
        
          PIE->qdelay_old_ = current_qdelay;
          PIE->last_timestamp_ = now;
          PIE->burst_allowance_ = max(0,PIE->burst_allowance_ -
             T_UPDATE);
       }
   }
        
   ============================
        
   //Called on each packet departure
     deque(Packet packet) {
        
        //Dequeue rate estimation
        if (PIE->in_measurement_ == TRUE) {
             PIE->dq_count_ = packet.size() + PIE->dq_count_;
             //Start a new measurement cycle if we have enough packets
             if ( PIE->dq_count_ >= DQ_THRESHOLD) {
               dq_time = now - PIE->measurement_start_;
               if (PIE->avg_dq_time_ == 0) {
                   PIE->avg_dq_time_ = dq_time;
               } else {
                   weight = DQ_THRESHOLD/2^16
                   PIE->avg_dq_time_ = dq_time * weight +
                      PIE->avg_dq_time_ * (1 - weight);
               }
               PIE->in_measurement_ = FALSE;
             }
        }
        
        //Start a measurement if we have enough data in the queue
        if (queue_.byte_length() >= DQ_THRESHOLD &&
            PIE->in_measurement_ == FALSE) {
               PIE->in_measurement_ = TRUE;
               PIE->measurement_start_ = now;
               PIE->dq_count_ = 0;
        }
     }
        

Contributors

貢献者

Bill Ver Steeg Comcast Cable Email: William_VerSteeg@comcast.com

Bill Ver Steeg Comcast Cableメール:William_VerSteeg@comcast.com

Mythili Prabhu* Akamai Technologies 3355 Scott Blvd. Santa Clara, CA 95054 United States of America Email: mythili@akamai.com

Maithili Prabhu *マネジメントテクノロジースコットビルド。アメリカ合衆国、サンタクララメール:Maithili Camp.com

Chiara Piglione* Broadcom Corporation 3151 Zanker Road San Jose, CA 95134 United States of America Email: chiara@broadcom.com

Chiara Piglione * Broadcom Corporation 3151 Zanker Road San Jose、CA 95134アメリカ合衆国メール:chiara@broadcom.com

Vijay Subramanian* PLUMgrid, Inc. 350 Oakmead Parkway Suite 250 Sunnyvale, CA 94085 United States of America Email: vns@plumgrid.com * Formerly at Cisco Systems

Vijay Subramanian * PLUMgrid、Inc. 350 Oakmead Parkway Suite 250 Sunnyvale、CA 94085 United States of Email Email:vns@plumgrid.com *旧Cisco Systems

Authors' Addresses

著者のアドレス

Rong Pan Cisco Systems 3625 Cisco Way San Jose, CA 95134 United States of America

Rong Pan Cisco Systems 3625 Cisco Way San Jose、CA 95134アメリカ合衆国

   Email: ropan@cisco.com
        

Preethi Natarajan Cisco Systems 725 Alder Drive Milpitas, CA 95035 United States of America

Preethi Natarajan Cisco Systems 725 Alder Drive Milpitas、CA 95035アメリカ合衆国

   Email: prenatar@cisco.com
        

Fred Baker Santa Barbara, CA 93117 United States of America

フレッドベイカーサンタバーバラ、カリフォルニア州93117アメリカ合衆国

   Email: FredBaker.IETF@gmail.com
        

Greg White CableLabs 858 Coal Creek Circle Louisville, CO 80027 United States of America

グレッグホワイトCableLabs 858コールクリークサークルルイビル、CO 80027アメリカ合衆国

   Email: g.white@cablelabs.com