Subject: HTTP/3 Prioritization Proposal

From: Patrick Meenan <[email-masked]>
Date: Mon, 28 Jan 2019 12:10:08 -0500

I'm happy to draft it as an I-D but wanted to see if people thought there
was merit to it before going through the effort:
https://github.com/pmeenan/http3-prioritization-proposal/blob/master/README.md

Basically, I'd like to propose replacing the dependency trees and weights
with a simpler scheme that has "priority" and "concurrency" values for each
stream (with no shared tree state).

There may be HTTP use cases that it doesn't cover but coming from the
browser side of things (and having spent some time working on server-side
prioritization) it should make it MUCH easier to manage prioritization and
to schedule an "optimal" prioritization for resources.

Thanks,

-Pat Meenan

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 29 Jan 2019 06:54:21 +0900

Hi Pat,

There's been a fair amount of discussion (and interest) about prioritisation, both here and in the QUIC WG.

So far, AIUI our inclination has been to avoid making a large change from HTTP/2 in HTTP/3, because doing so would both increase complexity of implementations, and also potentially introduce friction for sites and applications transitioning from HTTP/2. 

I don't recall us having a formal consensus call to support that position, but if you want to talk about it more, the QUIC WG mailing list is probably the right place.

My sense is that people know that we need to do something about prioritisation, but we're not yet confident about any particular solution. Experimentation with new schemes as HTTP/2 extensions would be very helpful, as it would give us some data to work with. If you'd like to propose such an extension, this is the right place to do it.

Hope this helps,

Cheers,

> On 29 Jan 2019, at 2:10 am, Patrick Meenan <[email-masked]> wrote:
> 
> I'm happy to draft it as an I-D but wanted to see if people thought there was merit to it before going through the effort: https://github.com/pmeenan/http3-prioritization-proposal/blob/master/README.md
> 
> Basically, I'd like to propose replacing the dependency trees and weights with a simpler scheme that has "priority" and "concurrency" values for each stream (with no shared tree state).
> 
> There may be HTTP use cases that it doesn't cover but coming from the browser side of things (and having spent some time working on server-side prioritization) it should make it MUCH easier to manage prioritization and to schedule an "optimal" prioritization for resources.
> 
> Thanks,
> 
> -Pat Meenan

--
Mark Nottingham   https://www.mnot.net/

---

From: Patrick Meenan <[email-masked]>
Date: Mon, 28 Jan 2019 17:03:57 -0500

Thanks. I wasn't sure where the split was going to be as QUIC seemed to be
pushing a lot of prioritization decisions into HTTP. If QUIC is going to be
a general user-mode TCP/IP replacement then this kind of prioritization
probably doesn't belong there since it's mostly targeted at HTTP (and
specifically, web/browser) but if QUIC is more targeted to just be HTTP
then it might make sense.

I'd be open to experimenting with it as an HTTP/2 extension as a step
towards figuring out if it makes sense as well. I'll poke around a bit and
see what would be involved to implement it in a dev build of Chrome and a
server (h2o or nginx) to be able to do some lab testing with it.

On Mon, Jan 28, 2019 at 4:54 PM Mark Nottingham <[email-masked]> wrote:

> Hi Pat,
>
> There's been a fair amount of discussion (and interest) about
> prioritisation, both here and in the QUIC WG.
>
> So far, AIUI our inclination has been to avoid making a large change from
> HTTP/2 in HTTP/3, because doing so would both increase complexity of
> implementations, and also potentially introduce friction for sites and
> applications transitioning from HTTP/2.
>
> I don't recall us having a formal consensus call to support that position,
> but if you want to talk about it more, the QUIC WG mailing list is probably
> the right place.
>
> My sense is that people know that we need to do something about
> prioritisation, but we're not yet confident about any particular solution.
> Experimentation with new schemes as HTTP/2 extensions would be very
> helpful, as it would give us some data to work with. If you'd like to
> propose such an extension, this is the right place to do it.
>
> Hope this helps,
>
> Cheers,
>
>
> > I'm happy to draft it as an I-D but wanted to see if people thought
> there was merit to it before going through the effort:
> > Basically, I'd like to propose replacing the dependency trees and
> weights with a simpler scheme that has "priority" and "concurrency" values
> for each stream (with no shared tree state).
> >

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 29 Jan 2019 07:21:31 +0900

Hey Mark,

> propose such an extension, this is the right place to do it.

The small amount of thinking I did on this lead me to a different
conclusion. That it would be easier to experiment with new prioritization
schemes in HTTP/3, due mainly to the removal of priority information from
the H3 HEADERS frame. This makes it quite feasible to write an extension
along the lines of "the extension replaces/supersedes the base standard
PRIORITY frame when negotiated". In contrast, a H2 extension either needs
to define a new HEADERS format or provide supplemental information in the
form of a new frame, which is possible but a bit redundant.

