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

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

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 January 22, 2015.

Copyright Notice

Copyright (c) 2014 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 the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.


Table of Contents

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

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 allocates resources for the concurrent streams by using HTTP/2 priority mechanism ([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 add new streams into the priority tree. If the server receives a priority for a stream referencing a stream no longer in its priority tree, the 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 the more important one, 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. 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. In addition, 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.

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 global 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. Server Feedback

3.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 [unapplied.priority.frame] is defined to allow the server to inform the client that a priority has not been applied.

3.2. The UNAPPLIED_PRIORITY Frame

The UNAPPLIED_PRIORITY HTTP/2 frame ([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.

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

3.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 be able to apply it.

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 [setting.priority.states].

[CREF2]The SETTING_PRIORITY_STATES setting parameter could be removed if the benefits it brings are not sufficient compared to its complexity.

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

4.2. Algorithm

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

    4.3. The SETTING_PRIORITY_STATES parameter

    The SETTING_PRIORITY_STATES SETTINGS parameter ([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 knowledge, 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.

    5. Priority Retention

    5.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 [priority.retention.frame] 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.

    5.2. The PRIORITY_RETENTION Frame

    The PRIORITY_RETENTION HTTP/2 frame ([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:

    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.

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

    5.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 priority tree.

    The client has to use strategies relying on a reasonable amount of retained stream priority states by the server, otherwise the memory consumption on the server side would be too large.

    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 [priority.retention.frame] frame can be abused to cause a peer to retain an undue amount of priority state by sending a large number of priority retention requests.

    7. Normative References

    [HTTP2] Belshe, M., Peon, R. and M. Thomson, "Hypertext Transfer Protocol version 2", Internet-Draft draft-ietf-httpbis-http2-13, June 2014.
    [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

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

    Authors' Addresses

    Hervé 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