Subject: Updated QCRAM Draft

From: Mike Bishop <[email-masked]>
Date: Wed, 24 Jan 2018 05:53:55 +0000

Buck has posted an updated QCRAM draft at https://tools.ietf.org/html/draft-krasic-quic-qcram-04 -- please read before tomorrow's meeting so we can have a useful discussion.  Thanks!

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 24 Jan 2018 20:11:58 +1100

Buck,

Thank you for the draft.

I like the approach and I think that it is not difficult to implement.

Reading the spec, the question I have is why you need the BLOCKING flag and
two variables (i.e. base index and depends). Can't each HEADERS frame
always hold just one offset (i.e. largest index that the frame refers to)?

Maybe I am missing something.

2018-01-24 16:53 GMT+11:00 Mike Bishop <[email-masked]>:

> Buck has posted an updated QCRAM draft at https://tools.ietf.org/html/
> draft-krasic-quic-qcram-04 -- please read before tomorrow’s meeting so we
> can have a useful discussion.  Thanks!
>

-- 
Kazuho Oku

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 24 Jan 2018 23:10:14 +1100

The draft outlines what I think the room converged on, and it seems fairly
straightforward -- thanks for the quick turnaround!

Kazuho: I could be wrong, so Buck or Mike should correct me if so, but I
believe the "Base Index" is basically what I think of as the "generation
ID" of the table. It reflects the number of table operations that have
happened... this is important when you have evictions, since just a
reference to the largest index is ambiguous if there have been evictions.

I don't understand however how the largest index is "Base Index - Depends".
I would've thought the largest index would simply be "Depends". What am I
missing?

On Wed, Jan 24, 2018 at 8:11 PM, Kazuho Oku <[email-masked]> wrote:

> Reading the spec, the question I have is why you need the BLOCKING flag
> and two variables (i.e. base index and depends). Can't each HEADERS frame
>> Buck has posted an updated QCRAM draft at https://tools.ietf.org/html/dr
>> aft-krasic-quic-qcram-04 -- please read before tomorrow’s meeting so we

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 25 Jan 2018 02:27:41 +1100

2018-01-24 23:10 GMT+11:00 Jana Iyengar <[email-masked]>:
>
> The draft outlines what I think the room converged on, and it seems fairly straightforward -- thanks for the quick turnaround!
>
> Kazuho: I could be wrong, so Buck or Mike should correct me if so, but I believe the "Base Index" is basically what I think of as the "generation ID" of the table. It reflects the number of table operations that have happened... this is important when you have evictions, since just a reference to the largest index is ambiguous if there have been evictions.

Jana, thank you for the response.

Please correct me if I am wrong, but the below is my understanding.

Modifications to the HPACK state only happens on the Control Stream.
So we do not need to rely on the index to determine how the state
needs to be changed.

For HEADERS frames sent over non-control streams, the only information
that the decoder needs is the absolute indices of the header table,
which can be encoded as largest_index (or whatever you call) plus the
deltas.

>
>
> I don't understand however how the largest index is "Base Index - Depends". I would've thought the largest index would simply be "Depends". What am I missing?
>
>> Reading the spec, the question I have is why you need the BLOCKING flag and two variables (i.e. base index and depends). Can't each HEADERS frame always hold just one offset (i.e. largest index that the frame refers to)?
>>
>>> Buck has posted an updated QCRAM draft at https://tools.ietf.org/html/draft-krasic-quic-qcram-04 -- please read before tomorrow’s meeting so we can have a useful discussion.  Thanks!
>>
>>
>>
>>
>> --
>> Kazuho Oku
>
>

-- 
Kazuho Oku

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Wed, 24 Jan 2018 08:44:27 -0800

On Wed, Jan 24, 2018 at 7:27 AM, Kazuho Oku <[email-masked]> wrote:

> > The draft outlines what I think the room converged on, and it seems
> fairly straightforward -- thanks for the quick turnaround!
> >

Great point.  The prefix is not needed for the modifications to HPACK
state, i.e. for the blocks delivered on the Control Stream.

> > I don't understand however how the largest index is "Base Index -
> Depends". I would've thought the largest index would simply be "Depends".
> What am I missing?
>

Alan F.  also made a similar point.

