Subject: Re: [quicwg/base-drafts] QPACK Blocking Setting (#1143)

From: Mike Bishop <[email-masked]>
Date: Wed, 09 May 2018 12:33:57 -0700

How about SETTINGS_QPACK_BLOCKED_STREAMS?

-- 
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/1143#issuecomment-387850769

---

From: Mike Bishop <[email-masked]>
Date: Wed, 09 May 2018 13:29:05 -0700

@MikeBishop pushed 1 commit.

c2b3fe8  Martin's feedback

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1143/files/7b81097b0c2446b291b2a8bc7763f848b17377aa..c2b3fe892d35318ab4ff4bbed135e669f2469fe9

---

From: Martin Thomson <[email-masked]>
Date: Wed, 09 May 2018 15:32:05 -0700

martinthomson requested changes on this pull request.

Worked it out.  No need for the term "vulnerable" at all.

> @@ -95,17 +95,29 @@ reintroduced by HPACK when the loss includes a HEADERS frame.
 
 ## Avoiding Head-of-Line Blocking in HTTP/QUIC {#overview-hol-avoidance}
 
-In the example above, the second stream contained a reference to data
-which might not yet have been processed by the recipient.  Such references
-are called "vulnerable," because the loss of a different packet can keep
-the reference from being usable.
-
-The encoder can choose on a per-header-block basis whether to favor higher
+Because QUIC does not guarantee order between data on different streams, a
+reference might be received on a request stream to an entry which is not yet in

request streams aren't the only affected streams

"a header block might reference an entry in the dynamic table that has not yet been received."

> @@ -95,17 +95,29 @@ reintroduced by HPACK when the loss includes a HEADERS frame.
 
 ## Avoiding Head-of-Line Blocking in HTTP/QUIC {#overview-hol-avoidance}
 
-In the example above, the second stream contained a reference to data
-which might not yet have been processed by the recipient.  Such references
-are called "vulnerable," because the loss of a different packet can keep
-the reference from being usable.
-
-The encoder can choose on a per-header-block basis whether to favor higher
+Because QUIC does not guarantee order between data on different streams, a
+reference might be received on a request stream to an entry which is not yet in
+the dynamic table. References are called "vulnerable" when they refer to entries
+whose receipt has not been confirmed by the peer, because loss or reordering can
+keep the reference from being immediately usable.  If the reference cannot be
+immediately processed on receipt, the stream is considered "blocked."

I *still* don't like "vulnerable" and I think that I understand better now.  The problem is that you are putting the cart before the horse.  The problem is that the decoder might block.  The focus on the encoder side is wrong.

Hence, I suggest, without the word "vulnerable" at all:

> [The QUIC is not ordered preface]. A decoder that receives a reference to a dynamic table entry that has not been received is "blocked".
>
> An encoder can decide whether to risk having a header block becoming blocked at a decoder.  Compression efficiency can be improved by referencing dynamic table entries that are still in transit, but if there is packet loss or reordering a decoder can become blocked.  An encoder avoids the risk of blocking by only referencing dynamic table entries that have been acknowledged, though this means using literals, which make the header block larger.  Larger header blocks can result in an encoder become blocked on congestion or flow control limits.
>
> A decoder can permit the possibility of blocking references using the SETTINGS_QPACK_BLOCKING_REFERENCES setting.  This setting sets an upper bound on the number of header blocks that can reference unacknowledged entries in the dynamic table.  An encoder respects this setting when deciding whether to reference unacknowledged dynamic table entries.
>
> Every header block contains a Largest Reference (see ...).  This is used to determine the minimum number of entries need to be present in the dynamic table before the header block can be successfully decoded.  A decoder becomes blocked if the Largest Reference is greater than the number of dynamic table entries that it has received.
>
> An encoder MUST limit the number of unacknowledged header blocks that reference unacknowledged dynamic table entries to the value of the SETTINGS_...  A decoder that is blocked on a number of header blocks equal to the limit it advertised SHOULD treat receipt of an additional blocked header block [awkward] as a stream error of type HTTP_...

Or something like that. 

> @@ -547,9 +559,9 @@ have outstanding (unacknowledged) references.
 An encoder MUST ensure that a header block which references a dynamic table
 entry is not received by the decoder after the referenced entry has already been
 evicted, and MUST ensure that the decoder will not suffer head-of-line blocking
-if the decoder has not opted to receive blocking references. Even if the decoder
-is willing to process blocking references, the encoder might choose to avoid
-them in certain cases.
+if the decoder has not opted to receive vulnerable references. Even if the

End the sentence after "evicted".  Then "An encoder also respects the limit set by the decoder on the number of header blocks that are allow to be blocked."

-- 
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/1143#pullrequestreview-118920325

---

From: afrind <[email-masked]>
Date: Wed, 09 May 2018 15:50:53 -0700

afrind commented on this pull request.

 

I think this is a workable direction.  We should be consistent about blocked vs blocking (I prefer blocked), and what is blocked - is it the stream, header block, or reference?

A single header block may contain many references to unacknowledged entries, so it's not blocked references the decoder is counting, but header blocks.  It seems logical that the entire stream should be blocked until the blocked header block is decoded, but perhaps the text needs to be more explicit about it.

All of this to say that I like Mike's suggestion: SETTINGS_QPACK_BLOCKED_STREAMS.

-- 
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/1143#discussion_r187198485

---

From: Martin Thomson <[email-masked]>
Date: Wed, 09 May 2018 18:29:37 -0700

martinthomson commented on this pull request.

 

Yes, I think that the unit is header blocks.  A decoder is blocked on the decoding of a header block.  

We can generalize that to streams, since the correspondence is perfect to streams: a blocked header block is a blocked stream.  In fact, we should...

Thinking more about that, if an endpoint is silly and they read a blocked header block, then concentrating on header blocks might be wrong.  A message with trailers has two header blocks and if both are blocked, you might expect the encoder to only account for one lot of blocking.  But a silly decoder might find itself blocked on both header and trailer at the same time.  Specifying this as the number of streams that have a decoder blocked on the decoding of a header block with unresolved references to the dynamic table is ideal.

-- 
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/1143#discussion_r187219662

---

From: Mike Bishop <[email-masked]>
Date: Thu, 10 May 2018 09:56:26 -0700

MikeBishop commented on this pull request.

 

I agree that the unit should be streams; the decoder SHOULD NOT be reading even the body of the header block, which means it won't see any further header blocks on that stream.  A cautious encoder might choose to count blocks for simplicity, but the decoder's count will almost certainly be one per stream.  A silly decoder might read further in an attempt to over-optimize, and specifying the blocking count to be streams helps keep them from blowing up.

-- 
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/1143#discussion_r187391474

---

From: Mike Bishop <[email-masked]>
Date: Thu, 10 May 2018 10:22:19 -0700

f10d1cc  Adapting Martin's text

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1143/files/c2b3fe892d35318ab4ff4bbed135e669f2469fe9..f10d1cc59c5c717e5d42845e4094a4a35c35edde

---

From: Martin Thomson <[email-masked]>
Date: Thu, 10 May 2018 17:45:58 -0700

martinthomson approved this pull request.

The MUST is a problem.  I trust that you can fix that though.

> -compression ratio (by permitting vulnerable references) or HoL resilience (by
-avoiding them).
-
-An encoder MUST NOT have header blocks which contain vulnerable references
-outstanding on more streams than the value of SETTINGS_QPACK_BLOCKED_STREAMS at
-any time. Note that the decoder's count of streams which are actually blocked
-will be less than or equal to the encoder's count of references which are
-vulnerable (potentially blocking).  If the decoder encounters more blocked
+header block might reference an entry in the dynamic table that has not yet been
+received.
+
+Each header block contains a Largest Reference (see {{absolute-index}}) which
+identifies the table state necessary for decoding. If the greatest absolute
+index in the dynamic table is less than the value of the Largest Reference, the
+stream is considered "blocked."  While blocked, header field data MUST remain in
+the blocked stream's flow control window.  When the Largest Reference is zero,

I don't think that there is an interoperability requirement here.  Holding data outstanding is advice, not a requirement.

> +identifies the table state necessary for decoding. If the greatest absolute
+index in the dynamic table is less than the value of the Largest Reference, the
+stream is considered "blocked."  While blocked, header field data MUST remain in
+the blocked stream's flow control window.  When the Largest Reference is zero,
+the frame contains no references to the dynamic table and can always be
+processed immediately.
+
+A decoder can permit the possibility of blocked streams by setting
+SETTINGS_QPACK_BLOCKED_STREAMS to a non-zero value.  This setting specifies an
+upper bound on the number of streams which can be blocked.
+
+An encoder can decide whether to risk having a stream become blocked. If
+permitted by the value of SETTINGS_QPACK_BLOCKED_STREAMS, compression efficiency
+can be improved by referencing dynamic table entries that are still in transit,
+but if there is loss or reordering the stream can become blocked at the decoder.
+An encoder avoids the rist of blocking by only referencing dynamic table entries

typo: risk

> +SETTINGS_QPACK_BLOCKED_STREAMS to a non-zero value.  This setting specifies an
+upper bound on the number of streams which can be blocked.
+
+An encoder can decide whether to risk having a stream become blocked. If
+permitted by the value of SETTINGS_QPACK_BLOCKED_STREAMS, compression efficiency
+can be improved by referencing dynamic table entries that are still in transit,
+but if there is loss or reordering the stream can become blocked at the decoder.
+An encoder avoids the rist of blocking by only referencing dynamic table entries
+which have been acknowledged, but this means using literals. Since literals make
+the header block larger, this can result in the encoder becoming blocked on
+congestion or flow control limits.
+
+An encoder MUST limit the number of streams which could become blocked to the
+value of SETTINGS_QPACK_BLOCKED_STREAMS at all times. Note that the decoder's
+count of streams which are actually blocked will be at most the encoder's count
+of streams which could become blocked.  If the decoder encounters more blocked

How about simply: "A decoder might not be forced to block on streams that risk being blocked."

-- 
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/1143#pullrequestreview-119290645

---

From: Mike Bishop <[email-masked]>
Date: Fri, 11 May 2018 14:19:25 -0700

e19cd23  Martin's rewords

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1143/files/f10d1cc59c5c717e5d42845e4094a4a35c35edde..e19cd23aa8d662d5fcaef33207aa30f0bb0f51a0

---

From: afrind <[email-masked]>
Date: Mon, 14 May 2018 16:19:07 -0700

> -decoder and cannot be processed until the greatest absolute index in the dynamic
-table is at least the value of the Largest Reference.  While blocked, header
-field data MUST remain in the blocked stream's flow control window.  When the
-Largest Reference is zero, the frame contains no references to the dynamic table
-and can always be processed immediately.
+Because QUIC does not guarantee order between data on different streams, a
+header block might reference an entry in the dynamic table that has not yet been
+received.
+
+Each header block contains a Largest Reference (see {{absolute-index}}) which
+identifies the table state necessary for decoding. If the greatest absolute
+index in the dynamic table is less than the value of the Largest Reference, the
+stream is considered "blocked."  While blocked, header field data should remain
+in the blocked stream's flow control window.  When the Largest Reference is
+zero, the frame contains no references to the dynamic table and can always be
+processed immediately.

We probably need to explain when a stream becomes unblocked.

-- 
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/1143#pullrequestreview-120042585

---

From: Mike Bishop <[email-masked]>
Date: Mon, 14 May 2018 16:50:35 -0700

0779dbc  Describe unblocking

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1143/files/e19cd23aa8d662d5fcaef33207aa30f0bb0f51a0..0779dbcb852122a1a01126e7d0a4a2b578dcf78f

---

From: afrind <[email-masked]>
Date: Mon, 14 May 2018 16:57:30 -0700

Merged #1143.

-- 
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/1143#event-1626045997