Subject: [quicwg/base-drafts] Placeholder -1 (#2690)

From: Mike Bishop <[email-masked]>
Date: Fri, 10 May 2019 11:28:40 -0700

Fixes #2502 by creating a "special" placeholder that's always a zero-weight child of the root.  This is the new default dependency.  As a result, resources with unknown initial priority will briefly get low priority instead of briefly getting high priority and disrupting actual high-priority resources.

If we're going to have a zero-weighted placeholder, it makes sense to allow zero-weighting in general, so I added that at the same time.  Also filled a few editorial gaps in the priority section (mostly concepts assumed from H2 that aren't explicitly stated) since I noticed them while working on this.  Can separate those out if this doesn't get traction.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Placeholder -1
  * Dependency on unknown

-- File Changes --

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

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2690.patch
https://github.com/quicwg/base-drafts/pull/2690.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/2690

---

From: ianswett <[email-masked]>
Date: Fri, 10 May 2019 11:41:15 -0700

ianswett commented on this pull request.

> +cannot be reprioritized.  The structure of the dependency tree changes as
+PRIORITY frames modify the dependency links between other prioritized elements.
+
+All dependent streams are allocated an integer weight between 0 and 255
+(inclusive).
+
+Streams with the same parent SHOULD be allocated resources proportionally based
+on their weight.  Thus, if stream B depends on stream A with weight 4, stream C
+depends on stream A with weight 12, and no progress can be made on stream A,
+stream B ideally receives one-third of the resources allocated to stream C.
+
+A weight of zero indicates that no resources should be allocated to the
+indicated stream if progress can be made on other streams dependent on the same
+parent.
+
+A reference to an element which is no longer in the tree is treated as a

If I read this correctly, if I reference stream 10 in a priority frame for stream 100 and you've removed all state for 10, 100 gets no resources whatsoever until all other requests finish?

That seems awful, so I must be missing something.

-- 
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/2690#pullrequestreview-236256709

---

From: Mike Bishop <[email-masked]>
Date: Fri, 10 May 2019 11:46:44 -0700

MikeBishop commented on this pull request.