Base index is for interpreting indexed representations correctly regardless
of re-ordering.  It is basically the total number of insertions that
happened before the current block has processed.

Depends is for ensuring that the decoder blocks if necessary to wait for
table updates the current block depends on.

The 'Base Index - Depends' is poorly written and needs an example, sorry
about that.   The point I was trying (badly) to make was that depends is
encoded relative to Base Index so that it's size stays bounded, it's just
an optimization to save bytes for the case of very long lived connections.
Note that Base Index does not have such bound right now.  Maybe a change to
specify wrap-around  might be a reasonable way to also bound Base Index.

Alternatively, and maybe this is what you just said (?), the two could be
combined into one number.   I think that is tricky because one does not
naturally know "depends" yet while emitting indexed entries.    It could be
in practice that either the depends flag is false, or it is true and the
Depends value is the same as Base Index.   This was definitely not true
with QCRAM-03, but it might well be with QCRAM-04.    That's what I hope to
sort out ASAP with updates to the simulator. 🤔

-- 
Charles 'Buck' Krasic | Software Engineer | [email-masked] | +1 (408)
412-1141

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 24 Jan 2018 11:49:51 -0500

On Wed, Jan 24, 2018 at 05:53:55AM +0000, Mike Bishop wrote:
> Buck has posted an updated QCRAM draft at
> https://tools.ietf.org/html/draft-krasic-quic-qcram-04 -- please read
> before tomorrow's meeting so we can have a useful discussion.  Thanks!

Single Control Stream Prevents QCRAM-04 from Solving HoLB
=========================================================

    Abstract:  A consice overview of the HoLB problem is presented.
    The QCRAM-04 approach to solving this problem is analyzed.  A
    problematic design choice is identified and its impact assessed.
    An alternative design is suggested.

Problem Statement
-----------------

QCRAM-04 is a version of QCRAM in which all table updates occur on a
dedicated control stream.  This restriction has a negative effect on
the protocol's ability to minimize HoLB.  There exists a class of
applications for which QCRAM-04 does not solve HoLB, solely as a
result of introducing ordering to otherwise independent operations.

The Original HoLB Problem
-------------------------

The original HoLB problem that we are trying to solve is as follows.
HPACK/GQUIC delivers all HTTP message headers as header blocks on a
separate control stream.  HTTP message payload (bodies) are sent on
different streams, one message per stream.  The application (HTTP)
cannot process message bodies without the headers; it must have the
headers before it starts reading from the message stream.

    +----------------+----------------+
    | Header Block A | Header Block B |
    +----------------+----------------+

    +----------------+
    | Message A Body |
    +----------------+

    +--------------------------------+
    |        Message B Body          |
    +--------------------------------+

  Figure 1: HPACK/GQUIC: Control stream carrying two header blocks and
            two streams carrying message bodies.

If a packet carrying part of the Header Block A is lost, Header Block B
and, therefore, the whole of Message B cannot be processed, even if all
of the packets carrying Header Block B and Message B Body have arrived.
Message B is stalled until the lost packet is retransmitted successfully
and the control stream is unblocked.  This is the HoLB problem.

Proposed Solutions
------------------

The solutions to the HoLB problem fall into two categories:

    1. Avoidance:  Disallow vulnerable references.  This approach is
       robust and simple to implement, but carries a compression
       performance penalty.

    2. Minimization:  Allow vulnerable references, but minimize their
       impact.  This approach looks to achieve maximum compression at
       the cost of protocol and implementation complexity.

QCRAM and QPACK belong to the second category.  Until QCRAM-04, both
carried table updates on multiple streams, for the following reason:

Coping with False Dependencies
------------------------------

(Refer to Figure 1 again).  If Header Block B uses a dynamic entry
inserted by Header Block A, then B cannot be processed until A has
been processed; this is a true dependency.  If, however, Header Block B
does not depend on any insertions performed by Header Block A, placing
them in order on a single control stream introduces a false dependency.
The design choice of placing dynamic table updates on separate streams
is driven by desire to eliminate false dependencies and, thereby, to
minimize HoLB.

How QCRAM-04 is Different From HPACK/GQUIC
------------------------------------------

