RFC 8033
Proportional Integral Controller Enhanced (PIE): A Lightweight Control Scheme to Address the Bufferbloat Problem
RFC 8033: PIE, the Lightweight Bufferbloat Fixer 🎀
Okay bestie, this one is RFC 8033, and it's all about PIE (Proportional Integral controller Enhanced), a lightweight way to tame bufferbloat 🫶
- RFC number: 8033 🦋
- Title: Proportional Integral Controller Enhanced (PIE): A Lightweight Control Scheme to Address the Bufferbloat Problem
- Published by: the Internet Engineering Task Force (IETF) 💜
- Authors: R. Pan and P. Natarajan (Cisco Systems), F. Baker (Unaffiliated), and G. White (CableLabs) 👑
- Category: Experimental 🧪
- ISSN: 2070-1721
- Date: February 2017 📅
- Obsoletes / Updates: nothing is listed in the title block, so this one doesn't obsolete or update anything 🌸
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 ................................................30Abstract ✨
Okay so bufferbloat is what happens when there are way too many extra buffers in the network 🙈 Those extra buffers cause high latency and latency variation, which is a huge problem because more and more interactive apps (think voice over IP, real-time video streaming, and financial transactions) are running on the Internet. High latency and latency variation totally wreck app performance. We really need smart queue management schemes that can control latency and latency variation, so users get the quality of service they deserve 💅
This document presents a lightweight active queue management design called "PIE" (Proportional Integral controller Enhanced), and it can effectively control the average queuing latency to a target value 🎯 Simulation results, theoretical analysis, and Linux testbed results have all shown that PIE can keep latency low and still achieve high link utilization in a bunch of different congestion situations 🔥 The design doesn't need per-packet timestamps, so it adds very little overhead and is simple enough to implement in both hardware and software 🫶
Status of This Memo 📜
This document is not an Internet Standards Track specification. It's published for examination, experimental implementation, and evaluation 🧪
This document defines an Experimental Protocol for the Internet community. It's a product of the Internet Engineering Task Force (IETF) and 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 🌈
Info about the current status of this document, any errata, and how to give feedback on it can be found 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, because 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 they're provided without warranty as described in the Simplified BSD License 📝
1. Introduction 💖
Smart phones, tablets, and video traffic are exploding across the Internet, and that brings a whole unique set of challenges for congestion control 😭 To avoid packet drops, lots of service providers or data-center operators ask vendors to put in as much buffer as possible. Memory chip prices have dropped so fast that those requests are easy to accommodate, so everyone stays happy 🍓 This solution does succeed at assuring low packet loss and high TCP throughput, but it has a major downside 💀 TCP keeps increasing its sending rate and causes network buffers to fill up. TCP only cuts its rate when it gets a packet drop or mark that gets interpreted as a congestion signal. The catch is that drops and marks usually happen when network buffers are full or almost full. So all those excess buffers, which were originally designed to avoid packet drops, end up causing highly elevated queuing latency and latency variation 😩 Designing a queue management scheme is a delicate balancing act. It not only should let short-term bursts smoothly pass, but it also should control the average latency when there are long-running greedy flows around 🧚
Active Queue Management (AQM) schemes could potentially solve this problem ✨ AQM schemes like 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 in software. The unfortunate part is that RED needs careful tuning of its parameters for different network conditions, so most network operators just don't turn RED on 🙈 Also, RED is designed to control the queue length, which affects latency implicitly. It doesn't control latency directly. So the Internet today still lacks an effective design that can control buffer latency and improve the quality of experience for latency-sensitive apps 😤 The more recently published RFC 7567 calls for new methods of controlling network latency 🫶
New algorithms are starting to emerge that control queuing latency directly to tackle bufferbloat [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 🌸 Like RED, PIE randomly drops an incoming packet at the onset of congestion. The difference is that congestion detection is based on queuing latency instead of queue length (as with RED) ⭐ PIE also uses the derivative (rate of change) of the queuing latency to help figure out congestion levels and an appropriate response. The design parameters of PIE are chosen through control theory stability analysis. These parameters can be fixed to work in various traffic conditions, but they could also be made self-tuning to optimize system performance 🌈
Separately, it's 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 has been 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 built on top of FQ or CBQ could benefit from these advantages. 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 make sure their latency is better controlled and their fairness is not worse than 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 their active queue management algorithm 📡 On top of cable-specific improvements, the PIE design in DOCSIS 3.1 [RFC8034] has improved on the original design in several areas, including derandomization of coin tosses and enhanced burst protection 🦋
This document describes the design of PIE and splits it into basic elements and optional components that may be implemented to boost 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 with various flows' round-trip times. Latency bloat is the real issue that needs to be addressed, because it impairs real-time applications. If latency can be controlled, bufferbloat stops being 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 make TCP back off and avoid queue buildup. On the other hand, TCP's rate reduction could result in link underutilization. So there's a delicate balance between 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 keep 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, and not design parameters 👑
In the following text, we'll go through the design of PIE and how it operates in detail 🌈
Part 1 of 6 done, bestie 🫶 Part 2 picks up with Section 4, where the basic PIE scheme starts getting really fun 💖
4. The Basic PIE Scheme ✨
okay so PIE is literally made of three simple parts 🧚: a) random dropping when a packet enqueues, b) periodic drop probability updates, and c) latency calculation. when a packet shows up, the queue flips a little coin to decide whether to drop it 🪙. then the drop probability gets refreshed on a schedule, based on how far the current latency is from the target and whether the queuing latency is trending up or down 📈📉. the queuing latency can come from direct measurements or be estimated from the queue length and the dequeue rate, so you get options bestie 💅
the detailed definition of the parameters is in Appendix A of this document ("The Basic PIE Pseudocode") 🎀. any state variables PIE keeps are written with "PIE->" in front of them. if you want the full algorithm tea, check the full paper [HPSR-PIE] 📄
Random Drop
/ --------------
-------/ --------------> | | | | | -------------->
/|\ | | | | |
| --------------
| Queue Buffer \
| | \
| |Queue \
| |Length \
| | \
| \|/ \/
| ----------------- -------------------
| | Drop | | |
-----<-----| Probability |<---| Latency |
| Calculation | | Calculation |
----------------- -------------------
Figure 1: The PIE Structurethe picture above is Figure 1, and honestly it's giving architecture 🏛️🌸
4.1. Random Dropping
PIE randomly drops a packet when it arrives at a queue, using a drop probability called PIE->drop_prob_. that number comes from the drop-probability-calculation component 🎲. the random drop gets triggered by a packet arriving, right before it gets enqueued 💌
- Upon a packet enqueue:
randomly drop the packet with a probability of PIE->drop_prob_.
now here's the work-conserving glow-up 🌈. PIE wants the link to stay busy, so it skips the random drop in two cases. the first is when the latency sample, PIE->qdelay_old_, is smaller than half of the target latency (QDELAY_REF) AND the drop probability isn't too high (that means PIE->drop_prob_ < 0.2). the second is when 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) 🦋, so check out Section 5.1 for the details 💜
4.2. Drop Probability Calculation
PIE updates the drop probability on a schedule, using the latency samples 🕰️. it looks at the current latency sample AND whether the latency is trending up or down. this is the classic Proportional Integral (PI) controller method, and it's known for getting rid of steady-state errors 👑. controllers like this have been studied before for controlling queue length [PI] [QCN]. PIE uses the PI controller to control latency instead ✨. the algorithm also auto-adjusts its control parameters based on how heavy the congestion is, which you can read from the current drop probability. and the current drop probability is a direct measure of the current congestion level, so there's no need to measure arrival rate and dequeue rate mismatches 🙈
when a congestion period ends, you might be stuck with a high drop probability even though packets are arriving lightly 😭. so PIE has a mechanism where the drop probability decays exponentially (not linearly) when the system isn't congested 🍓. this helps the drop probability converge to 0 faster, and the PI controller makes sure it eventually hits zero anyway 🔥. the decay parameter of 2% gives a time constant of around 50 * T_UPDATE ⏳
specifically, PIE 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- store the current latency value:
PIE->qdelay_old_ = current_qdelay.the update interval, T_UPDATE, defaults to 15 milliseconds ⏱️. it MAY be reduced on high-speed links to give a smoother response 🏎️💨. the target latency, QDELAY_REF, SHOULD be set to 15 milliseconds 🎯. current_qdelay and PIE->qdelay_old_ are the current and previous samples of queuing latency, and they're calculated by the "latency calculation" component (see Section 4.3) 💅. current_qdelay is just a temporary variable, while PIE->qdelay_old_ is a state variable PIE keeps. the drop probability is a value between 0 and 1, but implementations can totally use integers too 🔢
the controller parameters, alpha and beta (expressed in Hz), were designed with feedback loop analysis. TCP's behaviour was modelled using results from well-studied prior art [TCP-Models] 🧠. also, adjusting 'p' like this effectively scales alpha and beta based on the current congestion level shown by the drop probability 🪄
the theoretical analysis of PIE is in [HPSR-PIE] 📚. as a rule of thumb, to keep the same feedback loop dynamics: if you cut T_UPDATE in half, you should also cut alpha in half and increase beta by alpha/4 🍰. if the target latency gets reduced (for example, for data-center use), alpha and beta should go up by the same order of magnitude that the target latency went down 🏢. for example, if QDELAY_REF goes from 15 milliseconds to 150 microseconds (that's two orders of magnitude!), then alpha and beta should be increased to alpha * 100 and beta * 100 💯
4.3. Latency Calculation
PIE uses latency to calculate the 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 ⏰
4.4. Burst Tolerance
PIE doesn't penalize short-term packet bursts, as suggested in [RFC7567] 🌊. PIE lets bursts through that create finite-duration events where the current queuing latency goes over QDELAY_REF, and it doesn't trigger any packet drops 🙌. this document introduces a parameter called "MAX_BURST", and MAX_BURST defines the burst duration that gets 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 do burst tolerance, two basic components of PIE are involved: "random dropping" and "drop probability calculation" 🤝. here's what the PIE algorithm does:
- 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 as PIE->burst_allowance_, starts out set to MAX_BURST 🍼. as long as PIE->burst_allowance_ is above zero, an incoming packet gets enqueued and skips the random drop entirely 🏃♀️. at every update, PIE->burst_allowance_ goes down by the update period, T_UPDATE, and it bottoms out at 0 🪫. when the congestion goes away (defined here as PIE->drop_prob_ equals 0 AND both the current and previous latency samples are less than half of QDELAY_REF) 🥳, PIE->burst_allowance_ gets reset to MAX_BURST. it's the comeback arc 💜
5. Optional Design Elements of PIE 🎀
there are several enhancements that can be added to boost the basic algorithm's performance 🚀. for clarity, they're all collected in this section 📋
5.1. ECN Support
PIE MAY support ECN by marking (rather than dropping) ECN-capable packets [ECN] 🏳️🌈. this document introduces another threshold called "mark_ecnth", and it works as a safeguard: if the calculated drop probability goes over mark_ecnth, PIE goes back 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 🌸
okay bestie, so a latency sample can only be grabbed when a packet reaches the head of the queue 👀 but sometimes you need a quick answer, or there's no direct sample at all. that's when you measure the dequeue rate instead 💅 the draining rate of a queue usually wiggles around because other queues share the same link or because the link capacity just fluctuates. wireless networks are especially chaotic about this, literally the drama queen of links 🙈
you can measure it right at the dequeue operation. quick heads up tho: short, non-persistent bursts can leave the queue empty every now and then, and that makes the measurement less accurate. so PIE only measures latency when there's enough data in the buffer, meaning the queue length is over a certain threshold (DQ_THRESHOLD). PIE times how long it takes to drain DQ_THRESHOLD packets ⏱️ here's how the rate estimation works:
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 PIE->dq_count_ is basically your running tally of bytes that have left since the last measurement 🧮 once it goes over DQ_THRESHOLD, boom, you get a sample ✨ the doc recommends setting the threshold to 16 KB, assuming a typical packet size of around 1 KB or 1.5 KB. that's enough data to get a solid average draining rate, but it's also fast enough (< 64 KB) to notice sudden changes in the draining rate 🏎️ if DQ_THRESHOLD ends up smaller than 64 KB, a small weight gets used to smooth out the dequeue time and produce PIE->avg_dq_time_. the dequeue rate is then just DQ_THRESHOLD divided by PIE->avg_dq_time_. the threshold isn't crucial for system stability, so no stress 🫶
one more thing that's lowkey important: the update interval for the drop probability calculation is not the same as the rate measurement cycle 🙌 the drop probability calculation happens periodically per Section 4.2, and it happens even when the algorithm isn't in a measurement cycle. in that case, the previously latched value of PIE->avg_dq_time_ gets used 💖
Random Drop
/ --------------
-------/ --------------------> | | | | | -------------->
/|\ | | | | | |
| | --------------
| | Queue Buffer
| | |
| | |Queue
| | |Length
| | |
| \|/ \|/
| ------------------------------
| | Dequeue Rate |
-----<-----| & Drop Probability |
| Calculation |
------------------------------
Figure 2: The Enqueue-Based PIE Structuresome platforms keep enqueuing and dequeuing in totally separate modules that don't know about each other 🙃 for those cases, you can build a pure enqueue-based design, which is what Figure 2 shows. the dequeue rate gets deduced from the number of packets enqueued and the queue length. the big idea is this: over a certain time interval, the number of dequeued packets equals the number of enqueued packets minus the number of packets still sitting in the queue 🧠 so everything can be triggered by packet arrival, including the background update process. and honestly, the design complexity here is similar to the original design, so it's not a whole new headache 💅
5.3. Setting PIE Active and Inactive 🦋
traffic naturally fluctuates in a network, so it's better not to drop packets just because queuing latency had a spurious uptick 🌊 PIE has an optional feature where it automatically becomes active or inactive. to do that, PIE may choose to only become active (from inactive) when the buffer occupancy goes 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 and the current and previous latency samples are all below half of QDELAY_REF 🎀
ideally, PIE would switch active and inactive based on latency. but calculating latency while PIE is inactive would add unnecessary packet-processing overhead 😩 so after weighing the trade-offs, the authors decided to compare against the tail drop threshold instead, to keep things simple ✨
when PIE optionally becomes active or inactive, the burst protection logic from Section 4.4 gets modified like this:
- "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 🎲
PIE uses random dropping to control latency, but independent coin tosses can cause outliers 😵💫 sometimes packets get dropped way too close together, and sometimes way too far apart. that makes the real drop percentage wobble away from the intended value PIE->drop_prob_. in certain scenarios, like a small number of simultaneous TCP flows, those wobbles can cause big swings in link utilization and queuing latency. so PIE may use a derandomization mechanism to dodge that mess 🧘♀️ the trick is a parameter called "PIE->accu_prob_", which gets reset to 0 after a drop. every time a packet arrives, PIE->accu_prob_ goes up 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 gets enqueued 📥 - if
PIE->accu_prob_is more than a high threshold, e.g., 8.5, and the queue is congested, the arriving packet is forced to be dropped 🚫 - a packet only gets randomly dropped if
PIE->accu_prob_falls between the two thresholds 🎰
since PIE->accu_prob_ resets to 0 after a drop, the next drop won't happen until 0.85/PIE->drop_prob_ packets later. that stops packets from being dropped too close to each other 🙅♀️ and in the opposite extreme, if 8.5/PIE->drop_prob_ packets have been enqueued without a drop, PIE forces one, so the drops don't get spaced too far apart. the full analysis is in [RFC8034] if you want the nerdy details 🤓
5.5. Cap Drop Adjustment 🧢
in the case of a single TCP flow, the queue can shoot up really fast during slow-start 🚀 that could make the drop probability jump super rapidly, which would seriously hurt throughput in this scenario. so to stop that excessive ramp-up, 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 💅
okay bestie, PIE is lowkey the easiest AQM to bolt onto stuff that already exists 🧚 There are three steps in PIE (as covered in Section 4), so let's look at how hard each one is ✨
When a packet shows up, PIE just randomly drops it based on the drop probability 🎲 That's the whole step. It's giving straightforward, and it doesn't need to poke around in packet headers or change them at all 🫶 If your implementation doesn't use packet timestamps to calculate latency, PIE doesn't need any extra memory 💖 Also, the input side of a queue is usually under software control while the output side is hardware based, so a drop at enqueuing can be readily retrofitted into existing or software implementations 🔧
The drop probability calculation runs in the background, once every T_UPDATE interval 🧠 With modern high-speed links, that works out to once every tens, hundreds, or even thousands of packets 🚀 So this calculation runs on a way slower time scale than packet processing, at least an order of magnitude slower 🐢 It involves multiplications using alpha and beta. PIE's control law is robust to minor changes in those values, so an implementation MAY round them to the closest multiples of 2 or 1/2 (e.g., alpha = 1/8, beta = 1 + 1/4) so the multiplications can be done with simple adds and shifts 🍓 No complicated functions are needed, so PIE is easy to implement in both hardware and software 👑 The state is only three variables per queue, burst_allowance_, PIE->drop_prob_, and PIE->qdelay_old_, so the memory overhead stays small 🌸
If you choose to implement departure rate estimation, PIE keeps a counter of the bytes departed for the current interval 🧮 That counter goes up on every packet departure. Every T_UPDATE, PIE works out latency from the departure rate, which can be done with a single multiply operation ⏱️ Plenty of network devices already track an interface's departure rate, so PIE might reuse that info and simply skip the third step of the algorithm, meaning it costs nothing extra 🙌 And if a platform already uses packet timestamps for other stuff, PIE can use those timestamps for latency calculation instead of estimating the departure rate 🦋
Flow queuing can also team up with PIE to isolate flows from each other 🫧 In that case it's preferable to have an independent drop probability per queue. That way each flow gets the most appropriate congestion signal, and sparse flows are protected from packet drops 💜 Running the entire PIE algorithm separately on every queue just to calculate drop probability may be overkill, though 😅 Also, when departure rate estimation is used to predict queuing latency, you can't calculate an accurate per-queue departure rate to run the PIE drop probability calculation on. So it has been proposed [DOCSIS-AQM] that you run one PIE drop probability calculation based on the overall latency estimate, then scale each queue's drop probability by the ratio of queue depth between that queue and the current largest queue 📏 This scaling is pretty simple and has a couple of nice properties:
- If a packet arrives to an empty queue, it gets total immunity from packet drops, no matter what the other queues are up to 🛡️
- If only a single queue is in use, the algorithm behaves exactly like the single-queue PIE algorithm 🎀
So yeah, PIE is simple enough to implement in both software and hardware 💅
7. Scope of Experimentation 🔬
PIE is the design presented in this document, and it effectively controls the average queuing latency to a target value 🎯 Here are some areas 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'd 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 run to experiment with further improvements to PIE's performance 🧪
Not all network nodes can be changed altogether to adopt latency-based AQM schemes such as PIE, but 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 deployed and managed independently, with no need for interoperability between different network devices 🔌 Any individual buffer queue can also be incrementally upgraded to PIE, since 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, get 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 🧚
Since the data path only needs a simple coin toss and the control-path calculation happens on a much slower time scale, we don't foresee any scaling issues with the algorithm as link speed scales up 🏎️
9. Security Considerations 🔒
Security check, bestie: 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>.
[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>.
[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.Appendix A. The Basic PIE Pseudocode 🎀
okay so this appendix is the basic PIE pseudocode, and it's giving "here's the whole recipe, bestie" 💅 Here are the knobs you can turn first. ✨
QDELAY_REF: the AQM Latency Target (default: 15 milliseconds)MAX_BURST: the AQM Max Burst Allowance (default: 150 milliseconds)
Then there are the internal parameters, which are the stuff the algorithm uses behind the scenes:
- 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)
Next up is the table of status variables. Anything ending in an underscore is one of these:
burst_allowance_: current burst allowancedrop_prob_: The current packet drop probability. Reset to 0qdelay_old_: The previous queue delay. Reset to 0
And these are the public and system functions the pseudocode leans on, so you know what's what 🧚
queue_: Holds the pending packetsdrop(packet): Drops/discards a packetnow(): Returns the current timerandom(): Returns a uniform r.v. in the range 0 ~ 1queue_.byte_length(): Returns current queue_ length in bytesqueue_.enque(packet): Adds packet to tail of queue_queue_.deque(): Returns the packet from the head of queue_packet.size(): Returns size of packetpacket.timestamp_delay(): Returns timestamped packet latency
Here's the actual pseudocode, copied exactly as written so nothing gets lost in translation 🌸
============================
//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() {
//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;
} 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 💜
this one is the upgraded version, with the optional enhancement, and it's lowkey iconic 👑 The configurable parameters pick up one more friend here:
QDELAY_REF: the AQM Latency Target (default: 15 milliseconds)MAX_BURST: the AQM Max Burst Allowance (default: 150 milliseconds)MAX_ECNTH: the AQM Max ECN Marking Threshold (default: 10%)
The internal parameters get a few new ones too:
- 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
The status variables table is bigger now, so pay attention 🦋
active_: INACTIVE/ACTIVEburst_allowance_: current burst allowancedrop_prob_: The current packet drop probability. Reset to 0accu_prob_: Accumulated drop probability. Reset to 0qdelay_old_: The previous queue delay estimate. Reset to 0last_timestamp_: Timestamp of previous status updatedq_count_,measurement_start_,in_measurement_,avg_dq_time_. Variables for measuring average dequeue rate
Public and system functions, the sequel edition 🌈
queue_: Holds the pending packetsdrop(packet): Drops/discards a packetmark(packet): Marks ECN for a packetnow(): Returns the current timerandom(): Returns a uniform r.v. in the range 0 ~ 1queue_.byte_length(): Returns current queue_ length in bytesqueue_.enque(packet): Adds packet to tail of queue_queue_.deque(): Returns the packet from the head of queue_packet.size(): Returns size of packetpacket.ecn(): Returns whether packet is ECN capable or not
And the full pseudocode, verbatim, because implementers need every single character 🙈
============================
//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() {
//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 🫶
huge shoutout to the lovely people who helped make this happen, the real MVPs 🌸 Here are their details, exactly as they appear in the original:
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 SystemsAuthors' Addresses 💌
okay bestie, these are the four legends who wrote this thing, and yes, you can totally find them 🫶✨
Rong Pan 💖
Rong Pan
Cisco Systems
3625 Cisco Way
San Jose, CA 95134
United States of America
Email: ropan@cisco.comPreethi Natarajan 🦋
Preethi Natarajan
Cisco Systems
725 Alder Drive
Milpitas, CA 95035
United States of America
Email: prenatar@cisco.comFred Baker 🧚
Fred Baker
Santa Barbara, CA 93117
United States of America
Email: FredBaker.IETF@gmail.comGreg White 🌈
Greg White
CableLabs
858 Coal Creek Circle
Louisville, CO 80027
United States of America
Email: g.white@cablelabs.comThat's the whole crew, periodt 💅👑
📦 where this page comes from
- ietf: rfc8033 2017-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms