Re: Restarting the discussion on HTTP/2 stream priorities

I think you're assuming that all streams in a connection belong to a single
webpage load. Let me know if not, and I can explain further.
On Nov 3, 2013 9:04 AM, "Peter Lepeska" <> wrote:

> Right. But my point is that an extremely simple scheme, where the browser
> just indicates that an object is blocking or not, gets you to the same
> place as the dependency scheme.
> Peter
> On Sun, Nov 3, 2013 at 8:54 AM, Martin Thomson <>wrote:
>> The intent would be to use ordering (i.e. dependencies) for this
>> scenario, not "priorities" (aka weights).
>> On 3 November 2013 07:37, <> wrote:
>>> Going through your example, would the prioritization at any instant be
>>> any different if you simply assigned two priorities -- high for resources
>>> that are blocking (the .js and the .css in your example) and low for
>>> resources that are non-blocking (the .jpgs)?
>>> Sorry if I'm missing something but it doesn't seem like it to me.
>>> Peter
>>> On Oct 28, 2013, at 3:45 PM, William Chan (陈智昌) <>
>>> wrote:
>>> On Mon, Oct 28, 2013 at 3:34 PM, Martin Thomson <
>>>> wrote:
>>>> On 28 October 2013 14:32, William Chan (陈智昌) <>
>>>> 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 motivation<>for dependencies, protocol
>>> changes<>to support them, and
>>> examples<>of how those mechanisms can be used by the browser. We conclude with a
>>> discussion of the client and server policies<>afforded by expressing dependency information in SPDY.
>>> (Note that flow control is the subject of a separate document and is out
>>> of scope here.)
>>> Motivation
>>> 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
>>> created.
>>> Priorities provide hints to the server about which streams are most
>>> important to the client, but they are poorly suited to several common
>>> use-cases.
>>>    - 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<>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.jsshould 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:
>>>    1. 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.
>>>    2. 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 transfers.
>>> 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 SETTINGS id/value pair. We describe the layout and semantics of
>>> each in turn.
>>> Note that these protocol changes are defined in terms of the latest
>>> version of the SPDY draft specification<>
>>> .
>>>     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 (§2.2.2<>).
>>> A new 32 bit field replaces the existing SYN_STREAM priority bits (
>>> §2.6.1<>)
>>> with:
>>>    - 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 (§2.6.11<>)
>>>    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 section<>
>>> .
>>> 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 (§3.3.1<>
>>> ).
>>> REPRI:
>>>     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 Idsince 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 (
>>> §2.6.4<>
>>> ),
>>>    the 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.)
>>>    long 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
>>> entirely.
>>> 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:
>>>    1. 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.
>>>    2. Resources that can be progressively rendered (e.g., images) are
>>>    transferred concurrently and (re)configured to depend on parser-blocking
>>>    resource transfers.
>>>    3. 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
>>> parent.
>>> 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.htmis 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 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"/>
>>> <link rel="stylesheet" type="text/css" href="style.css">
>>> </body>
>>> with a.js:
>>> document.write('<script src="b.js"></script>');
>>> b.js:
>>> document.write('<div>blocker</div>');
>>> 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 a.js).
>>>    - 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_STREAMis another
>>>    REPRI message rewiring style.css to depend on b.js. This serializes
>>>    the transfers (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
>>> design:
>>> 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:
>>> <html>
>>> <body>
>>> <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"/>
>>> </body>
>>> 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
>>> REPRI message updating the placeholder.
>>> Multiple parents
>>> ...

Received on Sunday, 3 November 2013 21:30:56 UTC