Subject: Proposal: drop QPACK encoder stream framing

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 7 Jun 2018 11:11:13 -0400

Abstract
--------

The encoder block specified in Section 3.3 of draft-ietf-quic-qpack-00
is unnecessary.  For reasons of efficiency, I propose that the framing
be removed: let the encoder instructions be written and interpreted as
a stream instead.

Background
----------

I brought this up during the first day (June 6) of the Kista Interim.
Alan explained that there are two reasons for framing the instructions
in this way on the encoder stream:

    1. Historically, some (or most) HPACK decoders have struggled with
       input that breaks in the middle of an instruction, as they do
       not maintain state.

    2. The blocks can be used as a clue to send Table State Synchronize
       instructions on the decoder stream (Section 3.4.1).

The downside to having length-prefixed blocks is that it makes it
difficult to optimize encoding by writing to the outgoing packets
directly.  One has to buffer the block, write the block length first,
and then copy the block.

Additionally, there is a potential for a deadlock (issue #1420).  Recall
that QPACK owes its current form to the fact that the WG decided to
prevent deadlocks at the compression protocol level, and not via advisory
notes to the implementers.

Reasons Behind the Block
------------------------

First, let's look at the historical HPACK chokers.

The HPACK decoder only processes HEADER blocks.  There is only one stream
and thus only one HEADER block can be processed at a time.

The QPACK decoder has to process two inputs: a) the encoder stream
and b) HEADER blocks.  There is only one encoder stream.  This stream
modifies the decoder state: the dynamic table.  The HEADER blocks do not
modify the state.

The HEADER blocks already come with a prefix length (HQ framing), and so
QPACK implementations can choose to wait until the whole HEADER block is
available.  It is processing of the encoder stream that is under
consideration.

With regards to the Table Synch signaling, the draft states that

 "                                                         A decoder MAY
 " coalesce multiple synchronization updates into a single update.

This effectively means that the encoder already should not expect to get
a one-to-one mapping between its Encoder Blocks and Table Synchs.

Working with the Encoder Stream
-------------------------------

The dynamic table instruction stream can be thought of as its own state.
Already, the QPACK decoder must be able to pause reading from streams when
a blocked HEADERS block arrives.  Similar techniques can be used to resume
reading from the encoder stream.  It should not be difficult to resume
decoding a single instruction!  While breaking with the HPACK precedent
(the hold-my-hand-I-need-buffer-size chokers), it keeps in line with the
Seattle hum that the new compression mechanism is free from its HPACK
shackles.

Conclusion
----------

Prefixing arbitrary sets of encoder instructions with a length denies
zero-copy optimization opportunities.  At the cost of some slight
complexity increase at the decoder, this framing mechanism can be
dropped.  The proposed change is limited to just this -- technically
superfluous -- piece.

  - Dmitri.

P.S.  An added bonus is some saved framing bytes on the encoder stream.
      I believe the "compression performance above everything else" is
      also the Working Group's consensus (Melbourne).

---

From: Spencer Dawkins at IETF <[email-masked]>
Date: Thu, 7 Jun 2018 11:55:23 -0500

Hi, Dmitri,

This is me as an individual, asking a question, and NOT making an informed
observation or suggestion ... but I was curious.

> be removed: let the encoder instructions be written and interpreted as

[snip]

I note that TSVWG  currently has two FECFRAME docs in WGLC now:

(1) https://datatracker.ietf.org/doc/draft-ietf-tsvwg-fecframe-ext/

(2) https://datatracker.ietf.org/doc/draft-ietf-tsvwg-rlc-fec-scheme/

The intent for these documents is to add support for sliding window FEC
codes to the RFC 6363 FEC Framework, which was limited to block FEC codes.

I don't know whether there is any relationship between your proposal
(moving from framing to a stream for compression) and the work currently in
TSVWG. I have some guesses, but not well-informed guesses, so thought I
should ask.

Thanks,

Spencer

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 7 Jun 2018 15:02:27 -0400

Hi Spencer,

[snip]

> codes to the RFC 6363 FEC Framework, which was limited to block FEC codes.

I have to admit, I have never seen RFC 6363 or the FECFRAME drafts until
today.  With that said, I believe I understand on high level what they
are about after reading the abstracts.

> TSVWG. I have some guesses, but not well-informed guesses, so thought I

