Subject: [quicwg/base-drafts] Use "Insert Count" rather than "Largest Reference" (#2111)

From: Martin Thomson <[email-masked]>
Date: Mon, 10 Dec 2018 23:06:45 -0800

The construction of largest reference currently implies the use of
1-based indexing, which is unnatural.  Using the insert count is much
more natural, even if it means the encoding is a little strange and a
tiny bit inefficient (it goes 0, 2, 3, ..., Max-1, 1, 2, ...).

I've gone through and put the references on the boundary between
records, which makes explanations much easier for post-base indexing in
my view.  I've renamed Base Index (which was never really an index) to
Base, which matches that change.  Similarly, renaming Largest Known
Received to Known Received Count makes it match better.

There are also examples added to Insert Count and Base sections.  These
definitions are pretty damned opaque without them.

Closes #2110.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Use "Insert Count" rather than "Largest Reference"

-- File Changes --

    M draft-ietf-quic-qpack.md (257)

-- Patch Links --

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

---

From: Martin Thomson <[email-masked]>
Date: Mon, 10 Dec 2018 23:11:07 -0800

@martinthomson pushed 1 commit.

3f8aad952fd8a3acf4fe921fc9f33b95c274ef38  Self-review fixes

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2111/files/5c9c3ee45d8a8440dea836839eafa6d2dcdfb31c..3f8aad952fd8a3acf4fe921fc9f33b95c274ef38

---

From: Martin Thomson <[email-masked]>
Date: Mon, 10 Dec 2018 23:13:10 -0800

120a51b94760db3d7fb2747de1a140a367fab90e  Missing colon

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2111/files/3f8aad952fd8a3acf4fe921fc9f33b95c274ef38..120a51b94760db3d7fb2747de1a140a367fab90e

---

From: afrind <[email-masked]>
Date: Tue, 18 Dec 2018 21:41:06 +0000 (UTC)

afrind commented on this pull request.

I'm not really sure that Largest Reference was so unclear or that this provides substantially more clarity.  Interested to hear what other think as well.

> @@ -249,18 +250,19 @@ 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 ({{header-prefix}}) 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. A stream becomes unblocked when the greatest absolute
-index in the dynamic table becomes greater than or equal to the Largest
-Reference for all header blocks the decoder has started reading from the stream.
-If the decoder encounters a header block where the actual largest reference is
-not equal to the Largest Reference declared in the prefix, it MAY treat this as
-a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED.
+Each header block contains the total number of entries added to the dynamic
+table - the Insert Count - which identifies the table state necessary for
+decoding (see {{header-prefix}}). If the Insert Count is greater than the number

I think this will be somewhat confusing, because the state of the table at the encoder at the time of encoding (insert count) can be different than the table state (insert count) required to decode a particular block.  Maybe if you called it 'Required Insert Count' in the header prefix that would make it clear that an encoder shouldn't just blindly use the actual Insert Count?

 n = count of entries inserted
 d = count of entries dropped
 ~~~~~
 {: title="Example Dynamic Table Indexing - Control Stream"}
 
 Because frames from request streams can be delivered out of order with
-instructions on the encoder stream, relative indices are relative to the Base
-Index at the beginning of the header block (see {{header-prefix}}). The Base
-Index is an absolute index. When interpreting the rest of the frame, the entry
-identified by Base Index has a relative index of zero.  The relative indices of
-entries do not change while interpreting headers on a request or push stream.
+instructions on the encoder stream, relative indices are relative to the Base at
+the beginning of the header block (see {{header-prefix}}). The Base is encoded
+as a value relative to the Insert Count, so it can be expressed as the number of
+entries inserted. The dynamic table entries up to the Base can be referenced.

What about post-base?

 n = count of entries inserted
 d = count of entries dropped
 ~~~~~
 {: title="Example Dynamic Table Indexing - Control Stream"}
 
 Because frames from request streams can be delivered out of order with
-instructions on the encoder stream, relative indices are relative to the Base
-Index at the beginning of the header block (see {{header-prefix}}). The Base
-Index is an absolute index. When interpreting the rest of the frame, the entry
-identified by Base Index has a relative index of zero.  The relative indices of
-entries do not change while interpreting headers on a request or push stream.
+instructions on the encoder stream, relative indices are relative to the Base at
+the beginning of the header block (see {{header-prefix}}). The Base is encoded
+as a value relative to the Insert Count, so it can be expressed as the number of
+entries inserted. The dynamic table entries up to the Base can be referenced.

> The Base is encoded as a value relative to the Insert Count, so it can be expressed as the number entries inserted

I'm having a hard time understanding why you are trying to say here.  That Base in the number of entries inserted?  Or the encoding of Base is the number of entries inserted?

 n = count of entries inserted
 d = count of entries dropped
 ~~~~~
 {: title="Example Dynamic Table Indexing - Control Stream"}
 
 Because frames from request streams can be delivered out of order with
-instructions on the encoder stream, relative indices are relative to the Base
-Index at the beginning of the header block (see {{header-prefix}}). The Base
-Index is an absolute index. When interpreting the rest of the frame, the entry
-identified by Base Index has a relative index of zero.  The relative indices of
-entries do not change while interpreting headers on a request or push stream.
+instructions on the encoder stream, relative indices are relative to the Base at
+the beginning of the header block (see {{header-prefix}}). The Base is encoded
+as a value relative to the Insert Count, so it can be expressed as the number of
+entries inserted. The dynamic table entries up to the Base can be referenced.
+The most recently inserted entry within the limit set by the Base has a relative
+index of 0.
+
+Though new entries could be added while processing a header block, the relative
+indices of entries do not change.

How are new entries added while processing a header block?  Do you mean on the encoder side?  Maybe encoding would be better than processing then?

 In order to identify which dynamic table entries can be safely used
 without a stream becoming blocked, the encoder tracks the absolute index of the
-decoder's Largest Known Received entry.
+decoder's Known Received Count entry.

What is the decoder's Known Received Count entry?  That doesn't really make sense to me, maybe just this sentence needs rewording.

What the encoder is tracking is the state of the decoder.  The state of either the encoder or the decoder can be uniquely identified by the number of inserts that it has performed on its dynamic table.  

Would it be helpful to call the a table's 'State' or 'Version'?  Or maybe change it from "Known Received Count" to "Decoder's Known Insert Count"?

 n = count of entries inserted
 d = count of entries dropped
 ~~~~~
 {: title="Example Dynamic Table Indexing - Control Stream"}
 
 Because frames from request streams can be delivered out of order with
-instructions on the encoder stream, relative indices are relative to the Base
-Index at the beginning of the header block (see {{header-prefix}}). The Base
-Index is an absolute index. When interpreting the rest of the frame, the entry
-identified by Base Index has a relative index of zero.  The relative indices of
-entries do not change while interpreting headers on a request or push stream.
+instructions on the encoder stream, relative indices are relative to the Base at
+the beginning of the header block (see {{header-prefix}}). The Base is encoded
+as a value relative to the Insert Count, so it can be expressed as the number of
+entries inserted. The dynamic table entries up to the Base can be referenced.
+The most recently inserted entry within the limit set by the Base has a relative

> The most recently inserted entry with the limit set by the Base

I think this is where calling it Base rather than Base Index becomes awkward.  Base Index tells you which entry in the table is relative index 0.

-- 
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/2111#pullrequestreview-186287017

---

From: Mike Bishop <[email-masked]>
Date: Tue, 18 Dec 2018 23:08:11 +0000 (UTC)

MikeBishop commented on this pull request.

I'm with Alan that this seems unnecessary.  Also, the largest reference and the number of entries inserted at the end of the encoding are often the same, but need not be.

In theory, you could process instructions on the encoder stream in parallel with interpreting a header block.  However, more likely this refers to entries getting inserted during encoding, and this is the wrong terminology.

-- 
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/2111#pullrequestreview-186323745

---

From: Martin Thomson <[email-masked]>
Date: Tue, 18 Dec 2018 19:49:10 -0800

7e7d7b5e7d7474d2f5c0bb8236113af547567e66  Rewrite some of the thorny pieces

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2111/files/120a51b94760db3d7fb2747de1a140a367fab90e..7e7d7b5e7d7474d2f5c0bb8236113af547567e66

---

From: Martin Thomson <[email-masked]>
Date: Tue, 18 Dec 2018 19:56:15 -0800

martinthomson commented on this pull request.

We never say whether we are using 0-based or 1-based indexing, but in using the term, we implicitly established that we use 1-based indexing.  Except that the draft is inconsistent throughout.  The static table starts at 0, relative indexing is 0-based (ish), but the largest reference is implicitly 1-based.  If I want to refer to the first entry, I send a 1. 

That's very confusing.  To me at least, maybe because I didn't ever internalize the bizarre internal logic that drove HPACK.

Changing to a count means that this is not relevant.  The indexing we do in the draft is all 0-based, as it should be.  But then there is less of a dependency on that because we're counting, not indexing, in the trickiest part.

I failed to update this text.  I will do that.

Yeah, I tried to fix this without changing it too much and that turned out badly.  I've a rewrite for you.

I was referring to parallel processing.  My implementation allows for that possibility.

-- 
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/2111#pullrequestreview-186377587

---

From: Martin Thomson <[email-masked]>
Date: Tue, 18 Dec 2018 22:12:20 -0800

5a58a9aa1466a9b298df43471f29147e2dd7e2ab  Wrap

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2111/files/4745b0667cc8fe73adfaed70482a664b5470103e..5a58a9aa1466a9b298df43471f29147e2dd7e2ab

---

From: afrind <[email-masked]>
Date: Wed, 19 Dec 2018 09:15:57 -0800

Did you include some js and svg files that you did not intend?  

-In order to identify which dynamic table entries can be safely used
-without a stream becoming blocked, the encoder tracks the absolute index of the
-decoder's Largest Known Received entry.
+In order to identify which dynamic table entries can be safely used without a
+stream becoming blocked, the encoder tracks the number of entries received by
+the decoder.  TheKnown Received Count tracks the total number of acknowledged

There's a missing space here

-- 
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/2111#pullrequestreview-186656443

---

From: Bence Béky <[email-masked]>
Date: Wed, 26 Dec 2018 10:41:35 -0800

bencebeky requested changes on this pull request.

I enthusiastically support this change for the following reasons:
* The Required Insert Count concept inherently is zero if there are no dynamic table references ("the lowest possible value of insert count with which this header block can be decoded").  No need for awkward language like what I am proposing at issue #2251 (which I'm happy to abandon in favor of this PR).  Sure one can add a clarifying note about the zero case, but this flows much better to me.
* This PR silently adds clarity by using distinct terms for the abstract value "Required Insert Count" and its encoding "EncodedInsertCount".  Me having proposed #2250 is a testimony that I feel strongly about this.  (And I'm happy to abandon #2250 in favor of this.)
* While I understand that this is purely editorial, I also feel strongly that dynamic table absolute indexing should be zero based, to match static table indexing, and indexing schemes in the majority of programming languages.  I never voiced this, because issue #1650 was shut down, in large part because 0 for Largest Reference is used to indicate no dynamic table references, making it convenient to start absolute indices with 1.  I support this change because it gets rid of this fairly artificial restriction, unblocking the discussion to change absolute indexing to more natural zero-based.

Couple of humble suggestions below.

-Reference for all header blocks the decoder has started reading from the stream.
-If the decoder encounters a header block where the actual largest reference is
-not equal to the Largest Reference declared in the prefix, it MAY treat this as
-a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED.
+Each header block contains the total number of entries added to the dynamic
+table - the Required Insert Count - which identifies the table state necessary
+for decoding (see {{header-prefix}}). If the Required Insert Count is greater
+than the number of dynamic table entries received, the stream is considered
+"blocked."  While blocked, header field data SHOULD remain in the blocked
+stream's flow control window.  When the Required Insert Count is zero, the frame
+contains no references to the dynamic table and can always be processed
+immediately. A stream becomes unblocked when the number of entries inserted in
+the dynamic table becomes greater than or equal to the Required Insert Count for
+all header blocks the decoder has started reading from the stream.  If the
+decoder encounters a header block where the largest Absolute Index used not

s/not equal to/is not equal to/ or s/not equal to/does not equal/

-Reference for all header blocks the decoder has started reading from the stream.
-If the decoder encounters a header block where the actual largest reference is
-not equal to the Largest Reference declared in the prefix, it MAY treat this as
-a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED.
+Each header block contains the total number of entries added to the dynamic
+table - the Required Insert Count - which identifies the table state necessary
+for decoding (see {{header-prefix}}). If the Required Insert Count is greater
+than the number of dynamic table entries received, the stream is considered
+"blocked."  While blocked, header field data SHOULD remain in the blocked
+stream's flow control window.  When the Required Insert Count is zero, the frame
+contains no references to the dynamic table and can always be processed
+immediately. A stream becomes unblocked when the number of entries inserted in
+the dynamic table becomes greater than or equal to the Required Insert Count for
+all header blocks the decoder has started reading from the stream.  If the
+decoder encounters a header block where the largest Absolute Index used not

"where the Required Insert Count does not match the definition in {{conventions-and-definitions}}, it MAY" to avoid having to talk explicitly about the case of no dynamic table references.

-If the decoder encounters a header block where the actual largest reference is
-not equal to the Largest Reference declared in the prefix, it MAY treat this as
-a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED.
+Each header block contains the total number of entries added to the dynamic
+table - the Required Insert Count - which identifies the table state necessary
+for decoding (see {{header-prefix}}). If the Required Insert Count is greater
+than the number of dynamic table entries received, the stream is considered
+"blocked."  While blocked, header field data SHOULD remain in the blocked
+stream's flow control window.  When the Required Insert Count is zero, the frame
+contains no references to the dynamic table and can always be processed
+immediately. A stream becomes unblocked when the number of entries inserted in
+the dynamic table becomes greater than or equal to the Required Insert Count for
+all header blocks the decoder has started reading from the stream.  If the
+decoder encounters a header block where the largest Absolute Index used not
+equal to the largest value permitted by the Required Insert Count, it MAY treat

s/permitted/communicated/ or s/permitted/specified/

>  +---+---------------------------+
 |      Compressed Headers     ...
 +-------------------------------+
 ~~~~~~~~~~
 {:#fig-base-index title="Frame Payload"}
 
-#### Largest Reference
+#### Insert Count

s/Insert Count/Required Insert Count/ here and below throughout.

-`Largest Reference` identifies the largest absolute dynamic index referenced in
-the block.  Blocking decoders use the Largest Reference to determine when it is
-safe to process the rest of the block.  If Largest Reference is greater than
-zero, the encoder transforms it as follows before encoding:
+`Insert Count` identifies the state of the dynamic table needed to process the
+header block successfully.  Blocking decoders use the Insert Count to determine
+when it is safe to process the rest of the block.  If Insert Count is greater

Explicitly include the case of RequiredInsertCount == 0.  (Currently EncodedInsertCount is undefined in that case.)

 ~~~~~~~~~~  drawing
   0   1   2   3   4   5   6   7
 +---+---+---+---+---+---+---+---+
-|     Largest Reference (8+)    |
+|   Required Insert Count (8+)  |

s/Required Insert Count/EncodedInsertCount/

> @@ -784,29 +798,29 @@ streams emit the headers for an HTTP request or response.
 
 ### Header Data Prefix {#header-prefix}
 
-Header data is prefixed with two integers, `Largest Reference` and `Base Index`.
+Header data is prefixed with two integers, `Required Insert Count` and `Base`.

In wire format sections I usually see an explicit textual description of all fields.  Consider adding some text similar to https://github.com/quicwg/base-drafts/pull/2250/files#diff-c3ed24528f71fade042cdefbeadbd7b9R787.

Maybe "Each header block contains a Required Insert Count, the lowest possible value for the Insert Count with which the header block can be decoded.  For a header block with no references to the dynamic table, the Required Insert Count is zero."?

"Unlike on the encoder stream, relative indices on push and request streams are relative to the Base at the beginning of the header block (see bla).  This allows for the mapping from relative indices to absolute indices to not be affected by dynamic table insertions on the encoder stream, regardless of what order the decoder processes request stream and encoder stream instructions.", and scratch the paragraph "Though new entries..." below.  Processing order encompasses on-the-wire reordering as well as the parallel processing case, and specifically talking about "mapping" makes it unnecessary to mention blocking in this sentence.

> @@ -923,10 +948,9 @@ header field name matches the header field name of an entry stored in the static
 table or the dynamic table.
 
 If the entry is in the static table, or in the dynamic table with an absolute
-index less than or equal to Base Index, this representation starts with the '01'
-two-bit pattern.  If the entry is in the dynamic table with an absolute index
-greater than Base Index, the representation starts with the '0000' four-bit
-pattern.
+index less than the Base, this representation starts with the '01' two-bit

Are you changing one-based absolute indexing to zero-based in this PR?  Then update 3.2.4 Absolute Indexing, #indexing.  Or maybe do this in a separate PR?

 ### Literal Header Field With Post-Base Name Reference
 
-For entries in the dynamic table with an absolute index greater than Base Index,
+For entries in the dynamic table with an absolute index greater than the Base,

If you change "less than or equal to" to "less than" above, maybe "greate than" here should be changed to "greater than or equal to"?

-- 
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/2111#pullrequestreview-187935117

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Dec 2018 17:57:38 -0800

@martinthomson pushed 4 commits.

3da4d1f14e0d795fd2f32e103c5e23492f6461e0  Some editorial changes
3a434690741d9e497d5c15d1b509501068af872d  Base editorial changes
9ccc5caabd0a2b6ba1f8225830556687ec4a0b45  Text format description for header block prefix
c6296d477fead565b297ccdb96e3a98a08476b43  Change absolute indices to 0-based too

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2111/files/79f819ffdeb06c80fe30dce5dba5d37da45433fe..c6296d477fead565b297ccdb96e3a98a08476b43

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Dec 2018 17:59:13 -0800

39f9930445e718bb0f34746a0e77c13328e989c2  >=Base

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2111/files/c6296d477fead565b297ccdb96e3a98a08476b43..39f9930445e718bb0f34746a0e77c13328e989c2

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Dec 2018 18:00:02 -0800

Thanks for the comments @bencebeky.

I think that this needs to change absolute indexing to 0-based to be consistent.  That makes everything else better.

Thanks, that prompted me to restructure this (massive) paragraph.

I think that I'm OK with this as is.  Repeating the requirement is OK if that requirement is tricky.

Thanks.  That's better.

 

Yeah, that is a good idea.  The prose here was a little light.

 ~~~~~~~~~~  drawing
   0   1   2   3   4   5   6   7

I think that I'll stick with Required Insert Count at this level.

 |      Compressed Headers     ...
 
-#### Largest Reference
+#### Insert Count

Done.  Thanks.

-- 
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/2111#pullrequestreview-188456171