Header Compression for HTTP/QUIC
draft-bishop-quic-http-and-qpack-01

Abstract

HTTP/2 [RFC7540] uses HPACK [RFC7541] for header compression. However, HPACK relies on the in-order message-based semantics of the HTTP/2 framing layer in order to function. Messages can only be successfully decoded if processed by the decoder in the same order as generated by the encoder. This draft refines HPACK to loosen the ordering requirements for use over QUIC [I-D.ietf-quic-transport].

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on July 21, 2017.

Copyright Notice

Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Introduction
• 1.1. Terminology
• 2. QPACK
• 2.1. Changes to Static and Dynamic Tables
• 2.1.1. Dynamic Table State Synchronization
• 2.1.2. Changes to Maximum Table Size
• 2.2. Changes to Binary Format
• 2.2.1. Literal Header Field Representation
• 2.2.2. Deletion
• 2.2.3. The QPACK-ACK frame
• 3. Use in HTTP/QUIC
• 4. Performance Considerations
• 5. Security Considerations
• 6. IANA Considerations
• 7. Acknowledgements
• 8. Normative References
• Author's Address

1. Introduction

HPACK has a number of features that were intended to provide performance advantages to HTTP/2, but which don’t live well in an out-of-order environment such as that provided by QUIC.

The largest challenge is the fact that elements are referenced by a very fluid index. Not only is the index implicit when an item is added to the header table, the index will change without notice as other items are added to the header table. Static entries occupy the first 61 values, followed by dynamic entries. A newly-added dynamic entry would cause older dynamic entries to be evicted, and the retained items are then renumbered beginning with 62. This means that, without processing all preceding header sets, no index into the dynamic table can be interpreted, and the index of a given entry cannot be predicted.

Any solution to the above will almost certainly fall afoul of the memory constraints the decompressor imposes. The automatic eviction of entries is done based on the compressor’s declared dynamic table size, which MUST be less than the maximum permitted by the decompressor (and relayed using an HTTP/2 SETTINGS value).

In the following sections, this document proposes a new version of HPACK which makes different trade-offs, enabling out-of-order interpretation and bounded memory consumption with minimal head-of-line blocking. None of the proposed improvements to HPACK (strongly-typed fields, binary compression of common header syntax) are currently included, but certainly could be.

1.1. Terminology

In this document, the key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” are to be interpreted as described in BCP 14, RFC 2119 [RFC2119] and indicate requirement levels for compliant STuPiD implementations.

2. QPACK

2.1. Changes to Static and Dynamic Tables

QPACK uses two tables for associating header fields to indexes. The static table is unchanged from [RFC7541].

The dynamic table is a map from index to header field. Indices are arbitrary numbers greater than the last index of the static table. Each insert instruction will specify the index being modified. While any index MAY be chosen for a new entry, smaller numbers will yield better compression performance.

In order to improve resiliency to reordering, an encoder MAY send multiple insert instructions for the same value to the same index. However, any attempt to insert a different value to an occupied index is a fatal error.

The dynamic table is still constrained to the size specified by the decoder. An attempt to add a header to the dynamic table which causes it to exceed the maximum size MUST be treated as an error by a decoder. To enable encoders to reclaim space, encoders can delete entries in the dynamic table, but can only reuse the index or the space after receiving confirmation of a successful deletion.

Because it is possible for QPACK frames to arrive which reference indices which have not yet been defined, such frames MUST wait until another frame has arrived and defined the index. In order to guard against malicious peers, implementations SHOULD impose a time limit and treat expiration of the timer as a decoding error. However, if the implementation chooses not to abort the connection, the remainder of the header block MUST be decoded and the output discarded.

2.1.1. Dynamic Table State Synchronization

No entries are evicted from the dynamic table. Size management is purely the responsibility of the encoder, which MUST NOT exceed the declared memory size of the decoder.

Both encoder and decoder will maintain a count of references to the indexed entry. This count includes:

• Insertions to the field, both the initial and any redundant indexed literal emissions.
• Literal values which use the indexed entry to provide the header name
• Explicit emissions of the indexed value

The encoder MUST consider memory as committed beginning with the first time the indexed entry is assigned. An encoder MAY repeat the insertion instruction in other frames rather than leveraging the index while it waits for the frame to arrive.

