Re: Question about HTTP 2.0 priority

On Mon, Oct 6, 2014 at 11:20 AM, Martin Thomson <martin.thomson@gmail.com>
wrote:

> On 6 October 2014 10:39, Chad Austin <caustin@gmail.com> wrote:
> > If it's truly the case that PRIORITY is O(depth(parent) - depth(stream)),
> > does that leave an implementation of HTTP 2's priority graph open to
> denial
> > of service?
>
> That depends on what trade-offs you want to make.
>
> If you really do have a tree that is 10k entries deep, then walking
> what is effectively a linked list is going to cost a non-trivial
> amount of time.  But you don't have to maintain a linked list.  As you
> note, a small increase in complexity and storage allows for certain
> kinds of reprioritization.
>

The part I haven't been able to wrap my head around -- and maybe you can
help -- is, if I reduce the depth of the tree from an N-entry linked list,
where N is the number of requests, to a K-depth tree, where K is the number
of unique priorities, how do I prevent completion of the dependent request
from automatically bumping everything at a lower priority to a higher
priority?  That is, given three priorities A, B, and C (A is highest):

A1    A2    A3
^
+-----+
+     +-----+
B1    B2    B3
^
+-----+
+     +-----+
C1    C2    C3

Sorry for the terrible ASCII art.  :)  Everything at priority B depends on
some element in A, and everything in C depends on some element in B.

How do I handle the case that B1 completes before B2?

As I understand the spec, if that happens, then the dependency tree would
be reduced to:

A1    A2    A3
^
<-----+
|     <-----+
|     |     <-----+
+     +     +     +-----+
C1    C2    C3    B2    B3

It seems a linked list is truly necessary to express "Everything in B is
lower priority than everything in A" and "Everything in C is lower priority
than everything in B".

Am I missing something?

-- 
Chad Austin
http://chadaustin.me