QPACK: Header Compression for HTTP/3

2.1.1. Reference Tracking

An encoder MUST ensure that a header block which references a dynamic table entry is not processed by the decoder after the referenced entry has been evicted. Hence the encoder needs to retain information about each compressed header block that references the dynamic table until that header block is acknowledged by the decoder; see Section 4.4.1.¶

2.1.2. Limits on Dynamic Table Insertions

Inserting entries into the dynamic table might not be possible if the table contains entries which cannot be evicted.¶

A dynamic table entry cannot be evicted immediately after insertion, even if it has never been referenced. Once the insertion of a dynamic table entry has been acknowledged and there are no outstanding unacknowledged references to the entry, the entry becomes evictable.¶

If the dynamic table does not contain enough room for a new entry without evicting other entries, and the entries which would be evicted are not evictable, the encoder MUST NOT insert that entry into the dynamic table (including duplicates of existing entries). In order to avoid this, an encoder that uses the dynamic table has to keep track of whether each entry is currently evictable or not.¶

   +----------+---------------------------------+--------+
   | Draining |          Referenceable          | Unused |
   | Entries  |             Entries             | Space  |
   +----------+---------------------------------+--------+
   ^          ^                                 ^
   |          |                                 |
 Dropping    Draining Index               Insertion Point
  Point

2.1.3. Blocked Streams

Because QUIC does not guarantee order between data on different streams, a decoder might encounter a header block that references a dynamic table entry that it has not yet received.¶

Each header block contains a Required Insert Count (Section 4.5.1), the lowest possible value for the Insert Count with which the header block can be decoded. For a header block with references to the dynamic table, the Required Insert Count is one larger than the largest absolute index of all referenced dynamic table entries. For a header block with no references to the dynamic table, the Required Insert Count is zero.¶

When the decoder receives a header block with a Required Insert Count greater than its own Insert Count, the stream cannot be processed immediately, and is considered "blocked"; see Section 2.2.1.¶

The decoder specifies an upper bound on the number of streams which can be blocked using the SETTINGS_QPACK_BLOCKED_STREAMS setting; see Section 5. An encoder MUST limit the number of streams which could become blocked to the value of SETTINGS_QPACK_BLOCKED_STREAMS at all times. If a decoder encounters more blocked streams than it promised to support, it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED.¶

Note that the decoder might not become blocked on every stream which risks becoming blocked.¶

An encoder can decide whether to risk having a stream become blocked. If permitted by the value of SETTINGS_QPACK_BLOCKED_STREAMS, compression efficiency can often be improved by referencing dynamic table entries that are still in transit, but if there is loss or reordering the stream can become blocked at the decoder. An encoder can avoid the risk of blocking by only referencing dynamic table entries which have been acknowledged, but this could mean using literals. Since literals make the header block larger, this can result in the encoder becoming blocked on congestion or flow control limits.¶

2.1.4. Avoiding Flow Control Deadlocks

Writing instructions on streams that are limited by flow control can produce deadlocks.¶

A decoder might stop issuing flow control credit on the stream that carries a header block until the necessary updates are received on the encoder stream. If the granting of flow control credit on the encoder stream (or the connection as a whole) depends on the consumption and release of data on the stream carrying the header block, a deadlock might result.¶

More generally, a stream containing a large instruction can become deadlocked if the decoder withholds flow control credit until the instruction is completely received.¶

To avoid these deadlocks, an encoder SHOULD avoid writing an instruction unless sufficient stream and connection flow control credit is available for the entire instruction.¶

2.1.5. Known Received Count

The Known Received Count is the total number of dynamic table insertions and duplications acknowledged by the decoder. The encoder tracks the Known Received Count in order to identify which dynamic table entries can be referenced without potentially blocking a stream. The decoder tracks the Known Received Count in order to be able to send Insert Count Increment instructions.¶

A Header Acknowledgement instruction (Section 4.4.1) implies that the decoder has received all dynamic table state necessary to process corresponding the header block. If the Required Insert Count of the acknowledged header block is greater than the current Known Received Count, Known Received Count is updated to the value of the Required Insert Count.¶

An Insert Count Increment instruction Section 4.4.3 increases the Known Received Count by its Increment parameter. See Section 2.2.2.3 for guidance.¶

2.2.1. Blocked Decoding

