W3C home > Mailing lists > Public > ietf-http-wg@w3.org > October to December 2013

Re: Restarting the discussion on HTTP/2 stream priorities

From: 陈智昌 <willchan@chromium.org>
Date: Mon, 28 Oct 2013 15:45:31 -0700
Message-ID: <CAA4WUYhhc68fBM5f3OqLynY71prQ9MSP3GRcX4r5wE1SdaRJvQ@mail.gmail.com>
To: Martin Thomson <martin.thomson@gmail.com>
Cc: HTTP Working Group <ietf-http-wg@w3.org>
On Mon, Oct 28, 2013 at 3:34 PM, Martin Thomson <martin.thomson@gmail.com>wrote:

> On 28 October 2013 14:32, William Chan (陈智昌) <willchan@chromium.org>
> wrote:
> > I think that the second point is far more controversial and requires more
> > discussion.
> It may be the case that you find the first issue compelling enough
> that a change of some form is justified regardless of what you think
> on the second :)
> Of course, I think that there are some significant problems with the
> proposal, most of which I think that you will find are easy to fix.
> The first is largely procedural.  I've have people complain about the
> use of references to documents like the above for archival and IPR
> reasons.  Maybe copying and pasting the entirety of that document to
> an email will address those concerns.  Maybe it will also help you
> understand that it is a little wordy and that perhaps the essence of
> your proposal could be made more succinctly :)

I have to confess that I heard complaints but never understood the
reasoning behind them. If it's archival/IPR, I'm perfectly happy to
copy/paste the document into email. These concerns aren't obvious to me as
I'm a relative newb to IETF stuff.

As far as the proposal's wordiness, I mostly view it as a straw man to
ignite discussion. I'm completely expecting that it will be ripped apart :)
I'm hoping to rely heavily on editors to make it much more succinct once we
reach some rough consensus. Or perhaps this was a subtle play on your part
to get me to do better editorial work before sending it to the group :)

I'll give others a chance to discuss other points first. I don't want to
yell more loudly than others anymore than I already do.

