Subject: [quicwg/base-drafts] QPACK: wrap absolute index values (#1657)

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 13 Aug 2018 13:18:27 -0700

Resolves #1644.

Includes #1650 and #1642.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Start indexing dynamic QPACK table beginning at zero
  * Initial table size is the maximum permitted when table is first usable
  * Some Martin tweaks
  * Limit range of the absolute index: wrap the values
  * Recalculate MaxEntries should the server increase max table size

-- File Changes --

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

-- Patch Links --

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

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 13 Aug 2018 13:20:10 -0700

I think that it may make sense to rename _Largest Reference_ to _Latest Reference_.  This would remove the now-ambiguous term "larger."

-- 
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/1657#issuecomment-412649848

---

From: Martin Thomson <[email-masked]>
Date: Mon, 13 Aug 2018 14:39:45 -0700

Or "Table State" to match the "Table State Synchronize" instruction.

-- 
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/1657#issuecomment-412674256

---

From: Martin Thomson <[email-masked]>
Date: Mon, 13 Aug 2018 19:56:27 -0700

martinthomson commented on this pull request.

The structure around the description of largest reference would seem to need more work.  I'd like to get that groundwork in place first.

 Each entry possesses both an absolute index which is fixed for the lifetime of
 that entry and a relative index which changes over time based on the context of
-the reference. The first entry inserted has an absolute index of "1"; indices
-increase sequentially with each insertion.
+the reference.
+
+The absolute index takes on the values in the range
+
+~~~
+   [ 0, MaxEntries * 2 - 1 ]

Inclusive, I presume.

> @@ -251,14 +299,33 @@ 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 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
+Each header block contains a Largest Reference field which identifies the
+table state necessary for decoding.
+
+When the Largest Reference value is not specified, the frame contains no

You need to explain what "not specified" means.  Here, that's an encoded value of 0.

> -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
+Each header block contains a Largest Reference field which identifies the
+table state necessary for decoding.
+
+When the Largest Reference value is not specified, the frame contains no
+references to the dynamic table and can always be processed immediately.
+
+When it is specified, the Largest Reference value is compared with
+the absolute index value of the next entry to be inserted into the
+dynamic table.  That entry's absolute index value divides the absolute

This explanation, relying on the "next entry to be inserted" is awkward.  As I suggested, if you count the total number of inserts, you get something easier to manage:

```
0 -----
  First: Insert (i.e., Index 8)
1 -----
...
  Index: 1
8 -----
  Index: 0
9 -----  << Base offset = 2 (or -2, I forget which this is).
  Post-Base: 0
10 -----
  Post-Base: 1
11 -----  << Table state = 11
  This: Can't be referenced
12 -----
```

Then you can say that the signaled table state and the decoder's view of the table state might differ, but only by less than `MaxEntries`.  That means that if `SignaledTableState%(MaxEntries*2)` differs from `LocalTableState` by more than MaxEntries, then it needs to be wrapped to get the full table state.

Don't worry about describing these in terms of absolute values.  I think that's easier than having the variables be modulo `2MaxEntries`.

> @@ -312,6 +379,11 @@ for example because the encoder or the decoder have chosen not to risk blocked
 streams, the decoder sends a Table State Synchronize instruction (see
 {{table-state-synchronize}}).
 
+### Insertion Throttling
+
+The encoder MUST NOT create -- either via insertion or duplication -- more
+than "MaxEntries" unacknowledged dynamic table entries.

This text prevents an encoder from sending the insertions, but it doesn't prevent it from attempting to reference them.  I would start by saying that an encoder *cannot* reference dynamic table entries that have an absolute index more than MaxEntries greater than the largest acknowledged value.

I would prefer to lean more strongly on different advice.  If we say that an encoder MUST NOT reference a table state that it has not sent at least once we get a stronger guarantee.  The text here is only correct in that it prevents the table from extending more than MaxEntries into the future, but it doesn't also cover the point regarding references to those entries.

I'd also like to get more context here.  Why?

-- 
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/1657#pullrequestreview-145899749

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 14 Aug 2018 05:54:03 -0700

dtikhonov commented on this pull request.

The reference restriction is specified in another place in the document:

> 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.

This guarantees that the encoder won't reference an entry that's more than `MaxEntries` away.

A header block cannot reference entries more than `MaxEntries - 1` slots apart.  This holds both for past and future entries.  Why do we need more restrictions?

The advice that
> an encoder MUST NOT reference a table state that it has not sent at least once
seems like a stronger version of the warning about deadlocks (which does not exist in the current draft).

Point taken regarding the context; I'll add it.

-- 
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/1657#discussion_r209938777

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 14 Aug 2018 05:56:00 -0700

> Or "Table State" to match the "Table State Synchronize" instruction.

`TSS` transmits deltas, whereas `Largest Reference` specifies an absolute position in the table.  How could they match?

-- 
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/1657#issuecomment-412861886

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 14 Aug 2018 05:57:12 -0700

Yes, inclusive.  Is something more that using square brackets required?

-- 
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/1657#discussion_r209939817

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 14 Aug 2018 12:59:49 +0000 (UTC)

Will a forward reference do?  I'd like to avoid discussing the actual encoding of the _Largest Reference_ in two places.

-- 
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/1657#discussion_r209940641

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 14 Aug 2018 06:11:28 -0700

I used the "next entry to be inserted" because I see no other way to describe the initial state, when there is no "last inserted entry."  Perhaps we could add the concept of "cursor?"

The "total number of inserts" concept eludes me.  The diagram is confusing, as it combines both encoder instructions (`Insert`) and header block instructions (`Post-Base`).

1. If the "total number of inserts" is the number of inserts performed while encoding a given header block, how does the decoder know where to start?
1. If this number is added to the current absolute index, then it is the same as _Largest Reference_.
1. ?

-- 
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/1657#discussion_r209944304

---

From: Martin Thomson <[email-masked]>
Date: Tue, 14 Aug 2018 17:42:27 -0700

> TSS transmits deltas, whereas Largest Reference specifies an absolute position in the table. How could they match?

Table State Synchronize transmits deltas to the table state?

-- 
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/1657#issuecomment-413059899

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 15 Aug 2018 04:09:56 -0700

Yes, _the [TSS] instruction specifies the total number of dynamic table inserts and duplications **since the last** Table State Synchronize or Header Acknowledgement that increased the Largest Known Received dynamic table entry._  (Emphasis added).

The _Largest Reference_, on the other hand, communicates the exact state (or position) in the dynamic table.  Counting all the inserts will work, of course (modulo `MaxEntries * 2`), but it will defeat the purpose of the proposed change, as the encoded representation will now grow.

-- 
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/1657#issuecomment-413166216