Re: [aqm] AQM schemes: Queue length vs. delay based

Preethi Natarajan <preethi.cis@gmail.com> Fri, 08 November 2013 20:00 UTC

Return-Path: <preethi.cis@gmail.com>
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 A01C021E81F3 for <aqm@ietfa.amsl.com>; Fri, 8 Nov 2013 12:00:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.975
X-Spam-Level:
X-Spam-Status: No, score=-0.975 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=1.396, SARE_SUB_OBFU_Q1=0.227]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kTrDTI0nLbcb for <aqm@ietfa.amsl.com>; Fri, 8 Nov 2013 12:00:31 -0800 (PST)
Received: from mail-pd0-x22a.google.com (mail-pd0-x22a.google.com [IPv6:2607:f8b0:400e:c02::22a]) by ietfa.amsl.com (Postfix) with ESMTP id BFB3721E8179 for <aqm@ietf.org>; Fri, 8 Nov 2013 12:00:31 -0800 (PST)
Received: by mail-pd0-f170.google.com with SMTP id v10so2601153pde.29 for <aqm@ietf.org>; Fri, 08 Nov 2013 12:00:14 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=user-agent:date:subject:from:to:cc:message-id:thread-topic :in-reply-to:mime-version:content-type; bh=jpI6ittpC462oD0RVZ29EbAiK9l2v0ti34zbDqbROQA=; b=hpSWvtcFccJ8zdZVh3o/kisPPuxxX1XrjQf/YVLhsuLI6o+xeMVeJXsP3gNynRK1UQ YUc28JRIyG7xetciyILE/cQn2Edy5wf5xThzXTv2xVCFXeMZYCBwVMQL9rNVl81W0WR6 Ammt1Lr+jXEk9qDQB6dILXt6fTQRUbnV3pZmaMM4bYAEJqfGUKqcCwFJI2hMNP/EFUkG VnwOlGcgVgGMUJZMukWFEpa/tmPothFgdxnYvqlELtF6h6bG+S+Eh2gOya0FdlaHC5EW yTUEDqWLMTS7ySzQ4DJtCxuuFF5uQopMawkJILUxHB3tzkUQKSTR2KcU/fOTtUPzQJG5 m0KQ==
X-Received: by 10.66.121.68 with SMTP id li4mr17294573pab.33.1383940814407; Fri, 08 Nov 2013 12:00:14 -0800 (PST)
Received: from [10.33.22.215] (128-107-239-235.cisco.com. [128.107.239.235]) by mx.google.com with ESMTPSA id lm2sm16397912pab.2.2013.11.08.12.00.13 for <multiple recipients> (version=TLSv1 cipher=RC4-SHA bits=128/128); Fri, 08 Nov 2013 12:00:13 -0800 (PST)
User-Agent: Microsoft-MacOutlook/14.2.1.120420
Date: Fri, 08 Nov 2013 12:00:09 -0700
From: Preethi Natarajan <preethi.cis@gmail.com>
To: Naeem Khademi <naeem.khademi@gmail.com>
Message-ID: <CEA27FCC.4AF01%prenatar@cisco.com>
Thread-Topic: [aqm] AQM schemes: Queue length vs. delay based
In-Reply-To: <CAEjQQ5UdW38nAm4WSO8CXL5B8Eo5weu65L17uYVzZJvzzZU3fw@mail.gmail.com>
Mime-version: 1.0
Content-type: multipart/alternative; boundary="B_3466756813_10807102"
Cc: "aqm@ietf.org" <aqm@ietf.org>
Subject: Re: [aqm] AQM schemes: Queue length vs. delay based
X-BeenThere: aqm@ietf.org
X-Mailman-Version: 2.1.12
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: <http://www.ietf.org/mail-archive/web/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: Fri, 08 Nov 2013 20:00:55 -0000

Hi Naeem, all:

Please see detailed responses inline.

