Re: [aqm] Questioning each PIE heuristic - moving averages and rate measurement

[Bob Briscoe]

Rong,

That's a good rationale.
I withdraw my criticism of PIE on this point.

The code is OK, it's just the explanation that is misleading. it 
shouldn't say it is measuring the average dequeue rate, and there's no 
need to. It should describe the calculation as a moving average of the 
time to dequeue a set amount of bytes, scaled by the queue size relative 
to that number of bytes.


Cheers


Bob

On 26/05/17 19:29, Rong Pan (ropan) wrote:

Michael and Bob,

The depart_rate is inversed in calculation delay….
Delay = queue_length/depart_rate;
Hence, current_qdelay = queue_.byte_length() * PIE- >avg_dq_time_/DQ_THRESHOLD;

Basically the average dq_time for dequeueing DQ_THRESHOLD is PIE->dq_time; What 
is the approximate time to deque the current_qlen?
Current_qlen/DQ_THRESHOLD(what portion is current queue length relative to 
DQ_THRESHOLD)? * avg_dq_time.

That is the rationale behind it.

Thanks,

Rong

 >> (EWMA) of the rate should be:
 >>
 >>  ewma(depart_rate) = DQ_THRESHOLD ∗ ewma(1/t1,1/t2,1/t3,...)
 >>   != DQ_THRESHOLD / ewma(t1,t2,t3,...)
 >> "
 >> PIE uses the second (incorrect) formula. In the review, I discuss how
 >> wrong this could be, with an example.
 > Thanks, Bob, for pointing this out to me.
 >
 > Rong, is PIE doing this by intent (if so, what's the reason?) or is this
 > a flaw?
 >


___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm


--

Bob Briscoe   http://bobbriscoe.net/

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic - moving averages and rate measurement

[Rong Pan (ropan)]

Additional consideration is that 1/t1 would involve divide, which will be hard 
to implement in hardware…

Regards,

Rong

On 5/26/17, 11:29 AM, "aqm on behalf of Rong Pan (ropan)"  wrote:

Michael and Bob,

The depart_rate is inversed in calculation delay….
Delay = queue_length/depart_rate; 
Hence, current_qdelay = queue_.byte_length() * PIE- 
>avg_dq_time_/DQ_THRESHOLD;

Basically the average dq_time for dequeueing DQ_THRESHOLD is PIE->dq_time; 
What is the approximate time to deque the current_qlen?
Current_qlen/DQ_THRESHOLD(what portion is current queue length relative to 
DQ_THRESHOLD)? * avg_dq_time.

That is the rationale behind it.

Thanks,

Rong

>> (EWMA) of the rate should be:
>>
>>  ewma(depart_rate) = DQ_THRESHOLD ∗ ewma(1/t1,1/t2,1/t3,...)
>>   != DQ_THRESHOLD / ewma(t1,t2,t3,...)
>> "
>> PIE uses the second (incorrect) formula. In the review, I discuss how
>> wrong this could be, with an example.
> Thanks, Bob, for pointing this out to me.
>
> Rong, is PIE doing this by intent (if so, what's the reason?) or is 
this
> a flaw?
>


___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm


___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic - moving averages and rate measurement

[Rong Pan (ropan)]

Michael and Bob,

The depart_rate is inversed in calculation delay….
Delay = queue_length/depart_rate; 
Hence, current_qdelay = queue_.byte_length() * PIE- >avg_dq_time_/DQ_THRESHOLD;

Basically the average dq_time for dequeueing DQ_THRESHOLD is PIE->dq_time; What 
is the approximate time to deque the current_qlen?
Current_qlen/DQ_THRESHOLD(what portion is current queue length relative to 
DQ_THRESHOLD)? * avg_dq_time.

That is the rationale behind it.

Thanks,

Rong

>> (EWMA) of the rate should be:
>>
>>  ewma(depart_rate) = DQ_THRESHOLD ∗ ewma(1/t1,1/t2,1/t3,...)
>>   != DQ_THRESHOLD / ewma(t1,t2,t3,...)
>> "
>> PIE uses the second (incorrect) formula. In the review, I discuss how
>> wrong this could be, with an example.
> Thanks, Bob, for pointing this out to me.
>
> Rong, is PIE doing this by intent (if so, what's the reason?) or is this
> a flaw?
>


___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic - moving averages and rate measurement

[Bob Briscoe]

Michael,

Yes, I should have said that the most useful aspect of your paper is the 
model that ties all the different algos together allowing comparison.



Bob

On 25/05/17 08:55, Michael Menth wrote:

Hi Bob, hi Rong,

Am 25.05.2017 um 00:34 schrieb Bob Briscoe:

Michael,

I just started reading your paper. Two comments so far:

*1) PIE rate averaging is an unfortunate example**
*In related work, you mention PIE's measurement of the link rate as an
example of use of moving averages. This is an unfortunate example,
because the PIE code screws up the calculation. It averages a fraction
by averaging the denominator, which I pointed out is wrong in Section
5.3.2 of my PIE review .
Quoting...

"The [PIE] pseudocode continually measures the sequence of dequeue
times, t1, t2, t3,... that it takes to transmit constant amounts of
bytes (DQ_THRESHOLD). Then the exponentially weighted moving average
(EWMA) of the rate should be:

 ewma(depart_rate) = DQ_THRESHOLD ∗ ewma(1/t1,1/t2,1/t3,...)
  != DQ_THRESHOLD / ewma(t1,t2,t3,...)
"
PIE uses the second (incorrect) formula. In the review, I discuss how
wrong this could be, with an example.

Thanks, Bob, for pointing this out to me.

Rong, is PIE doing this by intent (if so, what's the reason?) or is this
a flaw?


*2) Exponential Moving Average is an Approximation**
*In your moving averages paper, you compare your unbiased exponential
moving average (UEMA) algorithm with this commonly used exponential
moving average (EMA) algorithm:
 ewma(X) <- (1-a)*X + a*ewma(X)

A few years ago I wondered about this comparison, and wrote a 2-page
memo for myself to record the proof. I've temporarily uploaded it here:
Moving Averages .

I used a Taylor series expansion to show that the iterative formula
tends to the exact formula (what you call the unbiased EMA or UEMA) as
the number of readings (n) becomes large.

When n is not large, you could use the formula at the top of my p2 (just
before the Taylor series approximation) to calculate the ratio between
the actual (unbiased) UEMA and my regular iterative EMA (REMA). This
ratio can be pre-calculated, because its independent of the readings:
 REMA/UEMA = (1-a)*(Sum_{j=0}^{n-1} a^j)

where
   "theta" in my formula is "a" in yours
   "Sum_{j=0}^{n-1}" means "the sum from j=0 to j=n-1"
   Your iterative formula (EMA) starts with an exception, whereas I use
an iterative formula that just starts the same as it carries on. To
distinguish between them, I have called mine "regular EMA" or REMA.

For instance, if a = 0.75 as in your Fig 1(c), then the correction
factors for various small numbers of readings, n, are:

n   UEMA/REMA
_
12.29
21.73
31.46
41.31
51.22
61.15
71.11
81.08
91.06
101.04
111.03
121.02
131.02
141.01
151.01
161.01
171.01
181.00
191.00
201.00

Yes, the bias of E(W)MA is caused by the first sample and vanishes over
time. If EMA runs continuously, it has no impact. If EMA is continuously
restarted, it may have an impact. However, this is only a minor aspect
of the paper.
https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth17c.pdf

The major contribution of the paper is a framework that brings together
various types of moving averages, moving histograms and rate measurement
methods. In particular, it relates E(W)MA's "magic weight parameter" to
a memory which is also implemented by other methods (with other
parameters). The concept of a memory simplifies many engineering problems.

Regards,

Michael



Cheers


Bob

On 30/03/17 10:57, Michael Menth wrote:

Hi all,

Am 30.03.2017 um 11:08 schrieb Jonathan Morton:

On 30 Mar, 2017, at 10:46, Bob Briscoe  wrote:

For PI2 we removed all but 2 and it worked the same or better than PIE in all 
our tests. I have been assessing each of the other 7 one by one for 
reinstatement. So far I've rejected 6. I think I can reject this last one by 
making the sampling time of the base PI algo dependent on the max link rate. 
Then when the queue goes idle, the base PI algo will decay drop down to zero no 
slower than the queue drains, without needing this extra heuristic.

That’s fair enough.

It sounds like the fairly coarsely discrete time intervals in PIE are the main 
justification for this particular heuristic, so it might be sufficient to 
document that WRT PIE itself.  Using finer time intervals is clearly a better 
choice for the future.

PIE uses time intervals for measurement purposes and several parameters
contribute. We've recently done some basic work on measurement
methodology that facilitates a comparison of different measurement
approaches and better-informed parametrization by 

Re: [aqm] Questioning each PIE heuristic - moving averages and rate measurement

[Michael Menth]

Hi Bob, hi Rong,

Am 25.05.2017 um 00:34 schrieb Bob Briscoe:
> Michael,
> 
> I just started reading your paper. Two comments so far:
> 
> *1) PIE rate averaging is an unfortunate example**
> *In related work, you mention PIE's measurement of the link rate as an
> example of use of moving averages. This is an unfortunate example,
> because the PIE code screws up the calculation. It averages a fraction
> by averaging the denominator, which I pointed out is wrong in Section
> 5.3.2 of my PIE review .
> Quoting...
> 
> "The [PIE] pseudocode continually measures the sequence of dequeue
> times, t1, t2, t3,... that it takes to transmit constant amounts of
> bytes (DQ_THRESHOLD). Then the exponentially weighted moving average
> (EWMA) of the rate should be:
> 
> ewma(depart_rate) = DQ_THRESHOLD ∗ ewma(1/t1,1/t2,1/t3,...)
>  != DQ_THRESHOLD / ewma(t1,t2,t3,...)
> "
> PIE uses the second (incorrect) formula. In the review, I discuss how
> wrong this could be, with an example.

Thanks, Bob, for pointing this out to me.

Rong, is PIE doing this by intent (if so, what's the reason?) or is this
a flaw?

> 
> *2) Exponential Moving Average is an Approximation**
> *In your moving averages paper, you compare your unbiased exponential
> moving average (UEMA) algorithm with this commonly used exponential
> moving average (EMA) algorithm:
> ewma(X) <- (1-a)*X + a*ewma(X)
> 
> A few years ago I wondered about this comparison, and wrote a 2-page
> memo for myself to record the proof. I've temporarily uploaded it here:
> Moving Averages .
> 
> I used a Taylor series expansion to show that the iterative formula
> tends to the exact formula (what you call the unbiased EMA or UEMA) as
> the number of readings (n) becomes large.
> 
> When n is not large, you could use the formula at the top of my p2 (just
> before the Taylor series approximation) to calculate the ratio between
> the actual (unbiased) UEMA and my regular iterative EMA (REMA). This
> ratio can be pre-calculated, because its independent of the readings:
> REMA/UEMA = (1-a)*(Sum_{j=0}^{n-1} a^j)
> 
> where
>   "theta" in my formula is "a" in yours
>   "Sum_{j=0}^{n-1}" means "the sum from j=0 to j=n-1"
>   Your iterative formula (EMA) starts with an exception, whereas I use
> an iterative formula that just starts the same as it carries on. To
> distinguish between them, I have called mine "regular EMA" or REMA.
> 
> For instance, if a = 0.75 as in your Fig 1(c), then the correction
> factors for various small numbers of readings, n, are:
> 
> n   UEMA/REMA
> _
> 12.29
> 21.73
> 31.46
> 41.31
> 51.22
> 61.15
> 71.11
> 81.08
> 91.06
> 101.04
> 111.03
> 121.02
> 131.02
> 141.01
> 151.01
> 161.01
> 171.01
> 181.00
> 191.00
> 201.00
Yes, the bias of E(W)MA is caused by the first sample and vanishes over
time. If EMA runs continuously, it has no impact. If EMA is continuously
restarted, it may have an impact. However, this is only a minor aspect
of the paper.
https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth17c.pdf

The major contribution of the paper is a framework that brings together
various types of moving averages, moving histograms and rate measurement
methods. In particular, it relates E(W)MA's "magic weight parameter" to
a memory which is also implemented by other methods (with other
parameters). The concept of a memory simplifies many engineering problems.

Regards,

Michael

> 
> 
> Cheers
> 
> 
> Bob
> 
> On 30/03/17 10:57, Michael Menth wrote:
>> Hi all,
>>
>> Am 30.03.2017 um 11:08 schrieb Jonathan Morton:
 On 30 Mar, 2017, at 10:46, Bob Briscoe  wrote:

 For PI2 we removed all but 2 and it worked the same or better than PIE in 
 all our tests. I have been assessing each of the other 7 one by one for 
 reinstatement. So far I've rejected 6. I think I can reject this last one 
 by making the sampling time of the base PI algo dependent on the max link 
 rate. Then when the queue goes idle, the base PI algo will decay drop down 
 to zero no slower than the queue drains, without needing this extra 
 heuristic.
>>> That’s fair enough.
>>>
>>> It sounds like the fairly coarsely discrete time intervals in PIE are the 
>>> main justification for this particular heuristic, so it might be sufficient 
>>> to document that WRT PIE itself.  Using finer time intervals is clearly a 
>>> better choice for the future.
>> PIE uses time intervals for measurement purposes and several parameters
>> contribute. We've recently done some basic work on measurement
>> methodology that facilitates a comparison of different measurement
>> approaches 

Re: [aqm] Questioning each PIE heuristic - moving averages and rate measurement

[Bob Briscoe]

Michael,

I just started reading your paper. Two comments so far:

*1) PIE rate averaging is an unfortunate example**
*In related work, you mention PIE's measurement of the link rate as an 
example of use of moving averages. This is an unfortunate example, 
because the PIE code screws up the calculation. It averages a fraction 
by averaging the denominator, which I pointed out is wrong in Section 
5.3.2 of my PIE review . 
Quoting...


