Greg,
Thanks for your feedback. Attached please see the revised draft. I answer your
comments below as well. I will hold for uploading it as a new draft for now,
hoping more comments will come in. Please feel free to let me know if you have
any further comments.
Regards,
Rong
From: Greg Skinner <[email protected]<mailto:[email protected]>>
Date: Tuesday, November 17, 2015 at 6:24 PM
To: Rong Pan <[email protected]<mailto:[email protected]>>
Cc: "[email protected]<mailto:[email protected]>" <[email protected]<mailto:[email protected]>>
Subject: Re: [aqm] draft-ietf-aqm-pie-02 review
Rong,
Thank you for uploading the new draft. I have some comments about it also.
I found the pseudocode for calculating the drop probability in section 4.2
confusing, in comparison with how it is presented in section 11. For example,
the drop probability is incremented prior to the auto-tuning steps in section
4.2, but it is incremented after the auto-tuning steps in section 11. Also,
there is a leftover assignment to p (the drop probability specified in -02),
that I assume should be corrected to drop_prob_ also. I think it would be less
confusing if these steps were summarized as bullet points in section 4.2, and
some text was added to refer the reader to section 11 for the (more detailed)
pseudocode.
>>>>>>>>>>>>>>>>>>>>>> “p" is a temporary variable, it eventually got assigned
>>>>>>>>>>>>>>>>>>>>>> to drop_prob_. I have made them consistent.
I also found some nits:
Section 4.2:
s/if the QDELAY_REF is changed from 15ms to 150us/if the QDELAY_REF is changed
from 15ms to 0.15 ms/
(if a 'µ' character cannot be placed in the draft, otherwise s/150us/150µs/)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: IMHO, “us” is understandable. I would like to
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>keep “us" as it is a common term for data center
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>folks.
Section 5:
s/For clarity purpose/For clarity purposes/
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
Section 5.2:
s/different modules that are independent to each other/different modules that
are independent of each other/
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
Section 5.5:
s/queue could quickly goes up during slow start and demands high drop
probability/the queue size could quickly increase during slow start, leading to
high drop probability/
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
Section 6:
s/their complexities are examined below/Their complexities are examined below/
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
Sections 11 and 12:
Where beta's value is given, using its fractional representation (5/4), or
adding a space in the expression for it (1 + 1/4) could improve readability.
You could also use decimal representations, as you did in section 6.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
General:
Using a consistent spelling (for example, either enque or enqueue) could
improve readability.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: changed the ones that I can find…
Regards,
Greg
On Nov 17, 2015, at 03:19 PM, "Rong Pan (ropan)"
<[email protected]<mailto:[email protected]>> wrote:
Polina,
A new version of PIE, draft-ietf-aqm-pie-03, is uploaded which addresses your
comments below. I also address your comments below.
Thanks,
Rong
From: aqm <[email protected]<mailto:[email protected]>> on behalf of
Polina Goltsman
<[email protected]<mailto:[email protected]>>
Date: Friday, August 14, 2015 at 5:25 AM
To: AQM IETF list <[email protected]<mailto:[email protected]>>
Subject: [aqm] draft-ietf-aqm-pie-02 review
Hello all,
Currently, I'm implementing various AQMs and one of them is PIE. However, one
problem is that the implementation is made difficult due to slight
inconsistencies between the draft section 4 and the pseudocode as well as it's
difficulty
to understand without the corresponding (theoretical) background knowledge.
Therefore, here are my suggestions for improvement from my review of the latest
draft version [thanks to Roland for helping with the suggestions and text]:
General feedback:
IHMO the current version of the draft, especially Section 4, is hard to
understand without reading the PIE paper ([HSPR-PIE]) first. Ideally I would
prefer an introduction section with the overview of the design before the
"Terminology" section, but it should at least be suggested to read the paper
first. BTW is the paper publicly available?
>>>>>>>>>>>>>>>RP: I have added more explanations before each of the sessions
>>>>>>>>>>>>>>>to make them more readable. I have also added a paper link to
>>>>>>>>>>>>>>>the HSPR-PIE paper in the draft.
In Section 4 there is a subsection per feature added, as opposed to a
subsection per component. As a result, requirements from the same component are
written in pieces in different subsections. For me it is very hard to combine
them together. One solution could be to include the pseudocode as last
subsection of Section 4. The same applies to Section 5.
>>>>>>>>>>>>>>>RP: some functions are implemented in multiple components. I
>>>>>>>>>>>>>>>have reorganized the sections. For each feature, I try to
>>>>>>>>>>>>>>>explain what components are involved.
The variables in formulas are not introduced before the formulas. I would
prefer to have a short description of what a formula does before the code and a
long description after the code.
>>>>>>>>>>>>>>>RP: I have added descriptions in each subsection explaining the
>>>>>>>>>>>>>>>intent of each components.
PIE is described as consisting of three components, however the "preambles" in
the formulas (the lines that start with stars) do not referred directly to the
components and the code for the same components are titled with different
star-lines: e.g., the specification of "random dropping at enqueue" component
appears under:
* upon a packet arrival MUST
* upon packet arrival
* if rand() < p
In the previous draft version there was only the link capacity estimation
version and there was no latency component, only the capacity estimation
component. In the current draft this is replaced with two options, which made
the whole draft very confusing. For instance, why is delay called est-delay if
it is either estimated or sampled? It is also not clear that estimated delay is
calculated in drop_probability_calculation. I would guess it after reading the
paper... IMO it would be better to describe the whole original version with
link capacity estimation and then suggest the alternatives: implementation with
timestamps or reading capacity from some other (external to PIE) system
component as in DOCSIS-PIE. Is it expected that most versions will use capacity
estimation?
>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: I have reworded the latency, not as
>>>>>>>>>>>>>>>>>>>>>>>>>>>estimated_delay, but as delay samples. Hopefully it
>>>>>>>>>>>>>>>>>>>>>>>>>>>is clear now.
There are SHOULD values for parameters of PIE, but it is never explained in
what range of conditions these parameters are [expected to be] valid. There are
slides for PIE in Data Centers here:
http://www.ietf.org/proceedings/86/slides/slides-86-iccrg-5.pdf. They use
different parameters for alpha, beta, and T_update. So I assume that the
parameters in the draft are not valid in these scenario. Also, since
target/reference delay is what a user probably wants to configure, should it be
SHOULD as opposed to RECOMMENDED. Finally, what minimum buffer size is required
for these values of target and burst-allow, so that PIE doesn't revert to
taildrop in the process?
Moreover, it is IMHO questionable whether implementers are familiar with the
control theory and can perform calculations based on the formulas in the paper.
Ideally, I would prefer a spreadsheet, where I can input visible network
parameters - e.g., link capacity, average or max RTT, max_available_buffer,
desired delay and get values for PIE variables.
>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: I have added rule of thumbs at the end of the
>>>>>>>>>>>>>>>>>>>>>>>>>>>Section 4.2. The idea is that the operators don’t
>>>>>>>>>>>>>>>>>>>>>>>>>>>need to change those parameters. There is no
>>>>>>>>>>>>>>>>>>>>>>>>>>>requirement of them learning the control theory. All
>>>>>>>>>>>>>>>>>>>>>>>>>>>those are internal parameters for PIE.
As a nit, IMHO delay should always be called delay and not sometimes delay and
sometimes latency.
>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: I have tried to change as much as possible.
per-Section feedback:
Sec4.2:
>in the formulas for autotune: if (drop_prob_ < X)
is p a value between 0 and 1 or between 0 and 100% ?
>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: 0 to 1.
Sec4.2:
>Here, the current queue length is denoted by qlen.
there is no qlen in the formulas
>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: removed.
Sec4.2:
> Variables, est_del and est_del_old represent the current and previous
> estimation of the queueing delay.
suggestion: which are calculate by the latency component (see Section 4.3)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: changed to current_qdelay and qdelay_old.
Sec4.2:
IMO the rationale for PI controller belongs to Design Goals in Section 3 and
not to algorithm specification. By this line, it should already be clear that
PI is used.
>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: PI is not the design goal of PIE. It is a
>>>>>>>>>>>>>>>>>>>>>>>>>>>mechanism that can achieve our goals. I moved the
>>>>>>>>>>>>>>>>>>>>>>>>>>>high level discussion about PI controller up to the
>>>>>>>>>>>>>>>>>>>>>>>>>>>beginning of Section 4.
Sec4.4:
>* if p == 0 and est_del < del_ref and est_del_old < del_ref
>burst_allowance = max_burst;
to what component does this formula belongs?
>>>>>>>>>>>>>>>>>>>>>>>>>>RP: initializing the burst allowance, it should be
>>>>>>>>>>>>>>>>>>>>>>>>>>in "Random Dropping” block.
Sec5.1
* if rand() < p
This is implementation consideration that belongs to Section 6, here should be
"upon packet arrival"
>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done
Sec5.2
see the comment to the PIE enhanced pseudocode, denoted as [**]. it affects
this line too.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: addressed below.
Sec5.3
Is the size of a buffer specified somewhere? It can be bufferbloated, so that
1/3buffer is more than reference delay and burst_allowance together.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: sizing the buffer is not the goal of PIE.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Also, micro burst over 1/3 buffer is not the
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>issue, and we don’t want to stop it from
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>happening. The goal is to avoid long term
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>persistent congestion that causes the delay bloat,
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>explained in Section 5.3.
Sec6
>If the implementation doesn’t rely on packet timestamps for calculating
>latency, PIE does not require extra memory.
extra operations?
I assume that Linux's Codel does not allocate extra space in skb for
timestamps, it is already there...
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: timestamp has to be stored
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>somewhere, all we claiming is that we
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>don’t need anything extra.
>The state requirement is only two variables per queue: est_del and
>est_del_old. Hence the memory overhead is small.
well the state is est_del_old, p, and burst_allow, and depending on the delay
calculation either est_delay or average drain rate and drained bytes for
measurement.
>PIE calculates latency using the departure rate, which can be implemented
>using a multiplication.
see the comment to the PIE enhanced pseudocode, denoted as [**]. it affects
this line too.
>In summary, PIE is simple to implement
given the current state of the draft I really doubt this ...
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: the statement is subjective. I removed
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>it and changed it to "PIE is simple enough
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>to be implemented in both hardware and
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>software". This is a fact.
>SFQ can be combined with PIE to provide further improvement of latency for
>various flows with different priorities.
There was a discussion started by me here
(http://www.ietf.org/mail-archive/web/aqm/current/msg01269.html) in which it
was concluded that for SFQ scheduler there is supposed to be a single PIE state
and drop probability of each queue is multiplied by its qlen/max qlen
(http://www.ietf.org/mail-archive/web/aqm/current/msg01363.html). Additionally,
it was stated that the same approach was taken for a scheduler with small
number of queues ( probably in this email
http://www.ietf.org/mail-archive/web/aqm/current/msg01358.html)
Since discussing the interaction of AQM with a scheduler is a requirement from
draft-aqm-eval-guidelines, this qlen/max_qlen recomendation should be summarized
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: Added a paragraph at the end of
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>Section 6 to discuss SFQ and PIE.
PIE BASIC pseudocode feedback:
>current_qdelay_, -qdelay_old_,
aren't they called est_delay and est_delay_old in Section 4. It would be good
to use consistent names
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
enqueue():
Burst allowance is reset in this routine. However in the next pseudocode it is
reset in calculate_drop_prob() which does make more sense to me.
>if (PIE->burst_allowance_ < 0 && drop_early() == DROP && PIE->burst_allowance_
><= 0) {
the burst_allowance condition is verified two times, with < and with <=
>if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 20%)
>|| (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) {
>return ENQUE;
>}
is this line explained in Section 4?
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: this is to make PIE work conserving, which is
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>not the key part of PIE.
calculate_drop_prob():
>//can be implemented using integer multiply,
>qdelay = PIE->current_qdelay_;
it probably can, but isn't simple assignment better :)
>PIE->last_timestamp_ = now;
I assume this line came from calling the timer function based on timestamps,
which is implementation decision and should not be present in pseudocode. Linux
e.g., calls calculate_drop_prob() by timer.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: pseudo code is simply showing how it can be
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>conceptually done, not trying to match Linux
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>code.
PIE enhanced pseudocode feedback:
enqueue:
>if (queue_.byte_length()+packet.size() > TAIL_DROP) {
>drop(packet);
this I assume is from Bob Briscoe's review
(http://www.ietf.org/mail-archive/web/aqm/current/msg01175.html), is it
explained somewhere in Section 5?
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: yes, but since it is regarding tail
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>dropping but PIE per se. We don’t want
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>to over explain everything in the pseudo
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>code.
calculate_drop_prob:
>if ( (now - PIE->last_timestampe_) >= T_UPDATE &&
>PIE->active_ == ACTIVE) {
1) it is not explained in Section 5 that when PIE is inactive, drop probability
is not recalculated. Also should it really not?
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: If PIE is not active, drop
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>probability calculation is ignored. We
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>don’t want to get into a situation
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>where as soon as PIE is back to be
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>active, packets would incur massive
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>drops.
2) now - timestamp is implementation choice and should not be here
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: it is meant to illustrate the
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>point, I.e. Pseudo code, not the real
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>code.
3) there is a typo in timestampe
>if (PIE->drop_prob_ >= 10% && p > 2%) {
>p = 0.02;
>}
>PIE->drop_prob_ += p;
it this line explained somewhere in Section 5? I believe this line was
commented in this email
(http://www.ietf.org/mail-archive/web/aqm/current/msg01216.html) and should
have appeared as MAY requirement.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: added a section Section 5.5.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>addressing this.
dequeue:
>weight = DQ_THRESHOLD/2^16
1) this is new and not explained in Section 5.2
2) since dq_thresh is in bytes, weight also has units - bytes. which makes
avg_dq_time in units bytes * sec or something unknown like (1 - bytes) * sec.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: weight does not have unit. Consider it
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>as weight = DQ_THRESHOLD/2^16Byte
in Linux code it is first checked whether a new measurement cycle can be
started, and then departed bytes are updated. With current version if there is
exactly dq_threshold bytes in queue and new packets will not come the code will
not count bytes in the first packet and the condition (queue_.byte_length() >=
DQ_THRESHOLD ) will not happen after new packets arrive.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> RP: Sorry, Linux code is not maintained
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> at this moment.
[**]
the PIE version in [HSPR-PIE] and Linux version calculate instantaneous
capacity (also called departure rate) as dq_count/dq_time. Then the average
capacity was calculated. The new code proposes to calculate instantaneous
dq_time and average dq_time and then calculate capacity as dq_thresh/dq_time in
calculate_drop_prob. Since the queue can send packets and not bytes, dq_count
is not dq_thresh and it may be well different and measured capacity not precise.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: Yes, it is not precise as you
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>mentioned. However, we tried to avoid a
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>non-trivial (from hardware point of view)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>divide by using DQ_THRESHOLD which can be
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>simply done using a right shift. Given that
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>our DQ_THRESHOLD is 2^16, one or two packet
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>can only affect the resolution around 1/64
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>=1.5%, which we believe is a good trade off.
I think it would be better to include the correct formulas, and then suggest a
less precise implementation, which requires less overhead in Section 6. In some
situations there can be enough hardware power so that the optimization is not
necessary (e.g., Linux on modern Desktops). Plus on 10Gb interface Linux sends
65K tso segments on 10Gb, I don't think I would want the value to be += one
segment precise.
PIE Linux Code:
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: the person who wrote the PIE Linux code
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>has left Cisco. We don’t support the
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>maintenance of Linux code at the moment.
This is code from
https://github.com/torvalds/linux/blob/master/net/sched/sch_pie.c
As far as I've checked, the code in
https://github.com/hironoriokano/fq-pie/blob/master/pie.h is the same.
enqueue:
line 125 - byte mode
byte mode is not explained anywhere in the draft
dequeue:
line 286:
do I understand correctly: old epsilon is 1/8 but new epsilon is threshold /
2^16 which is supposedly 16 * 2^10 / 2^16 = 2^-4.
line 300 updates burst-allow-= dtime:
according to the draft, burst-allow should be updated every Tupdate together
with drop probability and not on every measure ?
since there is no guarantee that measurement is always active these are two
different results. Is this code then wrong?
calculate_drop_prob:
line 378:
>if (qdelay > (PSCHED_NS2TICKS(250 * NSEC_PER_MSEC)))
>delta += MAX_PROB / (100 / 2);
this is not in the draft, is it ?
line 416 and below:
> /* We restart the measurement cycle if the following conditions are met ...
why do we need to restart measurement cycle? In my understanding the
measurement cycle is independent of p , and only update to burst-allow is
necessary.
Nits:
just before 4.
>In the following, the design of PIE and its operation are described in deta.
Detail
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
Sec4.1
>PIE optionally supports ECN and will be discussed in Section 5.1.
PIE optionally supports ECN. See Section 5.1.
or
PIE optionally supports ECN which will be discussed in Section 5.1.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
>It can b reduced
it can be reduced
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
Sec5.2
> This threshold would allow us a long enough period
us should not be there
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>RP: done.
Best Regards,
Polina
Internet Draft R. Pan, P. Natarajan, F. Baker
Active Queue Management G. White, B. VerSteeg, M.S. Prabhu
Working Group C. Piglione, V. Subramanian
Intended Status: Standards Track
Expires: May 20, 2016 November 17, 2015
PIE: A Lightweight Control Scheme To Address the
Bufferbloat Problem
draft-ietf-aqm-pie-03
Abstract
Bufferbloat is a phenomenon where excess buffers in the network cause
high latency and jitter. As more and more interactive applications
(e.g. voice over IP, real time video streaming and financial
transactions) run in the Internet, high latency and jitter degrade
application performance. There is a pressing need to design
intelligent queue management schemes that can control latency and
jitter; and hence provide desirable quality of service to users.
This document presents a lightweight active queue management design,
called PIE (Proportional Integral controller Enhanced), that can
effectively control the average queueing latency to a target value.
Simulation results, theoretical analysis and Linux testbed results
have shown that PIE can ensure low latency and achieve high link
utilization under various congestion situations. The design does not
require per-packet timestamp, so it incurs very small overhead and is
simple enough to implement in both hardware and software.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
Pan et al. Expires May 20, 2016 [Page 1]
INTERNET DRAFT PIE November 17, 2015
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Copyright and License Notice
Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. The Basic PIE Scheme . . . . . . . . . . . . . . . . . . . . . 6
4.1 Random Dropping(ECN Support is described later in this
document) . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Drop Probability Calculation . . . . . . . . . . . . . . . . 7
4.3 Latency Calculation . . . . . . . . . . . . . . . . . . . . 9
4.4 Burst Tolerance . . . . . . . . . . . . . . . . . . . . . . 9
5. Optional Design Elements of PIE . . . . . . . . . . . . . . . . 10
5.1 ECN Support . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 Departure Rate Estimation . . . . . . . . . . . . . . . . . 11
5.3 Turning PIE on and off . . . . . . . . . . . . . . . . . . . 12
5.4 De-randomization . . . . . . . . . . . . . . . . . . . . . . 13
5.5 Cap Drop Adjustment . . . . . . . . . . . . . . . . . . . . 14
6. Implementation Cost . . . . . . . . . . . . . . . . . . . . . . 14
7. Future Research . . . . . . . . . . . . . . . . . . . . . . . . 15
8. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 16
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 16
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.1 Normative References . . . . . . . . . . . . . . . . . . . 16
10.2 Informative References . . . . . . . . . . . . . . . . . . 16
Pan et al. Expires May 20, 2016 [Page 2]
INTERNET DRAFT PIE November 17, 2015
10.3 Other References . . . . . . . . . . . . . . . . . . . . . 16
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 17
11. The Basic PIE pseudo Code . . . . . . . . . . . . . . . . . . 18
12. Pseudo code for PIE with optional enhancement . . . . . . . . 21
Pan et al. Expires May 20, 2016 [Page 3]
INTERNET DRAFT PIE November 17, 2015
1. Introduction
The explosion of smart phones, tablets and video traffic in the
Internet brings about a unique set of challenges for congestion
control. To avoid packet drops, many service providers or data center
operators require vendors to put in as much buffer as possible. With
rapid decrease in memory chip prices, these requests are easily
accommodated to keep customers happy. While this solution succeeds in
assuring low packet loss and high TCP throughput, it suffers from a
major downside. The TCP protocol continuously increases its sending
rate and causes network buffers to fill up. TCP cuts its rate only
when it receives a packet drop or mark that is interpreted as a
congestion signal. However, drops and marks usually occur when
network buffers are full or almost full. As a result, excess buffers,
initially designed to avoid packet drops, would lead to highly
elevated queueing latency and jitter. It is a delicate balancing act
to design a queue management scheme that not only allows short-term
burst to smoothly pass, but also controls the average latency in the
presence of long-running greedy flows.
Active queue management (AQM) schemes, such as Random Early Discard
(RED), have been around for well over a decade. AQM schemes could
potentially solve the aforementioned problem. RFC 2309[RFC2309]
strongly recommends the adoption of AQM schemes in the network to
improve the performance of the Internet. RED is implemented in a wide
variety of network devices, both in hardware and software.
Unfortunately, due to the fact that RED needs careful tuning of its
parameters for various network conditions, most network operators
don't turn RED on. In addition, RED is designed to control the queue
length which would affect delay implicitly. It does not control
latency directly. Hence, the Internet today still lacks an effective
design that can control buffer latency to improve the quality of
experience to latency-sensitive applications. Notably, a recent IETF
AQM working group draft [IETF-AQM] calls for new methods of
controlling network latency.
New algorithms are beginning to emerge to control queueing latency
directly to address the bufferbloat problem [CoDel]. Along these
lines, PIE also aims to keep the benefits of RED: such as easy
implementation and scalability to high speeds. Similar to RED, PIE
randomly drops an incoming packet at the onset of the congestion. The
congestion detection, however, is based on the queueing latency
instead of the queue length like RED. Furthermore, PIE also uses the
derivative (rate of change) of the queueing latency to help determine
congestion levels and an appropriate response. The design parameters
of PIE are chosen via control theory stability analysis. While these
parameters can be fixed to work in various traffic conditions, they
could be made self-tuning to optimize system performance.
Pan et al. Expires May 20, 2016 [Page 4]
INTERNET DRAFT PIE November 17, 2015
Separately, it is assumed that any delay-based AQM scheme would be
applied over a Fair Queueing (FQ) structure or one of its approximate
designs, Flow Queueing or Class Based Queueing (CBQ). FQ is one of
the most studied scheduling algorithms since it was first proposed in
1985 [RFC970]. CBQ has been a standard feature in most network
devices today[CBQ]. Any AQM scheme that is built on top of FQ or CBQ
could benefit from these advantages. Furthermore, these advantages
such as per flow/class fairness are orthogonal to the AQM design
whose primary goal is to control latency for a given queue. For flows
that are classified into the same class and put into the same queue,
one needs to ensure their latency is better controlled and their
fairness is not worse than those under the standard DropTail or RED
design. More details about the relationship between FQ and AQM can be
found in IETF draft [FQ-Implement].
In October 2013, CableLabs' DOCSIS 3.1 specification [DOCSIS_3.1]
mandated that cable modems implement a specific variant of the PIE
design as the active queue management algorithm. In addition to cable
specific improvements, the PIE design in DOCSIS 3.1 [DOCSIS-PIE] has
improved the original design in several areas: de-randomization of
coin tosses, enhanced burst protection and expanded range of auto-
tuning.
This draft separates the PIE design into the basic elements that are
MUST to be implemented and optional SHOULD/MAY enhancement elements.
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
3. Design Goals
A queue management framework is designed to improve the performance
of interactive and delay-sensitive applications. It should follow the
general guidelines set by the AQM working group document "IETF
Recommendations Regarding Active Queue Management" [IETF-AQM]. More
specifically PIE design has the following basic criteria.
* First, queueing latency, instead of queue length, is
controlled. Queue sizes change with queue draining rates and
various flows' round trip times. Delay bloat is the real issue
that needs to be addressed as it impairs real time applications.
Pan et al. Expires May 20, 2016 [Page 5]
INTERNET DRAFT PIE November 17, 2015
If latency can be controlled, bufferbloat is not an issue. In
fact, once latency is under control it frees up buffers for
sporadic bursts.
* Secondly, PIE aims to attain high link utilization. The goal
of low latency shall be achieved without suffering link under-
utilization or losing network efficiency. An early congestion
signal could cause TCP to back off and avoid queue building up.
On the other hand, however, TCP's rate reduction could result in
link under-utilization. There is a delicate balance between
achieving high link utilization and low latency.
* Furthermore, the scheme should be simple to implement and
easily scalable in both hardware and software. PIE strives to
maintain similar design simplicity to RED, which has been
implemented in a wide variety of network devices.
* Finally, the scheme should ensure system stability for various
network topologies and scale well with arbitrary number streams.
Design parameters shall be set automatically. Users only need to
set performance-related parameters such as target queue delay,
not design parameters.
In the following, the design of PIE and its operation are described in
detail.
4. The Basic PIE Scheme
As illustrated in Fig. 1, PIE conceptually comprises three simple MUST
components: a) random dropping at enqueing; b) periodic drop probability
update; c) latency calculation. When a packet arrives, a random decision
is made regarding whether to drop the packet. The drop probability is
updated periodically and it is based on how far the current delay is
away from the target and whether the queueing delay is currently
trending up or down. The queueing delay can be obtained using direct
measurements or using estimations calculated from the queue length and
the deque rate.
The detailed definition of parameters can be found in the pseudo code
section of this document (Section 11). For full description of the
algorithm, one can refer to the full paper [HPSR-PIE].
Pan et al. Expires May 20, 2016 [Page 6]
INTERNET DRAFT PIE November 17, 2015
Random Drop
/ --------------
-------/ --------------> | | | | | -------------->
/|\ | | | | |
| --------------
| Queue Buffer \
| | \
| |queue \
| |length \
| | \
| \|/ \/
| ----------------- -------------------
| | Drop | | |
-----<-----| Probability |<---| Latency |
| Calculation | | Calculation |
----------------- -------------------
Figure 1. The PIE Structure
4.1 Random Dropping(ECN Support is described later in this document)
PIE MUST drop a packet upon its arrival to a queue according to a drop
probability, drop_prob_, that is obtained from the drop-probability-
calculation component. The random drop is triggered by a packet arrival
before enqueueing into a queue.
* Upon a packet enque, PIE MUST:
randomly drop the packet with a probability drop_prob_.
PIE optionally supports ECN and see Section 5.1.
4.2 Drop Probability Calculation
The PIE algorithm periodically updates the drop probability based on the
delay samples: not only the current delay sample but also the trend
where the delay is going, up or down. This is the classical Proportional
Integral (PI) controller method which is known for eliminating steady
state errors. This type of controller has been studied before for
controlling the queue length [PI, QCN]. PIE adopts the Proportional
Integral controller for controlling delay. The algorithm also auto-
adjusts the control parameters based on how heavy the congestion is,
which is reflected in the current drop probability.
Pan et al. Expires May 20, 2016 [Page 7]
INTERNET DRAFT PIE November 17, 2015
When a congestion period goes away, we might be left with a high drop
probability with light packet arrivals. Hence, the PIE algorithm MUST
include a mechanism by which the drop probability decay exponentially
(rather than linearly) when the system is not congested. This would help
the drop probability converge to 0. The decay parameter of 2% gives us
around 750ms time constant, a few RTT.
Specifically, the PIE algorithm MUST periodically adjust the drop
probability every T_UPDATE interval:
* MUST calculate drop probability drop_prob_ and auto-tune it as:
p = alpha*(current_qdelay-QDELAY_REF) +
beta*(current_qdelay-qdelay_old);
qdelay_old_ = current_qdelay_.
if (drop_prob_ < 0.000001) {
p /= 2048;
} else if (drop_prob_ < 0.00001) {
p /= 512;
} else if (drop_prob_ < 0.0001) {
p /= 128;
} else if (drop_prob_ < 0.001) {
p /= 32;
} else if (drop_prob_ < 0.01) {
p /= 8;
} else if (drop_prob_ < 0.1) {
p /= 2;
} else {
p = p;
}
drop_prob_ += p;
* MUST decay the drop probability exponentially:
if (current_qdelay_ == 0 && qdelay_old_ == 0) {
drop_prob_ = drop_prob_*0.98; //1- 1/64 is sufficient
}
The update interval, T_UPDATE, is defaulted to be 15ms. It MAY be
reduced on high speed links in order to provide smoother response. The
target delay value, QDELAY_REF, SHOULD be set to 15ms. Variables,
current_qdelay_ and qdelay_old_ represent the current and previous
samples of the queueing delay, which are calculated by the "Latency
Pan et al. Expires May 20, 2016 [Page 8]
INTERNET DRAFT PIE November 17, 2015
Calculation" component (see Section 4.3). The drop probability is a
value between 0 and 1. However, implementations can certainly use
integers.
As mentioned above, the adjustment to the drop probability is based not
only on the current estimation of the queueing delay, but also on the
rate of change of queueing delay. This rate of change is simply measured
as the difference between current_qdelay_ and qdelay_old_. They are used
together to control queueing latency so that, at the steady state, the
difference between the queueing latency and the target value is zero
even under heavy load. The controller parameters, in the unit of hz, are
designed using feedback loop analysis where TCP's behaviors are modeled
using the results from well-studied prior art[TCP-Models].
The theoretical analysis of PIE can be found in [HPSR-PIE]. As a rule of
thumb, if we cut T_UPDATE in half, we should also cut alpha by half and
increase beta by alpha/4 in order to keep the same feedback loop
dynamics. If PIE is to be used in data centers, the values of alpha and
beta SHOULD be increased by the same order of magnitude that the target
latency is reduced. For example, if the QDELAY_REF is changed from 15ms
to 150us, a reduction of two orders of magnitude, then alpha and beta
values should be increased to alpha*100 and beta*100.
4.3 Latency Calculation
The PIE algorithm MUST use latency to calculate drop probability.
* It MAY estimate current queueing delay using Little's law:
current_qdelay = qlen/dq_rate_;
Details can be found in Section 5.2.
* or MAY use other techniques for calculating queueing delay, ex:
timestamp packets at enqueue and use the same to calculate delay
during dequeue.
4.4 Burst Tolerance
PIE MUST also NOT penalize short-term packet bursts [IETF-AQM]. PIE MUST
give users precise control of how much burst to allow without penalty. A
parameter, MAX_BURST, is introduced that is similar to the burst
tolerance in the token bucket design. By default, the parameter SHOULD
be set to be 150ms (MUST be > 0).
Pan et al. Expires May 20, 2016 [Page 9]
INTERNET DRAFT PIE November 17, 2015
To implement this function, two basic components of PIE are involved:
"random dropping" and "drop probability calculation". The PIE algorithm
MUST do the following:
* In "Random Dropping" block and upon a packet arrival , PIE MUST
check:
Upon a packet enque:
if burst_allowance_ > 0 enqueue packet;
else randomly drop a packet with a probability drop_prob_.
if (drop_prob_ == 0 and current_qdelay_ < QDELAY_REF and
qdelay_old < QDELAY_REF)
burst_allowance_ = MAX_BURST;
* In "Drop Probability Calculation" block, PIE MUST additionally
calculate:
burst_allowance_ = burst_allowance_ - T_UPDATE;
The burst allowance, noted by burst_allowance_, is initialized to
MAX_BURST. As long as burst_allowance_ is above zero, an incoming packet
will be enqueued bypassing the random drop process. During each update
instance, the value of burst_allowance_ is decremented by the update
period, T_UPDATE. When the congestion goes away, defined here as
drop_prob_ equals to 0 and both the current and previous samples of
estimated delay are less than QDELAY_REF, burst_allowance_ is reset to
MAX_BURST.
5. Optional Design Elements of PIE
The above forms the basic MUST have elements of the PIE algorithm. There
are several enhancements that are added to further augment the
performance of the basic algorithm. For clarity purposes, they are
included in this section.
5.1 ECN Support
PIE SHOULD support ECN by marking (rather than dropping) ECN capable
packets. However, as a safeguard, an additional threshold, mark_ecnth,
is introduced. If the calculated drop probability exceeds mark_ecnth,
PIE MUST revert to packet drop for ECN capable packets. The variable
mark_ecnth SHOULD be set at 0.1(10%).
* To support ECN, the "random drop with a probability drop_prob_"
Pan et al. Expires May 20, 2016 [Page 10]
INTERNET DRAFT PIE November 17, 2015
function in "Random Dropping" block SHOULD be changed to the
following:
* Upon a packet enque:
if rand() < drop_prob_:
if drop_prob_ < mark_ecnth && ecn_capable_packet == TRUE:
mark packet;
else:
drop packet;
5.2 Departure Rate Estimation
One way to calculate latency is to obtain the departure rate. The
draining rate of a queue in the network often varies either because
other queues are sharing the same link, or the link capacity fluctuates.
Rate fluctuation is particularly common in wireless networks. One MAY
measure directly at the deque operation. Short, non-persistent bursts of
packets result in empty queues from time to time, this would make the
measurement less accurate. PIE SHOULD only measure the departure rate
when there are sufficient data in the buffer, i.e., when the queue
length is over a certain threshold. More specifically, PIE MAY implement
the rate estimation as follows:
* Upon a packet deque:
if in_measurement_ == FALSE and qlen > DQ_THRESHOLD:
in_measurement_ = TRUE;
measurement_start_ = now;
dq_count_ = 0;
if in_measurement_ == TRUE:
dq_count_ = dq_count_ + deque_pkt_size;
if dq_count_ > DQ_THRESHOLD then
dq_rate_ = dq_count/(now-start_);
dq_count=0;
start_ = now
The parameter, dq_count_, represents the number of bytes departed since
the last measurement. Once dq_count_ is over a certain threshold,
DQ_THRESHOLD, a measurement sample is obtained. The threshold is
recommended to be set to 16KB assuming a typical packet size of around
1KB or 1.5KB. This threshold would allow sufficient data to obtain an
Pan et al. Expires May 20, 2016 [Page 11]
INTERNET DRAFT PIE November 17, 2015
average draining rate but also fast enough to reflect sudden changes in
the draining rate. This threshold is not crucial for the system's
stability. Please note that the update interval for calculating the drop
probability is different from the rate measurement cycle. The drop
probability calculation is done periodically per section 4.2 and it is
done even when the algorithm is not in a measurement cycle; in this case
the previously latched value of depart_rate is used.
Random Drop
/ --------------
-------/ --------------------> | | | | | -------------->
/|\ | | | | | |
| | --------------
| | Queue Buffer
| | |
| | |queue
| | |length
| | |
| \|/ \|/
| ------------------------------
| | Departure Rate |
-----<-----| & Drop Probability |
| Calculation |
------------------------------
Figure 2. The Enque-based PIE Structure
In some platforms, enqueueing and dequeueing functions belong to
different modules that are independent of each other. In such
situations, a pure enque-based design MAY be designed. As shown in
Figure 2, an enque-based design is depicted. The departure rate is
deduced from the number of packets enqueued and the queue length. The
design is based on the following key observation: over a certain time
interval, the number of departure packets = the number of enqueued
packets - the number of remaining packets in queue. In this design,
everything can be triggered by a packet arrival including the background
update process. The design complexity here is similar to the original
design.
5.3 Turning PIE on and off
Pan et al. Expires May 20, 2016 [Page 12]
INTERNET DRAFT PIE November 17, 2015
Traffic naturally fluctuates in a network. It would be preferable not to
unnecessarily drop packets due to a spurious uptick in queueing latency.
PIE can be optionally turned on and off. IT SHOULD only be turned on
(from off) when the buffer occupancy is over a certain threshold, which
SHOULD be set to 1/3 of the tail drop threshold. If it is on, PIE SHOULD
be turned off when congestion is over, i.e. when the drop probability,
queue length and estimated queue delay all reach 0.
Ideally PIE should be turned on or off based on the latency. However,
calculating latency when PIE is off would introduce unnecessary packet
processing overhead. Weighing the trade-offs, it is decided to compare
against tail drop threshold to keep things simple.
When PIE is optionally turned on and off, the burst protection logic in
Section 4.4 MAY be modified as follows:
* "Random Dropping" block, PIE MAY add:
Upon packet arrival:
if PIE_active_ == FALSE && queue_length >= TAIL_DROP/3:
PIE_active_ = TRUE;
burst_allowance = MAX_BURST;
if burst_allowance_ > 0 enqueue packet;
else randomly drop a packet with a probability drop_prob_.
if (drop_prob_ == 0 and current_qdelay_ < QDELAY_REF and
qdelay_old < QDELAY_REF)
PIE_active_ = FALSE;
burst_allowance_ = MAX_BURST;
* "Drop Probability Calculation" block, PIE MAY do the following:
if PIE_active == TRUE:
burst_allowance = burst_allowance - T_UPDATE;
5.4 De-randomization
Although PIE adopts random dropping to achieve latency control,
independent coin tosses could introduce outlier situations where packets
are dropped too close to each other or too far from each other. This
would cause real drop percentage to temporarily deviate from the
intended drop probability p. In certain scenarios, such as small number
of simultaneous TCP flows, these deviations can cause significant
deviations in link utilization and queueing latency. PIE MAY introduce a
de-randomization mechanism to avoid such scenarios. A parameter, called
accu_prob, is reset to 0 after a drop. Upon a packet arrival, accu_prob
Pan et al. Expires May 20, 2016 [Page 13]
INTERNET DRAFT PIE November 17, 2015
is incremented by the amount of drop probability, p. If accu_prob is
less than a low threshold, e.g. 0.85, the arriving packet is enqued; on
the other hand, if accu_prob is more than a high threshold, e.g. 8.5, a
packet is forced to be dropped. A packet is only randomly dropped if
accu_prob falls in between the two thresholds. Since accu_prob is reset
to 0 after a drop, another drop will not happen until 0.85/p packets
later. This avoids packets being dropped too close to each other. In the
other extreme case where 8.5/p packets have been enqued without
incurring a drop, PIE would force a drop that prevents much fewer drops
than desired. Further analysis can be found in [DOCSIS-PIE].
5.5 Cap Drop Adjustment
In the case of one single TCP flow during slow start phase in the
system, queue could quickly increase during slow start and demands high
drop probability. In some environments such as Cable Modem Speed Test,
one could not afford triggering timeout and lose throughput as
throughput is shown to customers who are testing his/her connection
speed. We MAY cap the maximum drop probability increase in each step.
* "Drop Probability Calculation" block, PIE MAY add:
if (PIE->drop_prob_ >= 0.1 && p > 0.02) {
p = 0.02;
}
6. Implementation Cost
PIE can be applied to existing hardware or software solutions. There are
three steps involved in PIE as discussed in Section 4. Their
complexities are examined below.
Upon packet arrival, the algorithm simply drops a packet randomly based
on the drop probability p. This step is straightforward and requires no
packet header examination and manipulation. If the implementation
doesn't rely on packet timestamps for calculating latency, PIE does not
require extra memory. Furthermore, the input side of a queue is
typically under software control while the output side of a queue is
hardware based. Hence, a drop at enqueueing can be readily retrofitted
into existing hardware or software implementations.
The drop probability calculation is done in the background and it occurs
every T_UPDATE interval. Given modern high speed links, this period
translates into once every tens, hundreds or even thousands of packets.
Hence the calculation occurs at a much slower time scale than packet
processing time, at least an order of magnitude slower. The calculation
Pan et al. Expires May 20, 2016 [Page 14]
INTERNET DRAFT PIE November 17, 2015
of drop probability involves multiplications using alpha and beta. Since
PIE's control law is robust to minor changes in alpha and beta values,
an implementation MAY choose these values to the closest multiples of 2
or 1/2 (ex: alpha=1/8, beta=1 + 1/4) such that the multiplications can
be done using simple adds and shifts. As no complicated functions are
required, PIE can be easily implemented in both hardware and software.
The state requirement is only two variables per queue: current_qdelay_
and qdelay_old_. Hence the memory overhead is small.
If one chooses to implement the departure rate estimation, PIE uses a
counter to keep track of the number of bytes departed for the current
interval. This counter is incremented per packet departure. Every
T_UPDATE, PIE calculates latency using the departure rate, which can be
implemented using a multiplication. Note that many network devices keep
track of an interface's departure rate. In this case, PIE might be able
to reuse this information, simply skip the third step of the algorithm
and hence incurs no extra cost. If platform already leverages packet
timestamps for other purposes, PIE MAY make use of these packet
timestamps for latency calculation instead of estimating departure rate.
Since the PIE design is separated into data path and control path, if
control path is implemented in software, any further improvement in
control path can be easily accommodated.
SFQ can also be combined with PIE to further improve latency for various
flows with different priorities. If the timestamp is used to obtain
queueing latency, PIE can be adopted directly to each individual queue.
If the latency is obtained via the deque rate calculation, we recommend
one PIE instance using the overall queue length divided by the overall
deque rate. Then the overall drop_prob_ is modified using each
individual queue divided by the maximum individual queue length:
drop_prob_(i)=qlen(i)/max_qlen.
In summary, PIE is simple enough to be implemented in both software and
hardware.
7. Future Research
The design of the PIE algorithm is presented in this document. It
effectively controls the average queueing latency to a target value. The
following areas can be further studied:
* Autotuning of target delay without losing utilization;
* Autotuning for average RTT of traffic;
Pan et al. Expires May 20, 2016 [Page 15]
INTERNET DRAFT PIE November 17, 2015
8. Incremental Deployment
PIE scheme can be independently deployed and managed without any
need for interoperability.
Although all network nodes cannot be changed altogether to adopt
latency-based AQM schemes, a gradual adoption would eventually lead
to end-to-end low latency service for all applications.
9. IANA Considerations
There are no actions for IANA.
10. References
10.1 Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
10.2 Informative References
[RFC970] Nagle, J., "On Packet Switches With Infinite
Storage",RFC970, December 1985.
10.3 Other References
[IETF-AQM] Baker, F. and Fairhurst, G., "IETF Recommendations
Regarding Active Queue Management", draft-ietf-aqm-recommendation-11.
[CoDel] Nichols, K., Jacobson, V., "Controlling Queue Delay",
ACM Queue. ACM Publishing. doi:10.1145/2209249.22W.09264.
[CBQ] Cisco White Paper,
"http://www.cisco.com/en/US/docs/12_0t/12_0tfeature/guide/cbwfq.html";.
[FQ-Implement] Baker, F. and Pan, R. "On Queueing, Marking and
Dropping", IETF draft-ietf-aqm-fq-implementation.
[DOCSIS_3.1] http://www.cablelabs.com/wp-content/uploads/specdocs
/CM-SP-MULPIv3.1-I01-131029.pdf.
Pan et al. Expires May 20, 2016 [Page 16]
INTERNET DRAFT PIE November 17, 2015
[DOCSIS-PIE] White, G. and Pan, R., "A PIE-Based AQM for DOCSIS
Cable Modems", IETF draft-white-aqm-docsis-pie-00.
[HPSR-PIE] Pan, R., Natarajan, P. Piglione, C., Prabhu, M.S.,
Subramanian, V., Baker, F. Steeg and B. V., "PIE: A Lightweight
Control Scheme to Address the Bufferbloat Problem", IEEE HPSR 2013.
https://www.researchgate.net/publication/261134127_PIE_A_lightweight
_control_scheme_to_address_the_bufferbloat_problem?origin=mail
[AQM DOCSIS] http://www.cablelabs.com/wp-
content/uploads/2014/06/DOCSIS-AQM_May2014.pdf
[TCP-Models] Misra, V., Gong, W., and Towsley, D., "Fluid-base
Analysis of a Network of AQM Routers Supporting TCP Flows with an
Application to RED", SIGCOMM 2000
[PI] Hollot, C.V., Misra, V., Towsley, D. and Gong, W., "On
Designing Improved Controller for AQM Routers Supporting TCP Flows",
Infocom 2001.
[QCN] "Data Center Bridging - Congestion Notification",
http://www.ieee802.org/1/pages/802.1au.html.
Authors' Addresses
Rong Pan
Cisco Systems
3625 Cisco Way,
San Jose, CA 95134, USA
Email: [email protected]
Preethi Natarajan,
Cisco Systems
725 Alder Drive,
Milpitas, CA 95035, USA
Email: [email protected]
Fred Baker
Cisco Systems
725 Alder Drive,
Milpitas, CA 95035, USA
Email: [email protected]
Bill Ver Steeg
Cisco Systems
5030 Sugarloaf Parkway
Pan et al. Expires May 20, 2016 [Page 17]
INTERNET DRAFT PIE November 17, 2015
Lawrenceville, GA, 30044, USA
Email: [email protected]
Mythili Prabhu*
Akamai Technologies
3355 Scott Blvd
Santa Clara, CA - 95054
Email: [email protected]
Chiara Piglione*
Broadcom Corporation
3151 Zanker Road
San Jose, CA 95134
Email: [email protected]
Vijay Subramanian*
PLUMgrid, Inc.
350 Oakmead Parkway,
Suite 250
Sunnyvale, CA 94085
Email: [email protected]
Greg White
CableLabs
858 Coal Creek Circle
Louisville, CO 80027, USA
Email: [email protected]
* Formerly at Cisco Systems
11. The Basic PIE pseudo Code
Configurable Parameters:
- QDELAY_REF. AQM Latency Target (default: 16ms)
- MAX_BURST. AQM Max Burst Allowance (default: 150ms)
Internal Parameters:
- Weights in the drop probability calculation (1/s):
alpha (default: 1/8), beta(default: 1 + 1/4)
- T_UPDATE: a period to calculate drop probability (default:16ms)
Table which stores status variables (ending with "_"):
- burst_allowance_: current burst_allowance
- drop_prob_: The current packet drop probability. reset to 0
- current_qdelay_: The current queue delay. reset to 0
- qdelay_old_: The previous queue delay. reset to 0
Pan et al. Expires May 20, 2016 [Page 18]
INTERNET DRAFT PIE November 17, 2015
Public/system functions:
- queue_. Holds the pending packets.
- drop(packet). Drops/discards a packet
- now(). Returns the current time
- random(). Returns a uniform r.v. in the range 0 ~ 1
- queue_.byte_length(). Returns current queue_ length in bytes
- queue_.enque(packet). Adds packet to tail of queue_
- queue_.deque(). Returns the packet from the head of queue_
- packet.size(). Returns size of packet
- packet.timestamp_delay(). Returns timestamped packet latency
============================
//called on each packet arrival
enque(Packet packet) {
if (PIE->drop_prob_ == 0 && PIE->current_qdelay_ < del_ref
&& PIE->qdelay_old < del_ref) {
burst_allowance = MAX_BURST;
}
if (PIE->burst_allowance_ < 0 && drop_early() == DROP
&& PIE->burst_allowance_ <= 0) {
drop(packet);
} else {
queue_.enque(packet);
}
}
===========================
drop_early() {
//Safeguard PIE to be work conserving
if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2)
|| (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) {
return ENQUE;
}
double u = random();
if (u < PIE->drop_prob_) {
return DROP;
} else {
return ENQUE;
}
}
Pan et al. Expires May 20, 2016 [Page 19]
INTERNET DRAFT PIE November 17, 2015
===========================
//we choose the timestamp option of obtaining latency for clarity
//rate estimation method can be found in the extended PIE pseudo code
deque(Packet packet) {
PIE->current_qdelay_ = packet.timestamp_delay();
}
============================
//update periodically, T_UPDATE = 16ms
calculate_drop_prob() {
//can be implemented using integer multiply,
qdelay = PIE->current_qdelay_;
p = alpha*(qdelay - QDELAY_REF) + \
beta*(qdelay-PIE->qdelay_old_);
if (drop_prob_ < 0.000001) {
p /= 2048;
} else if (drop_prob_ < 0.00001) {
p /= 512;
} else if (drop_prob_ < 0.0001) {
p /= 128;
} else if (drop_prob_ < 0.001) {
p /= 32;
} else if (drop_prob_ < 0.01) {
p /= 8;
} else if (drop_prob_ < 0.1) {
p /= 2;
} else {
p = p;
}
PIE->drop_prob_ += p;
//Exponentially decay drop prob when congestion goes away
if (qdelay == 0 && PIE->qdelay_old_ == 0) {
PIE->drop_prob_ *= 0.98; //1- 1/64 is sufficient
}
//bound drop probability
if (PIE->drop_prob_ < 0)
PIE->drop_prob_ = 0
Pan et al. Expires May 20, 2016 [Page 20]
INTERNET DRAFT PIE November 17, 2015
if (PIE->drop_prob_ > 1)
PIE->drop_prob_ = 1
PIE->qdelay_old_ = qdelay;
PIE->last_timestamp_ = now;
if (PIE->burst_allowance_ > 0) {
PIE->burst_allowance_ = PIE->burst_allowance_ - T_UPDATE;
}
}
}
12. Pseudo code for PIE with optional enhancement
Configurable Parameters:
- QDELAY_REF. AQM Latency Target (default: 16ms)
- MAX_BURST. AQM Max Burst Allowance (default: 150ms)
- MAX_ECNTH. AQM Max ECN Marking Threshold (default: 10%)
Internal Parameters:
- Weights in the drop probability calculation (1/s):
alpha (default: 1/8), beta(default: 1+1/4)
- DQ_THRESHOLD: (in bytes, default: 2^14 (in a power of 2) )
- T_UPDATE: a period to calculate drop probability (default:16ms)
- TAIL_DROP: each queue has a tail drop threshold, pass it to PIE
Table which stores status variables (ending with "_"):
- active_: INACTIVE/ACTIVE
- burst_allowance_: current burst_allowance
- drop_prob_: The current packet drop probability. reset to 0
- accu_prob_: Accumulated drop probability. reset to 0
- qdelay_old_: The previous queue delay estimate. reset to 0
- last_timestamp_: Timestamp of previous status update
- dq_count_, measurement_start_, in_measurement_,
avg_dq_time_. variables for measuring avg_dq_rate_.
Public/system functions:
- queue_. Holds the pending packets.
- drop(packet). Drops/discards a packet
- mark(packet). Marks ECN for a packet
- now(). Returns the current time
- random(). Returns a uniform r.v. in the range 0 ~ 1
- queue_.byte_length(). Returns current queue_ length in bytes
- queue_.enque(packet). Adds packet to tail of queue_
Pan et al. Expires May 20, 2016 [Page 21]
INTERNET DRAFT PIE November 17, 2015
- queue_.deque(). Returns the packet from the head of queue_
- packet.size(). Returns size of packet
- packet.ecn(). Returns whether packet is ECN capable or not
============================
//called on each packet arrival
enque(Packet packet) {
if (queue_.byte_length()+packet.size() > TAIL_DROP) {
drop(packet);
PIE->accu_prob_ = 0;
} else if (PIE->active_ == TRUE && drop_early() == DROP
&& PIE->burst_allowance_ <= 0) {
if (PIE->drop_prob_ < MAX_ECNTH && packet.ecn() == TRUE)
mark(packet);
else
drop(packet);
PIE->accu_prob_ = 0;
} else {
queue_.enque(packet);
}
//If the queue is over a certain threshold, turn on PIE
if (PIE->active_ == INACTIVE
&& queue_.byte_length() >= TAIL_DROP/3) {
PIE->active_ = ACTIVE;
PIE->qdelay_old_ = 0;
PIE->drop_prob_ = 0;
PIE->in_measurement_ = TRUE;
PIE->dq_count_ = 0;
PIE->avg_dq_time_ = 0;
PIE->last_timestamp_ = now;
PIE->burst_allowance_ = MAX_BURST;
PIE->accu_prob_ = 0;
PIE->measurement_start_ = now;
}
//If the queue has been idle for a while, turn off PIE
//reset counters when accessing the queue after some idle
//period if PIE was active before
if ( PIE->drop_prob_ == 0 && PIE->qdelay_old_ == 0
&& queue_.byte_length() == 0) {
PIE->active_ = INACTIVE;
PIE->in_measurement_ = FALSE;
}
}
Pan et al. Expires May 20, 2016 [Page 22]
INTERNET DRAFT PIE November 17, 2015
===========================
drop_early() {
//PIE is active but the queue is not congested, return ENQUE
if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2)
|| (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) {
return ENQUE;
}
if (PIE->drop_prob_ == 0) {
PIE->accu_prob_ = 0;
}
//For practical reasons, drop probability can be further scaled
//according to packet size. but need to set a bound to
//avoid unnecessary bias
//Random drop
PIE->accu_prob_ += PIE->drop_prob_;
if (PIE->accu_prob_ < 0.85)
return ENQUE;
if (PIE->accu_prob_ >= 8.5)
return DROP;
double u = random();
if (u < PIE->drop_prob_) {
PIE->accu_prob_ = 0;
return DROP;
} else {
return ENQUE;
}
}
============================
//update periodically, T_UPDATE = 15ms
calculate_drop_prob() {
if ( (now - PIE->last_timestampe_) >= T_UPDATE &&
PIE->active_ == ACTIVE) {
//can be implemented using integer multiply,
//DQ_THRESHOLD is power of 2 value
qdelay = queue_.byte_length() * avg_dq_time_/DQ_THRESHOLD;
Pan et al. Expires May 20, 2016 [Page 23]
INTERNET DRAFT PIE November 17, 2015
p = alpha*(qdelay - QDELAY_REF) + \
beta*(qdelay-PIE->qdelay_old_);
if (drop_prob_ < 0.000001) {
p /= 2048;
} else if (drop_prob_ < 0.00001) {
p /= 512;
} else if (drop_prob_ < 0.0001) {
p /= 128;
} else if (drop_prob_ < 0.001) {
p /= 32;
} else if (drop_prob_ < 0.01) {
p /= 8;
} else if (drop_prob_ < 0.1) {
p /= 2;
} else {
p = p;
}
if (PIE->drop_prob_ >= 0.1 && p > 0.02) {
p = 0.02;
}
PIE->drop_prob_ += p;
//Exponentially decay drop prob when congestion goes away
if (qdelay == 0 && PIE->qdelay_old_ == 0) {
PIE->drop_prob_ *= 0.98; //1- 1/64 is sufficient
}
//bound drop probability
if (PIE->drop_prob_ < 0)
PIE->drop_prob_ = 0
if (PIE->drop_prob_ > 1)
PIE->drop_prob_ = 1
PIE->qdelay_old_ = qdelay;
PIE->last_timestampe_ = now;
if (PIE->burst_allowance_ > 0) {
PIE->burst_allowance_ = PIE->burst_allowance_ - T_UPDATE;
}
}
}
==========================
//called on each packet departure
deque(Packet packet) {
Pan et al. Expires May 20, 2016 [Page 24]
INTERNET DRAFT PIE November 17, 2015
//deque rate estimation
if (PIE->in_measurement_ == TRUE) {
PIE->dq_count_ = packet.size() + PIE->dq_count_;
//start a new measurement cycle if we have enough packets
if ( PIE->dq_count_ >= DQ_THRESHOLD) {
dq_time = now - PIE->measurement_start_;
if(PIE->avg_dq_time_ == 0) {
PIE->avg_dq_time_ = dq_time;
} else {
weight = DQ_THRESHOLD/2^16
PIE->avg_dq_time_ = dq_time*weight + PIE->avg_dq_time*(1-
weight);
}
PIE->in_measurement = FALSE;
}
}
//start a measurement if we have enough data in the queue:
if (queue_.byte_length() >= DQ_THRESHOLD &&
PIE->in_measurement_ == FALSE) {
PIE->in_measurement_ = TRUE;
PIE->measurement_start_ = now;
PIE->dq_count_ = 0;
}
}
Pan et al. Expires May 20, 2016 [Page 25]
_______________________________________________
aqm mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/aqm