Upon receipt of a header block, the decoder examines the Required Insert Count. When the Required Insert Count is less than or equal to the decoder's Insert Count, the header block can be processed immediately. Otherwise, the stream on which the header block was received becomes blocked.¶

While blocked, header block data SHOULD remain in the blocked stream's flow control window. A stream becomes unblocked when the Insert Count becomes greater than or equal to the Required Insert Count for all header blocks the decoder has started reading from the stream.¶

When processing header blocks, the decoder expects the Required Insert Count to exactly match the value defined in Section 2.1.3. If it encounters a smaller value than expected, it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED; see Section 2.2.3. If it encounters a larger value than expected, it MAY treat this as a connection error of type QPACK_DECOMPRESSION_FAILED.¶

2.2.2. State Synchronization

The decoder signals the following events by emitting decoder instructions (Section 4.4) on the decoder stream.¶

2.2.3. Invalid References

If the decoder encounters a reference in a header block representation to a dynamic table entry which has already been evicted or which has an absolute index greater than or equal to the declared Required Insert Count (Section 4.5.1), it MUST treat this as a connection error of type QPACK_DECOMPRESSION_FAILED.¶

If the decoder encounters a reference in an encoder instruction to a dynamic table entry which has already been evicted, it MUST treat this as a connection error of type QPACK_ENCODER_STREAM_ERROR.¶

3.2.1. Dynamic Table Size

The size of the dynamic table is the sum of the size of its entries.¶

The size of an entry is the sum of its name's length in bytes, its value's length in bytes, and 32. The size of an entry is calculated using the length of its name and value without Huffman encoding applied.¶

3.2.2. Dynamic Table Capacity and Eviction

The encoder sets the capacity of the dynamic table, which serves as the upper limit on its size. The initial capacity of the dynamic table is zero. The encoder sends a Set Dynamic Table Capacity instruction (Section 4.3.1) with a non-zero capacity to begin using the dynamic table.¶

Before a new entry is added to the dynamic table, entries are evicted from the end of the dynamic table until the size of the dynamic table is less than or equal to (table capacity - size of new entry). The encoder MUST NOT cause a dynamic table entry to be evicted unless that entry is evictable; see Section 2.1.2. The new entry is then added to the table. It is an error if the encoder attempts to add an entry that is larger than the dynamic table capacity; the decoder MUST treat this as a connection error of type QPACK_ENCODER_STREAM_ERROR.¶

A new entry can reference an entry in the dynamic table that will be evicted when adding this new entry into the dynamic table. Implementations are cautioned to avoid deleting the referenced name or value if the referenced entry is evicted from the dynamic table prior to inserting the new entry.¶

Whenever the dynamic table capacity is reduced by the encoder (Section 4.3.1), entries are evicted from the end of the dynamic table until the size of the dynamic table is less than or equal to the new table capacity. This mechanism can be used to completely clear entries from the dynamic table by setting a capacity of 0, which can subsequently be restored.¶

3.2.3. Maximum Dynamic Table Capacity

To bound the memory requirements of the decoder, the decoder limits the maximum value the encoder is permitted to set for the dynamic table capacity. In HTTP/3, this limit is determined by the value of SETTINGS_QPACK_MAX_TABLE_CAPACITY sent by the decoder; see Section 5. The encoder MUST not set a dynamic table capacity that exceeds this maximum, but it can choose to use a lower dynamic table capacity; see Section 4.3.1.¶

For clients using 0-RTT data in HTTP/3, the server's maximum table capacity is the remembered value of the setting, or zero if the value was not previously sent. When the client's 0-RTT value of the SETTING is zero, the server MAY set it to a non-zero value in its SETTINGS frame. If the remembered value is non-zero, the server MUST send the same non-zero value in its SETTINGS frame. If it specifies any other value, or omits SETTINGS_QPACK_MAX_TABLE_CAPACITY from SETTINGS, the encoder must treat this as a connection error of type QPACK_DECODER_STREAM_ERROR.¶

For HTTP/3 servers and HTTP/3 clients when 0-RTT is not attempted or is rejected, the maximum table capacity is 0 until the encoder processes a SETTINGS frame with a non-zero value of SETTINGS_QPACK_MAX_TABLE_CAPACITY.¶

When the maximum table capacity is zero, the encoder MUST NOT insert entries into the dynamic table, and MUST NOT send any encoder instructions on the encoder stream.¶

