nghttp2.org

HTTP/2 C library and tools

How Dependency Based Prioritization Works

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.

    Quoted from 5.3.2. Dependency weighting:

    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.

  1. HIGHEST – main HTML (index.html)
  2. HIGH – CSS files (theme.css)
  3. MIDDLE – Javascript files (doctools.js, jquery.js, theme.js)
  4. LOWEST – Images (none in this case)

Hopefully, we’d like to build dependency tree like this:

Ideal dependency tree

We use following command-line to run nghttp client:

1
$ nghttp -nva https://localhost:3000/doc/manual/html/index.html

With -v option, we can see what happens in HTTP/2 frameing layer. First, nghttp requested index.html to the server:

1
2
3
4
5
6
7
8
9
10
11
[  0.041] send HEADERS frame <length=67, flags=0x05, stream_id=1>
          ; END_STREAM | END_HEADERS
          (padlen=0)
          ; Open new stream
          :authority: localhost:3000
          :method: GET
          :path: /doc/manual/html/index.html
          :scheme: https
          accept: */*
          accept-encoding: gzip, deflate
          user-agent: nghttp2/0.4.0-DEV

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[  0.042] (stream_id=1, noind=0) :status: 200
[  0.042] (stream_id=1, noind=0) server: nghttpd nghttp2/0.4.0-DEV
[  0.042] (stream_id=1, noind=0) content-length: 13978
[  0.042] (stream_id=1, noind=0) cache-control: max-age=3600
[  0.042] (stream_id=1, noind=0) date: Sun, 27 Apr 2014 13:18:26 GMT
[  0.042] (stream_id=1, noind=0) last-modified: Sun, 27 Apr 2014 10:48:12 GMT
[  0.042] recv HEADERS frame <length=84, flags=0x04, stream_id=1>
          ; END_HEADERS
          (padlen=0)
          ; First response header
[  0.043] recv DATA frame <length=4096, flags=0x00, stream_id=1>
[  0.044] recv DATA frame <length=4096, flags=0x00, stream_id=1>
[  0.044] recv DATA frame <length=4096, flags=0x00, stream_id=1>
[  0.044] recv DATA frame <length=1690, flags=0x00, stream_id=1>
[  0.044] recv DATA frame <length=0, flags=0x01, stream_id=1>
          ; END_STREAM

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
[  0.044] send HEADERS frame <length=32, flags=0x25, stream_id=3>
          ; END_STREAM | END_HEADERS | PRIORITY
          (padlen=0, stream_id=1, weight=16, exclusive=0)
          ; Open new stream
          :authority: localhost:3000
          :method: GET
          :path: /doc/manual/html/_static/jquery.js
          :scheme: https
          accept: */*
          accept-encoding: gzip, deflate
          user-agent: nghttp2/0.4.0-DEV
[  0.044] send HEADERS frame <length=34, flags=0x25, stream_id=5>
          ; END_STREAM | END_HEADERS | PRIORITY
          (padlen=0, stream_id=1, weight=16, exclusive=0)
          ; Open new stream
          :authority: localhost:3000
          :method: GET
          :path: /doc/manual/html/_static/underscore.js
          :scheme: https
          accept: */*
          accept-encoding: gzip, deflate
          user-agent: nghttp2/0.4.0-DEV
[  0.044] send HEADERS frame <length=32, flags=0x25, stream_id=7>
          ; END_STREAM | END_HEADERS | PRIORITY
          (padlen=0, stream_id=1, weight=16, exclusive=0)
          ; Open new stream
          :authority: localhost:3000
          :method: GET
          :path: /doc/manual/html/_static/doctools.js
          :scheme: https
          accept: */*
          accept-encoding: gzip, deflate
          user-agent: nghttp2/0.4.0-DEV

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:

Dependency tree after stream 3, 5 and 7 were requested

Then nghttp found CSS link and issued request:

1
2
3
4
5
6
7
8
9
10
11
[  0.044] send HEADERS frame <length=34, flags=0x25, stream_id=9>
          ; END_STREAM | END_HEADERS | PRIORITY
          (padlen=0, stream_id=1, weight=16, exclusive=1)
          ; Open new stream
          :authority: localhost:3000
          :method: GET
          :path: /doc/manual/html/_static/css/theme.css
          :scheme: https
          accept: */*
          accept-encoding: gzip, deflate
          user-agent: nghttp2/0.4.0-DEV

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:

Dependency tree after stream 3, 5, 7 and 9 were requested

The last resource was theme.js:

1
2
3
4
5
6
7
8
9
10
11
[  0.044] send HEADERS frame <length=33, flags=0x25, stream_id=11>
          ; END_STREAM | END_HEADERS | PRIORITY
          (padlen=0, stream_id=9, weight=16, exclusive=0)
          ; Open new stream
          :authority: localhost:3000
          :method: GET
          :path: /doc/manual/html/_static/js/theme.js
          :scheme: https
          accept: */*
          accept-encoding: gzip, deflate
          user-agent: nghttp2/0.4.0-DEV

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:

Final dependency tree

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
[  0.047] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.047] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.047] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.047] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.047] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.047] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.047] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.047] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=0>
          (window_size_increment=34458)
[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=9>
          (window_size_increment=32768)
[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] recv DATA frame <length=2405, flags=0x00, stream_id=9>
[  0.048] recv BLOCKED frame <length=0, flags=0x00, stream_id=0>

[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.048] recv DATA frame <length=1690, flags=0x00, stream_id=9>
[  0.048] recv BLOCKED frame <length=0, flags=0x00, stream_id=9>

[  0.049] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=0>
          (window_size_increment=35173)
[  0.049] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=9>
          (window_size_increment=32767)
[  0.049] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.049] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.049] recv DATA frame <length=4096, flags=0x00, stream_id=7>
[  0.049] recv DATA frame <length=1675, flags=0x00, stream_id=11>
[  0.049] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.049] recv DATA frame <length=2421, flags=0x00, stream_id=5>
[  0.049] recv BLOCKED frame <length=0, flags=0x00, stream_id=0>

[  0.049] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.049] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.049] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.049] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=0>
          (window_size_increment=34458)
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=9>
[  0.050] recv DATA frame <length=105, flags=0x00, stream_id=9>
[  0.050] recv DATA frame <length=0, flags=0x01, stream_id=9>
          ; END_STREAM

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
[  0.050] recv DATA frame <length=2584, flags=0x00, stream_id=7>
[  0.050] recv DATA frame <length=0, flags=0x01, stream_id=11>
          ; END_STREAM
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.050] recv DATA frame <length=3812, flags=0x00, stream_id=5>
[  0.050] recv BLOCKED frame <length=0, flags=0x00, stream_id=0>

[  0.050] recv DATA frame <length=0, flags=0x01, stream_id=7>
          ; END_STREAM
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.050] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=0>
          (window_size_increment=35173)
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.050] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.050] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=3>
          (window_size_increment=32768)
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.051] recv DATA frame <length=1690, flags=0x00, stream_id=3>
[  0.051] recv BLOCKED frame <length=0, flags=0x00, stream_id=0>

[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.051] send WINDOW_UPDATE frame <length=4, flags=0x00, stream_id=0>
          (window_size_increment=34458)
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=5>
[  0.051] recv DATA frame <length=2416, flags=0x00, stream_id=5>
[  0.051] recv DATA frame <length=0, flags=0x01, stream_id=5>
          ; END_STREAM
[  0.051] recv DATA frame <length=4085, flags=0x00, stream_id=3>
[  0.051] recv BLOCKED frame <length=0, flags=0x00, stream_id=0>

[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=3>
[  0.051] recv DATA frame <length=4096, flags=0x00, stream_id=3>