Internet DRAFT - draft-ruellan-priority-tree-sync

draft-ruellan-priority-tree-sync







Network Working Group                                         H. Ruellan
Internet-Draft                                                 Y. Fablet
Intended status: Standards Track                           R. Bellessort
Expires: July 26, 2015                                         Canon CRF
                                                             J. Fujisawa
                                                             Canon, Inc.
                                                        January 22, 2015


                  HTTP/2 Priority Tree Synchronization
                  draft-ruellan-priority-tree-sync-01

Abstract

   This specification describes an issue in HTTP/2 linked to the
   synchronization of priority trees between a client and a server.  It
   outlines possible solutions to this issue.

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 26, 2015.

Copyright Notice

   Copyright (c) 2015 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




Ruellan, et al.           Expires July 26, 2015                 [Page 1]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


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

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Conventions . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Problem Overview  . . . . . . . . . . . . . . . . . . . . . .   3
     2.1.  HTTP/2 Priorities . . . . . . . . . . . . . . . . . . . .   3
     2.2.  Priority Usage  . . . . . . . . . . . . . . . . . . . . .   3
   3.  Priority Retention  . . . . . . . . . . . . . . . . . . . . .   5
     3.1.  Overview  . . . . . . . . . . . . . . . . . . . . . . . .   5
     3.2.  The PRIORITY_RETENTION Frame  . . . . . . . . . . . . . .   6
     3.3.  Evaluation  . . . . . . . . . . . . . . . . . . . . . . .   7
   4.  Priority Pruning Algorithm  . . . . . . . . . . . . . . . . .   7
     4.1.  Overview  . . . . . . . . . . . . . . . . . . . . . . . .   7
     4.2.  Algorithm . . . . . . . . . . . . . . . . . . . . . . . .   7
     4.3.  The SETTING_PRIORITY_STATES parameter . . . . . . . . . .   8
     4.4.  Evaluation  . . . . . . . . . . . . . . . . . . . . . . .   8
   5.  Server Feedback . . . . . . . . . . . . . . . . . . . . . . .   9
     5.1.  Overview  . . . . . . . . . . . . . . . . . . . . . . . .   9
     5.2.  The UNAPPLIED_PRIORITY Frame  . . . . . . . . . . . . . .   9
     5.3.  Evaluation  . . . . . . . . . . . . . . . . . . . . . . .   9
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .   9
   7.  Normative References  . . . . . . . . . . . . . . . . . . . .  10
   Appendix A.  Change Log (to be removed by RFC Editor before
                publication) . . . . . . . . . . . . . . . . . . . .  11

1.  Introduction

   HTTP/2 [HTTP2] allows multiplexing messages over a single connection.
   A client can express the processing order it expects from the server
   for its requests, by using HTTP/2 priority mechanism.  Using this
   mechanism, the client requests are organized in a priority tree.

   The priority tree evolves as new requests are sent by the client, and
   as older requests are fulfilled by the server.  Due to this dynamic
   nature, the client and the server can have different views of the
   priority tree.  A discrepancy can cause issues, mainly due to the
   removal of requests from the priority tree.

   Section 2 details this synchronization issue and its possible
   consequences.

   Section 3, Section 4, and Section 5 draw rough sketches of possible
   solutions to this synchronization issue.





Ruellan, et al.           Expires July 26, 2015                 [Page 2]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


1.1.  Conventions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].

   All numeric values are in network byte order.  Values are unsigned
   unless otherwise indicated.  Literal values are provided in decimal
   or hexadecimal as appropriate.  Hexadecimal literals are prefixed
   with "0x" to distinguish them from decimal literals.

2.  Problem Overview

