Subject: [Editorial Errata Reported] RFC7540 (4871)

From: RFC Errata System <[email-masked]>
Date: Tue, 29 Nov 2016 20:33:54 -0800 (PST)

The following errata report has been submitted for RFC7540,
"Hypertext Transfer Protocol Version 2 (HTTP/2)".

--------------------------------------
You may review the report below and at:
http://www.rfc-editor.org/errata_search.php?rfc=7540&eid=4871

--------------------------------------
Type: Editorial
Reported by: Martin Thomson <[email-masked]>

Section: 5.3.4

Original Text
-------------
For example, assume streams A and B share a parent, and streams C
and D both depend on stream A. Prior to the removal of stream A,
if streams A and D are unable to proceed, then stream C receives
all the resources dedicated to stream A. If stream A is removed
from the tree, the weight of stream A is divided between streams
C and D. If stream D is still unable to proceed, this results in
stream C receiving a reduced proportion of resources. For equal
starting weights, C receives one third, rather than one half, of
available resources.

Corrected Text
--------------
For example, assume streams A and B share a parent, and streams C
and D both depend on stream A. When A is complete, streams C and
D receive all the resources that would be allocated to stream
A. If stream D is unable to proceed, stream C shares resources
with stream B. Assuming equal starting weights on all streams,
this means that streams B and C receive an equal share.  However,
if stream A is removed from the tree, the weight of stream A is
divided between streams C and D. With stream A removed and stream
D unable to proceed, stream C receives a reduced proportion of
resources. For equal starting weights, C receives one third,
rather than one half, of available resources.

Notes
-----
The example was incorrect.  Dependent streams do not receive resources if their parent is blocked; they only receive resources once the parent is complete.

Note that I didn't correct the common misunderstanding regarding the third here.  That might be further improved by doing the math.  That is:

Before removal: A=N (C=N, D=N), B=N;
After removal: B=N, C=N/2, D=N/2;
Therefore viable streams are B=N and C=N/2 meaning a total pool of 3N/2.  The resource proportion allocated to C is therefore (N/2)/(3N/2)=1/3.

But that would probably need an entire section for the example, rather than a single paragraph.

Instructions:
-------------
This erratum is currently posted as "Reported". If necessary, please
use "Reply All" to discuss whether it should be verified or
rejected. When a decision is reached, the verifying party  
can log in to change the status and edit the report, if necessary. 

--------------------------------------
RFC7540 (draft-ietf-httpbis-http2-17)
--------------------------------------
Title               : Hypertext Transfer Protocol Version 2 (HTTP/2)
Publication Date    : May 2015
Author(s)           : M. Belshe, R. Peon, M. Thomson, Ed.
Category            : PROPOSED STANDARD
Source              : Hypertext Transfer Protocol Bis APP
Area                : Applications
Stream              : IETF
Verifying Party     : IESG

---

From: Cory Benfield <[email-masked]>
Date: Wed, 30 Nov 2016 08:41:07 +0000

> On 30 Nov 2016, at 04:33, RFC Errata System <[email-masked]> wrote:
> 

Well, this tripped me up: the Python priority implementation gets this wrong.

Let me ask a follow-on question that I have not been able to find an answer for in RFC 7540. If we continue the example from the erratum (streams A, B, C, D, A and B have stream 0 as parent, C and D depend on A), it’s now clear to me that if stream A is blocked then stream B gets all the resources. What happens if both stream A and B are blocked? Should my server endeavour to serve dependent streams in that case? I *think* the answer is yes because of the logic around having grouping nodes formed from idle streams, but I’m not 100% sure and would like clarification.

Cory

---

From: Martin Thomson <[email-masked]>
Date: Wed, 30 Nov 2016 20:35:37 +1100

On 30 November 2016 at 19:41, Cory Benfield <[email-masked]> wrote:
> What happens if both stream A and B are blocked? Should my server endeavour to serve dependent streams in that case?

I guess so.  You don't want to completely stall out.  Obviously, if A
and B have a parent with siblings that aren't blocked, then you
continue there, but if everything is stalled, then I guess it's OK to
make progress on any stream.

You could probably devise some sort of scheme where you pick the
stream using some algorithm or other - maybe based on some best-fit
criteria.  But I'd say that it doesn't matter at that point: if we
assume that all streams that aren't blocked depend on blocked streams,
then none of them will be useful to the other side until those blocked
streams finish.  All you are doing is avoiding having a completely
wasted connection.

---

From: Benedikt Christoph Wolters <[email-masked]>
Date: Wed, 30 Nov 2016 12:32:20 +0100

2016-11-30 9:41 GMT+01:00 Cory Benfield <[email-masked]>:
> What happens if both stream A and B are blocked? Should my server endeavour to serve dependent streams in that case? I *think* the answer is yes because of the logic around having grouping nodes formed from idle streams, but I’m not 100% sure and would like clarification.

Section 5.3.4 Prioritization State Management states:
> 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.

