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

QUIC Working Group                                             M. Bishop
Internet-Draft                                                 Microsoft
Intended status: Standards Track                        January 17, 2017
Expires: July 21, 2017

                    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

Bishop                    Expires July 21, 2017                 [Page 1]
Internet-Draft                    QPACK                     January 2017

   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

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

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

Bishop                    Expires July 21, 2017                 [Page 2]
Internet-Draft                    QPACK                     January 2017

   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.

Bishop                    Expires July 21, 2017                 [Page 3]
Internet-Draft                    QPACK                     January 2017

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:

   o  Insertions to the field, both the initial and any redundant
      indexed literal emissions.

   o  Literal values which use the indexed entry to provide the header
      name

   o  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

Bishop                    Expires July 21, 2017                 [Page 4]
Internet-Draft                    QPACK                     January 2017

   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.

Bishop                    Expires July 21, 2017                 [Page 5]
Internet-Draft                    QPACK                     January 2017

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

Bishop                    Expires July 21, 2017                 [Page 6]
Internet-Draft                    QPACK                     January 2017

   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.

Bishop                    Expires July 21, 2017                 [Page 7]
Internet-Draft                    QPACK                     January 2017

   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:

   o  The Sequence field is removed from HEADERS frames (Section 5.2.2)
      and PUSH_PROMISE frames (Section 5.2.6).

   o  Header Block Fragments consist of QPACK data instead of HPACK
      data.

   o  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.

Bishop                    Expires July 21, 2017                 [Page 8]
Internet-Draft                    QPACK                     January 2017

   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:

   o  Jana Iyengar

   o  Patrick McManus

   o  Martin Thomson

   o  Charles 'Buck' Krasic

   o  Kyle Rose

8.  Normative References

   [I-D.ietf-quic-http]
              Bishop, M., "Hypertext Transfer Protocol (HTTP) over
              QUIC", draft-ietf-quic-http-01 (work in progress), January
              2017.

   [I-D.ietf-quic-transport]
              Iyengar, J. and M. Thomson, "QUIC: A UDP-Based Multiplexed
              and Secure Transport", draft-ietf-quic-transport-01 (work
              in progress), January 2017.

Bishop                    Expires July 21, 2017                 [Page 9]
Internet-Draft                    QPACK                     January 2017

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>.

   [RFC7230]  Fielding, R., Ed. and J. Reschke, Ed., "Hypertext Transfer
              Protocol (HTTP/1.1): Message Syntax and Routing",
              RFC 7230, DOI 10.17487/RFC7230, June 2014,
              <http://www.rfc-editor.org/info/rfc7230>.

   [RFC7231]  Fielding, R., Ed. and J. Reschke, Ed., "Hypertext Transfer
              Protocol (HTTP/1.1): Semantics and Content", RFC 7231,
              DOI 10.17487/RFC7231, June 2014,
              <http://www.rfc-editor.org/info/rfc7231>.

   [RFC7540]  Belshe, M., Peon, R., and M. Thomson, Ed., "Hypertext
              Transfer Protocol Version 2 (HTTP/2)", RFC 7540,
              DOI 10.17487/RFC7540, May 2015,
              <http://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,
              <http://www.rfc-editor.org/info/rfc7541>.

Author's Address

   Mike Bishop
   Microsoft

   Email: michael.bishop@microsoft.com

Bishop                    Expires July 21, 2017                [Page 10]