2.1.  HTTP/2 Priorities

   HTTP/2 [HTTP2] allows multiplexing concurrent messages on the same
   connection.  Each message exchange is carried by a stream.  A client
   can express how it would prefer the server allocate resources for the
   concurrent streams, by using HTTP/2 priority mechanism (Section 5.3
   of [HTTP2]).

   Streams are organized into a priority tree by making each stream
   depend on another stream.  A stream is processed only when all its
   parents in the priority tree have been processed.

   Each stream is allocated a weight.  This weight is used to determine
   the relative share of resources that are allocated to streams
   depending on the same parent.

   A priority is set for a stream by defining its parent stream (i.e.,
   the stream it depends on), and its weight (a value between 1 and
   256).  By default, the priority for a stream is to depend on no
   stream, and to have a weight of 16.

   A client can define the priority for a stream when creating it.  It
   can later change this priority to reflect new expectations regarding
   the allocation of resources by the server.

2.2.  Priority Usage

   A server needs to control the amount of memory used by a HTTP/2
   connection.  To this end, it can limit the maximum number of
   simultaneous streams that a client is allowed to create.  It also
   needs to remove streams from the priority tree once they are closed.
   However, the client could rely on these closed streams to place new
   streams in the priority tree.  If the server receives a priority for
   a stream referencing a stream no longer in its priority tree, the




Ruellan, et al.           Expires July 26, 2015                 [Page 3]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


   default priority is assigned to the stream.  This can lead to
   suboptimal behaviour.

   For example, when downloading a web page, a client can prioritize the
   resources used by the page to optimize the download speed as
   perceived by the user.  To this end, the client organizes its
   priority tree to download less important resources after the more
   important ones.  The stream for a less important resource is
   prioritized as depending on a stream for a more important resource.
   If the server is not able to apply this priority, because it has not
   kept priority information for the latter stream, it will use a
   default priority for the less important resource.  As a result, this
   less important resource will be downloaded concurrently with much
   more important resource, and the downloading of the web page will not
   be optimized according to the client expectations.

   Another example is the downloading of two web pages in parallel, one
   in the foreground, the other in the background.  The client can
   prioritize the resources to ensure the web page in the foreground is
   downloaded faster that the web page in the background.  To be able to
   react to the user inverting the foreground and the background web
   pages, the client can organize the resources corresponding to each
   web page in a different branch of the priority tree.  By changing the
   weights of the root of each branch, the client can change the
   relative download speeds of the two pages.  However, if the server
   does not keep priority information for these roots, it will not be
   able to apply the weight changes sent by the client, and the client
   will not be able to change the relative download speed of the pages.

   As seen in these examples, not all streams are of the same importance
   to the client for defining new priorities.  As a general rule, recent
   streams are more useful to the client as it will use them to define
   the priorities of new streams.  However, there are two particular
   cases that can be used by the client to structure the priority tree.

   First, some streams are used as branching points in the priority
   tree.  A branching point has several children that are intended to be
   processed in parallel.  A branching point is useful to the client for
   adding further streams to be processed in parallel, alongside the
   existing children of the branching point.

   [[CREF1: Revise the figures to include Idle streams.]]









Ruellan, et al.           Expires July 26, 2015                 [Page 4]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


   For example, the following priority tree allows downloading the three
   images in parallel:

          index.html
               |
          script.js
               |
          layout.css
         /     |    \
        /      |     \
       /       |      \
    i1.png  i2.png  i3.png

                              Branching Point

   Second, some streams are at the root of priority tree branches.
   These streams are useful to the client for changing the general
   priority of a whole branch of the priority tree.

   For example, the following priority tree contains two branches, each
   corresponding to a web page:

       i1.html              i2.html
          |                    |
        s1.js                s2.js
          |                    |
        l1.css               l2.css
       /      \                |
    i1.png   i2.png          i3.jpg

                                Branch Root

3.  Priority Retention

3.1.  Overview

   The client can ask the server to keep the priority state for a stream
   for some time after the stream is closed.  A new frame
   PRIORITY_RETENTION (Section 3.2) is defined to allow this.

   This frame can also be used by the client to indicate that it no
   longer needs the server to keep the priority state corresponding to a
   stream.








