Subject: [tsvwg] Questioning each PIE heuristic

From: Bob Briscoe <[email-masked]>
Date: Fri, 24 Mar 2017 00:01:01 +0000

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/

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Tue, 28 Mar 2017 01:04:55 +0000

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" <[email-masked]

>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

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.

>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.

>_______________________________________________
>aqm mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/aqm

---

From: Jonathan Morton <[email-masked]>
Date: Tue, 28 Mar 2017 09:25:22 +0300

> On 28 Mar, 2017, at 04:04, Rong Pan (ropan) <[email-masked]> wrote:
> 
> 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

---

From: Fred Baker <[email-masked]>
Date: Tue, 28 Mar 2017 06:39:05 -0500

> On Mar 28, 2017, at 1:25 AM, Jonathan Morton <[email-masked]> 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.

---

From: Jonathan Morton <[email-masked]>
Date: Tue, 28 Mar 2017 14:46:48 +0300

> On 28 Mar, 2017, at 14:39, Fred Baker <[email-masked]> wrote:
> 

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

 - Jonathan Morton

---

From: "Bless, Roland (TM)" <[email-masked]>
Date: Tue, 28 Mar 2017 13:48:42 +0200

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

---

From: Luca Muscariello <[email-masked]>
Date: Tue, 28 Mar 2017 14:48:52 +0200

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

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Tue, 28 Mar 2017 14:17:19 +0000

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 <[email-masked]<mailto:[email-masked]>>
Date: Tuesday, March 28, 2017 at 8:48 AM
To: "Bless, Roland (TM)" <[email-masked]<mailto:[email-masked]>>
Cc: Fred Baker <[email-masked]<mailto:[email-masked]>>, Jonathan Morton <[email-masked]<mailto:[email-masked]>>, tsvwg IETF list <[email-masked]<mailto:[email-masked]>>, Bob Briscoe <[email-masked]<mailto:[email-masked]>>, "De Schepper, Koen (Koen)" <[email-masked]<mailto:[email-masked]>>, Rong Pan <[email-masked]<mailto:[email-masked]>>, Greg White <[email-masked]<mailto:[email-masked]>>, AQM IETF list <[email-masked]<mailto:[email-masked]>>, Preethi Natarajan <[email-masked]<mailto:[email-masked]>>
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) <[email-masked]<mailto:[email-masked]>> wrote:
Hi,

Regards,
 Roland

_______________________________________________
aqm mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/aqm

---

From: "Lautenschlaeger, Wolfram (Nokia - DE/Stuttgart)" <[email-masked]>
Date: Wed, 29 Mar 2017 06:30:00 +0000

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:[email-masked]] On Behalf Of Rong Pan (ropan)
Sent: Dienstag, 28. März 2017 16:17
To: Luca Muscariello <[email-masked]>; Bless, Roland (TM) <[email-masked]>
Cc: tsvwg IETF list <[email-masked]>; Fred Baker <[email-masked]>; Bob Briscoe <[email-masked]>; De Schepper, Koen (Nokia - BE/Antwerp) <[email-masked]>; Greg White <[email-masked]>; Jonathan Morton <[email-masked]>; AQM IETF list <[email-masked]>; Preethi Natarajan <[email-masked]>
Subject: Re: [aqm] Questioning each PIE heuristic

Rong

Luca

Regards,
 Roland

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Wed, 29 Mar 2017 17:58:08 +0000

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)" <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, March 29, 2017 at 2:30 AM
To: Rong Pan <[email-masked]<mailto:[email-masked]>>, Luca Muscariello <[email-masked]<mailto:[email-masked]>>, "Bless, Roland (TM)" <[email-masked]<mailto:[email-masked]>>
Cc: tsvwg IETF list <[email-masked]<mailto:[email-masked]>>, Fred Baker <[email-masked]<mailto:[email-masked]>>, Bob Briscoe <[email-masked]<mailto:[email-masked]>>, "De Schepper, Koen (Nokia - BE/Antwerp)" <[email-masked]<mailto:[email-masked]>>, Greg White <[email-masked]<mailto:[email-masked]>>, Jonathan Morton <[email-masked]<mailto:[email-masked]>>, AQM IETF list <[email-masked]<mailto:[email-masked]>>, Preethi Natarajan <[email-masked]<mailto:[email-masked]>>
Subject: RE: [aqm] Questioning each PIE heuristic

Wolfram

From: aqm [mailto:[email-masked]] On Behalf Of Rong Pan (ropan)
Sent: Dienstag, 28. März 2017 16:17
To: Luca Muscariello <[email-masked]<mailto:[email-masked]>>; Bless, Roland (TM) <[email-masked]<mailto:[email-masked]>>
Cc: tsvwg IETF list <[email-masked]<mailto:[email-masked]>>; Fred Baker <[email-masked]<mailto:[email-masked]>>; Bob Briscoe <[email-masked]<mailto:[email-masked]>>; De Schepper, Koen (Nokia - BE/Antwerp) <[email-masked]<mailto:[email-masked]>>; Greg White <[email-masked]<mailto:[email-masked]>>; Jonathan Morton <[email-masked]<mailto:[email-masked]>>; AQM IETF list <[email-masked]<mailto:[email-masked]>>; Preethi Natarajan <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] Questioning each PIE heuristic

