Subject: [quicwg/base-drafts] PRIORITY frame on control stream referencing unopened request stream (#2502)

From: Robin Marx <[email-masked]>
Date: Thu, 07 Mar 2019 16:42:33 +0000 (UTC)

There is a specific prioritization situation which to my interpretation isn't fully clear in the draft-18 text.

Context: trying to re-create the concept of exclusive prioritization (which was removed from h3 a while ago). 
Approach: simulate exclusivity by sending new PRIORITY frames on the control stream for all the streams we want to be dependent on a new request stream.

Example:
```
A                      B                         C
1                      1                         1   
|                     |  \                       |
2                     2   3                      3
                                                 |
                                                 2     
```
Step A: stream 1 and 2 are opened in sequence with priority frame as first frame of their stream
Step B: stream 3 is opened with priority frame as first frame
Step C: we have sent a priority frame on the control stream for stream 2, updating its dependency to stream 3

(In http/2, step B and C would be the same due to exclusivity, in h3 we need step C to simulate this).

The question:

**What happens if the priority frame from step C arrives before stream 3 is opened? We then have a priority update for stream 2, making it dependent on stream 3, which does not exist yet (at least at the receiving endpoint).**

There are various points in the text that might lead to an interpretation of this, but none really reference this exact situation (afaict).

e.g., 

> A PRIORITY frame that references a non-existent Push ID, a
   Placeholder ID greater than the server's limit, or a Stream ID the
   client is not yet permitted to open MUST be treated as an
   HTTP_LIMIT_EXCEEDED error.

Here, stream 3 is certainly "permitted to open"

>  A reference to an element which
   is no longer in the tree is treated as a reference to the root of the
   tree.

"no longer" != "not yet"
If this is the current intended behavior here though, I would suggest to change it to allow the use case above.

> Due to reordering between streams, an element can also be prioritized
   which is not yet in the tree.  Such elements are added to the tree
   with the requested priority.

This one reads a bit weird to me... I assume it is talking about the case where you don't send an initial priority frame on the request stream itself, but rather only on the control stream, and that can arrive before the request stream itself. In this case I assume the priority frame is buffered until the stream is opened. 

This *could* be read to also apply to my situation above, but if that's the case I would make it a bit more explicit. If that's not the case, I would change it to something like "Due to reordering between the control stream and request streams, ..."

___

If I'm not missing something and this case is indeed not yet handled in the text, we might add something like "If a priority frame references a request stream that is permitted to be opened but which has not yet been opened, the priority frame MUST be applied once the referenced request stream becomes opened."

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 07 Mar 2019 13:46:15 -0800

I believe this has been addressed in the changes that removed the exclusive dependencies: see PR #2075.  The draft (version 18) states:

```
   If, by the time a new request stream is opened, its priority
   information has already been received via the control stream, the
   PRIORITY frame sent on the request stream MUST be ignored.
```

This answers your question, which is
> What happens if the priority frame from step C arrives before stream 3 is opened? We then have a priority update for stream 2, making it dependent on stream 3, which does not exist yet (at least at the receiving endpoint).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-470707450

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 07 Mar 2019 21:57:15 +0000 (UTC)

Would it be problematic to actually update the logical priority tree?

>From a DATA frame handling perspective, I'd be unable to serve data for node 3 (because I don't know what the request *is*). That seems like the same classification, unable to make progress, as defined in RFC 7540:

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

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-470710996

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 07 Mar 2019 13:59:08 -0800

No, it's not problematic -- just requires a [bit of coding](https://github.com/litespeedtech/lsquic-client/blob/201902251004-ietf-ID-18/src/liblsquic/lsquic_h3_prio.c).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-470711783

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 07 Mar 2019 14:03:03 -0800

I think this case is different to what you quote @dtikhonov. This is about prioritisation of 2 onto 3 before 3 exists. Not reprioritisation of 3 before it exists.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-470713368

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 07 Mar 2019 14:15:19 -0800

> This is about prioritisation of 2 onto 3 before 3 exists. Not reprioritisation of 3 before it exists.

Oh, you're right, @LPardue.  Nevertheless, there is still no problem.  As @rmarx points out:

```

So just record the information in the priority tree and wait for the stream to be opened.  There is no need to buffer this _PRIORITY_ frame.  At least, I don't see this need mandated by anything in the draft.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-470717972

---

From: Lucas Pardue <[email-masked]>
Date: Thu, 07 Mar 2019 14:19:22 -0800

I think we agree. My first post got received behind your first :)

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-470719592

---

From: Mike Bishop <[email-masked]>
Date: Fri, 08 Mar 2019 16:53:06 -0800

>From discussion, I think the intent of that text was that if a PRIORITY frame prioritizes _or references_ something that's not in the tree, the missing element gets added at the default priority.

So if C arrives before B, the tree would briefly have this layout:
~~~
  o
 / \
1   3
    |
    2
~~~

Yes, that means the prioritization isn't quite what the client intended until the other PRIORITY frame arrives -- our design goal was eventual consistency, not guaranteed lockstep. The safeguard against that is to repeat B on the control stream if you care.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-471128018

---

From: Robin Marx <[email-masked]>
Date: Tue, 12 Mar 2019 05:57:55 -0700

Thank you all for the comments.

While I agree with Lucas' point that not all streams in the priority tree have to exist yet (and that this is a nicer solution than buffering the priority frame), the fact that this can happen and that this should be treated as "unable to make progress" imo should be mentioned explicitly in the text then. 

The problem then indeed becomes that you get the situation described by Mike: there is no stream 3 yet, we don't know where it is in the tree, temporary 3 gets added as child of root node, stream 2 is now in effect a sibling of 1 instead of a child (since stream 3 is "unable to make progress"). This could be "briefly" but if the control stream is experiencing loss, it might last for 1RTT+, which might lead to some difficult to debug unwanted bandwidth allocations. 

The solution to that could indeed be to replicate stream 3's PRIORITY frame on the control stream as well, but that also feels a bit dirty... especially since a) this scheme is Chrome's default behavior for H2 and b) some of our tests indicate that this is a better default scheme than the current full round-robin one<sup>1</sup>. In this case, buffering the priority frame feels better to me. If we decide not to got for that route, I feel this use case (aka: "how to fake exclusive dependencies in H3") should be mentioned in the text. 

Summary of proposal: Either change to buffering behaviour or add additional text describing/clarifying A) non-opened streams can exist in the tree and B) how to fake exclusive dependencies. 

[1]: https://speeder.edm.uhasselt.be/www18/files/h2priorities_mwijnants_www2018.pdf

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-471989303

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 12 Mar 2019 06:10:38 -0700

The discussion in PR #2075 goes into some length when _PRIORITY_ frame duplication on the control stream is appropriate. We can port some of the language into the draft. It does not have to be a lot of text.

Of course non-opened streams can exist in the tree; it is not necessary to buffer frames.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-471993674

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 12 Mar 2019 13:16:47 +0000 (UTC)

One way to fake exclusive dependencies is, I think, to create a placeholder "spine" early in the connection. This is a static, ordered single branch tree of depth roughly equal to concurrency limit . Only one request is allowed per placeholder node, and it becomes easy to manage request leaves because you're just changing references to the placeholder that is always in the tree.

However, I'm still not completely convinced tree structures are the best way of managing priority in practice, and would entertain the idea of alternative priority scheme.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/2502#issuecomment-471995747