The dependency based prioritization was first introduced in HTTP/2
draft-11 and further refined in HTTP/2 draft-12, which is the latest
draft version at the of this writing. The draft describes its mechanism and requirements for client and server in 5.3. Stream priority in detail.
In short, dependency based prioritization works like this:
A stream can depend on another stream. If stream B depends on
stream A, stream B is not processed unless stream A is closed or
stream A cannot progress due to, for example, flow control or data
is not available from backend content server. These dependency
links form a tree, which is called dependency tree (circular
dependency is not allowed).
Dependency has weight. This is used to determine how much available
resource (e.g., bandwidth) is allocated to a stream.
Streams with the same dependencies SHOULD be allocated resources
proportionally based on their weight. Thus, if stream B depends on
stream A with weight 4, and C depends on stream A with weight 12, and
if no progress can be made on A, stream B ideally receives one third
of the resources allocated to stream C.
We do not describe about weight further in this post. We focus about
stream dependency part and assumes all weightings are equal.
We first have to say that prioritization in HTTP/2 is completely
optional feature. Client can freely provide prioritization
information to a server, but server has a choice to ignore them.
Simple server implementation may ignore prioritization altogether.
So how is this mechanism used for our Web pages? When loading a
typical Web page, client first requests HTML file. It then parses
received portion of HTML file and finds the links to resources, such
as CSS, Javascript and images, and issues requests to get these
resources as well. Suppose that client wants HTML in highest
priority, since it is the main page to show. Then it wants CSS or
Javascript in medium priority. Images are in lowest priority. These
requirement can be expressed as dependency: CSSs and Javascripts
depend on a HTML file. Images depend on CSSs or Javascripts files.
Providing these prioritization information to the server, client can
load resoures in opitimal order.
nghttp2 fully implements prioritization. So let’s see how the
prioritization works in the real use case. We use nghttp2
documentation index.html generated by sphinx (the same page is
available at https://nghttp2.org/documentation/) as a test page. That
page contains links to the followings resources:
theme.css
doctools.js
jquery.js
theme.js
underscore.js
We use nghttp command-line client with -a option. With -a option,
it also downloads links found in HTML page it is downloading. It is
programmed to categorize resources in the following priority levels.
index.html is stream 1 (see stream_id=1). index.html does not depend
any streams since this is the first stream ever in this connection.
Then server responded with HTTP response header in HEADERS frame and
its response body in DATA frames:
END_STREAM means that content of stream 1 was completely received.
nghttp parsed received HTML in DATA frame found that links to
resources. First it requested 3 Javascript files:
There is priority information in each request HEADERS. For example,
stream requesting jquery.js has stream_id=1, weight=16, exclusive=0,
which means it depend on stream 1 with weight 16. exclusive=0 means
that its dependency is not exclusive, so if there are any dependencies
to a designated stream, new stream joins existing siblings. We’ll see
the example of exclusive=1 case soon. The other 2 requests also
depend on stream 1. At this moment, dependency tree became like this:
Here we have stream_id=1, weight=16, exclusive=1. This is a bit
different from the previous priority information. This time we have
exclusive=1, which means that stream 9 solely depends on stream 1
and the streams which formerly depend on stream 1 depend on stream 9.
So resulting dependency tree became like this:
The priority information for this request was stream_id=9, weight=16,
exclusive=0. The stream 9 was theme.css. So unlike the first 3
Javascript files, this request directly specified the dependency to
stream 9. Finally the dependency tree became like this:
This completely reflects the priority levels nghttp client implements.
Did the server respect this prioritization? Let’s see the DATA flow
of these streams. Since stream 1 was already finished, stream 9 was
the highest priority. The log shows that server correctly sent its
DATA first:
You will notice that there are stream 3, 5, 7 and 11 interleaved
before stream 9 got finished. This is because stream 9 could not make
progress because of flow control. You see BLOCKED frame for stream 9
in the above log. The progress of stream 9 was blocked until
WINDOW_UPDATE frame for stream 9 was arrived to the server. While
stream 9 was blocked, streams which depend on stream 9 were unblocked
and started to send its DATA frames. After the server received
WINDOW_UPDATE frame for stream 9, it started to send DATA frame of
stream 9 again and stream 3, 5, 7 and 11 were blocked.
After stream 9 was finished, the remaining streams had equal priority,
so they were sent interleaved:
