Subject: Comments on draft-chan-http2-stream-dependencies-00

From: Martin Thomson <[email-masked]>
Date: Mon, 13 Jan 2014 14:18:28 -0800

First of all, thanks to Will for making this happen.  Is this your
first internet-draft?

I have quite a few concerns about END_STREAM_ACK.

Primary of these is a concern that as protocol machinery, it seems too
heavy for something like priority, which is - in essence -
augmentation.  A big part of this is that it imposes a cost even where
prioritization isn't used, and I don't like that sort of externality.

The key use for END_STREAM_ACK is to force a server (* - I'm using
server and client here throughout, though I understand the properties
of this to be basically symmetric) to hold prioritization state until
the client can signal that it has received the END_STREAM, thereby
removing the closed stream from the set of candidate streams that can
be referenced.  In part, this shifts the timing problems to the
server, because the server needs to maintain timers to track
unacknowledged stream endings.

I'm not sure whether it makes sense to send END_STREAM_ACK when
transitioning into one of the half-closed states.

The handling of END_STREAM_ACK with respect to RST_STREAM needs to be
specified.  If the intent is to ensure complete consistency regarding
the set of streams that are available for reference, this is
necessary.  An acknowledgement for RST_STREAM could resolve the
problem whereby a sender of RST_STREAM has to ignore frames for some
open-ended period.  But I'm not sure that we need that machinery.)

As far as it goes, I think that garbage collection is trivial to
accomplish.  If you accept the fact that sending too complex or too
many prioritization dependencies could result in some forms of
suboptimal prioritization, it gets very easy to bound the amount of
state that you maintain.

I don't think that you need the ORDERED bit.  It seems to me like you
could do "A <- B -- C" just as easily by having C reference A.  The
single chain of antecedent-dependent nodes is something an
implementation could easily do, even if this were the case.  I don't
see the advantage to having ORDERED in the protocol.

If each stream has two priority-related properties, why not make them
separate properties?  It's fairly obvious that an ORDERED dependency
doesn't require it, but an unORDERED dependency can have two numbers:
the stream ID of its parent, and a relative weight compared to its
peers.  Then all streams would have both values, with streams
inheriting a parent of 0 by default.  It's a framing change, but I
don't see why you couldn't add two numbers to each stream.

And just for completeness, here's my crazy idea of the day.  Split the
32 bits.  The first 16 could be a relative backwards reference to
another stream, the second 16 could be a relative weight.  Or, go even
crazier...  16 bits is a lot for weighting, so how about a third split
that contains a priority horizon, beyond which the client promises
never to reference a stream for prioritization (maybe: 8 weight/16
relative stream/8 relative horizon) to allow for explicit release.

Nits:

Section 4 needs to come before all the protocol-stuff.  It contains
all the actual useful information; before that, I was reading things
and becoming confused about the whys and wherefores and whatnot.

This:
   "Updating dependencies when overwriting values is analogous to list
      insertion."
Is not quite correct.  Change is an atomic delete+add.

Section 5 is a wee bit long.  I don't usually find that you need to
include such detailed justification in a draft.  Motivating material
(as most of this is), usually goes up front, and when things are
up-front, short and sweet is the best way to go.  List discussion and
meetings provide ample opportunity for expanding on all the nasty
details.  That said, I'm surprised at how little mention there is of
the intermediary bug that first caused this to arise.

---

From: William Chan (陈智昌) <[email-masked]>
Date: Tue, 14 Jan 2014 17:22:48 -0800

> First of all, thanks to Will for making this happen.  Is this your

Yep

> unacknowledged stream endings.

Timers are only necessary if you'd like to garbage collect. Otherwise,
what are you doing on a timer?

> open-ended period.  But I'm not sure that we need that machinery.)

Indeed, I'll add that down to the list of things to update in the next version.

> suboptimal prioritization, it gets very easy to bound the amount of

We picked an option knowing that people would want to debate it. I'm
interested in hearing what others have to say here. It's not clear to
me that explicit END_STREAM_ACKs are better or worse than just relying
on garbage collection.

> see the advantage to having ORDERED in the protocol.