QCRAM-04 moves parts of header blocks from the control stream to the
individual message streams.  This means that if a particular message's
headers do not cause an insertion into the dynamic table, this message
does not have to write to the control stream.  This eliminates some
false dependencies and is an improvement over HPACK/GQUIC.

    +---------------------------+
    | Updates Associated with A |
    +---------------------------+

    +----------------+----------------+
    | Header Block A | Message A Body |
    +----------------+----------------+

    +----------------+--------------------------------+
    | Header Block B |          Message B Body        |
    +----------------+--------------------------------+

  Figure 2: QCRAM-04: control stream carrying table modifications upon
            which Header Block A depends and message streams for
            messages A and B.  Message B can be processed if parts of
            message A are lost.

False Dependencies Remain
-------------------------

If messages A and B cause independent updates to the dynamic table,
they are written to the control stream.  This fact makes message B
depend on message A: a false dependency.

    +-----------------------+-----------------------+
    | Updates Assoc. with A | Updates Assoc. with B |
    +-----------------------+-----------------------+

    +----------------+----------------+
    | Header Block A | Message A Body |
    +----------------+----------------+

    +----------------+--------------------------------+
    | Header Block B |          Message B Body        |
    +----------------+--------------------------------+

  Figure 3: QCRAM-04: control stream carrying independent table
            modifications which, nevertheless, make Message B
            depend on Message A: a false dependency.

Note that Figure 3 and Figure 1 are quite similar.

Three Application Classes
-------------------------

To analyze how QCRAM-04 improves over HPACK/GQUIC, we should consider
three application classes (basically, usage patterns):

    I.   Dependent header blocks;
    II.  Independent header blocks without table modification; and
    III. Independent header blocks with table modification.

I. Dependent Header Blocks
--------------------------

If Header Block B uses table entries added by Header Block A, there is
not much one can do about that: A must be processed before B, no matter
how the header blocks are transmitted.  QCRAM-04 and HPACK/GQUIC do not
introduce HoLB: this is the property of the application itself.

II. Independent header blocks without table modification
--------------------------------------------------------

Header blocks that do not modify the dynamic table do not require the
use of the control stream in QCRAM-04 (see Figure 2).  This is a clear
improvement over HPACK/GQUIC, which introduces a false dependency and
risks HoLB by delivering all header blocks over the same stream.

III. Independent header blocks with table modification
------------------------------------------------------

If Header Blocks A and B insert different entries into the dynamic
table and Header Block B does not use any entries inserted by A, both
QCRAM-04 and HPACK/GQUIC introduce a false dependency by delivering
unrelated table updates associated with A and B on the same stream
(see Figure 3).

Quantitatively, QCRAM-04 is a little better than HPACK/GQUIC here.
This is because it sends less data on the control stream, which means
that the chances of packet loss are smaller.  However, the improvement
is small: the control stream carries table updates, which is most of
the header block data.

Summary
-------

QCRAM-04 achieves HoLB minimization in one class of applications, but
not in the other, where it introduces a false dependency.  This means
that the answer to the question "Will my application suffer from
protocol-induced HoLB were I to switch to HTTP/QUIC?" is "It depends."
That is not good enough.  In the HoLB minimization approach, independent
dynamic table updates must be sent on different streams.

  - Dmitri.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 25 Jan 2018 04:06:09 +1100

Hi,

Thank you for the response.

2018-01-25 3:44 GMT+11:00 Charles 'Buck' Krasic <[email-masked]>:

>> > Kazuho: I could be wrong, so Buck or Mike should correct me if so, but
>> I believe the "Base Index" is basically what I think of as the "generation
> Base index is for interpreting indexed representations correctly
> regardless of re-ordering.  It is basically the total number of insertions
> that happened before the current block has processed.
>
> combined into one number.
>

Yes. That is what I have been thinking of.

> I think that is tricky because one does not naturally know "depends" yet
> while emitting indexed entries.
>

I think that the encoder needs to do a two-pass operation regardless of if
we encode two numbers (i.e. base_index, depends) or just one. This is
because since base_index and depends cannot be determined until the encoder
iterate through all the headers.

So to me it seems that it is not tricker for an encoder to use an unified
value; in the first pass the encoder determines the absolute index, and
then in the second pass emit the unified "base index" plus the deltas.