> The second is that the idea of prioritization between separate trees
> isn't really described as being prioritization.  I think that what you
> want to do is a proportional allocation of resources between those
> trees, so a term like "weight" is probably more accurate.  You even
> use that word later.  (Oh crap, I just realized that this is a classic
> case of "the names aren't important, the standards committee always
> changes them anyway" scenario, sorry.)
> Probably more substantially, you need to be a little more concrete
> when it comes to requirements for managing placeholders and garbage
> collection.
> The settings seem like over-engineering to me.  I'm sure that a server
> implementation can arrive at a reasonable set of behaviours that
> doesn't degrade too badly for their common workloads without settings
> being exchanged.  When it comes to resource exhaustion, I think that
> it's probably more appropriate to deal with those in the DoS
> considerations than with settings.
> On the over-engineering theme, the idea that you can reprioritize
> multiple streams with a single PRIORITY frame concerns me.  That's
> going to mess with intermediaries of all sorts.  The cost of a
> PRIORITY frame for each stream is 4 bytes per stream, but then you
> weren't going to bother with that anyway.
> Please consider placing default values on priority.  Since you are
> only going to be able to provide either a dependency or a weight, the
> complementary item is going to inherit a default.

I'm copy/pasting the doc here:
Proposal for Stream Dependencies in SPDY

Draft 1
Last Updated: 26 October 2012

This document proposes changes to the SPDY protocol to support stream
dependencies. During a pageload, the server uses dependencies to improve
performance by allocating bandwidth capacity to the most important resource
transfers first.

The remainder of this document describes the
dependencies, protocol
support them, and
how those mechanisms can be used by the browser. We conclude with a
discussion of the client and server
by expressing dependency information in SPDY.

(Note that flow control is the subject of a separate document and is out of
scope here.)

In SPDY today, each stream has a priority (0–7) chosen by the client upon
stream creation. Push streams are

an exception. The server policy today is to assume push streams are all low
priority. Push or pull, the priority of a stream cannot be changed once

Priorities provide hints to the server about which streams are most
important to the client, but they are poorly suited to several common


   Specifying an ordering of resource transfers
   Sharing bandwidth between resource transfers may degrade performance as
   measured by page-load time, e.g., when transferring two Javascript
   resources that cannot be executed until transfer is complete, or two video
   chunks that will be played back-to-back. In these circumstances, the
   browser may wish to specify an ordering --- HTML before script1.js before
   script2.js before image.png, for example, or video_chunk1 before
   video_chunk2 and so on. (Moreover, changing the priority of the HTML
   transfer itself may benefit performance; e.g., a large blocking script will
   be interpreted and executed more quickly if it does not compete for
   bandwidth capacity with a large HTML transfer.)

   With a small number of fixed priorities, the browser is simply unable to
   express an ordering over many resource transfers, and with a large number
   of priorities, reordering is costly.

   Reacting to document parsing
   Because the browser's document parser blocks while waiting for script
   and style resource transfers to complete, many resource requests will be
   speculative. (For more background, see Tony Gentilcore's excellent
   summary <http://gent.ilcore.com/2011/01/webkit-preloadscanner.html> of
   Chrome's implementation of speculative parsing, the preload scanner.) These
   requests may need to be preempted as the document parser learns of higher
   priority resources. For example, if a script a.js uses document.write to
   embed another script, b.js, the transfer of b.js should preempt other
   in-flight resource transfers, as the receipt of b.js blocks page layout.
   As another example, consider images styled with display: none; once such
   styling is discovered during parsing, associated image transfers should be
   deferred to prioritize visible content.

   Reacting to user behavior
   Suppose a SPDY proxy is servicing multiple users. In this case, many
   tabs (and their associated streams) are multiplexed over the same SPDY
   connection. Fixed priorities (i.e., unchanging over the lifetime of a
   stream) preclude reacting to user behavior; e.g., a user may switch among
   concurrently loading tabs.

   Server push
   No single fixed priority is appropriate for server push. A stream
   pushing a large image, for example, should have lower priority than JS/CSS.
   But, when pushing JS/CSS that the browser needs, those stream should have
   high priority.

In sum, for many common scenarios, fixed priorities are not sufficient to
optimize the allocation of bandwidth among competing requests.

Protocol changes

To address the limitations of priorities, we propose
expressingdependencies among streams.
Dependencies improve matters in two main ways:


   Dependencies more accurately reflect the constraints of the browser.
   Rendering a page is a streaming process that naturally leads to a series
   of dependencies among resource transfers. For example, a script may block
   HTML parsing, and a final layout may depend on an external stylesheet.

   Dependencies can be updated efficiently.
   The relative importance of streams may change as Javascript executes or
   a user changes tabs, for example. Dependencies allow the browser to express
   these changes compactly. If a user changes tabs, for example, the browser
   may simply signal a change in priority of the tab's dependency root,
   thereby reducing (or increasing) the bandwidth allocated to all dependent

Dependencies are expressed in two ways: 1) a new dependency field in the
SYN_STREAM message, and 2) a new REPRI message that updates the dependency
pointers of existing streams. To allow servers to advertise their support
for scheduling transfers based on dependencies, we propose a new
SETTINGSid/value pair. We describe the layout and semantics of each in

Note that these protocol changes are defined in terms of the latest version
of the SPDY draft


   0        1        2        3         4        5        6        7


| Length(16)      |Flags(8)|1| Stream Id(31)                    |    0x1 |


   8        9        10        11     12,13,14..N


|P| PriOrDep(31)                     | Name/Value Header Block |


Here, the first 8 bytes are the standard control frame header
A new 32 bit field replaces the existing SYN_STREAM priority bits


   P: A bit indicating whether the following PriOrDep bits specify a
   priority (P = 1) or a stream ID (P = 0) on which this new stream depends.

   PriOrDep: Depending on the value of P, either the priority of the new
   stream or a stream ID on which this new stream depends.

   The structure and semantics of the Name/Value header block
   are unchanged.

P is exclusive; a stream may be assigned a priority or a parent dependency
upon creation, but not both. There are no constraints of the value of
PriOrDep; any 31 bit value is valid. Thus, a stream may refer to a
dependency identifier that does not correspond to any current or previous
stream ID. This is a deliberate design choice that increases flexibility
for clients when structuring dependencies, a topic we expand upon in
the policies

Server push streams are assigned an initial parent at the discretion of the
server. A conformant implementation SHOULD create a dependency on the push
stream's associated-to-stream-id


   0        1        2        3         4        5        6        7


| Length(16)      |Flags(8)|1| Dependency Id(31)                |    0xc |


   8        9        10        11


|P| PriOrDep(31)                     | optionally followed by:


DependencyPriOrDep pairs, where a DependencyPriOrDep pair is:


|X| Dependency Id (31)               |P| PriOrDep(31)                     |


As in SYN_STREAM, the control frame header is standard, followed by a
P/PriOrDep label indicating an update to the 31 bit Dependency Id specified
in the header. We relabel the typical Stream Id here as Dependency Id since
a dependency need not correspond to an actual stream. (Recall that any 31
bit value is a valid dependency identifier.)

