Subject: Re: Priority straw man

From: Martin Thomson <[email-masked]>
Date: Mon, 3 Feb 2014 09:44:50 -0800

I'm starting to get ready for -10, which I would very much like to push soon.

More feedback would be nice, but absent stronger feedback, I'm going
to push the button on this for -10.

p.s., The suggestion for PRIORITY on stream zero requires additional
changes and a little more support, so I'll ask for that to be tracked
separately.

On 26 January 2014 13:34, Martin Thomson <[email-masked]> wrote:
> As requested, a writeup on prioritization.
>
> As a pull request: https://github.com/http2/http2-spec/pull/364
>
> In HTML form:
> http://martinthomson.github.io/drafts/priority.html#StreamPriority
> http://martinthomson.github.io/drafts/priority.html#PRIORITY
>
> Comments or pull requests happily accepted.

---

From: Mike Bishop <[email-masked]>
Date: Mon, 3 Feb 2014 20:57:26 +0000

Your draft has this list of initial dependencies:  (A->0, B->A, C->A, D->B, E->C, F->0, G->A).  This creates the ordered list-of-buckets (A,F) <- (B,C,G) <- (D,E).  That makes sense in terms of building initial priorities.

What feels unclear is when a new priority is sent -- what happens when the client now sends C->G?

I see two reasonable approaches, both of which appear in agreement with the text:
  - (B,C,G) are a bucket.  Because C now depends on G, C moves to the next bucket (of things which depend on the bucket B,G) and the result is (A,F) <- (B,G) <- (D,E,C).
  - We've previously stated E->C, and nothing has changed that dependency.  The result is (A,F) <- (B,G) <- (D,C) <- (E).

Neither interpretation is entirely satisfying.  The first could require many PRIORITY frames to perform an insert in the list, but the second feels suspiciously like a tree, which you explicitly said it wasn't.

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]] 
Sent: Monday, February 3, 2014 9:45 AM
To: HTTP Working Group
Subject: Re: Priority straw man

More feedback would be nice, but absent stronger feedback, I'm going to push the button on this for -10.

p.s., The suggestion for PRIORITY on stream zero requires additional changes and a little more support, so I'll ask for that to be tracked separately.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 3 Feb 2014 13:06:05 -0800

> Neither interpretation is entirely satisfying.  The first could require many PRIORITY frames to perform an insert in the list, but the second feels suspiciously like a tree, which you explicitly sa…

Excellent point.  I think that the former is more in keeping with the
original intent.  I will add some text on reprioritization to cover
this, including the case where moving C empties the bucket.

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 4 Feb 2014 17:30:50 +0000

I also much prefer the former: it is more in the spirit of the proposal, and is much simpler than the later proposal.

However, as Mike said, it makes it hard to insert a new bucket in the middle of the list.
To go from (A, F) <- (B, C, G) <- (D, E)
To (A, F) <- (H) <- (B, C, G) <- (D, E), many re-prioritization are necessary.

I propose to use the reserved flag in the priority information to indicate that a new dependency creates a new bucket.
In this way, to obtain the previous change, it is only necessary to send the dependency H->A with the flag set.

I sent a pull request containing all these changes: https://github.com/http2/http2-spec/pull/375.

Hervé.

> Sent: lundi 3 février 2014 22:06
> To: Mike Bishop
> Cc: HTTP Working Group
> > Your draft has this list of initial dependencies:  (A->0, B->A, C->A, D->B, E->C,
> F->0, G->A).  This creates the ordered list-of-buckets (A,F) <- (B,C,G) <- (D,E).
> That makes sense in terms of building initial priorities.
> >
> >   - (B,C,G) are a bucket.  Because C now depends on G, C moves to the next
> bucket (of things which depend on the bucket B,G) and the result is (A,F) <-
> (B,G) <- (D,E,C).
> >   - We've previously stated E->C, and nothing has changed that dependency.
> The result is (A,F) <- (B,G) <- (D,C) <- (E).
> >
> > Neither interpretation is entirely satisfying.  The first could require many
> PRIORITY frames to perform an insert in the list, but the second feels
> suspiciously like a tree, which you explicitly said it wasn't.
>

---

From: Martin Thomson <[email-masked]>
Date: Tue, 4 Feb 2014 09:36:33 -0800

> To (A, F) <- (H) <- (B, C, G) <- (D, E), many re-prioritization are necessary.

Yes, this is true.  A more important question is whether this is a
feature that is important enough to justify the additional complexity.

---

From: Osama Mazahir <[email-masked]>
Date: Tue, 4 Feb 2014 20:16:41 +0000

Priority is definitely useful when you have more DATA to send than network capacity.  However, Microsoft has no interest in implementing dependencies; neither advertising nor honoring across IE, IIS, client stack APIs and server stack APIs.

Being able to express an ordering relation is valuable but the approach should be more decoupled from the stream lifecycle and more stateless on the server.  Below is our feedback and suggested changes.  The one-liner explanation of the change is: replace the Stream Dependency field with a numerical priority field.  

