[aqm] Control Theoretic Analyses of PI(E) (was Gen-art LC review of draft-ietf-aqm-recommendation-08)

Vishal Misra <misra@cs.columbia.edu> Mon, 26 January 2015 09:29 UTC

Return-Path: <vm2020@columbia.edu>
X-Original-To: aqm@ietfa.amsl.com
Delivered-To: aqm@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8B6DC1A8855 for <aqm@ietfa.amsl.com>; Mon, 26 Jan 2015 01:29:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.609
X-Spam-Level:
X-Spam-Status: No, score=-3.609 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, J_CHICKENPOX_22=0.6, RCVD_IN_DNSWL_MED=-2.3, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
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 L4lJLNUyeOyW for <aqm@ietfa.amsl.com>; Mon, 26 Jan 2015 01:29:22 -0800 (PST)
Received: from buckwheat.cc.columbia.edu (buckwheat.cc.columbia.edu [128.59.72.251]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2CFDE1A8852 for <aqm@ietf.org>; Mon, 26 Jan 2015 01:29:22 -0800 (PST)
Received: from hazelnut (hazelnut.cc.columbia.edu [128.59.213.250]) by buckwheat.cc.columbia.edu (8.13.8/8.13.8) with ESMTP id t0Q9S4QM030682 for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:21 -0500
Received: from hazelnut (localhost.localdomain [127.0.0.1]) by hazelnut (Postfix) with ESMTP id E4E1F38 for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:20 -0500 (EST)
Received: from rambutan.cc.columbia.edu (rambutan.cc.columbia.edu [128.59.29.5]) by hazelnut (Postfix) with ESMTP id CE1E638 for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:20 -0500 (EST)
Received: from mail-qa0-f42.google.com (mail-qa0-f42.google.com [209.85.216.42]) by rambutan.cc.columbia.edu (8.14.4/8.14.3) with ESMTP id t0Q9TKec005941 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <aqm@ietf.org>; Mon, 26 Jan 2015 04:29:20 -0500 (EST)
Received: by mail-qa0-f42.google.com with SMTP id dc16so5928877qab.1 for <aqm@ietf.org>; Mon, 26 Jan 2015 01:29:20 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:content-type:subject:message-id:date:to :mime-version; bh=JfdGHwgUB3mASVl/BMG6UqvWUAGri4iPViu0GBwsh7U=; b=GqX1AhnZtUsqrmcjy7UM3uViJckrVA4ylC2HsPRoiCNwrCJAU3ABfyDB9wVfUu3x9r GDs4ti8lCLDsQqHWji2oZ+H3/ZPQ+nROt4sijP2Lm1KI/PcLbcZ8Ipiz9IHIhJGS62Jz pHNkv41248xoJf0OnJpvVHWj7Mz7aOksC3wLo/349+Htuj0K/rOPS5omeKR1bkYCHWPS k9R9BCdvMuEpFAnQ7Gy6nb7rVE0UwHE8YAOUgXjDGYwHKqYxH4Zuar3uu6nEaUDFJDPl pzgvuSDF3FtbnWC2T95WnwzrJbZr5IIhowmhFqLQTF6BJm9fmDd+3I4t80GRxg4mNBsZ dyWg==
X-Gm-Message-State: ALoCoQnfyn6Nvj7tgH7aax+g1sBNRDNtqYi88HSodMyzyOsRBsNAwbmNpWmWSB10qQTv/dtuW8JmCQNHDvy1URJIAdZaYrvuVDZlGp265ALgqn/lcA0/qRkFMJELIRQmJ5OUmGzu1kq7
X-Received: by 10.229.236.129 with SMTP id kk1mr14741476qcb.20.1422264560270; Mon, 26 Jan 2015 01:29:20 -0800 (PST)
X-Received: by 10.229.236.129 with SMTP id kk1mr14741461qcb.20.1422264560084; Mon, 26 Jan 2015 01:29:20 -0800 (PST)
Received: from ?IPv6:2001:18d8:ffff:16:6d80:4a54:250d:3cf1? ([2001:18d8:ffff:16:6d80:4a54:250d:3cf1]) by mx.google.com with ESMTPSA id r2sm9426061qab.46.2015.01.26.01.29.18 for <aqm@ietf.org> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 26 Jan 2015 01:29:18 -0800 (PST)
From: Vishal Misra <misra@cs.columbia.edu>
Content-Type: multipart/alternative; boundary="Apple-Mail=_9608AFCE-D20E-4F1C-998E-AD569E51EF46"
Message-Id: <039049E6-71E2-4E55-8678-E1E0E472F87B@cs.columbia.edu>
Date: Mon, 26 Jan 2015 04:29:17 -0500
To: aqm@ietf.org
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.4\))
X-Mailer: Apple Mail (2.2070.4)
X-No-Spam-Score: Local
X-Scanned-By: MIMEDefang 2.68 on 128.59.29.5
Archived-At: <http://mailarchive.ietf.org/arch/msg/aqm/hAsLOyo-GeBMHbcQZ4t9QnPXXvU>
Subject: [aqm] Control Theoretic Analyses of PI(E) (was Gen-art LC review of draft-ietf-aqm-recommendation-08)
X-BeenThere: aqm@ietf.org
X-Mailman-Version: 2.1.15
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: Mon, 26 Jan 2015 09:29:24 -0000