There didn't seem to be much appetite for adopting H3 priority placeholder
design in H2 (I cant remember when this was presented, sorry). I'd be
curious to know if there is more interest in other alternate priority
schemes in H2.

Lucas

---

From: Mike Bishop <[email-masked]>
Date: Tue, 29 Jan 2019 00:33:17 +0000

I think you’re both right, actually.  We’ve had discussions in H3 about whether the built-in PRIORITY scheme should be pulled out to an extension, and one of the reasons not to was that we didn’t have a competing priority scheme specified.  If the proposal is an extension, whether to H2 or H3, the HTTPbis WG owns those per our recharter, no?  So it belongs here, but it’s relevant to the H3 discussion and H3 is a reasonable target.

As to the actual proposal, I think it goes a long way toward giving us much of the needed functionality with a minimum of complexity.  I like it.  One minor suggestion:  I would swap the polarity of the low bits so that it flows the same direction as the priority field – greater numbers are more important.  (That is, make `11` Exclusive Sequential and `01` Shared.)  This enables a naïve implementation to just sort by the entire byte and come out not far wrong, plus makes a more correct implementation more intuitive.

From: Lucas Pardue <[email-masked]>
Sent: Tuesday, January 29, 2019 7:22 AM
To: Mark Nottingham <[email-masked]>
Cc: Patrick Meenan <[email-masked]>; HTTP Working Group <[email-masked]>
Subject: Re: HTTP/3 Prioritization Proposal

Hey Mark,

On Tue, 29 Jan 2019, 06:58 Mark Nottingham <[email-masked]<mailto:[email-masked]> wrote:
My sense is that people know that we need to do something about prioritisation, but we're not yet confident about any particular solution. Experimentation with new schemes as HTTP/2 extensions would be very helpful, as it would give us some data to work with. If you'd like to propose such an extension, this is the right place to do it.

The small amount of thinking I did on this lead me to a different conclusion. That it would be easier to experiment with new prioritization schemes in HTTP/3, due mainly to the removal of priority information from the H3 HEADERS frame. This makes it quite feasible to write an extension along the lines of "the extension replaces/supersedes the base standard PRIORITY frame when negotiated". In contrast, a H2 extension either needs to define a new HEADERS format or provide supplemental information in the form of a new frame, which is possible but a bit redundant.

There didn't seem to be much appetite for adopting H3 priority placeholder design in H2 (I cant remember when this was presented, sorry). I'd be curious to know if there is more interest in other alternate priority schemes in H2.

Lucas

---

From: Amos Jeffries <[email-masked]>
Date: Tue, 29 Jan 2019 15:16:01 +1300

On 29/01/19 1:33 pm, Mike Bishop wrote:
> I think you’re both right, actually.  We’ve had discussions in H3 about
> whether the built-in PRIORITY scheme should be pulled out to an
> extension, and one of the reasons not to was that we didn’t have a
> competing priority scheme specified.  If the proposal is an extension,
> whether to H2 /or /H3, the HTTPbis WG owns those per our recharter, no? 
> So it belongs here, but it’s relevant to the H3 discussion and H3 is a
> reasonable target.

IMO, if there are multiple priority schemes competing then there has to
be some SETTINGS (or equivalent) negotiation between the endpoints about
which one they are going to use.

This new proposal uses the same number of bits as the existing HTTP/2
scheme, so could easily re-use the same bits - the endpoints just need
to negotiate which interpretation those bits are given.

That said, looking through the proposal the very first thing that stands
out to me is that all the problems cited are somewhat artificial, or at
least indirect. They are a natural result of the particular Browsers
choice of implementation rather than problems with the priority design
itself:

 * Chrome - does not implement concurrency in its tree -> problems with
items that benefit from concurrency .

 * Firefox - aggregate only by type, forced concurrency -> problems with
items that should be high priority but have type with low-priority
classification, and with items that need sequential delivery.

 * Safari - does not implement -> latency problems with objects that
could benefit from priority markings.

The rational conclusion then is that better Browser implementations
would solve these particular annoyances. So what problems exactly are
preventing that better implementation happening?

Any replacement prioritization would likely have to face and resolve the
same issues. Along with the issues which caused the HTTP/2 priority
complexity -  that was a very simple design to begin with too.

As a side note this statement worries me:

"
The dependency tree management requires the tree state to be
synchronized on both ends of the connection.
"

IIRC one of the main benefits of the priority scheme we have is
precisely the opposite to that. Priority itself being a guideline more
than a hard requirement and sync between the endpoints after the initial
request weight assignment by HEADERS is an optional bonus for better UI
performance.

The Browse endpoint and the Origin endpoint(s) *will* have different
trees. If only because the response content comes from multiple
locations (middleware cache vs origin cache vs origin as-needed
generator) with vastly different frame delivery speeds.