In my understanding in your example A and B are blocked, C and D are
immediate neighbors of A so according to this they would get the
resources of A.

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 1 Dec 2016 00:46:01 +1300

On 30/11/2016 10:35 p.m., Martin Thomson wrote:
> On 30 November 2016 at 19:41, Cory Benfield wrote:

Well, not just that. You are also speeding up / making progress on the
non-blocked streams while waiting. The priority is a utopian/best-case
preference not a requirement.

The server should even deliver bytes of dependent streams if they have
bytes available, even if the A/B are not blocked but simply need less
bandwidth than is currently free in the send window.

Amos

---

From: Cory Benfield <[email-masked]>
Date: Wed, 30 Nov 2016 12:42:33 +0000

> On 30 Nov 2016, at 11:32, Benedikt Christoph Wolters <[email-masked]> wrote:
> 

No, they aren’t immediate neighbours, they are immediate *children*. This is exactly the core question.

---

From: Cory Benfield <[email-masked]>
Date: Wed, 30 Nov 2016 12:48:29 +0000

> On 30 Nov 2016, at 12:42, Cory Benfield <[email-masked]> wrote:
> 
> 

Oh, I apologise, I hadn’t realised that “neighbours” might be being applied in terms of its graph-theoretical definition. That’s an interesting point.

---

From: Cory Benfield <[email-masked]>
Date: Wed, 30 Nov 2016 12:49:46 +0000

> On 30 Nov 2016, at 09:35, Martin Thomson <[email-masked]> wrote:
> 

So presumably the sensible heuristic for this is to do the following logic:

1) Select the streams that depend on stream 0 that are not blocked, completed, or idle, and add them to set A.
2) For each stream dependent on stream 0 that is completed or idle,
    a) Select their children that are not blocked, completed or idle, adjusting their effective weights as detailed in RFC 7540, and add them to set A.
    b) If no streams were selected in part a), but there are streams that are completed or idle streams, repeat step 2) for the children of those streams.
3) If set A is empty, repeat the above but treat streams that are blocked as though they are completed or idle (that is, allow their children to be selected to be served).

I am not sure how many server/intermediary implementations actually implement priority in this manner. It’d be interesting to hear what the others do.

Cory

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 30 Nov 2016 22:04:13 +0900

2016-11-30 21:49 GMT+09:00 Cory Benfield <[email-masked]>:

> >> What happens if both stream A and B are blocked? Should my server
> endeavour to serve dependent streams in that case?
> >
> 1) Select the streams that depend on stream 0 that are not blocked,
> completed, or idle, and add them to set A.
>     a) Select their children that are not blocked, completed or idle,
> adjusting their effective weights as detailed in RFC 7540, and add them to
> set A.
>     b) If no streams were selected in part a), but there are streams that
> are completed or idle streams, repeat step 2) for the children of those
> streams.
> 3) If set A is empty, repeat the above but treat streams that are blocked
> as though they are completed or idle (that is, allow their children to be
> selected to be served).
>
> I am not sure how many server/intermediary implementations actually
> implement priority in this manner. It’d be interesting to hear what the
> others do.
>
>
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.

-- 
Kazuho Oku

---

From: Cory Benfield <[email-masked]>
Date: Wed, 30 Nov 2016 13:05:26 +0000

> On 30 Nov 2016, at 13:04, Kazuho Oku <[email-masked]> 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. However, that’s also what the Python Priority implementation does.

Cory

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 30 Nov 2016 22:29:53 +0900

2016-11-30 22:05 GMT+09:00 Cory Benfield <[email-masked]>:
> 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.

>
> However, that’s also what the Python Priority implementation does.
>
> Cory
>

-- 
Kazuho Oku

---

From: Benedikt Christoph Wolters <[email-masked]>
Date: Wed, 30 Nov 2016 14:34:22 +0100

2016-11-30 14:05 GMT+01:00 Cory Benfield <[email-masked]>:
> blocked streams do not distribute their weight to their dependants

Blocked streams do, if you apply the 'immediate neighbors' definition
in a graph-theoretical sense.
Note that there is a difference between neighbors and siblings.
So with this in mind, I think the example under subject of this errata
is fine as it was before.

---

From: Cory Benfield <[email-masked]>
Date: Wed, 30 Nov 2016 13:44:31 +0000

> On 30 Nov 2016, at 13:34, Benedikt Christoph Wolters <[email-masked]> wrote:
> 

Generally speaking I agree with you and Kazuho, as we can see based on the way I implemented the priority mechanic in code. ;)

However, Martin edited the spec and proposed the erratum, so his understanding of the specification does carry a decent chunk of weight. That’s why I asked implementers to chime in: right now we appear to have Martin on one side, and three implementations on the other.

For now I’m mostly interested to see if Martin (or anyone else who agrees with Martin) can chime in on that position.

Cory

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Wed, 30 Nov 2016 22:49:45 +0900

On Wed, Nov 30, 2016 at 10:29 PM, Kazuho Oku <[email-masked]> wrote:

> > For a stream under either of the three states, the weight associated to
> the stream is distributed to the dependents.
> >
> > My understanding of what Martin is suggesting is that that isn’t true:
> blocked streams do not distribute their weight to their dependants.
>
>
​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

---

From: Stefan Eissing <[email-masked]>
Date: Wed, 30 Nov 2016 15:54:05 +0100

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 <[email-masked]>:
> 
> 
> 
> ​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
> 
> 
>  
> >

---

From: Ryan Hamilton <[email-masked]>
Date: Wed, 30 Nov 2016 07:20:26 -0800

I completely agree. Priority is all about sending the most important data
first. Flow control is a distinct issue and mixing them together seems
complex and confusing in ways that would limit the effectiveness of
priority.

On Wed, Nov 30, 2016 at 6:54 AM, Stefan Eissing <
[email-masked]> 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
>
> > > 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.
> > >
> > >
> > ​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.
> >

---

From: laike9m <[email-masked]>
Date: Wed, 30 Nov 2016 23:56:40 +0800

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.
​

---

From: Mike Bishop <[email-masked]>
Date: Wed, 30 Nov 2016 18:58:31 +0000

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:[email-masked]]
Sent: Wednesday, November 30, 2016 7:57 AM
To: Stefan Eissing <[email-masked]>
Cc: [email-masked]; Kazuho Oku <[email-masked]>; Cory Benfield <[email-masked]>; Martin Thomson <[email-masked]>; RFC Errata System <[email-masked]>; Mike Belshe <[email-masked]>; Roberto Peon <[email-masked]>; Ben Campbell <[email-masked]>; Alissa Cooper <[email-masked]>; Alexey Melnikov <[email-masked]>; Patrick McManus <[email-masked]>; Mark Nottingham <[email-masked]>; HTTP Working Group <[email-masked]>
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.

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 <[email-masked]<mailto:[email-masked]>> 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.

-Stefan

> Am 30.11.2016 um 14:49 schrieb Tatsuhiro Tsujikawa <[email-masked]<mailto:[email-masked]>>:
>
>
>
> On Wed, Nov 30, 2016 at 10:29 PM, Kazuho Oku <[email-masked]<mailto:[email-masked]>> wrote:
> 2016-11-30 22:05 GMT+09:00 Cory Benfield <[email-masked]<mailto:[email-masked]>>:
> >
> >
> > On 30 Nov 2016, at 13:04, Kazuho Oku <[email-masked]<mailto:[email-masked]>> wrote:
> >

---

From: Martin Thomson <[email-masked]>
Date: Thu, 1 Dec 2016 10:03:37 +1100

On 1 December 2016 at 00:05, Cory Benfield <[email-masked]> wrote:
> blocked streams do not distribute their weight to their dependants. However,
> that’s also what the Python Priority implementation does.

And this was my error in writing up the errata and my earlier emails.
The spec is clear that there is no functional distinction between
blocked and finished.  The original text is correct.

It's pretty obvious however that it's not clear.  I'd answered on the
basis of first principles, and that was an error on my part.

Mike's algorithm is almost correct, but I would revise it.  Starting
at the top level:

Given a set of dependents of S,
  find all S where not TreeBlocked(S) as S'
  allocate resources to S' proportional to their weights
    for a stream s in S', if StreamBlocked(s), repeat algorithm with
its dependents

Not treating closed as special keeps this simple.  If you were to
treat closed as different to blocked, then you have the issues that
Cory was digging into.

Kazuho points out:
> I also do not see why it would be beneficial to treat them [closed streams] differently.

It's beneficial if you have other streams that are not blocked that
don't have dependencies.

Imagine that you have two HTML files and then images for each as
dependents.  If one HTML file is blocked, then there is potentially
less value in loading the images that depend on it than there is in
making progress on the other HTML file.  Now, that is arguably not
valuable because HTML/image dependencies are sort of loose, but if you
have an application that has absolute dependencies (I can't use this
until you give me that) and other constraints (not enough memory to
buffer), then you can see a way to treating closed and blocked
differently.

Of course, that isn't what the spec says and we don't get to change that :)

BTW, in answer to what people suggested about flow control, that is
only one reason a resource might be blocked.  A resource might be
blocked because the server hasn't finished building it, that might be
IO or processing.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 1 Dec 2016 13:00:49 +0900

Hi,

>> blocked streams do not distribute their weight to their dependants.
However,
> Of course, that isn't what the spec says and we don't get to change that
:)

Thank you for explaining what you had in mind.

That makes sense, and _if_ we are going to fix the issue, I'd prefer adding
a feature to group multiple streams into one so that other streams can
depend against a group of streams.

In H2O, we internally promote CSS and JavaScript files in such way, e.g.:

       +- CSS1 -+

 root -+- CSS2 -+- HTML - ...

       +- JS   -+

I believe that adding an ability to designate this kind of dependency would
be better than adding special casing for blocked streams.

-- 
Kazuho Oku