Re: Proposal: drop QPACK encoder stream framing

[Ian Swett <[e-mail]>]

As a person who spent a fair amount of time both trying to make Google's
FEC scheme work and subsequently analyzing why it didn't, a core issue was
that losses were much more correlated than expected.  The only FEC scheme
tested had zero value if more than two packets were lost within an FEC
block.

Additionally, it was not wired up to the general purpose recovery code, so
it failed to prevent spurious retransmits.

That being said, if you have a few RTTs to play with, QUIC's fast
retransmission works very well.  If you're running a realtime application
like WebRTC, the bandwidth overhead of FEC is well-justified.

On Tue, Jun 12, 2018 at 7:36 PM Roberto Peon <[e-mail]> wrote:

> Were I to put lengths somewhere, it'd be on another stream, which
> consisted solely of fixed/constant-sized metadata about the headers.
> -=R
>
> On 6/9/18, 3:57 PM, "QUIC on behalf of Kazuho Oku" <[e-mail]
> on behalf of [e-mail]> wrote:
>
>     2018-06-09 8:26 GMT+09:00 Alan Frindell <[e-mail]>:
>     >     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).
>     >
>     > The O(N^2) work I was thinking of was something like this:
>     >
>     > The encoder sends a very long Huffman encoded header name followed
> by a long value, but they send the value one byte at a time.  If the
> decoder naively reparses the entire Insert instruction every time a byte
> arrives, it will end up Huffman decoding the header name on every new byte
> of the value.  The name can be skipped over to re-parse the value length,
> and verify if the full value is present.  However, even skipping over it
> may be a linear operation in a zero-copy implementation that maintains a
> linked list of data buffers.
>
>     Thank you for the clarification. That sounds like an interesting
>     attack vector that we need to be aware of.
>
>     OTOH, I am not sure if we need to consider the possibility of
>     streaming Huffman decoding in this discussion, considering the fact
>     that the compressed strings remain length-prefixed.
>
>     Even if we remove the framing of the QCACK instructions,
>     implementations will continue to have the freedom to buffer a complete
>     Huffman-encoded string (the length of the string being identified by
>     the length octets.
>
>     > -Alan
>     >
>     >
>
>
>
>     --
>     Kazuho Oku
>
>
>
>