Having C reference A brings us back to dependency trees instead of
lists. And if you have a D which is lower priority than both B & C in
your example, how do you express it? Maybe you have D depend on B? And
if you have an E, what happens if you mark E as depending on C? What's
the priority ordering between D and E, if any?

Once you open it up to a possible tree, it gets more complicated. In
terms of the complexity tradeoff, I think adding a bit for order is
simpler than having to have peers/siblings.

> don't see why you couldn't add two numbers to each stream.

OIC, this is something we didn't clean up. We don't want
siblings/peers. Just a single list.

> the intermediary bug that first caused this to arise.

OK, this is an artifact of the authors never having written
internet-drafts before. And I hope to hand this off to you at some
point sooner than later if it gets accepted for HTTP/2, at which point
the structure of this I-D will be irrelevant :)

---

From: Martin Thomson <[email-masked]>
Date: Wed, 15 Jan 2014 09:43:52 -0800

> what are you doing on a timer?

So what you are saying is that if you don't want to do priority
properly, you can ignore this END_STREAM_ACK message.  That sounds
reasonable I guess.  I'll note that those implementations will lose
any sanity checking on the message, such that a peer can send 0, 1, or
many instances of the message and it will be ignored (though it might
trip DoS counters).

> lists.

Not really.  If you send A <- B followed by A <- C, then that
collapses to A <- B -- C.  You can do that based on the order that the
priorities are set (or by stream identifier numbers, but that would be
harder to work out).

> And if you have a D which is lower priority than both B & C in
> your example, how do you express it?

Depends.  The easiest way is to require that D depend on the last
stream in the priority class (i.e., D depends on C), which would be
exactly equivalent to what your draft says.  You could equally
stipulate that the first in the group is identified (D depends on B).
At the same time, it is possible (though less easy in practice due to
the need for a little searching) to allow D to depend on either B or
C.  No matter what the choice, it's trivial to have the receiver
translate that into A <- B -- C <- D.

> Maybe you have D depend on B? And

Again, if you stipulate a strict requirement to depend on the last
(prioritized) stream in the group of equivalent ordering dependencies,
then E would depend on C and produce A <- B -- C <- D -- E.

> simpler than having to have peers/siblings.

It's not really a tree in the sense that you think.  It's a list of
lists.  The exact same structure you describe in the draft in fact.
See:

A
^
B -- C
^
D -- E

The only difference is that in the draft you make statements about
what implementations do with their internal data structures, which
isn't really necessary.

> siblings/peers. Just a single list.

That's an implementation choice.  Fact is, your nodes have two numbers
on each.  Why not make that explicit?

---

From: William Chan (陈智昌) <[email-masked]>
Date: Wed, 15 Jan 2014 14:35:43 -0800

I skimmed this response. AFAICT, we're in agreement on the
desirability of stream dependencies and seem to disagree on
interpretation of how to express this in the wire format. I'm going to
say that I don't really care. If an ORDERED bit is not necessary, then
it's not necessary. I'm happy to, if we have agreement on stream
dependencies, to walk through all the use cases and how to express
them in the wire format and make sure we accommodate them accordingly.
And if people want to make the relative weight explicit, I'm kinda OK
with that too, even though it's not clear to me that it's necessary.
I'm trying to resist the temptation to bike shed prematurely here :)

> many instances of the message and it will be ignored (though it might

This is true. And if many server implementations do this, then it will
make clients wary of relying on the prioritization mechanism, which
would be a bad state to end up in. The only thing I can think of to
mitigate this is having END_STREAM_ACK be required in order to
completely remove the stream from counting towards the stream limit.

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 16 Jan 2014 11:48:25 +1300

On 2014-01-16 06:43, Martin Thomson wrote:
> On 14 January 2014 17:22, William Chan (陈智昌) wrote:
<snip>
> priorities are set (or by stream identifier numbers, but that would be
<snip>

> what implementations do with their internal data structures, which

I have been wondering exactly how best such a list tree would be 
implemented to prevent some objects at the leaf ends being starved or 
stateful interactions between the implementations. In particular how to 
avoid/reduce problems with stateless or stream-ID mapping 
intermediaries.

In short: I am completely against adding weightings and complex 
relationship indicators. Even though the feature is OPTIONAL, jumping 
through such hoops is completely unrealistic for middleware. Here is a 
simple off-the-cuff implementation example for the simplest A<-B, A<-C, 
C<-D type of dependency tree/list.

If each stream is assigned a single depends-on parent (which can be 
changed dynamically with PRIORITY). It could be implemented as a single 
list in stream-ID order with but one property indicating the depended-on 
stream. Scanning over the list for scheduling frame writes could 
recursively try to write available frames for the depended-on stream 
before writing the current stream frames, then moving on to the next 
listed. Garbage-collection would simply be removing depends-on 
information for already completed streams, effectively raising the child 
streams all up a level of priority.

Simple, fast and quite memory efficient. There are also a few very 
useful emergent properties from this:

1) Default priority (no dependencies or implementations ignoring this 
mechanism) would be to deliver frames for the lowest stream-ID first.
  a) HTTP/1.1 ordering maps cleanly to the 2.0 default priority for 
