Debian Codegraph @

rfc8033.html

raw
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&nbsp;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="&quot;Random Early Detection (RED) Gateways for Congestion Avoidance&quot;">RED</a>] as suggested in [<a href="./rfc2309" title="&quot;Recommendations on Queue Management and Congestion Avoidance in the Internet&quot;">RFC2309</a>] (which is now obsoleted by
172 [<a href="./rfc7567" title="&quot;IETF Recommendations Regarding Active Queue Management&quot;">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="&quot;Controlling Queue Delay&quot;">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="&quot;On Packet Switches With Infinite Storage&quot;">RFC970</a>]. CBQ has been a standard feature in most network
203 devices today [<a href="#ref-CBQ" title="&quot;Class-Based Weighted Fair Queueing&quot;">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="&quot;On Queuing, Marking, and Dropping&quot;">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="&quot;Active Queue Management (AQM) Based on Proportional Integral Controller Enhanced (PIE) for Data-Over-Cable Service Interface Specifications (DOCSIS) Cable Modems&quot;">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="&quot;Key words for use in RFCs to Indicate Requirement Levels&quot;">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="&quot;IETF Recommendations Regarding Active Queue Management&quot;">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-&gt;". For a full description of the
299 algorithm, one can refer to the full paper [<a href="#ref-HPSR-PIE" title="&quot;PIE: A lightweight control scheme to address the bufferbloat problem&quot;">HPSR-PIE</a>].
300
301 Random Drop
302 / --------------
303 -------/ --------------&gt; | | | | | --------------&gt;
304 /|\ | | | | |
305 | --------------
306 | Queue Buffer \
307 | | \
308 | |Queue \
309 | |Length \
310 | | \
311 | \|/ \/
312 | ----------------- -------------------
313 | | Drop | | |
314 -----&lt;-----| Probability |&lt;---| 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-&gt;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-&gt;drop_prob_.
347
348 To ensure that PIE is "work conserving", we bypass the random drop if
349 the latency sample, PIE-&gt;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-&gt;drop_prob_ &lt; 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-&gt;qdelay_old_ &lt; QDELAY_REF/2 &amp;&amp; PIE-&gt;drop_prob_ &lt; 0.2)
358 || (queue_.byte_length() &lt;= 2 * MEAN_PKTSIZE) )
359 return ENQUE;
360 else
361 randomly drop the packet with a probability of
362 PIE-&gt;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="&quot;On designing improved controllers for AQM routers supporting TCP flows&quot;">PI</a>] [<a href="#ref-QCN" title="&quot;IEEE Standard for Local and Metropolitan Area Networks--Virtual Bridged Local Area Networks - Amendment: 10: Congestion Notification&quot;">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-&gt;drop_prob_, and autotune it as
403 follows:
404
405 p = alpha * (current_qdelay - QDELAY_REF) +
406 beta * (current_qdelay - PIE-&gt;qdelay_old_);
407
408 if (PIE-&gt;drop_prob_ &lt; 0.000001) {
409 p /= 2048;
410 } else if (PIE-&gt;drop_prob_ &lt; 0.00001) {
411 p /= 512;
412 } else if (PIE-&gt;drop_prob_ &lt; 0.0001) {
413 p /= 128;
414 } else if (PIE-&gt;drop_prob_ &lt; 0.001) {
415 p /= 32;
416 } else if (PIE-&gt;drop_prob_ &lt; 0.01) {
417 p /= 8;
418 } else if (PIE-&gt;drop_prob_ &lt; 0.1) {
419 p /= 2;
420 } else {
421 p = p;
422 }
423 PIE-&gt;drop_prob_ += p;
424
425 * decay the drop probability exponentially:
426
427 if (current_qdelay == 0 &amp;&amp; PIE-&gt;qdelay_old_ == 0) {
428 PIE-&gt;drop_prob_ = PIE-&gt;drop_prob_ * 0.98;
429 //1 - 1/64 is
430 //sufficient
431 }
432
433 * bound the drop probability:
434
435 if (PIE-&gt;drop_prob_ &lt; 0)
436 PIE-&gt;drop_prob_ = 0.0
437 if (PIE-&gt;drop_prob_ &gt; 1)
438 PIE-&gt;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-&gt;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-&gt;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-&gt;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="&quot;PIE: A lightweight control scheme to address the bufferbloat problem&quot;">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="&quot;IETF Recommendations Regarding Active Queue Management&quot;">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-&gt;burst_allowance_ &gt; 0
525 enqueue packet;
526 else
527 randomly drop a packet with a probability of
528 PIE-&gt;drop_prob_.
529
530 if (PIE-&gt;drop_prob_ == 0 and current_qdelay &lt; QDELAY_REF/2 and
531 PIE-&gt;qdelay_old_ &lt; QDELAY_REF/2)
532 PIE-&gt;burst_allowance_ = MAX_BURST;
533
534 * In the "drop probability calculation" block, PIE additionally
535 calculates:
536
537 PIE-&gt;burst_allowance_ = max(0,PIE-&gt;burst_allowance_ - T_UPDATE);
538
539 The burst allowance, noted by PIE-&gt;burst_allowance_, is initialized
540 to MAX_BURST. As long as PIE-&gt;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-&gt;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-&gt;drop_prob_
545 equals 0 and both the current and previous samples of estimated
546 latency are less than half of QDELAY_REF -- PIE-&gt;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="&quot;Guidelines for Adding Congestion Notification to Protocols that Encapsulate IP&quot;">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-&gt;drop_prob_" function in the "random dropping" block is
578 changed to the following:
579
580 * Upon a packet enqueue:
581
582 if rand() &lt; PIE-&gt;drop_prob_:
583 if PIE-&gt;drop_prob_ &lt; mark_ecnth &amp;&amp; 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-&gt;avg_dq_time_/DQ_THRESHOLD;
623
624 * Upon a packet dequeue:
625
626 if PIE-&gt;in_measurement_ == FALSE and queue.byte_length() &gt;=
627 DQ_THRESHOLD:
628 PIE-&gt;in_measurement_ = TRUE;
629 PIE-&gt;measurement_start_ = now;
630 PIE-&gt;dq_count_ = 0;
631
632 if PIE-&gt;in_measurement_ == TRUE:
633 PIE-&gt;dq_count_ = PIE-&gt;dq_count_ + deque_pkt_size;
634 if PIE-&gt;dq_count_ &gt;= DQ_THRESHOLD then
635 weight = DQ_THRESHOLD/2^16
636 PIE-&gt;avg_dq_time_ = (now - PIE-&gt;measurement_start_) *
637 weight + PIE-&gt;avg_dq_time_ *
638 (1 - weight);
639 PIE-&gt;dq_count_ = 0;
640 PIE-&gt;measurement_start_ = now
641 else
642 PIE-&gt;in_measurement_ = FALSE;
643
644 The parameter PIE-&gt;dq_count_ represents the number of bytes departed
645 since the last measurement. Once PIE-&gt;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 (&lt; 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-&gt;avg_dq_time_. The dequeue rate is
653 simply DQ_THRESHOLD divided by PIE-&gt;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-&gt;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 -------/ --------------------&gt; | | | | | --------------&gt;
676 /|\ | | | | | |
677 | | --------------
678 | | Queue Buffer
679 | | |
680 | | |Queue
681 | | |Length
682 | | |
683 | \|/ \|/
684 | ------------------------------
685 | | Dequeue Rate |
686 -----&lt;-----| &amp; 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-&gt;active_ == FALSE &amp;&amp; queue_length &gt;= TAIL_DROP/3:
737 PIE-&gt;active_ = TRUE;
738 PIE-&gt;burst_allowance_ = MAX_BURST;
739
740 if PIE-&gt;burst_allowance_ &gt; 0
741 enqueue packet;
742 else
743 randomly drop a packet with a probability of
744 PIE-&gt;drop_prob_.
745
746 if (PIE-&gt;drop_prob_ == 0 and current_qdelay &lt; QDELAY_REF/2 and
747 PIE-&gt;qdelay_old_ &lt; QDELAY_REF/2)
748 PIE-&gt;active_ = FALSE;
749 PIE-&gt;burst_allowance_ = MAX_BURST;
750
751 * "Drop probability calculation" block: PIE does the following:
752 if PIE-&gt;active_ == TRUE:
753 PIE-&gt;burst_allowance_ =
754 max(0,PIE-&gt;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-&gt;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-&gt;accu_prob_" is reset to 0
767 after a drop. Upon packet arrival, PIE-&gt;accu_prob_ is incremented by
768 the amount of drop probability, PIE-&gt;drop_prob_. If PIE-&gt;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-&gt;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-&gt;accu_prob_ falls between the two thresholds. Since
774 PIE-&gt;accu_prob_ is reset to 0 after a drop, another drop will not
775 happen until 0.85/PIE-&gt;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-&gt;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="&quot;Active Queue Management (AQM) Based on Proportional Integral Controller Enhanced (PIE) for Data-Over-Cable Service Interface Specifications (DOCSIS) Cable Modems&quot;">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-&gt;drop_prob_ &gt;= 0.1 &amp;&amp; p &gt; 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-&gt;drop_prob_, and PIE-&gt;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 &lt;<a href="http://www.rfc-editor.org/info/rfc2119">http://www.rfc-editor.org/info/rfc2119</a>&gt;.
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 &lt;<a href="http://www.rfc-editor.org/info/rfc970">http://www.rfc-editor.org/info/rfc970</a>&gt;.
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 &lt;<a href="http://www.rfc-editor.org/info/rfc2309">http://www.rfc-editor.org/info/rfc2309</a>&gt;.
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 &lt;<a href="http://www.rfc-editor.org/info/rfc7567">http://www.rfc-editor.org/info/rfc7567</a>&gt;.
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 &lt;<a href="http://www.rfc-editor.org/info/rfc7806">http://www.rfc-editor.org/info/rfc7806</a>&gt;.
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, &lt;<a href="http://www.rfc-editor.org/info/rfc8034">http://www.rfc-editor.org/info/rfc8034</a>&gt;.
1014
1015 [<a id="ref-CBQ">CBQ</a>] Cisco, "Class-Based Weighted Fair Queueing",
1016 &lt;<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>&gt;.
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 &lt;<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>&gt;.
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, &lt;<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>&gt;.
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 &lt;<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>&gt;.
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 &lt;<a href="http://www.ieee802.org/1/pages/802.1au.html">http://www.ieee802.org/1/pages/802.1au.html</a>&gt;.
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-&gt;drop_prob_ == 0 &amp;&amp; current_qdelay &lt; QDELAY_REF/2
1154 &amp;&amp; PIE-&gt;qdelay_old_ &lt; QDELAY_REF/2) {
1155 PIE-&gt;burst_allowance_ = MAX_BURST;
1156 }
1157 if (PIE-&gt;burst_allowance_ == 0 &amp;&amp; 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-&gt;qdelay_old_ &lt; QDELAY_REF/2 &amp;&amp; PIE-&gt;drop_prob_ &lt; 0.2)
1181 || (queue_.byte_length() &lt;= 2 * MEAN_PKTSIZE) ) {
1182 return ENQUE;
1183 }
1184
1185 double u = random();
1186 if (u &lt; PIE-&gt;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-&gt;qdelay_old_);
1214
1215 if (PIE-&gt;drop_prob_ &lt; 0.000001) {
1216 p /= 2048;
1217 } else if (PIE-&gt;drop_prob_ &lt; 0.00001) {
1218 p /= 512;
1219 } else if (PIE-&gt;drop_prob_ &lt; 0.0001) {
1220 p /= 128;
1221 } else if (PIE-&gt;drop_prob_ &lt; 0.001) {
1222 p /= 32;
1223 } else if (PIE-&gt;drop_prob_ &lt; 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-&gt;drop_prob_ &lt; 0.1) {
1234 p /= 2;
1235 } else {
1236 p = p;
1237 }
1238
1239 PIE-&gt;drop_prob_ += p;
1240
1241 //Exponentially decay drop prob when congestion goes away
1242 if (current_qdelay == 0 &amp;&amp; PIE-&gt;qdelay_old_ == 0) {
1243 PIE-&gt;drop_prob_ *= 0.98; //1 - 1/64 is
1244 //sufficient
1245 }
1246
1247 //Bound drop probability
1248 if (PIE-&gt;drop_prob_ &lt; 0)
1249 PIE-&gt;drop_prob_ = 0.0
1250 if (PIE-&gt;drop_prob_ &gt; 1)
1251 PIE-&gt;drop_prob_ = 1.0
1252
1253 PIE-&gt;qdelay_old_ = current_qdelay;
1254
1255 PIE-&gt;burst_allowance_ =
1256 max(0,PIE-&gt;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() &gt; TAIL_DROP) {
1348 drop(packet);
1349 PIE-&gt;accu_prob_ = 0;
1350 } else if (PIE-&gt;active_ == TRUE &amp;&amp; drop_early() == DROP
1351 &amp;&amp; PIE-&gt;burst_allowance_ == 0) {
1352 if (PIE-&gt;drop_prob_ &lt; MAX_ECNTH &amp;&amp; packet.ecn() ==
1353 TRUE)
1354 mark(packet);
1355 else
1356 drop(packet);
1357 PIE-&gt;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-&gt;active_ == INACTIVE
1364 &amp;&amp; queue_.byte_length() &gt;= TAIL_DROP/3) {
1365 PIE-&gt;active_ = ACTIVE;
1366 PIE-&gt;qdelay_old_ = 0;
1367 PIE-&gt;drop_prob_ = 0;
1368 PIE-&gt;in_measurement_ = TRUE;
1369 PIE-&gt;dq_count_ = 0;
1370 PIE-&gt;avg_dq_time_ = 0;
1371 PIE-&gt;last_timestamp_ = now;
1372 PIE-&gt;burst_allowance_ = MAX_BURST;
1373 PIE-&gt;accu_prob_ = 0;
1374 PIE-&gt;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-&gt;drop_prob_ == 0 &amp;&amp; PIE-&gt;qdelay_old_ == 0
1381 &amp;&amp; current_qdelay == 0) {
1382 PIE-&gt;active_ = INACTIVE;
1383 PIE-&gt;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-&gt;qdelay_old_ &lt; QDELAY_REF/2 &amp;&amp; PIE-&gt;drop_prob_ &lt; 0.2)
1405 || (queue_.byte_length() &lt;= 2 * MEAN_PKTSIZE) ) {
1406 return ENQUE;
1407 }
1408
1409
1410 if (PIE-&gt;drop_prob_ == 0) {
1411 PIE-&gt;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-&gt;accu_prob_ += PIE-&gt;drop_prob_;
1420 if (PIE-&gt;accu_prob_ &lt; 0.85)
1421 return ENQUE;
1422 if (PIE-&gt;accu_prob_ &gt;= 8.5)
1423 return DROP;
1424 double u = random();
1425 if (u &lt; PIE-&gt;drop_prob_) {
1426 PIE-&gt;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-&gt;last_timestamp_) &gt;= T_UPDATE &amp;&amp;
1460 PIE-&gt;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-&gt;avg_dq_time_/DQ_THRESHOLD;
1466
1467 p = alpha * (current_qdelay - QDELAY_REF) + \
1468 beta * (current_qdelay - PIE-&gt;qdelay_old_);
1469
1470 if (PIE-&gt;drop_prob_ &lt; 0.000001) {
1471 p /= 2048;
1472 } else if (PIE-&gt;drop_prob_ &lt; 0.00001) {
1473 p /= 512;
1474 } else if (PIE-&gt;drop_prob_ &lt; 0.0001) {
1475 p /= 128;
1476 } else if (PIE-&gt;drop_prob_ &lt; 0.001) {
1477 p /= 32;
1478 } else if (PIE-&gt;drop_prob_ &lt; 0.01) {
1479 p /= 8;
1480 } else if (PIE-&gt;drop_prob_ &lt; 0.1) {
1481 p /= 2;
1482 } else {
1483 p = p;
1484 }
1485
1486 if (PIE-&gt;drop_prob_ &gt;= 0.1 &amp;&amp; p &gt; 0.02) {
1487 p = 0.02;
1488 }
1489 PIE-&gt;drop_prob_ += p;
1490
1491 //Exponentially decay drop prob when congestion goes away
1492 if (current_qdelay &lt; QDELAY_REF/2 &amp;&amp; PIE-&gt;qdelay_old_ &lt;
1493 QDELAY_REF/2) {
1494 PIE-&gt;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-&gt;drop_prob_ &lt; 0)
1515 PIE-&gt;drop_prob_ = 0
1516 if (PIE-&gt;drop_prob_ &gt; 1)
1517 PIE-&gt;drop_prob_ = 1
1518
1519 PIE-&gt;qdelay_old_ = current_qdelay;
1520 PIE-&gt;last_timestamp_ = now;
1521 PIE-&gt;burst_allowance_ = max(0,PIE-&gt;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-&gt;in_measurement_ == TRUE) {
1533 PIE-&gt;dq_count_ = packet.size() + PIE-&gt;dq_count_;
1534 //Start a new measurement cycle if we have enough packets
1535 if ( PIE-&gt;dq_count_ &gt;= DQ_THRESHOLD) {
1536 dq_time = now - PIE-&gt;measurement_start_;
1537 if (PIE-&gt;avg_dq_time_ == 0) {
1538 PIE-&gt;avg_dq_time_ = dq_time;
1539 } else {
1540 weight = DQ_THRESHOLD/2^16
1541 PIE-&gt;avg_dq_time_ = dq_time * weight +
1542 PIE-&gt;avg_dq_time_ * (1 - weight);
1543 }
1544 PIE-&gt;in_measurement_ = FALSE;
1545 }
1546 }
1547
1548 //Start a measurement if we have enough data in the queue
1549 if (queue_.byte_length() &gt;= DQ_THRESHOLD &amp;&amp;
1550 PIE-&gt;in_measurement_ == FALSE) {
1551 PIE-&gt;in_measurement_ = TRUE;
1552 PIE-&gt;measurement_start_ = now;
1553 PIE-&gt;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>