Amos

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 29 Jan 2019 06:08:01 +0000

I personally find the concurrency levels quite a nice simplification, and you should definitely write a draft.
For non browser, cases we've been thinking of supplying deadlines to the peer to guide things like transmission/re-transmission policies. It might be interesting (while still keeping it simple) to consider deadlines within a concurrency group.
In any case, even just being able to negotiate a priority scheme will mean that we can start of with something simple and then add on.

Subodh

________________________________
From: Amos Jeffries <[email-masked]>
Sent: Monday, January 28, 2019 6:16 PM
To: [email-masked]
Subject: Re: HTTP/3 Prioritization Proposal

"

Amos

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 29 Jan 2019 05:26:09 +0000

Subodh

"

Amos

---

From: Ian Swett <[email-masked]>
Date: Tue, 29 Jan 2019 07:10:55 -0500

I'm not sure this is exactly what I'd specify, but I prefer this over the
existing priority scheme and I believe it's simple enough most clients
would actually implement it.

I agree with Lucas that H3 makes experimenting with priority easier, and
I'd like to see a lot more of it given the lack of adoption of H2
priorities on the client side.

I agree with Subodh that deadlines are very useful in QUIC, but I'm not
convinced that clients are always in a better position to specify the
deadline than servers.  If servers can specify the deadline, then we don't
need to add them to priorities.

On Tue, Jan 29, 2019 at 3:12 AM Subodh Iyengar <[email-masked]> wrote:

> For non browser, cases we've been thinking of supplying deadlines to the
> peer to guide things like transmission/re-transmission policies. It might
> be interesting (while still keeping it simple) to consider deadlines within
> a concurrency group.
> In any case, even just being able to negotiate a priority scheme will mean
> that we can start of with something simple and then add on.
>
> Subodh
> ------------------------------
> *From:* Amos Jeffries <[email-masked]>
> *Sent:* Monday, January 28, 2019 6:16 PM
> *To:* [email-masked]
> *Subject:* Re: HTTP/3 Prioritization Proposal
>

---

From: Patrick Meenan <[email-masked]>
Date: Tue, 29 Jan 2019 09:38:40 -0500

Thanks for the suggestion on the concurrency bit swapping, just made the
change.

On Mon, Jan 28, 2019 at 7:33 PM Mike Bishop <[email-masked]> wrote:

> whether the built-in PRIORITY scheme should be pulled out to an extension,
> and one of the reasons not to was that we didn’t have a competing priority
> scheme specified.  If the proposal is an extension, whether to H2 *or *H3,
> the HTTPbis WG owns those per our recharter, no?  So it belongs here, but
> it’s relevant to the H3 discussion and H3 is a reasonable target.
>
>
>
> As to the actual proposal, I think it goes a long way toward giving us
> much of the needed functionality with a minimum of complexity.  I like it.
> One minor suggestion:  I would swap the polarity of the low bits so that it
> flows the same direction as the priority field – greater numbers are more
> important.  (That is, make `11` Exclusive Sequential and `01` Shared.)
> This enables a naïve implementation to just sort by the entire byte and
> come out not far wrong, plus makes a more correct implementation more
> intuitive.
>
>
>
> *From:* Lucas Pardue <[email-masked]>
> *Sent:* Tuesday, January 29, 2019 7:22 AM
> *To:* Mark Nottingham <[email-masked]>
> *Cc:* Patrick Meenan <[email-masked]>; HTTP Working Group <
> [email-masked]>

---

From: Patrick Meenan <[email-masked]>
Date: Tue, 29 Jan 2019 09:51:36 -0500

