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

Michael Menth <menth@uni-tuebingen.de> Thu, 25 May 2017 07:55 UTC

Return-Path: <menth@uni-tuebingen.de>

X-Original-To: aqm@ietfa.amsl.com

Delivered-To: aqm@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 5D03012E036;
Thu, 25 May 2017 00:55:51 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -4.201

X-Spam-Level:

X-Spam-Status: No, score=-4.201 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.001]
autolearn=ham autolearn_force=no

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id yFsqfRxwRDNv; Thu, 25 May 2017 00:55:48 -0700 (PDT)

Received: from mx04.uni-tuebingen.de (mx04.uni-tuebingen.de [134.2.5.214])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 5F56812DFE0;
Thu, 25 May 2017 00:55:47 -0700 (PDT)

Received: from [192.168.1.101]
(hsi-kbw-5-56-217-255.hsi17.kabel-badenwuerttemberg.de [5.56.217.255])
by mx04.uni-tuebingen.de (Postfix) with ESMTPSA id 033615C420;
Thu, 25 May 2017 09:55:43 +0200 (CEST)

To: Bob Briscoe <ietf@bobbriscoe.net>

References: <9ddba389-e368-9050-3b14-aa235c99fcb8@bobbriscoe.net>
<D4FDD717.2636D%ropan@cisco.com>
<77D4FC66-C99F-49D0-BB73-27A0CEF70F31@gmail.com>
<99a7b737-fc3c-efd0-b6c8-d71a089b7de8@bobbriscoe.net>
<FB0F3D38-63E2-441E-BAB4-2541D7E9FE94@gmail.com>
<471e91b1-c469-3d36-9af1-0411e5661286@uni-tuebingen.de>
<abadc87c-49f2-46e2-ae43-0853ac81e794@bobbriscoe.net>

Cc: "Rong Pan (ropan)" <ropan@cisco.com>, tsvwg IETF list <tsvwg@ietf.org>,
AQM IETF list <aqm@ietf.org>

From: Michael Menth <menth@uni-tuebingen.de>

Message-ID: <da895a48-6b9c-c67f-1f52-d9eb52844ad6@uni-tuebingen.de>

Date: Thu, 25 May 2017 09:55:40 +0200

User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.8.0

MIME-Version: 1.0

In-Reply-To: <abadc87c-49f2-46e2-ae43-0853ac81e794@bobbriscoe.net>

Content-Type: text/plain; charset=utf-8

Content-Transfer-Encoding: 8bit

Archived-At: <https://mailarchive.ietf.org/arch/msg/aqm/mhPjx11zz0EMkFpQrDj0YCahOv4>

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

X-BeenThere: aqm@ietf.org

X-Mailman-Version: 2.1.22

Precedence: list

List-Id: "Discussion list for active queue management and flow isolation."
<aqm.ietf.org>

List-Unsubscribe: <https://www.ietf.org/mailman/options/aqm>,
<mailto:aqm-request@ietf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/aqm/>

List-Post: <mailto:aqm@ietf.org>

List-Help: <mailto:aqm-request@ietf.org?subject=help>

List-Subscribe: <https://www.ietf.org/mailman/listinfo/aqm>,
<mailto:aqm-request@ietf.org?subject=subscribe>

X-List-Received-Date: Thu, 25 May 2017 07:55:51 -0000

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 <http://bobbriscoe.net/pubs.html#piervw_tr>. > 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 <http://bobbriscoe.net/tmp/ewma.pdf>. > > 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 > _____________________ > 1 2.29 > 2 1.73 > 3 1.46 > 4 1.31 > 5 1.22 > 6 1.15 > 7 1.11 > 8 1.08 > 9 1.06 > 10 1.04 > 11 1.03 > 12 1.02 > 13 1.02 > 14 1.01 > 15 1.01 > 16 1.01 > 17 1.01 > 18 1.00 > 19 1.00 > 20 1.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 <ietf@bobbriscoe.net> 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/ > -- 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:menth@uni-tuebingen.de http://kn.inf.uni-tuebingen.de

- [aqm] Questioning each PIE heuristic Bob Briscoe
- Re: [aqm] Questioning each PIE heuristic Rong Pan (ropan)
- Re: [aqm] Questioning each PIE heuristic Jonathan Morton
- Re: [aqm] Questioning each PIE heuristic Fred Baker
- Re: [aqm] Questioning each PIE heuristic Jonathan Morton
- Re: [aqm] Questioning each PIE heuristic Bless, Roland (TM)
- Re: [aqm] Questioning each PIE heuristic Bob Briscoe
- Re: [aqm] Questioning each PIE heuristic Rong Pan (ropan)
- Re: [aqm] Questioning each PIE heuristic Luca Muscariello
- Re: [aqm] Questioning each PIE heuristic Rong Pan (ropan)
- Re: [aqm] Questioning each PIE heuristic Lautenschlaeger, Wolfram (Nokia - DE/Stuttgart)
- Re: [aqm] Questioning each PIE heuristic Bob Briscoe
- Re: [aqm] Questioning each PIE heuristic Rong Pan (ropan)
- Re: [aqm] Questioning each PIE heuristic Bob Briscoe
- Re: [aqm] Questioning each PIE heuristic Jonathan Morton
- Re: [aqm] Questioning each PIE heuristic - moving… Michael Menth
- Re: [aqm] Questioning each PIE heuristic Dave Dolson
- Re: [aqm] Questioning each PIE heuristic - moving… Bob Briscoe
- Re: [aqm] Questioning each PIE heuristic - moving… Michael Menth
- Re: [aqm] Questioning each PIE heuristic - moving… Bob Briscoe
- Re: [aqm] Questioning each PIE heuristic - moving… Rong Pan (ropan)
- Re: [aqm] Questioning each PIE heuristic - moving… Rong Pan (ropan)
- Re: [aqm] Questioning each PIE heuristic - moving… Bob Briscoe