Developer’s Corner: QCRAM-04 Does Not Solve HoLB

At the Melbourne Interim meeting, the IETF QUIC Working Group decided to use a version of the QCRAM header compression protocol with the following modification: use a dedicated control stream to carry all dynamic table updates. The result is QCRAM-04. This modification is one way to prevent deadlock hazard (the subject of last week’s blog post) present in the previous QCRAM proposals. While it certainly addresses the deadlock, the single control stream introduces ordering to otherwise independent operations, making it unable to minimize HoLB for a class of applications.

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.

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.

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.

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):

1. Dependent header blocks;
2. Independent header blocks without table modification; and
3. 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.

—
Text by: Dmitri Tikhonov
Graphics by: Mark Zou