Certain details, such as the bit widths (X, Y and Z), are purposefully omitted to keep the focus on design.

==== OVERVIEW

- A stream is assigned to a group
- A stream is assigned a priority that represents its importance, with respect to other streams, within its group
- A group is identified by a group ID
- A group is assigned a weight that represents its importance, with respect to other groups, within its connection

The client knows the relative importance of streams and is trying to convey a simple representation of that information to the server so that the server can choose to allocate resources more intelligently.  Priorities and weights are merely advisory and do not guarantee any specific server behavior.  

Group weight defines a proportional definition of importance with respect to other groups.  For example, if Group1, Group2 and Group3 are assigned weights 1, 3 and 6, then ideally they receives 10%, 30% and 60% of the resources, respectively. 

Within a group, stream priority defines a strict ordering of importance.  If two streams have the same priority then their resource assignment is server implementation specific (e.g. round robin, shortest job next, first in first out, etc).

The PRIORITY frame payload (the same payload can also be included as part of the HEADERS frame) contains:
- Group ID        (X bits)
- Group Weight    (Y bits)
- Stream Priority (Z bits)

Similar to what it does currently, the payload assigns the given stream (from the encapsulating frame header) to the specified Group ID, sets the given Group Weight and assigns the stream the given Stream Priority within that group.

==== MOTIVATION

1) Robustness
This avoids the server from having to track relationship dependencies between streams.  Consequently, the design race where the a stream will close while prioritization information that creates a dependency on that stream is in transit is eliminated.  Which also eliminates having to maintain state about closed streams after closure (and all subsequent timer or load based purging).  Increasing the decoupling from the stream lifecycle is design goodness.

2) Changing a stream priority is clearer
In the case where a stream has to be reprioritized, all its children need to be reprioritized to their new parent via new dependency advertisements.  With simple priority numbers, this becomes a simple one priority change operation.  See http://lists.w3.org/Archives/Public/ietf-http-wg/2014JanMar/0395.html

3) Simplicity
Simpler to describe.  Simpler for basic server and proxies to implement.  Don't pay for complexity in the base cases.  The client is free to have arbitrarily complex prioritization determination schemes (e.g. not necessarily tied to rendering tree) and can afford to spend CPU/memory/etc on this.  

4) Equivalency
The tree examples used in the current issue #364 proposal can be represented using this weight+priority scheme.  Having Z bits (i.e. the Stream Priority width) will allow us to represent a tree of depth 2^Z.

5) Simple Priority Collapsing
Proxies, and perhaps servers, may want to limit the amount of concurrent priorities/depth they track.  Using numerical priorities opens the ability to have a stateless reduction/mapping.  For example, a proxy/server might do something like: internal_priority = wire_priority >> 3.

---

From: Michael Sweet <[email-masked]>
Date: Tue, 04 Feb 2014 15:55:06 -0500

+1

Seems like this will work for both client->server and client(s)->proxy->server(s) without too much effort in the proxy, and it gives us a simple method of grouping priorities to prevent starvation.

>> Comments or pull requests happily accepted.

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 6 Feb 2014 09:46:36 +0000

From my understanding, a good download order for resources is:
- Javascript first, one resource at a time, in document order;
- CSS
- Media, possibly in parallel, as with progressive encoding, this allows early partial rendering.

This means that a specific ordering is desirable, but it may not be the document order, in particular because there are good reasons to put the Javascripts at the end of the document.

So I think that this feature is important.

Hervé.

> Sent: mardi 4 février 2014 18:37
> To: RUELLAN Herve
> Cc: Mike Bishop; HTTP Working Group

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Thu, 6 Feb 2014 22:59:53 +0900

On Feb 4, 2014, at 3:16 PM, Osama Mazahir <[email-masked]> wrote:

> Priority is definitely useful when you have more DATA to send than
network capacity.  However, Microsoft has no interest in implementing
dependencies; neither advertising nor honoring across IE, IIS, client stack
APIs and server stack APIs.
>
> Being able to express an ordering relation is valuable but the approach
should be more decoupled from the stream lifecycle and more stateless on
the server.  Below is our feedback and suggested changes.  The one-liner
explanation of the change is: replace the Stream Dependency field with a
numerical priority field.

+1

I prefer Osama's proposal. Without relying on "ghost" streams is a good
property.
The complexity of dependency is only paid by the client that wants it and
server just uses the numerical value. Also the simple browser which uses
static priority based on content type works fine without additional
priority adjustment which described in
http://lists.w3.org/Archives/Public/ietf-http-wg/2014JanMar/0415.html

Best regards,
Tatsuhiro Tsujikawa

On Wed, Feb 5, 2014 at 5:55 AM, Michael Sweet <[email-masked]> wrote:

> +1
>
> Seems like this will work for both client->server and
> client(s)->proxy->server(s) without too much effort in the proxy, and it
> gives us a simple method of grouping priorities to prevent starvation.
>
>
> > Priority is definitely useful when you have more DATA to send than
> network capacity.  However, Microsoft has no interest in implementing
> dependencies; neither advertising nor honoring across IE, IIS, client stack
> APIs and server stack APIs.
> >
> > Being able to express an ordering relation is valuable but the approach
> should be more decoupled from the stream lifecycle and more stateless on
> the server.  Below is our feedback and suggested changes.  The one-liner
> explanation of the change is: replace the Stream Dependency field with a
> numerical priority field.
> >
> > - A stream is assigned a priority that represents its importance, with
> respect to other streams, within its group
> > - A group is assigned a weight that represents its importance, with
> respect to other groups, within its connection
> >
> > The client knows the relative importance of streams and is trying to
> convey a simple representation of that information to the server so that
> the server can choose to allocate resources more intelligently.  Priorities
> and weights are merely advisory and do not guarantee any specific server
> behavior.
> >
> > Group weight defines a proportional definition of importance with
> respect to other groups.  For example, if Group1, Group2 and Group3 are
> assigned weights 1, 3 and 6, then ideally they receives 10%, 30% and 60% of
> the resources, respectively.
> >
> > Within a group, stream priority defines a strict ordering of importance.
>  If two streams have the same priority then their resource assignment is
> server implementation specific (e.g. round robin, shortest job next, first
> in first out, etc).
> >
> > Similar to what it does currently, the payload assigns the given stream
> (from the encapsulating frame header) to the specified Group ID, sets the
> given Group Weight and assigns the stream the given Stream Priority within
> that group.
> >
> >
> > ==== MOTIVATION
> >
> > 1) Robustness
> > This avoids the server from having to track relationship dependencies
> between streams.  Consequently, the design race where the a stream will
> close while prioritization information that creates a dependency on that
> stream is in transit is eliminated.  Which also eliminates having to
> maintain state about closed streams after closure (and all subsequent timer
> or load based purging).  Increasing the decoupling from the stream
> lifecycle is design goodness.
> >
> > In the case where a stream has to be reprioritized, all its children
> need to be reprioritized to their new parent via new dependency
> advertisements.  With simple priority numbers, this becomes a simple one
> priority change operation.  See
> http://lists.w3.org/Archives/Public/ietf-http-wg/2014JanMar/0395.html
> >
> > 3) Simplicity
> > Simpler to describe.  Simpler for basic server and proxies to implement.
>  Don't pay for complexity in the base cases.  The client is free to have
> arbitrarily complex prioritization determination schemes (e.g. not
> necessarily tied to rendering tree) and can afford to spend CPU/memory/etc
> on this.
> >
> > 4) Equivalency
> > The tree examples used in the current issue #364 proposal can be
> represented using this weight+priority scheme.  Having Z bits (i.e. the
> Stream Priority width) will allow us to represent a tree of depth 2^Z.
> >
> > Proxies, and perhaps servers, may want to limit the amount of concurrent
> priorities/depth they track.  Using numerical priorities opens the ability
> to have a stateless reduction/mapping.  For example, a proxy/server might
> do something like: internal_priority = wire_priority >> 3.
> >
> >

---

From: Peter Lepeska <[email-masked]>
Date: Thu, 6 Feb 2014 11:44:12 -0500

I like the way that the dependencies give us additional information about
the way that the page is constructed. This information can be useful for
various applications I can think of. However, if this is our goal:

"The purpose of prioritization is to allow an endpoint to express how it
would prefer its peer allocate resources when managing concurrent streams.
Most importantly, priority can be used to select streams for transmitting
frames when there is limited capacity for sending."

Then I can't think of anything that the dependency-based approaches allows
us to do that cannot also be accomplished via Osama's proposal and I agree
with the five benefits he outlines.

Can anyone else think of a benefit to the dependency-based approach from
the perspective of allowing an endpoint to express how it would prefer its
peers to allocate network resources?

Thanks,

Peter

On Thu, Feb 6, 2014 at 8:59 AM, Tatsuhiro Tsujikawa
<[email-masked]>wrote:

>> > Within a group, stream priority defines a strict ordering of
>> importance.  If two streams have the same priority then their resource
>> assignment is server implementation specific (e.g. round robin, shortest
>> job next, first in first out, etc).
>> >
>> > Simpler to describe.  Simpler for basic server and proxies to
>> implement.  Don't pay for complexity in the base cases.  The client is free
>> to have arbitrarily complex prioritization determination schemes (e.g. not
>> > Proxies, and perhaps servers, may want to limit the amount of
>> concurrent priorities/depth they track.  Using numerical priorities opens
>> the ability to have a stateless reduction/mapping.  For example, a
>> proxy/server might do something like: internal_priority = wire_priority >>
>> 3.
>> >
>> >

---

From: William Chan (陈智昌) <[email-masked]>
Date: Fri, 7 Feb 2014 14:46:54 -0800

Thanks for the proposal Osama!

Overall, I like this proposal. It incorporates a lot of our feedback
about the problems we've identified with the existing prioritization
mechanism. It is simpler in terms of protocol understanding, although
it has some other complexity costs, namely in usage, at least on the
client. I am hesitant to claim that this proposal is strictly better
or worse than our stream dependencies proposal, because I see some of
the appeal of keeping it simple. Let me point out some downsides and
things to consider:

* From a client perspective, when you only have priority levels, it
becomes harder to decide how to allocate the priority level ranges.
During dynamic request allocation (for example, during web document
parsing), it's common to want to insert a request at a priority level
in between two other requests. document.write() is an obvious example
of this. And let's be clear, this is extremely common in web
documents, and even more common with web apps where much more of the
loading occurs dynamically using scripts. A dependency list makes this
elegant since you simply need a list insertion operation. With integer
priority levels, now you have to pre-plan the integer ranges and leave
spaces in between to allow insertion of stream priorities in between
different streams. And it's unclear where to insert it...halfway in
the priority range between two streams? When we get it wrong, we may
need to blast out a lot of PRIORITY frames to correct this.
* Also from a client perspective, how do you describe a pipeline of
ordered resources? Video frames are the obvious example. You want
frame 1 before frame 2 before etc.
* Let's now make it more complicated. What happens when you fast
forward or rewind in the video? What happens when you scroll within a
loading document? How do you dynamically reprioritize large numbers of
streams?
* What's WinInet's API going to look like? Is it going to punt
knowledge/responsibility of HTTP/2 priority levels out to the
application, and let the application decide how to heuristically
assign these priorities?

By keeping the protocol semantics simple, we impose more burden on
application developers to utilize heuristics to assign priorities. Is
it the right tradeoff?

I think that HTTP/2 removes the need for many browser/client-side
heuristics which is a great thing. I'd like to remove more of them. I
think that this new proposal is a step in the right direction, but it
doesn't go as far as I'd like. But I wholeheartedly approve of it as
an improvement over what currently exists in the spec.

Cheers.

On Thu, Feb 6, 2014 at 8:44 AM, Peter Lepeska <[email-masked]> wrote:
> Can anyone else think of a benefit to the dependency-based approach from the
> perspective of allowing an endpoint to express how it would prefer its peers
> to allocate network resources?
>
> Thanks,
>
> Peter
>
>
> On Thu, Feb 6, 2014 at 8:59 AM, Tatsuhiro Tsujikawa <[email-masked]>
> wrote:
>>
>>
>> > should be more decoupled from the stream lifecycle and more stateless on the
>> > server.  Below is our feedback and suggested changes.  The one-liner
>> static priority based on content type works fine without additional priority
>> adjustment which described in
>>> > should be more decoupled from the stream lifecycle and more stateless on the
>>> > server.  Below is our feedback and suggested changes.  The one-liner
>>> > convey a simple representation of that information to the server so that the
>>> > server can choose to allocate resources more intelligently.  Priorities and
>>> > weights are merely advisory and do not guarantee any specific server
>>> > behavior.
>>> >
>>> > assignment is server implementation specific (e.g. round robin, shortest job
>>> > next, first in first out, etc).
>>> >
>>> > or load based purging).  Increasing the decoupling from the stream lifecycle
>>> > is design goodness.
>>> >

---

From: Martin Thomson <[email-masked]>
Date: Fri, 7 Feb 2014 15:30:37 -0800

Just to clarify:

what I wrote up (stream dependencies) > osama's simplification
(priority instead of depedencies) >> the crap in -09

And maybe I can infer also:

something with better insertion, like Herve's suggestion > what I wrote up

---

How realistic do you imagine this video scenario to be?  Seeking
hurts, but that's enough of a specialized scenario that I think I'm
willing to suggest that it's going to need application-specific
interactions to get "right" anyway.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 7 Feb 2014 15:42:09 -0800

The usecase seems likely to me... ;)

Given experience with SPDY, I'm strongly convinced that we need to think of
this from the perspective of the proxy, which would be forced to do
substantially suboptimal things with any proposal which doesn't offer a
'linkable' ordering (i.e. representable as operations to a list or tree)
with multiple roots.

This problem can become painful if we stick to "simple" numeric
priorities-- Imho, we very much trade off some minor simplicity in the
specification for mountains of machinery.
I'd be perfectly happy to see some clients ignore whatever they believe to
be complicated and stick to a strict-priority scheme (which the proposal
from the interim supported) and allow proxies to utilize the mechanism to
solve the very real problem there.

Remember that this proposal was borne out of the pain we experienced when
deploying a proxy: it is not theoretical.
-=R

On Fri, Feb 7, 2014 at 3:30 PM, Martin Thomson <[email-masked]>wrote:

> >>>> > Certain details, such as the bit widths (X, Y and Z), are
> purposefully
> >>>> > omitted to keep the focus on design.
> >>>> >
> >>>> > ==== OVERVIEW
> >>>> >
> >>>> > I'm starting to get ready for -10, which I would very much like to
> push
> >>>> > soon.
> >>>> >
> >>>> > More feedback would be nice, but absent stronger feedback, I'm
> going to
> >>>> > push the button on this for -10.
> >>>> >

---

From: Jeff Pinner <[email-masked]>
Date: Fri, 7 Feb 2014 16:07:06 -0800

I like the simplified state management with Osamas proposal, but I worry that
removing dependencies causes us to need to fall back to heuristics to achieve
the same effect, and that those will be much harder to "get right." And
should there be more stream dependency links than priority levels than
instead of simplifying the state management you simply move it to the
client as it has to reprioritize as streams close to achieve the same
effect.

On Fri, Feb 7, 2014 at 3:42 PM, Roberto Peon <[email-masked]> wrote:

> Given experience with SPDY, I'm strongly convinced that we need to think
> of this from the perspective of the proxy, which would be forced to do
>> >>>> > The PRIORITY frame payload (the same payload can also be included
>> as
>> >>>> > part of the HEADERS frame) contains:
>> >>>> > - Group ID        (X bits)
>> >>>> > - Group Weight    (Y bits)
>> >>>> > On 26 January 2014 13:34, Martin Thomson <[email-masked]
>> >
>> >>>> > wrote:

---

From: William Chan (陈智昌) <[email-masked]>
Date: Fri, 7 Feb 2014 18:32:27 -0800

Jeff, do you mind clarifying your position? I think we can infer it
given your sentence structure, but it'd be nice if you explicitly
said, between the simplified state management and removing the need to
rely on heuristics, which one you valued more. I think everyone can
appreciate the tradeoff we need to make here, and it's important to
identify which one people find most important. I for one think the
richer protocol semantics are worth the implementation burden.

It's somewhat interesting to hear Roberto's description of proxies'
need of stream dependencies, as it conflicts with Microsoft's
description of the situation, and they both operate proxies. I say
only somewhat, because Roberto has previously voiced similar concerns
on many occasions. My understanding of Roberto's concerns is because
proxies take many many many users' flows and multiplex them over the
same connections to a gateway's backends, richer protocol semantics
between the gateway and the backends would help out significantly.
It'd be interesting to hear Microsoft's discussion of the same issues
and why they believe that a simpler protocol with simpler semantics is
overall less complexity. Do they simply have different uses? My
understanding is that they also encounter these gateway concerns (not
to mention forward proxy issues), so it's intriguing to see their
evaluation of these protocol mechanisms. I'm surprised to see so clear
a signal that they're so willing to accept implementation heuristic
complexity in order to have simpler protocol mechanics.

Martin, as far as the video scenario goes, I think it happens,
although not necessarily that often. Seeking is very common, but I
suspect that it wouldn't significantly affect the user experience if,
upon a seek, the user agent simply cancelled previous resource
requests and initiated new ones. That said, I think that video seeking
is just one example of a common trend of more dynamic loading and
reprioritization. I may very possibly be wrong here, but my instinct
is that this is the direction that HTTP usage is moving towards, and
it would be rather short-sighted to assume ignore such dynamic and
real-time request prioritization / reprioritization desires, which in
general would be better suited by direct protocol semantic
equivalents, rather than heuristic translations.

Also, as far as Herve's suggestion for insertion, I don't have a
concrete opinion yet. I personally view that as within the level of
marginal benefit/cost that it's not worth fighting much over. I'm more
interested in discussing the dependencies vs priority levels issue.

Cheers! Happy weekend y'all.

On Fri, Feb 7, 2014 at 4:07 PM, Jeff Pinner <[email-masked]> wrote:
> I like the simplified state management with Osamas proposal, but I worry
> that removing dependencies causes us to need to fall back to heuristics to
> achieve the same effect, and that those will be much harder to "get right."
> And should there be more stream dependency links than priority levels than
> instead of simplifying the state management you simply move it to the client
> as it has to reprioritize as streams close to achieve the same effect.
>
>
>>> >>>> > On 26 January 2014 13:34, Martin Thomson
>>> >>>> > <[email-masked]>
>>> >>>> > wrote:

---

From: Michael Sweet <[email-masked]>
Date: Sat, 08 Feb 2014 11:41:22 -0500

Roberto,

The advantage of the priority groups that Osama proposed is that they "balance" automatically across all of the active groups maintained by the proxy.  The only thing you'll need to do is map the client group IDs to any active server connection your proxy is maintaining, rather than mapping all of the dependencies (1-deep vs. N-deep).

On Feb 7, 2014, at 6:42 PM, Roberto Peon <[email-masked]> wrote:

> Given experience with SPDY, I'm strongly convinced that we need to think of this from the perspective of the proxy, which would be forced to do substantially suboptimal things with any proposal which doesn't offer a 'linkable' ordering (i.e. representable as operations to a list or tree) with multiple roots.
> 
> This problem can become painful if we stick to "simple" numeric priorities-- Imho, we very much trade off some minor simplicity in the specification for mountains of machinery.
> I'd be perfectly happy to see some clients ignore whatever they believe to be complicated and stick to a strict-priority scheme (which the proposal from the interim supported) and allow proxies to utilize the mechanism to solve the very real problem there.
> 
> Remember that this proposal was borne out of the pain we experienced when deploying a proxy: it is not theoretical.
> -=R
> 
> 
> On Fri, Feb 7, 2014 at 3:30 PM, Martin Thomson <[email-masked]> wrote:
> Just to clarify:
>

---

From: Michael Sweet <[email-masked]>
Date: Sat, 08 Feb 2014 11:50:33 -0500

Jeff,

I look at the groups as relative QoS groups, e.g. group 1 needs 80% of the bandwidth and group 2 needs 20%.  And within each group you use the priority to determine the order of packet delivery.  And within the priority each client can determine an optimal subdivision of values to allow for insertion of new streams without painful re-prioritization.

Let's not make this every potential prioritization scheme, but rather focus on the common use cases and how they can be represented and implemented efficiently for the client/user agent, proxy, and server.  Exactly controlling the order of resource delivery is NOT a common requirement and can already be achieved through serialization by the client if it is really important.

On Feb 7, 2014, at 7:07 PM, Jeff Pinner <[email-masked]> wrote:

> I like the simplified state management with Osamas proposal, but I worry that removing dependencies causes us to need to fall back to heuristics to achieve the same effect, and that those will be much harder to "get right." And should there be more stream dependency links than priority levels than instead of simplifying the state management you simply move it to the client as it has to reprioritize as streams close to achieve the same effect.
> 
>

---

From: Jeff Pinner <[email-masked]>
Date: Sat, 8 Feb 2014 10:22:45 -0800

I will try to clarify my concerns and address Michael's response:

On Sat, Feb 8, 2014 at 8:50 AM, Michael Sweet <[email-masked]> wrote:

> Jeff,
>
> I look at the groups as relative QoS groups, e.g. group 1 needs 80% of the
> bandwidth and group 2 needs 20%.  And within each group you use the
> priority to determine the order of packet delivery.  And within the
> priority each client can determine an optimal subdivision of values to
> allow for insertion of new streams without painful re-prioritization.
>
>
Let's assume for sake of argument and simplicity we have 2 priority levels
(add more levels and add more streams and the point remains the same).
Let's also assume, as a proxy, we receive from some client two groups, each
with two streams:

G1 (80% w/ S1 (pri 0) and S3 (pri 1)) and G2 (20% w/ S5 (pri 0) and S7
(pri1))

If I need to proxy this to some backend, I will likely need to merge the
priority groups (as I have more incoming connections than outgoing
connections). So with "n" incoming connections, I will send to the backend
something like:

Gn (1/"n"% w S1, S3 (pri 0) and S5, S7 (pri 1))

Here I prioritize S3 now higher than S5 to ensure that the original G1
still gets more bandwidth, since otherwise if S1 closes, and if S5 had the
higher priority, G2 would get the majority of the bandwidth.

Once S1 does close, as a client I now need to re-prioritize S5 in order to
make sure that when S3 closes, S5 has a higher priority again than S7 --
basically on the client connection, I have to remember and re-introduce the
dependency information.

In contrast to dependencies, where the incoming request looks something
like:

G1 (80% w/ S1 <-- S3) and G2 (20% w/ S5 <-- S7)

I can proxy these approximately to the backend server as something like:

Gn (1/"n"% w S1 <-- S3 & S5 <-- S7)

Now when S1 closes, S3 and S5 share bandwidth and when S3 closes, S5 still
has higher priority than S7, without needing any re-prioritization.

Clearly re-prioritizing the incoming streams adds complexity, as does
re-weighting the groups. But I believe that even in these cases
dependencies become simpler to proxy than priorities because the relative
ordering is explicit.

Let's not make this every potential prioritization scheme, but rather focus
> on the common use cases and how they can be represented and implemented
> efficiently for the client/user agent, proxy, and server.  Exactly
> controlling the order of resource delivery is NOT a common requirement and
> can already be achieved through serialization by the client if it is really
> important.
>
>
Now you could always argue that the above example is not a common use case
or that the proxy could always fall back on ignoring priority. However I do
believe that multiplexing incoming connections over a single outgoing
connection is common and will become more so as HTTP/2 adoption increases.
As for ignoring priority, if the scheme we come up with is difficult enough
to proxy that proxies will end up ignoring it, then clients will fall back
on using heuristics.

Osama is completely correct that part of the difficulty in the
dependency-based priority scheme is having to track stream life cycles and
handling race conditions where stream dependency information arrives for
closed streams. This is also a concern I have that I would like to figure
out how to address.

