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

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 09 Aug 2018 06:25:15 -0700

_What follows is a modified version of the [original proposal on the mailing list](https://www.ietf.org/mail-archive/web/quic/current/msg04515.html).  It includes changes to address a few problems identified by @martinthomson._

Abstract
--------

The practical and theoretical problems caused by the unbounded absolute index values in the current QPACK Internet Draft are discussed.  The proposal to impose a limit on the range of absolute index values by wrapping them is presented.

Background
----------

The current QPACK draft states that

> [the] first entry inserted has an absolute index of "1"; indices increase sequentially with each insertion.

No upper limit is specified.  This is reasonable, as it is impossible to run out of numbers.

Nevertheless, an absolute index whose value is ever-increasing creates significant problems.

Problem 1: Compression Impact
-----------------------------

A large absolute index value has a negative effect on compression.  The unadjusted value of the
absolute index is used in the _Largest Reference_ field in the _Header Data Prefix_.

Larger values mean that more bytes are necessary to encode them.  For example, using 8-bit prefix integer encoding, values larger than  254 encode to 2 bytes, larger than 382 to 3 bytes, and larger than 16638 to 4 bytes.

Relatively quickly, the overhead associated with communicating the absolute index doubles and then triples.

Problem 2: Theoretical Concerns
-------------------------------

Why should compression at _t(1)_ be worse than at _t(0)_?  An ability to operate at the optimum level in perpetuity is a good property for a protocol to have.

Problem 3: Implementation Efficiency
------------------------------------

A QPACK implementation has to place some limits on the value of the absolute index -- simply because it has to pick an integral type to store it.  For example, uint64_t is likely large enough for all uses of the protocol, but it is wider than uint32_t and may be more expensive to process.  On other platforms, uint16_t may be the fastest integer; the unbounded nature of the absolute index would rule out its use.

Such limit also requires an [extra check](https://github.com/litespeedtech/ls-qpack/blob/122d1163eaca359f5d79cd608722b1b19acad15f/src/lsqpack.c#L1110) to cease inserting entries into the dynamic table once the maximum value for the integer is reached.  (One can run out of numbers in practice...)

Solution: Have the Absolute Index Wrap Around
---------------------------------------------

The main insight of the proposal is that the dynamic table has a bounded number of entries, that both encoder and decoder know what this number is, and that both can use this information to place an absolute index value communicated to it by its peer at the correct place in the sequence.

The dynamic table has a maximum size which is specified at the beginning of the connection and which never changes afterwards.  The current size of the table is the sum of all its entry sizes.  The entry size is the sum of the fixed overhead plus the lengths of the name and the value strings.  It is this fixed entry overhead that places a hard limit on the number of entries in the dynamic table:

```
    MaxEntries = MaxTableSize / FixedEntryOverhead
```

For example, using the current QPACK defaults, this number is

```
    MaxEntries = 4096 / 32 = 128
```

Imagine an encoder or decoder whose largest absolute index value (referred to as the total number of insertions in the QPACK draft) is `X`.  The smallest valid absolute index value its peer could possibly communicate to it is `X - MaxEntries + 1`.

The value of the largest possible absolute index value at a certain point in time cannot be known in the current specification of QPACK.  This is because the encoder is allowed to insert an unlimited number of entries into the dynamic table -- for example, speculative updates -- as long as their eviction is not blocked.  Nevertheless, such behavior is unlikely to be useful in practice.  The proposal is to limit the number of unacked insertions into the dynamic table to a multiple of `MaxEntries`.  Let's call this number `CeilMul`.

Given the two limits above, we can wrap the absolute index value without loss of information.  The proposal is to limit the absolute index values to the range

```
    [ 1, MaxEntries * (1 + CeilMul) ]
```

Continuing with the QPACK defaults example above and using `CeilMul = 1`, the sequence would go

```
    1, 2, 3, ... 254, 255, 256, 1, 2, ... (and so on).
```

The compression overhead cost is now a function of the maximum table size (and not a function of time as before).

To continue with our example, out of 256 possible values, 254 encode to 1 byte and 2 to two bytes.  A 64 KB table results in a maximum encoding of 3 bytes, while a 1 MB table has a maximum encoding of 4 bytes.

Changes to the Draft
--------------------

The following changes are necessary:
1. The definition of the absolute index changes: now its values are calculated using [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic).
1. The window size calculation based on the maximum dynamic table size needs to be added.

Conclusion
----------

Limiting the range of values the absolute index can have improves compression and implementation efficiency and removes the time penalty from the QPACK protocol.  A mechanism to do just that using existing QPACK parameters is hereby proposed.

-- 
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/issues/1644

---

From: Mike Bishop <[email-masked]>
Date: Thu, 09 Aug 2018 17:49:03 +0000 (UTC)

I don't disagree with the goals or the general mechanism.  However, given that the max table size can change unilaterally over the course of a connection, it seems problematic to use that to determine the wrapping point.  It needs to be something relatively stable over the lifetime of the connection, and that probably means the setting which bounds the max table size.

Even that can change on a 0-RTT connection when the SETTINGS frame is received, but there's a simple way around that (assuming #1641).  You tentatively calculate `MaxEntries` based on the remembered value, and prohibit sending more than `MaxEntries` entries prior to seeing the SETTINGS frame.  Once you see the SETTINGS frame, you know where the wrap point actually is and you can wrap if you need to.  For any reasonable value of the bound, that prohibition shouldn't be an issue.

-- 
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/issues/1644#issuecomment-411841355

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 09 Aug 2018 17:59:29 +0000 (UTC)

>  It needs to be something relatively stable over the lifetime of the connection, and that probably means the setting which bounds the max table size.

That's what I meant by the sentence _The dynamic table has a maximum size which is specified at the beginning of the connection and which never changes afterwards._

> You tentatively calculate `MaxEntries` based on the remembered value, and prohibit sending more than `MaxEntries` entries prior to seeing the SETTINGS frame. Once you see the SETTINGS frame, you know where the wrap point actually is and you can wrap if you need to. For any reasonable value of the bound, that prohibition shouldn't be an issue.

That's a good idea.  You can actually send up to `MaxEntries * CeilMul` (whatever `CeilMul` is set to in the end) until you see the _SETTINGS_ frame.

-- 
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/issues/1644#issuecomment-411844365

---

From: Mike Bishop <[email-masked]>
Date: Thu, 09 Aug 2018 11:31:54 -0700

Okay, just terminology, then.  Yes, I agree you can send as much as you're able to without wrapping, and artificially expanding the index range gives you more room at the potential price of bits in part of the sequence.

It seems like the more efficient way to do that would be to:
  - Calculate `MaxEntries`
  - Figure out how many bytes are required to encode `MaxEntries`
  - Wrap at the maximum number encodable in that number of bytes

It gets a less-fixed expansion, but the expansion is always free.  `MaxEntries` as defined will already always be enough items to overflow the table, so I'm not particularly inclined to be much more aggressive than that.  However, that's a little more obtuse to specify.

-- 
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/issues/1644#issuecomment-411853975

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 09 Aug 2018 11:57:01 -0700

Why do you think that the range can be as small as `MaxEntries`?  The proposal has it as at least twice that.

I think the price of expansion to the maximum encodable number can be steep.  If the window is 256, then the maximum encodable value in two bytes is 382.  When the window is 256, the average length of the encoded number is `(254 * 1 + 2 * 2) / 256 = 1.008`.  When you expand the window to 282, that number grows to `(254 * 1 + (382 - 254) * 2) / 382 = 1.335`.

-- 
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/issues/1644#issuecomment-411861293

---

From: Mike Bishop <[email-masked]>
Date: Thu, 09 Aug 2018 12:26:39 -0700

I think doubling-or-more is attempting to guard against a situation where X was valid pre-wrap but about to expire, then enough entries are added that X is valid again post-wrap, and there's confusion about whether a new frame refers to the old or new one, correct?  If so, the existing prohibition on evicting entries which still have references should ensure that there's no confusion, and the fact that real entry sizes will produce more of a gap in real usage further insulates us from the problem.  If it's intended to prevent a different issue, please clarify.

Your math about how much it costs is correct, but somewhat misconstrues the idea -- the window is being expanded to the rest of the byte *instead of* being doubled or more, not expanded after doubling.  For smaller table sizes, that's more conservative.

So for example, modulo any off-by-one errors in counting:

| MaxEntries | Expansion | Doubled |
|---|---|---|
| 128 | [0..254) = 1 byte | (254 * 1 + 2 * 2) / 256 = 1.008 bytes |
| 256 | [0..382) = (254 * 1 + 128 * 2) / 382 = 1.335 bytes | [0..512) = (254 * 1 + 128 * 2 + 130 * 3) = 1.76 bytes |
| 2000 | [0..16639) = (254 * 1 + 128 * 2 + 16257 * 3) = 2.96 bytes | [0..4000) = (254 * 1 + 128 * 2 + 3618 * 3) = 2.81 bytes

However, you're right that it becomes more tilted to the largest possible encoding once you pass two bytes, so that's not ideal for very large table sizes.

-- 
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/issues/1644#issuecomment-411869426

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 09 Aug 2018 13:56:11 -0700

> I think doubling-or-more is attempting to guard against a situation where X was valid pre-wrap but about to expire, then enough entries are added that X is valid again post-wrap, and there's confusion about whether a new frame refers to the old or new one, correct? If so,

Almost, but not quite (or maybe we _are_ talking about the same thing -- in that case, apologies):  The particular values of the index -- pre-wrap or post-wrap -- do not really matter, as what matters is where they are relative to the position of the latest entry -- either to the left of it or to the right of it.

> the existing prohibition on evicting entries which still have references should ensure that there's no confusion

Please note that a dynamic entry may have no references (e.g. a speculative update).  The encoder is currently allowed to insert an unlimited number of entries into the table -- and evict them -- if no headers reference them.

The purpose of making the window larger than `MaxEntries` is to provide low and high boundaries.  Since the numbers wrap, the decoder must be able to classify an incoming _Largest Reference_ as something that it is supposed to possess (the lower bound, or past) or as a future reference that the header block should be blocked on (the upper bound).

The low bound is the absolute index of the decoder's newest entry in the dynamic table minus `MaxEntries` plus one.  A difference of `MaxEntries` or more would indicate that the encoder has inserted more than `MaxEntries` into the dynamic table, which is an error.

Thus, the window must be at least `MaxEntries` to cover entries that may already exist.  Because the index wraps, we need more room for the "future" entries -- those on which the header block will block on.  The proposal is to extend the window another `MaxEntries` and place additional restrictions on the encoder to guarantee that no more than that number of entries be unacknowledged.

The full range of values can be separated into two broad sections, Past and Future:

```
  1                                                                       MaxAbsIndexId

  |                Past                             |              Future             |
  |  Error area     |   Current Dynamic Table     X |                                 |

                                                  ^
                                                  |
                                                  /
                                      Latest Entry
```

_(Absolute index value increases from left to right and then wraps around.  The diagram has `X = MaxEntries` for convenience.)_

After classifying the incoming _Largest Reference_ as Past or Future, the decoder either:
- Marks the header block as blocked and parks the stream (Future);
- Processes the header block (Past, with _Largest Reference_ pointing to a valid table entry); or
- Produces an error if the _Largest Reference_ points to an already-evicted entry.

Reserving `MaxEntries` for the lower bound and a healthy number of entries for the future entries makes for rules that are easy to reason about.  This gives us a theoretical guarantee, so to speak, without using arguments such as "in practice, entries are larger then the fixed overhead."  A smaller window, I am afraid, will require much more complicated rules.

-- 
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/issues/1644#issuecomment-411894178

---

From: Mike Bishop <[email-masked]>
Date: Thu, 09 Aug 2018 15:39:16 -0700

Okay, that helps a lot.  I see where you're coming from.

My perspective was that MaxEntries is an absolute bound on the size of the table, so if entries are off the end of the table (the "Error area" in your diagram) the correct interpretation would be that they're in the future.  That always allows some room to insert without acknowledgement, because of the difference between real entries and the zero-size entries used to calculate MaxEntries.  I don't think it leads to confusion since you have to reference the table on a stream to have anything to get confused by 😉 and once you've referenced an entry you have a new pin in how far the table can advance without acknowledgement.

In any scheme, you can't reuse a slot until the *eviction* of the item which previously occupied it has been acknowledged.  If the window is 2*MaxEntries or more, that's at least a full turnover of the table and the limit on unacknowledged entries automatically implies that requirement.  If the window is MaxEntries, you have to explicitly track that dependency which will create the limit on how many unacknowledged entries can exist.  I think either is easy enough to reason about, but yours tracks a single value rather than a ring buffer of references, which is a decided advantage.

Okay -- I'm sufficiently convinced.

-- 
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/issues/1644#issuecomment-411920382

---

From: Martin Thomson <[email-masked]>
Date: Thu, 09 Aug 2018 18:44:27 -0700

I'm also convinced and would like to see a PR.

CeilMul can be 1.  I don't see any point in entertaining anything less (too complicated) and anything more is bananas: you are creating a header block that is blocked for >1 RTT if that arrives.

I think that we should work with 0-based indexing.  HPACK having 1-based indexing was awful and we managed to get rid of that by tweaking the opcodes in QPACK.

Make sure that you include `floor()` in your calculation of MaxEntries.

I like Mike's addendum about 0-RTT.  We will need to be careful about that.  And implementations will need to test that specially.  Of course, for the table to wrap, you need to have evictions in 0-RTT, which won't happen because that takes round trips (at least two, with CeilMul at 1, I believe).  If you have round trips in your 0-RTT, something is badly wrong.

-- 
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/issues/1644#issuecomment-411949968

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 10 Aug 2018 05:57:38 -0700

I am glad that you approve the proposal, @MikeBishop and @martinthomson .  I will create a PR.

I agree: setting `CeilMul` to 1 is the best choice.  It gives the index range the property of being exactly twice the size of the maximum size of the dynamic table.  This permits some immediate optimizations in the implementation.

I also agree that beginning the dynamic table at index 0 is better, as this is how most of us index arrays (C, C++, Go, etc.).  Should this be a separate PR -- assuming that @afrind, @krasic, and @MikeBishop agree as well?  Also, shall we start the static table with 0 for consistency's sake?

The remarks regarding `floor()` and the 0-RTT scenario have been noted.

-- 
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/issues/1644#issuecomment-412074314

---

From: Mike Bishop <[email-masked]>
Date: Fri, 10 Aug 2018 16:43:06 +0000 (UTC)

No one's approval is needed to create the PR.  😉 

1-based indexing shows up wherever a sentinel is needed at 0, basically.  We managed to get rid of the sentinel requirement for table references (the static table actually is 0-based in QPACK, there's just nothing *in* slot 0 until I stop being lazy and get #1355 ready to go).  However, for absolute indices, 0 is currently the sentinel for "no dynamic references in this packet."  If we want to go back to using a flag for that, or if you have some other way to communicate that, there's no reason it ought to be 1-based.

-- 
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/issues/1644#issuecomment-412139139

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 10 Aug 2018 10:36:43 -0700

> 0 is currently the sentinel for "no dynamic references in this packet." If we want to go back to using a flag for that, or if you have some other way to communicate that, there's no reason it ought to be 1-based.

That's pretty easy: 0 means "no dynamic references", non-zero means "decode the value and subtract 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/issues/1644#issuecomment-412153296

---

From: Mike Bishop <[email-masked]>
Date: Fri, 10 Aug 2018 10:40:24 -0700

...which is functionally what we have now, just with different wording to describe it.  As far as I'm concerned, that's purely editorial semantics, so whatever @afrind wants is fine.

-- 
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/issues/1644#issuecomment-412154301

---

From: Martin Thomson <[email-masked]>
Date: Sun, 12 Aug 2018 17:27:45 -0700

I'm completely comfortable with largest reference starting at 1.  Because I use `len(table)` there; that is, the number of entries in the table.  In other words, "you need N entries available before you can use this header block"; as opposed to "the index of the last entry referenced in this header block is N".  It's better than trying to work out how to signal the special value.

-- 
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/issues/1644#issuecomment-412382372

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 13 Aug 2018 05:36:07 -0700

> In other words, "you need N entries available before you can use this header block"; as opposed to "the index of the last entry referenced in this header block is N".

I don't see how this could work.  Imagine a full table -- then, on average, one insertion results in one eviction.  The number of entries stays about the same.  This number does not tell you anything useful.  You need the actual index value.

-- 
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/issues/1644#issuecomment-412503086

---

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

The number counts insertions without regard for evictions that might happen.  It's no different in practice to the current number, but is simply moving the goalpost.

The other way of thinking of this is as follows:

```
0 -----
   header: value
1 -----
   other: 1
2 -----   <<< in 0-based indexing, this refers to the start of :host
   :host: example.com
3 -----   <<< but with our indexing scheme we work backwards
          <<<  so it makes sense to identify the end of the entry instead
```

That's consistent.

-- 
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/issues/1644#issuecomment-412672616

---

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

I am still lost.  Is this number the absolute index of the next entry to be inserted, then?

In that case, you will still need signaling -- this is because zero is a valid index value.  `0` cannot both mean "no references" and "reference to entry `MaxEntries * 2 - 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/issues/1644#issuecomment-412857880