Subject: [quicwg/base-drafts] Define INITIAL_PRIORITY frame and remove exclusive dependencies (#2075)

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Nov 2018 15:59:37 -0800

Fixes #1865.  The observations from the issue discussion are:
- HTTP/2's "exclusive" prioritization (which make the prioritized element the sole child of the parent, making all current parents children of the prioritized element instead) is the cause of many ordering headaches and actually makes it impossible to guarantee an eventually-consistent view of priority between client and server.
- If a PRIORITY frame gets delayed and a request is quickly processed, it may be processed immediately (default is pretty high) and only later be discovered to be unimportant.

In the absence of exclusive dependencies, it's possible for a request stream to carry its own initial priority, as @dtikhonov proposed.  This is guaranteed to be the first time that a priority is assigned to this request, and subsequent PRIORITY frames always override it.  (If a PRIORITY frame gets reordered ahead, INITIAL_PRIORITY is ignored.)

This is a further departure from RFC 7540's priority scheme, but as it appears exclusive priorities and reordering are somewhat incompatible, I believe is still within our design space.

**Depends on #2074; retarget before merging.**
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/2075

-- Commit Summary --

  * INITIAL_PRIORITY

-- File Changes --

    M draft-ietf-quic-http.md (87)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2075.patch
https://github.com/quicwg/base-drafts/pull/2075.diff

-- 
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/pull/2075

---

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Nov 2018 16:00:48 -0800

(I considered making this a stream header on request streams, but since it's optional, decided a frame type was probably more appropriate.  I'm open to being convinced otherwise.)

-- 
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/pull/2075#issuecomment-443039698

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Nov 2018 17:14:04 -0800

martinthomson commented on this pull request.

I don't know if the exclusive thing need to be bundled in here.

There needs to be more text in this about managing races with PRIORITY frames.  You have resolved the question of which one takes precedence, but you should mention that the identified dependency might have default priority when this is received, resulting in potentially inconsistent prioritization.  Not a big problem, but worth noting I think.

@ddragana, do you know if we use the exclusive thing in our priority setup at all?

> @@ -496,13 +496,9 @@ The PRIORITY frame payload has the following fields:
   : A two-bit field indicating the type of element being depended on.
 
   Empty:
-  : A three-bit field which MUST be zero when sent and MUST be ignored
+  : A four-bit field which MUST be zero when sent and MUST be ignored
     on receipt.

Not really for this, but do we have to mandate ignoring reserved fields?

> +
+~~~~~~~~~~  drawing
+ 0                   1                   2                   3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+|DT |   Empty   |           Element Dependency ID (i)         ...
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+|   Weight (8)  |
++-+-+-+-+-+-+-+-+
+~~~~~~~~~~
+{: #fig-initial-priority title="INITIAL_PRIORITY frame payload"}
+
+The INITIAL_PRIORITY frame payload has the following fields:
+
+  Dependency Type:
+  : A two-bit field indicating the type of element being depended on.

The alignment of the dependency type in comparison to PRIORITY is unfortunate.

-- 
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/pull/2075#pullrequestreview-180086578

---

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Nov 2018 22:59:40 -0800

MikeBishop commented on this pull request.

   Empty:

If you don't, you risk an overzealous implementation enforcing the "MUST be zero" and we can't use it later without negotiation.  "MUST ignore" seems cleaner than "MUST not die in flames if it's not zero."

-- 
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/pull/2075#discussion_r237762806

---

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Nov 2018 23:00:18 -0800

+~~~~~~~~~~  drawing
+ 0                   1                   2                   3

True -- I considered having a separate two-bit empty field, but that also felt unfortunate.  If you think that's the better of two evils, I'm fine.

-- 
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/pull/2075#discussion_r237762911

---

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Nov 2018 23:02:37 -0800

The necessity of the Exclusive change might be debatable, but I think it is needed.  Without Exclusive, there's an obvious race -- INITIAL_PRIORITY is racing with an Exclusive dependency on the parent, and the outcome on the server is indeterminate.  With the exclusive change, it's possible to make the outcome of this addition deterministic.

-- 
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/pull/2075#issuecomment-443111440

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 30 Nov 2018 06:56:49 -0800

dtikhonov approved this pull request.

-- 
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/pull/2075#pullrequestreview-180300549

---

From: Ryan Hamilton <[email-masked]>
Date: Fri, 30 Nov 2018 16:19:58 -0800

With HTTP/2, the initial HEADERS frame carries the priority information for the request. I wonder if instead of introducing an INITIAL_PRIORITY frame it would be simpler to bundle this initial priority information into the HEADERS frame instead. That would have the advantage of matching HTTP/2.

-- 
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/pull/2075#issuecomment-443379135

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 30 Nov 2018 17:17:44 -0800

@RyanAtGoogle 
> I wonder if instead of introducing an INITIAL_PRIORITY frame it would be simpler to bundle this initial priority information into the HEADERS frame instead. That would have the advantage of matching HTTP/2.

I am afraid that creates a race condition. If a PRIORITY frame of stream X says that it depends on stream Y, and if PRIORITY frame of stream Y says it depends on X, the server cannot tell which to apply first. IIUC, the observation behind this PR is that the ordering between INITIAL_PRIORITY and PRIORITY frames can be recovered; i.e., any reference to a stream from a PRIORITY frame is guaranteed to occur after the INITIAL_PRIORITY frame of that frame is issued.

-- 
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/pull/2075#issuecomment-443386238

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 30 Nov 2018 17:27:41 -0800

kazuho commented on this pull request.

+~~~~~~~~~~  drawing
+ 0                   1                   2                   3

Considering the fact that we are changing the definition of the PRIORITY frame, it might make sense to change the order of the flags and fields as well.

Specifically, we can move the PT to the end of the flags and PEID to the end of the fields. That would help us having a unified decoder for the two frames. Additionally, we might call PEID an optional field that only exists when the frame is sent over a control stream, thereby unifiying the frame definition to one.

-- 
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/pull/2075#discussion_r238045649