>> I'd be perfectly happy to see some clients ignore whatever they believe
>> to be complicated and stick to a strict-priority scheme (which the proposal
>>> >>>> > I'm starting to get ready for -10, which I would very much like
>>> to push
>>> >>>> > soon.
>>> >>>> >
>>> >>>> > On 26 January 2014 13:34, Martin Thomson <
>>> [email-masked]>
>>> >>>> > wrote:

---

From: Michael Sweet <[email-masked]>
Date: Mon, 10 Feb 2014 08:10:46 -0500

Jeff,

On Feb 8, 2014, at 1:22 PM, Jeff Pinner <[email-masked]> wrote:
> Let's assume for sake of argument and simplicity we have 2 priority levels (add more levels and add more streams and the point remains the same). Let's also assume, as a proxy, we receive from some client two groups, each with two streams:
> 
> G1 (80% w/ S1 (pri 0) and S3 (pri 1)) and G2 (20% w/ S5 (pri 0) and S7 (pri1))
> 
> If I need to proxy this to some backend, I will likely need to merge the priority groups (as I have more incoming connections than outgoing connections). So with "n" incoming connections, I will send to the backend something like:

I don't see how this would necessarily follow.  A equally valid implementation would preserve the client's priority groups and create additional outgoing connections as needed should the group ID space be exhausted at a particular point in time.

> ...
> Clearly re-prioritizing the incoming streams adds complexity, as does re-weighting the groups. But I believe that even in these cases dependencies become simpler to proxy than priorities because the relative ordering is explicit.

True, however prioritization only truly addresses optimization of page delivery.  In today's typical video + static content web site world, priorities by themselves could easily cause resource starvation - Osama's weighted group proposal addresses that quite nicely and partitions the priorities into those groups where the re-prioritization problem is a lot simpler (or at least a lot less likely IMHO...)

> Now you could always argue that the above example is not a common use case or that the proxy could always fall back on ignoring priority. However I do believe that multiplexing incoming connections over a single outgoing connection is common and will become more so as HTTP/2 adoption increases. As for ignoring priority, if the scheme we come up with is difficult enough to proxy that proxies will end up ignoring it, then clients will fall back on using heuristics.

I agree on this point (which also applies to servers I think).

---

From: Martin Thomson <[email-masked]>
Date: Mon, 10 Feb 2014 10:01:51 -0800

> Gn (1/"n"% w S1 <-- S3 & S5 <-- S7)

Unless I misunderstand, that's not entirely correct.  The
prioritization schemes that both Will and I described wouldn't permit
that.  You would have to choose (S1, S3) <-- (S5, S7) or (S1, S5) <--
(S3, S7) or (S1) <-- (S3, S5) <-- (S7), or something like that.

In all cases, the end states produced by the dependency schemes Will
and I wrote up (I don't know what Roberto is talking about here) are
exactly equivalent to the scheme Osama described unless there are more
layers of dependencies than there are allowed priorities.

The real difference between the schemes is how they handle transitions
into the desired end state, particularly when an intermediary needs to
translate multiple ways between connections.

It seems to me that a dependency scheme has some advantages when it
comes to transitions (the video reprioritization thing, maybe some
proxy cases).  It may be that a dependency scheme also has advantages
when it comes to translating, but I'm not sure that it's a clear win
without full tree-based dependencies.  The cost of these purported
advantages is largely borne by the server, which has to deal with the
additional complexity of managing dead streams, garbage collection.

I'll also point out that we have to be careful not to raise the bar
too high for the server implementers, otherwise we will find that they
start ignoring priority more than we would like.  That creates
incentives for browsers to hold back requests, apply heuristics,
etc...

---

From: Mike Bishop <[email-masked]>
Date: Mon, 10 Feb 2014 18:36:51 +0000

Assuming I'm following correctly, Jeff's comments seem to reflect the tree model in Will's draft which had already been removed and isn't part of either proposal currently under discussion.  He would sent two unconnected chains of requests within a group, and expect them to be equally treated within that group's timeslice, regardless of the relative priorities of resources within each chain.  That's not possible with either proposal on the table currently, since as Martin notes the end results of both are equivalent.  The difference is strictly whether the collapsing of dependencies into a strict order happens on the client or server side of the connection.

I'm curious about his comment that he would have to merge priority groups on the back-end, though -- unlike stream IDs, it's not like they're exhausted once used.  As soon as a group is empty, you can reclaim it for more streams and a different user.  Part of the bikeshed on the number of bits will certainly be how many simultaneously-active groups you need available on the back-end, but that's orthogonal to how priorities within a group are expressed.

I've been envisioning the scenario working like this:
 - Server is allocating X% of back-end connection per user; user sends two groups with weights 80% and 20% on the front-end.
 - On the back-end, proxy creates two corresponding groups, weighting them at 80%*X% and 20%*X%.

This does require the proxy to reweight when one of the groups goes away -- and maybe even when the server doesn't have anything to send on one group -- if it wanted to maintain strict resource allocation across front-end connections; to deal with that, you would need groups-of-groups, or the ability to have disjoint lists of resources within a group which is essentially the same thing.  But then when you introduce multiple proxies on a path, the same problem shows up with another layer of indirection.

To me, the key point is that this is advisory -- we need to get the server enough information to make smart decisions *when* there are decisions to be made, but not introduce so much extra state on the server that we slow things down in the aggregate.  It doesn't have to be perfect -- which is good, because it never will be.

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]] 
Sent: Monday, February 10, 2014 10:02 AM
To: Jeff Pinner
Cc: Michael Sweet; Roberto Peon; William Chan (陈智昌); Peter Lepeska; Tatsuhiro Tsujikawa; Osama Mazahir; HTTP Working Group
Subject: Re: Priority straw man