"The [PIE] pseudocode continually measures the sequence of dequeue 
times, t1, t2, t3,... that it takes to transmit constant amounts of 
bytes (DQ_THRESHOLD). Then the exponentially weighted moving average 
(EWMA) of the rate should be:


ewma(depart_rate) = DQ_THRESHOLD ∗ ewma(1/t1,1/t2,1/t3,...)
 != DQ_THRESHOLD / ewma(t1,t2,t3,...)
"
PIE uses the second (incorrect) formula. In the review, I discuss how 
wrong this could be, with an example.


*2) Exponential Moving Average is an Approximation**
*In your moving averages paper, you compare your unbiased exponential 
moving average (UEMA) algorithm with this commonly used exponential 
moving average (EMA) algorithm:

ewma(X) <- (1-a)*X + a*ewma(X)

A few years ago I wondered about this comparison, and wrote a 2-page 
memo for myself to record the proof. I've temporarily uploaded it here: 
Moving Averages .


I used a Taylor series expansion to show that the iterative formula 
tends to the exact formula (what you call the unbiased EMA or UEMA) as 
the number of readings (n) becomes large.


When n is not large, you could use the formula at the top of my p2 (just 
before the Taylor series approximation) to calculate the ratio between 
the actual (unbiased) UEMA and my regular iterative EMA (REMA). This 
ratio can be pre-calculated, because its independent of the readings:

REMA/UEMA = (1-a)*(Sum_{j=0}^{n-1} a^j)

where
  "theta" in my formula is "a" in yours
  "Sum_{j=0}^{n-1}" means "the sum from j=0 to j=n-1"
  Your iterative formula (EMA) starts with an exception, whereas I use 
an iterative formula that just starts the same as it carries on. To 
distinguish between them, I have called mine "regular EMA" or REMA.


For instance, if a = 0.75 as in your Fig 1(c), then the correction 
factors for various small numbers of readings, n, are:


n   UEMA/REMA
_
12.29
21.73
31.46
41.31
51.22
61.15
71.11
81.08
91.06
101.04
111.03
121.02
131.02
141.01
151.01
161.01
171.01
181.00
191.00
201.00


Cheers


Bob

On 30/03/17 10:57, Michael Menth wrote:

Hi all,

Am 30.03.2017 um 11:08 schrieb Jonathan Morton:

On 30 Mar, 2017, at 10:46, Bob Briscoe  wrote:

For PI2 we removed all but 2 and it worked the same or better than PIE in all 
our tests. I have been assessing each of the other 7 one by one for 
reinstatement. So far I've rejected 6. I think I can reject this last one by 
making the sampling time of the base PI algo dependent on the max link rate. 
Then when the queue goes idle, the base PI algo will decay drop down to zero no 
slower than the queue drains, without needing this extra heuristic.

That’s fair enough.

It sounds like the fairly coarsely discrete time intervals in PIE are the main 
justification for this particular heuristic, so it might be sufficient to 
document that WRT PIE itself.  Using finer time intervals is clearly a better 
choice for the future.

PIE uses time intervals for measurement purposes and several parameters
contribute. We've recently done some basic work on measurement
methodology that facilitates a comparison of different measurement
approaches and better-informed parametrization by introduction of the
"memory" concept.
https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth17c.pdf
PIE essentially implements TDRM-DTWMA-UEMA illustrated in Fig. 6d.

The concept of "memory" can also be applied to moving averages which are
also used in PIE for several purposes. Configuration via a "memory" can
make some heuristics more intuitive.

Best wishes,

Michael




  - Jonathan Morton



--

Bob Briscoe   http://bobbriscoe.net/

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Dave Dolson]

While reviewing PIE, it might be worth revisiting my comment here: 
https://mailarchive.ietf.org/arch/msg/aqm/ifkBe6uvME5Nqm-J6ulZWlooBxo
The second part was never answered to my satisfaction.

I believed I had found a bug:  I said, "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"

Maybe you've addressed this, because I think it was due to a heuristic.

I'm much in favor of removing the heuristics on control systems; thanks.

-Dave



-Original Message-
From: aqm [mailto:aqm-boun...@ietf.org] On Behalf Of Bob Briscoe
Sent: Thursday, March 30, 2017 2:47 AM
To: Jonathan Morton; Rong Pan (ropan)
Cc: Greg White; tsvwg IETF list; AQM IETF list; fredbaker.i...@gmail.com
Subject: Re: [aqm] Questioning each PIE heuristic

Jonathan,

Picking up on an earlier point you made about avoiding heuristics by ensuring 
the underlying algo is sound,... that's precisely why I'm going through all the 
(9) PIE heuristics...

For PI2 we removed all but 2 and it worked the same or better than PIE in all 
our tests. I have been assessing each of the other 7 one by one for 
reinstatement. So far I've rejected 6. I think I can reject this last one by 
making the sampling time of the base PI algo dependent on the max link rate. 
Then when the queue goes idle, the base PI algo will decay drop down to zero no 
slower than the queue drains, without needing this extra heuristic. But I need 
to check that's realistic.

