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

[Dmitri Tikhonov <[e-mail]>]

_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