Re: Proposal: drop QPACK encoder stream framing

[Kazuho Oku <[e-mail]>]

2018-06-08 23:49 GMT+03:00 Alan Frindell <[e-mail]>:
>     1a. buffer the entire frame, and then iterate though the instructions,
>     while checking for every instruction that it does not go beyond the
>     end of the frame
>     1b. iterate though the instructions as they arrive, while checking
>     that the entire instruction is available and that the instruction does
>     not go beyond the end of the frame
>
>     If we remove framing, the decoder can be implemented as:
>
>     2. iterate through the instructions as they arrive, while checking
>     that the entire instruction is available
>
> Consider the most complicated instruction, which is Inserting a pure literal (all fields have variable length)
>
> | Name Length | Name | Value Length | Value |

Thank you for bringing up the example. I think this is a very good
example, that would help us determine the complexity.

> When you know the length of the instruction block in advance, you know that an incomplete instruction is a decoding error which you can check as you decode, and fail immediately on underflow.  Here, you either need to do a trial decode of the variable lengths to see if you have enough bytes, or check while decoding, and decide whether you want to save the state for later or discard it and reparse from the beginning of the instruction.  I'm not even sure reparsing is workable since it might open you up to doing N^2 work -- at least you need to be careful how you implement it.  It's worth calling out that discovering the length of a QPACK varint is more complicated than a QUIC varint.

Because I think reparsing is the best strategy here, let me argue that
the worst case is not O(N^2).

Of course, in theory it is O(N^2), because there is no upper bound for
the integer representation. But the reality is that implementations
are required to have an upper bound. I'd assume that they would
typically only permit values that fit in a 32-bit (u)int (16-bit is
another option for some).

Note that such safe-guard is required even if we have framing.

RFC7541; section 5.1 specifically requires HPACK stacks to implement
such safe-guard:

   This integer representation allows for values of indefinite size.  It
   is also possible for an encoder to send a large number of zero
   values, which can waste octets and could be used to overflow integer
   values.  Integer encodings that exceed implementation limits -- in
   value or octet length -- MUST be treated as decoding errors.
   Different limits can be set for each of the different uses of
   integers, based on implementation constraints.

Considering these facts, I would argue that the worst case cost of
parsing a Literal header field will remain O(N), and that complexity
of the code will remain at least comparable to when having framing
(considering the fact that framing is a complexity by itself).

> It’s not impossible to solve of course.  “It’s just software” as Dmitri likes to say.  It’s just one piece of complexity I was hoping to avoid.

Yeah. It's a trade-off between having more layers to split the issues
vs. reducing the numbers of layers to minimize overall complexity.

>
> -Alan
>



-- 
Kazuho Oku