Re: Retrospective on PRIORITY

I cannot speak to the proxy use case, but FWIW, I completely support
changing the priority scheme not only in QUIC, but also HTTP/2. One reason
is that HTTP/2 priority scheduling is O(n) in the worst case (
https://lists.w3.org/Archives/Public/ietf-http-wg/2017JanMar/0107.html).
Another reason in the complexity, which has been discussed elsewhere.

However, the biggest reason is that I haven't seen much real evidence that
HTTP/2's priority scheme performs strictly better than something simpler
like SPDY's, even ignoring the O(n) issue. A few months ago, I did a small
study of page load times in Chrome, comparing HTTP/2's priority scheme vs
SPDY's (https://docs.google.com/document/d/1oLhNg1skaWD4_DtaoCxdSRN5erEXrH-
KnLrMwEpOtFY/edit#heading=h.921ubylubq2r). I found that SPDY pageloads were
faster about 35% of the time, HTTP/2 pageloads were faster about 20% of the
time, and the remaining 45% of cases showed no difference.

Don't read too much into those specific numbers. The takeaway is that it's
impossible to express some priorities in HTTP/2 that could be expressed
with SPDY, which means that HTTP/2 is not strictly better than SPDY. Take
the following example:

r1 <- r2 <- ... <- rN <- (group A of unordered requests) <- (group B of
unordered requests)

In this example, (r1, r2, ..., rN) might be a sequence of scripts that need
to be evaluated in a linear order, group A might be high-priority images,
and group B might be low-priority images. Or, group A could be images and
group B could be async scripts. For group A and group B, the browser does
not know the true dependency order and is making some heuristic guesses. In
SPDY, we might not have enough priority levels to fully express the linear
ordering from r1 to rN, so we have to collapse them:

pri=0 (r1 ... rN), pri=1 (groupA), pri=2 (groupB)

This is obviously suboptimal and demonstrates why HTTP/2 might be faster
than SPDY. However, in HTTP/2, we cannot express the dependence between
group A and group B because the A-to-B dependencies are a DAG, not a tree.
There are a few ways this can be encoded in HTTP/2, but they are all
suboptimal in some way.

I really like Osama Mazahir's proposal. With 64-bit integer priorities, we
have enough space to generate any linear order that will arise in practice
(at least for browser clients), yet we can also handle cases like the
above. The "groups" let us naturally give separate weights to individual
tabs. Hierarchical groups could be added if needed by proxies. I believe
(but have not proven) that a scheduler over hierarchical groups would be
O(depthOfGroupTree) in the worst case, which isn't so bad if we expect that
depthOfGroupTree = O(numProxies) most of the time.

On Tue, Apr 18, 2017 at 11:46 AM, Mike Bishop <Michael.Bishop@microsoft.com>
wrote:

> I had an interesting side conversation in Chicago, where it was proposed
> that HTTP/QUIC pull out the H2 priority scheme and go with something
> simpler, or at least make all priority schemes extensions so client/server
> can negotiate which one they want to use.  I think efforts like that
> probably need to be driven out of the HTTP WG rather than the QUIC WG, but
> it did raise some interesting questions.
>
>
>
> Back in this thread (https://lists.w3.org/Archives/Public/ietf-http-wg/
> 2014JanMar/0396.html), we had a proposal which permits expressing the
> same desired end-states, but requires the client to do the tree collapsing
> instead of the server.  That means clients can be as simple or as complex
> as they desire, and the server just needs to see the end output of whatever
> fancy algorithm they’re using.
>
>
>
> The argument that drove the current scheme was that when running a proxy,
> you need a way to be able to encapsulate the priorities declared by one
> client onto priorities in a back-end connection while isolating the user’s
> declared priorities from other users’ declared priorities.  Clearly you
> can’t just do a straight pass-through, or everyone is incented to use the
> top end of the priority range.  The scheme that ultimately landed in H2
> allows this at the proxy:
>
>    - Every user gets a placeholder node; weights of placeholders
>    represent relative priorities of the users
>    - Anything the user declares depends on stream zero in their
>    connection depends on this placeholder; weights unchanged
>    - Anything the user declares depends some other stream still depends
>    on that stream; weights unchanged
>
> Also, when something changes near the root of the tree, the client might
> be issuing a *lot* of PRIORITY frames to update everything as a result if
> all the server gets is the output of the tree.  In the video playback case,
> finishing the current chunk is a change near the root of the tree that’s
> fairly common.
>
>
>
> With any simpler scheme, the proxy either has to ignore declared
> priorities or do work to coalesce declared priorities across users.  And
> obviously, if you have tiers of proxies, the same logic can be applied
> multiple times and still get a sensible result at the back-end.  You could
> bring that idea into the proposal linked above, but you’d need
> groups-of-groups, and groups-of-groups-of-groups, and soon you wind up with
> something that looks a lot like a dependency tree again.
>
>
>
> I think any reasonable priority scheme will work fine between client and
> server – it’s the proxy (forward or reverse) that needs to see the
> uncollapsed tree so that it can merge trees between clients.  Now that H2
> is deployed, I’m curious how proxy vendors are finding this to work out.
> Do you find the additional richness useful, or is there more appetite for
> simpler priority schemes?  Are you actually using the algorithm above, or
> something like it?
>