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

Tom Bergan <tombergan@chromium.org> Tue, 24 January 2017 23:12 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 C74D6129517 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Tue, 24 Jan 2017 15:12:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.719
X-Spam-Level:
X-Spam-Status: No, score=-9.719 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, 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, RCVD_IN_SORBS_SPAM=0.5, RP_MATCHES_RCVD=-3.199, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=chromium.org
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 887M4_FW3pVe for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Tue, 24 Jan 2017 15:12:47 -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 15C711294FE for <httpbisa-archive-bis2Juki@lists.ietf.org>; Tue, 24 Jan 2017 15:12:47 -0800 (PST)
Received: from lists by frink.w3.org with local (Exim 4.80) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1cWAEL-0007jX-LN for ietf-http-wg-dist@listhub.w3.org; Tue, 24 Jan 2017 23:10:25 +0000
Resent-Date: Tue, 24 Jan 2017 23:10:25 +0000
Resent-Message-Id: <E1cWAEL-0007jX-LN@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 <tombergan@chromium.org>) id 1cWAEI-0007hl-I0 for ietf-http-wg@listhub.w3.org; Tue, 24 Jan 2017 23:10:22 +0000
Received: from mail-wm0-f49.google.com ([74.125.82.49]) by titan.w3.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) (envelope-from <tombergan@chromium.org>) id 1cWAEC-0007I3-6i for ietf-http-wg@w3.org; Tue, 24 Jan 2017 23:10:17 +0000
Received: by mail-wm0-f49.google.com with SMTP id c85so1830464wmi.1 for <ietf-http-wg@w3.org>; Tue, 24 Jan 2017 15:09:55 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=JvDWZjHTJu7UPUsXBklmEE02tvluMT8YlIPCOkDjuww=; b=Bx+NGn0aHYwBZefugGuwFxhl7A3opklKCrJIfXaQq+HuqUvwxV2z8wtRpyObLReVLw J0mwcTLLf2jMWf1gOhTkjomdEc+TqR2s7ryme37IA14LPt3Y5nFciv6NGKeXe+a99hPu E6Ht/uYsSOxYa1KEL3+TrKofo+k4voM+Gg/y0=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=JvDWZjHTJu7UPUsXBklmEE02tvluMT8YlIPCOkDjuww=; b=klucoHvLlDM8r3k/fNJ1kbkcKn+GvlsDjb5zMZnADvRvx5kqnY+unsKM1iD62Bqxxc 3SSMuDVQrJHAgdJOQ2Z824utGk5tJufQb8eaqpaqhZsimjuiIF8nX2G6NViXWrQxnn9Y 6dFGyVEKigYwjzIqrOEwQ8AqjuvnKKPOh+gGEFzUUlN1s2nGkyI/tRtcLSzS98lOCjjB j182owjzc8ZW9balm2QuDT4ABM/Nguy4Mguwdt6waXUI0M7Vmq/WPfx70pbYKn1YZ6f/ XkgmFf2kG61yu//NyrsoVuBYLYRdSHWgB1MhS5HODrbRNtwaSZa5KsSKVZfIdhSRa8w3 9UOQ==
X-Gm-Message-State: AIkVDXLEDq+i2g6zsPbG8w4oy8nbhekpOUnhbWDwJUxHNA97qIGOREr9sLe7qLXvWiFpuTF0
X-Received: by 10.223.133.164 with SMTP id 33mr629185wrt.39.1485299388608; Tue, 24 Jan 2017 15:09:48 -0800 (PST)
Received: from mail-wm0-f45.google.com (mail-wm0-f45.google.com. [74.125.82.45]) by smtp.gmail.com with ESMTPSA id z67sm22090807wrb.49.2017.01.24.15.09.47 for <ietf-http-wg@w3.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 24 Jan 2017 15:09:48 -0800 (PST)
Received: by mail-wm0-f45.google.com with SMTP id r126so2313329wmr.0 for <ietf-http-wg@w3.org>; Tue, 24 Jan 2017 15:09:47 -0800 (PST)
X-Received: by 10.223.141.229 with SMTP id o92mr34612315wrb.22.1485299387650; Tue, 24 Jan 2017 15:09:47 -0800 (PST)
MIME-Version: 1.0
Received: by 10.28.135.201 with HTTP; Tue, 24 Jan 2017 15:09:47 -0800 (PST)
In-Reply-To: <20170125.075510.1795999132739277437.kazu@iij.ad.jp>
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>
From: Tom Bergan <tombergan@chromium.org>
Date: Tue, 24 Jan 2017 15:09:47 -0800
X-Gmail-Original-Message-ID: <CA+3+x5HxOkJfEmurFgZCH1-BN2PswHZfsoA7cvksf5dgUbJEgA@mail.gmail.com>
Message-ID: <CA+3+x5HxOkJfEmurFgZCH1-BN2PswHZfsoA7cvksf5dgUbJEgA@mail.gmail.com>
To: Kazu Yamamoto <kazu@iij.ad.jp>
Cc: HTTP Working Group <ietf-http-wg@w3.org>
Content-Type: multipart/alternative; boundary=f403045f530a6308bf0546df3640
Received-SPF: pass client-ip=74.125.82.49; envelope-from=tombergan@chromium.org; helo=mail-wm0-f49.google.com
X-W3C-Hub-Spam-Status: No, score=-3.5
X-W3C-Hub-Spam-Report: BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RCVD_IN_SORBS_SPAM=0.5, SPF_PASS=-0.001, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: titan.w3.org 1cWAEC-0007I3-6i 5862999e7da639679ae75d5831468e63
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/CA+3+x5HxOkJfEmurFgZCH1-BN2PswHZfsoA7cvksf5dgUbJEgA@mail.gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/33369
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>

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)