Subject: [quicwg/base-drafts] In-order priority changes in HQ does not hold (#1865)

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 17 Oct 2018 07:14:26 -0700

draft-ietf-quic-http-15 states:

```
   For example, implicit in the HTTP/2 prioritization scheme is the
   notion of in-order delivery of priority changes (i.e., dependency
   tree mutations): since operations on the dependency tree such as
   reparenting a subtree are not commutative, both sender and receiver
   must apply them in the same order to ensure that both sides have a
   consistent view of the stream dependency tree.  HTTP/2 specifies
   priority assignments in PRIORITY frames and (optionally) in HEADERS
   frames.  To achieve in-order delivery of priority changes in HTTP/
   QUIC, PRIORITY frames are sent on the control stream and the PRIORITY
   section is removed from the HEADERS frame.
```

The current scheme does not achieve the in-order delivery of priority changes.  This is because a _PRIORITY_ frame to set the priority for an incoming request may arrive later than the request stream.  Since processing of a request is not delayed until its priority is known, it must be assigned some priority by the server.  To state it another way, a request possesses an implicit priority.

I don't think we can ensure in-order delivery of priority changes without introducing inter-stream dependencies and -- egads! -- head-of-line-blocking.  With that in mind, it may be good to allow a request stream to carry a _PRIORITY_ frame as its first frame.

-- 
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/1865

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 17 Oct 2018 07:23:40 -0700

> With that in mind, it may be good to allow a request stream to carry a PRIORITY frame as its first frame. 

Or add the PRIORITY section back to headers? 🙊 

-- 
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/1865#issuecomment-430649049

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 17 Oct 2018 07:40:34 -0700

Yes, the full _PRIORITY_ frame on a request stream is an overkill, as the `Prioritized Type` and `Prioritized Element ID` would be redundant.  We could use a new frame type for this purpose.

-- 
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/1865#issuecomment-430655450

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 17 Oct 2018 07:53:28 -0700

Does either suggestion solve the problem though? There is no in-order guarantee between request streams (from the server's perspective). I.e. server needs the a full tree before servicing a request, receiving a PRIORITY of the leaf node requires knowledge of the parent branches.

_disclaimer: not a prioritisation expert_

-- 
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/1865#issuecomment-430660964

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 17 Oct 2018 08:12:58 -0700

Since priorities are only advisory, I don't see why HQ must ensure an ordering of priority changes.  The server will do whatever it wants anyway.  One can assume that a good implementation will do something reasonable with the latest priority information it has.

-- 
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/1865#issuecomment-430668993

---

From: Mike Bishop <[email-masked]>
Date: Wed, 17 Oct 2018 09:47:35 -0700

HQ must ensure an ordering of changes because that's the only way the server can ever reach consistency with the client's view.  Delayed data on a single stream can cause delays in the server catching up to what the client wants -- and your observation that the request can arrive before its PRIORITY frame does is certainly a valid instance of that -- but reordering of valid priority instructions causes actual differences, not just delay.

The issue happens when things which affect the same element (even indirectly) get crossed.  For example, consider two instructions are in flight:
1. X depends exclusively on A
2. C depends on A

If the order is (1,2), then X and C are peers, both depending on A.  If the order is (2,1), then C now depends on X, which depends on A.

You could probably avoid this with a scheme which prohibits further changes to an element with unacknowledged priority changes in flight, but that requires a layer of machinery I don't think anyone is incented to build right now.  Alternatively, there's the direction of your last comment, which is that consistency between client's desires and server's understanding of them is either unnecessary or a lost cause; that's a pragmatic view, but perhaps not one I'd like to bake into the spec.

-- 
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/1865#issuecomment-430703532

---

From: Mike Bishop <[email-masked]>
Date: Wed, 17 Oct 2018 09:50:40 -0700

That said, it's an interesting proposal to have a tag at the beginning of a request that says, "In the absence of other guidance, I depend on X".  If no exclusive dependencies can be declared, it can't affect anything else; if it's always ignored if a PRIORITY frame has reprioritized that stream, the ordering can be reconstructed.

That's a very surgical fix to the issue of PRIORITY getting reordered with the stream opening.

-- 
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/1865#issuecomment-430704584

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 17 Oct 2018 09:57:40 -0700

The thought of removing Request-oriented prioritisation has crossed my mind. Instead just set up Placeholders at the start of the connection and use this "prioritisation prefix tag" to indicate preferred priority.

That feels like too much of a departure from H2's model though.

-- 
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/1865#issuecomment-430707065

---

From: Mike Bishop <[email-masked]>
Date: Wed, 17 Oct 2018 10:06:38 -0700

Yes, and there are situations where you want to be able to make changes mid-session where that doesn't work.  We already depart plenty, but I'd like to minimize gratuitous changes that have nothing to do with QUIC.  Let's leave that for the HTTP WG to do.  (See you there!)

-- 
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/1865#issuecomment-430709982

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sat, 20 Oct 2018 08:44:46 -0700

> Delayed data on a single stream can cause delays in the server catching up to what the client wants -- and your observation that the request can arrive before its PRIORITY frame does is certainly a valid instance of that -- **but** reordering of valid priority instructions causes actual differences, not just delay.

_[emphasis added]_

@MikeBishop, why the "but?" Since the server must prioritize a new request somehow when its _PRIORITY_ frame is delayed, are you sure there is no scenario wherein the reordering you describe can occur?

-- 
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/1865#issuecomment-431592988

---

From: Mike Bishop <[email-masked]>
Date: Sat, 20 Oct 2018 22:45:52 -0700

Of course I'm not, because there's an obvious one -- the server finishes sending the response before it sees the PRIORITY frame.  The request was handled at a different priority than it would have been had the client's wishes been known.

The Exclusive flag enables a PRIORITY frame about two elements to implicitly change the relationships of other elements, and that's what fundamentally makes the race inescapable.  If that flag didn't exist, I think Dmitri's solution would work quite elegantly.

Hmm....  *\*considers taking a bit out\**

-- 
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/1865#issuecomment-431640820