Subject: [quicwg/base-drafts] Better Indexing in QPACK (#1314)

From: Mike Bishop <[email-masked]>
Date: Fri, 20 Apr 2018 15:51:47 -0700

Adds a section more clearly (I hope!) explaining how indices work in different contexts.  Cleans up a whole mess of index-related issues in the process.

Fixes #1176, #1145, #1136, #1130, #1128, #1125.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Better Indexing

-- File Changes --

    M draft-ietf-quic-http.md (4)
    M draft-ietf-quic-qpack.md (214)

-- Patch Links --

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

---

From: Mike Bishop <[email-masked]>
Date: Fri, 20 Apr 2018 15:56:58 -0700

@MikeBishop pushed 1 commit.

c2341b1  BLOCKING was in HTTP, too.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1314/files/149dae261d0794156b2a863c206ebca0df6c2327..c2341b1163321ee25689604792229ff5cf093e65

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 24 Apr 2018 09:40:47 -0700

LPardue approved this pull request.

> +    +---+-----+  -  +-----+   -   +
+              |  0  | ... | n-d-3 |  Relative Index
+              +-----+-----+-------+
+                 ^
+                 |
+             Base Index
+
+n = count of entries inserted
+d = count of entries dropped
+~~~~~
+{: title="Dynamic Table Indexing - Request Stream"}
+
+Entries with an absolute index greater than a frame's Base Index cannot be
+referenced by that frame.  If the decoder encounters a reference to an entry
+which has already been dropped from the table, this MUST be treated as a stream
+error of type `HTTP_QPACK_DECOMPRESSION_FAILED` error code.  If this reference

> this MUST be treated as a stream error of type `HTTP_QPACK_DECOMPRESSION_FAILED` error code

seems a bit clunky

-- 
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/1314#pullrequestreview-114869796

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Apr 2018 10:37:06 -0700

MikeBishop commented on this pull request.

Yeah, that's the discussion in #1176.  It's clunky, but what's better?  Otherwise, a delayed packet can cause your entire compression context to blow up.  The other alternatives discussed require major changes to how the HTTP layer uses QUIC that I'm not comfortable with.

I did have one other idea, which is to add a second acknowledgment type to QPACK, and require it to be sent if a stream was aborted without reading to the end.  Then the encoder has to consider even reset streams to still be outstanding until it receives something from the other side.

-- 
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/1314#discussion_r183819880

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 24 Apr 2018 17:41:52 +0000 (UTC)

LPardue commented on this pull request.

Sorry, simpler issue, I just meant the language was clunky, "stream error of type X error code". Reducing to using type or error code would work I think

-- 
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/1314#discussion_r183821302

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Apr 2018 18:19:20 +0000 (UTC)

Ah -- *that's* an easy fix!

-- 
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/1314#discussion_r183832870

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Apr 2018 18:20:17 +0000 (UTC)

026d9a9  Less clunky

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1314/files/eb45712bb3941a44bf6d177bfcc51df8416ec398..026d9a919caa96cb88d61cdb9d47f7e552118f8d

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Apr 2018 11:23:34 -0700

a2c9791  Match language used elsewhere

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1314/files/026d9a919caa96cb88d61cdb9d47f7e552118f8d..a2c9791f1097162d09deb732fc1be1aaf8dc3654

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 24 Apr 2018 18:42:57 +0000 (UTC)

Lgtm

-- 
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/1314#issuecomment-384038164

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 25 Apr 2018 14:01:10 +0000 (UTC)

dtikhonov requested changes on this pull request.

Looks good, just two small issues.  The pictures are very helpful.

> +The first entry inserted has an absolute index of "1"; indices
+increase sequentially with each insertion.
+
+On the control stream, a relative index of "0" always refers to the most
+recently inserted value in the dynamic table.  Note that this means the
+entry referenced by a given relative index can change while interpreting
+a HEADERS frame as new entries are inserted.
+
+~~~~~ drawing
+    +---+---------------+-------+
+    | n |      ...      | d + 1 |  Absolute Index
+    + - +---------------+   -   +
+    | 0 |      ...      | n-d-1 |  Relative Index
+    +---+---------------+-------+
+      ^                     |
+      |                     V

While RFC7541 has Insertion Point on the left and Dropping Point on the right, I think it would be more intuitive if the Absolute Index grew left-to-right.

+n = count of entries inserted
+d = count of entries dropped
+~~~~~
+{: title="Dynamic Table Indexing - Control Stream"}
+
+Because frames from request streams can be delivered out of order with
+instructions on the control stream, relative indices are based on the Base Index
+(see {{absolute-index}}) included in the HEADERS or PUSH_PROMISE frame.  The
+Base Index is the absolute index of the entry which has the relative index of
+zero when interpreting the frame.  The relative indices of entries do not change
+while interpreting headers on a request or push stream.
+
+~~~~~ drawing
+    +---+-----+-----+-----+-------+
+    | n | n-2 | n-3 | ... |  d+1  |  Absolute Index

I think you missed `n-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/1314#pullrequestreview-115187931

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 12:33:47 -0700

ace84a9  Fix index in drawing

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

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 12:36:48 -0700

Whatever we do, either absolute or relative will be starting at the greatest number and counting down.  Given that relative is what's sent in instructions, I found that to be more intuitive, personally.  I'm open to swapping them if most people prefer, though.

-- 
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/1314#discussion_r184181854

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 12:36:57 -0700

Good catch!

-- 
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/1314#discussion_r184181905

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 25 Apr 2018 20:45:23 +0000 (UTC)

dtikhonov approved this pull request.

LGTM.  The left-to-right issue is not really a bug, but rather a preference.

-- 
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/1314#pullrequestreview-115347538

---

From: afrind <[email-masked]>
Date: Wed, 25 Apr 2018 14:10:59 -0700

afrind commented on this pull request.

+    | n | n-1 | n-2 | ... |  d+1  |  Absolute Index

Since Base Index is an absolute index, would it be more intuitive to have this on the top of the drawing pointing down?

+Insertion Point         Dropping Point

"...relative indices are relative to the Base Index..." perhaps?

+
+~~~~~ drawing
+    | n | n-1 | n-2 | ... |  d+1  |  Absolute Index

Include the word 'example' in the caption?

> @@ -225,9 +273,8 @@ represented as an 8-bit prefix string literal.
 ### Duplicate {#indexed-duplicate}
 
 Duplication of an existing entry in the dynamic table starts with the '000'
-three-bit pattern.  The index of the existing entry is represented as an integer
-with a 5-bit prefix. Table indices are always non-zero; a table index of zero
-MUST be treated as a decoding error.
+three-bit pattern.  The absolute index of the existing entry is represented as

Why absolute?  Because it's ordered on the control stream, this can be relative to N=number of inserts.

+Insertion Point         Dropping Point

You mention Base Index here like it's a field in the HEADERS or PUSH_PROMISE frame, but it looks more like the beginning of the header block below.

I have a slight preference for absolute index growing left-to-right, but I can live with it as is too.

-- 
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/1314#pullrequestreview-115353033

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 14:28:50 -0700

#1128.  You're almost certainly going to duplicate entries which have the largest possible relative index in your table.  Unless your table has wrapped multiple times, that means they have a relatively *small* absolute index.  On the flip side, the size of this will grow continuously over the lifetime of a connection while the relative index is at least bounded.

For ideal compression, this would be relative to the total number of drops (so the last item in the table is 0, etc.), but I was really hesitant to introduce a third (fourth, given #1239) way of indexing entries in the same table.

-- 
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/1314#discussion_r184211565

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 21:59:21 +0000 (UTC)

74acf83  Alan's feedback

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1314/files/ace84a9c3bd904c7af807a1e7b2d4d18d858ea59..74acf83d51ad3d59138f9ed9126442fe863bad9a

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 15:06:08 -0700

5eae922  Example

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1314/files/74acf83d51ad3d59138f9ed9126442fe863bad9a..5eae922720f39fac2a09566d8cb059b216a5f6c4

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 15:43:17 -0700

Okay, you've convinced me.  😀 

-- 
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/1314#discussion_r184227015

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Apr 2018 16:00:42 -0700

2b3e651  Another example + duplicate on relative

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1314/files/5eae922720f39fac2a09566d8cb059b216a5f6c4..2b3e6515f9f6f62557364dcf8dfa119b4e243610

---

From: afrind <[email-masked]>
Date: Wed, 25 Apr 2018 23:34:20 +0000 (UTC)

afrind 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/1314#pullrequestreview-115389672

---

From: afrind <[email-masked]>
Date: Thu, 26 Apr 2018 15:51:56 +0000 (UTC)

Merged #1314.

-- 
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/1314#event-1596882082