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

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

  +----------------+     +----------------+
  |                |     |                |
  | Tab1.html (P6) |     | Tab2.html (P6) |
  |                |     |                |
  +----------------+     +----------------+
          ^                       ^
          |                       |
          +                       +
  +----------------+     +----------------+
  |                |     |                |
  |      a.js      |     |     a.jpg      |
  |                |     |                |
  +----------------+     +----------------+
          ^                       |
          |                       |
          +                       |
  +----------------+     +----------------+
  |                |     |                |
  |      b.js      |     |      b.jpg     |
  |                |     |                |
  +----------------+     +----------------+

Figure 1: Multiple Tab Example

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. Thus, the dependency between b.jpg and a.jpg is unordered, indicating that writes for the tab2.html stream should be scheduled first, but capacity may be shared between the streams for a.jpg and b.jpg.

When scheduling transfers, we consider a server that treats dependencies conceptually as lists. Recall that streams depend on and are depended on by at most one other stream. These can be treated as predecessor and successor ids. Stream writes are scheduled in two steps: 1) choosing a dependency list with at least one stream ready to write and 2) then selecting the stream to write by traversing the list. (An implementation might maintain ready queues of streams for efficiency, but we consider a simplified setting for clarity.)

Because the streams associated with the transfers of tab1 and tab2 have priorities rather than dependencies, they are always scheduled before any dependent streams. But, bandwidth allocation between dependency lists remains proportional as defined by the relative priority of tab1 and tab2. For example, if the transfer of tab2.htm is in progress and tab1.htm (now complete) is ready and selected by the scheduler, a.js will be scheduled before tab2.htm completes. This process proceeds until all transfers in a list have completed.

5.1. Specifying an ordering of resource transfers and 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:

<html>
<body>
<script src="a.js"></script>
<img src="a.jpg" width="100" height="100"/>
<img src="b.jpg" width="100" height="100"/>
</body>

with a.js:

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

and b.js:

document.write('<div>blocker</div>');

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 and b.jpg 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:

Client               Server
  +                     +
  |+ GET index.htm      |
  |+------------------->|
  |          index.htm +|
  |<-------------------+|
  |+ GET a.js           |
  |+------------------->|
  |+ GET a.jpg          |
  |+------------------->|
  |+ GET b.jpg          |
  |+------------------->|
  |               a.js +|
  |<-------------------+|
  |+ GET b.js           |
  |+------------------->|
  |              a.jpg +|
  |<-------------------+|
  |              b.jpg +|
  |<-------------------+|
  |               b.js +|
  |<-------------------+|
  |                     |
  v                     v

This transfer schedule is suboptimal. Page rendering will complete only when once b.js has completed, but receiving b.js is slowed by competition for bandwidth capacity for a.jpg and b.jpg, which do not block rendering.

Ideally, the order resources are transferred would reflect the document parse order with bandwidth sharing only for progressive resources. More specifically, we want to receive: 1) index.htm, 2) a.js, and 3) b.js sequentially. After those critical transfers have completed, a.jpg and b.jpg should be transferred concurrently since they may be displayed progressively.

Folding in the protocol mechanisms described above:

Client                   Server |              Scheduling
  +                         +   |
  |+ 1: GET index.htm (P3)  |   |
  |+----------------------->|   | index.htm (P3)
  |              index.htm +|   |
  |<-----------------------+|   |====================================
  |+ 3: GET a.js (S1)       |   | +--------------+
  |+----------------------->|   | |index.htm (P3)|
  |+ 5: GET a.jpg (S3)      |   | +--------------+
  |+----------------------->|   |         ^
  |+ 7: GET b.jpg (S5=)     |   |         |---- a.js <- a.jpg - b.jpg
  |+----------------------->|   |====================================
  |                   a.js +|   |
  |<-----------------------+|   |
  |+ 9: GET b.js (S1)       |   | +--------------+    +----+
  |+----------------------->|   | |index.htm (P3)| <- |a.js|
  |                   b.js +|   | +--------------+    +----+
  |<-----------------------+|   |                        ^
  |                  a.jpg +|   |    |-------------------|
  |<-----------------------+|   |    |
  |                  b.jpg +|   |    |-b.js <- a.jpg - b.jpg
  |<-----------------------+|   |
  |                         |   |
  v                         v   |

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

The HEADERS for the index.htm request indicates 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 and b.jpg in parse order. a.jpg and b.jpg can be progressively rendered, so their transfer is concurrent (a.jpg has an ordered dependency on a.js, and b.jpg has an unordered dependency on a.jpg).
Once a.js completes, the document parser continues by 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 which depends on a.js (or, equivalently, index.htm).

This transfer schedule improves 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. The pipe remains full, as a queue of requests is maintained in the dependency list, filling 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 unordered 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.

5.2. Servicing multiple tabs/users over a single HTTP/2 connection

As an illustration of this case, recall the example [multiple_tab_example] from our straw-man design.

Suppose concurrent tabs are loading with the dependencies shown. When a user changes tabs, the browser sends a PRIORITY frame updating 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 is allocated among streams with priorities before considering their dependents, increasing the priority of tab2.htm effectively shifts capacity for all resource transfers depending on tab1.htm to tab2.htm.

5.3. Server Push

Push streams are assigned a priority or dependency at the discretion of the server. Typically, the Promised-Stream-ID would depend on the stream id carrying the PUSH_PROMISE frame. As information about resources needed for parsing is learned, the browser may update the dependency relationship by sending a PRIORITY message.

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

6.1. Assigning and updating dependencies

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 is needed to determine how best to assign and update dependencies.

6.2. 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 scheduler [LOTTERYSCHEDULING]) among top-level streams; i.e., those created with a priority and not a dependency. Capacity should be shared among a sequence of streams with unordered dependencies.

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 top-level streams, then ordered dependents, with sharing among unordered streams. But, depedents 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 top-level stream, for example, a dependent 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 dependencies.)

6.3. Garbage collecting dependency information

HTTP/2 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.

Typically, we envision servers will drop dependency information along with other stream state when an END_STREAM_ACK frame is received or the session is closed.

7. Security Considerations

TODO

8. Informative References

[PRELOADSCANNER]	Gentilcore, T., "The WebKit PreloadScanner", 2011.
[LOTTERYSCHEDULING]	Waldspurger, C. and W. Weihl, "Lottery scheduling: flexible proportional-share resource management", 1994.

Appendix A. Acknowledgements

This document resulted from discussions amongst the SPDY team at Google. The authors merely took that discussion and edited this document. The individuals who contributed to those discussions include, but are not limited to: Roberto Peon, Hasan Khalil, Ryan Hamilton, Jim Roskind, Bryan McQuade, Chris Bentzel, Ilya Grigorik.

Authors' Addresses

Michael Piatek Google EMail: piatek@chromium.org

William Chan Google EMail: willchan@chromium.org

Abstract

Status of This Memo

Copyright Notice

Table of Contents

1. Introduction

2. Motivation

3. Protocol Changes

3.1. HEADERS frame

3.2. PRIORITY frame

3.3. END_STREAM_ACK frame

4. Protocol invariants and definitions

5. Examples