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]
