RE: [Editorial Errata Reported] RFC7540 (4871)

[Mike Bishop <[e-mail]>]

And I think you’ve hit on half the controversy here:  wording.  From a non-graph-theory point of view, I read “neighbors” as “other nodes with a common parent.”  So the wording here may imply different things to different people.

I think of it as a recursive allocation – given a tree rooted at X and resources Y to allocate to it:

  *   Define Unblocked(N) true if N or any descendant of N can make progress
  *   If Unblocked(X) is false, allocate no capacity
  *   If X able to make progress, allocate Y to X; return
  *   Else
     *   Let C = count of children of X where Unblocked(child) is true
     *   Repeat algorithm allocating Y / C to the subtree rooted at each (unblocked) child of X

If I’m correct (always chancey), the other issue is that this text talks about redistributing if X is blocked, not if X and all descendants of X are blocked.  That’s addressed elsewhere, but not clearly stated in this particular instance.

From: laike9m [mailto:[e-mail]]
Sent: Wednesday, November 30, 2016 7:57 AM
To: Stefan Eissing <[e-mail]>
Cc: [e-mail]; Kazuho Oku <[e-mail]>; Cory Benfield <[e-mail]>; Martin Thomson <[e-mail]>; RFC Errata System <[e-mail]>; Mike Belshe <[e-mail]>; Roberto Peon <[e-mail]>; Ben Campbell <[e-mail]>; Alissa Cooper <[e-mail]>; Alexey Melnikov <[e-mail]>; Patrick McManus <[e-mail]>; Mark Nottingham <[e-mail]>; HTTP Working Group <[e-mail]>
Subject: Re: [Editorial Errata Reported] RFC7540 (4871)


Since it’s me that brought this question<https://github.com/http2/http2-spec/issues/758> to Martin, I also got some thoughts on it(from a reader's perspective):

Basically the question is not about the example being wrong, it’s about the above description being contradictory with the example.

…Resources are shared between streams with the same parent stream, which means that if a stream in that set closes or becomes blocked, any spare capacity allocated to a stream is distributed to the immediate neighbors of the stream. However, if the common dependency is removed from the tree, those streams share resources with streams at the next highest level.

So, let’s assume the example is correct, then there are three problems with this paragraph.
1.       “in that set”: “set” here apparently means “streams with the same parent stream”, so emphasizing “in that set” makes readers feel the resource reallocation process is between those streams. Better remove it.
2.       “neighbors”: it’s true that in graph theory “neighbors” means nodes that directly connect to a specific node(like C, D to A), but since we’re talking about a tree, if we could use more precise words like “dependent streams” or “child streams”, then there would be no controversy. I searched the whole RFC, “neighbor” is only used once, which does cause some confusion.
3.       “However, if the common dependency is removed from the tree, those streams share resources with streams at the next highest level.”: this whole sentence, in such case, is not even necessary.

So the modified version would be something like this:

Resources are shared between streams with the same parent stream, which means that if a stream closes or becomes blocked, any spare capacity allocated to the stream is distributed to the dependent streams of it.

But yeah, like Cory said, Martin definitely proposed the erratum for a reason, and it's still possible the erratum is what the RFC writers really meant.
​

On Wed, Nov 30, 2016 at 10:54 PM, Stefan Eissing <[e-mail]<mailto:[e-mail]>> wrote:
A stream is blocked only by flow-control, as I read it. The errata would suggest that the flow control of the parent would effectively rule those of its descendants? That does not make much sense to me.

This could easily become very messy. If flow control of dependant nodes become entangled with their ancestors, then we basically have nested flow control windows? Please. no.

-Stefan

> Am 30.11.2016 um 14:49 schrieb Tatsuhiro Tsujikawa <[e-mail]<mailto:[e-mail]>>:
>
>
>
> On Wed, Nov 30, 2016 at 10:29 PM, Kazuho Oku <[e-mail]<mailto:[e-mail]>> wrote:
> 2016-11-30 22:05 GMT+09:00 Cory Benfield <[e-mail]<mailto:[e-mail]>>:
> >
> >
> > On 30 Nov 2016, at 13:04, Kazuho Oku <[e-mail]<mailto:[e-mail]>> wrote:
> >
> > My understanding is that you do not need to distinguish between completed, idle and blocked states.
> >
> > For a stream under either of the three states, the weight associated to the stream is distributed to the dependents.
> >
> > That is what nghttp2 does and H2O does (except for the fact that it does not remember closed streams), and I this behavior is what is suggested by the spec.
> >
> >
> > My understanding of what Martin is suggesting is that that isn’t true: blocked streams do not distribute their weight to their dependants.
>
>
> Thank you for pointing that out.
>
> My understanding is that there is no special casing for blocked
> streams. Section 5.3.1 handles all the states we are discussing
> equally, quote:
>
>    Inside the dependency tree, a dependent stream SHOULD only be
>    allocated resources if either all of the streams that it depends on
>    (the chain of parent streams up to 0x0) are closed or it is not
>    possible to make progress on them.
>
> I also do not see why it would be beneficial to treat them differently.
>
>
> ​I agree with Kazuho.  I think RFC 7540 is written based on the idea that dependent stream ca​n receive resource if the streams between it and root are all either in closed, idle or blocked.
>
> Actually, from nghttp2 commit log, I made a commit which implemented the proposed  text.  But we later reverted it, since there is no text in the draft at that time to mandate that behaviour.
>
> Best regards,
> Tatsuhiro Tsujikawa
>
>
>
> >
> > However, that’s also what the Python Priority implementation does.
> >
> > Cory
> >
>
>
>
> --
> Kazuho Oku
>
>