We will be writing all this up (probably in an update to the PI2 paper - I 
don't think the IETF PI2 spec is the right place for a critique of heuristics 
that it doesn't use).

Our aim is a completely sound AQM in a few lines of code and a few operations 
so it can be implemented everywhere with minimal resistance from developers due 
to performance concerns (e.g. cheap ethernet switches, cheap home gateways, 
carrier-grade equipment for thousands of users, etc).


Bob

On 28/03/17 07:25, Jonathan Morton wrote:
>
> By all means, avoid dropping packets when the queue is actually empty - that 
> is, when you’re delivering the last packet in the queue.  In that case, there 
> is no congestion to signal for.  But there really is no need to have any 
> complex state-switching logic for that.  If your underlying algorithm is 
> sound, it will naturally decay to zero packet drops if the empty-queue 
> condition persists.
>
>   - Jonathan Morton
>


--

Bob Briscoe   http://bobbriscoe.net/

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm
___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic - moving averages and rate measurement

[Michael Menth]

Hi all,

Am 30.03.2017 um 11:08 schrieb Jonathan Morton:
> 
>> On 30 Mar, 2017, at 10:46, Bob Briscoe  wrote:
>>
>> For PI2 we removed all but 2 and it worked the same or better than PIE in 
>> all our tests. I have been assessing each of the other 7 one by one for 
>> reinstatement. So far I've rejected 6. I think I can reject this last one by 
>> making the sampling time of the base PI algo dependent on the max link rate. 
>> Then when the queue goes idle, the base PI algo will decay drop down to zero 
>> no slower than the queue drains, without needing this extra heuristic.
> 
> That’s fair enough.
> 
> It sounds like the fairly coarsely discrete time intervals in PIE are the 
> main justification for this particular heuristic, so it might be sufficient 
> to document that WRT PIE itself.  Using finer time intervals is clearly a 
> better choice for the future.
PIE uses time intervals for measurement purposes and several parameters
contribute. We've recently done some basic work on measurement
methodology that facilitates a comparison of different measurement
approaches and better-informed parametrization by introduction of the
"memory" concept.
https://atlas.informatik.uni-tuebingen.de/~menth/papers/Menth17c.pdf
PIE essentially implements TDRM-DTWMA-UEMA illustrated in Fig. 6d.

The concept of "memory" can also be applied to moving averages which are
also used in PIE for several purposes. Configuration via a "memory" can
make some heuristics more intuitive.

Best wishes,

Michael



> 
>  - Jonathan Morton
> 

-- 
Prof. Dr. habil. Michael Menth
University of Tuebingen
Faculty of Science
Department of Computer Science
Chair of Communication Networks
Sand 13, 72076 Tuebingen, Germany
phone: (+49)-7071/29-70505
fax: (+49)-7071/29-5220
mailto:me...@uni-tuebingen.de
http://kn.inf.uni-tuebingen.de

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Jonathan Morton]

> On 30 Mar, 2017, at 10:46, Bob Briscoe  wrote:
> 
> For PI2 we removed all but 2 and it worked the same or better than PIE in all 
> our tests. I have been assessing each of the other 7 one by one for 
> reinstatement. So far I've rejected 6. I think I can reject this last one by 
> making the sampling time of the base PI algo dependent on the max link rate. 
> Then when the queue goes idle, the base PI algo will decay drop down to zero 
> no slower than the queue drains, without needing this extra heuristic.

That’s fair enough.

It sounds like the fairly coarsely discrete time intervals in PIE are the main 
justification for this particular heuristic, so it might be sufficient to 
document that WRT PIE itself.  Using finer time intervals is clearly a better 
choice for the future.

 - Jonathan Morton

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Bob Briscoe]

Jonathan,

Picking up on an earlier point you made about avoiding heuristics by 
ensuring the underlying algo is sound,... that's precisely why I'm going 
through all the (9) PIE heuristics...


For PI2 we removed all but 2 and it worked the same or better than PIE 
in all our tests. I have been assessing each of the other 7 one by one 
for reinstatement. So far I've rejected 6. I think I can reject this 
last one by making the sampling time of the base PI algo dependent on 
the max link rate. Then when the queue goes idle, the base PI algo will 
decay drop down to zero no slower than the queue drains, without needing 
this extra heuristic. But I need to check that's realistic.


We will be writing all this up (probably in an update to the PI2 paper - 
I don't think the IETF PI2 spec is the right place for a critique of 
heuristics that it doesn't use).


Our aim is a completely sound AQM in a few lines of code and a few 
operations so it can be implemented everywhere with minimal resistance 
from developers due to performance concerns (e.g. cheap ethernet 
switches, cheap home gateways, carrier-grade equipment for thousands of 
users, etc).



Bob

On 28/03/17 07:25, Jonathan Morton wrote:


By all means, avoid dropping packets when the queue is actually empty - that 
is, when you’re delivering the last packet in the queue.  In that case, there 
is no congestion to signal for.  But there really is no need to have any 
complex state-switching logic for that.  If your underlying algorithm is sound, 
it will naturally decay to zero packet drops if the empty-queue condition 
persists.

  - Jonathan Morton




--

Bob Briscoe   http://bobbriscoe.net/

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Rong Pan (ropan)]

We are not holding back queued packets when the link is idle. We stop dropping 
packets when the queue is shallow in order to avoid unnecessary drops that 
could cause TCP traffic to back off and stop sending traffic that will cause 
link idle.

Rong

From: "Lautenschlaeger, Wolfram (Nokia - DE/Stuttgart)" 
<wolfram.lautenschlae...@nokia-bell-labs.com<mailto:wolfram.lautenschlae...@nokia-bell-labs.com>>
Date: Wednesday, March 29, 2017 at 2:30 AM
To: Rong Pan <ro...@cisco.com<mailto:ro...@cisco.com>>, Luca Muscariello 
<luca.muscarie...@gmail.com<mailto:luca.muscarie...@gmail.com>>, "Bless, Roland 
(TM)" <roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>>
Cc: tsvwg IETF list <ts...@ietf.org<mailto:ts...@ietf.org>>, Fred Baker 
<fredbaker.i...@gmail.com<mailto:fredbaker.i...@gmail.com>>, Bob Briscoe 
<i...@bobbriscoe.net<mailto:i...@bobbriscoe.net>>, "De Schepper, Koen (Nokia - 
BE/Antwerp)" 
<koen.de_schep...@nokia-bell-labs.com<mailto:koen.de_schep...@nokia-bell-labs.com>>,
 Greg White <g.wh...@cablelabs.com<mailto:g.wh...@cablelabs.com>>, Jonathan 
