Subject: Retrospective on PRIORITY

From: Mike Bishop <[email-masked]>
Date: Tue, 18 Apr 2017 18:46:56 +0000

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?

---

From: Alcides Viamontes E <[email-masked]>
Date: Tue, 18 Apr 2017 22:23:01 +0200

Interesting dig up Mike, I didn't follow the discussion during  2014 and
therefore had always wondered why the priorities ended up being a tree
instead of something simpler. Do you mean that we ended up with a
tree-based priority scheme because of the assumption that most people would
be deploying HTTP/2 through proxies that collapse multiple sets of streams
from client to proxy to a single set of streams from proxy to  origin?

As of your question, I'm more on your curious-side of the matter, though I
have some opinions.

We are not proxy implementors, but we sell an HTTP/2 solution that makes
strong use of priorities. We have opted for equipping the server with ways
to set priorities between streams a-priori, without directly using the
priority frames from the browser. We collect the priority frames and
combine then with other nuggets of information (e.g. information derived
from the browser's DOM in a sandbox) to program the priorities.

One of the reasons we prefer this approach is because of the latency of the
entire browser-network-server system, even when there are no proxies in the
middle. We have noticed that is not just pure network latency we have to
deal with, but also different buffers, caches, CPU saturation on the
server, and particularly, parsing and decompression time on the browser. We
have observed the last component to be significant even on moderately
powerful laptops, the situation on mobile devices being  worse. This system
latency means that priority frames often arrive a bit too late to be
effective, even without deploying HTTP/2 Push.

Back to your question, I would expect  a proxy that just relies priority
information to make this latency higher. A proxy can of course  improve
things by being  more sophisticated ... in some way, which I can't exactly
imagine. So, from my point of view, a flat priority indication would make
more sense.

On Tue, Apr 18, 2017 at 8:46 PM, Mike Bishop <[email-masked]>
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?
>

-- 
Alcides Viamontes E.
Chief Executive Officer, Zunzun AB
(+46) 722294542
(www.shimmercat.com is a property of Zunzun AB)

---

From: Tom Bergan <[email-masked]>
Date: Tue, 18 Apr 2017 13:53:25 -0700

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.

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 19 Apr 2017 13:34:44 +0900

Hi Mike,

Thank you for raising this interesting discussion.

2017-04-19 3:46 GMT+09:00 Mike Bishop <[email-masked]>:
> 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.
>
>
>
> 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,
> 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.
>
>
>
> 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

I would argue that for a reverse proxy there is no much need to
prioritize requests sent to origin, since the majority of HTTP
requests are requests for static assets and hence are terminated at
the reverse proxy. Users of a reverse proxy that sends all requests to
origin (e.g. WAF-as-a-service) might have a different opinion, though.

OTOH, I am kind of negative about designing a new priority scheme. The
priority scheme of HTTP/2 works fairly well, and we have experiences.
Is there any reason not to reuse?

My point is that we should better not risk delaying the delivery of
QUIC by trying to replace something that might be a bit complicated
but is already known to work well.

-- 
Kazuho Oku