delivery.
  b) hops without the feature implemented mostly act as if default 
priority were being used.

2) all streams get at least one shot at delivering a frame on the 
connection each cycle.
  a) preventing any hanging completely.
  b) allowing implementations to limit how much they send (ie DATA) on 
one write, secure in the guarantee that high priority stream will get 
more (and earlier) chances to write than others relative to how many 
streams depend on it.

3) groups of requests depending on each other (ie from the same client) 
are served relatively close to each other,
  a) increasing the likelihood of shared headers compressing the traffic 
size, and
  b) allowing any middleware caches to make better use of temporal 
locality for relatedness of resources.

4) priority delivery is completely up to the sender,
  a) no need for any receiver implementation complexity,
  b) no END_STREAM_ACK management

5) priority of frames self-corrects to a certain degree after relaying 
over a hop without the mechanism implemented.

6) any buffered streams awaiting write or being processed are 
immediately affected by the PRIORITY changes of all other streams.
  a) no need for middleware complexity juggling relationships

7) robust error handling with broken middleware improperly adjusting 
PRIORITY frame stream-IDs when it changes transferred stream-IDs.
  * The feature otherwise assumes that stream-IDs are identical 
end-to-end (a false assumption with middleware).

8) a streams weight is a product of how many other streams are depending 
on it.
  a) depended-on streams are likely first in the list, so naturally will 
get more frames delivered without weightings or explicit rate-limiting 
later streams.
  b) no need for middleware complexity juggling and balancing weights 
from N servers with M clients.
  c) no need for server complexity determining relative weight importance 
to clients.
  d) no risk of middleware being tricked into turning a small received 
PRIORITY change into a massive set of emitted PRIORITY side-effect 
changes (or worse given weightings, these could trigger PRIORITY changes 
to other client<->server traffic transactions).

Amos

---

From: Roberto Peon <[email-masked]>
Date: Wed, 15 Jan 2014 15:44:09 -0800

On Wed, Jan 15, 2014 at 2:48 PM, Amos Jeffries <[email-masked]> wrote:

> avoid/reduce problems with stateless or stream-ID mapping intermediaries.
>

Starvation is sometimes the intent. Without it pages load more slowly and
the user experience suffers.

> C<-D type of dependency tree/list.
I think it is a bit premature to say it is unrealistic? This was designed
to solve real-world problems in a real proxy :)

> recursively try to write available frames for the depended-on stream before
> writing the current stream frames, then moving on to the next listed.
> Garbage-collection would simply be removing depends-on information for
> already completed streams, effectively raising the child streams all up a
> level of priority.
>

Note that you're proposing a tree, not a list, unless you additionally
impose a requirement that any parent must have only one child (which you're
not doing in your example).
The list-of-lists or the tree-of-deps ends up being essentially the same
thing imho. I'd implement the list-of-lists as a tree anyway since it would
probably be the most space-and-time efficient implementation.

> Simple, fast and quite memory efficient. There are also a few very useful
> emergent properties from this:
>
>  b) hops without the feature implemented mostly act as if default priority
> were being used.
>

We know that the 'priority equals request sequence #' thing is suboptimal
in terms of latency and user experience, so that isn't an improvement :/