There is no relationship to the QPACK framing in question.  The QPACK
framing mechanism used to write encoder instructions to the encoder
QUIC stream is there solely as an aid to the decoder -- evidently
with the aim of making the QPACK decoder easier to implement (or to
port existing HPACK decoders).

Google experimented with FEC in gQUIC but the bandwidth overhead
proved to outweigh any advantages offered by ability to reconstruct
lost packets and the effort was abandoned, IMMSMC, in 2015.

Using FEC in IETF QUIC is something that is interesting to think about.
For example, one could envision adding FEC to a critical stream, such
as the QPACK encoder stream above, to cope with packet loss.  The
challenges posed by such approach would be non-trivial and likely
require changes to the transport layer.

  - Dmitri.

---

From: Spencer Dawkins at IETF <[email-masked]>
Date: Thu, 7 Jun 2018 15:08:08 -0500

Hi, Dmitri,

> require changes to the transport layer.

Thanks for this. It's helpful.

Spencer

  - Dmitri.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 8 Jun 2018 12:12:38 +0200

I think that this is a reasonable request and I'd support this.  It
saves an encoder from having to buffer and it even saves a few octets.
The complexity increase (the increased need to delay acknowledgments)
is manageable and even encourages good practice - the current design
encourages a little bit of laziness because you can acknowledge at the
end of each block and have a reasonable expectation of it being
approximately correct... most of the time.
On Thu, Jun 7, 2018 at 5:11 PM Dmitri Tikhonov

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 8 Jun 2018 13:19:35 +0200

> approximately correct... most of the time.

+1

Previously I had thought that having prefix has the possibility of
simplifying the encoder. But I think I was wrong.

If we have framing, we need to do either of the following:

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

As you can see, removing the framing simplifies the decoder design.
Because it reduces one layer of variable-length encoding.

-- 
Kazuho Oku

---

From: Ian Swett <[email-masked]>
Date: Fri, 8 Jun 2018 14:40:59 -0400

I'm not as much a QPACK expert as others on this thread, but I do agree
that it would be simpler without the length in this case, as well as saving
a few bytes.

---

From: Alan Frindell <[email-masked]>
Date: Fri, 8 Jun 2018 20:49:37 +0000

Consider the most complicated instruction, which is Inserting a pure literal (all fields have variable length)

| Name Length | Name | Value Length | Value |

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.
    
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.

-Alan

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 9 Jun 2018 00:44:24 +0300

> | 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…

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.

-- 
Kazuho Oku

---

From: Alan Frindell <[email-masked]>
Date: Fri, 8 Jun 2018 23:26:55 +0000

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.

-Alan

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sat, 9 Jun 2018 11:55:31 -0400

On Fri, Jun 08, 2018 at 08:49:37PM +0000, Alan Frindell wrote:
> Consider the most complicated instruction, which is Inserting a pure
> literal (all fields have variable length)
> 
> 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.

The example above contradicts the argument that follows.  It is evident
that we have a length followed by an instruction block (the Huffman-encoded
string).  A QPACK implementation is still free to buffer the instruction
blocks, in which case all the perceived advantages of framing you present
below are applicable.

Parsing of the length is, of course, more complicated than requiring a
known number of bytes to be available to read in a fixed-length integer.
Nevertheless, as Kazuho points out, there are practical limits whereby
most implementations will abide.

> 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.

An efficient implementation will not just blindly reparse over and over
as each byte of the stream data becomes available.  With a buffering
implementation, the need to reparse disappears if one is willing to
allocate the buffer large enough.  This is exactly the approach you
advocate to use with the current instruction block framing.

The proposal to drop framing is to allow an optimization (eliminate a
copy) at the encoder, not the decoder.  The decoder is still free to
use the same programming techniques as before.

> 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

And I hope I have demonstrated that the complexity increase is
minimal.  Soon, I will demonstrate the same using C code.

  - Dmitri.

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 10 Jun 2018 01:56:54 +0300

> 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…

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.

-- 
Kazuho Oku

---

From: Mike Bishop <[email-masked]>
Date: Sun, 10 Jun 2018 23:15:59 +0000

And they probably should, since they can't sensibly do anything without a full instruction.  So an implementation would need to do the following steps:

  *   Check the first byte; at this point, you either know the string’s exact length, or you know it’s longer than 32 bytes
     *   If longer, wait until you’ve gotten at least 32 more bytes, and you’re guaranteed to have the remainder of the number; find the actual length
     *   Wait until you have the actual length plus one byte
  *   Use the length of the encoded string to locate the first byte of the value length; you either find the full length, or you know it’s at least 128 bytes long
     *   If longer, wait until you’ve gotten at least 128 more bytes; you’re guaranteed to have the actual number in there
     *   Wait until you have the actual length (remainder of the instruction)
  *   Decode the instruction

