Re: Is a faithful HTTP/2 response scheduler necessarily O(n) in the worst case?

Thanks for the feedback. Sounds like the worst-case time really is O(n).

> kazuhooku@
> the constant for O(n) would be small enough so that it cannot be used an
attack vector

Don't you need to ensure that n is small, otherwise even O(n) with a small
constant factor can lead to degraded performance? e.g.,
if SETTINGS_MAX_CONCURRENT_STREAMS = 20,000, I may end up computing a sum
of 20,000 numbers every few frames, which is not terribly slow, but not
terribly fast either.

> kazu@
> http://www.mew.org/~kazu/material/2015-http2-priority2.pdf
> http://www.mew.org/~kazu/doc/paper/http2-haskell-2016.pdf

Thanks. IIUC, the algorithms described in both links are still at least
O(depth), which can be O(n) for dependency trees generated by certain
clients such as Chrome.

> stefan.eissing@
> The very same problem exists for stream processing in order to generate
response data.

What did you mean by "stream processing"?

On Tue, Jan 24, 2017 at 12:26 AM, Stefan Eissing <
stefan.eissing@greenbytes.de> wrote:

> The very same problem exists for stream processing in order to generate
> response data.
>
> > Am 24.01.2017 um 08:53 schrieb Kazu Yamamoto (山本和彦) <kazu@iij.ad.jp>:
> >
> > Hi Tom,
> >
> > Probably, this material would help you:
> >
> > http://www.mew.org/~kazu/material/2015-http2-priority2.pdf
> > http://www.mew.org/~kazu/doc/paper/http2-haskell-2016.pdf
> >
> > --Kazu
> >
> >> Regarding your question, I am unaware of a scheduler design that is
> >> better than O(n) for both dequeuing (i.e. selecting the stream to
> >> send) and for rescheduling a stream (especially a stream with many
> >> decendants).
> >>
> >> While designing the scheduler of H2O (you are right in pointing out
> >> the fact that it is O(depth)), I came up with two options. One was to
> >> retain the vertical (i.e. parent-children) relationship between the
> >> streams. The other was to squash the vertical relationships to
> >> generate a one-dimensional list of streams ordered by priority.
> >>
> >> By taking the latter approach, you could create a scheduler that
> >> dequeues at O(1). But such scheduler would need to perform O(N)
> >> operation when receiving a priority frame or a stream-level window
> >> update (in this case N is number of direct and indirect decendants of
> >> the reprioritized stream).
> >>
> >> Considering this, we chose to implement the scheduler of H2O as O(1)
> >> weight-wise, and O(n) depth-wise, but that the constant for O(n) would
> >> be small enough so that it cannot be used an attack vector.
> >>
> >> 2017-01-24 9:39 GMT+09:00 Tom Bergan <tombergan@chromium.org>:
> >>> I implemented the HTTP/2 response scheduler in Go's HTTP/2 server
> library.
> >>> I'm trying to understand the worst-case behavior of that scheduler. I
> >>> believe the worst-case behavior is necessarily O(n) operations per
> frame
> >>> sent on the wire, where n is the number of streams in the dependency
> tree.
> >>> Here is my rationale.
> >>>
> >>> The key operation is finding the highest-priority stream that is ready
> to
> >>> send data.
> >>>
> >>> If we don't care about weights, and we don't care about balancing
> bandwidth
> >>> usage across sibling nodes in a tree, then we can label each node with
> two
> >>> fields: "ready" (true if the stream is ready to send data) and "depth"
> (the
> >>> node's distance from the root of the tree). The scheduler must find a
> node
> >>> with the smallest depth over all nodes with ready = true. It is fairly
> >>> trivial to implement this in O(log n).
> >>>
> >>> Now, let's introduce weights. The scheduler must allocate bandwidth to
> all
> >>> ready nodes, which happens recursively as follows:
> >>>
> >>>  func allocateBandwidth(node, bw) {
> >>>    if (node.ready) {
> >>>      node.bandwidthShare = bw
> >>>      return
> >>>    }
> >>>    totalWeight = 0
> >>>    for (n in node.children) {
> >>>      if (n.ready || descendantIsReady(n)) {
> >>>        totalWeight += n.weight
> >>>      }
> >>>    }
> >>>    for (n in node.children) {
> >>>      if (n.ready || descendantIsReady(n)) {
> >>>        allocateBandwidth(n, bw * n.weight / totalWeight)
> >>>      }
> >>>    }
> >>>  }
> >>>  allocateBandwidth(root, 1.0)
> >>>
> >>> I believe the above definition is a direct translation of RFC 7540
> Section
> >>> 5.3.2 (also see this thread, which discussed bandwidth allocation).
> Given a
> >>> complete bandwidth allocation, the server can translate each node's
> >>> bandwidthShare to a number of tokens that are updated using a token
> bucket
> >>> algorithm (or similar). The scheduler would then pick the node with
> the most
> >>> available tokens. The scheduler looks something like:
> >>>
> >>>  func scheduleNextFrame() {
> >>>    if (tree changed since last frame written) {
> >>>      allocateBandwidth(root, 1.0)
> >>>      assign tokens and build a priority queue containing all nodes with
> >>> allocated bandwidth
> >>>    }
> >>>    node = priorityQueue.head()
> >>>    node.consumeTokens() // consume up to frame size or flow-control
> limit
> >>>    priorityQueue.update(node)
> >>>    return node
> >>>  }
> >>>
> >>> There are two steps in scheduleNextFrame. The first step updates the
> >>> bandwidth allocation if the tree changed since the last frame was
> written.
> >>> This is the most expensive step. I don't believe it's possible to
> implement
> >>> allocateBandwidth using fewer than O(n) worst-case steps. For example,
> if
> >>> the tree is mostly flat, meaning that most nodes are children of the
> same
> >>> node, then the loop to compute totalWeight is O(n). I believe Firefox
> >>> creates mostly-flat trees. Further, allocateBandwidth makes O(depth)
> >>> recursive steps, where "depth" is the maximum depth of the dependency
> tree.
> >>> If the tree is mostly-linear, then O(depth) becomes O(n). Chrome
> creates
> >>> mostly-linear trees.
> >>>
> >>> The overall runtime depends on how often the tree changes. If the tree
> >>> changes rarely, the scheduler is cheap. If the tree changes
> frequently, the
> >>> scheduler is worst-case O(n). A tree has "changed" if it changed shape
> >>> (nodes are added/moved/removed) or if any node's ready state has
> changed.
> >>> Both kinds of changes can happen often in practice, suggesting that the
> >>> overall scheduler is worst-case O(n). For example, consider a server
> that
> >>> sends small responses (one or two DATA frames per response) -- each
> stream
> >>> will be closed after one or two DATA frames, so on average, the tree
> will
> >>> change shape every few frames. Further, it's possible for ready states
> to
> >>> change more frequently than you might think. In Go's HTTP/2
> implementation,
> >>> a stream does not become ready until the application handler calls
> Write to
> >>> buffer response data. After that buffered data is serialized on the
> wire,
> >>> the stream transitions to "not ready" because the scheduler cannot
> know when
> >>> the next Write call will happen. The stream will transition back to
> "ready"
> >>> during the next Write call. Each Write call typically buffers about
> 32KB of
> >>> data. This is a "push" model, where the application handler "pushes"
> data
> >>> into the scheduler. I'm aware of one other HTTP/2 server that works
> >>> similarly. I suspect that frequent ready/not-ready transitions are
> common to
> >>> most HTTP/2 servers that use a "push" model. These servers will be more
> >>> susceptible to the O(n) worst case.
> >>>
> >>> Questions:
> >>>
> >>> 1. Am I missing a clever implementation, or is it true that a faithful
> >>> HTTP/2 scheduler necessarily requires O(n) operations per frame sent
> on the
> >>> wire, in the worst case? I could not find much discussion of this
> question
> >>> after a quick search. H2O claims to implement an O(1) scheduler,
> however,
> >>> the code seems to be worst-case O(depth) or O(n) -- see here, here, and
> >>> here.
> >>>
> >>> 2. If the above is correct, should I be concerned about the O(n) worst
> case?
> >>> I doubt that a typical web browsing session will trigger O(n) behavior
> >>> frequently, so I'm less concerned about the average case; I'm more
> concerned
> >>> about pathological cases or possible DoS vectors. Also, think about
> cases
> >>> where the "client" is actually a proxy server, meaning the HTTP/2
> connection
> >>> may have many more concurrent streams than a typical browsing session.
> For
> >>> comparison, if you recall the predecessor to HTTP/2 (SPDY), a SPDY
> scheduler
> >>> could be trivially implemented in O(1), since SPDY used just eight
> priority
> >>> buckets.
> >>>
> >>> 3. If I should be concerned about an O(n) worst case, are there any
> >>> suggested mitigations beyond setting SETTINGS_MAX_CONCURRENT_STREAMS
> to a
> >>> smallish constant?
> >>
> >>
> >>
> >> --
> >> Kazuho Oku
> >>
> >
>
>
>