When the encoder wishes to delete an inserted value, it flows through the following set of states:

1. Delete requested. The encoder emits a delete instruction including the terminal value of the reference counter. The encoder MUST NOT reference the entry in any subsequent frame until this state machine has completed and MUST continue to include the entry in its calculation of consumed memory.
2. Delete pending. The decoder receives the delete instruction and compares the encoder’s counter with its own. If the decoder’s counter is less than the encoder’s, it stores the encoder’s counter and waits for other QPACK frames to arrive.
3. Delete acknowledged. The decoder has received all QPACK frames which reference the deleted value, and can safely delete the entry. The decoder SHOULD promptly emit a QPACK-ACK frame, but MAY delay briefly waiting for other pending deletes as well.
4. Delete completed. When the encoder receives a QPACK-ACK frame acknowledging the delete, it no longer counts the size of the deleted entry against the table size and MAY emit insert instructions for the field with a new value.

The decoder can receive a delete instruction for a vacant table entry. A decoder MUST NOT consider this to be an error, but MUST handle the delete as usual even while waiting for the definition to arrive.

2.1.2. Changes to Maximum Table Size

A decoder MAY, at any time, modify its maximum table size by sending a SETTINGS frame containing a different value for SETTINGS_HEADER_TABLE_SIZE. This SETTINGS frame MUST request acknowledgement if the value is being reduced.

An increased value applies immediately upon sending the SETTINGS frame; a reduced value only applies on each stream after receiving an appropriate SETTINGS_ACK. The new value, in either direction, is applicable to the encoder immediately upon sending the SETTINGS_ACK frames.

Upon a reduced maximum value being applied, the dynamic table might be larger than the new maximum. This MUST NOT be considered an error, but any attempt to insert a new value into the dynamic table that takes it above the currently-applicable limit MUST be considered a fatal error. Before making any further insertions to the dynamic table, the encoder MUST delete enough entries to perform the insertion without violating the table maximum.

If an encoder opts to use a smaller maximum table size than the decoder has specified, it does not need to inform the decoder of this as in HPACK. The encoder’s maximum table size can be changed at any time without notice to the decoder, so long as the selected size is less than the decoder’s declared maximum.

2.2. Changes to Binary Format

2.2.1. Literal Header Field Representation

(This section replaces [RFC7541], Section 6.2.1.)

A literal header field with indexing representation results in inserting a header field to the decoded header list and inserting it as a new entry into the dynamic table.

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 0 | 1 |    New Index (6+)     |
   +---+---+-----------------------+
   |          Name Index (8+)      |
   +---+---------------------------+
   | H |     Value Length (7+)     |
   +---+---------------------------+
   | Value String (Length octets)  |
   +-------------------------------+

Literal Header Field with Indexing -- Indexed Name

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 0 | 1 |    New Index (6+)     |
   +---+---+-----------------------+
   |               0               |
   +---+---+-----------------------+
   | H |     Name Length (7+)      |
   +---+---------------------------+
   |  Name String (Length octets)  |
   +---+---------------------------+
   | H |     Value Length (7+)     |
   +---+---------------------------+
   | Value String (Length octets)  |
   +-------------------------------+

Literal Header Field with Indexing -- New Name

A literal header field with incremental indexing representation starts with the ‘01’ 2-bit pattern, followed by the new index of the header represented as an integer with a 6-bit prefix. This value is always greater than the number of entries in the static table.

If the header field name matches the header field name of an entry stored in the static table or the dynamic table, the header field name can be represented using the index of that entry. In this case, the index of the entry is represented as an integer with an 8-bit prefix (see Section 5.1 of [RFC7231]). This value is always non-zero.

Otherwise, the header field name is represented as a string literal (see Section 5.2 of [RFC7231]). A value 0 is used in place of the 8-bit index, followed by the header field name.

Either form of header field name representation is followed by the header field value represented as a string literal (see Section 5.2).

An encoder MUST NOT attempt to place a value at an index not known to be vacant. An encoder MAY insert the same value to the same vacant slot multiple times in different frames, to reduce the risk of blocking from out-of-order frame interpretation. However, a decoder MUST treat the attempt to insert a different header field into an occupied slot as a fatal error.

