[quicwg/base-drafts] HTTP/3 Zero-weighting (#2723)

Robin Marx <notifications@github.com> Sat, 18 May 2019 05:33 UTC

Return-Path: <noreply@github.com>
X-Original-To: quic-issues@ietfa.amsl.com
Delivered-To: quic-issues@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2C7F5120100 for <quic-issues@ietfa.amsl.com>; Fri, 17 May 2019 22:33:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.009
X-Spam-Level:
X-Spam-Status: No, score=-8.009 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, MAILING_LIST_MULTI=-1, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001, T_DKIMWL_WL_HIGH=-0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=github.com
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 413hQbDepdA4 for <quic-issues@ietfa.amsl.com>; Fri, 17 May 2019 22:33:02 -0700 (PDT)
Received: from out-7.smtp.github.com (out-7.smtp.github.com [192.30.252.198]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6366712002F for <quic-issues@ietf.org>; Fri, 17 May 2019 22:33:02 -0700 (PDT)
Date: Fri, 17 May 2019 22:33:01 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=github.com; s=pf2014; t=1558157581; bh=3m0xzSyx96K6m2JqSvEFqxKqU8xiBwcWuo1T221l46g=; h=Date:From:Reply-To:To:Cc:Subject:List-ID:List-Archive:List-Post: List-Unsubscribe:From; b=btdEFZdPi0VPJWV458sQqTMm5hI0+iv13GnJoD7lfrnM0nTbeTVCe91m/WLoeoXpq e3tanVgNDX6U7nTTR+MIa5C6fhROpc7dz18TJRLtRQtSP0lVoz9U3k/vt4Lmo0kzZt qjD75WWP+BmUim0WtualeKc99zH2yRoZqUjQcftM=
From: Robin Marx <notifications@github.com>
Reply-To: quicwg/base-drafts <reply+AFTOJK5J5PDFPTGJUBPUCQ525TFY3EVBNHHBVEEO5I@reply.github.com>
To: quicwg/base-drafts <base-drafts@noreply.github.com>
Cc: Subscribed <subscribed@noreply.github.com>
Message-ID: <quicwg/base-drafts/pull/2723@github.com>
Subject: [quicwg/base-drafts] HTTP/3 Zero-weighting (#2723)
Mime-Version: 1.0
Content-Type: multipart/alternative; boundary="--==_mimepart_5cdf990dab03_42053f8d68acd96c488444"; charset=UTF-8
Content-Transfer-Encoding: 7bit
Precedence: list
X-GitHub-Sender: rmarx
X-GitHub-Recipient: quic-issues
X-GitHub-Reason: subscribed
X-Auto-Response-Suppress: All
X-GitHub-Recipient-Address: quic-issues@ietf.org
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic-issues/Bq9aHRbWsWv3x0wRKlcV2dOtQcs>
X-BeenThere: quic-issues@ietf.org
X-Mailman-Version: 2.1.29
List-Id: Notification list for GitHub issues related to the QUIC WG <quic-issues.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic-issues/>
List-Post: <mailto:quic-issues@ietf.org>
List-Help: <mailto:quic-issues-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 18 May 2019 05:33:06 -0000

Fixes both problems in #2502
Consolidates #2700 and #2690
Allows the use cases from https://github.com/pmeenan/http3-prioritization-proposal/blob/master/README.md

(I am creating a new PR because I don't want to subsume #2700. While this is similar, it has enough differences to warrant separate discussion).

-----------

I believe we can get all the benefits of the previously proposed solutions by adding just a single new concept: zero-weighting of nodes in the dependency tree
This would have the following semantics:

Given a node in the tree:
- As long as there are children with non-zero weights: divide the node's bandwidth over those children based on their weights (which is what we already have)
- If there are only children with zero weight left: all bandwidth goes to the child with the lowest ID that can make progress (this is new, similar to #2700, but inverted)

Put differently: zero-weighted nodes get sent sequentially, after all non-zero weighted nodes. 

Additionally, a weight of zero becomes the default for newly added nodes (previously, the default weight was 16).
This makes the default behaviour First-Come-First-Served instead of Round-Robin. 

-----------

Differences from #2700 (strict priorities):
- This is very similar to the "weight absent" concept in #2700
- Removal of the "priority" field: this can be simulated instead by using placeholders. E.g., if you had three priorities of 63, 31 and 0, you would now have three zero-weighted placeholders, where the most important one (priority 64) is created first (has the lowest id) etc. See also below
- Still allows streams to depend on other streams (more similar to HTTP/2) (though this should not really even be needed anymore, see below)
- If you have both children with and without 0 weights, they no longer share bandwidth 50/50: the weighted children are sent first, then the non-weighted ones (this is detrimental if you "accidentally" mix both, as the sequential list will be sent after the round-robin resources, which is probably the opposite of what you want. So I admit there is the potential for dumb error here. Though the added simplicity for implementers who know what they are doing + better default behaviour is worth it imo)

Comparison to https://github.com/pmeenan/http3-prioritization-proposal/blob/master/README.md:
- @pmeenan's original proposal is probably easier to understand and possibly implement, as it requires a lot less placeholder/tree setup (I find that #2700 looses much of this simplicity though https://github.com/quicwg/base-drafts/pull/2700#issuecomment-493076309)
- @pmeenan's full setup would require 64 high-level placeholders in this proposal (1 per priority value), but even the original document only uses 3 levels in practice for current browser use cases (63, 31 and 0). As @ianswett indicates https://github.com/quicwg/base-drafts/pull/2700#issuecomment-493590118, the use case of "fairly share connectivity to an ORIGIN" would require more nodes, but it is very unclear whether this is/will be used in practice. 
- @pmeenan's concurrency concept requires 4 additional placeholders in this proposal (2 to split between concurrency 3 and 2+1 (both zero-weighted), then 2 more to split between 2 and 1 (both weight=50) ) (TODO: make an example image)
- TODO: I believe #2700 has similar issues with needing many placeholders, but haven't worked that out fully yet 
- In short, I feel that if we want to go with Pat's approach, we either need to go all-in (drop the dependency tree) or use a separate extension (potentially officially adopted by the wg prior to HTTP/3 RFC, after also adding a prioritization-negotation mechanism)

Comparison to #2960 (Orphan Placeholder):
- We no longer need a separate orphan placeholder: since nodes have a default weight of zero and those are only sent after weighted siblings (or, probably more commonly, zero-weight placeholder siblings with a lower id that are added at the start of the connection), nodes without explicit priority context never interrupt more important flows
- As such, "unprioritized" nodes can just be added to the root directly with weight zero without side-effects
- Fixes issues with early-pruning of the tree (https://github.com/quicwg/base-drafts/pull/2690#discussion_r282999731): all nodes can now just depend upon a placeholder. Direct references to other request nodes are no longer needed for sequential behaviour (also removes need for separate "append strategy" on the placeholder https://github.com/quicwg/base-drafts/pull/2700#pullrequestreview-237930797)

Comparison to HTTP/2 and current browser behaviour:
- Basically, we are adding a new type of prioritization semantic (sequential), without removing something that was already there
- The default behaviour is now First-Come-First-Served (FCFS), which our research [1] (and that of others [2]) has indicated is not perfect, but far better than HTTP/2's Round-Robin (RR) in almost all cases 
- Safari's current behaviour is still perfectly possible and requires no changes, same for Firefox
- Edge's old behaviour is implicitly changed from RR to FCFS, but seeing as they are switching to Chromium, this seems like a non-issue.
- Chrome's behaviour will have to change, but that was a given, since we removed exclusive dependencies in #2075, which it relies upon heavily. Chrome can just use 5 zero-weighted placeholder for the priority buckets (HIGHEST to LOWEST) and then just add zero-weighted requests to the appropriate placeholder. This is similar to https://github.com/quicwg/base-drafts/issues/2502#issuecomment-491246513, but there the placeholders have weight=1, which is not 100% as clean.

The "reprioritizing within a sequential list" issue:
- This was discussed previously in https://github.com/quicwg/base-drafts/issues/2502#issuecomment-491246513 and https://github.com/quicwg/base-drafts/pull/2700#issuecomment-493369036
- Upon reflection, I do not think either @pmeenan's proposal, nor #2700 actually allows this behaviour (for example, within priority 63, concurrency 3, there doesn't seem to be a way to add a resource before another one that is already there within the same concurrency, as things are also sent based on lowest request ID, same as in this proposal)
- It is also my understanding that Chrome doesn't even do this currently: exclusive prioritization only happens at the end of each "priority bucket", not within the bucket 
- A solution is to add yet another high-level placeholder (e.g., everything that is now in 63 moves to 62 and 63 is for the "really important stuff that needs to interrupt the other really important stuff")
- Alternatively, adding a weighted sibling node in this proposal also causes it to interrupt the other zero-weighted siblings' sequential processing (though this is more an all-or-nothing)

-------

This was a nice wall of text.
I wrote this after a sleepless night at 6AM, so probably there are some problems with this version (especially with the spec text, it's quite short now, probably requires some clarifications). 
I considered many other options (e.g., weight 255 instead of 0, placeholder append strategies, etc.) but the above came out as a clear winner on most points. 

I plan to add a couple of schema's/examples to clarify things and present this remotely at the interim (if the chairs think it's proper, of course).

I am not saying this is necessarily better than #2700, but I do like the simplicity. I think we should consider both options. 

TODO schema's/images:
- @pmeenan's example from his document (both for this proposal as for #2700)
- A reworking of Chrome's current behaviour into priority "buckets" (similar to https://github.com/quicwg/base-drafts/issues/2502#issuecomment-491246513)
- Examples of default behaviour (Edge's old behaviour, race-conditions from #2502)

[1]: https://speeder.edm.uhasselt.be/www18/
[2]: https://blog.cloudflare.com/better-http-2-prioritization-for-a-faster-web/
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/2723

-- Commit Summary --

  * HTTP/3 Zero-weighting

-- File Changes --

    M draft-ietf-quic-http.md (18)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2723.patch
https://github.com/quicwg/base-drafts/pull/2723.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2723