>  b) allowing implementations to limit how much they send (ie DATA) on one
> write, secure in the guarantee that high priority stream will get more (and
> earlier) chances to write than others relative to how many streams depend
> on it.
>
>
We played with this waaaay back in the early spdy days. It was
disadvantageous then, but it is probably worth trying it again.
The assumption at the time, given that layout time was a significant
percentage of display cost (latency), was that perhaps giving the layout
engine more information about the sizes of images where the markup didn't
make the size explicit would speed things up. It didn't help.

In the proxy case, you'll want to have relative priorities active within
the context of a single user's session, and then you'll want a different
set of priorities between different clients.
That way no *client* gets starved, though a client may be starving itself
of a resource by constantly requesting higher priority items without
changing the priority of the low-priority item.
Clients that don't do prioritization would lack information about relative
priorities within their session, and thus the server would probably just
serve them in order-received.

>  b) allowing any middleware caches to make better use of temporal locality
> for relatedness of resources.
>

While the results you state are certainly advantageous, forcing the
grouping of requests can be disadvantageous, depending on one's aims
(generally in terms of client experience). So I see this as both good and
bad.

>  b) no END_STREAM_ACK management
What complexity are you thinking about here?

> over a hop without the mechanism implemented.

I don't understand this part.

>
> 6) any buffered streams awaiting write or being processed are immediately
> affected by the PRIORITY changes of all other streams.

So, when client A requests a number of things, then changes their mind
about wanting them right now, how does that impact client B when both are
going through proxy C?

>  * The feature otherwise assumes that stream-IDs are identical end-to-end
> (a false assumption with middleware).
>

The prioritization proposal doesn't assume this at all. It assumes, rather,
that the proxy must maintain a mapping from client-side-stream-id to
server-side-stream-id.
This has to be the case, else things just wouldn't work properly.

>  b) no need for middleware complexity juggling and balancing weights from
> N servers with M clients.
> PRIORITY change into a massive set of emitted PRIORITY side-effect changes
> (or worse given weightings, these could trigger PRIORITY changes to other
> client<->server traffic transactions).

This doesn't easily allow a proxy to weight clients equally (i.e. fair
queuing across clients), which is oftentimes explicitly what is desired. A
client with 1000 outstanding requests shouldn't have a 1000X advantage over
one which wants only one, simply because it made more requests. That is
backwards from how many would like it done much of the time, and would
perform extremely poorly under DoS circumstances.
-=R

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 16 Jan 2014 14:55:55 +1300

On 2014-01-16 12:44, Roberto Peon wrote:
>> before
>> priority

Sure. I don't think Id support a feature where the case where it was NOT 
implemented was better than it's default. The point here is that its 
default is a non-change to regular behaviour, not better but no worse 
either.

>> one

In the proxy case the server is not necessarily aware of which requests 
are for what client. All requests are coming from the proxy and sending 
such info adds complexity.
A mechanism where all requests without pending dependencies are of equal 
top-level priority and treating them all equally prevents a proxy 
starving some client(s) simply by being there. And makes in unnecessary 
for the proxy to artificially create dependencies to avoid that 
starvation.

> What complexity are you thinking about here?

All of the state management receiver has to do to send accurate ACK 
frames, weights relative to everything else and how different requests 
are related to each other.
  The render engine in browsers may have that information, but I dare say 
few other client implementations have such a rich base of information to 
work from.

> I don't understand this part.

In the case(s) where there are multiple hops and one (other than the 
server) does not implement the PRIORITY mechanism in full the receiving 
client it is delivering to can perform frame re-ordering in a small 
degree simply by buffering frames. The buffered frames will be drained 
to the client according to the dependencies known at that hop - thus a 
small amount of re-ordering to correct any un-ordering done by its 
upstream.

>> immediately

How would client A have submitted that information about client B to the 
proxy and server anyway?

Within the restrictions of the stream ID order requirements the proxy 
may send a PRIORITY update upstream if it wishes making the client A 
requests depend on the client B ones.

> This has to be the case, else things just wouldn't work properly.

Unless I missed something this requirement is not stated in the draft: 
that the proxy needs to change the records listed inside PRIORITY or the 
HEADER field proposed. Thus any middleware not implementing this feature 
will ignore those records when relaying the frames. Thus end-to-end 
stream IDs are mandatory/assumed in this draft.

