Subject: QPACK and the Static Table

From: Mike Bishop <[email-masked]>
Date: Wed, 23 May 2018 23:16:18 +0000

Wanted to get a sense of the affected working groups on two issues in QPACK (header compression for HTTP/QUIC).

Rather than indexing the tables together and having the static table at 1-61, QPACK uses a bit to indicate static vs. dynamic.  Since the field is seven bits long, the performance is comparable for the dynamic table (you can access 63 entries in one byte, 190 in two), but you can increase the size of the static table without hurting the dynamic table.  As a result, we're building a fresh static table<https://github.com/quicwg/base-drafts/pull/1355> based on queries against HTTPArchive data.

The key question that has come up in a couple venues:  What real-world headers do we want to artificially remove from what the data shows, and what headers not seen by HTTP Archive do we want to force in anyway?

So far, we've:

  *   forced in pseudo-headers because the Archive doesn't capture them and they would otherwise be absent
     *   :path, :authority, :method
  *   deleted values presumed biased by the test configuration:
     *   Server: (various vendors)
     *   User-Agent
     *   Accept-Language: en-us, en;q=0.9
     *   Content-Length: 531
        *   I still wonder exactly why that's so common....
     *   P3p: policyref="https://www.googleadservices.com/..."....
     *   Origin: https://www.facebook.com
     *   Alt-Svc for various versions of gQUIC
     *   ...the list goes on
  *   deleted headers prohibited by HTTP/QUIC and HTTP/2
     *   Transfer-Encoding: chunked
  *   Reordered to put headers you're likely to name-reference at the front, especially if you're unlikely to add them to the dynamic table

The question is whether we should also backfill headers which HTTP Archive wouldn't see, delete headers we wish people wouldn't use, and/or insert the ones we hope they eventually will.  Some candidates:

  *   Add Alt-Svc entry for HTTP/QUIC with QUIC v1
  *   Add X-Forwarded-For
  *   Don't add X-Forwarded-For, but do add Forwarded
  *   Remove Expires to incent the use of Cache-Control
  *   Collapse the "Content-Type: <thingey>" and "Content-Type: <thingey>; charset=utf-8" entries together
     *   ...but which one to keep?
  *   Add Content-Encoding and/or Accept-Encoding entries for zstd

There's an endless parade of bikesheds here.  As Martin has pointed out, this will never be perfect, so the goal is "good enough and keep going."  Any strong feelings about any of these before we merge it?

Also, there's been some discussion of a mechanism for selecting one of several static tables at the start of a connection.  In that case, the spec would probably define three tables (client headers, server headers [for servers that don't push], combined [for servers that push]) and enable future RFCs to define others for targeted scenarios (proxies, video playback, IoT, etc.).  How much does that interest folks?

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 24 May 2018 09:47:45 +1000

Hey Mike,

My .02 (I also left some notes in the PR) -

The static table is most useful on request headers, so that's what we should be focusing on. If it were me, I'd drop all of the response header fields except the most common ones (say 10 or so), and focus on request headers.

In fact, I'd look at paring down the number of entries in total for *just* the initial requests on a connection -- putting too many things in the static table might influence how implementations emit other headers, and that's not the intent here.

The HTTP Archive is a bit problematic; not only is it focused on "big" sites (albeit a lot of them), but it's also AIUI pretty homogenous on the client side, so it's not going to be very representative for request headers.

I think it would be better to get a sample of request headers seen by a couple of sites, a CDN or two, and at least one "HTTP API" type deployment, and see where that leads -- if we can find someone willing to do the work.

Cheers,

