Re: [iccrg] Pareto frontier

Keith Winstein <keithw@cs.stanford.edu> Wed, 08 January 2020 15:41 UTC

Return-Path: <keithw@cs.stanford.edu>
X-Original-To: iccrg@ietfa.amsl.com
Delivered-To: iccrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C137D120180 for <iccrg@ietfa.amsl.com>; Wed, 8 Jan 2020 07:41:25 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.218
X-Spam-Level:
X-Spam-Status: No, score=-4.218 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=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 HV1Q7mX_axSS for <iccrg@ietfa.amsl.com>; Wed, 8 Jan 2020 07:41:22 -0800 (PST)
Received: from smtp1.cs.Stanford.EDU (smtp1.cs.stanford.edu [171.64.64.25]) (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 1E60112001A for <iccrg@irtf.org>; Wed, 8 Jan 2020 07:41:22 -0800 (PST)
Received: from mail-il1-f181.google.com ([209.85.166.181]:40999) by smtp1.cs.Stanford.EDU with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (Exim 4.92.3) (envelope-from <keithw@cs.stanford.edu>) id 1ipDSS-00066Q-7M for iccrg@irtf.org; Wed, 08 Jan 2020 07:41:21 -0800
Received: by mail-il1-f181.google.com with SMTP id f10so3011572ils.8 for <iccrg@irtf.org>; Wed, 08 Jan 2020 07:41:20 -0800 (PST)
X-Gm-Message-State: APjAAAV0lnNozK5tePxkXcmFAhmG8tgoEvYJS4DHVGduYxf8RDir0CQi EKzFAIEMsKO8b8LoE3o0bxaXEud0MT0LLQcizQ==
X-Google-Smtp-Source: APXvYqw10+MtDfYyGyAXtcU19HqV2h6kJjBWsIOZlRS7HGzbYkjGBeVCgCFVcjKSybnJxOTgiZwyuCE3bbH5Cg54TLc=
X-Received: by 2002:a92:c647:: with SMTP id 7mr4491009ill.28.1578498079727; Wed, 08 Jan 2020 07:41:19 -0800 (PST)
MIME-Version: 1.0
References: <510CB937-5E3B-4100-99E7-4F9AA3B81FEC@ifi.uio.no>
In-Reply-To: <510CB937-5E3B-4100-99E7-4F9AA3B81FEC@ifi.uio.no>
From: Keith Winstein <keithw@cs.stanford.edu>
Date: Wed, 08 Jan 2020 07:40:43 -0800
X-Gmail-Original-Message-ID: <CAMzhQmNRZN6+uzqm48rCmg78QDiomAJYDXVdL9aTiVedC35-yg@mail.gmail.com>
Message-ID: <CAMzhQmNRZN6+uzqm48rCmg78QDiomAJYDXVdL9aTiVedC35-yg@mail.gmail.com>
To: Michael Welzl <michawe@ifi.uio.no>
Cc: iccrg IRTF list <iccrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000052276a059ba2b9ae"
X-Scan-Signature: 55257a1a0ec20502294a0e86bc6a08bd
Archived-At: <https://mailarchive.ietf.org/arch/msg/iccrg/PomCadAfil4jmgerq-zzScRzhRY>
Subject: Re: [iccrg] Pareto frontier
X-BeenThere: iccrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Discussions of Internet Congestion Control Research Group \(ICCRG\)" <iccrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/iccrg>, <mailto:iccrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/iccrg/>
List-Post: <mailto:iccrg@irtf.org>
List-Help: <mailto:iccrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/iccrg>, <mailto:iccrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 08 Jan 2020 15:41:26 -0000

Hi Michael,

Formally speaking, given a set of feasible allocations (each the result of
some strategy), the Pareto frontier is the subset of allocations that
aren't strictly dominated by any other allocation. It's fashionable to show
this by drawing the convex hull through the frontier -- see, e.g., the
plots in the Wikipedia article on "Pareto efficiency." But the frontier is
really the set of points, not the line drawn to connect them.

It's okay that the set considered is finite -- the Pareto frontier does not
have to be taken only after evaluating the full (typically infinite) set of
all possible strategies. (Of course it's important to compare with the
right prior work or alternative strategies, but that's just true any time
you want to have a comparative evaluation -- it doesn't come from the
definition of Pareto frontier.) And in congestion control, it's not like we
usually have access to a tight upper bound. If you look at, e.g., Figure 7
of https://cs.nyu.edu/~anirudh/contest-ccr.pdf (3,000 different
congestion-control schemes run across the same time-varying emulated
network path), there's a substantial gap between the apparent
frontier-of-schemes-tested and the best known upper bound ("Omniscient").
Maybe there exists some scheme that comes very close to "Omniscient" and
would remove most other points from the frontier, or maybe there isn't --
one can't know this just by plotting a frontier of a finite set of
evaluated strategies.

Also, maybe the schemes on the frontier will still be on the frontier when
evaluated over a different emulated network, or over a real-world Internet
path, or maybe they won't -- one won't necessarily know this either. (Our
Pantheon paper,
https://pantheon.stanford.edu/static/pantheon/documents/pantheon-paper.pdf,
tries to show how challenging it can be to match the real-world results of
a variety of congestion-control schemes in an emulator.)

I assume when somebody says their scheme sits "outside the Pareto
frontier", they mean that it strictly dominated some of the schemes that
*had been* on the Pareto frontier before it was added to the set of
available schemes. One does have to be cautious about how far you interpret
these snapshot results -- some of my own results for schemes that strictly
dominated other schemes have not held up when you run the experiment with
different network paths, buffering regimes, workloads, figures of merit
(dimensions of the "allocation"), etc. I talked about this a bit here:
https://youtu.be/pzPy6VUuY-k?t=2474 .

But these problems belong, I think, more to the realm of computer
networking and the hardness of reasoning about how to make resource
allocation decisions under uncertainty in a decentralized manner, than in
the concept of Pareto efficiency.

Sincerely,
Keith

On Wed, Jan 8, 2020 at 5:53 AM Michael Welzl <michawe@ifi.uio.no> wrote:

> Hi,
>
> Recently, it has become common in some congestion control papers, when
> showing plots with various congestion control mechanisms and a "better"
> arrow, to also draw a line through the presumably best mechanisms and call
> it a Pareto frontier.
>
> I find it a bit of a stretch to just call this line a Pareto frontier - it
> MAY be one, but that's not proven, so I'm not sure this is a correct thing
> to state, strictly speaking. Anyway, I've recently seen cases where
> mechanism XY beats the others, as shown in the diagram, where it "sits
> comfortably outside the Pareto frontier".
>
> Now, either I totally misunderstand something, or I never got the idea of
> Pareto efficiency, OR such a statement is utter nonsense.
> (because being better than the mechanisms on the Pareto frontier simply
> means that this line is indeed *NOT* the Pareto frontier, and it was wrong
> to call it that in the first place).
>
> Can someone enlighten me please?
>
> Cheers,
> Michael
>
> _______________________________________________
> iccrg mailing list
> iccrg@irtf.org
> https://www.irtf.org/mailman/listinfo/iccrg
>