Ruellan, et al.           Expires July 26, 2015                 [Page 5]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


3.2.  The PRIORITY_RETENTION Frame

   The PRIORITY_RETENTION HTTP/2 frame (Section 4 of [HTTP2]) allows an
   endpoint to transmit priority state retention information to its
   peer.

   The PRIORITY_RETENTION frame is a non-critical extension to HTTP/2.
   Endpoints that do not support this frame can safely ignore it.

   An endpoint willing to support receiving the PRIORITY_RETENTION frame
   from a peer can announce it by sending a PRIORITY_RETENTION frame on
   stream 0.

   The PRIORITY_RETENTION frame type is TBD.

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |       R     |F|
    +-------------+-+

                     PRIORITY_RETENTION frame PAYLOAD

   The PRIORITY_RETENTION frame contains the following fields:

   R: A reserved 7-bit field.

   F: A 1-bit field indicating the retention status of priority
      information for the stream.

      The value 1 means that the priority state for the stream is
      retained.

      The value 0 means that the priority state for the stream is not
      retained.

   The PRIORITY_RETENTION frame does not define any flags.

   An endpoint can request its peer to retain priority information for a
   stream by sending a PRIORITY_RETENTION frame with the F field set to
   the value of 1 on this stream.

   An endpoint can inform its peer that it no longer needs to retain
   priority information for a stream by sending a PRIORITY_RETENTION
   frame with the F field set to the value of 0 on this stream.

   [[CREF2: The detailed usage of the PRIORITY_RETENTION frame needs to
   be defined.]]



Ruellan, et al.           Expires July 26, 2015                 [Page 6]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


3.3.  Evaluation

   This extension enables the client to ask the server to retain some
   specific priority information.  As such, the client has a good
   control over the priority tree of the server and can use many
   possible strategies for organizing the shape of the priority tree.

   The client is however limited in that it can't ask the server to
   retain a too large number of streams, otherwise the memory
   consumption on the server side would be too large.

4.  Priority Pruning Algorithm

4.1.  Overview

   The server can use a well-defined algorithm for selecting which
   priority states to keep for closed streams, and which to delete from
   memory.  The client can replicate this algorithm to know on which
   streams to rely for defining new priorities.

   The algorithm defines the number of priority states kept by the
   server.  By default, it is the same number as the maximum number of
   streams the client can open.  This can be changed through a new
   setting parameter, SETTING_PRIORITY_STATES (Section 4.3).

   The priority states are by default deleted in the stream creation
   order.  However, this order is modified to keep longer two types of
   streams:

   o  Streams that are branching points in the priority tree: those that
      have several child streams.  These streams are useful to define
      parallel processing.

   o  Streams that are at the root of a branch of the priority tree.
      These streams are useful for changing priorities on a large scale.

4.2.  Algorithm

   To select the priority states to keep for closed streams, the server
   applies the following algorithm:

   1.  The server creates a list containing all the closed streams and
       orders it according to the stream creation order.  The oldest
       stream is the first in the list, while the newest one is the
       last.

   2.  Each closed stream that has at least two children is moved after
       the latest of its child present in the list.



Ruellan, et al.           Expires July 26, 2015                 [Page 7]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


   3.  Each closed stream that depends on no other stream and that has
       at least one descendant is moved after the latest of its
       descendant in the list.

   4.  Priority states are kept only for the streams at the end of the
       list, such that the number of kept priority states is lower than
       or equal to the value of the SETTING_PRIORITY_STATES
       (Section 4.3) parameter.