> On 24 May 2018, at 9:16 am, Mike Bishop <[email-masked]> wrote:
> 
> Rather than indexing the tables together and having the static table at 1-61, QPACK uses a bit to indicate static vs. dynamic.  Since the field is seven bits long, the performance is comparable for the dynamic table (you can access 63 entries in one byte, 190 in two), but you can increase the size of the static table without hurting the dynamic table.  As a result, we’re building a fresh static tablebased on queries against HTTPArchive data.
>  
> So far, we’ve:
> 	• forced in pseudo-headers because the Archive doesn’t capture them and they would otherwise be absent
> 		• :path, :authority, :method
> 	• deleted values presumed biased by the test configuration:
> 		• Server: (various vendors)
> 		• User-Agent
> 		• Accept-Language: en-us, en;q=0.9
> 		• Content-Length: 531
> 			• I still wonder exactly why that’s so common….
> 		• P3p: policyref=”https://www.googleadservices.com/...”….
> 		• Origin: https://www.facebook.com
> 		• Alt-Svc for various versions of gQUIC
> 		• …the list goes on
> 	• deleted headers prohibited by HTTP/QUIC and HTTP/2
> 		• Transfer-Encoding: chunked
> 	• Reordered to put headers you’re likely to name-reference at the front, especially if you’re unlikely to add them to the dynamic table
>  
> The question is whether we should also backfill headers which HTTP Archive wouldn’t see, delete headers we wish people wouldn’t use, and/or insert the ones we hope they eventually will.  Some candidates:
> 	• Add Alt-Svc entry for HTTP/QUIC with QUIC v1
> 	• Add X-Forwarded-For
> 	• Don’t add X-Forwarded-For, but do add Forwarded
> 	• Remove Expires to incent the use of Cache-Control
> 	• Collapse the “Content-Type: <thingey>” and “Content-Type: <thingey>; charset=utf-8” entries together
> 		• …but which one to keep?
> 	• Add Content-Encoding and/or Accept-Encoding entries for zstd
>  
> There’s an endless parade of bikesheds here.  As Martin has pointed out, this will never be perfect, so the goal is “good enough and keep going.”  Any strong feelings about any of these before we merge it?
>  
> Also, there’s been some discussion of a mechanism for selecting one of several static tables at the start of a connection.  In that case, the spec would probably define three tables (client headers, server headers [for servers that don’t push], combined [for servers that push]) and enable future RFCs to define others for targeted scenarios (proxies, video playback, IoT, etc.).  How much does that interest folks?

--
Mark Nottingham   https://www.mnot.net/

---

From: Mike Bishop <[email-masked]>
Date: Wed, 23 May 2018 23:50:51 +0000

While I've tried to limit the bias introduced by their single browser and selection of sites, I share those concerns about using the HTTP Archive as a single source of data.  However, what I've heard from one HTTP API deployment and suspect is true across CDNs is that sharing request header values is problematic.

Maybe if we locally applied the filtering of not sharing values unless a single value represents more than 5% of header occurrences, that would be sufficiently anonymized for folks to be willing to share.

-----Original Message-----
From: Mark Nottingham <[email-masked]> 
Sent: Wednesday, May 23, 2018 4:48 PM
To: Mike Bishop <[email-masked]>
Cc: HTTP Working Group <[email-masked]>; [email-masked]
Subject: Re: QPACK and the Static Table

Hey Mike,

Cheers,

---

From: Patrick McManus <[email-masked]>
Date: Wed, 23 May 2018 19:52:43 -0400

limiting feedback to just strong opinions on your suggestions:

On Wed, May 23, 2018 at 7:16 PM, Mike Bishop <[email-masked]> wrote:

>
>    - Add Alt-Svc entry for HTTP/QUIC with QUIC v1
>
> this is clever and a good idea.

>
>    - Remove Expires to incent the use of Cache-Control
>
> tempting, but I think you're better off reflecting reality here.

>
>
>    - Add Content-Encoding and/or Accept-Encoding entries for zstd
>
> seems premature. When it was presented at ietf 100 Murray was clear this
was a 'targetted use case' and wasn't seeking browser adoption.. there are
certainly non-browser use cases to consider, but giving dictionary space to
it seems.. well, premature.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 24 May 2018 10:38:24 +1000

