HoL Blocking and Priority Inversion in QUIC

<aside> 💡 Series:

</aside>

Background

Producing a native header compression mechanism for QUIC is one of the goals of the IETF QUIC Working Group. The approach used in the Google QUIC (gQUIC) suffers from head-of-line blocking (HoLB) and is thus suboptimal. I had been interested in header compression for some time and, in November of 2017, I added my own proposal (QMIN) to the other two proposals already under consideration. The Working Group had empaneled the Compression Design Team and tasked it with coming up with a single proposal. Our team has six members:

Alan Frindell, the author of proxygen;
Charles “Buck” Krasic, the author of the QCRAM compression proposal;
Dmitri Tikhonov, the author of the QMIN compression proposal.
Martin Thomson, the co-editor of the QUIC Internet Draft;
Mike Bishop, the author of the QPACK compression proposal; and
Roberto Peon, the co-author of HPACK (RFC 7541).

There are many design decisions that go into producing a compression mechanism. The resulting proposal (Internet Draft) will hopefully become a standard (RFC) one day. The rationale behind many aspects of a standard usually does not get included into RFCs: this is not what the RFCs are for. In this article — which may become first in a series of several — I will describe an interesting problem that could impact the choices the Compression Design Team makes.

Introduction

QUIC streams have priorities which the application layer can set.

POST /api/data HTTP/3
Host: example.com
Priority: u=3,i

HTTP/2 and, consequently, HTTP/QUIC use priorities to improve UX. Usually, priorities are assigned by content type: HTML has higher priority than CSS, which in turn has higher priority than images. In general, an application using the protocol may assign any priorities to suit its needs.

Problem Statement

In gQUIC, the header blocks are delivered on a separate, high-priority (higher than all other priorities on the connection save the HANDSHAKE stream), unbounded HEADERS stream. The HTTP payload-bearing streams’ priorities are used to select which HTTP message to process. Lost or late packets on the HEADERS stream may cause other streams to wait. (This is the head-of-line blocking problem that the Design Team is trying to solve.) The HEADERS stream itself does not depend on other streams and it is always processed first.

In the current IETF HTTP/QUIC draft, on the other hand, the header blocks are part of the request/response stream itself. In the case where the header compression protocol mandates that the decoder be able to wait on unresolved entries (this is the decoder HoL blocking), the compression protocol and the QUIC protocol can actively hinder each other in the following manner:

<aside> 📘 优先级反转和 HoLB

优先级高的 stream 处理了一半丢包了，然后会先处理优先级低的 stream，这是优先级反转。

优先级低的 stream 处理完后，优先级高的 stream 的包重传 ok 了，得处理优先级高的 stream，这是 HoLB。

</aside>