Morton <chromati...@gmail.com<mailto:chromati...@gmail.com>>, AQM IETF list 
<aqm@ietf.org<mailto:aqm@ietf.org>>, Preethi Natarajan 
<prena...@cisco.com<mailto:prena...@cisco.com>>
Subject: RE: [aqm] Questioning each PIE heuristic

To my understanding a proper operating AQM _is_ work-conserving. Packet drops 
occur, if any, when a reasonable queue is present. And as long as packets are 
present in the queue, the link runs at 100%. I cannot see any (AQM) mechanism 
that is holding back queued packets while the link is idle.

Wolfram


From: aqm [mailto:aqm-boun...@ietf.org] On Behalf Of Rong Pan (ropan)
Sent: Dienstag, 28. März 2017 16:17
To: Luca Muscariello 
<luca.muscarie...@gmail.com<mailto:luca.muscarie...@gmail.com>>; Bless, Roland 
(TM) <roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>>
Cc: tsvwg IETF list <ts...@ietf.org<mailto:ts...@ietf.org>>; Fred Baker 
<fredbaker.i...@gmail.com<mailto:fredbaker.i...@gmail.com>>; Bob Briscoe 
<i...@bobbriscoe.net<mailto:i...@bobbriscoe.net>>; De Schepper, Koen (Nokia - 
BE/Antwerp) 
<koen.de_schep...@nokia-bell-labs.com<mailto:koen.de_schep...@nokia-bell-labs.com>>;
 Greg White <g.wh...@cablelabs.com<mailto:g.wh...@cablelabs.com>>; Jonathan 
Morton <chromati...@gmail.com<mailto:chromati...@gmail.com>>; AQM IETF list 
<aqm@ietf.org<mailto:aqm@ietf.org>>; Preethi Natarajan 
<prena...@cisco.com<mailto:prena...@cisco.com>>
Subject: Re: [aqm] Questioning each PIE heuristic

Sorry for causing the confusion in choosing the word "work-conserving". If we 
apply AQM and can not achieving 100% line rate, i.e. losing throughput, it is a 
big No No. Since we are dealing with TCP traffic, excess drops can cause TCP to 
back off too much and under-utilize the link.

Rong

From: Luca Muscariello 
<luca.muscarie...@gmail.com<mailto:luca.muscarie...@gmail.com>>
Date: Tuesday, March 28, 2017 at 8:48 AM
To: "Bless, Roland (TM)" <roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>>
Cc: Fred Baker <fredbaker.i...@gmail.com<mailto:fredbaker.i...@gmail.com>>, 
Jonathan Morton <chromati...@gmail.com<mailto:chromati...@gmail.com>>, tsvwg 
IETF list <ts...@ietf.org<mailto:ts...@ietf.org>>, Bob Briscoe 
<i...@bobbriscoe.net<mailto:i...@bobbriscoe.net>>, "De Schepper, Koen (Koen)" 
<koen.de_schep...@nokia.com<mailto:koen.de_schep...@nokia.com>>, Rong Pan 
<ro...@cisco.com<mailto:ro...@cisco.com>>, Greg White 
<g.wh...@cablelabs.com<mailto:g.wh...@cablelabs.com>>, AQM IETF list 
<aqm@ietf.org<mailto:aqm@ietf.org>>, Preethi Natarajan 
<prena...@cisco.com<mailto:prena...@cisco.com>>
Subject: Re: [aqm] Questioning each PIE heuristic

Work conserving is supposed to be referring to the scheduler.
I'm not familiar with work-conservation when it refers to active queue 
management.
I'm not sure it is actually defined.

I can understand that an AQM can produce under utilization of the link, but 
that is
different to work conservation. Or is it maybe more subtle than that?

Luca

On Tue, Mar 28, 2017 at 1:48 PM, Bless, Roland (TM) 
<roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>> wrote:
Hi,

Am 28.03.2017 um 13:39 schrieb Fred Baker:

> I'm not convinced I understand the definitions of "work conserving"
> and "non work conserving" in this context. A "work conserving"
> scheduling algorithm keeps an interface transmitting as long as there
> is data in the queue, while a non-work-conserving algorithm reduces
> the effective rate of the interface by spacing packets out.

+1 (that's also the definition I use, so I'm lost here too)

Regards,
 Roland

___
aqm mailing list
aqm@ietf.org<mailto:aqm@ietf.org>
https://www.ietf.org/mailman/listinfo/aqm

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Lautenschlaeger, Wolfram (Nokia - DE/Stuttgart)]

To my understanding a proper operating AQM _is_ work-conserving. Packet drops 
occur, if any, when a reasonable queue is present. And as long as packets are 
present in the queue, the link runs at 100%. I cannot see any (AQM) mechanism 
that is holding back queued packets while the link is idle.

Wolfram


From: aqm [mailto:aqm-boun...@ietf.org] On Behalf Of Rong Pan (ropan)
Sent: Dienstag, 28. März 2017 16:17
To: Luca Muscariello <luca.muscarie...@gmail.com>; Bless, Roland (TM) 
<roland.bl...@kit.edu>
Cc: tsvwg IETF list <ts...@ietf.org>; Fred Baker <fredbaker.i...@gmail.com>; 
Bob Briscoe <i...@bobbriscoe.net>; De Schepper, Koen (Nokia - BE/Antwerp) 
<koen.de_schep...@nokia-bell-labs.com>; Greg White <g.wh...@cablelabs.com>; 
Jonathan Morton <chromati...@gmail.com>; AQM IETF list <aqm@ietf.org>; Preethi 
Natarajan <prena...@cisco.com>
Subject: Re: [aqm] Questioning each PIE heuristic

Sorry for causing the confusion in choosing the word "work-conserving". If we 
apply AQM and can not achieving 100% line rate, i.e. losing throughput, it is a 
big No No. Since we are dealing with TCP traffic, excess drops can cause TCP to 
back off too much and under-utilize the link.