The biggest issue (at least currently) that I know of with the need to
synchronize the current priority trees is when adding new streams as a
child of a stream somewhere in the existing tree. The client has to hope
that the server still knows about the parent stream that the new stream is
being attached to, otherwise it gets dumped to the root with a weight of
16. This is a very real edge-case that, while known, impacted at least the
h2o and Google HTTP/2 server implementations serving traffic to Chrome. My
initial test for HTTP/2 prioritization triggered the edge case quite
reliably (unintentionally). h2o has since worked around it by "remembering"
some completed streams but I believe the Google edges are still impacted
(and I'm not sure about other implementations).

The existing scheme itself may be simple but implementing it is not. At
least on the client side, the browser needs to maintain a tree of all of
the in-flight requests to determine where the next stream should be
attached which is why the implementations are pretty simplistic. Firefox
just attaches new streams to the parent groups. Chrome keeps the "tree" but
it is effectively a linear list sorted by priority and new streams are
inserted as needed. Building a tree that supported ordering the critical
resources and splitting concurrency for visible images, hidden images, etc
is probably possible with some combination of Firefox's phantom streams for
grouping (to do group sequencing) but it would be a MUCH more complicated
tree. Trying to debug the trees and serving order from a dev perspective
then requires devs to draw out the full tree and understand what is going
on (website devs, not the protocol implementors).

I'm sure it's possible to do everything I'm proposing with the existing
tree scheme, I just think the complexity is too high for it to actually
happen. I'm hopeful that the proposal still achieves everything that
browsers actually need from scheduling resources while making it much
easier to understand, implement and debug.

---

From: Patrick Meenan <[email-masked]>
Date: Tue, 29 Jan 2019 09:55:36 -0500

I need to dig into the extensions mechanism a bit but does it require
negotiation (I would imagine it does to some level)? My main concern would
be to figure out how to pull off the prioritization without adding round
trips. If the new prioritization byte also made sense as a "weight" for
most implementations without breaking prioritization for servers that don't
understand the new scheme it might be possible to send the extension frame
and stuff the priorities into the weight field and still have servers that
don't understand the new prioritization do the right thing with the
existing trees.

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 29 Jan 2019 18:40:11 +0000

> I agree with Subodh that deadlines are very useful in QUIC, but I'm not convinced that clients are always in a better position to specify the deadline than servers.  If servers can specify the deadline, then we don't need to add them to priorities.

An example I have is a video player requesting the next DASH segment. The video player knows how much time is remaining before a buffering event will happen and can indicate this to the peer. However I think this could be separable from prioritization completely and could inform the scheduling of priorities.

Specifying a normative behavior of sequential scheduling in concurrency group 2, could be a bit limiting, and we could instead say that if an endpoint has some external information to guide scheduling within a concurrency group it may use that instead of sequential scheduling. Otherwise if we do add deadlines as a concept in the future we would have to use a completely different prioritization scheme which would be sad.

> I need to dig into the extensions mechanism a bit but does it require negotiation

One alternative is to use transport parameters, however that becomes tricky with shoving a bunch of HTTP related settings into transport parameters and also exposes the prioritization scheme being used in the clear. SETTINGs is probably the "right" way to do this even if it does take effect after 1-RTT and would probably have to specify what happens with the old priority frames.

Subodh
________________________________
From: Patrick Meenan <[email-masked]>
Sent: Tuesday, January 29, 2019 6:55 AM
To: Lucas Pardue
Cc: Mark Nottingham; HTTP Working Group
Subject: Re: HTTP/3 Prioritization Proposal

I need to dig into the extensions mechanism a bit but does it require negotiation (I would imagine it does to some level)? My main concern would be to figure out how to pull off the prioritization without adding round trips. If the new prioritization byte also made sense as a "weight" for most implementations without breaking prioritization for servers that don't understand the new scheme it might be possible to send the extension frame and stuff the priorities into the weight field and still have servers that don't understand the new prioritization do the right thing with the existing trees.

On Mon, Jan 28, 2019 at 5:21 PM Lucas Pardue <[email-masked]<mailto:[email-masked]>> wrote:
Hey Mark,

Lucas

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 29 Jan 2019 13:57:06 -0500

> (and I'm not sure about other implementations).

The current prioritization scheme in HTTP/3 (I am referring to the
current draft at version 18 [1]) uses placeholders, which solve
this exact problem.  The client no longer has to rely on hope.

Are there other problems the current prioritization scheme possesses
that cannot be boiled down to "programming is hard?"  I agree with

> > preventing that better implementation happening?

For this proposal to be accepted at this late stage in the game, it
should be demonstrably, non-marginally better than the current
mechanism.  It may be better than HTTP/2; but I don't see how it is
better than HTTP/3 [1].

  - Dmitri.

1. https://tools.ietf.org/html/draft-ietf-quic-http-18

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 29 Jan 2019 13:58:32 -0500

> would actually implement it.

Which existing scheme do you mean: HTTP/2 or HTTP/3 [1]?  If the
latter, why do you prefer the new proposal?

  - Dmitri.

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 30 Jan 2019 04:40:25 +0900

Ok, Dmitri's hit the nail of my thought  here so I'll be explicit

You might be able to achieve close to Pat's target design by declaring a
certain number of placeholders and assigning weights to them, meanwhile
ignoring other priority types in H3.

There are, of course, other options in this space. The elephant in the room
of the discussion is negotiang this stuff.

---

From: Patrick Meenan <[email-masked]>
Date: Tue, 29 Jan 2019 14:53:55 -0500

As far as I can tell, the placeholder streams serve to handle the Firefox
use case of using idle streams for groupings, not to eliminate the need to
synchronize tree states. When you chain streams after each other (the
Chrome case) you need to make sure the stream you are attaching to is still
known by the server. It is, of course, solvable by either a FIN/ACK before
deleting completed streams or the server keeping completed streams long
enough that the client will know they are completed (something larger than
BDP).

If the bar is too high this late in the process to change things then
that's fine and we can revisit it later with extension frames or HTTP/4 in
a few years. My hope was to introduce something that was easy enough to
plug into existing browser and server architectures that it would be able
to be used effectively. Yes, "programming is hard" but if that difficulty
prevents effective adoption and utilization of the protocol then it becomes
a problem for everyone.

On Tue, Jan 29, 2019 at 2:40 PM Lucas Pardue <[email-masked]>
wrote:

> There are, of course, other options in this space. The elephant in the
> room of the discussion is negotiang this stuff.
>

---

From: Patrick McManus <[email-masked]>
Date: Tue, 29 Jan 2019 15:09:22 -0500

On Tue, Jan 29, 2019 at 2:56 PM Patrick Meenan <[email-masked]> wrote:

> use case of using idle streams for groupings,
>

 yes.. and you can probably solve for that in a simpler way by having an
explicit set of groups with simple ways to share between them.

But what I think you really need to do with your proposal is address what
you're giving up by removing the tree structure because it was an explicit
choice to include it.

That structure exists because Google convinced the WG that it was important
to be able to combine an arbitrarily large number of sets of streams
together fairly. (and the solution allowed generalized sharing, not just
fairness).

In short, if you've got a set of streams from tabs A, B, and C you cannot
really expect them to be coordinated in an absolute priority sense - but if
they were all rooted at the same level in a tree they could share fairly
and then the streams within the tab could locally coordinate their priority.

This is a much more important property in an aggregator like a CDN who
might be bringing different front end connections into a single backend
connection.. the priority expressed by the client should exist in some ways
e2e (css before imgs!), but in other ways hop to hop (you don't want every
css to stall every browser's images).. the tree allows that.

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 30 Jan 2019 05:32:05 +0900

> explicit set of groups with simple ways to share between them.

The way I see it, H3 placeholders obsolete idle and unused streams. They
replace that with an abstract concept of a "thing" with no meaningful
default weight or dependecy parent (actual vals are 16 and root)

> you're giving up by removing the tree structure because it was an explicit

A tree of minimal depth (1-deep) could function pretty well. I think
addressing the gap from both sides cimould help identify it's size. Is the
size large due to following points quoted text?

> That structure exists because Google convinced the WG that it was
> important to be able to combine an arbitrarily large number of sets of
> streams together fairly. (and the solution allowed generalized sharing, not
> just fairness).
>

---

From: Patrick McManus <[email-masked]>
Date: Tue, 29 Jan 2019 15:51:41 -0500

probably.. I agree that a lot of the complexity comes from the infinite
generalization of the current design.. a depth of 1 and a settings-able
width with a decent default might get you a long way.

On Tue, Jan 29, 2019 at 3:32 PM Lucas Pardue <[email-masked]>
wrote:

>>> As far as I can tell, the placeholder streams serve to handle the
>>> Firefox use case of using idle streams for groupings,
>>>
>>

---

From: Patrick Meenan <[email-masked]>
Date: Tue, 29 Jan 2019 16:10:59 -0500

The tabs case always kind of fell apart when we tried to actually implement
anything because there isn't always a 1:1 relationship between requests and
tabs (multiple tabs may be waiting for the same request) so every request
needed to be managed directly anyway.

The aggregation/tunneling case does lend itself much better to the trees
though fundamentally it is a case of having a separate placeholder for each
aggregated connection so you can balance between the overall connections
and doesn't actually require a full tree (though as you start stacking
tunnels on top of each other you essentially end up with that anyway). We
could probably solve it by building trees of placeholders only and each
placeholder used something like the scheme I proposed but at that point
you're building trees anyway and maybe the added simplicity isn't there.

Thanks for the use case, that helps clear up the need for something more
complex. I'll redirect my efforts to see how complicated it would be to
build something that functions better than we're using today with the
current tree mechanism. It doesn't necessarily make it any easier for
Safari to plumb through into their current priority scheme but I don't know
what challenges they are having with plumbing it between WebKit and the OS
networking stack.

On Tue, Jan 29, 2019 at 3:51 PM Patrick McManus <[email-masked]>
wrote:

>>> But what I think you really need to do with your proposal is address
>>> what you're giving up by removing the tree structure because it was an
>>> explicit choice to include it.
>>>
>>
>>> In short, if you've got a set of streams from tabs A, B, and C you
>>> cannot really expect them to be coordinated in an absolute priority sense -
>>> but if they were all rooted at the same level in a tree they could share
>>> fairly and then the streams within the tab could locally coordinate their
>>> priority.
>>>

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 29 Jan 2019 16:13:46 -0500

On Tue, Jan 29, 2019 at 02:53:55PM -0500, Patrick Meenan wrote:
> known by the server.

The solution is to use placeholders: do not make one stream depend
on another, but put a placeholder in between.

    Some Node -> Stream A -> Placeholder X -> Stream B

If Stream A goes away, Stream B is not moved:

    Some Node -> Placeholder X -> Stream B

  - Dmitri.

---

From: Patrick Meenan <[email-masked]>
Date: Tue, 29 Jan 2019 16:37:50 -0500

I don't see how that would help for the Chrome linear-list case where
streams of the same "priority" are attached to the end of the last stream
with the same "priority" (and ahead of streams with a lower priority).

Root -> Placeholder X -> Stream A -> Placeholder Y -> Stream B ->
Placeholder Z -> Stream C

If you want to insert Stream D after Stream B you would literally need a
placeholder between EVERY stream and they would have to live forever,
otherwise you risk trying to attach to a placeholder or stream that may
have already completed. At that point you'll blow through any placeholder
limit and you may as well keep all of the stream ID's indefinitely. You
can't sparsely populate the placeholders because you don't know where you
will be inserting future streams or what previous streams may be in-flight
when you go to do the insert. Even moving the placeholder to always
represent the "end" of a list would be racy relative to the stream that the
placeholder is currently attached to.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 29 Jan 2019 18:04:23 -0500

My point is that placeholders allow a fixed structure that
survives individual streams' lifetimes.  As for Chrome's lining
them all up in a single chain (this seems to be a bit extreme):
perhaps this is a case of "doctor it hurts when I do that?"
In this scenario, there may not be enough placeholders and, true,
one wouldn't be able to represent this -- but neither would the
scheme you propose, which does not have dependencies at all.

The type of prioritization your proposal put forth can be
achieved -- or something close thereto -- using placeholders,
dependencies, and weights of the current prioritization mechanism.
In other words, clients can use this type of dependency-less
prioritization now.

  - Dmitri.

---

From: Patrick Meenan <[email-masked]>
Date: Tue, 29 Jan 2019 18:47:13 -0500

The sequential ordering of resources is intentional and desired for pretty
much everything except for images. Scripts and CSS loaded in the order that
they block the parser using 100% of the bandwidth lets you pipeline the
loading and parse/execution so you can be executing the first script while
the second is transferring. If you load them concurrently then they all
complete at the same time (later than individual ones) and then you need to
do the parse/execution of all of them. The Chrome chaining of requests is
to achieve exactly that while the Safari and Firefox models end up with the
parallel loading and sharing of bandwidth (but they do better for images
which benefit from parallel loading). This is a real problem in the field
today where things discovered late that get inserted early in the chain
(visible images or fonts) try to attach to a stream that already finished
from the server's perspective, miss, and attach to the root with a low
weight, effectively making them the lowest priority resource instead of
highest.

My proposal explicitly allowed for that with the "no cuncurrency" groups
which transfer resources sequentially by stream ID using 100% of the
bandwidth. The ordering is based on the order requested (which is normally
the order they are in the document as discovered by the parser) and if
something needs to jump ahead it can be given a higher priority bin.

On Tue, Jan 29, 2019 at 6:04 PM Dmitri Tikhonov <[email-masked]>
wrote:

> Firefox
> > > > use case of using idle streams for groupings, not to eliminate the
> need
> > > to

---

From: Mike Bishop <[email-masked]>
Date: Wed, 30 Jan 2019 02:56:52 +0000

Cliff Notes of extensions:

  *   Optional-to-understand frames can be sent without negotiation; optionally also negotiate to discover there’s no point in sending more of them after the connection is established.
  *   Mandatory-to-understand frames need to be negotiated first

I could imagine a model in which the client sends priority in all schemes it supports in the first flight, then picks one of them to continue with once it sees which ones the server supports.  That makes the overall state on the server somewhat fluid, however.

From: Patrick Meenan <[email-masked]>
Sent: Tuesday, January 29, 2019 11:56 PM
To: Lucas Pardue <[email-masked]>
Cc: Mark Nottingham <[email-masked]>; HTTP Working Group <[email-masked]>
Subject: Re: HTTP/3 Prioritization Proposal

Lucas

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 30 Jan 2019 12:07:14 +0900

On Wed, 30 Jan 2019, 08:47 Patrick Meenan <[email-masked]

> something needs to jump ahead it can be given a higher priority bin.

With H3 we need to be slightly careful, IMO requests will be handled in the
order of (received  + QPACK dependencies resolved). The removal of
exclusive is a logical concession.  Current priority language allows for
PRIORITY to be sent before the HEADERS on a request stream. This alleviates
some client concerns but not all.

The number of placeholders is a QUIC varint. The number of requests in a
connection is limited by stream ID ( varint modulo 4). It might be possible
to implement a Dmitri's tree design bit whether is logical is a different
question...

Lucas

---

From: Amos Jeffries <[email-masked]>
Date: Wed, 30 Jan 2019 17:30:48 +1300

On 30/01/19 12:47 pm, Patrick Meenan wrote:
> The sequential ordering of resources is intentional and desired for
> pretty much everything except for images. Scripts and CSS loaded in the
> order that they block the parser using 100% of the bandwidth lets you
> pipeline the loading and parse/execution so you can be executing the
> first script while the second is transferring. If you load them
> concurrently then they all complete at the same time (later than
> individual ones) and then you need to do the parse/execution of all of
> them. The Chrome chaining of requests is to achieve exactly that while
> the Safari and Firefox models end up with the parallel loading and
> sharing of bandwidth (but they do better for images which benefit from
> parallel loading). This is a real problem in the field today where
> things discovered late that get inserted early in the chain (visible
> images or fonts) try to attach to a stream that already finished from
> the server's perspective, miss, and attach to the root with a low

Ah. That last sentence.

IIRC, it was intended that such last-minute discovered be given a choice
of higher weight explicitly in their HEADERS priority field suitable for
resolving this last-place position within the other streams active at
the time. The client agent (Browser) is the only agent with full
knowledge about whether this new discovery is a blocking object or just
a background load sufficient.

The weight re-allocation prescribed on parent stream closure fixes up
any discrepancy from in-transit completions[1]. Then if one actually
cares about the sync a PRIORITY can explicitly realign to exact values
as needed by the client. Though in the later case traffic delivery (and
thus stream turnover) is expected to most often be so fast as to not
matter much in that regard.

[1] My personal preference is still to leave weights as static values
only changed by PRIORITY to make predictions by the client about server
state much more reliable.

Amos

---

From: Amos Jeffries <[email-masked]>
Date: Wed, 30 Jan 2019 17:29:50 +1300

On 30/01/19 3:56 pm, Mike Bishop wrote:
>   * Optional-to-understand frames can be sent without negotiation;
>     optionally also negotiate to discover there’s no point in sending
>     more of them after the connection is established.
> I could imagine a model in which the client sends priority in all
> schemes it supports in the first flight, then picks one of them to
> continue with once it sees which ones the server supports.  That makes
> the overall state on the server somewhat fluid, however.
> 

For an optional extension the server which does not implement would
treat any first-flight priorities in the base specification manner. One
that does can start using the clients preferred way immediately.

So from the client perspective it can be predictable - albeit more
memory state to manage until the (non-)use is confirmed by arrival of
the initial server SETTINGS frame.

In theory, if one wants to put in the planning work ahead of time the
weight field values might be made dual-purpose such that re-assigning
early flight streams with PRIORITY frames is not necessary regardless of
chosen interpretation of those 8 bits.

Amos

---

From: Patrick Meenan <[email-masked]>
Date: Wed, 30 Jan 2019 08:43:38 -0500

Another what-if thought. May be more complication than originally thought
but what it:

- Only PLACEHOLDER streams can be parents of streams so that the tree
structure can only be defined by PLACEHOLDERs (let's call them "GROUPS" for
the purpose of this discussion).
- Groups can only be parents to either other groups or streams but not both
(i.e. only leaf nodes can contain streams).
- The weights on groups continue to operate the way they do today with
bandwidth being split between groups based on their weight relative to the
bandwidth available at that point in the tree.
- The weights on streams are changed to be a priority instead (as defined
by the priority proposal).
- The root is an implicit group "0" that behaves like all other groups (can
only contain either groups or streams).

That would allow for easy aggregation of clients/tabs/CONNECT
streams/whatever or for splitting bandwidth between websockets, video
streams and http objects.  It would also make it more explicit that the
structure and streams are separate from each other.

On Tue, Jan 29, 2019 at 6:47 PM Patrick Meenan <[email-masked]> wrote:

> On Tue, Jan 29, 2019 at 6:04 PM Dmitri Tikhonov <
> [email-masked]> wrote:
>
>> > > > Chrome case) you need to make sure the stream you are attaching to
>> is
>> > > still
>> > > > known by the server.
>> > >

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 30 Jan 2019 23:14:44 +0900

Clarification question:

Is your what if thinking based on H3, or did you have H2 in mind for this.

H3 already has the mechanics to articulate a scheme like this, we'd just
need some different rules about what is allowed to be a PRIORITY frame
target.

The other reason I ask is because H3 placeholders are just a logical
construct already, divorced from concerns about stream lifetime management.
But as FF has shown, you can achieve that kind of design in H2 with streams.

On Wed, 30 Jan 2019, 22:47 Patrick Meenan <[email-masked] wrote:

> - Groups can only be parents to either other groups or streams but not
> both (i.e. only leaf nodes can contain streams).
> - The root is an implicit group "0" that behaves like all other groups
> (can only contain either groups or streams).
>
>> pipeline the loading and parse/execution so you can be executing the first
>> script while the second is transferring. If you load them concurrently then
>> they all complete at the same time (later than individual ones) and then
>> you need to do the parse/execution of all of them. The Chrome chaining of
>> requests is to achieve exactly that while the Safari and Firefox models end
>> up with the parallel loading and sharing of bandwidth (but they do better
>> for images which benefit from parallel loading). This is a real problem in
>> the field today where things discovered late that get inserted early in the
>> chain (visible images or fonts) try to attach to a stream that already
>> finished from the server's perspective, miss, and attach to the root with a
>> low weight, effectively making them the lowest priority resource instead of
>> highest.
>>

---

From: Patrick Meenan <[email-masked]>
Date: Wed, 30 Jan 2019 09:20:37 -0500

Primarily for H3. Essentially to remove the ability for streams to be
dependent on other streams and require any logical grouping be explicit.

It's kind of a merging of the existing spec and the proposal to have the
individual streams still used the proposed prioritization but to keep the
grouping offered by placeholders (and to remove the ability to do
dependencies with streams themselves).

On Wed, Jan 30, 2019 at 9:14 AM Lucas Pardue <[email-masked]>
wrote:

>>>> > > > use case of using idle streams for groupings, not to eliminate
>>>> the need
>>>> > > to
>>>> > > > Chrome case) you need to make sure the stream you are attaching
>>>> to is
>>>> > > still
>>>> > > > known by the server.
>>>> > >

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 30 Jan 2019 23:33:35 +0900