>     It could be in practice that either the depends flag is false, or it
> is true and the Depends value is the same as Base Index.   This was
> definitely not true with QCRAM-03, but it might well be with QCRAM-04.
> That's what I hope to sort out ASAP with updates to the simulator. 🤔
>

I understand that it's hard to update all the related code as we adjust the
approach. Thank you for your efforts!

>> >> Reading the spec, the question I have is why you need the BLOCKING
>> flag and two variables (i.e. base index and depends). Can't each HEADERS
>> frame always hold just one offset (i.e. largest index that the frame refers
>> to)?
>> >>
>> before tomorrow’s meeting so we can have a useful discussion.  Thanks!
>> >>
>> >>
>> >>
>> >>
>> >> --
>> >> Kazuho Oku
>> >
>> >
>>
>>
>>
>> --
>> Kazuho Oku
>>
>
>
>
> --
> 412-1141 <(408)%20412-1141>
>
>

-- 
Kazuho Oku

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Thu, 25 Jan 2018 13:03:28 -0800

I've gotten the simulator working with QCRAM -04 changes, specifically the
part that moves all updates to the control stream.

I ran some tests to compare hpack, qcram-03 and qcram-04.

                   HolBs     (%)
hpack         850         100
qcram-03   27            3.2
qcram-04   46            5.4

HolBs here are requests that experienced Hol blocking.

I think the main reason -04 doesn't degrade to HPACK is that there are
quite a lot of requests that do no updates.   Note that the indexing
strategy doesn't index :path.

Additional details:

The har was a facebook of my own.  I got it from chrome, using developer
tools For reference it has 299 requests, and 167955 uncompressed header
bytes.

The table maxed out at 38 entries (same for all runs).

The HolBs above are totals over 10 runs of each scheme.  I ran multiple
times to smooth variation due to the randomization of the simulator.

I set the simulator loss rate of 0.35, which may be insanely high, but it
stresses HoL Blocking.

On Wed, Jan 24, 2018 at 9:06 AM, Kazuho Oku <[email-masked]> wrote:

> I understand that it's hard to update all the related code as we adjust
> the approach. Thank you for your efforts!
>
>
>>
>>
>>
>>
>>
>>> >
>> Charles 'Buck' Krasic | Software Engineer | [email-masked] | +1
>> (408) 412-1141 <(408)%20412-1141>
>>
>>
>
>
> --
> Kazuho Oku
>

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 25 Jan 2018 17:10:45 -0500

> HolBs here are requests that experienced Hol blocking.

---8<----

> tools For reference it has 299 requests, and 167955 uncompressed header

I am sure I misunderstand something:

- How can the number of requests that experienced HoL
  blocking (850) be larger than the total number of
  requests (299)?

- What does the percentage column (100, 3.2, 5.4) represent?

  - Dmitri.

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Thu, 25 Jan 2018 14:53:21 -0800

On Thu, Jan 25, 2018 at 2:10 PM, Dmitri Tikhonov <
[email-masked]> wrote:

> It is a total over ten runs.

> - What does the percentage column (100, 3.2, 5.4) represent?

Just normalizing qcram-* against HPACK.   E.g.  for qcram-03, 27/850 =
3.2%.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 26 Jan 2018 19:56:04 +0000

Counting key-values vs counting header blocks perhaps?
-=R

On 1/25/18, 2:11 PM, "QUIC on behalf of Dmitri Tikhonov" <[email-masked] on behalf of [email-masked]> wrote:

    ---8<----

    

      - Dmitri.

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Fri, 26 Jan 2018 12:32:34 -0800

> Counting key-values vs counting header blocks perhaps?

I think you missed my reply, but just in case:

10 runs * 299 requests in the har = 2990 total requests.

>
> On 1/25/18, 2:11 PM, "QUIC on behalf of Dmitri Tikhonov" <
> [email-masked] on behalf of [email-masked]> wrote:
>

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Mon, 29 Jan 2018 10:57:40 -0800

Just an FYI, with mbishop@'s help and after sorting some issues with my qcram
github repo <https://github.com/krasic/draft-krasic-quic-hpack>, the pages
now have working editor's copy and diff links.

In recent days, I've made some simplifications and changes in response to
afrind@'s and kazuhooku@'s comments.

-- Buck