3.2.4. Absolute Indexing

Each entry possesses an absolute index which is fixed for the lifetime of that entry. The first entry inserted has an absolute index of "0"; indices increase by one with each insertion.¶

3.2.5. Relative Indexing

Relative indices begin at zero and increase in the opposite direction from the absolute index. Determining which entry has a relative index of "0" depends on the context of the reference.¶

In encoder instructions (Section 4.3), a relative index of "0" refers to the most recently inserted value in the dynamic table. Note that this means the entry referenced by a given relative index will change while interpreting instructions on the encoder stream.¶

      +-----+---------------+-------+
      | n-1 |      ...      |   d   |  Absolute Index
      + - - +---------------+ - - - +
      |  0  |      ...      | n-d-1 |  Relative Index
      +-----+---------------+-------+
      ^                             |
      |                             V
Insertion Point               Dropping Point

n = count of entries inserted
d = count of entries dropped

Unlike in encoder instructions, relative indices in header block representations are relative to the Base at the beginning of the header block; see Section 4.5.1. This ensures that references are stable even if header blocks and dynamic table updates are processed out of order.¶

In a header block a relative index of "0" refers to the entry with absolute index equal to Base - 1.¶

               Base
                |
                V
    +-----+-----+-----+-----+-------+
    | n-1 | n-2 | n-3 | ... |   d   |  Absolute Index
    +-----+-----+  -  +-----+   -   +
                |  0  | ... | n-d-3 |  Relative Index
                +-----+-----+-------+

n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2

3.2.6. Post-Base Indexing

Post-Base indices are used in header block instructions for entries with absolute indices greater than or equal to Base, starting at 0 for the entry with absolute index equal to Base, and increasing in the same direction as the absolute index.¶

Post-Base indices allow an encoder to process a header block in a single pass and include references to entries added while processing this (or other) header blocks.¶

               Base
                |
                V
    +-----+-----+-----+-----+-----+
    | n-1 | n-2 | n-3 | ... |  d  |  Absolute Index
    +-----+-----+-----+-----+-----+
    |  1  |  0  |                    Post-Base Index
    +-----+-----+

n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2

4.1.1. Prefixed Integers

The prefixed integer from Section 5.1 of [RFC7541] is used heavily throughout this document. The format from [RFC7541] is used unmodified. Note, however, that QPACK uses some prefix sizes not actually used in HPACK.¶

QPACK implementations MUST be able to decode integers up to and including 62 bits long.¶

4.1.2. String Literals

The string literal defined by Section 5.2 of [RFC7541] is also used throughout. This string format includes optional Huffman encoding.¶

HPACK defines string literals to begin on a byte boundary. They begin with a single bit flag, denoted as 'H' in this document (indicating whether the string is Huffman-coded), followed by the Length encoded as a 7-bit prefix integer, and finally Length bytes of data. When Huffman encoding is enabled, the Huffman table from Appendix B of [RFC7541] is used without modification.¶

This document expands the definition of string literals and permits them to begin other than on a byte boundary. An "N-bit prefix string literal" begins with the same Huffman flag, followed by the length encoded as an (N-1)-bit prefix integer. The prefix size, N, can have a value between 2 and 8 inclusive. The remainder of the string literal is unmodified.¶

A string literal without a prefix length noted is an 8-bit prefix string literal and follows the definitions in [RFC7541] without modification.¶

4.3.1. Set Dynamic Table Capacity

An encoder informs the decoder of a change to the dynamic table capacity using an instruction which begins with the '001' three-bit pattern. This is followed by the new dynamic table capacity represented as an integer with a 5-bit prefix; see Section 4.1.1.¶

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 |   Capacity (5+)   |
+---+---+---+-------------------+

The new capacity MUST be lower than or equal to the limit described in Section 3.2.3. In HTTP/3, this limit is the value of the SETTINGS_QPACK_MAX_TABLE_CAPACITY parameter (Section 5) received from the decoder. The decoder MUST treat a new dynamic table capacity value that exceeds this limit as a connection error of type QPACK_ENCODER_STREAM_ERROR.¶

Reducing the dynamic table capacity can cause entries to be evicted; see Section 3.2.2. This MUST NOT cause the eviction of entries which are not evictable; see Section 2.1.2. Changing the capacity of the dynamic table is not acknowledged as this instruction does not insert an entry.¶

