Subject: [aqm] PIE vs. RED

From: "Bless, Roland (TM)" <[email-masked]>
Date: Thu, 13 Aug 2015 14:28:27 +0200

Hi,

while looking at the PIE presentation
http://www.ietf.org/proceedings/86/slides/slides-86-iccrg-5.pdf,
slide 6 shows that RED is far away from the PIE
queuing delay. However, I'm not sure that this comparison is
really fair if looking at the choice of the parameters.
The buffer limit is set to 2000 packets, which is IMHO too large
for a BDP of 10Gbit/s * 100µs = 125000 bytes. Assuming your average
packet size of 1000 bytes we get 125 packets as buffer size.
Then Min_th = 25 packets and Max_th = 63 packets in contrast
to Min_th=400 packets if you use a buffer for 2000 packets.
For 25 packets you would also get a queuing delay of only
20µs for RED which is then close to the PIE target...
Was there a particular reason for using a 16x larger buffer
than required? Am I missing something here?

Regards,
 Roland

---

From: Jonathan Morton <[email-masked]>
Date: Thu, 13 Aug 2015 20:35:59 +0300

In the real world, the hardware buffer size is rarely matched to the real
BDP.  There are several reasons for this, but a couple of fundamental ones
are:

- BDP varies with RTT, which is in general different for flows
simultaneously using the same link/queue to reach different remote hosts,
and therefore cannot be accurately predicted by a hardware vendor.

- Frequently, the queue size is tuned for the maximum capability of the
device and a pessimistic value for RTT, but the same hardware is more often
used (at least initially) at lower link speeds and thebqueue size is not
adjusted to compensate.  Eg. DOCSIS 2 cable but DOCSIS 3 modem, Ethernet
NIC or switch capable of 1000Mbps but operating at 100 or even 10, 802.11ac
wifi struggling with a marginal 802.11g link...

Thus substantially oversized raw buffers are quite normal.  It is AQM's job
to keep the *actual* queue occupancy low; with a properly functioning AQM,
the effects of an oversized raw queue are nil.

- Jonathan Morton

---

From: Roland Bless <[email-masked]>
Date: Fri, 14 Aug 2015 00:39:22 +0200

Hi Jonathan,

Am 13.08.2015 um 19:35 schrieb Jonathan Morton:
> In the real world, the hardware buffer size is rarely matched to the
> real BDP.  There are several reasons for this, but a couple of
> fundamental ones are:
> 
> simultaneously using the same link/queue to reach different remote
> hosts, and therefore cannot be accurately predicted by a hardware vendor.

Yep, sure. My point was not to promote setting the buffers according to
"the BDP", but rather arguing that one should use comparable target
settings when comparing AQMs, see below...

> device and a pessimistic value for RTT, but the same hardware is more
> often used (at least initially) at lower link speeds and thebqueue size
> is not adjusted to compensate.  Eg. DOCSIS 2 cable but DOCSIS 3 modem,
> Ethernet NIC or switch capable of 1000Mbps but operating at 100 or even
> 10, 802.11ac wifi struggling with a marginal 802.11g link...
> 
> Thus substantially oversized raw buffers are quite normal.  It is AQM's
> job to keep the *actual* queue occupancy low; with a properly
> functioning AQM, the effects of an oversized raw queue are nil.

That's correct. However, IMHO if one compares AQMs one should set/tune
the individual parameters of the AQMs so that they achieve a similar
target value (and not more than an order of magnitude apart).
This is probably relevant for the aqm eval guidelines, but
I'll come up with a detailed review for the draft within the next days...

Regards,
 Roland

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Thu, 13 Aug 2015 23:07:07 +0000

To second Roland's point, the advantage of PIE over RED should not be entirely in the use of delay-based thresholds instead of queue-length ones, otherwise it could be argued that a version of RED with delay-based thresholds is not too hard to design (Wolfram easily did it for his GSP scheme). 

With such a RED version in place, hopefully PIE would still show better performance, so the same superiority should also emerge when the queue-length thresholds of conventional RED are reasonably tuned around the traffic scenario of each experiment.

Andrea

-----Original Message-----
From: aqm [mailto:[email-masked]] On Behalf Of Roland Bless
Sent: Thursday, August 13, 2015 6:39 PM
To: Jonathan Morton
Cc: [email-masked]
Subject: Re: [aqm] PIE vs. RED

Hi Jonathan,

Regards,
 Roland

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

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Thu, 13 Aug 2015 23:15:35 +0000

Delayed-based RED still would associate latency with drop probability:
drop probability will only go up when queueing latency goes up. A higher
drop probability can only be achieved via higher queueing latency.  As we
proved in PIE, the two can be made independent. We can maintain low
latency regardless of traffic intensity.

Rong

On 8/13/15, 4:07 PM, "aqm on behalf of Francini, Andrea (Andrea)"
<[email-masked] on behalf of [email-masked]>
wrote:

>To second Roland's point, the advantage of PIE over RED should not be
>entirely in the use of delay-based thresholds instead of queue-length
>ones, otherwise it could be argued that a version of RED with delay-based
>thresholds is not too hard to design (Wolfram easily did it for his GSP
>scheme). 
>
>With such a RED version in place, hopefully PIE would still show better
>performance, so the same superiority should also emerge when the
>queue-length thresholds of conventional RED are reasonably tuned around
>the traffic scenario of each experiment.
>
>Andrea
>

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Fri, 14 Aug 2015 00:25:33 +0000

> latency regardless of traffic intensity.

That's my point (and I believe also Roland's): In a direct experimental comparison, this good property of PIE would be better emphasized against a configuration of RED where the queue length thresholds are not grossly oversized.

By the way, Global Synchronization Protection (GSP) also drops/marks at a fixed delay level independently of the drop/mark rate that keeps the queue stable. The draft that describes it (https://tools.ietf.org/id/draft-lauten-aqm-gsp-02.txt) is still active. I have seen only marginal comments about GSP. Any specific reason why?

Andrea

---

From: Vishal Misra <[email-masked]>
Date: Fri, 14 Aug 2015 05:54:16 +0530

If you are interested, here's our 2001 paper showing all the limitations of RED and explaining the rationale behind the PI controller. It explained how delay and drop/ECN-mark can be decoupled for AQMs. 

http://dna-pubs.cs.columbia.edu/citation/paperfile/23/MisraInfocom01-AQM-Controller.pdf

The control action of PIE is identical to the PI controller we proposed. 

-Vishal
--
http://www.cs.columbia.edu/~misra/

> On Aug 14, 2015, at 4:45 AM, Rong Pan (ropan) <[email-masked]> wrote:
>

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 14 Aug 2015 01:56:22 +0000

>>That's my point (and I believe also Roland's): In a direct experimental
>>comparison, this good property of PIE would be better emphasized against
>>a >>configuration of RED where the queue length thresholds are not
>>grossly oversized.

In our PIE paper (attached), Figure 8 shows the max latency of RED is
around 100ms (which is very reasonable). PIE controls latency regardless
of traffic intensity. It is the plot that you want.

Thanks,

Rong

On 8/13/15, 5:25 PM, "Francini, Andrea (Andrea)"
<[email-masked]> wrote:

>That's my point (and I believe also Roland's): In a direct experimental
>comparison, this good property of PIE would be better emphasized against
>a configuration of RED where the queue length thresholds are not grossly
>oversized.
>
>By the way, Global Synchronization Protection (GSP) also drops/marks at a
>fixed delay level independently of the drop/mark rate that keeps the
>queue stable. The draft that describes it
>(https://tools.ietf.org/id/draft-lauten-aqm-gsp-02.txt) is still active.
>I have seen only marginal comments about GSP. Any specific reason why?
>
>Andrea 
>
>

---

From: "LAUTENSCHLAEGER, Wolfram (Wolfram)" <[email-masked]>
Date: Fri, 14 Aug 2015 07:01:34 +0000

> drop probability can only be achieved via higher queueing latency.

If following Bob's statements last IETF, this could even be a desirable
feature: Let the queue grow a little bit further to avoid drop probabilities
> 20%, or prevent AQM's attempts to lower CWND below 2 at small RTTs.

It is just that AQM is an extremely multidimensional problem space...

Wolfram

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Fri, 14 Aug 2015 14:44:36 +0000

Hi Rong, 

Thank you for pointing to Figure 8 in your HPSR 2013 paper.

At first glance it exemplifies well the stability vs. variability of the equilibrium point established by the two schemes as the traffic intensity (number of concurrent flows) changes.

However, there are two things I cannot explain after a closer look:

1. At the very beginning the PIE curve shows a delay peak at about 240ms. With 2MB buffer size and 100Mbps rate, the maximum delay I would expect is 160ms (as indeed shown by the RED curve). Do you know where the extra 80ms come from in the PIE case? It really looks like it is a single delay sample, so maybe it is just an issue with the initialization of the variables used in the delay measurements?

2. If I understand correctly the RED configuration used for the plot, min_th is set at 32ms (20% of 2MB) and max_th is set at 128ms (80%). In the plot the RED delay rightly oscillates within this two bounds. However, if I compute the theoretical packet drop rate p using the formula  p = (1.22 * MSS / BW * RTT)^2 in the case with 50 flows (corresponding to the 100s-150s interval in the experiment) I get a drop rate value around 0.5%. Since you used a max_p of 0.1 (or 10%), your delay plot places the drop probability well above 5%. With the theoretical value of 0.5% from the formula the average delay would be only 1/20 of the way between min_th and max_th, or about 37ms, much lower than the almost 100ms of the plot. I ran an ns2 simulation with the parameters of the paper, getting steady-state average and maximum delays of 36ms and 47ms and a drop rate of 0.29% (with PIE I get 20.1ms, 39.4ms, and 0.38%). The only way I can explain the larger RED delay of your plot is with a lower value of max_p (e.g., with max_p = 1% instead of 10% my simulation yields 62.3ms and 71.9ms for the average and maximum delay, with 0.2% average drop rate; the delay is still not at the level of Figure 8, but getting closer). Note that with thresholds tuned around the 20ms delay target of PIE (min_th = 16ms, max_th = 128ms) and max_p = 5%, the simulation yields Avg/Max delay of 17.8ms/29.5ms, pretty much the same as PIE. Overall, can you explain the discrepancy between expected and plotted delay for RED in Figure 8?

Thank you,

Andrea

-----Original Message-----
From: Rong Pan (ropan) [mailto:[email-masked]] 
Sent: Thursday, August 13, 2015 9:56 PM
To: Francini, Andrea (Andrea); Roland Bless; Jonathan Morton
Cc: [email-masked]
Subject: Re: [aqm] PIE vs. RED

Thanks,

Rong

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 14 Aug 2015 18:26:27 +0000

Please see inline.

Rong

On 8/14/15, 7:44 AM, "Francini, Andrea (Andrea)"
<[email-masked]> wrote:

>At first glance it exemplifies well the stability vs. variability of the
>equilibrium point established by the two schemes as the traffic intensity
>(number of concurrent flows) changes.
>
>1. At the very beginning the PIE curve shows a delay peak at about 240ms.
>With 2MB buffer size and 100Mbps rate, the maximum delay I would expect
>is 160ms (as indeed shown by the RED curve). Do you know where the extra
>80ms come from in the PIE case? It really looks like it is a single delay
>sample, so maybe it is just an issue with the initialization of the
>variables used in the delay measurements?

Yes, our queueing delay is calculated so there is an uptick in the
artificial delay at the beginning of the simulation when the draining rate
is just start to be calculated.

>
>2. If I understand correctly the RED configuration used for the plot,
>min_th is set at 32ms (20% of 2MB) and max_th is set at 128ms (80%). In
>the plot the RED delay rightly oscillates within this two bounds.
>However, if I compute the theoretical packet drop rate p using the
>formula  p = (1.22 * MSS / BW * RTT)^2 in the case with 50 flows
>(corresponding to the 100s-150s interval in the experiment) I get a drop
>rate value around 0.5%. Since you used a max_p of 0.1 (or 10%), your
>delay plot places the drop probability well above 5%. With the
>theoretical value of 0.5% from the formula the average delay would be
>only 1/20 of the way between min_th and max_th, or about 37ms, much lower
>than the almost 100ms of the plot. I ran an ns2 simulation with the
>parameters of the paper, getting steady-state average and maximum delays
>of 36ms and 47ms and a drop rate of 0.29% (with PIE I get 20.1ms, 39.4ms,
>and 0.38%). The only way I can explain the larger RED delay of your plot
>is with a lower value of max_p (e.g., with max_p = 1% instead of 10% my
>simulation yields 62.3ms and 71.9ms for the average and maximum delay,
>with 0.2% average drop rate; the delay is still not at the level of
>Figure 8, but getting closer). Note that with thresholds tuned around the
>20ms delay target of PIE (min_th = 16ms, max_th = 128ms) and max_p = 5%,
>the simulation yields Avg/Max delay of 17.8ms/29.5ms, pretty much the
>same as PIE. Overall, can you explain the discrepancy between expected
>and plotted delay for RED in Figure 8?

This is an omission in the paper, which we should specify. This simulation
is done with 10Mbps link with 200KB of buffer. We did size our buffers
according to the BDP. As Jonathan rightly pointed out, "the queue size is
tuned for the maximum capability of the device and a pessimistic value for
RTT². Figure 7 is intended to show that in reality link speed may not get
to the max capacity, and hence well-intended BDP buffer sizing may cause
extreme delays, the time between 50-100s in the plot.

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 14 Aug 2015 18:32:56 +0000

>extreme delays, the time between 50-100s in the plot.

Just to make it clear, Figure 8 is run using 10Mbps link with 200KB
buffer. 
We should clearly specify in the paper, sorry for that.

Figure 7 is run using 100Mbps with 2MB of buffer and in the middle of the
simulation,
the link speed is reduced to 20Mbps to illustrate the case where
well-intended 
buffer sizing might cause delay bloat.

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Fri, 14 Aug 2015 18:41:24 +0000

It has been a while since I last read the paper in detail :-).

In IV A, we specified that unless otherwise specified, the link speed is
10Mbps and buffer size is 200KB.

Thanks,

Rong

On 8/14/15, 11:32 AM, "Rong Pan (ropan)" <[email-masked]> wrote:

>>>>>As
>>>>>we

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Fri, 14 Aug 2015 19:07:48 +0000

Yes, with 10Mbps output rate the results in Figure 8 realign with the expectations. 

Because of the statement at the beginning of IV.A I had first thought that the 10Mbps setup should apply to Figure 8, but then the placement of the paragraph that describes the 100Mbps setup, titled "Performance Evaluation and Comparison", made me conclude that both of the remaining experiments in that section, not just the one in IV.A.5, used that same configuration. 

Thank you for clarifying,

Andrea

-----Original Message-----
From: Rong Pan (ropan) [mailto:[email-masked]] 
Sent: Friday, August 14, 2015 2:41 PM
To: Francini, Andrea (Andrea); Roland Bless; Jonathan Morton
Cc: [email-masked]
Subject: Re: [aqm] PIE vs. RED

Thanks,

Rong