| 1 |
<pre>Internet Engineering Task Force (IETF) R. Pan |
| 2 |
Request for Comments: 8033 P. Natarajan |
| 3 |
Category: Experimental Cisco Systems |
| 4 |
ISSN: 2070-1721 F. Baker |
| 5 |
Unaffiliated |
| 6 |
G. White |
| 7 |
CableLabs |
| 8 |
February 2017 |
| 9 |
|
| 10 |
|
| 11 |
<span class="h1">Proportional Integral Controller Enhanced (PIE):</span> |
| 12 |
<span class="h1">A Lightweight Control Scheme to Address the Bufferbloat Problem</span> |
| 13 |
|
| 14 |
Abstract |
| 15 |
|
| 16 |
Bufferbloat is a phenomenon in which excess buffers in the network |
| 17 |
cause high latency and latency variation. As more and more |
| 18 |
interactive applications (e.g., voice over IP, real-time video |
| 19 |
streaming, and financial transactions) run in the Internet, high |
| 20 |
latency and latency variation degrade application performance. There |
| 21 |
is a pressing need to design intelligent queue management schemes |
| 22 |
that can control latency and latency variation, and hence provide |
| 23 |
desirable quality of service to users. |
| 24 |
|
| 25 |
This document presents a lightweight active queue management design |
| 26 |
called "PIE" (Proportional Integral controller Enhanced) that can |
| 27 |
effectively control the average queuing latency to a target value. |
| 28 |
Simulation results, theoretical analysis, and Linux testbed results |
| 29 |
have shown that PIE can ensure low latency and achieve high link |
| 30 |
utilization under various congestion situations. The design does not |
| 31 |
require per-packet timestamps, so it incurs very little overhead and |
| 32 |
is simple enough to implement in both hardware and software. |
| 33 |
|
| 34 |
|
| 35 |
|
| 36 |
|
| 37 |
|
| 38 |
|
| 39 |
|
| 40 |
|
| 41 |
|
| 42 |
|
| 43 |
|
| 44 |
|
| 45 |
|
| 46 |
|
| 47 |
|
| 48 |
|
| 49 |
|
| 50 |
|
| 51 |
|
| 52 |
<span class="grey">Pan, et al. Experimental [Page 1]</span></pre> |
| 53 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span> |
| 54 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 55 |
|
| 56 |
|
| 57 |
Status of This Memo |
| 58 |
|
| 59 |
This document is not an Internet Standards Track specification; it is |
| 60 |
published for examination, experimental implementation, and |
| 61 |
evaluation. |
| 62 |
|
| 63 |
This document defines an Experimental Protocol for the Internet |
| 64 |
community. This document is a product of the Internet Engineering |
| 65 |
Task Force (IETF). It represents the consensus of the IETF |
| 66 |
community. It has received public review and has been approved for |
| 67 |
publication by the Internet Engineering Steering Group (IESG). Not |
| 68 |
all documents approved by the IESG are a candidate for any level of |
| 69 |
Internet Standard; see <a href="./rfc7841#section-2">Section 2 of RFC 7841</a>. |
| 70 |
|
| 71 |
Information about the current status of this document, any errata, |
| 72 |
and how to provide feedback on it may be obtained at |
| 73 |
<a href="http://www.rfc-editor.org/info/rfc8033">http://www.rfc-editor.org/info/rfc8033</a>. |
| 74 |
|
| 75 |
Copyright Notice |
| 76 |
|
| 77 |
Copyright (c) 2017 IETF Trust and the persons identified as the |
| 78 |
document authors. All rights reserved. |
| 79 |
|
| 80 |
This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal |
| 81 |
Provisions Relating to IETF Documents |
| 82 |
(<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) in effect on the date of |
| 83 |
publication of this document. Please review these documents |
| 84 |
carefully, as they describe your rights and restrictions with respect |
| 85 |
to this document. Code Components extracted from this document must |
| 86 |
include Simplified BSD License text as described in Section 4.e of |
| 87 |
the Trust Legal Provisions and are provided without warranty as |
| 88 |
described in the Simplified BSD License. |
| 89 |
|
| 90 |
|
| 91 |
|
| 92 |
|
| 93 |
|
| 94 |
|
| 95 |
|
| 96 |
|
| 97 |
|
| 98 |
|
| 99 |
|
| 100 |
|
| 101 |
|
| 102 |
|
| 103 |
|
| 104 |
|
| 105 |
|
| 106 |
|
| 107 |
|
| 108 |
<span class="grey">Pan, et al. Experimental [Page 2]</span></pre> |
| 109 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span> |
| 110 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 111 |
|
| 112 |
|
| 113 |
Table of Contents |
| 114 |
|
| 115 |
<a href="#section-1">1</a>. Introduction ....................................................<a href="#page-3">3</a> |
| 116 |
<a href="#section-2">2</a>. Terminology .....................................................<a href="#page-5">5</a> |
| 117 |
<a href="#section-3">3</a>. Design Goals ....................................................<a href="#page-5">5</a> |
| 118 |
<a href="#section-4">4</a>. The Basic PIE Scheme ............................................<a href="#page-6">6</a> |
| 119 |
<a href="#section-4.1">4.1</a>. Random Dropping ............................................<a href="#page-7">7</a> |
| 120 |
<a href="#section-4.2">4.2</a>. Drop Probability Calculation ...............................<a href="#page-7">7</a> |
| 121 |
<a href="#section-4.3">4.3</a>. Latency Calculation ........................................<a href="#page-9">9</a> |
| 122 |
<a href="#section-4.4">4.4</a>. Burst Tolerance ...........................................<a href="#page-10">10</a> |
| 123 |
<a href="#section-5">5</a>. Optional Design Elements of PIE ................................<a href="#page-11">11</a> |
| 124 |
<a href="#section-5.1">5.1</a>. ECN Support ...............................................<a href="#page-11">11</a> |
| 125 |
<a href="#section-5.2">5.2</a>. Dequeue Rate Estimation ...................................<a href="#page-11">11</a> |
| 126 |
<a href="#section-5.3">5.3</a>. Setting PIE Active and Inactive ...........................<a href="#page-13">13</a> |
| 127 |
<a href="#section-5.4">5.4</a>. Derandomization ...........................................<a href="#page-14">14</a> |
| 128 |
<a href="#section-5.5">5.5</a>. Cap Drop Adjustment .......................................<a href="#page-15">15</a> |
| 129 |
<a href="#section-6">6</a>. Implementation Cost ............................................<a href="#page-15">15</a> |
| 130 |
<a href="#section-7">7</a>. Scope of Experimentation .......................................<a href="#page-17">17</a> |
| 131 |
<a href="#section-8">8</a>. Incremental Deployment .........................................<a href="#page-17">17</a> |
| 132 |
<a href="#section-9">9</a>. Security Considerations ........................................<a href="#page-18">18</a> |
| 133 |
<a href="#section-10">10</a>. References ....................................................<a href="#page-18">18</a> |
| 134 |
<a href="#section-10.1">10.1</a>. Normative References .....................................<a href="#page-18">18</a> |
| 135 |
<a href="#section-10.2">10.2</a>. Informative References ...................................<a href="#page-18">18</a> |
| 136 |
<a href="#appendix-A">Appendix A</a>. The Basic PIE Pseudocode ..............................<a href="#page-21">21</a> |
| 137 |
<a href="#appendix-B">Appendix B</a>. Pseudocode for PIE with Optional Enhancement ..........<a href="#page-24">24</a> |
| 138 |
Contributors ......................................................<a href="#page-29">29</a> |
| 139 |
Authors' Addresses ................................................<a href="#page-30">30</a> |
| 140 |
|
| 141 |
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span> |
| 142 |
|
| 143 |
The explosion of smart phones, tablets, and video traffic in the |
| 144 |
Internet brings about a unique set of challenges for congestion |
| 145 |
control. To avoid packet drops, many service providers or |
| 146 |
data-center operators require vendors to put in as much buffer as |
| 147 |
possible. Because of the rapid decrease in memory chip prices, these |
| 148 |
requests are easily accommodated to keep customers happy. While this |
| 149 |
solution succeeds in assuring low packet loss and high TCP |
| 150 |
throughput, it suffers from a major downside. TCP continuously |
| 151 |
increases its sending rate and causes network buffers to fill up. |
| 152 |
TCP cuts its rate only when it receives a packet drop or mark that is |
| 153 |
interpreted as a congestion signal. However, drops and marks usually |
| 154 |
occur when network buffers are full or almost full. As a result, |
| 155 |
excess buffers, initially designed to avoid packet drops, would lead |
| 156 |
to highly elevated queuing latency and latency variation. Designing |
| 157 |
a queue management scheme is a delicate balancing act: it not only |
| 158 |
should allow short-term bursts to smoothly pass but also should |
| 159 |
control the average latency in the presence of long-running greedy |
| 160 |
flows. |
| 161 |
|
| 162 |
|
| 163 |
|
| 164 |
<span class="grey">Pan, et al. Experimental [Page 3]</span></pre> |
| 165 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span> |
| 166 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 167 |
|
| 168 |
|
| 169 |
Active Queue Management (AQM) schemes could potentially solve the |
| 170 |
aforementioned problem. AQM schemes, such as Random Early Detection |
| 171 |
(RED) [<a href="#ref-RED" title=""Random Early Detection (RED) Gateways for Congestion Avoidance"">RED</a>] as suggested in [<a href="./rfc2309" title=""Recommendations on Queue Management and Congestion Avoidance in the Internet"">RFC2309</a>] (which is now obsoleted by |
| 172 |
[<a href="./rfc7567" title=""IETF Recommendations Regarding Active Queue Management"">RFC7567</a>]), have been around for well over a decade. RED is |
| 173 |
implemented in a wide variety of network devices, both in hardware |
| 174 |
and software. Unfortunately, due to the fact that RED needs careful |
| 175 |
tuning of its parameters for various network conditions, most network |
| 176 |
operators don't turn RED on. In addition, RED is designed to control |
| 177 |
the queue length, which would affect latency implicitly. It does not |
| 178 |
control latency directly. Hence, the Internet today still lacks an |
| 179 |
effective design that can control buffer latency to improve the |
| 180 |
quality of experience to latency-sensitive applications. The more |
| 181 |
recently published <a href="./rfc7567">RFC 7567</a> calls for new methods of controlling |
| 182 |
network latency. |
| 183 |
|
| 184 |
New algorithms are beginning to emerge to control queuing latency |
| 185 |
directly to address the bufferbloat problem [<a href="#ref-CoDel" title=""Controlling Queue Delay"">CoDel</a>]. Along these |
| 186 |
lines, Proportional Integral controller Enhanced (PIE) also aims to |
| 187 |
keep the benefits of RED, including easy implementation and |
| 188 |
scalability to high speeds. Similar to RED, PIE randomly drops an |
| 189 |
incoming packet at the onset of congestion. Congestion detection, |
| 190 |
however, is based on the queuing latency instead of the queue length |
| 191 |
(as with RED). Furthermore, PIE also uses the derivative (rate of |
| 192 |
change) of the queuing latency to help determine congestion levels |
| 193 |
and an appropriate response. The design parameters of PIE are chosen |
| 194 |
via control theory stability analysis. While these parameters can be |
| 195 |
fixed to work in various traffic conditions, they could be made |
| 196 |
self-tuning to optimize system performance. |
| 197 |
|
| 198 |
Separately, it is assumed that any latency-based AQM scheme would be |
| 199 |
applied over a Fair Queuing (FQ) structure or one of its approximate |
| 200 |
designs, Flow Queuing or Class-Based Queuing (CBQ). FQ is one of the |
| 201 |
most studied scheduling algorithms since it was first proposed in |
| 202 |
1985 [<a href="./rfc970" title=""On Packet Switches With Infinite Storage"">RFC970</a>]. CBQ has been a standard feature in most network |
| 203 |
devices today [<a href="#ref-CBQ" title=""Class-Based Weighted Fair Queueing"">CBQ</a>]. Any AQM scheme that is built on top of FQ or |
| 204 |
CBQ could benefit from these advantages. Furthermore, these |
| 205 |
advantages, such as per-flow or per-class fairness, are orthogonal to |
| 206 |
the AQM design whose primary goal is to control latency for a given |
| 207 |
queue. For flows that are classified into the same class and put |
| 208 |
into the same queue, one needs to ensure that their latency is better |
| 209 |
controlled and that their fairness is not worse than those under the |
| 210 |
standard DropTail or RED design. More details about the relationship |
| 211 |
between FQ and AQM can be found in [<a href="./rfc7806" title=""On Queuing, Marking, and Dropping"">RFC7806</a>]. |
| 212 |
|
| 213 |
In October 2013, CableLabs' Data-Over-Cable Service Interface |
| 214 |
Specification 3.1 (DOCSIS 3.1) specification [<a href="#ref-DOCSIS_3.1">DOCSIS_3.1</a>] mandated |
| 215 |
that cable modems implement a specific variant of the PIE design as |
| 216 |
the active queue management algorithm. In addition to cable-specific |
| 217 |
|
| 218 |
|
| 219 |
|
| 220 |
<span class="grey">Pan, et al. Experimental [Page 4]</span></pre> |
| 221 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span> |
| 222 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 223 |
|
| 224 |
|
| 225 |
improvements, the PIE design in DOCSIS 3.1 [<a href="./rfc8034" title=""Active Queue Management (AQM) Based on Proportional Integral Controller Enhanced (PIE) for Data-Over-Cable Service Interface Specifications (DOCSIS) Cable Modems"">RFC8034</a>] has improved the |
| 226 |
original design in several areas, including derandomization of coin |
| 227 |
tosses and enhanced burst protection. |
| 228 |
|
| 229 |
This document describes the design of PIE and separates it into basic |
| 230 |
elements and optional components that may be implemented to enhance |
| 231 |
the performance of PIE. |
| 232 |
|
| 233 |
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Terminology</span> |
| 234 |
|
| 235 |
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", |
| 236 |
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this |
| 237 |
document are to be interpreted as described in <a href="./rfc2119">RFC 2119</a> [<a href="./rfc2119" title=""Key words for use in RFCs to Indicate Requirement Levels"">RFC2119</a>]. |
| 238 |
|
| 239 |
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Design Goals</span> |
| 240 |
|
| 241 |
A queue management framework is designed to improve the performance |
| 242 |
of interactive and latency-sensitive applications. It should follow |
| 243 |
the general guidelines set by the AQM working group document "IETF |
| 244 |
Recommendations Regarding Active Queue Management" [<a href="./rfc7567" title=""IETF Recommendations Regarding Active Queue Management"">RFC7567</a>]. More |
| 245 |
specifically, the PIE design has the following basic criteria. |
| 246 |
|
| 247 |
* First, queuing latency, instead of queue length, is controlled. |
| 248 |
Queue sizes change with queue draining rates and various flows' |
| 249 |
round-trip times. Latency bloat is the real issue that needs to |
| 250 |
be addressed, as it impairs real-time applications. If latency |
| 251 |
can be controlled, bufferbloat is not an issue. In fact, once |
| 252 |
latency is under control, it frees up buffers for sporadic bursts. |
| 253 |
|
| 254 |
* Secondly, PIE aims to attain high link utilization. The goal of |
| 255 |
low latency shall be achieved without suffering link |
| 256 |
underutilization or losing network efficiency. An early |
| 257 |
congestion signal could cause TCP to back off and avoid queue |
| 258 |
buildup. On the other hand, however, TCP's rate reduction could |
| 259 |
result in link underutilization. There is a delicate balance |
| 260 |
between achieving high link utilization and low latency. |
| 261 |
|
| 262 |
* Furthermore, the scheme should be simple to implement and easily |
| 263 |
scalable in both hardware and software. PIE strives to maintain |
| 264 |
design simplicity similar to that of RED, which has been |
| 265 |
implemented in a wide variety of network devices. |
| 266 |
|
| 267 |
* Finally, the scheme should ensure system stability for various |
| 268 |
network topologies and scale well across an arbitrary number of |
| 269 |
streams. Design parameters shall be set automatically. Users |
| 270 |
only need to set performance-related parameters such as target |
| 271 |
queue latency, not design parameters. |
| 272 |
|
| 273 |
|
| 274 |
|
| 275 |
|
| 276 |
<span class="grey">Pan, et al. Experimental [Page 5]</span></pre> |
| 277 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span> |
| 278 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 279 |
|
| 280 |
|
| 281 |
In the following text, the design of PIE and its operation are |
| 282 |
described in detail. |
| 283 |
|
| 284 |
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. The Basic PIE Scheme</span> |
| 285 |
|
| 286 |
As illustrated in Figure 1, PIE is comprised of three simple basic |
| 287 |
components: a) random dropping at enqueuing, b) periodic drop |
| 288 |
probability updates, and c) latency calculation. When a packet |
| 289 |
arrives, a random decision is made regarding whether to drop the |
| 290 |
packet. The drop probability is updated periodically based on how |
| 291 |
far the current latency is away from the target value and whether the |
| 292 |
queuing latency is currently trending up or down. The queuing |
| 293 |
latency can be obtained using direct measurements or using |
| 294 |
estimations calculated from the queue length and the dequeue rate. |
| 295 |
|
| 296 |
The detailed definition of parameters can be found in <a href="#appendix-A">Appendix A</a> of |
| 297 |
this document ("The Basic PIE Pseudocode"). Any state variables that |
| 298 |
PIE maintains are noted using "PIE->". For a full description of the |
| 299 |
algorithm, one can refer to the full paper [<a href="#ref-HPSR-PIE" title=""PIE: A lightweight control scheme to address the bufferbloat problem"">HPSR-PIE</a>]. |
| 300 |
|
| 301 |
Random Drop |
| 302 |
/ -------------- |
| 303 |
-------/ --------------> | | | | | --------------> |
| 304 |
/|\ | | | | | |
| 305 |
| -------------- |
| 306 |
| Queue Buffer \ |
| 307 |
| | \ |
| 308 |
| |Queue \ |
| 309 |
| |Length \ |
| 310 |
| | \ |
| 311 |
| \|/ \/ |
| 312 |
| ----------------- ------------------- |
| 313 |
| | Drop | | | |
| 314 |
-----<-----| Probability |<---| Latency | |
| 315 |
| Calculation | | Calculation | |
| 316 |
----------------- ------------------- |
| 317 |
|
| 318 |
Figure 1: The PIE Structure |
| 319 |
|
| 320 |
|
| 321 |
|
| 322 |
|
| 323 |
|
| 324 |
|
| 325 |
|
| 326 |
|
| 327 |
|
| 328 |
|
| 329 |
|
| 330 |
|
| 331 |
|
| 332 |
<span class="grey">Pan, et al. Experimental [Page 6]</span></pre> |
| 333 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span> |
| 334 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 335 |
|
| 336 |
|
| 337 |
<span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a>. Random Dropping</span> |
| 338 |
|
| 339 |
PIE randomly drops a packet upon its arrival to a queue according to |
| 340 |
a drop probability, PIE->drop_prob_, that is obtained from the |
| 341 |
drop-probability-calculation component. The random drop is triggered |
| 342 |
by a packet's arrival before enqueuing into a queue. |
| 343 |
|
| 344 |
* Upon a packet enqueue: |
| 345 |
|
| 346 |
randomly drop the packet with a probability of PIE->drop_prob_. |
| 347 |
|
| 348 |
To ensure that PIE is "work conserving", we bypass the random drop if |
| 349 |
the latency sample, PIE->qdelay_old_, is smaller than half of the |
| 350 |
target latency value (QDELAY_REF) when the drop probability is not |
| 351 |
too high (i.e., PIE->drop_prob_ < 0.2), or if the queue has less than |
| 352 |
a couple of packets. |
| 353 |
|
| 354 |
* Upon a packet enqueue, PIE does the following: |
| 355 |
|
| 356 |
//Safeguard PIE to be work conserving |
| 357 |
if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2) |
| 358 |
|| (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) |
| 359 |
return ENQUE; |
| 360 |
else |
| 361 |
randomly drop the packet with a probability of |
| 362 |
PIE->drop_prob_. |
| 363 |
|
| 364 |
PIE optionally supports Explicit Congestion Notification (ECN); see |
| 365 |
<a href="#section-5.1">Section 5.1</a>. |
| 366 |
|
| 367 |
<span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a>. Drop Probability Calculation</span> |
| 368 |
|
| 369 |
The PIE algorithm periodically updates the drop probability based on |
| 370 |
the latency samples -- not only the current latency sample but also |
| 371 |
whether the latency is trending up or down. This is the classical |
| 372 |
Proportional Integral (PI) controller method, which is known for |
| 373 |
eliminating steady-state errors. This type of controller has been |
| 374 |
studied before for controlling the queue length [<a href="#ref-PI" title=""On designing improved controllers for AQM routers supporting TCP flows"">PI</a>] [<a href="#ref-QCN" title=""IEEE Standard for Local and Metropolitan Area Networks--Virtual Bridged Local Area Networks - Amendment: 10: Congestion Notification"">QCN</a>]. PIE |
| 375 |
adopts the PI controller for controlling latency. The algorithm also |
| 376 |
auto-adjusts the control parameters based on how heavy the congestion |
| 377 |
is, which is reflected in the current drop probability. Note that |
| 378 |
the current drop probability is a direct measure of the current |
| 379 |
congestion level; there is no need to measure the arrival rate and |
| 380 |
dequeue rate mismatches. |
| 381 |
|
| 382 |
When a congestion period ends, we might be left with a high drop |
| 383 |
probability with light packet arrivals. Hence, the PIE algorithm |
| 384 |
includes a mechanism by which the drop probability decays |
| 385 |
|
| 386 |
|
| 387 |
|
| 388 |
<span class="grey">Pan, et al. Experimental [Page 7]</span></pre> |
| 389 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span> |
| 390 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 391 |
|
| 392 |
|
| 393 |
exponentially (rather than linearly) when the system is not |
| 394 |
congested. This would help the drop probability converge to 0 more |
| 395 |
quickly, while the PI controller ensures that it would eventually |
| 396 |
reach zero. The decay parameter of 2% gives us a time constant |
| 397 |
around 50 * T_UPDATE. |
| 398 |
|
| 399 |
Specifically, the PIE algorithm periodically adjusts the drop |
| 400 |
probability every T_UPDATE interval: |
| 401 |
|
| 402 |
* calculate drop probability PIE->drop_prob_, and autotune it as |
| 403 |
follows: |
| 404 |
|
| 405 |
p = alpha * (current_qdelay - QDELAY_REF) + |
| 406 |
beta * (current_qdelay - PIE->qdelay_old_); |
| 407 |
|
| 408 |
if (PIE->drop_prob_ < 0.000001) { |
| 409 |
p /= 2048; |
| 410 |
} else if (PIE->drop_prob_ < 0.00001) { |
| 411 |
p /= 512; |
| 412 |
} else if (PIE->drop_prob_ < 0.0001) { |
| 413 |
p /= 128; |
| 414 |
} else if (PIE->drop_prob_ < 0.001) { |
| 415 |
p /= 32; |
| 416 |
} else if (PIE->drop_prob_ < 0.01) { |
| 417 |
p /= 8; |
| 418 |
} else if (PIE->drop_prob_ < 0.1) { |
| 419 |
p /= 2; |
| 420 |
} else { |
| 421 |
p = p; |
| 422 |
} |
| 423 |
PIE->drop_prob_ += p; |
| 424 |
|
| 425 |
* decay the drop probability exponentially: |
| 426 |
|
| 427 |
if (current_qdelay == 0 && PIE->qdelay_old_ == 0) { |
| 428 |
PIE->drop_prob_ = PIE->drop_prob_ * 0.98; |
| 429 |
//1 - 1/64 is |
| 430 |
//sufficient |
| 431 |
} |
| 432 |
|
| 433 |
* bound the drop probability: |
| 434 |
|
| 435 |
if (PIE->drop_prob_ < 0) |
| 436 |
PIE->drop_prob_ = 0.0 |
| 437 |
if (PIE->drop_prob_ > 1) |
| 438 |
PIE->drop_prob_ = 1.0 |
| 439 |
|
| 440 |
|
| 441 |
|
| 442 |
|
| 443 |
|
| 444 |
<span class="grey">Pan, et al. Experimental [Page 8]</span></pre> |
| 445 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span> |
| 446 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 447 |
|
| 448 |
|
| 449 |
* store the current latency value: |
| 450 |
|
| 451 |
PIE->qdelay_old_ = current_qdelay. |
| 452 |
|
| 453 |
The update interval, T_UPDATE, is defaulted to be 15 milliseconds. |
| 454 |
It MAY be reduced on high-speed links in order to provide smoother |
| 455 |
response. The target latency value, QDELAY_REF, SHOULD be set to 15 |
| 456 |
milliseconds. The variables current_qdelay and PIE->qdelay_old_ |
| 457 |
represent the current and previous samples of the queuing latency, |
| 458 |
which are calculated by the "latency calculation" component (see |
| 459 |
<a href="#section-4.3">Section 4.3</a>). The variable current_qdelay is actually a temporary |
| 460 |
variable, while PIE->qdelay_old_ is a state variable that PIE keeps. |
| 461 |
The drop probability is a value between 0 and 1. However, |
| 462 |
implementations can certainly use integers. |
| 463 |
|
| 464 |
The controller parameters, alpha and beta (expressed in Hz), are |
| 465 |
designed using feedback loop analysis, where TCP's behaviors are |
| 466 |
modeled using the results from well-studied prior art [<a href="#ref-TCP-Models">TCP-Models</a>]. |
| 467 |
Note that the above adjustment of 'p' effectively scales the alpha |
| 468 |
and beta parameters based on the current congestion level indicated |
| 469 |
by the drop probability. |
| 470 |
|
| 471 |
The theoretical analysis of PIE can be found in [<a href="#ref-HPSR-PIE" title=""PIE: A lightweight control scheme to address the bufferbloat problem"">HPSR-PIE</a>]. As a |
| 472 |
rule of thumb, to keep the same feedback loop dynamics, if we cut |
| 473 |
T_UPDATE in half, we should also cut alpha by half and increase beta |
| 474 |
by alpha/4. If the target latency is reduced, e.g., for data-center |
| 475 |
use, the values of alpha and beta should be increased by the same |
| 476 |
order of magnitude by which the target latency is reduced. For |
| 477 |
example, if QDELAY_REF is reduced and changed from 15 milliseconds to |
| 478 |
150 microseconds -- a reduction of two orders of magnitude -- then |
| 479 |
alpha and beta values should be increased to alpha * 100 and |
| 480 |
beta * 100. |
| 481 |
|
| 482 |
<span class="h3"><a class="selflink" id="section-4.3" href="#section-4.3">4.3</a>. Latency Calculation</span> |
| 483 |
|
| 484 |
The PIE algorithm uses latency to calculate drop probability in one |
| 485 |
of two ways: |
| 486 |
|
| 487 |
* It estimates the current queuing latency using Little's law (see |
| 488 |
<a href="#section-5.2">Section 5.2</a> for details): |
| 489 |
|
| 490 |
current_qdelay = queue_.byte_length()/dequeue_rate; |
| 491 |
|
| 492 |
* It may use other techniques for calculating queuing latency, e.g., |
| 493 |
time-stamp the packets at enqueue, and use the timestamps to |
| 494 |
calculate latency during dequeue. |
| 495 |
|
| 496 |
|
| 497 |
|
| 498 |
|
| 499 |
|
| 500 |
<span class="grey">Pan, et al. Experimental [Page 9]</span></pre> |
| 501 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span> |
| 502 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 503 |
|
| 504 |
|
| 505 |
<span class="h3"><a class="selflink" id="section-4.4" href="#section-4.4">4.4</a>. Burst Tolerance</span> |
| 506 |
|
| 507 |
PIE does not penalize short-term packet bursts as suggested in |
| 508 |
[<a href="./rfc7567" title=""IETF Recommendations Regarding Active Queue Management"">RFC7567</a>]. PIE allows bursts of traffic that create finite-duration |
| 509 |
events in which current queuing latency exceeds QDELAY_REF without |
| 510 |
triggering packet drops. This document introduces a parameter called |
| 511 |
"MAX_BURST"; MAX_BURST defines the burst duration that will be |
| 512 |
protected. By default, the parameter SHOULD be set to 150 |
| 513 |
milliseconds. For simplicity, the PIE algorithm MAY effectively |
| 514 |
round MAX_BURST up to an integer multiple of T_UPDATE. |
| 515 |
|
| 516 |
To implement the burst tolerance function, two basic components of |
| 517 |
PIE are involved: "random dropping" and "drop probability |
| 518 |
calculation". The PIE algorithm does the following: |
| 519 |
|
| 520 |
* In the "random dropping" block and upon packet arrival, PIE checks |
| 521 |
the following: |
| 522 |
|
| 523 |
Upon a packet enqueue: |
| 524 |
if PIE->burst_allowance_ > 0 |
| 525 |
enqueue packet; |
| 526 |
else |
| 527 |
randomly drop a packet with a probability of |
| 528 |
PIE->drop_prob_. |
| 529 |
|
| 530 |
if (PIE->drop_prob_ == 0 and current_qdelay < QDELAY_REF/2 and |
| 531 |
PIE->qdelay_old_ < QDELAY_REF/2) |
| 532 |
PIE->burst_allowance_ = MAX_BURST; |
| 533 |
|
| 534 |
* In the "drop probability calculation" block, PIE additionally |
| 535 |
calculates: |
| 536 |
|
| 537 |
PIE->burst_allowance_ = max(0,PIE->burst_allowance_ - T_UPDATE); |
| 538 |
|
| 539 |
The burst allowance, noted by PIE->burst_allowance_, is initialized |
| 540 |
to MAX_BURST. As long as PIE->burst_allowance_ is above zero, an |
| 541 |
incoming packet will be enqueued, bypassing the random drop process. |
| 542 |
During each update instance, the value of PIE->burst_allowance_ is |
| 543 |
decremented by the update period, T_UPDATE, and is bottomed at 0. |
| 544 |
When the congestion goes away -- defined here as PIE->drop_prob_ |
| 545 |
equals 0 and both the current and previous samples of estimated |
| 546 |
latency are less than half of QDELAY_REF -- PIE->burst_allowance_ is |
| 547 |
reset to MAX_BURST. |
| 548 |
|
| 549 |
|
| 550 |
|
| 551 |
|
| 552 |
|
| 553 |
|
| 554 |
|
| 555 |
|
| 556 |
<span class="grey">Pan, et al. Experimental [Page 10]</span></pre> |
| 557 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span> |
| 558 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 559 |
|
| 560 |
|
| 561 |
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Optional Design Elements of PIE</span> |
| 562 |
|
| 563 |
There are several enhancements that are added to further augment the |
| 564 |
performance of the basic algorithm. For purposes of clarity, they |
| 565 |
are included in this section. |
| 566 |
|
| 567 |
<span class="h3"><a class="selflink" id="section-5.1" href="#section-5.1">5.1</a>. ECN Support</span> |
| 568 |
|
| 569 |
PIE MAY support ECN by marking (rather than dropping) ECN-capable |
| 570 |
packets [<a href="#ref-ECN" title=""Guidelines for Adding Congestion Notification to Protocols that Encapsulate IP"">ECN</a>]. This document introduces an additional threshold |
| 571 |
called "mark_ecnth", which acts as a safeguard: if the calculated |
| 572 |
drop probability exceeds mark_ecnth, PIE reverts to packet-dropping |
| 573 |
for ECN-capable packets. The variable mark_ecnth SHOULD be set to |
| 574 |
0.1 (10%). |
| 575 |
|
| 576 |
* To support ECN, the "random drop with a probability of |
| 577 |
PIE->drop_prob_" function in the "random dropping" block is |
| 578 |
changed to the following: |
| 579 |
|
| 580 |
* Upon a packet enqueue: |
| 581 |
|
| 582 |
if rand() < PIE->drop_prob_: |
| 583 |
if PIE->drop_prob_ < mark_ecnth && ecn_capable_packet == TRUE: |
| 584 |
mark packet; |
| 585 |
else |
| 586 |
drop packet; |
| 587 |
|
| 588 |
<span class="h3"><a class="selflink" id="section-5.2" href="#section-5.2">5.2</a>. Dequeue Rate Estimation</span> |
| 589 |
|
| 590 |
Using timestamps, a latency sample can only be obtained when a packet |
| 591 |
reaches the head of a queue. When a quick response time is desired |
| 592 |
or a direct latency sample is not available, one may obtain latency |
| 593 |
through measuring the dequeue rate. The draining rate of a queue in |
| 594 |
the network often varies either because other queues are sharing the |
| 595 |
same link or because the link capacity fluctuates. Rate fluctuation |
| 596 |
is particularly common in wireless networks. One may measure |
| 597 |
directly at the dequeue operation. Short, non-persistent bursts of |
| 598 |
packets result in empty queues from time to time; this would make the |
| 599 |
measurement less accurate. PIE only measures latency when there is |
| 600 |
sufficient data in the buffer, i.e., when the queue length is over a |
| 601 |
|
| 602 |
|
| 603 |
|
| 604 |
|
| 605 |
|
| 606 |
|
| 607 |
|
| 608 |
|
| 609 |
|
| 610 |
|
| 611 |
|
| 612 |
<span class="grey">Pan, et al. Experimental [Page 11]</span></pre> |
| 613 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span> |
| 614 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 615 |
|
| 616 |
|
| 617 |
certain threshold (DQ_THRESHOLD). PIE measures how long it takes to |
| 618 |
drain DQ_THRESHOLD packets. More specifically, the rate estimation |
| 619 |
can be implemented as follows: |
| 620 |
|
| 621 |
current_qdelay = queue_.byte_length() * |
| 622 |
PIE->avg_dq_time_/DQ_THRESHOLD; |
| 623 |
|
| 624 |
* Upon a packet dequeue: |
| 625 |
|
| 626 |
if PIE->in_measurement_ == FALSE and queue.byte_length() >= |
| 627 |
DQ_THRESHOLD: |
| 628 |
PIE->in_measurement_ = TRUE; |
| 629 |
PIE->measurement_start_ = now; |
| 630 |
PIE->dq_count_ = 0; |
| 631 |
|
| 632 |
if PIE->in_measurement_ == TRUE: |
| 633 |
PIE->dq_count_ = PIE->dq_count_ + deque_pkt_size; |
| 634 |
if PIE->dq_count_ >= DQ_THRESHOLD then |
| 635 |
weight = DQ_THRESHOLD/2^16 |
| 636 |
PIE->avg_dq_time_ = (now - PIE->measurement_start_) * |
| 637 |
weight + PIE->avg_dq_time_ * |
| 638 |
(1 - weight); |
| 639 |
PIE->dq_count_ = 0; |
| 640 |
PIE->measurement_start_ = now |
| 641 |
else |
| 642 |
PIE->in_measurement_ = FALSE; |
| 643 |
|
| 644 |
The parameter PIE->dq_count_ represents the number of bytes departed |
| 645 |
since the last measurement. Once PIE->dq_count_ is over |
| 646 |
DQ_THRESHOLD, a measurement sample is obtained. It is recommended |
| 647 |
that the threshold be set to 16 KB, assuming a typical packet size of |
| 648 |
around 1 KB or 1.5 KB. This threshold would allow sufficient data to |
| 649 |
obtain an average draining rate but would also be fast enough (< 64 |
| 650 |
KB) to reflect sudden changes in the draining rate. If DQ_THRESHOLD |
| 651 |
is smaller than 64 KB, a small weight is used to smooth out the |
| 652 |
dequeue time and obtain PIE->avg_dq_time_. The dequeue rate is |
| 653 |
simply DQ_THRESHOLD divided by PIE->avg_dq_time_. This threshold is |
| 654 |
not crucial for the system's stability. Please note that the update |
| 655 |
interval for calculating the drop probability is different from the |
| 656 |
rate measurement cycle. The drop probability calculation is done |
| 657 |
periodically per <a href="#section-4.2">Section 4.2</a>, and it is done even when the algorithm |
| 658 |
is not in a measurement cycle; in this case, the previously latched |
| 659 |
value of PIE->avg_dq_time_ is used. |
| 660 |
|
| 661 |
|
| 662 |
|
| 663 |
|
| 664 |
|
| 665 |
|
| 666 |
|
| 667 |
|
| 668 |
<span class="grey">Pan, et al. Experimental [Page 12]</span></pre> |
| 669 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span> |
| 670 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 671 |
|
| 672 |
|
| 673 |
Random Drop |
| 674 |
/ -------------- |
| 675 |
-------/ --------------------> | | | | | --------------> |
| 676 |
/|\ | | | | | | |
| 677 |
| | -------------- |
| 678 |
| | Queue Buffer |
| 679 |
| | | |
| 680 |
| | |Queue |
| 681 |
| | |Length |
| 682 |
| | | |
| 683 |
| \|/ \|/ |
| 684 |
| ------------------------------ |
| 685 |
| | Dequeue Rate | |
| 686 |
-----<-----| & Drop Probability | |
| 687 |
| Calculation | |
| 688 |
------------------------------ |
| 689 |
|
| 690 |
Figure 2: The Enqueue-Based PIE Structure |
| 691 |
|
| 692 |
In some platforms, enqueuing and dequeuing functions belong to |
| 693 |
different modules that are independent of each other. In such |
| 694 |
situations, a pure enqueue-based design can be developed. An |
| 695 |
enqueue-based design is depicted in Figure 2. The dequeue rate is |
| 696 |
deduced from the number of packets enqueued and the queue length. |
| 697 |
The design is based on the following key observation: over a certain |
| 698 |
time interval, the number of dequeued packets = the number of |
| 699 |
enqueued packets minus the number of remaining packets in the queue. |
| 700 |
In this design, everything can be triggered by packet arrival, |
| 701 |
including the background update process. The design complexity here |
| 702 |
is similar to the original design. |
| 703 |
|
| 704 |
<span class="h3"><a class="selflink" id="section-5.3" href="#section-5.3">5.3</a>. Setting PIE Active and Inactive</span> |
| 705 |
|
| 706 |
Traffic naturally fluctuates in a network. It would be preferable |
| 707 |
not to unnecessarily drop packets due to a spurious uptick in queuing |
| 708 |
latency. PIE has an optional feature of automatically becoming |
| 709 |
active/inactive. To implement this feature, PIE may choose to only |
| 710 |
become active (from inactive) when the buffer occupancy is over a |
| 711 |
certain threshold, which may be set to 1/3 of the tail drop |
| 712 |
threshold. PIE becomes inactive when congestion ends; i.e., when the |
| 713 |
drop probability reaches 0, current and previous latency samples are |
| 714 |
all below half of QDELAY_REF. |
| 715 |
|
| 716 |
Ideally, PIE should become active/inactive based on latency. |
| 717 |
However, calculating latency when PIE is inactive would introduce |
| 718 |
unnecessary packet-processing overhead. Weighing the trade-offs, |
| 719 |
we decided to compare against the tail drop threshold to keep things |
| 720 |
simple. |
| 721 |
|
| 722 |
|
| 723 |
|
| 724 |
<span class="grey">Pan, et al. Experimental [Page 13]</span></pre> |
| 725 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span> |
| 726 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 727 |
|
| 728 |
|
| 729 |
When PIE optionally becomes active/inactive, the burst protection |
| 730 |
logic described in <a href="#section-4.4">Section 4.4</a> is modified as follows: |
| 731 |
|
| 732 |
* "Random dropping" block: PIE adds the following: |
| 733 |
|
| 734 |
Upon packet arrival: |
| 735 |
|
| 736 |
if PIE->active_ == FALSE && queue_length >= TAIL_DROP/3: |
| 737 |
PIE->active_ = TRUE; |
| 738 |
PIE->burst_allowance_ = MAX_BURST; |
| 739 |
|
| 740 |
if PIE->burst_allowance_ > 0 |
| 741 |
enqueue packet; |
| 742 |
else |
| 743 |
randomly drop a packet with a probability of |
| 744 |
PIE->drop_prob_. |
| 745 |
|
| 746 |
if (PIE->drop_prob_ == 0 and current_qdelay < QDELAY_REF/2 and |
| 747 |
PIE->qdelay_old_ < QDELAY_REF/2) |
| 748 |
PIE->active_ = FALSE; |
| 749 |
PIE->burst_allowance_ = MAX_BURST; |
| 750 |
|
| 751 |
* "Drop probability calculation" block: PIE does the following: |
| 752 |
if PIE->active_ == TRUE: |
| 753 |
PIE->burst_allowance_ = |
| 754 |
max(0,PIE->burst_allowance_ - T_UPDATE); |
| 755 |
|
| 756 |
<span class="h3"><a class="selflink" id="section-5.4" href="#section-5.4">5.4</a>. Derandomization</span> |
| 757 |
|
| 758 |
Although PIE adopts random dropping to achieve latency control, |
| 759 |
independent coin tosses could introduce outlier situations where |
| 760 |
packets are dropped too close to each other or too far from each |
| 761 |
other. This would cause the real drop percentage to temporarily |
| 762 |
deviate from the intended value PIE->drop_prob_. In certain |
| 763 |
scenarios, such as a small number of simultaneous TCP flows, these |
| 764 |
deviations can cause significant deviations in link utilization and |
| 765 |
queuing latency. PIE may use a derandomization mechanism to avoid |
| 766 |
such situations. A parameter called "PIE->accu_prob_" is reset to 0 |
| 767 |
after a drop. Upon packet arrival, PIE->accu_prob_ is incremented by |
| 768 |
the amount of drop probability, PIE->drop_prob_. If PIE->accu_prob_ |
| 769 |
is less than a low threshold, e.g., 0.85, the arriving packet is |
| 770 |
enqueued; on the other hand, if PIE->accu_prob_ is more than a high |
| 771 |
threshold, e.g., 8.5, and the queue is congested, the arrival packet |
| 772 |
is forced to be dropped. A packet is only randomly dropped if |
| 773 |
PIE->accu_prob_ falls between the two thresholds. Since |
| 774 |
PIE->accu_prob_ is reset to 0 after a drop, another drop will not |
| 775 |
happen until 0.85/PIE->drop_prob_ packets later. This avoids packets |
| 776 |
being dropped too close to each other. In the other extreme case |
| 777 |
|
| 778 |
|
| 779 |
|
| 780 |
<span class="grey">Pan, et al. Experimental [Page 14]</span></pre> |
| 781 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span> |
| 782 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 783 |
|
| 784 |
|
| 785 |
where 8.5/PIE->drop_prob_ packets have been enqueued without |
| 786 |
incurring a drop, PIE would force a drop in order to prevent the |
| 787 |
drops from being spaced too far apart. Further analysis can be found |
| 788 |
in [<a href="./rfc8034" title=""Active Queue Management (AQM) Based on Proportional Integral Controller Enhanced (PIE) for Data-Over-Cable Service Interface Specifications (DOCSIS) Cable Modems"">RFC8034</a>]. |
| 789 |
|
| 790 |
<span class="h3"><a class="selflink" id="section-5.5" href="#section-5.5">5.5</a>. Cap Drop Adjustment</span> |
| 791 |
|
| 792 |
In the case of a single TCP flow, during the slow-start phase the |
| 793 |
queue could quickly increase, which could result in a very rapid |
| 794 |
increase in drop probability. In order to prevent an excessive |
| 795 |
ramp-up that could negatively impact the throughput in this scenario, |
| 796 |
PIE can cap the maximum drop probability increase in each step. |
| 797 |
|
| 798 |
* "Drop probability calculation" block: PIE adds the following: |
| 799 |
|
| 800 |
if (PIE->drop_prob_ >= 0.1 && p > 0.02) { |
| 801 |
p = 0.02; |
| 802 |
} |
| 803 |
|
| 804 |
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Implementation Cost</span> |
| 805 |
|
| 806 |
PIE can be applied to existing hardware or software solutions. There |
| 807 |
are three steps involved in PIE, as discussed in <a href="#section-4">Section 4</a>. Their |
| 808 |
complexities are examined below. |
| 809 |
|
| 810 |
Upon packet arrival, the algorithm simply drops a packet randomly, |
| 811 |
based on the drop probability. This step is straightforward and |
| 812 |
requires no packet header examination and manipulation. If the |
| 813 |
implementation doesn't rely on packet timestamps for calculating |
| 814 |
latency, PIE does not require extra memory. Furthermore, the input |
| 815 |
side of a queue is typically under software control while the output |
| 816 |
side of a queue is hardware based. Hence, a drop at enqueuing can be |
| 817 |
readily retrofitted into existing or software implementations. |
| 818 |
|
| 819 |
The drop probability calculation is done in the background, and it |
| 820 |
occurs every T_UPDATE interval. Given modern high-speed links, this |
| 821 |
period translates into once every tens, hundreds, or even thousands |
| 822 |
of packets. Hence, the calculation occurs at a much slower time |
| 823 |
scale than the packet-processing time -- at least an order of |
| 824 |
magnitude slower. The calculation of drop probability involves |
| 825 |
multiplications using alpha and beta. Since PIE's control law is |
| 826 |
robust to minor changes in alpha and beta values, an implementation |
| 827 |
MAY choose these values to the closest multiples of 2 or 1/2 (e.g., |
| 828 |
alpha = 1/8, beta = 1 + 1/4) such that the multiplications can be |
| 829 |
done using simple adds and shifts. As no complicated functions are |
| 830 |
required, PIE can be easily implemented in both hardware and |
| 831 |
|
| 832 |
|
| 833 |
|
| 834 |
|
| 835 |
|
| 836 |
<span class="grey">Pan, et al. Experimental [Page 15]</span></pre> |
| 837 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span> |
| 838 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 839 |
|
| 840 |
|
| 841 |
software. The state requirement is only three variables per queue: |
| 842 |
burst_allowance_, PIE->drop_prob_, and PIE->qdelay_old_. Hence, the |
| 843 |
memory overhead is small. |
| 844 |
|
| 845 |
If one chooses to implement the departure rate estimation, PIE uses a |
| 846 |
counter to keep track of the number of bytes departed for the current |
| 847 |
interval. This counter is incremented per packet departure. Every |
| 848 |
T_UPDATE, PIE calculates latency using the departure rate, which can |
| 849 |
be implemented using a single multiply operation. Note that many |
| 850 |
network devices keep track of an interface's departure rate. In this |
| 851 |
case, PIE might be able to reuse this information and simply skip the |
| 852 |
third step of the algorithm; hence, it would incur no extra cost. If |
| 853 |
a platform already leverages packet timestamps for other purposes, |
| 854 |
PIE can make use of these packet timestamps for latency calculation |
| 855 |
instead of estimating the departure rate. |
| 856 |
|
| 857 |
Flow queuing can also be combined with PIE to provide isolation |
| 858 |
between flows. In this case, it is preferable to have an independent |
| 859 |
value of drop probability per queue. This allows each flow to |
| 860 |
receive the most appropriate level of congestion signal and ensures |
| 861 |
that sparse flows are protected from experiencing packet drops. |
| 862 |
However, running the entire PIE algorithm independently on each queue |
| 863 |
in order to calculate the drop probability may be overkill. |
| 864 |
Furthermore, in the case where departure rate estimation is used to |
| 865 |
predict queuing latency, it is not possible to calculate an accurate |
| 866 |
per-queue departure rate upon which to implement the PIE drop |
| 867 |
probability calculation. Instead, it has been proposed [<a href="#ref-DOCSIS-AQM">DOCSIS-AQM</a>] |
| 868 |
that a single implementation of the PIE drop probability calculation |
| 869 |
based on the overall latency estimate be used, followed by a |
| 870 |
per-queue scaling of drop probability based on the ratio of |
| 871 |
queue depth between the queue in question and the current largest |
| 872 |
queue. This scaling is reasonably simple and has a couple of nice |
| 873 |
properties: |
| 874 |
|
| 875 |
* If a packet is arriving to an empty queue, it is given immunity |
| 876 |
from packet drops altogether, regardless of the state of the other |
| 877 |
queues. |
| 878 |
|
| 879 |
* In the situation where only a single queue is in use, the |
| 880 |
algorithm behaves exactly like the single-queue PIE algorithm. |
| 881 |
|
| 882 |
In summary, PIE is simple enough to be implemented in both software |
| 883 |
and hardware. |
| 884 |
|
| 885 |
|
| 886 |
|
| 887 |
|
| 888 |
|
| 889 |
|
| 890 |
|
| 891 |
|
| 892 |
<span class="grey">Pan, et al. Experimental [Page 16]</span></pre> |
| 893 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span> |
| 894 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 895 |
|
| 896 |
|
| 897 |
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. Scope of Experimentation</span> |
| 898 |
|
| 899 |
The design of the PIE algorithm is presented in this document. The |
| 900 |
PIE algorithm effectively controls the average queuing latency to a |
| 901 |
target value. The following areas can be used for further study and |
| 902 |
experimentation: |
| 903 |
|
| 904 |
* Autotuning of target latency without losing utilization. |
| 905 |
|
| 906 |
* Autotuning for the average round-trip time of traffic. |
| 907 |
|
| 908 |
* The proper threshold to transition smoothly between ECN marking |
| 909 |
and dropping. |
| 910 |
|
| 911 |
* The enhancements described in <a href="#section-5">Section 5</a>, which can be used in |
| 912 |
experiments to see if they would be of more value in the real |
| 913 |
world. If so, they will be incorporated into the basic PIE |
| 914 |
algorithm. |
| 915 |
|
| 916 |
* The PIE design, which is separated into the data path and the |
| 917 |
control path. The control path can be implemented in software. |
| 918 |
Field tests of other control laws can be performed to experiment |
| 919 |
with further improvements to PIE's performance. |
| 920 |
|
| 921 |
Although all network nodes cannot be changed altogether to adopt |
| 922 |
latency-based AQM schemes such as PIE, a gradual adoption would |
| 923 |
eventually lead to end-to-end low-latency service for all |
| 924 |
applications. |
| 925 |
|
| 926 |
<span class="h2"><a class="selflink" id="section-8" href="#section-8">8</a>. Incremental Deployment</span> |
| 927 |
|
| 928 |
From testbed experiments and large-scale simulations of PIE so far, |
| 929 |
PIE has been shown to be effective across a diverse range of network |
| 930 |
scenarios. There is no indication that PIE would be harmful to |
| 931 |
deploy. |
| 932 |
|
| 933 |
The PIE scheme can be independently deployed and managed without a |
| 934 |
need for interoperability between different network devices. In |
| 935 |
addition, any individual buffer queue can be incrementally upgraded |
| 936 |
to PIE, as it can coexist with existing AQM schemes such as |
| 937 |
Weighted RED (WRED). |
| 938 |
|
| 939 |
PIE is intended to be self-configuring. Users should not need to |
| 940 |
configure any design parameters. Upon installation, the two |
| 941 |
user-configurable parameters -- QDELAY_REF and MAX_BURST -- will be |
| 942 |
defaulted to 15 milliseconds and 150 milliseconds for non-data-center |
| 943 |
network devices and to 15 microseconds and 150 microseconds for |
| 944 |
data-center switches, respectively. |
| 945 |
|
| 946 |
|
| 947 |
|
| 948 |
<span class="grey">Pan, et al. Experimental [Page 17]</span></pre> |
| 949 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span> |
| 950 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 951 |
|
| 952 |
|
| 953 |
Since the data path of the algorithm needs only a simple coin toss |
| 954 |
and the control-path calculation happens in a much slower time scale, |
| 955 |
we don't foresee any scaling issues associated with the algorithm as |
| 956 |
the link speed scales up. |
| 957 |
|
| 958 |
<span class="h2"><a class="selflink" id="section-9" href="#section-9">9</a>. Security Considerations</span> |
| 959 |
|
| 960 |
This document describes PIE, an active queue management algorithm |
| 961 |
based on implementations in different products. The PIE algorithm |
| 962 |
introduces no specific security exposures. |
| 963 |
|
| 964 |
<span class="h2"><a class="selflink" id="section-10" href="#section-10">10</a>. References</span> |
| 965 |
|
| 966 |
<span class="h3"><a class="selflink" id="section-10.1" href="#section-10.1">10.1</a>. Normative References</span> |
| 967 |
|
| 968 |
[<a id="ref-RFC2119">RFC2119</a>] Bradner, S., "Key words for use in RFCs to Indicate |
| 969 |
Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>, |
| 970 |
DOI 10.17487/RFC2119, March 1997, |
| 971 |
<<a href="http://www.rfc-editor.org/info/rfc2119">http://www.rfc-editor.org/info/rfc2119</a>>. |
| 972 |
|
| 973 |
<span class="h3"><a class="selflink" id="section-10.2" href="#section-10.2">10.2</a>. Informative References</span> |
| 974 |
|
| 975 |
[<a id="ref-RFC970">RFC970</a>] Nagle, J., "On Packet Switches With Infinite Storage", |
| 976 |
<a href="./rfc970">RFC 970</a>, DOI 10.17487/RFC0970, December 1985, |
| 977 |
<<a href="http://www.rfc-editor.org/info/rfc970">http://www.rfc-editor.org/info/rfc970</a>>. |
| 978 |
|
| 979 |
[<a id="ref-RFC2309">RFC2309</a>] Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, |
| 980 |
S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., |
| 981 |
Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, |
| 982 |
S., Wroclawski, J., and L. Zhang, "Recommendations on |
| 983 |
Queue Management and Congestion Avoidance in the |
| 984 |
Internet", <a href="./rfc2309">RFC 2309</a>, DOI 10.17487/RFC2309, April 1998, |
| 985 |
<<a href="http://www.rfc-editor.org/info/rfc2309">http://www.rfc-editor.org/info/rfc2309</a>>. |
| 986 |
|
| 987 |
[<a id="ref-RFC7567">RFC7567</a>] Baker, F., Ed., and G. Fairhurst, Ed., "IETF |
| 988 |
Recommendations Regarding Active Queue Management", |
| 989 |
<a href="https://www.rfc-editor.org/bcp/bcp197">BCP 197</a>, <a href="./rfc7567">RFC 7567</a>, DOI 10.17487/RFC7567, July 2015, |
| 990 |
<<a href="http://www.rfc-editor.org/info/rfc7567">http://www.rfc-editor.org/info/rfc7567</a>>. |
| 991 |
|
| 992 |
[<a id="ref-RFC7806">RFC7806</a>] Baker, F. and R. Pan, "On Queuing, Marking, and Dropping", |
| 993 |
<a href="./rfc7806">RFC 7806</a>, DOI 10.17487/RFC7806, April 2016, |
| 994 |
<<a href="http://www.rfc-editor.org/info/rfc7806">http://www.rfc-editor.org/info/rfc7806</a>>. |
| 995 |
|
| 996 |
|
| 997 |
|
| 998 |
|
| 999 |
|
| 1000 |
|
| 1001 |
|
| 1002 |
|
| 1003 |
|
| 1004 |
<span class="grey">Pan, et al. Experimental [Page 18]</span></pre> |
| 1005 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span> |
| 1006 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1007 |
|
| 1008 |
|
| 1009 |
[<a id="ref-RFC8034">RFC8034</a>] White, G. and R. Pan, "Active Queue Management (AQM) Based |
| 1010 |
on Proportional Integral Controller Enhanced (PIE) for |
| 1011 |
Data-Over-Cable Service Interface Specifications (DOCSIS) |
| 1012 |
Cable Modems", <a href="./rfc8034">RFC 8034</a>, DOI 10.17487/RFC8034, |
| 1013 |
February 2017, <<a href="http://www.rfc-editor.org/info/rfc8034">http://www.rfc-editor.org/info/rfc8034</a>>. |
| 1014 |
|
| 1015 |
[<a id="ref-CBQ">CBQ</a>] Cisco, "Class-Based Weighted Fair Queueing", |
| 1016 |
<<a href="http://www.cisco.com/en/US/docs/ios/12_0t/12_0t5/feature/guide/cbwfq.html">http://www.cisco.com/en/US/docs/ios/12_0t/12_0t5/</a> |
| 1017 |
<a href="http://www.cisco.com/en/US/docs/ios/12_0t/12_0t5/feature/guide/cbwfq.html">feature/guide/cbwfq.html</a>>. |
| 1018 |
|
| 1019 |
[<a id="ref-CoDel">CoDel</a>] Nichols, K. and V. Jacobson, "Controlling Queue Delay", |
| 1020 |
Communications of the ACM, Volume 55, Issue 7, pp. 42-50, |
| 1021 |
DOI 10.1145/2209249.2209264, July 2012. |
| 1022 |
|
| 1023 |
[<a id="ref-DOCSIS_3.1">DOCSIS_3.1</a>] |
| 1024 |
CableLabs, "MAC and Upper Layer Protocols Interface |
| 1025 |
Specification", DOCSIS 3.1, January 2017, |
| 1026 |
<<a href="https://apps.cablelabs.com/specification/CM-SP-MULPIv3.1">https://apps.cablelabs.com/specification/</a> |
| 1027 |
<a href="https://apps.cablelabs.com/specification/CM-SP-MULPIv3.1">CM-SP-MULPIv3.1</a>>. |
| 1028 |
|
| 1029 |
[<a id="ref-DOCSIS-AQM">DOCSIS-AQM</a>] |
| 1030 |
White, G., "Active Queue Management in DOCSIS 3.x Cable |
| 1031 |
Modems", May 2014, <<a href="http://www.cablelabs.com/wp-content/uploads/2014/06/DOCSIS-AQM_May2014.pdf">http://www.cablelabs.com/wp-content/</a> |
| 1032 |
<a href="http://www.cablelabs.com/wp-content/uploads/2014/06/DOCSIS-AQM_May2014.pdf">uploads/2014/06/DOCSIS-AQM_May2014.pdf</a>>. |
| 1033 |
|
| 1034 |
[<a id="ref-ECN">ECN</a>] Briscoe, B., Kaippallimalil, J., and P. Thaler, |
| 1035 |
"Guidelines for Adding Congestion Notification to |
| 1036 |
Protocols that Encapsulate IP", Work in Progress, |
| 1037 |
<a href="./draft-ietf-tsvwg-ecn-encap-guidelines-07">draft-ietf-tsvwg-ecn-encap-guidelines-07</a>, July 2016. |
| 1038 |
|
| 1039 |
[<a id="ref-HPSR-PIE">HPSR-PIE</a>] Pan, R., Natarajan, P., Piglione, C., Prabhu, M.S., |
| 1040 |
Subramanian, V., Baker, F., and B. Ver Steeg, "PIE: A |
| 1041 |
lightweight control scheme to address the bufferbloat |
| 1042 |
problem", IEEE HPSR, DOI 10.1109/HPSR.2013.6602305, 2013, |
| 1043 |
<<a href="https://www.researchgate.net/publication/261134127_PIE_A_lightweight_control_scheme_to_address_the_bufferbloat_problem?origin=mail">https://www.researchgate.net/publication/</a> |
| 1044 |
<a href="https://www.researchgate.net/publication/261134127_PIE_A_lightweight_control_scheme_to_address_the_bufferbloat_problem?origin=mail">261134127_PIE_A_lightweight_control_scheme_to_address_</a> |
| 1045 |
<a href="https://www.researchgate.net/publication/261134127_PIE_A_lightweight_control_scheme_to_address_the_bufferbloat_problem?origin=mail">the_bufferbloat_problem?origin=mail</a>>. |
| 1046 |
|
| 1047 |
[<a id="ref-PI">PI</a>] Hollot, C.V., Misra, V., Towsley, D., and W. Gong, "On |
| 1048 |
designing improved controllers for AQM routers supporting |
| 1049 |
TCP flows", INFOCOM 2001, DOI 10.1109/INFCOM.2001.916670, |
| 1050 |
April 2001. |
| 1051 |
|
| 1052 |
[<a id="ref-QCN">QCN</a>] IEEE, "IEEE Standard for Local and Metropolitan Area |
| 1053 |
Networks--Virtual Bridged Local Area Networks - |
| 1054 |
Amendment: 10: Congestion Notification", IEEE 802.1Qau, |
| 1055 |
<<a href="http://www.ieee802.org/1/pages/802.1au.html">http://www.ieee802.org/1/pages/802.1au.html</a>>. |
| 1056 |
|
| 1057 |
|
| 1058 |
|
| 1059 |
|
| 1060 |
<span class="grey">Pan, et al. Experimental [Page 19]</span></pre> |
| 1061 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span> |
| 1062 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1063 |
|
| 1064 |
|
| 1065 |
[<a id="ref-RED">RED</a>] Floyd, S. and V. Jacobson, "Random Early Detection (RED) |
| 1066 |
Gateways for Congestion Avoidance", IEEE/ACM Transactions |
| 1067 |
on Networking, Volume 1, Issue 4, DOI 10.1109/90.251892, |
| 1068 |
August 1993. |
| 1069 |
|
| 1070 |
[<a id="ref-TCP-Models">TCP-Models</a>] |
| 1071 |
Misra, V., Gong, W., and D. Towsley, "Fluid-based analysis |
| 1072 |
of a network of AQM routers supporting TCP flows with an |
| 1073 |
application to RED", SIGCOMM 2000, Volume 30, Issue 4, |
| 1074 |
pp. 151-160, DOI 10.1145/347057.347421, October 2000. |
| 1075 |
|
| 1076 |
|
| 1077 |
|
| 1078 |
|
| 1079 |
|
| 1080 |
|
| 1081 |
|
| 1082 |
|
| 1083 |
|
| 1084 |
|
| 1085 |
|
| 1086 |
|
| 1087 |
|
| 1088 |
|
| 1089 |
|
| 1090 |
|
| 1091 |
|
| 1092 |
|
| 1093 |
|
| 1094 |
|
| 1095 |
|
| 1096 |
|
| 1097 |
|
| 1098 |
|
| 1099 |
|
| 1100 |
|
| 1101 |
|
| 1102 |
|
| 1103 |
|
| 1104 |
|
| 1105 |
|
| 1106 |
|
| 1107 |
|
| 1108 |
|
| 1109 |
|
| 1110 |
|
| 1111 |
|
| 1112 |
|
| 1113 |
|
| 1114 |
|
| 1115 |
|
| 1116 |
<span class="grey">Pan, et al. Experimental [Page 20]</span></pre> |
| 1117 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span> |
| 1118 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1119 |
|
| 1120 |
|
| 1121 |
<span class="h2"><a class="selflink" id="appendix-A" href="#appendix-A">Appendix A</a>. The Basic PIE Pseudocode</span> |
| 1122 |
|
| 1123 |
Configurable parameters: |
| 1124 |
- QDELAY_REF. AQM Latency Target (default: 15 milliseconds) |
| 1125 |
- MAX_BURST. AQM Max Burst Allowance (default: 150 milliseconds) |
| 1126 |
|
| 1127 |
Internal parameters: |
| 1128 |
- Weights in the drop probability calculation (1/s): |
| 1129 |
alpha (default: 1/8), beta (default: 1 + 1/4) |
| 1130 |
- T_UPDATE: a period to calculate drop probability |
| 1131 |
(default: 15 milliseconds) |
| 1132 |
|
| 1133 |
Table that stores status variables (ending with "_"): |
| 1134 |
- burst_allowance_: current burst allowance |
| 1135 |
- drop_prob_: The current packet drop probability. Reset to 0 |
| 1136 |
- qdelay_old_: The previous queue delay. Reset to 0 |
| 1137 |
|
| 1138 |
Public/system functions: |
| 1139 |
- queue_. Holds the pending packets |
| 1140 |
- drop(packet). Drops/discards a packet |
| 1141 |
- now(). Returns the current time |
| 1142 |
- random(). Returns a uniform r.v. in the range 0 ~ 1 |
| 1143 |
- queue_.byte_length(). Returns current queue_ length in bytes |
| 1144 |
- queue_.enque(packet). Adds packet to tail of queue_ |
| 1145 |
- queue_.deque(). Returns the packet from the head of queue_ |
| 1146 |
- packet.size(). Returns size of packet |
| 1147 |
- packet.timestamp_delay(). Returns timestamped packet latency |
| 1148 |
|
| 1149 |
============================ |
| 1150 |
|
| 1151 |
//Called on each packet arrival |
| 1152 |
enque(Packet packet) { |
| 1153 |
if (PIE->drop_prob_ == 0 && current_qdelay < QDELAY_REF/2 |
| 1154 |
&& PIE->qdelay_old_ < QDELAY_REF/2) { |
| 1155 |
PIE->burst_allowance_ = MAX_BURST; |
| 1156 |
} |
| 1157 |
if (PIE->burst_allowance_ == 0 && drop_early() == DROP) { |
| 1158 |
drop(packet); |
| 1159 |
} else { |
| 1160 |
queue_.enque(packet); |
| 1161 |
} |
| 1162 |
} |
| 1163 |
|
| 1164 |
============================ |
| 1165 |
|
| 1166 |
|
| 1167 |
|
| 1168 |
|
| 1169 |
|
| 1170 |
|
| 1171 |
|
| 1172 |
<span class="grey">Pan, et al. Experimental [Page 21]</span></pre> |
| 1173 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span> |
| 1174 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1175 |
|
| 1176 |
|
| 1177 |
drop_early() { |
| 1178 |
|
| 1179 |
//Safeguard PIE to be work conserving |
| 1180 |
if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2) |
| 1181 |
|| (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) { |
| 1182 |
return ENQUE; |
| 1183 |
} |
| 1184 |
|
| 1185 |
double u = random(); |
| 1186 |
if (u < PIE->drop_prob_) { |
| 1187 |
return DROP; |
| 1188 |
} else { |
| 1189 |
|
| 1190 |
return ENQUE; |
| 1191 |
} |
| 1192 |
} |
| 1193 |
|
| 1194 |
============================ |
| 1195 |
|
| 1196 |
//We choose the timestamp option of obtaining latency for clarity |
| 1197 |
//Rate estimation method can be found in the extended PIE pseudocode |
| 1198 |
|
| 1199 |
deque(Packet packet) { |
| 1200 |
|
| 1201 |
current_qdelay = packet.timestamp_delay(); |
| 1202 |
} |
| 1203 |
|
| 1204 |
============================ |
| 1205 |
|
| 1206 |
//Update periodically, T_UPDATE = 15 milliseconds |
| 1207 |
|
| 1208 |
calculate_drop_prob() { |
| 1209 |
|
| 1210 |
//Can be implemented using integer multiply |
| 1211 |
|
| 1212 |
p = alpha * (current_qdelay - QDELAY_REF) + \ |
| 1213 |
beta * (current_qdelay - PIE->qdelay_old_); |
| 1214 |
|
| 1215 |
if (PIE->drop_prob_ < 0.000001) { |
| 1216 |
p /= 2048; |
| 1217 |
} else if (PIE->drop_prob_ < 0.00001) { |
| 1218 |
p /= 512; |
| 1219 |
} else if (PIE->drop_prob_ < 0.0001) { |
| 1220 |
p /= 128; |
| 1221 |
} else if (PIE->drop_prob_ < 0.001) { |
| 1222 |
p /= 32; |
| 1223 |
} else if (PIE->drop_prob_ < 0.01) { |
| 1224 |
p /= 8; |
| 1225 |
|
| 1226 |
|
| 1227 |
|
| 1228 |
<span class="grey">Pan, et al. Experimental [Page 22]</span></pre> |
| 1229 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span> |
| 1230 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1231 |
|
| 1232 |
|
| 1233 |
} else if (PIE->drop_prob_ < 0.1) { |
| 1234 |
p /= 2; |
| 1235 |
} else { |
| 1236 |
p = p; |
| 1237 |
} |
| 1238 |
|
| 1239 |
PIE->drop_prob_ += p; |
| 1240 |
|
| 1241 |
//Exponentially decay drop prob when congestion goes away |
| 1242 |
if (current_qdelay == 0 && PIE->qdelay_old_ == 0) { |
| 1243 |
PIE->drop_prob_ *= 0.98; //1 - 1/64 is |
| 1244 |
//sufficient |
| 1245 |
} |
| 1246 |
|
| 1247 |
//Bound drop probability |
| 1248 |
if (PIE->drop_prob_ < 0) |
| 1249 |
PIE->drop_prob_ = 0.0 |
| 1250 |
if (PIE->drop_prob_ > 1) |
| 1251 |
PIE->drop_prob_ = 1.0 |
| 1252 |
|
| 1253 |
PIE->qdelay_old_ = current_qdelay; |
| 1254 |
|
| 1255 |
PIE->burst_allowance_ = |
| 1256 |
max(0,PIE->burst_allowance_ - T_UPDATE); |
| 1257 |
} |
| 1258 |
} |
| 1259 |
|
| 1260 |
|
| 1261 |
|
| 1262 |
|
| 1263 |
|
| 1264 |
|
| 1265 |
|
| 1266 |
|
| 1267 |
|
| 1268 |
|
| 1269 |
|
| 1270 |
|
| 1271 |
|
| 1272 |
|
| 1273 |
|
| 1274 |
|
| 1275 |
|
| 1276 |
|
| 1277 |
|
| 1278 |
|
| 1279 |
|
| 1280 |
|
| 1281 |
|
| 1282 |
|
| 1283 |
|
| 1284 |
<span class="grey">Pan, et al. Experimental [Page 23]</span></pre> |
| 1285 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span> |
| 1286 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1287 |
|
| 1288 |
|
| 1289 |
<span class="h2"><a class="selflink" id="appendix-B" href="#appendix-B">Appendix B</a>. Pseudocode for PIE with Optional Enhancement</span> |
| 1290 |
|
| 1291 |
Configurable parameters: |
| 1292 |
- QDELAY_REF. AQM Latency Target (default: 15 milliseconds) |
| 1293 |
- MAX_BURST. AQM Max Burst Allowance (default: 150 milliseconds) |
| 1294 |
- MAX_ECNTH. AQM Max ECN Marking Threshold (default: 10%) |
| 1295 |
|
| 1296 |
Internal parameters: |
| 1297 |
- Weights in the drop probability calculation (1/s): |
| 1298 |
alpha (default: 1/8), beta (default: 1 + 1/4) |
| 1299 |
- DQ_THRESHOLD: (in bytes, default: 2^14 (in a power of 2) ) |
| 1300 |
- T_UPDATE: a period to calculate drop probability |
| 1301 |
(default: 15 milliseconds) |
| 1302 |
- TAIL_DROP: the tail drop threshold (max allowed queue depth) |
| 1303 |
for the queue |
| 1304 |
|
| 1305 |
Table that stores status variables (ending with "_"): |
| 1306 |
- active_: INACTIVE/ACTIVE |
| 1307 |
- burst_allowance_: current burst allowance |
| 1308 |
- drop_prob_: The current packet drop probability. Reset to 0 |
| 1309 |
- accu_prob_: Accumulated drop probability. Reset to 0 |
| 1310 |
- qdelay_old_: The previous queue delay estimate. Reset to 0 |
| 1311 |
- last_timestamp_: Timestamp of previous status update |
| 1312 |
- dq_count_, measurement_start_, in_measurement_, avg_dq_time_. |
| 1313 |
Variables for measuring average dequeue rate |
| 1314 |
|
| 1315 |
Public/system functions: |
| 1316 |
- queue_. Holds the pending packets |
| 1317 |
- drop(packet). Drops/discards a packet |
| 1318 |
- mark(packet). Marks ECN for a packet |
| 1319 |
- now(). Returns the current time |
| 1320 |
- random(). Returns a uniform r.v. in the range 0 ~ 1 |
| 1321 |
- queue_.byte_length(). Returns current queue_ length in bytes |
| 1322 |
- queue_.enque(packet). Adds packet to tail of queue_ |
| 1323 |
- queue_.deque(). Returns the packet from the head of queue_ |
| 1324 |
- packet.size(). Returns size of packet |
| 1325 |
- packet.ecn(). Returns whether packet is ECN capable or not |
| 1326 |
|
| 1327 |
============================ |
| 1328 |
|
| 1329 |
|
| 1330 |
|
| 1331 |
|
| 1332 |
|
| 1333 |
|
| 1334 |
|
| 1335 |
|
| 1336 |
|
| 1337 |
|
| 1338 |
|
| 1339 |
|
| 1340 |
<span class="grey">Pan, et al. Experimental [Page 24]</span></pre> |
| 1341 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-25" ></span> |
| 1342 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1343 |
|
| 1344 |
|
| 1345 |
//Called on each packet arrival |
| 1346 |
enque(Packet packet) { |
| 1347 |
if (queue_.byte_length() + packet.size() > TAIL_DROP) { |
| 1348 |
drop(packet); |
| 1349 |
PIE->accu_prob_ = 0; |
| 1350 |
} else if (PIE->active_ == TRUE && drop_early() == DROP |
| 1351 |
&& PIE->burst_allowance_ == 0) { |
| 1352 |
if (PIE->drop_prob_ < MAX_ECNTH && packet.ecn() == |
| 1353 |
TRUE) |
| 1354 |
mark(packet); |
| 1355 |
else |
| 1356 |
drop(packet); |
| 1357 |
PIE->accu_prob_ = 0; |
| 1358 |
} else { |
| 1359 |
queue_.enque(packet); |
| 1360 |
} |
| 1361 |
|
| 1362 |
//If the queue is over a certain threshold, turn on PIE |
| 1363 |
if (PIE->active_ == INACTIVE |
| 1364 |
&& queue_.byte_length() >= TAIL_DROP/3) { |
| 1365 |
PIE->active_ = ACTIVE; |
| 1366 |
PIE->qdelay_old_ = 0; |
| 1367 |
PIE->drop_prob_ = 0; |
| 1368 |
PIE->in_measurement_ = TRUE; |
| 1369 |
PIE->dq_count_ = 0; |
| 1370 |
PIE->avg_dq_time_ = 0; |
| 1371 |
PIE->last_timestamp_ = now; |
| 1372 |
PIE->burst_allowance_ = MAX_BURST; |
| 1373 |
PIE->accu_prob_ = 0; |
| 1374 |
PIE->measurement_start_ = now; |
| 1375 |
} |
| 1376 |
|
| 1377 |
//If the queue has been idle for a while, turn off PIE |
| 1378 |
//Reset counters when accessing the queue after some idle |
| 1379 |
//period if PIE was active before |
| 1380 |
if ( PIE->drop_prob_ == 0 && PIE->qdelay_old_ == 0 |
| 1381 |
&& current_qdelay == 0) { |
| 1382 |
PIE->active_ = INACTIVE; |
| 1383 |
PIE->in_measurement_ = FALSE; |
| 1384 |
} |
| 1385 |
|
| 1386 |
} |
| 1387 |
|
| 1388 |
============================ |
| 1389 |
|
| 1390 |
|
| 1391 |
|
| 1392 |
|
| 1393 |
|
| 1394 |
|
| 1395 |
|
| 1396 |
<span class="grey">Pan, et al. Experimental [Page 25]</span></pre> |
| 1397 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-26" ></span> |
| 1398 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1399 |
|
| 1400 |
|
| 1401 |
drop_early() { |
| 1402 |
|
| 1403 |
//PIE is active but the queue is not congested: return ENQUE |
| 1404 |
if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2) |
| 1405 |
|| (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) { |
| 1406 |
return ENQUE; |
| 1407 |
} |
| 1408 |
|
| 1409 |
|
| 1410 |
if (PIE->drop_prob_ == 0) { |
| 1411 |
PIE->accu_prob_ = 0; |
| 1412 |
} |
| 1413 |
|
| 1414 |
//For practical reasons, drop probability can be further scaled |
| 1415 |
//according to packet size, but one needs to set a bound to |
| 1416 |
//avoid unnecessary bias |
| 1417 |
|
| 1418 |
//Random drop |
| 1419 |
PIE->accu_prob_ += PIE->drop_prob_; |
| 1420 |
if (PIE->accu_prob_ < 0.85) |
| 1421 |
return ENQUE; |
| 1422 |
if (PIE->accu_prob_ >= 8.5) |
| 1423 |
return DROP; |
| 1424 |
double u = random(); |
| 1425 |
if (u < PIE->drop_prob_) { |
| 1426 |
PIE->accu_prob_ = 0; |
| 1427 |
return DROP; |
| 1428 |
} else { |
| 1429 |
return ENQUE; |
| 1430 |
} |
| 1431 |
} |
| 1432 |
|
| 1433 |
============================ |
| 1434 |
|
| 1435 |
|
| 1436 |
|
| 1437 |
|
| 1438 |
|
| 1439 |
|
| 1440 |
|
| 1441 |
|
| 1442 |
|
| 1443 |
|
| 1444 |
|
| 1445 |
|
| 1446 |
|
| 1447 |
|
| 1448 |
|
| 1449 |
|
| 1450 |
|
| 1451 |
|
| 1452 |
<span class="grey">Pan, et al. Experimental [Page 26]</span></pre> |
| 1453 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-27" ></span> |
| 1454 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1455 |
|
| 1456 |
|
| 1457 |
//Update periodically, T_UPDATE = 15 milliseconds |
| 1458 |
calculate_drop_prob() { |
| 1459 |
if ( (now - PIE->last_timestamp_) >= T_UPDATE && |
| 1460 |
PIE->active_ == ACTIVE) { |
| 1461 |
|
| 1462 |
//Can be implemented using integer multiply |
| 1463 |
//DQ_THRESHOLD is power of 2 value |
| 1464 |
current_qdelay = queue_.byte_length() * |
| 1465 |
PIE->avg_dq_time_/DQ_THRESHOLD; |
| 1466 |
|
| 1467 |
p = alpha * (current_qdelay - QDELAY_REF) + \ |
| 1468 |
beta * (current_qdelay - PIE->qdelay_old_); |
| 1469 |
|
| 1470 |
if (PIE->drop_prob_ < 0.000001) { |
| 1471 |
p /= 2048; |
| 1472 |
} else if (PIE->drop_prob_ < 0.00001) { |
| 1473 |
p /= 512; |
| 1474 |
} else if (PIE->drop_prob_ < 0.0001) { |
| 1475 |
p /= 128; |
| 1476 |
} else if (PIE->drop_prob_ < 0.001) { |
| 1477 |
p /= 32; |
| 1478 |
} else if (PIE->drop_prob_ < 0.01) { |
| 1479 |
p /= 8; |
| 1480 |
} else if (PIE->drop_prob_ < 0.1) { |
| 1481 |
p /= 2; |
| 1482 |
} else { |
| 1483 |
p = p; |
| 1484 |
} |
| 1485 |
|
| 1486 |
if (PIE->drop_prob_ >= 0.1 && p > 0.02) { |
| 1487 |
p = 0.02; |
| 1488 |
} |
| 1489 |
PIE->drop_prob_ += p; |
| 1490 |
|
| 1491 |
//Exponentially decay drop prob when congestion goes away |
| 1492 |
if (current_qdelay < QDELAY_REF/2 && PIE->qdelay_old_ < |
| 1493 |
QDELAY_REF/2) { |
| 1494 |
PIE->drop_prob_ *= 0.98; //1 - 1/64 is |
| 1495 |
//sufficient |
| 1496 |
} |
| 1497 |
|
| 1498 |
|
| 1499 |
|
| 1500 |
|
| 1501 |
|
| 1502 |
|
| 1503 |
|
| 1504 |
|
| 1505 |
|
| 1506 |
|
| 1507 |
|
| 1508 |
<span class="grey">Pan, et al. Experimental [Page 27]</span></pre> |
| 1509 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-28" ></span> |
| 1510 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1511 |
|
| 1512 |
|
| 1513 |
//Bound drop probability |
| 1514 |
if (PIE->drop_prob_ < 0) |
| 1515 |
PIE->drop_prob_ = 0 |
| 1516 |
if (PIE->drop_prob_ > 1) |
| 1517 |
PIE->drop_prob_ = 1 |
| 1518 |
|
| 1519 |
PIE->qdelay_old_ = current_qdelay; |
| 1520 |
PIE->last_timestamp_ = now; |
| 1521 |
PIE->burst_allowance_ = max(0,PIE->burst_allowance_ - |
| 1522 |
T_UPDATE); |
| 1523 |
} |
| 1524 |
} |
| 1525 |
|
| 1526 |
============================ |
| 1527 |
|
| 1528 |
//Called on each packet departure |
| 1529 |
deque(Packet packet) { |
| 1530 |
|
| 1531 |
//Dequeue rate estimation |
| 1532 |
if (PIE->in_measurement_ == TRUE) { |
| 1533 |
PIE->dq_count_ = packet.size() + PIE->dq_count_; |
| 1534 |
//Start a new measurement cycle if we have enough packets |
| 1535 |
if ( PIE->dq_count_ >= DQ_THRESHOLD) { |
| 1536 |
dq_time = now - PIE->measurement_start_; |
| 1537 |
if (PIE->avg_dq_time_ == 0) { |
| 1538 |
PIE->avg_dq_time_ = dq_time; |
| 1539 |
} else { |
| 1540 |
weight = DQ_THRESHOLD/2^16 |
| 1541 |
PIE->avg_dq_time_ = dq_time * weight + |
| 1542 |
PIE->avg_dq_time_ * (1 - weight); |
| 1543 |
} |
| 1544 |
PIE->in_measurement_ = FALSE; |
| 1545 |
} |
| 1546 |
} |
| 1547 |
|
| 1548 |
//Start a measurement if we have enough data in the queue |
| 1549 |
if (queue_.byte_length() >= DQ_THRESHOLD && |
| 1550 |
PIE->in_measurement_ == FALSE) { |
| 1551 |
PIE->in_measurement_ = TRUE; |
| 1552 |
PIE->measurement_start_ = now; |
| 1553 |
PIE->dq_count_ = 0; |
| 1554 |
} |
| 1555 |
} |
| 1556 |
|
| 1557 |
|
| 1558 |
|
| 1559 |
|
| 1560 |
|
| 1561 |
|
| 1562 |
|
| 1563 |
|
| 1564 |
<span class="grey">Pan, et al. Experimental [Page 28]</span></pre> |
| 1565 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-29" ></span> |
| 1566 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1567 |
|
| 1568 |
|
| 1569 |
Contributors |
| 1570 |
|
| 1571 |
Bill Ver Steeg |
| 1572 |
Comcast Cable |
| 1573 |
Email: [email protected] |
| 1574 |
|
| 1575 |
Mythili Prabhu* |
| 1576 |
Akamai Technologies |
| 1577 |
3355 Scott Blvd. |
| 1578 |
Santa Clara, CA 95054 |
| 1579 |
United States of America |
| 1580 |
Email: [email protected] |
| 1581 |
|
| 1582 |
Chiara Piglione* |
| 1583 |
Broadcom Corporation |
| 1584 |
3151 Zanker Road |
| 1585 |
San Jose, CA 95134 |
| 1586 |
United States of America |
| 1587 |
Email: [email protected] |
| 1588 |
|
| 1589 |
Vijay Subramanian* |
| 1590 |
PLUMgrid, Inc. |
| 1591 |
350 Oakmead Parkway |
| 1592 |
Suite 250 |
| 1593 |
Sunnyvale, CA 94085 |
| 1594 |
United States of America |
| 1595 |
Email: [email protected] |
| 1596 |
* Formerly at Cisco Systems |
| 1597 |
|
| 1598 |
|
| 1599 |
|
| 1600 |
|
| 1601 |
|
| 1602 |
|
| 1603 |
|
| 1604 |
|
| 1605 |
|
| 1606 |
|
| 1607 |
|
| 1608 |
|
| 1609 |
|
| 1610 |
|
| 1611 |
|
| 1612 |
|
| 1613 |
|
| 1614 |
|
| 1615 |
|
| 1616 |
|
| 1617 |
|
| 1618 |
|
| 1619 |
|
| 1620 |
<span class="grey">Pan, et al. Experimental [Page 29]</span></pre> |
| 1621 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-30" ></span> |
| 1622 |
<span class="grey"><a href="./rfc8033">RFC 8033</a> PIE February 2017</span> |
| 1623 |
|
| 1624 |
|
| 1625 |
Authors' Addresses |
| 1626 |
|
| 1627 |
Rong Pan |
| 1628 |
Cisco Systems |
| 1629 |
3625 Cisco Way |
| 1630 |
San Jose, CA 95134 |
| 1631 |
United States of America |
| 1632 |
|
| 1633 |
Email: [email protected] |
| 1634 |
|
| 1635 |
|
| 1636 |
Preethi Natarajan |
| 1637 |
Cisco Systems |
| 1638 |
725 Alder Drive |
| 1639 |
Milpitas, CA 95035 |
| 1640 |
United States of America |
| 1641 |
|
| 1642 |
Email: [email protected] |
| 1643 |
|
| 1644 |
|
| 1645 |
Fred Baker |
| 1646 |
Santa Barbara, CA 93117 |
| 1647 |
United States of America |
| 1648 |
|
| 1649 |
Email: [email protected] |
| 1650 |
|
| 1651 |
|
| 1652 |
Greg White |
| 1653 |
CableLabs |
| 1654 |
858 Coal Creek Circle |
| 1655 |
Louisville, CO 80027 |
| 1656 |
United States of America |
| 1657 |
|
| 1658 |
Email: [email protected] |
| 1659 |
|
| 1660 |
|
| 1661 |
|
| 1662 |
|
| 1663 |
|
| 1664 |
|
| 1665 |
|
| 1666 |
|
| 1667 |
|
| 1668 |
|
| 1669 |
|
| 1670 |
|
| 1671 |
|
| 1672 |
|
| 1673 |
|
| 1674 |
|
| 1675 |
|
| 1676 |
Pan, et al. Experimental [Page 30] |
| 1677 |
</pre> |