Rong

From: Luca Muscariello 
<luca.muscarie...@gmail.com<mailto:luca.muscarie...@gmail.com>>
Date: Tuesday, March 28, 2017 at 8:48 AM
To: "Bless, Roland (TM)" <roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>>
Cc: Fred Baker <fredbaker.i...@gmail.com<mailto:fredbaker.i...@gmail.com>>, 
Jonathan Morton <chromati...@gmail.com<mailto:chromati...@gmail.com>>, tsvwg 
IETF list <ts...@ietf.org<mailto:ts...@ietf.org>>, Bob Briscoe 
<i...@bobbriscoe.net<mailto:i...@bobbriscoe.net>>, "De Schepper, Koen (Koen)" 
<koen.de_schep...@nokia.com<mailto:koen.de_schep...@nokia.com>>, Rong Pan 
<ro...@cisco.com<mailto:ro...@cisco.com>>, Greg White 
<g.wh...@cablelabs.com<mailto:g.wh...@cablelabs.com>>, AQM IETF list 
<aqm@ietf.org<mailto:aqm@ietf.org>>, Preethi Natarajan 
<prena...@cisco.com<mailto:prena...@cisco.com>>
Subject: Re: [aqm] Questioning each PIE heuristic

Work conserving is supposed to be referring to the scheduler.
I'm not familiar with work-conservation when it refers to active queue 
management.
I'm not sure it is actually defined.

I can understand that an AQM can produce under utilization of the link, but 
that is
different to work conservation. Or is it maybe more subtle than that?

Luca

On Tue, Mar 28, 2017 at 1:48 PM, Bless, Roland (TM) 
<roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>> wrote:
Hi,

Am 28.03.2017 um 13:39 schrieb Fred Baker:

> I'm not convinced I understand the definitions of "work conserving"
> and "non work conserving" in this context. A "work conserving"
> scheduling algorithm keeps an interface transmitting as long as there
> is data in the queue, while a non-work-conserving algorithm reduces
> the effective rate of the interface by spacing packets out.

+1 (that's also the definition I use, so I'm lost here too)

Regards,
 Roland

___
aqm mailing list
aqm@ietf.org<mailto:aqm@ietf.org>
https://www.ietf.org/mailman/listinfo/aqm

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Luca Muscariello]

Work conserving is supposed to be referring to the scheduler.
I'm not familiar with work-conservation when it refers to active queue
management.
I'm not sure it is actually defined.

I can understand that an AQM can produce under utilization of the link, but
that is
different to work conservation. Or is it maybe more subtle than that?

Luca

On Tue, Mar 28, 2017 at 1:48 PM, Bless, Roland (TM) 
wrote:

> Hi,
>
> Am 28.03.2017 um 13:39 schrieb Fred Baker:
>
> > I'm not convinced I understand the definitions of "work conserving"
> > and "non work conserving" in this context. A "work conserving"
> > scheduling algorithm keeps an interface transmitting as long as there
> > is data in the queue, while a non-work-conserving algorithm reduces
> > the effective rate of the interface by spacing packets out.
>
> +1 (that's also the definition I use, so I'm lost here too)
>
> Regards,
>  Roland
>
> ___
> aqm mailing list
> aqm@ietf.org
> https://www.ietf.org/mailman/listinfo/aqm
>
___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Rong Pan (ropan)]

Sorry for causing the confusion in choosing the word "work-conserving". If we 
apply AQM and can not achieving 100% line rate, i.e. losing throughput, it is a 
big No No. Since we are dealing with TCP traffic, excess drops can cause TCP to 
back off too much and under-utilize the link.

Rong

From: Luca Muscariello 
<luca.muscarie...@gmail.com<mailto:luca.muscarie...@gmail.com>>
Date: Tuesday, March 28, 2017 at 8:48 AM
To: "Bless, Roland (TM)" <roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>>
Cc: Fred Baker <fredbaker.i...@gmail.com<mailto:fredbaker.i...@gmail.com>>, 
Jonathan Morton <chromati...@gmail.com<mailto:chromati...@gmail.com>>, tsvwg 
IETF list <ts...@ietf.org<mailto:ts...@ietf.org>>, Bob Briscoe 
<i...@bobbriscoe.net<mailto:i...@bobbriscoe.net>>, "De Schepper, Koen (Koen)" 
<koen.de_schep...@nokia.com<mailto:koen.de_schep...@nokia.com>>, Rong Pan 
<ro...@cisco.com<mailto:ro...@cisco.com>>, Greg White 
<g.wh...@cablelabs.com<mailto:g.wh...@cablelabs.com>>, AQM IETF list 
<aqm@ietf.org<mailto:aqm@ietf.org>>, Preethi Natarajan 
<prena...@cisco.com<mailto:prena...@cisco.com>>
Subject: Re: [aqm] Questioning each PIE heuristic

Work conserving is supposed to be referring to the scheduler.
I'm not familiar with work-conservation when it refers to active queue 
management.
I'm not sure it is actually defined.

I can understand that an AQM can produce under utilization of the link, but 
that is
different to work conservation. Or is it maybe more subtle than that?

Luca

On Tue, Mar 28, 2017 at 1:48 PM, Bless, Roland (TM) 
<roland.bl...@kit.edu<mailto:roland.bl...@kit.edu>> wrote:
Hi,

Am 28.03.2017 um 13:39 schrieb Fred Baker:

> I'm not convinced I understand the definitions of "work conserving"
> and "non work conserving" in this context. A "work conserving"
> scheduling algorithm keeps an interface transmitting as long as there
> is data in the queue, while a non-work-conserving algorithm reduces
> the effective rate of the interface by spacing packets out.

+1 (that's also the definition I use, so I'm lost here too)

Regards,
 Roland

___
aqm mailing list
aqm@ietf.org<mailto:aqm@ietf.org>
https://www.ietf.org/mailman/listinfo/aqm

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Bob Briscoe]

Rong,

Some comments inline. And one remaining question at the end...

On 28/03/17 02:04, Rong Pan (ropan) wrote:

Bob,

Sorry for the late reply. I have been traveling. Please see inlineŠ

Rong

On 3/23/17, 5:01 PM, "aqm on behalf of Bob Briscoe"  wrote:


Rong, Preethi, Greg, Fred, and others involved in PIE,