>> changes

We seem to be envisaging different scopes here. I have been looking at 
this list/tree as a per-connection set of requests to prioritise between 
themselves. Your statement suggests that you are considering a single 
master list of all requests served up by the implementation.

By all means weight between connections. But that is absolutely 
something that should be decided local to the implementation rather than 
imposed by any single client or server of it.

Amos

---

From: Peter Lepeska <[email-masked]>
Date: Thu, 16 Jan 2014 10:56:47 -0500

I don't mean to change the topic, since Amos and Roberto are having a
good exchange, but I just wanted to endorse the proposal. The benefits
in terms of page load performance will be big, especially for a
forward proxy that is able to prioritize across resources from
different hosts for objects on the same page.

I like the core ideas of lists of dependent resources representing
each tab, with resources in the list either ordered or unordered. This
does expand out into a tree (with unordered dependent objects as
siblings) but the way the tree is expressed in the draft as a list is
elegant and simplifying, in my opinion.

That all said, any amount that we can further simplify this proposal
without significantly reducing the amount of information the browser
is providing to upstream servers is great.

Thanks,

Peter

On Wed, Jan 15, 2014 at 8:55 PM, Amos Jeffries <[email-masked]> wrote:
> implemented was better than it's default. The point here is that its default
> is a non-change to regular behaviour, not better but no worse either.
>
>
>>
> In the proxy case the server is not necessarily aware of which requests are
> for what client. All requests are coming from the proxy and sending such
> info adds complexity.
> top-level priority and treating them all equally prevents a proxy starving
> some client(s) simply by being there. And makes in unnecessary for the proxy
> to artificially create dependencies to avoid that starvation.
>
>
>
>>
> All of the state management receiver has to do to send accurate ACK frames,
> weights relative to everything else and how different requests are related
> to each other.
>  The render engine in browsers may have that information, but I dare say few
> other client implementations have such a rich base of information to work
> from.
>
>
>
>>
> In the case(s) where there are multiple hops and one (other than the server)
> does not implement the PRIORITY mechanism in full the receiving client it is
> delivering to can perform frame re-ordering in a small degree simply by
> buffering frames. The buffered frames will be drained to the client
> according to the dependencies known at that hop - thus a small amount of
> re-ordering to correct any un-ordering done by its upstream.
>
>
>
>>>
> Within the restrictions of the stream ID order requirements the proxy may
> send a PRIORITY update upstream if it wishes making the client A requests
> depend on the client B ones.
>
>
>
>
> Unless I missed something this requirement is not stated in the draft: that
> the proxy needs to change the records listed inside PRIORITY or the HEADER
> field proposed. Thus any middleware not implementing this feature will
> ignore those records when relaying the frames. Thus end-to-end stream IDs
> are mandatory/assumed in this draft.
>
>
>>
>>>
> We seem to be envisaging different scopes here. I have been looking at this
> list/tree as a per-connection set of requests to prioritise between
> themselves. Your statement suggests that you are considering a single master
> list of all requests served up by the implementation.
>
> By all means weight between connections. But that is absolutely something
> that should be decided local to the implementation rather than imposed by
> any single client or server of it.
>
> Amos
>

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 17 Jan 2014 17:39:12 +0000

I also much like this proposal. I think that there are interesting things in Martin's suggestion of splitting the PRIORITY field.

Contrary to Martin, I think the ORDERED bit is necessary. Once A <- B is sent, you have two possibilities for adding C inside this relationship:
- Between A and B, resulting in A <- C <- B
- At the same level as B, resulting in A <- B - C

At the same time, I don't like the ORDERED bit to be in a frame flag. So I'd prefer moving it to the PRIORITY field:
- All the information on priorities is in the same location.
- One PRIORITY frame can be used for updating all priorities (both ordered and unordered).

So, when specifying a dependency, we could have:
- P = 0, 1 bit.
- Relative dependency: signed 16 bit int, relative to stream-ID. Backward and forward references are probably desirable (forward references could be useful when updating priorities).
- O: 1 bit, for either ordered or unordered.
- Reserved: 14 bits. (This should be rearranged for easier encoding/decoding).

