Re: Is a faithful HTTP/2 response scheduler necessarily O(n) in the worst case?

Patrick McManus <pmcmanus@mozilla.com> Tue, 24 January 2017 23:23 UTC

Return-Path: <ietf-http-wg-request+bounce-httpbisa-archive-bis2juki=lists.ie@listhub.w3.org>
X-Original-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Delivered-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B3DDD129567 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Tue, 24 Jan 2017 15:23:52 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -10.119
X-Spam-Level:
X-Spam-Status: No, score=-10.119 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RP_MATCHES_RCVD=-3.199, SPF_HELO_PASS=-0.001, SPF_PASS=-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 OTF17elxsgJ5 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Tue, 24 Jan 2017 15:23:51 -0800 (PST)
Received: from frink.w3.org (frink.w3.org [128.30.52.56]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 16A34129566 for <httpbisa-archive-bis2Juki@lists.ietf.org>; Tue, 24 Jan 2017 15:23:51 -0800 (PST)
Received: from lists by frink.w3.org with local (Exim 4.80) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1cWAP1-0007Jt-8o for ietf-http-wg-dist@listhub.w3.org; Tue, 24 Jan 2017 23:21:27 +0000
Resent-Date: Tue, 24 Jan 2017 23:21:27 +0000
Resent-Message-Id: <E1cWAP1-0007Jt-8o@frink.w3.org>
Received: from titan.w3.org ([128.30.52.76]) by frink.w3.org with esmtps (TLS1.2:RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <pmcmanus@mozilla.com>) id 1cWAOw-0007Io-9w for ietf-http-wg@listhub.w3.org; Tue, 24 Jan 2017 23:21:22 +0000
Received: from www.ducksong.com ([192.155.95.102] helo=linode64.ducksong.com) by titan.w3.org with esmtp (Exim 4.84_2) (envelope-from <pmcmanus@mozilla.com>) id 1cWAOq-0007gm-4A for ietf-http-wg@w3.org; Tue, 24 Jan 2017 23:21:17 +0000
Received: from mail-qk0-f171.google.com (mail-qk0-f171.google.com [209.85.220.171]) by linode64.ducksong.com (Postfix) with ESMTPSA id CC87E3A0A9 for <ietf-http-wg@w3.org>; Tue, 24 Jan 2017 18:20:53 -0500 (EST)
Received: by mail-qk0-f171.google.com with SMTP id j126so39189538qkf.1 for <ietf-http-wg@w3.org>; Tue, 24 Jan 2017 15:20:53 -0800 (PST)
X-Gm-Message-State: AIkVDXLEvHTFe1HnEckDKtKbDm/OSfIcHe3jNOTRB6ifGjs167M0E/7dtoLTI9fznTvMLK/+bkbMkYw6gQ6XDw==
X-Received: by 10.55.20.105 with SMTP id e102mr25553486qkh.35.1485300053577; Tue, 24 Jan 2017 15:20:53 -0800 (PST)
MIME-Version: 1.0
Received: by 10.12.162.65 with HTTP; Tue, 24 Jan 2017 15:20:53 -0800 (PST)
In-Reply-To: <CA+3+x5HxOkJfEmurFgZCH1-BN2PswHZfsoA7cvksf5dgUbJEgA@mail.gmail.com>
References: <20170124.165356.870174430965764062.kazu@iij.ad.jp> <900A5D6B-0752-470E-840C-4518D933DD09@greenbytes.de> <CA+3+x5EdkLSAR2gWR9TT72o2Tg4Z_xKXMh8yVREYD7mvNuLB8w@mail.gmail.com> <20170125.075510.1795999132739277437.kazu@iij.ad.jp> <CA+3+x5HxOkJfEmurFgZCH1-BN2PswHZfsoA7cvksf5dgUbJEgA@mail.gmail.com>
From: Patrick McManus <pmcmanus@mozilla.com>
Date: Wed, 25 Jan 2017 08:20:53 +0900
X-Gmail-Original-Message-ID: <CAOdDvNqCEHGN1tSxCmMPHECtrOMHe8_nE0HPDqK+VideuFNQow@mail.gmail.com>
Message-ID: <CAOdDvNqCEHGN1tSxCmMPHECtrOMHe8_nE0HPDqK+VideuFNQow@mail.gmail.com>
To: Tom Bergan <tombergan@chromium.org>
Cc: Kazu Yamamoto <kazu@iij.ad.jp>, HTTP Working Group <ietf-http-wg@w3.org>
Content-Type: multipart/alternative; boundary=001a1144d26614155d0546df5e94
Received-SPF: softfail client-ip=192.155.95.102; envelope-from=pmcmanus@mozilla.com; helo=linode64.ducksong.com
X-W3C-Hub-Spam-Status: No, score=-4.4
X-W3C-Hub-Spam-Report: AWL=-1.617, BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_SORBS_SPAM=0.5, SPF_HELO_PASS=-0.001, SPF_SOFTFAIL=0.665, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: titan.w3.org 1cWAOq-0007gm-4A ecdd146dc5a2a4586b18909c887f831d
X-Original-To: ietf-http-wg@w3.org
Subject: Re: Is a faithful HTTP/2 response scheduler necessarily O(n) in the worst case?
Archived-At: <http://www.w3.org/mid/CAOdDvNqCEHGN1tSxCmMPHECtrOMHe8_nE0HPDqK+VideuFNQow@mail.gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/33370
X-Loop: ietf-http-wg@w3.org
Resent-Sender: ietf-http-wg-request@w3.org
Precedence: list
List-Id: <ietf-http-wg.w3.org>
List-Help: <http://www.w3.org/Mail/>
List-Post: <mailto:ietf-http-wg@w3.org>
List-Unsubscribe: <mailto:ietf-http-wg-request@w3.org?subject=unsubscribe>

media frames are another really good use case for linear orders. These, and
Tom's cases, were all cited as use cases during standardization.

I think the discussion about how to process that organization is germane
and interesting (chair hat!), and we should do that cognizant that this is
an expected use of the priority feature.

On Wed, Jan 25, 2017 at 8:09 AM, Tom Bergan <tombergan@chromium.org> wrote:

> On Tue, Jan 24, 2017 at 2:55 PM, Kazu Yamamoto <kazu@iij.ad.jp> wrote:
>
>> Hi Tom,
>>
>> >> http://www.mew.org/~kazu/material/2015-http2-priority2.pdf
>> >> http://www.mew.org/~kazu/doc/paper/http2-haskell-2016.pdf
>> >
>> > Thanks. IIUC, the algorithms described in both links are still at least
>> > O(depth), which can be O(n) for dependency trees generated by certain
>> > clients such as Chrome.
>>
>> Yes. Your understanding is correct.
>>
>> If a browser creates a list-like tree, I think it is misuse of priority.
>> And servers should limit the depth of trees.
>
>
> Why is that a misuse of priority? It seems entirely reasonable for a
> client to specify a mostly-linear order. There is a very good reason for
> this: inside HTML pages, CSS links and synchronous scripts must be
> evaluated in the order they appear in the HTML file. This implies that the
> server should send those resources in a linear order. This is exactly the
> rationale behind Chrome using mostly-linear orders. (This is not to say
> that mostly-linear orders are not occasionally problematic -- they are
> <https://bugs.chromium.org/p/chromium/issues/detail?id=651538#c1> -- but
> there are good reasons to linear orders at least some of the time.)
>
> (sorry for the duplicate message, replied from the wrong address)
>