Subject: [quicwg/base-drafts] Core concepts for QPACK (#1357)

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

Borrows a lot of RFC7540 text into the introduction to make it less critical to fully understand HPACK prior to reading the QPACK spec.  (Note that it's not a goal of this PR to make this spec fully independent of HPACK, but rather to have the core concepts live in QPACK and reference specific sections of RFC7541 for concrete items like the Huffman table, integer encodings, etc.)

Also moved the Indexing discussion into the Introduction to live with this text, since it's thematically related.  Along the way, removed the text that QPACK is a "relatively non-intrusive extension to HPACK" since, well, it's not.  ;-)
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Core concepts

-- File Changes --

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

-- Patch Links --

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

---

From: Martin Thomson <[email-masked]>
Date: Fri, 18 May 2018 15:57:18 -0700

martinthomson commented on this pull request.

This is a good idea.

> +
+An encoder can choose to use less capacity than this maximum size (see
+{{size-update}}), but the chosen size MUST stay lower than or equal to the
+maximum set by the decoder.  Whenever the maximum size for the dynamic table is
+reduced, entries are evicted from the end of the dynamic table until the size of
+the dynamic table is less than or equal to the maximum size.
+
+This mechanism can be used to completely clear entries from the dynamic table by
+setting a maximum size of 0, which can subsequently be restored.
+
+### Indexing
+
+Entries in the QPACK static and dynamic tables are addressed separately.
+
+While entries in the static table have the same indices at all times, entries
+are inserted into the dynamic table over time.  Each entry possesses both an

change

> +reduced, entries are evicted from the end of the dynamic table until the size of
+the dynamic table is less than or equal to the maximum size.
+
+This mechanism can be used to completely clear entries from the dynamic table by
+setting a maximum size of 0, which can subsequently be restored.
+
+### Indexing
+
+Entries in the QPACK static and dynamic tables are addressed separately.
+
+While entries in the static table have the same indices at all times, entries
+are inserted into the dynamic table over time.  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.

You need to explain that relative indexes increase in the opposite direction to the absolute index.  This is the most confusing aspect of this entire thing.

> +    | 0 |      ...      | n-d-1 |  Relative Index
+    +---+---------------+-------+
+      ^                     |
+      |                     V
+Insertion Point         Dropping Point
+
+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 control stream, relative indices are relative to the Base
+Index at the beginning of the header block (see {{absolute-index}}). 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

You can drop the "which has" onwards.  I find it confusing.  How about: "The Base Index is an absolute index.  All subsequent references use relative index, with the entry identified in the Base Index having a relative index of 0."

> +~~~~~ drawing
+             Base Index
+                 |
+                 V
+    +---+-----+-----+-----+-------+
+    | n | n-1 | n-2 | ... |  d+1  |  Absolute Index
+    +---+-----+  -  +-----+   -   +
+              |  0  | ... | n-d-3 |  Relative Index
+              +-----+-----+-------+
+
+n = count of entries inserted
+d = count of entries dropped
+~~~~~
+{: title="Example Dynamic Table Indexing - Request Stream"}
+
+Entries with an absolute index greater than a frame's Base Index can be

Explain why: "A header block on the request stream can reference entries added after the entry identified by the Base Index.  This allows an encoder to process a header block in a single pass and include references to entries added while processing this (or other) header blocks.  Newly added entries are referenced using Post-Base instructions.  Indices for Post-Base instructions increase in the same direction as absolute indices, but the zero value is one higher than the Base Index."

> +~~~~~ drawing
+             Base Index
+                 |
+                 V
+    +---+-----+-----+-----+-------+
+    | n | n-1 | n-2 | ... |  d+1  |  Absolute Index
+    +---+-----+  -  +-----+   -   +
+              |  0  | ... | n-d-3 |  Relative Index
+              +-----+-----+-------+
+
+n = count of entries inserted
+d = count of entries dropped
+~~~~~
+{: title="Example Dynamic Table Indexing - Request Stream"}
+
+Entries with an absolute index greater than a frame's Base Index can be

Also, is the Largest Reference a Post-Base index?  It should be.

-QPACK is intended to be a relatively non-intrusive extension to HPACK; an
-implementation should be easily shared within stacks supporting both HTTP/2 over
-(TLS+)TCP and HTTP/QUIC.
+## Header Tables

Make this h1.

-If the packet containing a header is lost, that stream cannot complete header
-processing until the packet is retransmitted.  This is unavoidable. However,
-other streams which rely on the state created by that packet *also* cannot make
-progress. This is the problem which QUIC solves in general, but which is
-reintroduced by HPACK when the loss includes a HEADERS frame.
+### Static Table {#table-static}
+
+The static table consists of a predefined static list of header fields.  Its
+entries are defined in Appendix A of {{!RFC7541}}. Note that because HPACK did
+not use zero-based references, there is no value at index zero of the static
+table.
+
+### Dynamic Table {#table-dynamic}

This would benefit from subsections so that people can find Absolute and Relative indexing, "Base Index", Post-Base, etc...

-- 
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/1357#pullrequestreview-121591572

---

From: Mike Bishop <[email-masked]>
Date: Fri, 18 May 2018 20:03:57 -0700

MikeBishop commented on this pull request.

Clarity

-- 
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/1357#discussion_r189423173

---

From: Mike Bishop <[email-masked]>
Date: Fri, 18 May 2018 20:05:58 -0700

+             Base Index
+                 |
+                 V

Not quite, though LR and Base are given one as absolute and one relative to the other. LR might be less than Base, or more, or the same. 

-- 
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/1357#discussion_r189423207

---

From: Martin Thomson <[email-masked]>
Date: Sun, 20 May 2018 15:58:54 -0700

table [change] over 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/1357#discussion_r189473124

---

From: Martin Thomson <[email-masked]>
Date: Sun, 20 May 2018 16:00:05 -0700

+             Base Index
+                 |
+                 V

I don't think that there is any value in having Largest Reference with a lower absolute value than the Base Index.  I mean, sure, it can happen, but why would you encode that?

-- 
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/1357#discussion_r189473153

---

From: Mike Bishop <[email-masked]>
Date: Mon, 21 May 2018 09:48:20 -0700

+             Base Index
+                 |
+                 V

Because a likely algorithm would be that Base is the largest entry you've inserted in the dynamic table, before you've examined the incoming header set.  If you don't wind up using entries that are in flight (or any entries, in the extreme case), then Largest Reference will indicate that the most recent entries aren't needed.

-- 
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/1357#discussion_r189647453

---

From: Mike Bishop <[email-masked]>
Date: Mon, 21 May 2018 10:11:25 -0700

@MikeBishop pushed 1 commit.

eade0aa  Re-level sections, Martin's comments

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

---

From: Martin Thomson <[email-masked]>
Date: Mon, 21 May 2018 16:27:02 -0700

+             Base Index
+                 |
+                 V

Right.  Of course.

-- 
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/1357#discussion_r189740878

---

From: afrind <[email-masked]>
Date: Tue, 22 May 2018 14:06:29 -0700

afrind commented on this pull request.

> +The static table consists of a predefined static list of header fields, each of
+which has a fixed index over time.  Its entries are defined in Appendix A of
+{{!RFC7541}}. Note that because HPACK did not use zero-based references, there
+is no value at index zero of the static table.
+
+## Dynamic Table {#table-dynamic}
+
+The dynamic table consists of a list of header fields maintained in first-in,
+first-out order.  The dynamic table is initially empty.  Entries are added by
+instructions on the Encoder Stream (see {{encoder-stream}}).
+
+Before a new entry is added to the dynamic table, entries are evicted from the
+end of the dynamic table until the size of the dynamic table is less than or
+equal to (maximum size - new entry size) or until the table is empty.
+
+If the size of the new entry is less than or equal to the maximum size, that

This is of course HPACK's behavior too, but it's a very inefficient way to accomplish this goal.  Is it worth mentioning that two dynamic table size update commands will accomplish the same effect with fewer bytes on the wire?

+The dynamic table consists of a list of header fields maintained in first-in,
+first-out order.  The dynamic table is initially empty.  Entries are added by
+instructions on the Encoder Stream (see {{encoder-stream}}).
+
+Before a new entry is added to the dynamic table, entries are evicted from the
+end of the dynamic table until the size of the dynamic table is less than or
+equal to (maximum size - new entry size) or until the table is empty.
+
+If the size of the new entry is less than or equal to the maximum size, that
+entry is added to the table.  It is not an error to attempt to add an entry that
+is larger than the maximum size; an attempt to add an entry larger than the
+maximum size causes the table to be emptied of all existing entries and results
+in an empty table.
+
+A new entry can reference the name of an entry in the dynamic table that will be

It can also reference the entire entry: eg Duplicate

+### Absolute and Relative Indexing {#indexing}
+
+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 relative index begins at zero and increases in the opposite direction from
+the absolute index.  Determining which entry has a relative index of "0" depends
+on the context of the reference.
+
+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.

HEADERS frames do not insert entries.

> +increase sequentially with each insertion.
+
+The relative index begins at zero and increases in the opposite direction from
+the absolute index.  Determining which entry has a relative index of "0" depends
+on the context of the reference.
+
+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

Nit: d + 1 has spaces around the operator and n-d-1 does not.  My preference would be to expand the column so both could have spaces.

-- 
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/1357#pullrequestreview-122350259

---

From: Mike Bishop <[email-masked]>
Date: Tue, 22 May 2018 16:00:33 -0700

If you're doing this intentionally, that's a better approach and might be worth mentioning.  However, I think we need to define what happens in this situation regardless, and the HPACK precedent is *a* logical choice.

-- 
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/1357#discussion_r190079257

---

From: Mike Bishop <[email-masked]>
Date: Tue, 22 May 2018 16:03:57 -0700

2bd45a0  Alan's comments

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1357/files/eade0aab84d87da1e696840ba695fb9e45b4f176..2bd45a03a758123324d6888347e240826e9ee37c

---

From: Martin Thomson <[email-masked]>
Date: Wed, 23 May 2018 18:05:39 -0700

Given that there is zero utility from blowing the table out like this, I think that we might be better prohibiting that outright.  In HPACK, this caused the header to be emitted as well, but here all you are doing is wasting bytes.

-- 
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/1357#discussion_r190440970

---

From: Mike Bishop <[email-masked]>
Date: Thu, 24 May 2018 11:23:32 -0700

So inserting a header that's larger than the static table is a hard error?  Works for 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/1357#discussion_r190685121

---

From: Mike Bishop <[email-masked]>
Date: Thu, 24 May 2018 18:26:15 +0000 (UTC)

f82f117  Blow out table, blow up connection

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1357/files/2bd45a03a758123324d6888347e240826e9ee37c..f82f11768959d8da210fc1c450baa219bac9ec0f

---

From: afrind <[email-masked]>
Date: Fri, 25 May 2018 16:23:47 -0700

Merged #1357.

-- 
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/1357#event-1647637578