Re: Priority straw man

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

On Sat, Feb 8, 2014 at 8:50 AM, Michael Sweet <msweet@apple.com> 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.


> On Feb 7, 2014, at 7:07 PM, Jeff Pinner <jpinner@twitter.com> 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 Fri, Feb 7, 2014 at 3:42 PM, Roberto Peon <grmocg@gmail.com> wrote:
>
>> 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 <martin.thomson@gmail.com>wrote:
>>
>>> 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.
>>>
>>>
>>> On 7 February 2014 14:46, William Chan (陈智昌) <willchan@chromium.org>
>>> wrote:
>>> > 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 <bizzbyster@gmail.com>
>>> wrote:
>>> >> 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 <
>>> tatsuhiro.t@gmail.com>
>>> >> wrote:
>>> >>>
>>> >>>
>>> >>> On Feb 4, 2014, at 3:16 PM, Osama Mazahir <OSAMAM@microsoft.com>
>>> 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 <msweet@apple.com>
>>> 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.
>>> >>>>
>>> >>>>
>>> >>>> On Feb 4, 2014, at 3:16 PM, Osama Mazahir <OSAMAM@microsoft.com>
>>> 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.
>>> >>>> >
>>> >>>> > 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.
>>> >>>> >
>>> >>>> >
>>> >>>> > -----Original Message-----
>>> >>>> > From: Martin Thomson [mailto:martin.thomson@gmail.com]
>>> >>>> > Sent: Monday, February 3, 2014 9:45 AM
>>> >>>> > To: HTTP Working Group
>>> >>>> > Subject: Re: Priority straw man
>>> >>>> >
>>> >>>> > 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 <
>>> martin.thomson@gmail.com>
>>> >>>> > 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.
>>> >>>> >
>>> >>>>
>>> >>>> _________________________________________________________
>>> >>>> Michael Sweet, Senior Printing System Engineer, PWG Chair
>>> >>>>
>>> >>>
>>> >>
>>>
>>>
>>
>
> _________________________________________________________
> Michael Sweet, Senior Printing System Engineer, PWG Chair
>
>