You may recall that when we wrote PI2 we didn't include any of PIE's
heuristics. Mostly because PI2 solved the issues they addressed
intrinsically. But we left some until we had checked their benefit,
which is what I'm doing now...

My first question is about this heuristic in PIE:

  //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;
  }

If it tests true, this block doesn't stop the calculation of drop_prob_
evolving, but it disables it being able to lead to any random packet drop.

I can understand why you want to disable packet drop when the queue is
no more than 2 packets.
My question is about the first half of the logical OR. The drop_prob_ <
20% test will be true under normal non-overloaded conditions. So I have
just realized that the qdelay_old_ < QDELAY_REF/2 test will turn off
random drop very often. I would expect this to radically impact the
behaviour of PIE. It seems to be overriding the PI controller as if you
are thinking "actually we don't really trust the PI controller to leave
it to do its thing, so we've overridden it a lot of the time." For
instance, whenever a single long-running TCP flow with RTT about the
same as the target delay is saw-toothing, this test will disable random
drop completely during the lower half of every saw-tooth in the queue.
Maybe that's OK, but...

Without this test, the PI controller should reduce drop probability as
the queue sawtooths down anyway. If another flow causes the queue to
rise rapidly while it is under half the target, the PI controller is
designed to detect such an increase and translate it into drop. But this
heuristic suppresses any drop until the queue has exceeded half the
target.

So my questions are:

Q1. What were the reasons for introducing such a frequent suppression of
the PI algorithm (the RFC just says what this code does, not why)?


To be work conserving and avoid any unnecessary drops are the main reasons
behind it.
Cisco had a not so successful algorithm before that is not work
conserving. So we are
extra cautious about being work conserving...
[BB] There is only a work-conservation problem if drop_early() is 
applied at enqueue. That's because, at enqueue, you don't yet know 
whether another packet will arrive to take the place of the packet you 
are deciding to drop.


We're shifting drop_early() to dequeue {Note 1}. So to be 
work-conserving we can rely solely on the test on the other side of the 
logical OR above that suppresses any drop if "backlog < 2 MTU".  That's 
the only heuristic that we are keeping so far, although I'm undecided 
about the  "< QDELAY_REF/2" test, which (as you say) might be beneficial 
for other reasons than work conservation. But we have no tests that show 
that yet.


{Note 1}: Because we're using sojourn time to measure the queue, so if 
we were still dropping on enqueue, each congestion signal would be 
delayed twice by the queue.






Q2. Why use qdelay_old_ in the test? This seems to drive suppression of
drop using stale state.

qdelay_old_ is the latency state currently stored. This is for
implementation
Considerations as we don¹t want to calculate qdelay_ on per packet basis.

[BB] Understood.
We're using sojourn time per packet for the shifted FIFO scheduler 
anyway, so no extra cost.



Q3. Having said that it looks like this heuristic will significantly
alter PIE's behaviour, in tests under a very wide range of traffic
conditions, link rates, mixed RTTs, traffic models etc, we have found
that removing the heuristics makes no measurable difference to PIE's
performance. So if you added this heuristic for a specific scenario,
please describe it, so we can test for it.

Again, to be work conserving and avoid drops are our goal. I don¹t
think it would be hurtful to add those safeguards.


[BB]: So that begs just one remaining question:
Q: Do you have tests showing any benefit, specifically comparing with 
and without this  "< QDELAY_REF/2" heuristic?


Given the point of a (non-ECN) AQM is to introduce the right level of 
random drops, it seems strange to suppress some of them with an 
additional arbitrary rule.



Thanks for your replies so far tho. They have helped me realize more 
reasons why PIE needs these heuristics, but PI2 might not.



Bob






Cheers


Bob




--

Bob Briscoehttp://bobbriscoe.net/

___
aqm mailing list
aqm@ietf.org

Re: [aqm] Questioning each PIE heuristic

[Bless, Roland (TM)]

Hi,

Am 28.03.2017 um 13:39 schrieb Fred Baker:

> I'm not convinced I understand the definitions of "work conserving"
> and "non work conserving" in this context. A "work conserving"
> scheduling algorithm keeps an interface transmitting as long as there
> is data in the queue, while a non-work-conserving algorithm reduces
> the effective rate of the interface by spacing packets out. 

+1 (that's also the definition I use, so I'm lost here too)

Regards,
 Roland

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Jonathan Morton]

> On 28 Mar, 2017, at 14:39, Fred Baker  wrote:
> 
> I'm not convinced I understand the definitions of "work conserving" and "non 
> work conserving" in this context. A "work conserving" scheduling algorithm 
> keeps an interface transmitting as long as there is data in the queue, while 
> a non-work-conserving algorithm reduces the effective rate of the interface 
> by spacing packets out.

In which case the explanation makes even less sense, as PIE doesn’t include a 
shaper.

 - Jonathan Morton

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Fred Baker]

> On Mar 28, 2017, at 1:25 AM, Jonathan Morton  wrote:
> 
> 
>> On 28 Mar, 2017, at 04:04, Rong Pan (ropan)  wrote:
>> 
>>> Q1. What were the reasons for introducing such a frequent suppression of
>>> the PI algorithm (the RFC just says what this code does, not why)?
>> 
>> To be work conserving and avoid any unnecessary drops are the main reasons
>> behind it. 
>> Cisco had a not so successful algorithm before that is not work
>> conserving. So we are extra cautious about being work conserving...
> 
> AQM algorithms are by definition *not* work-conserving, because they can drop 
> packets.  By *definition*.  I therefore think you’re chasing a non-goal here, 
> and you’re going to have to justify it much more clearly if it’s going to 
> make it into an RFC.
> 
> By all means, avoid dropping packets when the queue is actually empty - that 
> is, when you’re delivering the last packet in the queue.  In that case, there 
> is no congestion to signal for.  But there really is no need to have any 
> complex state-switching logic for that.  If your underlying algorithm is 
> sound, it will naturally decay to zero packet drops if the empty-queue 
> condition persists.

I'm not convinced I understand the definitions of "work conserving" and "non 
work conserving" in this context. A "work conserving" scheduling algorithm 
keeps an interface transmitting as long as there is data in the queue, while a 
non-work-conserving algorithm reduces the effective rate of the interface by 
spacing packets out. 
___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Jonathan Morton]