Rong

Luca

Regards,
 Roland

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 29 Mar 2017 19:47:39 +0100

Wolfram,

Just to explain some context. The PIE algorithm determines a dropping 
probability at sample times (default 16ms), then continues to drop with 
that probability until the next sample. If the queue had been large then 
traffic ends, while the queue is draining towards zero it is still 
dropping at the last calculated probability. So the PIE code includes a 
heuristic that suppresses any drop if the queue is less than half the 
target. Nonetheless, the PIE algo continues to calculate what the drop 
probability /would/ be if a queue of more than half the target appeared 
again.

This is so that the drop probability reflects a longer running measure 
of the load as well as the instantaneous queue.

Bob

On 29/03/17 18:58, Rong Pan (ropan) wrote:
> 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)" 
> <[email-masked] 
> <mailto:[email-masked]>>
> To: Rong Pan <[email-masked] <mailto:[email-masked]>>, Luca 
> Muscariello <[email-masked] 
> <mailto:[email-masked]>>, "Bless, Roland (TM)" 
> <[email-masked] <mailto:[email-masked]>>
> Cc: tsvwg IETF list <[email-masked] <mailto:[email-masked]>>, Fred 
> Baker <[email-masked] <mailto:[email-masked]>>, 
> Bob Briscoe <[email-masked] <mailto:[email-masked]>>, "De 
> Schepper, Koen (Nokia - BE/Antwerp)" 
> <[email-masked] 
> <mailto:[email-masked]>>, Greg White 
> <[email-masked] <mailto:[email-masked]>>, Jonathan 
> Morton <[email-masked] <mailto:[email-masked]>>, AQM 
> IETF list <[email-masked] <mailto:[email-masked]>>, Preethi Natarajan 
> <[email-masked] <mailto:[email-masked]>>
> 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:[email-masked]] *On Behalf Of *Rong Pan (ropan)
> *Sent:* Dienstag, 28. März 2017 16:17
> *To:* Luca Muscariello <[email-masked] 
> <mailto:[email-masked]>>; Bless, Roland (TM) 
> <[email-masked] <mailto:[email-masked]>>
> *Cc:* tsvwg IETF list <[email-masked] <mailto:[email-masked]>>; Fred 
> Baker <[email-masked] <mailto:[email-masked]>>; 
> Bob Briscoe <[email-masked] <mailto:[email-masked]>>; De 
> Schepper, Koen (Nokia - BE/Antwerp) 
> <[email-masked] 
> <mailto:[email-masked]>>; Greg White 
> <[email-masked] <mailto:[email-masked]>>; Jonathan 
> Morton <[email-masked] <mailto:[email-masked]>>; AQM 
> IETF list <[email-masked] <mailto:[email-masked]>>; Preethi Natarajan 
> <[email-masked] <mailto:[email-masked]>>
> *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 <[email-masked] 
> <mailto:[email-masked]>>
> *Date: *Tuesday, March 28, 2017 at 8:48 AM
> *To: *"Bless, Roland (TM)" <[email-masked] 
> <mailto:[email-masked]>>
> *Cc: *Fred Baker <[email-masked] 
> <mailto:[email-masked]>>, Jonathan Morton 
> <[email-masked] <mailto:[email-masked]>>, tsvwg IETF 
> list <[email-masked] <mailto:[email-masked]>>, Bob Briscoe 
> <[email-masked] <mailto:[email-masked]>>, "De Schepper, Koen 
> (Koen)" <[email-masked] 
> <mailto:[email-masked]>>, Rong Pan <[email-masked] 
> <mailto:[email-masked]>>, Greg White <[email-masked] 
> <mailto:[email-masked]>>, AQM IETF list <[email-masked] 
> <mailto:[email-masked]>>, Preethi Natarajan <[email-masked] 
> <mailto:[email-masked]>>
> *Subject: *Re: [aqm] Questioning each PIE heuristic
>
> On Tue, Mar 28, 2017 at 1:48 PM, Bless, Roland (TM) 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Hi,
>
>     [email-masked] <mailto:[email-masked]>

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 29 Mar 2017 20:47:11 +0100

Wolfram,

Bob

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 30 Mar 2017 08:46:44 +0100

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

---

From: Jonathan Morton <[email-masked]>
Date: Thu, 30 Mar 2017 12:08:29 +0300

> On 30 Mar, 2017, at 10:46, Bob Briscoe <[email-masked]> 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

---

From: Michael Menth <[email-masked]>
Date: Thu, 30 Mar 2017 11:57:10 +0200

Hi all,

> 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 t…
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

-- 
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:[email-masked]
http://kn.inf.uni-tuebingen.de

---

From: Dave Dolson <[email-masked]>
Date: Thu, 30 Mar 2017 12:06:48 +0000

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:[email-masked]] 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; [email-masked]
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