> Gn (1/"n"% w S1 <-- S3 & S5 <-- S7)

Unless I misunderstand, that's not entirely correct.  The prioritization schemes that both Will and I described wouldn't permit that.  You would have to choose (S1, S3) <-- (S5, S7) or (S1, S5) <-- (S3, S7) or (S1) <-- (S3, S5) <-- (S7), or something like that.

In all cases, the end states produced by the dependency schemes Will and I wrote up (I don't know what Roberto is talking about here) are exactly equivalent to the scheme Osama described unless there are more layers of dependencies than there are allowed priorities.

The real difference between the schemes is how they handle transitions into the desired end state, particularly when an intermediary needs to translate multiple ways between connections.

It seems to me that a dependency scheme has some advantages when it comes to transitions (the video reprioritization thing, maybe some proxy cases).  It may be that a dependency scheme also has advantages when it comes to translating, but I'm not sure that it's a clear win without full tree-based dependencies.  The cost of these purported advantages is largely borne by the server, which has to deal with the additional complexity of managing dead streams, garbage collection.

I'll also point out that we have to be careful not to raise the bar too high for the server implementers, otherwise we will find that they start ignoring priority more than we would like.  That creates incentives for browsers to hold back requests, apply heuristics, etc...

---

From: Jeff Pinner <[email-masked]>
Date: Mon, 10 Feb 2014 10:40:32 -0800

>
> (S1) <-- (S3, S5) <-- (S7)
>

that is what I meant -- sorry about the confusing "&"

---

From: Jeff Pinner <[email-masked]>
Date: Mon, 10 Feb 2014 10:52:50 -0800

On Mon, Feb 10, 2014 at 10:36 AM, Mike Bishop
<[email-masked]>wrote:

> Assuming I'm following correctly, Jeff's comments seem to reflect the tree
> model in Will's draft which had already been removed and isn't part of
> either proposal currently under discussion.  He would sent two unconnected
> chains of requests within a group, and expect them to be equally treated
> within that group's timeslice, regardless of the relative priorities of
> resources within each chain.  That's not possible with either proposal on
> the table currently, since as Martin notes the end results of both are
> equivalent.  The difference is strictly whether the collapsing of
> dependencies into a strict order happens on the client or server side of
> the connection.
>
>
Sorry I explained this poorly -- I meant the "(S1) <-- (S3, S5) <-- (S7)"
version as Martin put it.

> I'm curious about his comment that he would have to merge priority groups
> on the back-end, though -- unlike stream IDs, it's not like they're
> exhausted once used.  As soon as a group is empty, you can reclaim it for
> more streams and a different user.  Part of the bikeshed on the number of
> bits will certainly be how many simultaneously-active groups you need
> available on the back-end, but that's orthogonal to how priorities within a
> group are expressed.
>
>
I agree it's orthogonal. What I am trying to say is that with more streams
in a group than priority levels (which I believe is common -- even more so
if you collapse groups), it seems easier to proxy explicit dependencies
within streams than having to map them to group levels.

>  - Server is allocating X% of back-end connection per user; user sends two
> groups with weights 80% and 20% on the front-end.
> This does require the proxy to reweight when one of the groups goes away
> -- and maybe even when the server doesn't have anything to send on one
> group -- if it wanted to maintain strict resource allocation across
> front-end connections; to deal with that, you would need groups-of-groups,
> or the ability to have disjoint lists of resources within a group which is
> essentially the same thing.  But then when you introduce multiple proxies
> on a path, the same problem shows up with another layer of indirection.
>
> To me, the key point is that this is advisory -- we need to get the server
> enough information to make smart decisions *when* there are decisions to be
> made, but not introduce so much extra state on the server that we slow
> things down in the aggregate.  It doesn't have to be perfect -- which is
> good, because it never will be.
>
>
I'm not nearly as concerned about the server case as the proxy case -- the
transmission of the priority state to the server has to be accurate enough
to not incentivize the client to play other games with dispatch order,
connections, etc.