From:  Naeem Khademi <naeem.khademi@gmail.com>
Date:  Thursday, November 7, 2013 10:50 PM
To:  Preethi Natarajan <preethi.cis@gmail.com>
Cc:  "aqm@ietf.org" <aqm@ietf.org>
Subject:  Re: [aqm] AQM schemes: Queue length vs. delay based

> I fully agree with the need to have AQMs that use "queuing delay" as metric
> and not "queue length" and this is already a bonus for algorithms that use
> this metric (e.g. PIE). However, I believe that one can possibly modify RED or
> its derivatives (e.g. Adaptive RED) to set their thresholds based on "queuing
> delay" as well (although such algorithms don't exists yet as of now). Whether
> the outcome of these modifications to xRED algorithms would make them better
> than PIE and/or CoDel is another subject and I'm not going to speculate on
> that here. 

Of course. Our initial discussions considered a latency based RED
derivative. We later decided to focus on a proportional integral based
control law instead of RED (see below for more).

> 
> One specific issue with PIE is that it tries to *estimate* the queuing delay
> over a certain time interval (t_update) and still somehow uses the "queue
> length" and departure rate (over the interval) to estimate the queuing delay.
> So saying that PIE uses the queueing delay instead of queue length may not be
> 100% accurate. 

Any latency based scheme requires the queueing delay to work with. The fact
of the matter is, the queueing delay is not directly available on platforms.
Some platforms can afford timestamping to figure the queuing delay but not
all platforms  can. In fact, over the past months we've come to realize that
a latency based scheme is actually two different items at work ‹ (i) the
control law and (ii) the mechanism which provides the queueing delay to this
control law. This would be true for any latency based scheme, be it, PIE,
CoDEL, FQ_CoDEL or xRED. Based on this observation, we plan to separate out
the two components in PIE, possibly in the next version of the draft. The
objective being that (ii) would vary with the platform and it could be
direct input (if platform maintains it), timestamp-based (like in CoDEL
derivatives), dequeue-based, or even others that we are exploring at the
moment. 

The current version of the PIE draft fully acknowledges the fact that what
PIE acquires with the dequee-based rate estimation is only an estimate of
the queuing delay and not the actual (Section 4.2 of v00). The larger point
for discussion here is a latency based AQM that uses queuing delay instead
of queue length. 


> 
> Moreover, in a varying bandwidth scenario, depending on how often the
> bandwidth changes and at what granularity, the derived "estimated queuing
> delay" by PIE might be an outdated information e.g. it shows how the channel
> has been (in term of delay) in the last 30ms and now how it is now! if I'm not
> mistaken that has been somehow resolved in DOCSIS 3.1 by coupling PIE's
> departure rate to the actual link layer rate.

We've experimented with timestamp-based delay inputs to PIE. We have not
seen any noticeable difference between the dequeue-based scheme and the
timestamp-based for all the scenarios Rong has presented at IETF thus far.
Even in extreme bandwidth changing conditions dequeue-based scheme can adapt
within few tupdate cycles. Again, PIE is flexible in its delay input
mechanism and will go with whatever is the best possible option available on
the platform. I don't think any latency based scheme can get better than
that :). 

> 
> In overall, while there are of course significant improvements made in PIE's
> (and (FQ)-CoDel's) design, there are probably still lessons to be learned from
> xRED family (check http://urn.nb.no/URN:NBN:no-38868 to see some examples).
> Throwing away all the knowledge and improvement gained from RED-like AQMs,
> CHoKe, etc and coming up with brand-new AQMs without (experimentally)
> comparing them to the gallery of existing ones wouldn't be great!

Our initial discussions considered more than just the RED varieties. As
we've mentioned before, PIE is based on the concept of proportional integral
(PI). PI is not something we discovered. PI controller has been around for
long and you can refer to Hollot, Towsley et. al's paper from a decade ago
for more information on PI based AQM scheme. We believe PI's strong
theoretical stability is valuable for diverse deployment conditions and
incorporated PI into our PIE design. We did our own set of theoretical
analysis for PIE and we were proved right. You can find more details about
that in our HPSR paper (http://www.ieee-hpsr.org/2013/)

Thanks,
Preethi