On 08/01/15 01:20, Fred Baker (fred) wrote:


>> Yes. I think something like this would be good.   The buffer bloat
>> example is probably an extreme case of things not having AQM at all
>> and interacting badly.  It would maybe be worth mentioning that any
>> AQM  mechanism has also got to work in series with boxes that don't
>> have any active AQM - just tail drop. Ultimately, I would say this
>> is just a matter of control engineering principles:  You are
>> potentially making a  network in which various control algorithms
>> are implemented on different legs/nodes and the combination of
>> transfer functions could possibly be unstable.  Has anybody applied
>> any of the raft of control theoretic methods to these algorithms?
>> I have no idea! 

> Well, PIE basically came out of control theory (a basic equation that
> describes a phase-locked loop), and I believe that Van and Kathy will
> say something similar about Codel. But that’s not a question for this
> paper, it’s a  question for the various algorithmic papers.

Elwyn, 

I would like to expand on a comment that Fred made above.  He is
absolutely correct, about PIE coming out of control theory. PIE is
based on the PI AQM algorithm proposed by us back in 2001
(http://dna-pubs.cs.columbia.edu/citation/paperfile/23/MisraInfocom01-AQM-Controller.pdf <http://dna-pubs.cs.columbia.edu/citation/paperfile/23/MisraInfocom01-AQM-Controller.pdf>),
where we showed the  benefits of using a PI controller to regulate queue
lengths and delays through a formal control theoretic analysis. The PI
algorithm itself came from a fluid model of TCP+AQM that we developed
(http://dna-pubs.cs.columbia.edu/citation/paperfile/27/sigcomm2000.pdf <http://dna-pubs.cs.columbia.edu/citation/paperfile/27/sigcomm2000.pdf>)
and the model is referenced in the IETF draft. 

When we designed PI, we took great care in designing an algorithm that
was amenable to a very simple implementation at line speeds. We could
have gone in the direction of sophisticated (non-linear/optimal)
control algorithms but we instead kept simplicity of implementation front and
center and it is great to see that the standards community has come to
appreciate the work.

The PIE update algorithm is very similar to the original PI algorithm (we
controlled queue length to a reference value whereas PIE controls
delay by dividing the queue length by measured link capacity) - Rong
Pan and the PIE team have done great work in adapting the originial
algorithm for implementation in production environments and all our
original analyses carries through to PIE. I am happy to provide
references to more control theoretic analyses (including ours) that
look at the behavior and stability of the AQM algorithms.

One thing to note though that hasn't changed all these years is if you
look at Section VII.A of our PI paper linked above, the full benefits
of AQM are realized in conjunction with ECN. On a bottlenecked link,
if you reduce delay (by controlling it via a mechanims like PI(E) or
CoDel), unless you have ECN implemented you will end up increasing
loss rates which may not be a good thing.

Lastly, I had contributed pi.cc <http://pi.cc/> to ns2 back in 2001 - a version seems
to have survived all these years if anyone is interested in playing with it:

https://github.com/jridgewell/ns2/blob/master/queue/pi.cc <https://github.com/jridgewell/ns2/blob/master/queue/pi.cc>

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