2.2.2. Deletion

(This section replaces [RFC7541], Section 6.3.)

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 0 | 0 | 1 |   RefCount (5+)   |
   +---+---+---+---+---------------+
   |          Index (8+)           |
   +-------------------------------+

Header Field Deletion

A deletion starts with the ‘001’ 3-bit pattern, followed by the number of references to the deleted item (represented as an integer with a 5-bit prefix) and the index of the deleted item (represented as an integer with an 8-bit prefix).

The encoder may delete an entry in the dynamic header table at any time in order to stay below the decoder’s declared memory boundary. This instruction tells the decoder that they should prepare to delete the specified entry after all preceding frames referencing it have been received. The delete instruction includes the count of such frames to facilitate the decoder’s garbage collection process.

2.2.3. The QPACK-ACK frame

Each peer MUST periodically emit a QPACK-ACK frame (0xTBD) on the connection control stream to acknowledge deletions. A peer MAY omit sending a new QPACK-ACK frame if no deletions have completed since the last frame.

The QPACK-ACK frame defines no flags and consists of a bitmap. The first bit in the bitmap reflects the first index after the static table (currently 62), and each successive bit indicates the next integer value. Each bit MUST be set if the indexed entry has had a deletion complete since the preceding QPACK-ACK frame and MUST be unset otherwise. Indices beyond the end of the QPACK-ACK frame are assumed to be unset.

Upon receipt, an encoder uses the table to confirm which items have been deleted. At this point, the space can be recovered by the encoder and the encoder can safely reuse the index for future insertions.

3. Use in HTTP/QUIC

HTTP/QUIC [I-D.ietf-quic-http] currently retains the HPACK encoder/decoder from HTTP/2, using a Sequence number to enforce ordering. Using QPACK instead would entail the following changes:

• The Sequence field is removed from HEADERS frames (Section 5.2.2) and PUSH_PROMISE frames (Section 5.2.6).
• Header Block Fragments consist of QPACK data instead of HPACK data.
• The ordering requirements of header block fragments are eliminated.

A HEADERS or PUSH_PROMISE frame MAY contain an arbitrary number of QPACK instructions, but QPACK instructions SHOULD NOT cross a boundary between successive HEADERS frames. A partial HEADERS or PUSH_PROMISE frame MAY be processed upon arrival and the resulting partial header set emitted or buffered according to implementation requirements.

4. Performance Considerations

While QPACK is designed to minimize head-of-line blocking between streams on header decoding, there are some situations in which lost or delayed packets can still impact the performance of header compression.

References to indexed entries will block if the frame containing the entry definition is lost or delayed. Encoders MAY choose to trade off compression efficiency and avoid blocking by repeating the literal-with-indexing instruction rather than referencing the dynamic table until the insertion is known to be complete.

Delayed frames which prevent deletes from completing can prevent the encoder from adding any new entries due to the maximum table size. This does not block the encoder from continuing to make requests, but could sharply limit compression performance. Encoders would be well-served to delete entries in advance of encountering the table maximum. Decoders SHOULD be prompt about emitting QPACK-ACK frames to enable the encoder to recover the table space.

Note that this situation can arise as well from reducing the maximum table size abruptly – the encoder will find itself unable to add new entries for at least one RTT.

Decoders MAY choose whether to process partial header blocks upon arrival. Failure to process partial header blocks could introduce head-of-line blocking on other streams which depend on the definitions in the blocks, but processing them means buffering the resulting output, which is presumably larger than the encoded form.

5. Security Considerations

The security considerations for QPACK are believed to be the same as for HPACK.

6. IANA Considerations

This document currently makes no request of IANA, but probably should. In particular, the QPACK-ACK frame needs to be registered and have a frame type number assigned.

7. Acknowledgements

This draft draws heavily on the text of [RFC7541]. The indirect input of those authors is gratefully acknowledged, as well as ideas gleefully stolen from:

• Jana Iyengar
• Patrick McManus
• Martin Thomson
• Charles ‘Buck’ Krasic
• Kyle Rose

8. Normative References

Author's Address