Hervé.

> -----Original Message-----
> From: Peter Lepeska [mailto:[email-masked]]
> Sent: jeudi 16 janvier 2014 16:57
> To: Amos Jeffries
> Cc: [email-masked]
> Subject: Re: Comments on draft-chan-http2-stream-dependencies-00
>

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sun, 19 Jan 2014 12:37:14 +0900

> completely remove the stream from counting towards the stream limit.
+1 for mandatory END_STREAM_ACK to remove stream.
The current spec requires that if, for example, DATA frame is received
after a frame with END_STREAM flag set, it must respond with stream error,
but to do this, the receiver has to remember the all stream status,
including closed, which requires additional memory. I think it could be
connection error (I remember someone said that in this list), but we cannot
simply do this because of asynchronous nature of the stream closure.
Requiring additional memory for just dealing with bad peer is not a good
idea to me. With END_STREAM_ACK, both peers keep track of the streams in
bounded memory by MAX_CONCURRENT_STREAM. If a peer receives DATA frame and
whose associated stream does not exist, we can safely terminate connection
because it is a buggy client. Otherwise, we can check the stream state and
it is half-closed remote, then we can also make it connection error.

Best regards,

Tatsuhiro Tsujikawa

---

From: Amos Jeffries <[email-masked]>
Date: Mon, 20 Jan 2014 10:36:29 +1300

On 2014-01-19 16:37, Tatsuhiro Tsujikawa wrote:
> On Thu, Jan 16, 2014 at 7:35 AM, William Chan (陈智昌) wrote:
> 
> including closed, which requires additional memory.

Wrong. For both ACK'd and non-ACK'd models only the active streams state 
needs remembering.

1) Stream IDs are incremental and always increasing.

2) Any stream ID which is not currently remembered as active is 
ended/closed and needs to be responded with that stream error.

So the total state requirements is a 32-bit largest stream-ID, and a 
list of currently active streams. The rest is easily calculated and 
responded with stream error or connection error.

The END_STREAM flag acts as an ACK frame with payload. Reducing the 
overhead of an explicit END_STREAM_ACK frame to be scheduled and 
possibly dropped or broken in other ways. If the final frame with DATA 
(or HEADERS) carrying the end flag has not been received then truly the 
stream is not yet fully received and must be handled as such.

> I think it could be
> bounded memory by MAX_CONCURRENT_STREAM.

END_STREAM_ACK increases statefulness between client and server, which 
in turn adds high risk of DoS from malicious senders simply choosing to 
omit sending the END_STREAM_ACK.

To mitigate that error receivers would have to implement a mechanism for 
ending streams without the ACK. The HTTP design (even in HTTP/1 
keep-alive) makes that mechanism the default and avoids all the problems 
of creating two parallel mechanisms for closure.

Many problems in HTTP/1 are created by its multiple mechanisms for 
closure. HTTP/2 reduces that to 1 mechanism which is a VERY good design 
choice.

> If a peer receives DATA frame and

These actions must be done regardless of END_STERAM _ACK and are common, 
making a good case for -1 on END_STREAM_ACK.

Amos

---

From: Jeff Pinner <[email-masked]>
Date: Mon, 20 Jan 2014 04:28:18 +0100

strong agreement with everything Amos wrote

On Sun, Jan 19, 2014 at 10:36 PM, Amos Jeffries <[email-masked]>wrote:

> So the total state requirements is a 32-bit largest stream-ID, and a list
> of currently active streams. The rest is easily calculated and responded
> with stream error or connection error.
>
> overhead of an explicit END_STREAM_ACK frame to be scheduled and possibly
> dropped or broken in other ways. If the final frame with DATA (or HEADERS)
> carrying the end flag has not been received then truly the stream is not
> yet fully received and must be handled as such.
>
>
>
>  I think it could be
> END_STREAM_ACK increases statefulness between client and server, which in
> turn adds high risk of DoS from malicious senders simply choosing to omit
> sending the END_STREAM_ACK.
>
> ending streams without the ACK. The HTTP design (even in HTTP/1 keep-alive)
> makes that mechanism the default and avoids all the problems of creating
> two parallel mechanisms for closure.
>