It might be worth skimming our current drafts and recent RFCs for header
fields that might be useful.  Early-Data seems like a real option, value
and all.
On Thu, May 24, 2018 at 9:16 AM Mike Bishop <[email-masked]> wrote:

> Wanted to get a sense of the affected working groups on two issues in
QPACK (header compression for HTTP/QUIC).

> Rather than indexing the tables together and having the static table at
1-61, QPACK uses a bit to indicate static vs. dynamic.  Since the field is
seven bits long, the performance is comparable for the dynamic table (you
can access 63 entries in one byte, 190 in two), but you can increase the
size of the static table without hurting the dynamic table.  As a result,
we’re building a fresh static table based on queries against HTTPArchive
data.

> The key question that has come up in a couple venues:  What real-world
headers do we want to artificially remove from what the data shows, and
what headers not seen by HTTP Archive do we want to force in anyway?

> forced in pseudo-headers because the Archive doesn’t capture them and
they would otherwise be absent

> :path, :authority, :method

> deleted values presumed biased by the test configuration:

> Server: (various vendors)
> User-Agent
> Accept-Language: en-us, en;q=0.9
> Content-Length: 531

> I still wonder exactly why that’s so common….

> P3p: policyref=”https://www.googleadservices.com/...”….
> Origin: https://www.facebook.com
> Alt-Svc for various versions of gQUIC
> …the list goes on

> deleted headers prohibited by HTTP/QUIC and HTTP/2

> Transfer-Encoding: chunked

> Reordered to put headers you’re likely to name-reference at the front,
especially if you’re unlikely to add them to the dynamic table

> The question is whether we should also backfill headers which HTTP
Archive wouldn’t see, delete headers we wish people wouldn’t use, and/or
insert the ones we hope they eventually will.  Some candidates:

> Add Alt-Svc entry for HTTP/QUIC with QUIC v1
> Add X-Forwarded-For
> Don’t add X-Forwarded-For, but do add Forwarded
> Remove Expires to incent the use of Cache-Control
> Collapse the “Content-Type: <thingey>” and “Content-Type: <thingey>;
charset=utf-8” entries together

> …but which one to keep?

> Add Content-Encoding and/or Accept-Encoding entries for zstd

> There’s an endless parade of bikesheds here.  As Martin has pointed out,
this will never be perfect, so the goal is “good enough and keep going.”
  Any strong feelings about any of these before we merge it?

> Also, there’s been some discussion of a mechanism for selecting one of
several static tables at the start of a connection..  In that case, the
spec would probably define three tables (client headers, server headers
[for servers that don’t push], combined [for servers that push]) and enable
future RFCs to define others for targeted scenarios (proxies, video
playback, IoT, etc.).  How much does that interest folks?

---

From: Martin Thomson <[email-masked]>
Date: Thu, 24 May 2018 10:37:33 +1000

> this is clever and a good idea.

Alt-Svc includes a hostname, so the value won't help.  The name is all we
can realistically use.

---

From: Patrick McManus <[email-masked]>
Date: Wed, 23 May 2018 20:46:55 -0400

iirc alt-svc requires a colon and a port (and an alpn) but not a hostname.
so quic=":443" would make sense.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 24 May 2018 10:50:14 +1000

On Thu, May 24, 2018 at 10:46 AM Patrick McManus <[email-masked]>
wrote:> iirc alt-svc requires a colon and a port (and an alpn) but not a
hostname. so quic=":443" would make sense.

Ahh, right, then carry on.  That's not the interesting case, but it is
certainly a good default.  I think that it's hq=":443";quic=1 or something
like that though.

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 24 May 2018 06:41:46 +0200

Hi Mike,

