Re: Updated QCRAM Draft

[Dmitri Tikhonov <[e-mail]>]

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.