I like it and can see an easy way this could be specced up with a SETTING
that toggles the PRIORITY frame handling rule set. In other words, a
straightforward textual change, rather than a harder-to-do extension

On Wed, 30 Jan 2019, 23:20 Patrick Meenan <[email-masked] wrote:

>>> Another what-if thought. May be more complication than originally
>>> thought but what it:
>>>
>>> - The weights on streams are changed to be a priority instead (as
>>> defined by the priority proposal).
>>>> My proposal explicitly allowed for that with the "no cuncurrency"
>>>> groups which transfer resources sequentially by stream ID using 100% of the

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 30 Jan 2019 11:37:50 -0500

> The sequential ordering of resources is intentional and desired for pretty
---- 8< ----
> weight, effectively making them the lowest priority resource instead of

Thank you for the explanation.

> which transfer resources sequentially by stream ID using 100% of the
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This is what really differentiates this proposal.  The current
prioritization mechanism does not have a way to order streams by
their IDs.  This behavior would be difficult to mimic using just
the placeholders, so I take back what I stated in my previous
email.

> something needs to jump ahead it can be given a higher priority bin.

Your proposal is custom-made for Chrome's use case, but it drops
the tree structure that may be useful for CDNs, as described in
a different email in this thread.  (It is interesting that Chrome
chooses to use the linear list model even with the problem we are
discussing.  Note that using placeholders would alleviate at least
the problem of reparenting at the root node, which would be
strictly better than HTTP/2.)

