Re: QPACK proposal: wrap absolute index values

[Ryan Hamilton <[e-mail]>]

Do we have any sense on the overall impact on compression efficiency base
on typical HTTP workloads?

On Sun, Aug 5, 2018 at 5:29 PM, Martin Thomson <[e-mail]>
wrote:

> Table State Synchronize is relative, so it wouldn't benefit from a
> change here.  That's something I missed initially, so it's probably a
> candidate for clearer text.
>
> I've no real opinion on the wrapping proposal.  It seems like it might
> work for the Largest Reference.  The math is a tiny bit annoying to
> decode in the same way the packet number encoding is, but it is
> doable.  I imagine that you reconstruct the Largest Reference based on
> the smallest index in the table.  That is:
>
> rotation = floor(table_size / 32)
> base = minimum - (minimum % rotation)
> # equivalently: base = floor(minimum / rotation) * rotation
> largest = encoded + base
> if largest < minimum:
>   largest += rotation
> On Mon, Aug 6, 2018 at 1:47 AM Dmitri Tikhonov
> <[e-mail]> wrote:
> >
> > 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.
> > There are two places in QPACK that use the unadjusted value of the
> > absolute index:
> >
> >     - the Largest Reference field in the Header Data Prefix; and
> >     - the Table State Synchronize instruction.
> >
> > 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 [1] 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 largest value is X + MaxEntries.  (All
> > other values would indicate a bug at one or both sides.)  The maximum
> > size of the valid absolute index values window, then, is MaxEntries * 2.
> >
> > Therefore, 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 * 2 ]
> >
> > Continuing with the QPACK defaults example above, 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 changes to the draft are small.  Only the definition of the
> > absolute index has to change; all instructions and encodings stay
> > the same.
> >
> > 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 and with minimal changes to the draft has been proposed.
> > I suggest that it be examined for flaws.  If none be found, I say let's
> > include it in the next version of the QPACK Internet Draft.
> >
> >
> >   - Dmitri.
> >
> > 1. https://github.com/litespeedtech/ls-qpack/blob/
> 122d1163eaca359f5d79cd608722b1b19acad15f/src/lsqpack.c#L1110
> >
>
>