To support batched updates of dependencies, an optional list of
DependencyPriOrDep pairs with identical semantics may follow. The number of
such pairs is determined by examining the frame length.

number-of-pairs = ((length - 12) / 8). (12 required bytes, 8 bytes from len(
stream_id) + len(PriOrDep))

We expect most streams to have at most a single dependency, but this is not
a protocol requirement. (Later, we describe scenarios where multiple
parents may improve efficiency.) If a stream is referenced more than once
in a single frame, this indicates multiple parents. A server implementation
which does not support multiple parents MUST use the last referenced
parent. Clients which send multiple parents thus SHOULD put the most
important parent last.


Recall that dependencies and priorities are advisory. While servers must
accept the messages, they are not required to incorporate them into
scheduling decisions. A client may benefit from knowing a server's level of
support; e.g., a client may specify priorities only if it knows a server
will ignore dependencies. To communicate this, we propose a new
SETTINGSID/value pair (


   server to indicate resource limits for dependency scheduling, e.g., to
   limit memory consumption. A value of 0 indicates that the server does not
   support dependency scheduling. (We expect most implementations will select
   a value greater than or equal to MAX_CONCURRENT_STREAMS.)

   the server will maintain dependency nodes after creation. The value is an
   interval in milliseconds. This allows the client to estimate if previously
   created dependency relationships are still available for reference at the
   server. (We expect conformant implementations to maintain dependencies for
   at least as long as associated streams are active, although this is not a
   correctness requirement.)

Both of these values are advisory. Servers need not abide by their stated
values and clients may disregard them. Conformant clients should respect
the concurrency limit, but servers must be robust to a client that exceeds
it. Similarly, servers may drop dependency information at any time
regardless of previous statements made in SETTINGS. This is intended to
provide flexibility for service policies; e.g., a server may reduce the
timeout in response to memory pressure or abandon dependency scheduling

Examples / use-cases revisited

The combination of dependencies and priorities suffices to express
serialized as well as concurrent transfer schedules. (Both are necessary,
as we describe below.) But, how should the browser choose dependencies and
priorities when making requests? This question is best answered
quantitatively, but as a starting point, we consider the following policy
in our examples:


   Resource dependencies are (re)configured to reflect parser-blocking
   order. The transfer of non-streaming resources is always serialized; i.e.,
   non-async scripts and styling.

   Resources that can be progressively rendered (e.g., images) are
   transferred concurrently and (re)configured to depend on parser-blocking
   resource transfers.

   To ensure that the speculative parser can maintain enough in-flight
   requests to fill pipe between the client and server, page HTML is always a
   top-level dependency, although it may have lower priority than a resource
   transfer currently blocking document parsing.

When scheduling transfers, we consider a server that allocates
bandwidth hierarchically
within dependency trees and splits equally among streams with the same

Concretely, suppose a SPDY connection is multiplexing multiple tabs from a
user connected to a SPDY proxy, with parent pointers and priorities as
shown below. (P6, for example, indicates a priority of 6.)

To color in this example, suppose that Tab 1 is the foreground tab, loading
in parallel with Tab 2 in the background. Thus, its relatively higher
weight. a.js and b.js are scripts required for the first tab and should be
transferred serially (as scripts are executed in the order they are
declared in the document, and are not parsed until transfer completes.)
Thus, a.js depends on b.js depends on tab1.htm. In the background tab, two
image transfers share capacity as both can be rendered progressively. Both
image transfers have the same parent and hence transfer concurrently.

Because the streams associated with the transfers of tab1 and tab2 have no
parent, they are always scheduled before any lower level in their trees.
But, bandwidth allocation among trees remains proportional as defined by
the relative priority of roots. For example, if the transfer of tab2.htm is
in progress and tab1.htm (now complete) is selected, a.js will be scheduled
before tab2.htm completes. This process proceeds until all transfers in a
tree have completed.

As a practical matter, the timeout for pruning nodes in a tree should be
selected to allow transfers to complete and to allow clients to name
currently completed parents when defining transfer dependencies.
Concretely, on a high delay path, a small HTML transfer may be flushed
entirely by the server before the client receives any data and begins
making dependent requests for resources embedded in the page.

With these client and server policies in mind, we revisit the motivating
use-cases described above in greater detail.

- Specifying an ordering of resource transfers
- Reacting to document parsing

We illustrate the need for both serial dependencies, concurrency, and
reprioritization in these cases with a simple example.

Suppose site.com has index.htm:

<script src="a.js"></script>
<img src="a.jpg" width="100" height="100"/>
<img src="b.jpg" width="100" height="100"/>
<link rel="stylesheet" type="text/css" href="style.css">

with a.js:

document.write('<script src="b.js"></script>');



and style.css:

div {
 border: 1px solid #000;

How would this example page be transferred today? As the main HTML is
received and parsed, a request for a.js will be issued and block the
document parser. As the remaining HTML streams in, the speculative parser
will issue requests for a.jpg, b.jpg, and style.css in quick succession.
Once a.js is received and executed, a request for b.js will be issued,
which again blocks parsing until received. Visually:

This transfer schedule is suboptimal. Page rendering will complete only
when style.css and b.js have completed, but receiving each of those
critical resources is slowed by competition for bandwidth capacity with
bulk data that's not on the critical path (a.jpg and b.jpg).

What we would like is serialized transfer that reflects the document parse
order with concurrency for nonblocking, streaming resources. More
specifically, we want to receive: 1) index.html, 2) a.js, 3) b.js, and 4)
style.css serialized (i.e., with no deliberate sharing of capacity among
the ordered transfers). After those critical transfers have completed,
a.jpg and b.jpg should be transferred concurrently (as they may be
displayed progressively.)