> On 28 Mar, 2017, at 04:04, Rong Pan (ropan)  wrote:
> 
>> Q1. What were the reasons for introducing such a frequent suppression of
>> the PI algorithm (the RFC just says what this code does, not why)?
> 
> To be work conserving and avoid any unnecessary drops are the main reasons
> behind it. 
> Cisco had a not so successful algorithm before that is not work
> conserving. So we are extra cautious about being work conserving...

AQM algorithms are by definition *not* work-conserving, because they can drop 
packets.  By *definition*.  I therefore think you’re chasing a non-goal here, 
and you’re going to have to justify it much more clearly if it’s going to make 
it into an RFC.

By all means, avoid dropping packets when the queue is actually empty - that 
is, when you’re delivering the last packet in the queue.  In that case, there 
is no congestion to signal for.  But there really is no need to have any 
complex state-switching logic for that.  If your underlying algorithm is sound, 
it will naturally decay to zero packet drops if the empty-queue condition 
persists.

 - Jonathan Morton

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

Re: [aqm] Questioning each PIE heuristic

[Rong Pan (ropan)]

Bob,

Sorry for the late reply. I have been traveling. Please see inlineŠ

Rong

On 3/23/17, 5:01 PM, "aqm on behalf of Bob Briscoe"  wrote:

>Rong, Preethi, Greg, Fred, and others involved in PIE,
>
>You may recall that when we wrote PI2 we didn't include any of PIE's
>heuristics. Mostly because PI2 solved the issues they addressed
>intrinsically. But we left some until we had checked their benefit,
>which is what I'm doing now...
>
>My first question is about this heuristic in PIE:
>
>  //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;
>  }
>
>If it tests true, this block doesn't stop the calculation of drop_prob_
>evolving, but it disables it being able to lead to any random packet drop.
>
>I can understand why you want to disable packet drop when the queue is
>no more than 2 packets.
>My question is about the first half of the logical OR. The drop_prob_ <
>20% test will be true under normal non-overloaded conditions. So I have
>just realized that the qdelay_old_ < QDELAY_REF/2 test will turn off
>random drop very often. I would expect this to radically impact the
>behaviour of PIE. It seems to be overriding the PI controller as if you
>are thinking "actually we don't really trust the PI controller to leave
>it to do its thing, so we've overridden it a lot of the time." For
>instance, whenever a single long-running TCP flow with RTT about the
>same as the target delay is saw-toothing, this test will disable random
>drop completely during the lower half of every saw-tooth in the queue.
>Maybe that's OK, but...
>
>Without this test, the PI controller should reduce drop probability as
>the queue sawtooths down anyway. If another flow causes the queue to
>rise rapidly while it is under half the target, the PI controller is
>designed to detect such an increase and translate it into drop. But this
>heuristic suppresses any drop until the queue has exceeded half the
>target.
>
>So my questions are:
>
>Q1. What were the reasons for introducing such a frequent suppression of
>the PI algorithm (the RFC just says what this code does, not why)?


To be work conserving and avoid any unnecessary drops are the main reasons
behind it. 
Cisco had a not so successful algorithm before that is not work
conserving. So we are
extra cautious about being work conserving...


>
>Q2. Why use qdelay_old_ in the test? This seems to drive suppression of
>drop using stale state.

qdelay_old_ is the latency state currently stored. This is for
implementation
Considerations as we don¹t want to calculate qdelay_ on per packet basis.

>
>Q3. Having said that it looks like this heuristic will significantly
>alter PIE's behaviour, in tests under a very wide range of traffic
>conditions, link rates, mixed RTTs, traffic models etc, we have found
>that removing the heuristics makes no measurable difference to PIE's
>performance. So if you added this heuristic for a specific scenario,
>please describe it, so we can test for it.

Again, to be work conserving and avoid drops are our goal. I don¹t
think it would be hurtful to add those safeguards.


>
>
>Cheers
>
>
>Bob
>
>
>
>
>-- 
>
>Bob Briscoehttp://bobbriscoe.net/
>
>___
>aqm mailing list
>aqm@ietf.org
>https://www.ietf.org/mailman/listinfo/aqm

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm

[aqm] Questioning each PIE heuristic

[Bob Briscoe]

Rong, Preethi, Greg, Fred, and others involved in PIE,

You may recall that when we wrote PI2 we didn't include any of PIE's 
heuristics. Mostly because PI2 solved the issues they addressed 
intrinsically. But we left some until we had checked their benefit, 
which is what I'm doing now...


My first question is about this heuristic in PIE:

 //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;
 }

If it tests true, this block doesn't stop the calculation of drop_prob_ 
evolving, but it disables it being able to lead to any random packet drop.


I can understand why you want to disable packet drop when the queue is 
no more than 2 packets.
My question is about the first half of the logical OR. The drop_prob_ < 
20% test will be true under normal non-overloaded conditions. So I have 
just realized that the qdelay_old_ < QDELAY_REF/2 test will turn off 
random drop very often. I would expect this to radically impact the 
behaviour of PIE. It seems to be overriding the PI controller as if you 
are thinking "actually we don't really trust the PI controller to leave 
it to do its thing, so we've overridden it a lot of the time." For 
instance, whenever a single long-running TCP flow with RTT about the 
same as the target delay is saw-toothing, this test will disable random 
drop completely during the lower half of every saw-tooth in the queue. 
Maybe that's OK, but...


Without this test, the PI controller should reduce drop probability as 
the queue sawtooths down anyway. If another flow causes the queue to 
rise rapidly while it is under half the target, the PI controller is 
designed to detect such an increase and translate it into drop. But this 
heuristic suppresses any drop until the queue has exceeded half the target.


So my questions are:

Q1. What were the reasons for introducing such a frequent suppression of 
the PI algorithm (the RFC just says what this code does, not why)?


Q2. Why use qdelay_old_ in the test? This seems to drive suppression of 
drop using stale state.


Q3. Having said that it looks like this heuristic will significantly 
alter PIE's behaviour, in tests under a very wide range of traffic 
conditions, link rates, mixed RTTs, traffic models etc, we have found 
that removing the heuristics makes no measurable difference to PIE's 
performance. So if you added this heuristic for a specific scenario, 
please describe it, so we can test for it.



Cheers


Bob




--

Bob Briscoehttp://bobbriscoe.net/

___
aqm mailing list
aqm@ietf.org
https://www.ietf.org/mailman/listinfo/aqm