Priority Placeholders in HTTP/2
draft-bishop-httpbis-priority-placeholder-00

HTTPbis                                                        M. Bishop
Internet-Draft                                                 Microsoft
Intended status: Standards Track                           July 25, 2017
Expires: January 26, 2018

                    Priority Placeholders in HTTP/2
              draft-bishop-httpbis-priority-placeholder-00

Abstract

   [RFC7540] defines HTTP/2, including a method for communicating
   priorities.  Some implementations have begun using closed streams as
   placeholders when constructing their priority tree, but this has
   unbounded state commitments and interacts poorly with HTTP/QUIC
   ([I-D.ietf-quic-http]).  This document proposes an extension to the
   HTTP/2 priority scheme for both protocols.

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 January 26, 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
   (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 January 26, 2018                [Page 1]
Internet-Draft           Placeholders in HTTP/2                July 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.  Notational Conventions  . . . . . . . . . . . . . . . . .   3
   2.  The Priority Placeholder Extension  . . . . . . . . . . . . .   3
     2.1.  Priority Placeholder Setting  . . . . . . . . . . . . . .   3
       2.1.1.  Mid-session updates . . . . . . . . . . . . . . . . .   3
     2.2.  Frame Modifications . . . . . . . . . . . . . . . . . . .   3
       2.2.1.  Existing Frame Types  . . . . . . . . . . . . . . . .   4
       2.2.2.  PLACEHOLDER_PRIORITY Frame  . . . . . . . . . . . . .   4
     2.3.  Priority Management Logic . . . . . . . . . . . . . . . .   5
   3.  Security Considerations . . . . . . . . . . . . . . . . . . .   6
   4.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   6
     4.1.  SETTINGS_PLACEHOLDERS Setting . . . . . . . . . . . . . .   6
     4.2.  PLACEHOLDER_PRIORITY Frame  . . . . . . . . . . . . . . .   6
   5.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   7
     5.1.  Normative References  . . . . . . . . . . . . . . . . . .   7
     5.2.  Informative References  . . . . . . . . . . . . . . . . .   7
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .   7

1.  Introduction

   Stream Priority is described in [RFC7540], Section 5.3.  Priority is
   communicated using PRIORITY frames and with reference to other
   streams, with stream 0 being the root of the tree.  Each stream
   depends on one other stream with a particular weight; these weights
   represent relative priorities among the multiple children of a
   stream.

   Unfortunately, the scheme as specified encourages servers to actively
   maintain closed streams in the priority tree, since other streams
   might reference them later.  This produces an unbounded state
   commitment on the part of the server if it is to correctly reflect
   any possible reference the client might make.  While priorities are
   only advisory and the server is free to discard as much state as it
   needs to, references to streams which are no longer in the server's
   state are treated as references to the root of the tree.  This can
   result in wildly different conceptions of the priority tree between
   client and server, a situation which all parties would prefer to
   avoid.

Bishop                  Expires January 26, 2018                [Page 2]
Internet-Draft           Placeholders in HTTP/2                July 2017

1.1.  Notational Conventions

   The words "MUST", "MUST NOT", "SHOULD", and "MAY" are used in this
   document.  It's not shouting; when they are capitalized, they have
   the special meaning defined in [RFC2119].

2.  The Priority Placeholder Extension

   This extension consists of an additional setting Section 2.1, changes
   to the set of HTTP/2 frames Section 2.2, and modified state
   management logic on the server Section 2.3.

2.1.  Priority Placeholder Setting

   An HTTP/2 peer that supports Priority Placeholders indicates this
   using the HTTP/2 "SETTINGS_PLACEHOLDERS" (0xSETTING-TBD) setting.

   When a value for the "SETTINGS_PLACEHOLDERS" setting is not set, this
   indicates that the peer does not support the extension, and other
   protocol elements in this document MUST NOT be used.  A client that
   supports this extension SHOULD set this value to 0 (0x00).

   A server which supports this extension MUST set this value to a non-
   zero number indicating the number of placeholders it is willing to
   make available to the client, which MUST be at most 2^31-1.  Clients
   MUST NOT use the protocol elements in this document unless the server
   has indicated support by setting a non-zero value.

2.1.1.  Mid-session updates

   HTTP/2 permits settings to change during the course of a connection.
   This setting can be freely increased at any time without consequence,
   and servers SHOULD NOT reduce the value during the lifetime of a
   connection.

   If a client receives a reduction in the number of permitted
   placeholders, it MUST assume that all placeholders over the new limit
   have been pruned from the tree and SHOULD immediately issue PRIORITY
   and PLACEHOLDER_PRIORITY frames as necessary to rebuild the priority
   tree as desired.  Once the SETTINGS frame has been acknowledged,
   servers should treat the excess placeholders as inactive and prune
   them following the same logic in Section 2.3.

2.2.  Frame Modifications

Bishop                  Expires January 26, 2018                [Page 3]
Internet-Draft           Placeholders in HTTP/2                July 2017

2.2.1.  Existing Frame Types

   When client and server have opted in to this extension, the HTTP/2
   PRIORITY frame and HEADERS frame contain one additional flag:

   DEPENDENT_ON_PLACEHOLDER (0x2):  When set, bit 1 indicates that the
      value in the Stream Dependency field is a Placeholder ID rather
      than a Stream ID.

   In HEADERS, this flag MUST NOT be set if the PRIORITY flag is not
   set.

2.2.2.  PLACEHOLDER_PRIORITY Frame

   The PLACEHOLDER_PRIORITY (type=0xFRAME-TBD) frame specifies the
   sender-advised priority of a placeholder.  It MUST be sent only on
   Stream 0.  The semantics of the Stream Dependency, Weight, and E flag
   are the same as in the HTTP/2 PRIORITY frame.

   The flags defined are:

   E (0x01):  Indicates that the stream dependency is exclusive (see
      [RFC7540], Section 5.3).

   DEPENDENT_ON_PLACEHOLDER (0x2):  When set, bit 1 indicates that the
      value in the Stream Dependency field is a Placeholder ID rather
      than a Stream ID.

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |0|                    Placeholder ID (31)                      |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |0|                  Stream Dependency (31)                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |   Weight (8)  |
      +-+-+-+-+-+-+-+-+

                     Figure 1: PRIORITY frame payload

   The PLACEHOLDER_PRIORITY frame payload has the following fields:

   Prioritized Stream:  A 31-bit stream identifier for the request
      stream whose priority is being updated.

   Stream Dependency:  A 31-bit stream or placeholder identifier for the
      request stream that this stream depends on (see [RFC7540],
      Section 5.3).

Bishop                  Expires January 26, 2018                [Page 4]
Internet-Draft           Placeholders in HTTP/2                July 2017

   Weight:  An unsigned 8-bit integer representing a priority weight for
      the stream (see [RFC7540], Section 5.3).  Add one to the value to
      obtain a weight between 1 and 256.

   A PLACEHOLDER_PRIORITY frame MUST have a payload length of nine
   octets.  A PLACEHOLDER_PRIORITY frame of any other length MUST be
   treated as a connection error of type PROTOCOL_ERROR if the sender
   has advertised support for this extension, and ignored otherwise.

2.3.  Priority Management Logic

   This extension provides a mechanism for servers to limit how many
   additional IDs which do not refer to an active request will be used
   to maintain priority state.  Because the server commits to maintain
   these inactive IDs, clients can use them with confidence that the
   server will not have discarded the state without warning.

   In exchange, the server knows it can aggressively prune inactive
   regions from the priority tree, because placeholders will be used to
   "root" any persistent structure of the tree which the client cares
   about retaining.  For prioritization purposes, a node in the tree is
   considered "inactive" when the corresponding stream has been closed
   for at least two round-trip times (using any reasonable estimate
   available on the server).  This delay helps mitigate race conditions
   where the server has pruned a node the client believed was still
   active and used as a Stream Dependency.

   Specifically, the server MAY at any time:

   o  Identify and discard branches of the tree containing only inactive
      nodes (i.e. a node with only other inactive nodes as descendants,
      along with those descendants)

   o  Identify and condense interior regions of the tree containing only
      inactive nodes, allocating weight appropriately

       x                x                 x
       |                |                 |
       P                P                 P
      / \               |                 |
     I   I     ==>      I      ==>        A
        / \             |                 |
       A   I            A                 A
       |                |
       A                A

                Figure 2: Example of Priority Tree Pruning

Bishop                  Expires January 26, 2018                [Page 5]
Internet-Draft           Placeholders in HTTP/2                July 2017

   In the example in Figure 2, "P" represents a Placeholder, "A"
   represents an active node, and "I" represents an inactive node.  In
   the first step, the server discards two inactive branches (each a
   single node).  In the second step, the server condenses an interior
   inactive node.  Note that these transformations will result in no
   change in the resources allocated to a particular active stream.

   Clients MUST assume the server is actively performing such pruning
   and MUST NOT declare a dependency on a stream it knows to have been
   closed.

3.  Security Considerations

   This extension is believed to improve security relative to [RFC7540],
   as it helps to constrain a previously unbounded state commitment.

4.  IANA Considerations

   This document registers one new frame type and one new setting.

4.1.  SETTINGS_PLACEHOLDERS Setting

   The "SETTINGS_PLACEHOLDERS" setting is registered in the "HTTP/2
   Settings" registry established in [RFC7540].

   Name:  SETTINGS_PLACEHOLDERS

   Code:  0xSETTING-TBD

   Initial Value:  not set

   Specification:  This document.

4.2.  PLACEHOLDER_PRIORITY Frame

   The "PLACEHOLDER_PRIORITY" frame is registered in the "HTTP/2 Frames"
   registry established in [RFC7540].

   Name:  PLACEHOLDER_PRIORITY

   Code:  0xFRAME-TBD

   Specification:  This document.

Bishop                  Expires January 26, 2018                [Page 6]
Internet-Draft           Placeholders in HTTP/2                July 2017

5.  References

5.1.  Normative References

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

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

5.2.  Informative References

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

Author's Address

   Mike Bishop
   Microsoft

   Email: michael.bishop@microsoft.com

Bishop                  Expires January 26, 2018                [Page 7]