doc: Add RFC documents

1 files changed, 1683 insertions, 0 deletions

diff --git a/doc/rfc/rfc8033.txt b/doc/rfc/rfc8033.txt
new file mode 100644
index 0000000..952afa5
--- /dev/null
+++ b/doc/rfc/rfc8033.txt
@@ -0,0 +1,1683 @@
+
+
+
+
+
+
+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
+
+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.
+
+   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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                      [Page 1]
+
+RFC 8033                           PIE                     February 2017
+
+
+Status of This Memo
+
+   This document is not an Internet Standards Track specification; it is
+   published for examination, experimental implementation, and
+   evaluation.
+
+   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.
+
+   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.
+
+Copyright Notice
+
+   Copyright (c) 2017 IETF Trust and the persons identified as the
+   document authors.  All rights reserved.
+
+   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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                      [Page 2]
+
+RFC 8033                           PIE                     February 2017
+
+
+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
+
+   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.
+
+
+
+Pan, et al.                   Experimental                      [Page 3]
+
+RFC 8033                           PIE                     February 2017
+
+
+   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.
+
+   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.
+
+   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].
+
+   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
+
+
+
+Pan, et al.                   Experimental                      [Page 4]
+
+RFC 8033                           PIE                     February 2017
+
+
+   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.
+
+   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.
+
+2.  Terminology
+
+   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].
+
+3.  Design Goals
+
+   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.
+
+   *  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.
+
+   *  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.
+
+   *  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.
+
+
+
+
+Pan, et al.                   Experimental                      [Page 5]
+
+RFC 8033                           PIE                     February 2017
+
+
+   In the following text, the design of PIE and its operation are
+   described in detail.
+
+4.  The Basic PIE Scheme
+
+   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.
+
+   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].
+
+         Random Drop
+              /               --------------
+      -------/  -------------->    | | | | | -------------->
+             /|\                   | | | | |
+              |               --------------
+              |             Queue Buffer   \
+              |                     |       \
+              |                     |Queue   \
+              |                     |Length   \
+              |                     |          \
+              |                    \|/         \/
+              |          -----------------    -------------------
+              |          |     Drop      |    |                 |
+              -----<-----|  Probability  |<---| Latency         |
+                         |  Calculation  |    | Calculation     |
+                         -----------------    -------------------
+
+                        Figure 1: The PIE Structure
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                      [Page 6]
+
+RFC 8033                           PIE                     February 2017
+
+
+4.1.  Random Dropping
+
+   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.
+
+   *  Upon a packet enqueue:
+
+      randomly drop the packet with a probability of 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.
+
+   *  Upon a packet enqueue, PIE does the following:
+
+      //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 optionally supports Explicit Congestion Notification (ECN); see
+   Section 5.1.
+
+4.2.  Drop Probability Calculation
+
+   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.
+
+   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
+
+
+
+Pan, et al.                   Experimental                      [Page 7]
+
+RFC 8033                           PIE                     February 2017
+
+
+   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.
+
+   Specifically, the PIE algorithm periodically adjusts the drop
+   probability every T_UPDATE interval:
+
+   *  calculate drop probability PIE->drop_prob_, and autotune it as
+      follows:
+
+         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
+
+
+
+
+
+Pan, et al.                   Experimental                      [Page 8]
+
+RFC 8033                           PIE                     February 2017
+
+
+   *  store the current latency value:
+
+         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.
+
+   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.
+
+   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.
+
+4.3.  Latency Calculation
+
+   The PIE algorithm uses latency to calculate drop probability in one
+   of two ways:
+
+   *  It estimates the current queuing latency using Little's law (see
+      Section 5.2 for details):
+
+         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.
+
+
+
+
+
+Pan, et al.                   Experimental                      [Page 9]
+
+RFC 8033                           PIE                     February 2017
+
+
+4.4.  Burst Tolerance
+
+   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.
+
+   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:
+
+   *  In the "random dropping" block and upon packet arrival, PIE checks
+      the following:
+
+      Upon a packet enqueue:
+         if PIE->burst_allowance_ > 0
+            enqueue packet;
+         else
+            randomly drop a packet with a probability of
+            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->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.
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 10]
+
+RFC 8033                           PIE                     February 2017
+
+
+5.  Optional Design Elements of 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
+
+   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%).
+
+   *  To support ECN, the "random drop with a probability of
+      PIE->drop_prob_" function in the "random dropping" block is
+      changed to the following:
+
+      *  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
+
+   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
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 11]
+
+RFC 8033                           PIE                     February 2017
+
+
+   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:
+
+      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.
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 12]
+
+RFC 8033                           PIE                     February 2017
+
+
+            Random Drop
+                /                     --------------
+        -------/  -------------------->    | | | | | -------------->
+               /|\             |           | | | | |
+                |              |      --------------
+                |              |       Queue Buffer
+                |              |             |
+                |              |             |Queue
+                |              |             |Length
+                |              |             |
+                |             \|/           \|/
+                |          ------------------------------
+                |          |     Dequeue Rate           |
+                -----<-----|  & Drop Probability        |
+                           |        Calculation         |
+                           ------------------------------
+
+                 Figure 2: The Enqueue-Based PIE Structure
+
+   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.
+
+5.3.  Setting PIE Active and Inactive
+
+   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.
+
+   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.
+
+
+
+Pan, et al.                   Experimental                     [Page 13]
+
+RFC 8033                           PIE                     February 2017
+
+
+   When PIE optionally becomes active/inactive, the burst protection
+   logic described in Section 4.4 is modified as follows:
+
+   *  "Random dropping" block: PIE adds the following:
+
+      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_.
+
+      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
+
+   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
+
+
+
+Pan, et al.                   Experimental                     [Page 14]
+
+RFC 8033                           PIE                     February 2017
+
+
+   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].
+
+5.5.  Cap Drop Adjustment
+
+   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.
+
+   *  "Drop probability calculation" block: PIE adds the following:
+
+      if (PIE->drop_prob_ >= 0.1 && p > 0.02) {
+          p = 0.02;
+      }
+
+6.  Implementation Cost
+
+   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.
+
+   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.
+
+   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
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 15]
+
+RFC 8033                           PIE                     February 2017
+
+
+   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.
+
+   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.
+
+   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:
+
+   *  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.
+
+   In summary, PIE is simple enough to be implemented in both software
+   and hardware.
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 16]
+
+RFC 8033                           PIE                     February 2017
+
+
+7.  Scope of Experimentation
+
+   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:
+
+   *  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.
+
+   *  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.
+
+   *  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.
+
+   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.
+
+8.  Incremental Deployment
+
+   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.
+
+   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 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.
+
+
+
+Pan, et al.                   Experimental                     [Page 17]
+
+RFC 8033                           PIE                     February 2017
+
+
+   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
+
+   This document describes PIE, an active queue management algorithm
+   based on implementations in different products.  The PIE algorithm
+   introduces no specific security exposures.
+
+10.  References
+
+10.1.  Normative References
+
+   [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>.
+
+10.2.  Informative References
+
+   [RFC970]   Nagle, J., "On Packet Switches With Infinite Storage",
+              RFC 970, DOI 10.17487/RFC0970, December 1985,
+              <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>.
+
+   [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>.
+
+   [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>.
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 18]
+
+RFC 8033                           PIE                     February 2017
+
+
+   [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>.
+
+   [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.
+
+   [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-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>.
+
+   [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.
+
+   [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>.
+
+   [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.
+
+   [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>.
+
+
+
+
+Pan, et al.                   Experimental                     [Page 19]
+
+RFC 8033                           PIE                     February 2017
+
+
+   [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.
+
+   [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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 20]
+
+RFC 8033                           PIE                     February 2017
+
+
+Appendix A.  The Basic PIE Pseudocode
+
+   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);
+          }
+     }
+
+   ============================
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 21]
+
+RFC 8033                           PIE                     February 2017
+
+
+     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) {
+
+       current_qdelay = packet.timestamp_delay();
+     }
+
+   ============================
+
+   //Update periodically, T_UPDATE = 15 milliseconds
+
+     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;
+
+
+
+Pan, et al.                   Experimental                     [Page 22]
+
+RFC 8033                           PIE                     February 2017
+
+
+          } 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);
+       }
+   }
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 23]
+
+RFC 8033                           PIE                     February 2017
+
+
+Appendix B.  Pseudocode for PIE with Optional Enhancement
+
+   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
+
+   ============================
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 24]
+
+RFC 8033                           PIE                     February 2017
+
+
+   //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;
+          }
+
+     }
+
+   ============================
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 25]
+
+RFC 8033                           PIE                     February 2017
+
+
+     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;
+         }
+      }
+
+   ============================
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 26]
+
+RFC 8033                           PIE                     February 2017
+
+
+    //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
+          }
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 27]
+
+RFC 8033                           PIE                     February 2017
+
+
+          //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;
+        }
+     }
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 28]
+
+RFC 8033                           PIE                     February 2017
+
+
+Contributors
+
+   Bill Ver Steeg
+   Comcast Cable
+   Email: William_VerSteeg@comcast.com
+
+   Mythili Prabhu*
+   Akamai Technologies
+   3355 Scott Blvd.
+   Santa Clara, CA  95054
+   United States of America
+   Email: mythili@akamai.com
+
+   Chiara Piglione*
+   Broadcom Corporation
+   3151 Zanker Road
+   San Jose, CA  95134
+   United States of America
+   Email: 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
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 29]
+
+RFC 8033                           PIE                     February 2017
+
+
+Authors' Addresses
+
+   Rong Pan
+   Cisco Systems
+   3625 Cisco Way
+   San Jose, CA  95134
+   United States of America
+
+   Email: ropan@cisco.com
+
+
+   Preethi Natarajan
+   Cisco Systems
+   725 Alder Drive
+   Milpitas, CA  95035
+   United States of America
+
+   Email: prenatar@cisco.com
+
+
+   Fred Baker
+   Santa Barbara, CA  93117
+   United States of America
+
+   Email: FredBaker.IETF@gmail.com
+
+
+   Greg White
+   CableLabs
+   858 Coal Creek Circle
+   Louisville, CO  80027
+   United States of America
+
+   Email: g.white@cablelabs.com
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Pan, et al.                   Experimental                     [Page 30]
+