4.3.2. Insert With Name Reference

An encoder adds an entry to the dynamic table where the header field name matches the header field name of an entry stored in the static or the dynamic table using an instruction that starts with the '1' one-bit pattern. The second ('T') bit indicates whether the reference is to the static or dynamic table. The 6-bit prefix integer (Section 4.1.1) that follows is used to locate the table entry for the header name. When T=1, the number represents the static table index; when T=0, the number is the relative index of the entry in the dynamic table.¶

The header name reference is followed by the header field value represented as a string literal; see Section 4.1.2.¶

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

4.3.3. Insert Without Name Reference

An encoder adds an entry to the dynamic table where both the header field name and the header field value are represented as string literals using an instruction that starts with the '01' two-bit pattern.¶

This is followed by the name represented as a 6-bit prefix string literal, and the value represented as an 8-bit prefix string literal; see Section 4.1.2.¶

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

4.3.4. Duplicate

An encoder duplicates an existing entry in the dynamic table using an instruction that begins with the '000' three-bit pattern. This is followed by the relative index of the existing entry represented as an integer with a 5-bit prefix; see Section 4.1.1.¶

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

The existing entry is re-inserted into the dynamic table without resending either the name or the value. This is useful to avoid adding a reference to an older entry, which might block inserting new entries.¶

4.4.1. Header Acknowledgement

After processing a header block whose declared Required Insert Count is not zero, the decoder emits a Header Acknowledgement instruction. The instruction begins with the '1' one-bit pattern which is followed by the header block's associated stream ID encoded as a 7-bit prefix integer; see Section 4.1.1.¶

This instruction is used as described in Section 2.1.5 and in Section 2.2.2.¶

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |      Stream ID (7+)       |
+---+---------------------------+

If an encoder receives a Header Acknowledgement instruction referring to a stream on which every header block with a non-zero Required Insert Count has already been acknowledged, that MUST be treated as a connection error of type QPACK_DECODER_STREAM_ERROR.¶

The Header Acknowledgement instruction might increase the Known Received Count; see Section 2.1.5.¶

4.4.2. Stream Cancellation

When a stream is reset or reading is abandoned, the decoder emits a Stream Cancellation instruction. The instruction begins with the '01' two-bit pattern, which is followed by the stream ID of the affected stream encoded as a 6-bit prefix integer.¶

This instruction is used as described in Section 2.2.2.¶

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |     Stream ID (6+)    |
+---+---+-----------------------+

4.4.3. Insert Count Increment

The Insert Count Increment instruction begins with the '00' two-bit pattern, followed by the Increment encoded as a 6-bit prefix integer. This instruction increases the Known Received Count (Section 2.1.5) by the value of the Increment parameter. The decoder should send an Increment value that increases the Known Received Count to the total number of dynamic table insertions and duplications processed so far.¶

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 |     Increment (6+)    |
+---+---+-----------------------+

An encoder that receives an Increment field equal to zero, or one that increases the Known Received Count beyond what the encoder has sent MUST treat this as a connection error of type QPACK_DECODER_STREAM_ERROR.¶

4.5.1. Header Block Prefix

Each header block is prefixed with two integers. The Required Insert Count is encoded as an integer with an 8-bit prefix after the encoding described in Section 4.5.1.1). The Base is encoded as a sign bit ('S') and a Delta Base value with a 7-bit prefix; see Section 4.5.1.2.¶

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
|   Required Insert Count (8+)  |
+---+---------------------------+
| S |      Delta Base (7+)      |
+---+---------------------------+
|      Compressed Headers     ...
+-------------------------------+

   if ReqInsertCount == 0:
      EncInsertCount = 0
   else:
      EncInsertCount = (ReqInsertCount mod (2 * MaxEntries)) + 1

   MaxEntries = floor( MaxTableCapacity / 32 )

   FullRange = 2 * MaxEntries
   if EncodedInsertCount == 0:
      ReqInsertCount = 0
   else:
      if EncodedInsertCount > FullRange:
         Error
      MaxValue = TotalNumberOfInserts + MaxEntries

      # MaxWrapped is the largest possible value of
      # ReqInsertCount that is 0 mod 2*MaxEntries
      MaxWrapped = floor(MaxValue / FullRange) * FullRange
      ReqInsertCount = MaxWrapped + EncodedInsertCount - 1

      # If ReqInsertCount exceeds MaxValue, the Encoder's value
      # must have wrapped one fewer time
      if ReqInsertCount > MaxValue:
         if ReqInsertCount <= FullRange:
            Error
         ReqInsertCount -= FullRange

      # Value of 0 must be encoded as 0.
      if ReqInsertCount == 0:
         Error

   if S == 0:
      Base = ReqInsertCount + DeltaBase
   else:
      Base = ReqInsertCount - DeltaBase - 1

