Re: [aqm] PIE departure rate estimation

[Dave Dolson <[e-mail]>]

Rong,
(Please keep in mind I am only trying to provide constructive criticism, as someone new to the PIE algorithm.)

>>>>>>>>>>>>>>RP: There are two calculations in the PIE algorithm: one is for p update and one is for calculate the rate. They are independent from each other. If there are not enough packets in the buffer, we simply don't update depart rate estimation,  instead we use the previous value. However, the drop probability calculation is always updated. Hence, the "p" in your example will go down to 0.

I didn't get this point from the draft, that 'p' is periodically updated regardless of whether rate measurements are available.
May I suggest a statement in section 4.3: "Note that p is updated per section 4.2 even when not in a measurement cycle; in this case the previously latched value of depart_rate is used."


[Sorry, the following is really pedantic, but I couldn't help myself...]

I tried to prove to myself that "p" will go down to 0 when the queue size is below a certain size.
I found that it will not go down to 0 in a contrived situation when packet arrival rate equals transmit rate, keeping qlen constant
target_del * depart_rate <= qlen <= dq_threshold

In this range, depart_rate is never recomputed, so it might have latched any arbitrary value, making the lower bound a constant.

In this range, p is not reduced because the beta*(est_del - est_del_old) term is zero (constant qlen) and the alpha*(est_del-target_del) is zero or positive.

I didn't work out the details, but because it takes a while for 'p' to get to zero, I think there are a variety of traffic patterns that can allow 'p' to meander around in non-zero space even though the queue is nearly empty. (p could be fairly large, which is the reason the queue is nearly empty).

The key to this scenario is latching a low value of depart_rate and never updating it.

In practice this might never happen, but also in practice anything that can happen will. At least it probably won't be reproducible :-)

Is there a fix? I think it is to remove the restriction that a minimum queue size is required for a measurement cycle. It's better to measure the actual rate (even if it is not the potential rate) than have a bad estimate. Then depart_rate is allowed to increase to the actual rate, and the estimated delay is allowed to decrease.

-Dave



From: Rong Pan (ropan) [mailto:[e-mail]]
Sent: Wednesday, April 01, 2015 6:28 PM
To: Dave Dolson; [e-mail]
Subject: Re: [aqm] PIE departure rate estimation

Please see inline...

Rong

From: Dave Dolson <[e-mail]<mailto:[e-mail]>>
Date: Wednesday, April 1, 2015 2:43 PM
To: rong <[e-mail]<mailto:[e-mail]>>, "[e-mail]<mailto:[e-mail]>" <[e-mail]<mailto:[e-mail]>>
Subject: RE: [aqm] PIE departure rate estimation

Inline [DD]

From: Rong Pan (ropan) [mailto:[e-mail]]
Sent: Wednesday, April 01, 2015 5:23 PM
To: Dave Dolson; [e-mail]<mailto:[e-mail]>
Subject: Re: [aqm] PIE departure rate estimation

Dave,

Thanks for the valuable comments. We will see how we can incorporate them. For the comments below, please see inline.

Regards,

Rong


From: Dave Dolson <[e-mail]<mailto:[e-mail]>>
Date: Wednesday, April 1, 2015 1:22 PM
To: "[e-mail]<mailto:[e-mail]>" <[e-mail]<mailto:[e-mail]>>
Subject: [aqm] PIE departure rate estimation

In https://tools.ietf.org/html/draft-ietf-aqm-pie-00#section-4.3,

it says, "We only measure the departure rate when there are sufficient data in the buffer"

Why can't departure rate be estimated regardless of queue size? Just count packets leaving over time? I'm wondering how to avoid the estimate getting stuck at the last value sampled when the queue had a certain quantity in it.

>>>>>>>>>>>>RP: We need to make sure that there are enough data in the queue to guarantee a rate sample. The reason is that if a queue is empty from time to time, we can't measure its true draining rate. The time when the queue empty should be cut out of the drain time calculation. For simplicity, it is better to make sure we have enough data in the queue to ensure accurate rate measurement sample.
[DD] I understand the rationale, but supposing p=0.1, but the queue has very few items in it, too few to obtain a rate calculation. What causes p to go to zero, since an update is not permitted? It isn't obvious to me that the algorithm always stops for all input traffic patterns.

>>>>>>>>>>>>>>RP: There are two calculations in the PIE algorithm: one is for p update and one is for calculate the rate. They are independent from each other. If there are not enough packets in the buffer, we simply don't update depart rate estimation,  instead we use the previous value. However, the drop probability calculation is always updated. Hence, the "p" in your example will go down to 0.


Section 4.2 cites Little's Law as "est_del = qlen/depart_rate",
but according to Wikipedia<http://en.wikipedia.org/wiki/Little%27s_law>, the law uses arrival rate, not departure rate.
I don't know if it matters (I didn't read Little's proof), but this gives credence to the suggestion in section 6 that the algorithm could use arrival rate.
And I think it might be easier to measure when the queue has few items in it.

>>>>>>>>>>>>RP: what you mentioned is to calculate average number of customers in a system using the arrival. http://en.wikipedia.org/wiki/Little's_law Wikipedia also mentions that mean responseTime = MeanNumberInSystem / MeanThroughput. What we measure is the mean response time (latency). Hence, it is correct in our draft.
[DD] Arrival (post drop) and departure rates are almost never the same at any instant. I guess they must average to the same value. Practically, it might not matter which is used, but I thought Little's law should be cited correctly. In Wikipedia the law is cited one way and the example is shown another way. Furthermore there is this ominous comment: "When exploring Little's law and learning to trust it, be aware of the common mistakes of using arrivals(work arriving) when throughput(work completed) is called for..."

>>>>>>>>>>>>>RP: I understand the concern. But I think we have used it in the right way. Arrival is related to how many customers/packets in a system. However, given #of customers/packets in a system, the wait time is directly related to the service time (inverse of throughput), not arrival rate any more.

David Dolson
Senior Software Architect, Sandvine Inc.