4.3.  The SETTING_PRIORITY_STATES parameter

   The SETTING_PRIORITY_STATES SETTINGS parameter (Section 6.5.2 of
   [HTTP2]) indicates the number of priority states kept for closed
   streams by the endpoint.

   This parameter identifier is TBD.

   The initial value for this parameter is 100.  It is recommended that
   the value for this parameter be at least the same as the value of the
   SETTING_MAX_CONCURRENT_STREAMS parameter.

   The usage of this new setting parameter doesn't require any
   negotiation between peers.  Upon sending this setting parameter, an
   endpoint informs its peer that it uses the pruning algorithm
   described above (Section 4.2) for selecting for which closed streams
   priority states are kept.

   A peer receiving this setting parameter and understanding it can
   choose to take advantage of it to compute the priority state
   information kept by the sending endpoint.

   [[CREF3: The detailed usage of the SETTING_MAX_CONCURRENT_STREAMS
   parameter needs to be defined.]]

4.4.  Evaluation

   This extension enables the client to have a good knowledge of the
   closed streams for which priority information is kept by the server.
   Using this information, the client can define priorities knowing
   reliably that the server will be able to apply them.

   However, this extension is based on assumptions on which streams are
   the most useful to the client for defining priorities.  If these
   assumptions don't hold, then the client may not be able to fully
   express its expectations for the processing order of its requests by
   the server.





Ruellan, et al.           Expires July 26, 2015                 [Page 8]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


5.  Server Feedback

5.1.  Overview

   When the server is not able to apply a priority sent by the client,
   it fails silently.  To mitigate the consequences of this failure, the
   server could send feedback to the client.

   A new frame UNAPPLIED_PRIORITY (Section 5.2) is defined to allow the
   server to inform the client that a priority has not been applied.

5.2.  The UNAPPLIED_PRIORITY Frame

   The UNAPPLIED_PRIORITY HTTP/2 frame (Section 4 of [HTTP2]) allows an
   endpoint to inform its peer that the priority it received was not
   applied.  The UNAPPLIED_PRIORITY frame is sent on the stream for
   which the priority was not applied.

   The UNAPPLIED_PRIORITY frame is a non-critical extension to HTTP/2.
   Endpoints that do not support this frame can safely ignore it.

   The UNAPPLIED_PRIORITY frame type is TBD.

   The UNAPPLIED_PRIORITY frame has no payload.

   The UNAPPLIED_PRIORITY frame does not define any flags.

   [[CREF4: The detailed usage of the UNAPPLIED_PRIORITY frame needs to
   be defined.]]

5.3.  Evaluation

   This extension provides a lightweight way for the server to inform
   the client when it cannot apply a priority sent for a stream.

   While this feedback enables the client to know that a priority has
   not been applied by the server, it provides little information on how
   to change the priority in order for the server to able to apply it.

6.  Security Considerations

   The different extensions proposed in this specification introduce new
   HTTP/2 setting parameters, or new HTTP/2 frames that could be abused
   in the same way as existing setting parameters and frames.

   The PRIORITY_RETENTION (Section 3.2) frame can be abused to cause a
   peer to retain a large amount of priority state by sending only
   priority retention requests.



Ruellan, et al.           Expires July 26, 2015                 [Page 9]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


7.  Normative References

   [HTTP2]    Belshe, M., Peon, R., and M. Thomson, Ed., "Hypertext
              Transfer Protocol version 2", draft-ietf-httpbis-http2-13
              (work in progress), June 2014.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.











































Ruellan, et al.           Expires July 26, 2015                [Page 10]

Internet-Draft    HTTP/2 Priority Tree Synchronization      January 2015


Appendix A.  Change Log (to be removed by RFC Editor before publication)

Authors' Addresses

   Herve Ruellan
   Canon CRF

   EMail: herve.ruellan@crf.canon.fr


   Youenn Fablet
   Canon CRF

   EMail: youenn.fablet@crf.canon.fr


   Romain Bellessort
   Canon CRF

   EMail: romain.bellessort@crf.canon.fr


   Jun Fujisawa
   Canon, Inc.

   EMail: fujisawa.jun@canon.co.jp

























Ruellan, et al.           Expires July 26, 2015                [Page 11]