>From [Section 5.3.2](https://quicwg.org/base-drafts/draft-ietf-quic-http.html#priority-tree-maintenance):
> For prioritization purposes, a node in the tree is considered “inactive” when the corresponding stream has been closed for at least two round-trip times (using any reasonable estimate available on the server).

and

> Clients SHOULD assume the server is actively performing such pruning and SHOULD NOT declare a dependency on a stream it knows to have been closed.

So, yes, it is awful.  Is it more awful than saying it's the most important thing in the system because it parents directly to the root?  That's seriously context-dependent.  I'm inclined to minimize harm from a lost/delayed PRIORITY frame over minimizing harm from a misbehaving client.

-- 
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/2690#discussion_r283001767

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 10 May 2019 17:09:59 -0700

kazuho commented on this pull request.

Nice work! LGTM module the point below.

> @@ -1102,18 +1109,33 @@ that can be prioritized are:
 
 Taken together, the dependencies across all prioritized elements in a connection
 form a dependency tree. An element can depend on another element or on the root
-of the tree. A reference to an element which is no longer in the tree is treated
-as a reference to the root of the tree. The structure of the dependency tree
-changes as PRIORITY frames modify the dependency links between prioritized
-elements.
-
-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.
+of the tree.  The tree also contains a dedicated placeholder with index "-1"

Could we call it something else than "-1" placeholder? Maybe "orphan placeholder".

The reason I feel uncomfortable with calling it "-1" are:
* It is not actually an index.
* We already have a placeholder that is called by name "root".

-- 
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/2690#pullrequestreview-236351251

---

From: Martin Thomson <[email-masked]>
Date: Sun, 12 May 2019 16:41:21 -0700

martinthomson commented on this pull request.

I prefer Kazuho's idea here about "-1".  Though I disagree about weight 0.  HTTP/2 didn't have it, which makes this more complicated.  I don't even think that you need weight 0, that's a gratuitous change in this PR.  You can simply say that streams with an "orphaned" priority is not given resources until all prioritized streams are handled.

-- 
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/2690#discussion_r283160418

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 12 May 2019 17:13:01 -0700

Clarification: my intent was to state what exactly @martinthomson recommends.

-- 
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/2690#discussion_r283161943

---

From: Mike Bishop <[email-masked]>
Date: Mon, 13 May 2019 18:17:10 +0000 (UTC)

@MikeBishop pushed 1 commit.

8741911f38487d5928414c1cd60ad89d2d506c55  Orphan; -1 is an implementation detail

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2690/files/5b7f49e837ef46af3a5b8779bbfb5b8fb0dd9164..8741911f38487d5928414c1cd60ad89d2d506c55

---

From: Mike Bishop <[email-masked]>
Date: Mon, 13 May 2019 11:20:25 -0700

But I _want_ weight=0!  😉

More seriously, I think calling it "orphan placeholder" is more elegant than -1, and a negative index is a totally reasonable implementation-internal way of tracking this, so done.  I removed the weight=0 definition and brought back the weight-plus-one definition.

-- 
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/2690#issuecomment-491931750

---

From: Lucas Pardue <[email-masked]>
Date: Mon, 13 May 2019 11:39:26 -0700

Can we call it after a famous orphan? Darwin perhaps? That would go well with the an award for relying on this behaviour all the time

-- 
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/2690#issuecomment-491938208

---

From: Robin Marx <[email-masked]>
Date: Thu, 16 May 2019 07:02:31 -0700

rmarx commented on this pull request.

This is the main crux and why I proposed adding the orphan placeholder in the first place. Imo, it makes more sense for stream 100 to get no bandwidth, than to make it part of the root and thus make it one of the most important resources in the tree (even if it just has a weight of 16). 

-- 
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/2690#discussion_r284722202

---

From: Robin Marx <[email-masked]>
Date: Thu, 16 May 2019 07:10:17 -0700

I want to come back to weight=0 for a moment, because it would allow use to make a node not receive any bandwidth until all its children are finished. 

For example, as I discussed here https://github.com/quicwg/base-drafts/issues/2502#issuecomment-491246513, a way to subvert the need for exclusive priorities is to work with a sort of priority "bucket" system with the placeholders. However, as can be seen in the 2nd image, P1, the buckets would get a weight of 1, where ideally that would be 0. 1 means they would still get 1/257th of the bandwidth (again, see P1, split between the HIGH placeholder and the HTML file). With weight 0, we could make this type of bucket system more semantically correct (arguably, 1/257th is too small to matter in practice, but still...). This might partially help circumvent the need for #2700, as discussed in https://github.com/quicwg/base-drafts/pull/2700#issuecomment-493076309

-- 
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/2690#issuecomment-493083556

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 16 May 2019 18:17:01 -0700

> I want to come back to weight=0 for a moment, because it would allow use to make a node not receive any bandwidth until all its children are finished.

I believe you mean "until all its siblings are finished."

> Imo weights between 0 and 255 works as well as between 1 and 256. You might say the weight=0 is a 'special case' but I would disagree: a zero-th share of the bandwidth is 0, it makes sense semantically.

I think the counterargument would be you are supposed to use a dependency chain for ordering the responses. And assuming that is the case, I think I prefer not diverting from what we do in HTTP/2 in minor ways, because that would cause confusion among the users of HTTP.

-- 
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/2690#issuecomment-493283763

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 30 May 2019 23:49:42 -0700

FWIW, we've implement this.

Orphan placeholder was indeed a simplification for us; we could revert the introduction of `implicitly_initialized` flag that we had to make to the HTTP/2 scheduler (see https://github.com/quicwg/base-drafts/issues/2502#issuecomment-490330136). Now, we are using the HTTP/2 scheduler as-is in our HTTP/3 stack.

-- 
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/2690#issuecomment-497596898