Subject: QPACK proposal: wrap absolute index values

From: Dmitri Tikhonov <[email-masked]>
Date: Sun, 5 Aug 2018 11:46:50 -0400

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

---

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Aug 2018 10:29:50 +1000

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

---

From: Ryan Hamilton <[email-masked]>
Date: Sun, 5 Aug 2018 20:14:55 -0700

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 <[email-masked]>
wrote:

> > 1. https://github.com/litespeedtech/ls-qpack/blob/
> 122d1163eaca359f5d79cd608722b1b19acad15f/src/lsqpack.c#L1110
> >
>
>

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sun, 5 Aug 2018 23:33:30 -0400

> on typical HTTP workloads?

The "typical" part is somewhat subjective.  The impact is on compression
would be more pronounced in scenarios where the header blocks are smaller
(meaning that the dynamic table has slower churn).  For example, a small
HAR I've been working with as example to our QPACK implementation contains
18 requests.  The header blocks and the encoder stream compress to about
1 KB.  An overhead of 2 bytes per header block would translate to

    18 * 2 / 1024 = ~4%

The penalty is not dramatic, but it's not insignificant, either.

  - Dmitri.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sun, 5 Aug 2018 23:40:37 -0400

> candidate for clearer text.

I think the text looks fine -- I simply was not reading it carefully
enough.

> doable.

Yes, it is similar to the packet number logic, except that unlike the
packet number, the absolute index wraps around.

  - Dmitri.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 6 Aug 2018 00:36:11 -0400

> # equivalently: base = floor(minimum / rotation) * rotation

My thinking is that there is no need to reconstruct the Largest
Reference, as the encoded value represents the actual absolute
index.  It is its interpretation that requires some logic.

One way to think about it is whether the absolute index is in the
Past or the Future -- as it is always either one or the other.

        The window is 2 * MaxEntries wide

 1                                        2 * MaxEntries

 |--------------------------------------------|

If the current maximum absolute index has the value MaxEntries, all
values to its left are in the Past, while all entries to the right
are in the Future:

    <-- Past ---------\ /---- Future --->
 |----------------- CurMax -------------------|

If CurMax is larger than or equal to than MaxEntries, the Past region is
contiguous.  If CurMax is smaller than or equal to MaxEntries, the Future
region is contiguous.

The code is

    bool
    isHeaderBlocked (unsigned LargestRef)
    {
        if (CurMax <= MaxEntries)
            return LargestRef > CurMax
                                && LargestRef <= CurMax + MaxEntries;
        else
            return !(LargestRef <= CurMax
                                && LargestRef > CurMax - MaxEntries + 1);
    }

  - Dmitri.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 6 Aug 2018 00:46:27 -0400

Bug fix:

      bool
      isHeaderBlocked (unsigned LargestRef)
      {
          if (CurMax <= MaxEntries)
              return LargestRef > CurMax
                                  && LargestRef <= CurMax + MaxEntries;
          else
              return !(LargestRef <= CurMax
-                                 && LargestRef > CurMax - MaxEntries + 1);
+                                 && LargestRef >= CurMax - MaxEntries + 1);
      }

---

From: Martin Thomson <[email-masked]>
Date: Mon, 6 Aug 2018 16:52:34 +1000

>       isHeaderBlocked (unsigned LargestRef)

Thanks for sharing code.  Note that I'm not just interested in whether
I'm blocked, but for how many table updates I should block for, but I
can use this function (repeatedly if necessary) to make that
determination, I guess.

It took me ages to understand this code.  Are you expecting all the
arithmetic for CurMax to be modulo MaxEntries*2 ?  Because if that is
the case, then this makes sense.  Without that stipulation, I really
struggled.

We should examine the assertion here then.  That is, you make two
claims: one true, and one maybe-true:

1. You can't receive a header block with a largest reference that is
more than MaxEntries old from the current state.  This holds trivially
because that would mean that the entire header table was evicted.  We
don't allow entries to be referenced after eviction and there is no
way to reach this state without evicting the largest reference.

2. You can't receive a header block with a largest reference that is
more than MaxEntries new.  This doesn't hold because we don't cap the
amount that a header block can be blocked by.  Now, it's arguably a
reasonable restriction, because it takes multiple round trips to reach
a state where that header block can be used, but we don't currently
prevent someone from doing something like that.

Now, it's reasonable to assume that you can't have more than
MaxEntries worth of updates in flight, which means that in one round
trip, this will never happen.  But we don't say that you can't
reference dynamic table entries that are far in the future.  For this
to work, we would have to prohibit that.  Maybe we should, because
referencing entries that can't be sent is a footgun, just as
referencing entries that have not yet been sent is a footgun (it can
deadlock flow control if you do that).

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 6 Aug 2018 08:19:48 -0400

> can use this function (repeatedly if necessary) to make that

Well, that's just pseudo-code, you know.  I'd never CamelCase real
code!

> the case, then this makes sense.  Without that stipulation, I really

Yes, all the arithmetic for the absolute index is modulo MaxEntries * 2.

> amount that a header block can be blocked by.

This is true -- my assertion about the future horizon is incorrect.
Somehow I assumed that the mirror argument about the encoder worked,
but it does not.  For example, nothing prevents the encoder from
pumping the table full of speculative updates, maybe even a few times
over, before ever using it.

> Now, it's arguably a

Yes, for the proposed mechanism to work, we'd have to mandate that the
encoder not create new entries past some limit, which is a function of
the known decoder state (based on TSS or Header Acks) and MaxEntries.

Thanks for identifying this flaw.  The change is larger than I was
hoping it would be.  It's still worth it.

  - Dmitri.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 9 Aug 2018 07:32:01 +1000

So this is a really interesting idea, but I did a triage yesterday and
missed it.  Dmitri, would you mind creating an issue for this?
On Mon, Aug 6, 2018 at 10:19 PM Dmitri Tikhonov

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 9 Aug 2018 09:17:23 -0400

> missed it.  Dmitri, would you mind creating an issue for this?

Not at all:

  https://github.com/quicwg/base-drafts/issues/1644

  - Dmitri.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 9 Aug 2018 23:19:00 +1000

>   https://github.com/quicwg/base-drafts/issues/1644

Thanks.