So you’re potentially waiting for more bytes up to four times per instruction (though the odds that a non-malicious sender would hit all four are low), and a naïve implementation might well re-parse the instruction from the beginning after each wait completes.  Implicit in this is the assumption that a 32 byte long integer will always be unacceptably long, and if after the wait you can’t move to the next field successfully, you’ll fail the instruction.

An implementation can always determine how many bytes it needs to wait for to make progress, without accidentally waiting past the end of the instruction and creating a deadlock if that’s a tail.  I think this example has convinced me that the length prefix is unnecessary.  (It does make me wonder whether it would have made more sense to put both lengths at the beginning of the instruction, followed by the values.)

-----Original Message-----
From: QUIC <[email-masked]> On Behalf Of Kazuho Oku
Sent: Saturday, June 9, 2018 3:57 PM
To: Alan Frindell <[email-masked]>
Cc: QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>
Subject: Re: Proposal: drop QPACK encoder stream framing

> 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…

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.

--

Kazuho Oku

---

From: Alan Frindell <[email-masked]>
Date: Mon, 11 Jun 2018 15:22:18 +0000

The fact that you now need an algorithm that tells you how to correctly/safely deserialize a single instruction is pretty much the point I was making.  This is more complex than just having a byte on the wire tell you how many bytes are required.  But I feel there’s clear consensus here to discard the length prefix.

-Alan

From: Mike Bishop <[email-masked]>
Date: Sunday, June 10, 2018 at 4:16 PM
To: Kazuho Oku <[email-masked]>, Alan Frindell <[email-masked]>
Cc: QUIC WG <[email-masked]>, Martin Thomson <[email-masked]>
Subject: RE: Proposal: drop QPACK encoder stream framing

-----Original Message-----
From: QUIC <[email-masked]> On Behalf Of Kazuho Oku
Sent: Saturday, June 9, 2018 3:57 PM
To: Alan Frindell <[email-masked]>
Cc: QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>
Subject: Re: Proposal: drop QPACK encoder stream framing

--

Kazuho Oku

---

From: Roberto Peon <[email-masked]>
Date: Tue, 12 Jun 2018 23:33:46 +0000

To be fair, Google's FEC implementation was.... naïve at best.
I wouldn't say that it proved FEC unuseful, but rather that it proved that FEC over temporally-proximate packets wasn't that useful.
-=R

On 6/7/18, 12:03 PM, "QUIC on behalf of Dmitri Tikhonov" <[email-masked] on behalf of [email-masked]> wrote:

    Hi Spencer,

    [snip]
    
    > (1) https://urldefense.proofpoint.com/v2/url?u=https-3A__datatracker.ietf.org_doc_draft-2Dietf-2Dtsvwg-2Dfecframe-2Dext_&d=DwIBAg&c=5VD0RTtNlTh3ycd41b3MUw&r=C0sUo-LFNBaYfyoaCsf6TA&m=Kc5MaxpPcqAxoBem1RsFu2d5jUxRsvSOFAU1tUoujBk&s=J_0CNYflHhBvUwAf9oBP40OHkGDkZ8rNBswKhx7fyOA&e=
    > 
    > (2) https://urldefense.proofpoint.com/v2/url?u=https-3A__datatracker.ietf.org_doc_draft-2Dietf-2Dtsvwg-2Drlc-2Dfec-2Dscheme_&d=DwIBAg&c=5VD0RTtNlTh3ycd41b3MUw&r=C0sUo-LFNBaYfyoaCsf6TA&m=Kc5MaxpPcqAxoBem1RsFu2d5jUxRsvSOFAU1tUoujBk&s=1dWjaPRse5ArHTUgAQvsEMJEZtU15tsDEV5w6X_DGoM&e=
    > 

    

    
      - Dmitri.

---

From: Roberto Peon <[email-masked]>
Date: Tue, 12 Jun 2018 23:36:04 +0000

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" <[email-masked] on behalf of [email-masked]> wrote:

    

    
    -- 
    Kazuho Oku

---

From: Ian Swett <[email-masked]>
Date: Tue, 12 Jun 2018 21:29:32 -0400

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