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

[Robin Marx <[e-mail]>]

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