4.5.2. Indexed Header Field

An indexed header field representation identifies an entry in the static table, or an entry in the dynamic table with an absolute index less than the value of the Base.¶

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

This representation starts with the '1' 1-bit pattern, followed by the 'T' bit indicating whether the reference is into the static or dynamic table. The 6-bit prefix integer (Section 4.1.1) that follows is used to locate the table entry for the header field. When T=1, the number represents the static table index; when T=0, the number is the relative index of the entry in the dynamic table.¶

4.5.3. Indexed Header Field With Post-Base Index

An indexed header field with post-base index representation identifies an entry in the dynamic table with an absolute index greater than or equal to the value of the Base.¶

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

This representation starts with the '0001' 4-bit pattern. This is followed by the post-base index (Section 3.2.6) of the matching header field, represented as an integer with a 4-bit prefix; see Section 4.1.1.¶

4.5.4. Literal Header Field With Name Reference

A literal header field with name reference representation encodes a header field where the header field name matches the header field name of an entry in the static table, or the header field name of an entry in the dynamic table with an absolute index less than the value of the Base.¶

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 0 | 1 | N | T |Name Index (4+)|
   +---+---+---+---+---------------+
   | H |     Value Length (7+)     |
   +---+---------------------------+
   |  Value String (Length bytes)  |
   +-------------------------------+

This representation starts with the '01' two-bit pattern. The following bit, 'N', indicates whether an intermediary is permitted to add this header to the dynamic header table on subsequent hops. When the 'N' bit is set, the encoded header MUST always be encoded with a literal representation. In particular, when a peer sends a header field that it received represented as a literal header field with the 'N' bit set, it MUST use a literal representation to forward this header field. This bit is intended for protecting header field values that are not to be put at risk by compressing them; see Section 7 for more details.¶

The fourth ('T') bit indicates whether the reference is to the static or dynamic table. The 4-bit prefix integer (Section 4.1.1) that follows is used to locate the table entry for the header name. When T=1, the number represents the static table index; when T=0, the number is the relative index of the entry in the dynamic table.¶

Only the header field name is taken from the dynamic table entry; the header field value is encoded as an 8-bit prefix string literal; see Section 4.1.2.¶

4.5.5. Literal Header Field With Post-Base Name Reference

A literal header field with post-base name reference representation encodes a header field where the header field name matches the header field name of a dynamic table entry with an absolute index greater than or equal to the value of the Base.¶

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 0 | 0 | 0 | 0 | N |NameIdx(3+)|
   +---+---+---+---+---+-----------+
   | H |     Value Length (7+)     |
   +---+---------------------------+
   |  Value String (Length bytes)  |
   +-------------------------------+

This representation starts with the '0000' four-bit pattern. The fifth bit is the 'N' bit as described in Section 4.5.4. This is followed by a post-base index of the dynamic table entry (Section 3.2.6) encoded as an integer with a 3-bit prefix; see Section 4.1.1.¶

Only the header field name is taken from the dynamic table entry; the header field value is encoded as an 8-bit prefix string literal; see Section 4.1.2.¶

4.5.6. Literal Header Field Without Name Reference

The literal header field without name reference representation encodes a header field name and a header field value as string literals.¶

     0   1   2   3   4   5   6   7
   +---+---+---+---+---+---+---+---+
   | 0 | 0 | 1 | N | H |NameLen(3+)|
   +---+---+---+---+---+-----------+
   |  Name String (Length bytes)   |
   +---+---------------------------+
   | H |     Value Length (7+)     |
   +---+---------------------------+
   |  Value String (Length bytes)  |
   +-------------------------------+

This representation begins with the '001' three-bit pattern. The fourth bit is the 'N' bit as described in Section 4.5.4. The name follows, represented as a 4-bit prefix string literal, then the value, represented as an 8-bit prefix string literal; see Section 4.1.2.¶