On Wed, May 23, 2018 at 11:16:18PM +0000, Mike Bishop wrote:
> Rather than indexing the tables together and having the static table at 1-61,
> QPACK uses a bit to indicate static vs. dynamic.  Since the field is seven
> bits long, the performance is comparable for the dynamic table (you can
> access 63 entries in one byte, 190 in two), but you can increase the size of
> the static table without hurting the dynamic table.

It will make the code look less "magic"!

> As a result, we're
> building a fresh static
> table<https://github.com/quicwg/base-drafts/pull/1355> based on queries
> against HTTPArchive data.
> 
> headers do we want to artificially remove from what the data shows, and what
> headers not seen by HTTP Archive do we want to force in anyway?

I agree with Mark that request really is what matters the most.

>   *   Reordered to put headers you're likely to name-reference at the front,
>   especially if you're unlikely to add them to the dynamic table

Well, some of us have been really bothered by the lack of ordering
in the HPACK headers table, making it painful to perform efficient
lookups. I'd suggest that they are sorted by (name,value) to make
it possible to perform efficient dichotomic lookups.

> The question is whether we should also backfill headers which HTTP Archive
> wouldn't see, delete headers we wish people wouldn't use, and/or insert the
> ones we hope they eventually will.  Some candidates:

That's indeed a good point.

>   *   Don't add X-Forwarded-For, but do add Forwarded

In practice, we can take both or none. After all, most QUIC requests going
through proxies will be encrypted already thus the proxy will not be able
to add these fields. For clear-text requests, the header field name is
roughly as long as the value, so there's not *that* much to save by encoding
them. And it will not change in most consecutive requests, so the dynamic
compression will be more efficient than the static one. Thus I suggest that
we only add them *if* we have enough unused slots at the end that we care
to cover a very broad set.

>   *   Remove Expires to incent the use of Cache-Control

Expires is for responses only anyway, thus it matters much less. Cache-control
can be used in both directions. I think that the technical focus on request
may make Expires disappear from the table ;-)

>      *   ...but which one to keep?

Probably just focus on the most reported ones and not try to collapse. I
suspect that we see a lot of en-us alone, and utf-8 added to some other
languages, but I could be wrong.

>   *   Add Content-Encoding and/or Accept-Encoding entries for zstd

Probably too early yet, and will not make a big difference overall (almost
only response, 4 characters value).

> There's an endless parade of bikesheds here.  As Martin has pointed out, this
> will never be perfect, so the goal is "good enough and keep going."  Any
> strong feelings about any of these before we merge it?

No real strong feeling here except about the ability to perform fast lookups.

> Also, there's been some discussion of a mechanism for selecting one of
> several static tables at the start of a connection.  In that case, the spec
> would probably define three tables (client headers, server headers [for
> servers that don't push], combined [for servers that push]) and enable future
> RFCs to define others for targeted scenarios (proxies, video playback, IoT,
> etc.).  How much does that interest folks?

I think it could be a good solution. We could also think about APIs and
various datacenter-oriented use cases (eg: webservice etc) where very fast
response and network efficiency matters. It could be a way to encourage
QUIC adoption inside the DC. The risk however is that tables defined too
late are never deployed due to interoperability concerns (unless there's
a way to know that it will be supported before encoding). Thus if some
participants are interested in optimizing for certain use cases, they should
probably provide their own tables to be merged into the standard from day 1.

Cheers,
Willy

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 24 May 2018 14:20:56 -0400

On Thu, May 24, 2018 at 05:53:14PM +0000, Roberto Peon wrote:
> One could make the lookup (more) efficient by storing the index (a
> byte at most) with the key-value pair, where the key-value pair were
> sorted via whatever sorting you'd find most efficient.  If reordering
> allows for some increased efficiency without increasing bits-on-wire,
> I'd think it seems reasonable to change.

Lookup efficiency should be a marginal consideration.  The table has
only a few dozen entries.  There are ways to compile the static table
to make lookups faster (for example, by using a perfect hash) if one
is bothered by doing a simple scan.

  - Dmitri.

---

From: Mike Bishop <[email-masked]>
Date: Thu, 24 May 2018 18:21:15 +0000

Yes, I think you need the lookup table for indices.  Alphabetical doesn't work as well, because there are two key barriers to deal with:

  *   Only the first sixteen entries can be name-referenced in a single byte.  We degraded performance in a previous draft of this table because :path wasn’t in the first sixteen entries, and the encoder that tried the updated table used two-byte name references for every request.
  *   Only the first sixty-four entries can be index-referenced in a single byte.

This implies that you want an ordering by likelihood of using the name at all, by likelihood of not indexing the value for repeat use, and by likelihood of using the name+value pair directly.

While an alphabetically-sorted list isn’t impossible within each tier, it seems easier to maintain a static map of the indices than to alphabetically index into each tier to see if the header you want is present.

I’d be open to additional sources of data to run the same query against.  Any browsers up to running an experiment and sharing the telemetry?

-----Original Message-----
From: Roberto Peon <[email-masked]>
Sent: Thursday, May 24, 2018 10:53 AM
To: Willy Tarreau <[email-masked]>; Mike Bishop <[email-masked]>
Cc: [email-masked]; HTTP Working Group <[email-masked]>
Subject: Re: QPACK and the Static Table

One could make the lookup (more) efficient by storing the index (a byte at most) with the key-value pair, where the key-value pair were sorted via whatever sorting you'd find most efficient.

If reordering allows for some increased efficiency without increasing bits-on-wire, I'd think it seems reasonable to change.

I would not trust the HTTP Archive to give a frequency analysis for real-world use. Remember that we gathered the freq data for HPACK from real-world use across a hopefully not-so-biased sample via browsers directly. If the world has changed since HPACK came out in terms of header freq (seems possible if not probable), then perhaps we should consider an update to HTTP2/HPACK as well?

I agree that perfection here isn't really needed, but I'm not sure adding items to the table arbitrarily makes sense either.

-=R

On 5/23/18, 9:42 PM, "QUIC on behalf of Willy Tarreau" <[email-masked] on behalf of [email-masked]<mailto:[email-masked][email-masked]>> wrote:

    Hi Mike,

    Cheers,

    Willy

---

From: Lucas Pardue <[email-masked]>
Date: Fri, 25 May 2018 17:46:05 +0000

If we assume that HTTP/QUIC will be bootstrapped by Alt-Svc on TCP, then a QPACK Alt-Svc entry is mainly about refreshing liveliness. So ":port" appears as a reasonable option to refresh to self, plus omission of the "ma" parameter implies a freshness of 24 hours (RFC 7838). Anecdotally, I would expect the same Alt-Svc to be sent on every response.

However, I don't think that there is any Alt-Svc reasonable general value that can be picked. We've previously discussed the use of UDP port 443. Some of that was punted to the applicability document (https://github.com/quicwg/ops-drafts/issues/26). The HTTP doc kind of skirts this by saying that any port can be used.

Is there any danger in optimising for v1 when it is anticipated that QUIC will rev quickly?

To summarise, I think a simple Alt-Svc default could cause more harm than good.

Lucas
________________________________________
From: QUIC [[email-masked]] on behalf of Martin Thomson [[email-masked]]
Sent: 24 May 2018 01:50
To: patrick mcmanus
Cc: QUIC WG; Mike Bishop; HTTP Working Group
Subject: Re: QPACK and the Static Table

-----------------------------
http://www.bbc.co.uk
This e-mail (and any attachments) is confidential and
may contain personal views which are not the views of the BBC unless specifically stated.
If you have received it in
error, please delete it from your system.
Do not use, copy or disclose the
information in any way nor act in reliance on it and notify the sender
immediately.
Please note that the BBC monitors e-mails
sent or received.
Further communication will signify your consent to
this.
-----------------------------