Internet DRAFT - draft-tikhonov-quic-qmin
draft-tikhonov-quic-qmin
QUIC Working Group D. Tikhonov
Internet-Draft LiteSpeed Technologies
Intended status: Standards Track November 13, 2017
Expires: May 17, 2018
QMIN: Header Compression for QUIC
draft-tikhonov-quic-qmin-00
Abstract
This specification defines QMIN, a compression format and protocol
for HTTP/2 ([RFC7540]) headers. QMIN is based on HPACK ([RFC7541]).
The modifications to HPACK are meant to allow robust compression use
in QUIC: That is, no head-of-line blocking and low overhead. QMIN is
guided by HPACK design principles. It inherits all of HPACK's data
structures and retains binary compatibility with it. While designed
with QUIC in mind, QMIN can be used in other contexts.
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 https://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 May 17, 2018.
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
(https://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
Tikhonov Expires May 17, 2018 [Page 1]
Internet-Draft QMIN: Header Compression for QUIC November 2017
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Checkpoint States . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Checkpoint State: NEW . . . . . . . . . . . . . . . . . . 5
3.2. Checkpoint State: PENDING . . . . . . . . . . . . . . . . 5
3.3. Checkpoint State: LIVE . . . . . . . . . . . . . . . . . 5
3.4. Checkpoint State: DEAD . . . . . . . . . . . . . . . . . 6
4. Control Stream . . . . . . . . . . . . . . . . . . . . . . . 6
4.1. Encoder Commands . . . . . . . . . . . . . . . . . . . . 6
4.1.1. INSERT_ENTRY . . . . . . . . . . . . . . . . . . . . 6
4.1.2. REUSE_ENTRY . . . . . . . . . . . . . . . . . . . . . 7
4.1.3. FLUSH_CHKPOINT . . . . . . . . . . . . . . . . . . . 8
4.1.4. DROP_CHKPOINT . . . . . . . . . . . . . . . . . . . . 8
4.2. Decoder Messages . . . . . . . . . . . . . . . . . . . . 9
4.2.1. ACK_FLUSH . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Stream Notification Commands . . . . . . . . . . . . . . 9
4.3.1. STREAM_DONE . . . . . . . . . . . . . . . . . . . . . 9
4.4. Expansion . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Header Encoding . . . . . . . . . . . . . . . . . . . . . . . 10
6. Table Size Calculation . . . . . . . . . . . . . . . . . . . 10
6.1. Entry Size . . . . . . . . . . . . . . . . . . . . . . . 10
6.2. Checkpoint Size . . . . . . . . . . . . . . . . . . . . . 10
6.3. Overall Table Size . . . . . . . . . . . . . . . . . . . 11
6.4. Comparison with HPACK . . . . . . . . . . . . . . . . . . 11
7. Encoding Process . . . . . . . . . . . . . . . . . . . . . . 11
7.1. Indexable Header Fields . . . . . . . . . . . . . . . . . 11
7.1.1. New Index . . . . . . . . . . . . . . . . . . . . . . 11
7.1.2. Existing Index . . . . . . . . . . . . . . . . . . . 11
7.2. Non-indexable Header Fields . . . . . . . . . . . . . . . 12
7.3. When Maximum Table Size Is Reached . . . . . . . . . . . 12
7.4. Memory Cost of Flushing . . . . . . . . . . . . . . . . . 12
8. Decoding Process . . . . . . . . . . . . . . . . . . . . . . 12
9. Encoder Strategies . . . . . . . . . . . . . . . . . . . . . 13
9.1. Flushing and Dropping . . . . . . . . . . . . . . . . . . 13
9.1.1. Simple Strategy . . . . . . . . . . . . . . . . . . . 13
9.1.2. Rule-Based Strategy . . . . . . . . . . . . . . . . . 13
9.1.3. Feedback-Based Strategy . . . . . . . . . . . . . . . 14
9.2. Control Channel Cost . . . . . . . . . . . . . . . . . . 14
10. HPACK Interoperability . . . . . . . . . . . . . . . . . . . 15
11. Implementation Notes . . . . . . . . . . . . . . . . . . . . 15
11.1. Control Messages Made Easy . . . . . . . . . . . . . . . 15
12. QMIN Drawbacks . . . . . . . . . . . . . . . . . . . . . . . 15
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 16
Tikhonov Expires May 17, 2018 [Page 2]
Internet-Draft QMIN: Header Compression for QUIC November 2017
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 16
14.1. Normative References . . . . . . . . . . . . . . . . . . 16
14.2. Informative References . . . . . . . . . . . . . . . . . 16
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 16
1. Introduction
Google QUIC implementation uses HPACK to compress HTTP headers. HTTP
headers for all requests and responses are sent on a dedicated
stream. This introduces head-of-line (HoL) blocking: if this stream
is blocked due to packet loss, all HTTP messages whose compressed
headers follow the lost packet in the stream are stalled. Solving
the HoL problem has been one of the goals of the IETF QUIC Working
Group.
QMIN solves the HoL problem and has the following beneficial
properties:
o The compression logic is mostly contained in the encoder, keeping
the decoder simple.
o QMIN is transport-independent.
o Memory penalty over HPACK is manageable (Section 6.4).
o QMIN and HPACK are interoperable (Section 10).
2. Overview
The QMIN innovation is in using a *checkpointed* dynamic table, with
the encoder always aware whether the decoder possesses the dynamic
table entry (from here on, simply "entry") necessary for decoding a
header. The encoder learns this information from messages carried on
a single dedicated control stream. The reliable nature of this
stream guarantees serialized protocol operation.
In request and response streams, header blocks use either literal
representations or references to entries that are known to exist in
the decoder table. Dynamic table changes are communicated via the
control stream. The process of decoding header blocks does not
change the decoder state, thus avoiding the HoL blocking.
QMIN inherits HPACK's data structures and encoding formats (see
[RFC7541]).
In addition, *checkpoints* are introduced. A checkpoint is used to
track entries added to the dynamic table and streams that reference
those entries.
Checkpoints are ordered in a list, from newest to oldest. A new
checkpoint gets appended to the "new" end of the checkpoint list.
Tikhonov Expires May 17, 2018 [Page 3]
Internet-Draft QMIN: Header Compression for QUIC November 2017
The encoder always has a checkpoint in the NEW state. Flushing a
checkpoint is a two-step operation. First, a FLUSH_CHKPOINT command
is sent to the decoder. At that time, the encoder's NEW checkpoint
becomes PENDING. The decoder moves its NEW checkpoint directly to
LIVE and responds with ACK_FLUSH message. When the encoder receives
this message, its PENDING checkpoint becomes LIVE and entries
associated with this checkpoint become available for encoding.
The encoder always has exactly one NEW checkpoint, zero or one
PENDING checkpoints, and zero or more LIVE and DEAD checkpoints. The
decoder has exactly one NEW checkpoint and zero or more LIVE
checkpoints.
Unused entries are evicted indirectly, by dropping checkpoints.
Before a checkpoint can be dropped, its state is changed to DEAD: the
encoder cannot use an entry for encoding that is not referenced by a
LIVE checkpoint. Changing a checkpoint's state to DEAD allows the
checkpoint to age out. The encoder can decide to drop a DEAD
checkpoint when it is no longer referenced by any active streams.
See Section 3.
The control stream is used to notify the encoder that the peer is
done decoding HTTP headers for a stream using the STREAM_DONE
message. The encoder uses this information to track which
checkpoints can be dropped.
When a checkpoint is dropped, the table entries it references are
checked: if an entry is no longer referenced by any checkpoint, the
entry is evicted. The encoder sends the DROP_CHKPOINT command to the
decoder when it drops a checkpoint; no acknowledgement for this
command is necessary.
Dropping a checkpoint and the entries associated with it is not
limited to just the oldest checkpoint; any DEAD checkpoint -- as long
as state transition rules are followed -- may be dropped. This
flexibility permits the encoder to use a number of strategies for
entry eviction.
As long as the maximum dynamic table size is observed, new
checkpoints can be created; no upper limit on the number of
checkpoints is specified. A well-balanced spread of checkpoints
permits the encoder to recycle entries effectively.
The HPACK index address space stays the same. The static table stays
as-is. Indices are unique between all checkpoints. An index can be
reused once no checkpoint references it.
Tikhonov Expires May 17, 2018 [Page 4]
Internet-Draft QMIN: Header Compression for QUIC November 2017
3. Checkpoint States
A checkpoint can be in one of several states. It goes through these
states in order, without skipping any, throughout its lifetime.
On the encoder, the checkpoint states are:
o NEW
o PENDING
o LIVE
o DEAD
On the decoder, only two states are used:
o NEW
o LIVE
3.1. Checkpoint State: NEW
Applicability: encoder and decoder.
All newly reused or inserted entries are referred to by the NEW
checkpoint. There is always a NEW checkpoint. Whenever this
checkpoint changes state, a new NEW checkpoint is created.
The encoder and the decoder both begin with an empty NEW checkpoint.
3.2. Checkpoint State: PENDING
Applicability: encoder only.
At some point, the encoder may want to flush new entries. It then
changes the NEW checkpoint state to PENDING and issues the
FLUSH_CHKPOINT command. The entries in the PENDING checkpoint cannot
be used for encoding yet; the encoder waits for ACK_FLUSH message.
Upon receipt of this message, the PENDING checkpoint changes to the
LIVE state.
There can be at most one PENDING checkpoint.
3.3. Checkpoint State: LIVE
Applicability: encoder and decoder.
Entries that were added to the dynamic table when this checkpoint was
in the NEW state can now be used to encode and decode headers. The
decoder moves its NEW checkpoint to LIVE when it receives the
Tikhonov Expires May 17, 2018 [Page 5]
Internet-Draft QMIN: Header Compression for QUIC November 2017
FLUSH_CHKPOINT command. The encoder moves its PENDING checkpoint to
LIVE when it receives the ACK_FLUSH message.
Other than the maximum table size, the number of LIVE checkpoints is
not limited.
3.4. Checkpoint State: DEAD
Applicability: encoder only.
To evict old entries, the encoder marks a LIVE checkpoint as DEAD.
(An entry that is not referenced by any LIVE checkpoint cannot be
used for header encoding. Marking a checkpoint DEAD allows entries
to age out.) When all streams whose header blocks were encoded using
entries referenced by this checkpoint have been closed, the
checkpoint is destroyed and the DROP_CHKPOINT message is sent to the
decoder.
There can be any number of DEAD checkpoints.
4. Control Stream
The control stream is used to carry messages to the encoder and the
decoder. This is the only way that dynamic table changes are
communicated to the decoder.
The messages are either
o Commands issued by the encoder to the decoder;
o Acknowledgements issued by the decoder; or
o Stream processed notifications sent to the encoder.
The format of the messages is similar in structure to the format of
the encoded header fields in the header block as specified in HPACK
(RFC 7541, Section 6). The same variable-length integer encoding
mechanism is used (RFC 7541, Section 5).
4.1. Encoder Commands
The encoder issues the following commands:
4.1.1. INSERT_ENTRY
This message is sent by the encoder at the same time it creates a new
indexed entry in its dynamic table. The smallest unused index in the
address space ( [62 - oO] ) MUST be assigned to the new entry.
Tikhonov Expires May 17, 2018 [Page 6]
Internet-Draft QMIN: Header Compression for QUIC November 2017
The decoder creates the new entry in the table, but does not make the
entry available for decoding yet. If indexed name representation is
used, but the decoder does not have this entry already referenced by
its NEW checkpoint, it MUST treat it as an error.
The format of this message is identical to HPACK's Literal Header
Field Representation (RFC 7541, Section 6.2).
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | Index (6+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
Figure: Insert Entry - Indexed Name
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | 0 |
+---+---+-----------------------+
| H | Name Length (7+) |
+---+---------------------------+
| Name String (Length octets) |
+---+---------------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length octets) |
+-------------------------------+
Figure: Insert Entry - New Name
4.1.2. REUSE_ENTRY
This message is issued instead of INSERT_ENTRY whenever the encoder
uses an indexed representation from an existing LIVE checkpoint to
encode a header and this index has not yet been added to the NEW
checkpoint.
Upon receipt of the REUSE_ENTRY command, the decoder creates a
reference to the corresponding entry in its NEW checkpoint.
The encoder MUST NOT issue multiple REUSE_ENTRY commands for the same
entry in the context of the same NEW checkpoint. If the decoder
receives the REUSE_ENTRY message that specifies an index already
referenced by its NEW checkpoint, it MUST treat it as an error. If a
Tikhonov Expires May 17, 2018 [Page 7]
Internet-Draft QMIN: Header Compression for QUIC November 2017
non-existent index is specified, the decoder MUST treat is as an
error.
The format of this message is identical to HPACK's Indexed Header
Field Representation (RFC 7541, Section 6.1).
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | Index (7+) |
+---+---------------------------+
Figure: Reuse Entry Message
4.1.3. FLUSH_CHKPOINT
When the encoder wants to start using entries associated with the NEW
checkpoint, it moves it from NEW to PENDING state and issues the
FLUSH_CHKPOINT command.
The decoder moves its checkpoint from NEW to LIVE: all newly inserted
entries become available for decoding.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
+---+---------------------------+
Figure: Flush Checkpoint
4.1.4. DROP_CHKPOINT
When a DEAD checkpoint is no longer referenced by any streams, the
encoder MAY drop it. This means evicting all dynamic table entries
whose reference counts have gone to zero and issuing the
DROP_CHKPOINT command.
The ID of the checkpoint to drop is its current position in the
checkpoint list, from oldest to newest. Thus, the oldest checkpoint
has ID 0, second-oldest has ID 1, and so on.
The decoder performs the same operation as the encoder: decrements
reference counts of dynamic table entries -- evicting those whose
reference counts are now zero -- and drops the specified checkpoint.
Tikhonov Expires May 17, 2018 [Page 8]
Internet-Draft QMIN: Header Compression for QUIC November 2017
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+----+----+
| 0 | 0 | 0 | 0 | 0 | 1 | ID (2+) |
+---+------------------------+----+
Figure: Drop Checkpoint
4.2. Decoder Messages
The decoder sends replies to one of the encoder commands.
4.2.1. ACK_FLUSH
The decoder SHOULD inform the encoder that it has performed the flush
using ACK_FLUSH message. The encoder's PENDING checkpoint becomes
LIVE when this acknowledgement is received.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
+---+---------------------------+
Figure: Ack Flush
4.3. Stream Notification Commands
4.3.1. STREAM_DONE
When all HTTP headers for a stream have been decoded, this message is
sent to inform the encoder that the peer is done with the stream.
This allows the encoder to decrement its reference counts,
potentially triggering a checkpoint flush or a checkpoint drop.
It is preferable to send this message as soon as possible. For
example, one does not have to wait until stream FIN is read if HTTP
headers have been decoded and there are no trailers.
0 1 2 3 4 5 6 7
+---+---+---+---+---+----+-----+-----+
| 0 | 0 | 0 | 0 | 1 | Stream ID (3+) |
+---+--------------------------------+
Figure: Stream Done
The client knows that the server is done with the request if the
stream is reset or it has read all of the response. A QMIN
implementation SHOULD use this knowledge to let the encoder know that
Tikhonov Expires May 17, 2018 [Page 9]
Internet-Draft QMIN: Header Compression for QUIC November 2017
the stream is done. The encoder SHOULD use the earliest indicator to
move its mechanisms along. Any subsequent indicators are no-ops.
4.4. Expansion
Two bit patterns are still available to the command coding scheme:
001 and 00000001. The former is used to encode the dynamic table
size update by HPACK (RFC 7541, Section 6.3). There is no inherent
limitation in QMIN as to why it could not support this command.
5. Header Encoding
The headers are encoded in the same way they are encoded by HPACK,
except QMIN does not support the dynamic table size update specified
in RFC 7541, Section 6.3 in the headers block. This is because
header block decoding is not to change the decoder state.
6. Table Size Calculation
HPACK defines the dynamic table size as "the sum of the size of its
entries." (RFC 7541, Section 4.1). QMIN's dynamic table entry
carries another element -- reference count -- which increases the
entry size.
QMIN introduces checkpoints, whose size should also be accounted for.
A decoder-side checkpoint keeps track of the index values created or
reused when it was NEW.
6.1. Entry Size
A QMIN entry contains a reference count, which makes it larger that
the HPACK entry. Using a standard integer size, the QMIN entry
overhead is set to 36 bytes: 32 bytes overhead of the HPACK entry
plus four bytes for the additional reference count field. Thus, the
QMIN entry size is the sum of the entry name size, the entry value
size, and 36.
6.2. Checkpoint Size
QMIN uses the smallest possible available value (Section 4.1.2) in
the index address space for new entries. Therefore, the total number
of index values is at most the value of the largest index in use. A
checkpoint can track indices via a bitmask: 1 bit per index. The
size of a checkpoint, then, is defined as
(Highest Index Value - 62) / 8 + 128
The additional 128 bytes is the checkpoint overhead.
Tikhonov Expires May 17, 2018 [Page 10]
Internet-Draft QMIN: Header Compression for QUIC November 2017
6.3. Overall Table Size
The decoder table size is calculated as number of entries times the
entry size as calculated in Section 6.1 plus the number of
checkpoints times the checkpoint size as calculated in Section 6.2.
6.4. Comparison with HPACK
In HPACK, a table with 700 dynamic entries and 35,000 bytes allocated
to header names and values is
700 * 32 + 35,000 = 57,400 bytes.
The same table in QMIN with 10 checkpoints is
700 * 36 + 35,000 + 10 * ((1000 / 8) + 128) = 62,730 bytes.
This is a 9% increase in memory consumption.
7. Encoding Process
Given a header field to compress, the encoder returns the compressed
representation of it. In addition, it may emit one or more commands
that should be sent on the control stream.
7.1. Indexable Header Fields
An indexable header field is that which the user specifies as "with
indexing" (RFC 7541, Section 6.2).
7.1.1. New Index
If no matching entry is found, a new entry is created, its ID is
recorded in the NEW checkpoint, and the encoder emits the
INSERT_ENTRY command.
If the encoded name component refers to an existing entry, this entry
is reused as described in Section 7.1.2.
7.1.2. Existing Index
An indexable header field causes the encoder to search the table. If
an existing dynamic table entry is found that is referenced by at
least one LIVE checkpoint, it can be used to encode the header field.
The encoder records a reference to the stream using this entry in one
of the checkpoints. (Which checkpoint to select can be decided based
on strategy. See Section 9.1).
Tikhonov Expires May 17, 2018 [Page 11]
Internet-Draft QMIN: Header Compression for QUIC November 2017
If the NEW checkpoint does not have a reference to this entry, the
reference is recorded in the NEW checkpoint and the REUSE_ENTRY
command is emitted.
7.2. Non-indexable Header Fields
Non-indexable header fields are compressed the same way as HPACK (RFC
7541, Sections 6.2.2 and 6.2.3). The encoder state is not changed.
No command is emitted.
7.3. When Maximum Table Size Is Reached
When the encoder table reaches its maximum size, further insertions
into the dynamic table are not possible. In this case, the encoder
compresses header fields without inserting or reusing entries and
without emitting any commands.
A simple recovery strategy is to mark one or more checkpoints DEAD
immediately.
Alternatively, the existing table may provide an acceptable
compression level. It may be more efficient to wait until this level
falls below a threshold before marking checkpoints DEAD, as it may
become possible to drop an already-DEAD checkpoint before the
threshold is reached.
The encoder SHOULD try to avoid reaching a point when it can no
longer insert new entries. See Section 9.
7.4. Memory Cost of Flushing
Because flushing automatically creates a new NEW checkpoint, it is
possible to get into a situation where a flush is not possible due to
the memory constraint. If inserting a new entry would result in
subsequent inability to flush, the encoder SHOULD flush instead.
8. Decoding Process
All header field representations defined in HPACK (Section 6 of
[RFC7541]) are used as-is. Dynamic size update (Ibid., Section 6.3)
or an unknown command MUST be treated as an error.
The decoder looks up dynamic entries in its table when it is given a
header list to decode. If corresponding entry is not found or if it
is found but not referred to by any of LIVE checkpoints, this MUST be
treated as an error.
Tikhonov Expires May 17, 2018 [Page 12]
Internet-Draft QMIN: Header Compression for QUIC November 2017
9. Encoder Strategies
9.1. Flushing and Dropping
The encoder decides when to flush checkpoints and when to declare
them dead. Flushing SHOULD occur when enough new entries have been
created to try to reuse them. Marking checkpoints as DEAD SHOULD
happen before the table size is exhausted.
If an entry used to encode a header field is referenced to by more
than one LIVE checkpoint, one of them is selected to refer to the
stream ID whose header field has been encoded. Which LIVE checkpoint
to pick is a decision that also affects compression performance.
Several strategies are outlined below.
9.1.1. Simple Strategy
The encoder picks a number of streams to use as a threshold for
flushing checkpoints. Every time header blocks for N streams have
been encoded, flush.
The encoder picks the oldest checkpoint to mark as DEAD. It does so
when table size reaches some proportion, let's say 3/4, of the
maximum table size.
The newest LIVE checkpoint that references an entry used for encoding
is picked to record the stream ID.
This strategy is estimated to work well most of the time due to the
temporal aspect of the checkpoint dropping policy. When a connection
is used to serve a small number of requests, however, the compression
will be overall suboptimal, as the initial period when no dynamic
table is available for encoding is amortized poorly.
9.1.2. Rule-Based Strategy
Heuristic rules may provide performance improvement over the simple
strategy above. For example:
o Flush very often, perhaps once for every new stream, when the
number of dynamic entries is very small (such as when the encoder
has just been instantiated). Since the table size is likely to be
small when only few dynamic entries exist, one can fit a lot of
checkpoints and still be able to add new entries to the table.
These early-flushed checkpoints will also be easier to drop later,
as they are not referenced by many streams.
Tikhonov Expires May 17, 2018 [Page 13]
Internet-Draft QMIN: Header Compression for QUIC November 2017
o Flush when the number of newly added entries is 1/10 of the number
of existing entries. When this many new entries have been added,
it is a likely indicator making them available for encoding will
improve overall compression.
o When declaring a checkpoint DEAD:
* Pick a LIVE checkpoint that is referenced by the fewest
existing streams; or
* Pick a LIVE checkpoint that references the largest number of
old entries, where an "old" entry is that which has not been
used for encoding in a period of some number of checkpoints.
Other rules are possible.
9.1.3. Feedback-Based Strategy
The goal of QMIN is to produce the best compression. The compression
level can be computed by dividing the sum of the sizes of all header
fields submitted for compression by the number of compressed bytes
returned *plus* the size of all commands sent to the decoder. A
checkpoint can be taken as unit of time and a decaying average can be
computed.
Availability of entries that can be used for compression directly
affects compression performance. This availability, in turn, is a
function of how often checkpoints are flushed and which checkpoints
are marked for deletion. Flushing very often costs memory;
infrequent flushing delays entry availability.
It is possible to come up with a dynamic function that adjusts these
parameters based on feedback: the compression performance.
9.2. Control Channel Cost
Sending commands on the control channel affects the overall
compression level. Sending an INSERT_ENTRY command for a header
field that is never reused is more expensive than not inserting the
field at all. A single large, ever-changing HTTP header (for
example, session state in a cookie) could defeat the compression
mechanism. The encoder SHOULD prevent this from happening.
Since a header field that repeats is likely to repeat more than once,
a simple conservative approach is never to insert a header field that
is not known to have repeated. Because HTTP header names are
relatively small and not as numerous as the header values, it is
possible to maintain a history of a number of recently compressed
header fields. (To use less memory, hashes of header values, instead
of the values themselves, can be stored.) The encoder can consult
Tikhonov Expires May 17, 2018 [Page 14]
Internet-Draft QMIN: Header Compression for QUIC November 2017
this history and only issue an INSERT_ENTRY command if the header
field has been seen before.
10. HPACK Interoperability
Because QMIN uses the same binary format as HPACK, the two are
interoperable. This makes it possible for peers to use the current
HTTP/QUIC HPACK mechanism to talk to peers that use QMIN. It is
useful: all implementations do not have to start using QMIN at the
same time.
For this to work, four things must be true:
1. The HPACK side must advertise maximum dynamic table size of zero.
2. The HPACK side must not send dynamic table size updates.
3. The HPACK side must consume and discard data sent on the control
stream. This is so that QMIN sender does not get stuck when it
reaches the stream flow control limit.
4. The HPACK side must assume that peer's dynamic table size is
zero. This is to prevent HPACK encoder from relying on dynamic
entries.
(1) and (2) are already true according to [I-D.ietf-quic-http]. (3)
and (4) are trivial modifications.
11. Implementation Notes
11.1. Control Messages Made Easy
Since INSERT_ENTRY and REUSE_ENTRY messages are identical to the
encoded header field representation, the latter can be placed onto
the control stream verbatim. Generate once, use twice.
12. QMIN Drawbacks
The following QMIN properties affect compression negatively:
o All insertion commands are duplicated: they are sent both as
literal representation in headers block and as insertion commands
on the control stream.
o A new entry cannot be used until the checkpoint is flushed and the
encoder receives ACK_FLUSH message. Until that time, the header
field literal representation must be used for subsequent
encodings.
Tikhonov Expires May 17, 2018 [Page 15]
Internet-Draft QMIN: Header Compression for QUIC November 2017
13. Acknowledgements
QMIN is based on HPACK ([RFC7540]); I am thankful to its authors.
Observations of the following members of the IETF QUIC WG have been
particularly insightful:
o Alan Frindell;
o Charles 'Buck' Krasic; and
o Mike Bishop.
Finally, my colleagues at LiteSpeed Technologies reviewed the rough
draft and provided valuable feedback:
o George Wang;
o Ron Saad.
14. References
14.1. Normative References
[RFC7540] Belshe, M., Peon, R., and M. Thomson, Ed., "Hypertext
Transfer Protocol Version 2 (HTTP/2)", RFC 7540,
DOI 10.17487/RFC7540, May 2015,
<https://www.rfc-editor.org/info/rfc7540>.
[RFC7541] Peon, R. and H. Ruellan, "HPACK: Header Compression for
HTTP/2", RFC 7541, DOI 10.17487/RFC7541, May 2015,
<https://www.rfc-editor.org/info/rfc7541>.
14.2. Informative References
[I-D.ietf-quic-http]
Bishop, M., "Hypertext Transfer Protocol (HTTP) over
QUIC", draft-ietf-quic-http-07 (work in progress), October
2017.
Author's Address
Dmitri Tikhonov
LiteSpeed Technologies
Email: dtikhonov@litespeedtech.com
Tikhonov Expires May 17, 2018 [Page 16]