Folding in the protocol mechanisms described above:

In the figure, each resource request corresponds to a new SPDY stream with
the form ID: reqest (PriOrDep). In more detail:


   The SYN_STREAM for the index.htm request has a parent indicating a
   default priority (3) and a stream id of 1.

   The document parser is blocked once the external script a.js is parsed.
   At this point, the speculative  parser looks ahead and creates new streams
   for a.jpg, b.jpg in parse order. a.jpg and b.jpg can be progressively
   rendered, so their transfer is concurrent (same parent, 2, corresponding to

   When the parser encounters style.css, back-to-back control messages are
   sent to create the stream and update the dependencies of the image
   transfers. Since stylesheets block rendering and cannot be streamed, the
   image transfers are updated to depend on style.css (P5).

   Once a.js completes, the document parser continues, executing a.js and
   inserting b.js via document.write(), again blocking document parsing on
   the receipt of b.js. At this point, b.js should preempt all other transfers
   since it's a non-streaming resource that is blocking page rendering. To
   this end, the client creates the b.js stream with a.js as its parent (or,
   equivalently, index.htm). Batched with this SYN_STREAM is another
REPRImessage rewiring style.css to depend on b.js. This serializes the
   (modulo the delay associated with message propagation and any transfer
   buffering delay at the server).

This transfer schedule may significantly improve performance. By
serializing the transfer of resources on the critical path, the browser can
ensure that resources needed immediately do not compete for bandwidth
capacity with less important transfers. Yet, the pipe remains full, as a
queue of requests is maintained in the scheduling tree ready to fill any
idle capacity with useful data. Where we cannot make an informed scheduling
decision, we hedge our bets with concurrent transfers by hinting that they
are peers and letting the server decide what makes the most sense --- as in
the case of two above the fold images that can be rendered progressively.

Note that this sort of explicit scheduler hinting is not possible in HTTP
today. Requests, once issued, cannot be reprioritized or reordered on a
single connection. This results in suboptimal transfer schedules given the
limitations of HTML lookahead scanning. Yet, lookahead is essential for
ensuring the concurrency necessary to keep the client <-> server pipe full.
While the browser might serialize transfers itself, the many small
transfers typical of pageloads would significantly limit utilization. With
ordering and reprioritization in SPDY, browsers can jointly optimize both
the transfer pipeline and resource priority as desired, rather than being
forced to accept poor utilization or poor transfer schedules.

- Servicing multiple tabs/users over a single SPDY session
As an illustration of this case, recall the example from our straw-man

Suppose concurrent tabs are loading with a scheduling forest as shown. When
a user changes tabs, the browser simple sends a REPRI for the stream
associated with tab2.htm to, say, priority 8. (A batched message might also
reduce the priority of tab1.htm to weight 3.) Because bandwidth allocation
decisions are made tree-by-tree and level-by-level, increasing the priority
of tab2.htm effectively shifts capacity for all resource transfers
depending on tab1.htm to tab2.htm.

- Server push

As in client SYN_STREAM messages, server push messages indicate the
priority and dependencies of a resource as chosen by the server. Much like
the client, the server is free to adopt prioritization policies to improve
performance, e.g., by prioritizing pushes of styles over images. But, as in
our example above, the browser may update the server's choices as
information about resources needed for parsing is learned. (Again,
expressed via REPRI messages.)

Policy considerations

Both priorities and stream dependencies are advisory hints. Browsers may
adopt sophisticated policies or leave dependencies entirely unspecified.
Similarly, servers may incorporate dependency hints into very sophisticated
schedulers or ignore them entirely. The protocol mechanisms for encoding
dependencies are designed to be simple. But, these mechanisms afford a very
flexible set of policies depending on how browsers and servers use them.
This section expands on several policy considerations.

Assigning and updating dependencies.
Updates and overhead
In our examples, we consider a browser that configures dependencies to
reflect parser-blocking order for resources, updated as parsing continues.
We expect this to improve performance, but browsers are free to deviate
from this policy, and there may be good reasons to do so. For example, if
the parser-blocking order is highly dynamic (e.g., in response to many JS
events), the overhead of updating dependencies may not be worth the cost,
particularly for small transfers. A sophisticated client may base
dependency update decisions on content-length and/or RTT, restricting
updates to only those streams likely to benefit from it. Quantitative
implementation experience will be helpful here.

The overhead of updating dependencies depends in part on the existing
structure of dependencies. In some scenarios, it may be more efficient to
introduce placeholder nodes to improve the efficiency of common update
operations. For example, consider a variant of our earlier example page:

<script src="a.js"></script> <!-- containing: document.write('<script
src="b.js"></script>'); -->
<img src="1.jpg" width="100" height="100"/>
<img src="2.jpg" width="100" height="100"/>
<img src="3.jpg" width="100" height="100"/>
<img src="10.jpg" width="100" height="100"/>

In this example, the speculative parser might create 10 streams depending
on the JS transfer; i.e.,

But, once a.js is executed, the transfer of b.js should preempt all image
transfers; i.e.,

Transitioning between these dependency structures requires sending
REPRImessages for each image. Because updating the dependencies of
images is
common, a client might create all image streams with a placeholder
dependency, yielding an initial configuration of:

With such an initial configuration, updating the dependencies of the images
to the stream associated with b.js can be accomplished with a single
REPRImessage updating the placeholder.

Multiple parents
All of our examples have considered nodes with a single parent. But, single
parent trees cannot express some transfer schedules. For example, an
asynchronous script at the end of HTML is non-blocking and does not block
interaction or pageload. It should be loaded after all visible resources
(e.g., images) have completed. A possible dependency graph is:

Here, any of img1, img2, or img3 should be prioritized before the
asynchronous script, a schedule that cannot be expressed with single parent

Reacting to server capabilities

Clients should not specify dependencies to servers that do not support it
SETTINGS frame). Rather, an intelligent client may fall back to specifying
priorities only, thereby improving performance relative to specifying
dependencies that will be ignored.

Server scheduling.
A conformant server should respect the semantics of priorities and
dependencies in its scheduling policy. Priorities indicate a
preference for weighted
scheduling (e.g., using a lottery
among root nodes (i.e., those created with a priority and not a parent).
Interior nodes with identical parents are weighted equally.

Server scheduling should reflect guidance from dependencies, but it need
need not be strict. If all streams in a dependency tree have data available
to write at the server, writes should be serviced first for root nodes,
then children, then grandchildren, and so on. But, children that are ready
to write should not starve to enforce a scheduling dependency. In other
words, scheduling dependencies should not lead servers to waste capacity.
If data is not available to continue writing the root, for example, a child
ready to write should do so.

Finally, we point out that servers may improve performance even if clients
do not provide dependency information or priorities. For example, an
intelligent server may inspect the content type of resources to make
informed prioritization decisions on its own without client guidance.
(However, respecting client-provided hints when available is likely to
improve performance, as clients have detailed knowledge of parser

Garbage collecting dependency information.
SPDY implementations must take care to protect themselves from the use of
dependencies as a DoS vector. The protocol provides wide flexibility in
this regard; servers are free to drop dependency or priority data at any
time without sacrificing correctness.

Otherwise, we envision servers choosing a timeout value for dependency
nodes that is large enough to cover the likely time period during which a
client may reference a node; e.g., page load time + rtt. Alternatively, a
large fixed number of dependencies may be maintained per-session with LRU
eviction. Either of these policies is likely to sharply limit the number of
missed dependency references. On the client side, browsers should take care
to manage dependencies according to server policies, e.g., by creating new
dependency structures rather than referring to those that have likely timed
out and been garbage collected.

While missed references may be rare, they are unavoidable in an
asynchronous system with timeouts. (This is why we require that servers
accept as correct any dependency id.) In cases where a reference is made to
an unknown node at the server, the server may create the referenced id as a
new root for future reference or ignore the dependency entirely (i.e.,
treat the new stream as a root).
Received on Monday, 28 October 2013 22:46:03 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 11:11:18 UTC