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

From: Robin Marx <[email-masked]>
Date: Fri, 17 May 2019 22:33:01 -0700

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

---

From: Robin Marx <[email-masked]>
Date: Fri, 17 May 2019 22:39:50 -0700

@rmarx pushed 1 commit.

736250c590e93e1433c00c82007d4a9183a99f28  Fix trailing whitespace

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2723/files/38438620ca5ac2b80e6e824e51e950170f57e468..736250c590e93e1433c00c82007d4a9183a99f28

---

From: Robin Marx <[email-masked]>
Date: Fri, 17 May 2019 22:45:42 -0700

@rmarx pushed 1 commit.

9cc555aa0cdcda6d8776ebf06999ea839bed24ef  Line length off-by-one error

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2723/files/736250c590e93e1433c00c82007d4a9183a99f28..9cc555aa0cdcda6d8776ebf06999ea839bed24ef

---

From: MikkelFJ <[email-masked]>
Date: Sat, 18 May 2019 00:53:59 -0700

Why not make zero take precedence over any weights and avoid the dumb error:

As long as there are 0 weights the first such is served, then weighted entries. You could also call this infinity weight.

I agree that a design does not have to adhere to easily avoidable dumb errors, but sometimes such cases reveal something fundamental about the underlying design.

-- 
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#issuecomment-493657259

---

From: MikkelFJ <[email-masked]>
Date: Sat, 18 May 2019 00:58:58 -0700

Moreover, if the weights are fractions, then 0 becomes infinite in a natural manner, and 1 becomes the highest priority naturally instead of some arbitrary large number.

-- 
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#issuecomment-493657558

---

From: Daan De Meyer <[email-masked]>
Date: Sat, 18 May 2019 04:09:25 -0700

Sequentially sending both before and after non-zero weighted nodes could potentially be supported by hijacking weight 256 for sending sequentially after non-zero weighted nodes and using weight 0 for sending sequentially before non-zero weighted nodes.

I'd imagine there being scenario's where both are applicable. Before for when a high priority resource is discovered and after for when you don't really care about the order a resource is delivered in.

-- 
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#issuecomment-493668705

---

From: Igor Lubashev <[email-masked]>
Date: Sat, 18 May 2019 13:03:02 -0700

The situation I would like to be able to cover is a page with several videos (or animated gifs) and a few async scripts.  You want these videos to start playing asap and all together (before scripts load), but you do not want to wait till videos are completely downloaded to begin loading those async scripts (which should load serially).

> As long as there are children with non-zero weights: divide the node's bandwidth over those children based on their weights

So what happens to sequential scripts? They shall wait till all videos are downloaded?

> If there are only children with zero weight left: all bandwidth goes to the child with the lowest ID that can make progress

I do not like creating arbitrary priorities where none are warranted. It is best not to lie to the server and let it pick its own priority, if it is all the same to the User Agent. For example, if there are multiple zero-weight children, the server may choose to deliver whatever object is fully available in memory rather than deliver 80% of an object with the lowest ID first and only then start sending the fully-available object.

-- 
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#issuecomment-493703452

---

From: MikkelFJ <[email-masked]>
Date: Sat, 18 May 2019 14:13:04 -0700

> So what happens to sequential scripts? They shall wait till all videos are downloaded?

You are not forced to use zero weights - but how the browser decides, I don't know.

> I do not like creating arbitrary priorities where none are warranted. Let the server pick its own priority, i

That is a good point. But it would prevent queued requests.

-- 
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#issuecomment-493707624

---

From: Igor Lubashev <[email-masked]>
Date: Sat, 18 May 2019 21:24:53 -0700

> You are not forced to use zero weights - but how the browser decides, I don't know.

The problem with using weights in this scheme is that weights imply round-robin. That's not what you want for scripts (resources that cannot be consumed until they are loaded 100%). So you want scripts to load serially (among scripts) but concurrently with a bunch of videos.

-- 
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#issuecomment-493725923

---

From: MikkelFJ <[email-masked]>
Date: Sun, 19 May 2019 01:03:04 -0700

> The problem with using weights in this scheme is that weights imply round-robin. That's not what you want for scripts (resources that cannot be consumed until they are loaded 100%). So you want scr…

So what you actually want is a weighted serial bucket. Anywhere you'd add a zero-weight you would instead put the resource into a weighted serial bucket.

-- 
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#issuecomment-493735900

---

From: Robin Marx <[email-masked]>
Date: Sun, 19 May 2019 03:30:17 -0700

Thank you all for the comments!

> As long as there are 0 weights the first such is served, then weighted entries. You could also call this infinity weight.

I considered this, but that would again introduce the need for a special case treatment of the default situation (e.g., the orphan placeholder). I feel that the "dumb error" is really quite dumb and should be quite rare, as you would need to specify a weight and add the node to a placeholder that also has zero-weighted streams attached to it for it to come into play. That type of error is not specific to this proposal and would always lead to weird behavior. I expect it more likely that people will just not use placeholders/weights at all, and we end up in the FCFS case.

> Sequentially sending both before and after non-zero weighted nodes could potentially be supported by hijacking weight 256 for sending sequentially after non-zero weighted nodes and using weight 0 f…

That being said, I do really like the symmetry behind this approach. I would reverse the semantics you propose though: 255 takes precedence over everything, 0 is lowest priority. It adds a bit of extra complexity, but this might be worth it. I will try to make some example graphs for this too.

> The situation I would like to be able to cover is a page with several videos (or animated gifs) and a few async scripts. You want these videos to start playing asap and all together (before scripts…

If I understand your use case correctly, this is supported by adding 2 sibling placeholders (PH): 1 placeholder for the videos and 1 for the scripts. The video PH would for example get weight 60 and all videos are added to it with an (equal) weight so they get transferred in parallel. The script PH would get weight 30 and all scripts are added to it with weight 0 so they get transferred sequentially. The videos/scripts would then get about 2x as much bandwidth as the scripts (60 vs 30). 

This is normal HTTP/2 behaviour and supported by this proposal and #2700 and also the current HTTP/3 draft text. The main change for this proposal (and also #2700) is that you can add the scripts to the PH with weight 0 and they automatically are transferred sequentially. Without this, you would need to add a script to the previous script node (instead of the placeholder) to get the sequential behaviour. See both compared in the image below. 

 In the case of @pmeenan's proposal, iiuc, you would put scripts in concurrency 2 and videos in concurrency 1 and they would automatically share the bandwidth 50/50 (while here we can specify the weights in more detail). 

![2019-05-19 12_25_52](https://user-images.githubusercontent.com/2240689/57980888-5506b580-7a31-11e9-965d-faacc4b212ed.png)

> I do not like creating arbitrary priorities where none are warranted. Let the server pick its own priority, if it is all the same to the User Agent. For example, if there are multiple zero-weight children, the server may choose to deliver whatever object is fully available in memory rather than deliver 80% of an object with the lowest ID first and only then start sending the fully-available object.

This is a good point and of course still possible. The priorities in the HTTP/3 and HTTP/2 texts can perfectly be overridden by a server if it feels it has a better grasp on the situation. However, as I understand it, for HTTP/2 most (non-proxy) servers do not do custom logic and implement the spec and as such, the spec needs to have sensible defaults. 

-- 
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#issuecomment-493745276