We could take the idea of prioritization by stream ID and add it
to the current prioritization scheme, thereby keeping the tree
and making it possible to construct linear dependency lists.  For
example, we have four unused bits in the PRIORITY frame [1].  We
can take one bit to mean "weigh by stream ID" or the like.

  - Dmitri.

1. https://tools.ietf.org/html/draft-ietf-quic-http-18#section-4.2.3

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 30 Jan 2019 11:49:30 -0500

On Wed, Jan 30, 2019 at 12:07:14PM +0900, Lucas Pardue wrote:
> With H3 we need to be slightly careful, IMO requests will be
> handled in the order of (received  + QPACK dependencies resolved).

This is a good point and something to keep in mind.

> The number of placeholders is a QUIC varint. The number of requests
> in a connection is limited by stream ID ( varint modulo 4). It
> might be possible to implement a Dmitri's tree design bit whether
> is logical is a different question...

By "Dmitri's tree design," do you mean "keeping a placeholder between
streams in the priority tree?"

I did think about what clients may use placeholders for when I was
writing the priority tree code and I realized that the recommended
value of 16 may be too low; you want something like 1:2 or even 1:1
placeholder/stream ratio.  Thus, we have a default of 50 instead
of 16.

I have been meaning to write up my thoughts on the matter, but
haven't gotten around to it yet.

  - Dmitri.

1. https://github.com/litespeedtech/lsquic-client/blob/b7abc05c2408af247a70b4cb69a5a197225549c4/include/lsquic.h#L296

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 30 Jan 2019 11:54:46 -0500

> dependencies with streams themselves).

Do you want to remove the ability for streams to depend on each
other directly because of personal preference or is this technically
necessary?

  - Dmitri.

---

From: Patrick Meenan <[email-masked]>
Date: Wed, 30 Jan 2019 13:22:46 -0500

It's not technically necessary but it does eliminate the need to
synchronize trees for attaching to other streams. It's more of a clean-up
where we'd explicitly use placeholders for defining structure.