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?
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.
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.
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?
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.
As a nit, IMHO delay should always be called delay and not sometimes
delay and sometimes latency.
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% ?
Sec4.2:
>Here, the current queue length is denoted by qlen.
there is no qlen in the formulas
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)
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.
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?
Sec5.1
* if rand() < p
This is implementation consideration that belongs to Section 6, here
should be "upon packet arrival"
Sec5.2
see the comment to the PIE enhanced pseudocode, denoted as [**]. it
affects this line too.
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.
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...
>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 ...
>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
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
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?
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.
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?
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?
2) now - timestamp is implementation choice and should not be here
3) there is a typo in timestamp*e*
>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.
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.
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.
[**]
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.
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:
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
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.
>It can *b* reduced
it can be reduced
Sec5.2
> This threshold would allow *us* a long enough period
us should not be there
Best Regards,
Polina
_______________________________________________
aqm mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/aqm
