Re: [aqm] the cisco pie patent and IETF IPR filing

Vishal Misra <misra@cs.columbia.edu> Fri, 06 March 2015 19:46 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 C1FD11A6F3A for <aqm@ietfa.amsl.com>; Fri, 6 Mar 2015 11:46:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.21
X-Spam-Level:
X-Spam-Status: No, score=-4.21 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, 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 bDw8Evr1pUb9 for <aqm@ietfa.amsl.com>; Fri, 6 Mar 2015 11:46: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 3CEDC1A6EED for <aqm@ietf.org>; Fri, 6 Mar 2015 11:46: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 t26Jh5Gr025374 for <aqm@ietf.org>; Fri, 6 Mar 2015 14:46:20 -0500
Received: from hazelnut (localhost.localdomain [127.0.0.1]) by hazelnut (Postfix) with ESMTP id CF5576D for <aqm@ietf.org>; Fri, 6 Mar 2015 14:46:20 -0500 (EST)
Received: from salak.cc.columbia.edu (salak.cc.columbia.edu [128.59.29.6]) by hazelnut (Postfix) with ESMTP id B072A7E for <aqm@ietf.org>; Fri, 6 Mar 2015 14:46:20 -0500 (EST)
Received: from mail-qc0-f172.google.com (mail-qc0-f172.google.com [209.85.216.172]) by salak.cc.columbia.edu (8.14.4/8.14.3) with ESMTP id t26JkKwL008079 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NOT) for <aqm@ietf.org>; Fri, 6 Mar 2015 14:46:20 -0500 (EST)
Received: by qcxn11 with SMTP id n11so25085978qcx.11 for <aqm@ietf.org>; Fri, 06 Mar 2015 11:46: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:content-type:mime-version:subject:from :in-reply-to:date:cc:message-id:references:to; bh=w0F5gE+PGgps4151GZUDBLXXSYJeEP69vmSdtbWCktk=; b=U0woCyY9Gt/P26MQAFWDiNN7Umf0ZYCAkp1ToKE6fH+uMT0XwPMzWtwRwj5ZKwIIwN nnRLb/WAOTmB5XyLbF4AGggux9qAf2FuTZmEAhxvH7jqPL4wDAT8d54+uYJbVzKBhw2w ITRlCWKbDi77m847TMZDqhAkCYotFWR/6oORwkuLqoDLyfnB1MdbXV1FVC237pqTsJjr ORyOUwfIHwx8m+nuA0p5sOu/toVjl7nbPrmIKaw3OV/xfZHKZb2Ti9zfXldLEORPlDs6 MIF6MqYg/US91Rjf6f5eVO6OvFl1oB+GINVImBlXCquvTV1iUQu9cSdHTgT8qe5ZE+AU ZZoA==
X-Gm-Message-State: ALoCoQk0wkmuSPqVFL9D1ENA6l1hGKdesM9nzXnbGTTKOJ7Le5v0USaH+nSgLAYJvy2xnlfzCorOd1KDCG3GE+VKe7ka0qNfK9dL/2thw2FDEvwoz/hHxC1Q+3eHoYUBF6iJqqFgUBbl
X-Received: by 10.229.80.3 with SMTP id r3mr21867385qck.23.1425671180311; Fri, 06 Mar 2015 11:46:20 -0800 (PST)
X-Received: by 10.229.80.3 with SMTP id r3mr21867369qck.23.1425671180126; Fri, 06 Mar 2015 11:46:20 -0800 (PST)
Received: from ?IPv6:2001:18d8:ffff:16:c878:1c08:7c77:6b10? ([2001:18d8:ffff:16:c878:1c08:7c77:6b10]) by mx.google.com with ESMTPSA id l37sm4911963qkh.9.2015.03.06.11.46.17 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 06 Mar 2015 11:46:18 -0800 (PST)
Content-Type: multipart/alternative; boundary="Apple-Mail=_E3255D03-82D0-4BF7-82E4-907E93507E79"
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2087\))
From: Vishal Misra <misra@cs.columbia.edu>
In-Reply-To: <CAA93jw4p-jYt_XLN+NQbAGyLWVAHuRWcVab0CpJBkmpE5QoTBA@mail.gmail.com>
Date: Fri, 6 Mar 2015 14:46:14 -0500
Message-Id: <FF2FCC82-97AB-4917-A33E-71357D7DE8BB@cs.columbia.edu>
References: <CAA93jw4zZXGn_z2_dBBMsKN-XdwP88Wt-ChvfWJgCtp=J+i0rg@mail.gmail.com> <473265656416337848@unknownmsgid> <CAA93jw4p-jYt_XLN+NQbAGyLWVAHuRWcVab0CpJBkmpE5QoTBA@mail.gmail.com>
To: Dave Taht <dave.taht@gmail.com>
X-Mailer: Apple Mail (2.2087)
X-No-Spam-Score: Local
X-Scanned-By: MIMEDefang 2.68 on 128.59.29.6
Archived-At: <http://mailarchive.ietf.org/arch/msg/aqm/ytsAXfO2N9Cp_S34vWd3hfW_uLM>
Cc: "aqm@ietf.org" <aqm@ietf.org>, bloat <bloat@lists.bufferbloat.net>
Subject: Re: [aqm] the cisco pie patent and IETF IPR filing
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: Fri, 06 Mar 2015 19:46:24 -0000

Hi Dave,

> On Mar 5, 2015, at 8:58 AM, Dave Taht <dave.taht@gmail.com> wrote:
> 
> I let the data take me where it may. I (not) always have, but reformed
> about 15 years ago. [1] I hope that you and your students also,  do
> some experiments on the successors to PI and RED and DRR - and also
> follow the data where-ever it leads you.



In 2003 we had published a paper on STPI (Self-Tuning PI). The self-tuning design accounted for variations in link capacity, presence of cross traffic (i.e. unregulated UDP flows) and variations in the number of flows being controlled. We also proved the (local, exponential) stability of our self-tuning mechanism.

The paper is available at http://dna-pubs.cs.columbia.edu/citation/paperfile/79/GLOBECOM_2003_STAQM.pdf

This was an evolution over our first PI design where we introduced the concept of linear controllers for AQM.

BTW STPI is not PIE, the differences as I see them are

(1) STPI explicitly accounts for cross traffic.
(2) STPI tunes the parameters continuously, over the entire range of loss (marking) rates unlike PIE which seems to be doing it for 3 specific values chosen ahead of time.
(3) The stability of the adaptive mechanism of STPI was rigorously proven in a linearized setting. 
(4) The tradeoff between stability and responsiveness for the time constant of adaptation was made explicit.
(5) STPI does not, as the author of PIE stated recently "control the offset to the reference level and second moment of the latency independently”. STPI simply controls the latency, I don’t know of any way to control the second moment of any reference signal by a linear controller like PI(E), but then I do not know the details of PIE. It was a very deliberate design choice by us to introduce a linear controller like PI for AQM because of ease of implementation. We could’ve gone the route of optimal and/or non-linear controllers but we didn’t.

As a side note, we also designed a self-tuning version of RED that we called STRED (different from ARED) but RED suffers from some fundamental limitations so exploring that won’t be of interest.

So I am getting STPI and PI implemented as part of cerowrt and will release the code for anyone to play with/evaluate.

More than anything, it is the increased deployment of ECN that has revived an interest in AQM for me.

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