Subject: Suggestion for simplified HTTP 2.0 header compression algorithm

From: Hans Spaak <[email-masked]>
Date: Wed, 6 Nov 2013 09:04:44 +0000

Hello,

The proposed header compression algorithm is rather complicated and we foresee that  there will be at least initially a lot of interworking problems
when different compressor and de-compressor implementations need to work together.
We experienced those problems when the equally complicated WAP1.x header compression was implemented.

Here is our proposal for simplifying how headers are compressed in HTTP/2.0.
It does not compress as hard as the currently proposed solution (if the encoder is written in a very smart way),
but it is much easier to implement.

Please have a look at it and comment.

Exchange of static headers, which are the same for one TCP connection:

The SETTINGS frame is used to transmit the static request and response headers.
The HEADERS frame is used to transmit the dynamic request and response headers.
Static headers and dynamic headers are combined in the following way:

1.       Emit the dynamic headers.

2.       Emit the static headers whose header names are not present in the dynamic headers.

                         Client                        Server
                           |                             |
                           |SETTINGS                     |
                           | - static request headers    |
                           |   (:method, :host,          |
                           |    User-Agent, Accept, ...)   |
                           |---------------------------->| Store static request
                           |                             | headers for connection
                           |SETTINGS                     |
                           | - static response headers   |
                           |   (:status 200, Server, ...)  |
                           |                             |
     Store static response |<----------------------------|
    headers for connection |                             |
                           |HEADERS                      |
                           | - dynamic request headers   |
                           |   (:path, ...)                |
                           |---------------------------->| Combine static and
                           |                             | dynamic request
                           |                             | headers.
                           |                             | Dynamic headers have
                           |                             | precedence over static
                           |                             | headers.
                           |HEADERS                      |
                           | - dynamic response headers  |
                           |   (Content-Type, Age, ...)    |
        Combine static and |<----------------------------|
 dynamic response headers. |                             |
      Dynamic headers have |                             |
    precedence over static |                             |
                  headers. |                             |

Coding of header names and values:

Standard headers are coded in the following way:
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 | Index of standard header  |
+---+---------------------------+
|  Value length (8+)            |
+-------------------------------+
| Value String (Length octets)  |
+-------------------------------+

Non-standard headers are coded in the following way:
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | Name Length (7+)          |
+---+---------------------------+
| Name String (Length octets)   |
+-------------------------------+
| Value length (8+)             |
+-------------------------------+
| Value String (Length octets)  |
+-------------------------------+

Indices for standard headers (example only):

0 :scheme
1 :host
2 :path
3 :method
4 :status
5 accept
6 accept-charset
7 accept-encoding
8 accept-language
9 age
10 cache-control
11 content-length
...

Br,

Hans Spaak
Ericsson AB
E-mail: [email-masked]<mailto:[email-masked]>
Web: www.ericsson.com<http://www.ericsson.com>

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 06 Nov 2013 09:16:19 +0000

In message <[email-masked]>, H
ans Spaak writes:

>The proposed header compression algorithm is rather complicated [...]

>Here is our proposal for simplifying how headers are compressed in HTTP/2.0

Any proposal which is simpler has my support.

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: Amos Jeffries <[email-masked]>
Date: Wed, 06 Nov 2013 23:38:33 +1300

On 6/11/2013 10:04 p.m., Hans Spaak wrote:
>
> Hello,
>
> The proposed header compression algorithm is rather complicated and we 
> foresee that there will be at least initially a lot of interworking 
> problems
> It does not compress as hard as the currently proposed solution (if 
> the encoder is written in a very smart way),
>
> _Exchange of static headers, which are the same for one TCP connection:_
>
> 1.Emit the dynamic headers.
>
> 2.Emit the static headers whose header names are not present in the 
> dynamic headers.
>

Your diagram shows those in reverse order. I assume your diagram is the 
right version as it makes more sense than re-transmitting static headers 
constantly.

> | User-Agent, Accept, …) |
>
> | (:status 200, Server, …) |
>
> | |
>
> | (:path, …) |
> | (Content-Type, Age, …) |
>

Sounds familiar....
http://tools.ietf.org/html/draft-tarreau-httpbis-network-friendly-00#section-2.2

Slightly different frame and grouping names though.

> _Coding of header names and values:_
>

... and the header encoding can be made more efficient without affecting 
transport encrypt/decrypt speed:
http://tools.ietf.org/html/draft-tarreau-httpbis-network-friendly-00#section-2.1.5

Amos

---

From: Michael Sweet <[email-masked]>
Date: Wed, 06 Nov 2013 08:02:37 -0500

Hans,

I am all for simplifying the current header compression algorithm, which is growing needlessly complicated IMHO as people try to achieve ever greater compression ratios without regard to implementation complexity or interoperability concerns.

That said, I don’t like the idea of putting headers in the settings frame since it doesn’t play well with proxies - clients need to be able to direct requests to multiple origin servers and proxies need to be able to consolidate multiple client connections onto a single connection to the origin server.  (it will be hard enough for the current header compression scheme to work for that, but at least it is possible)

On Nov 6, 2013, at 4:04 AM, Hans Spaak <[email-masked]> wrote:

> …
> E-mail: [email-masked]
> Web: www.ericsson.com
>  
>  

_______________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: James M Snell <[email-masked]>
Date: Wed, 6 Nov 2013 05:54:17 -0800

Throughout this process I've gone through several iterations of a
decidedly less complicated header encoding mechanism [1] and have
consistently come up against the point of view that achieving the best
possible compression ratio appears to be the single most important
deciding factor. Whenever I have raised concerns about the level of
complexity, I've been told that the tooling will handle it so it's not
a problem.

[1] http://tools.ietf.org/html/draft-snell-httpbis-bohe-13

My personal opinion is that achieving the best possible compression
ratio should not be the sole deciding factor and that the currently
proposed mechanism is far into the "trying to be way too clever" range
and introduces far too much unjustified additional complexity. In
other words, I'm very -1 on it but, thus far, I appear to be in the
minority. (and yes, FWIW, I have taken the time to implement the
current scheme so I'm not just speaking out of some theoretical
concern).

- James

On Wed, Nov 6, 2013 at 5:02 AM, Michael Sweet <[email-masked]> wrote:
> Hans,
>
> I am all for simplifying the current header compression algorithm, which is
> growing needlessly complicated IMHO as people try to achieve ever greater
> compression ratios without regard to implementation complexity or
> interoperability concerns.
>
> That said, I don’t like the idea of putting headers in the settings frame
> since it doesn’t play well with proxies - clients need to be able to direct
> requests to multiple origin servers and proxies need to be able to
> consolidate multiple client connections onto a single connection to the
> origin server.  (it will be hard enough for the current header compression
> scheme to work for that, but at least it is possible)
>
>
>                            |                             | Dynamic headers
> have

---

From: Michael Sweet <[email-masked]>
Date: Wed, 06 Nov 2013 10:07:47 -0500

James,

I think I’ve commented in the past that I prefer your proposed encoding - my only nit is the timestamp encoding due to the requirement to support large integers…

In my mind HTTP/2.0’s big killer feature is support for multiple, parallel requests over a single connection.  This eliminates the largest source of latency for web clients - connection setup time, which can be significant for encrypted connections - and it potentially allows web servers and clients to do more work with less resources.

Header compression is only important for getting the initial request into a single packet to avoid the RTT, but once you have reached that goal any further compression is, IMHO, not (as) important.  If we keep adding more and more state that needs to be maintained by both ends, we risk losing all of the resource savings (above) and making it less likely to be implemented at all.

---

From: James M Snell <[email-masked]>
Date: Wed, 6 Nov 2013 08:32:10 -0800

> I think I’ve commented in the past that I prefer your proposed encoding - my only nit is the timestamp encoding due to the requirement to support large integers…

I played around with quite a few alternatives and they all came about
to be about the same number of bytes, so I opted for the least
complicated option. I'm open to other suggestions but, at some point,
we just need to get the barn painted and move on ;-)

>[snip]

+1 ... or worse, implemented incorrectly.

- James

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 6 Nov 2013 09:11:27 -0800

Hi Hans,

As you’ve seen, complexity of header compression is a shared concern; in our latest drafts, we’ve been significantly simplifying HPACK.

Do you have any running code to share?

Regards,

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

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 6 Nov 2013 09:16:39 -0800

Hi James,

On 6 Nov 2013, at 5:54 am, James M Snell <[email-masked]> wrote:

> deciding factor.

I’m surprised to hear you say that. In all of the discussions I’ve been a part of, the emphasis has been on balancing compression efficiency and complexity, with a bias towards simplicity (and a constraint of security). Pretty much everyone acknowledges that HPACK is more complex than we’d like, but we don’t yet have an alternate proposal that’s gathered more interest.

The concerns I’ve heard about BOHE are that it requires knowledge of individual headers when sending, and that it adds complexity. We haven’t yet ruled it out; the issue you raised is still open, but the approach so far has been to see how well delta coding works before considering adding other techniques or replacing it.

We’re just getting starting to get that experience with HPACK.

> Whenever I have raised concerns about the level of

Who told you that? I haven’t heard that point of view expressed at all.

---

From: James M Snell <[email-masked]>
Date: Wed, 6 Nov 2013 09:28:29 -0800

> I’m surprised to hear you say that. In all of the discussions I’ve been a part of, the emphasis has been on balancing compression efficiency and complexity, with a bias towards simplicity (and a co…

Just a personal opinion, really. Take it for what it's worth.

> The concerns I’ve heard about BOHE are that it requires knowledge of individual headers when sending, and that it adds complexity. We haven’t yet ruled it out; the issue you raised is still open, b…

FWIW, it does not *require* knowledge of individual headers, but does
allow a sender that does happen to have such knowledge to leverage
that to encode more efficiently. Once encoded, the encoding is
self-describing with very clear processing and backwards
compatibility.

Also note, my proposal comes in two parts: a header encoding and a
value encoding. They are distinct and do not necessarily depend on one
another.

[snip]

Note that I've backed off pushing on the bohe option while the work on
HPACK is ongoing. I stated my concerns, offered an alternative, put it
on the table, then backed off to see how things develop. Personally,
HPACK is still far too complicated for my taste, but that's just one
opinion out of many. Again, take it for what it's worth.

- James

---

From: Peter Lepeska <[email-masked]>
Date: Wed, 6 Nov 2013 13:01:37 -0500

Do you have any numbers on performance of BOHE? Be nice to get performance
numbers vs HPACK for the same max memory setting and the same HTTP header
data set.

Peter

On Wednesday, November 6, 2013, James M Snell wrote:

> On Wed, Nov 6, 2013 at 9:16 AM, Mark Nottingham <[email-masked]<javascript:;>>
> wrote:
> >[snip]
> > I’m surprised to hear you say that. In all of the discussions I’ve been
> a part of, the emphasis has been on balancing compression efficiency and
> complexity, with a bias towards simplicity (and a constraint of security).
> Pretty much everyone acknowledges that HPACK is more complex than we’d
> like, but we don’t yet have an alternate proposal that’s gathered more
> interest.
> >
>
> > The concerns I’ve heard about BOHE are that it requires knowledge of
> individual headers when sending, and that it adds complexity. We haven’t
> yet ruled it out; the issue you raised is still open, but the approach so
> far has been to see how well delta coding works before considering adding
> other techniques or replacing it.
> >
>
> >>> when different compressor and de-compressor implementations need to
> work
> >>> together.
> >>> We experienced those problems when the equally complicated WAP1.x
> header
> >>> compression was implemented.
> >>>
> >>>
> >>>
> >>> 2.       Emit the static headers whose header names are not present in
> the
> >>> dynamic headers.
> >>>
> >>>
> >>>
> >>>                         Client                        Server
> >>>
> >>>                           |                             |
> >>>
> >>>                           |SETTINGS                     |

---

From: James M Snell <[email-masked]>
Date: Wed, 6 Nov 2013 10:04:34 -0800

I generated some last spring that would be out of date now. I need to
update my impl and re-generate the numbers... just haven't had a great
opportunity to do so yet, and with primary focus on hpack, there
hasn't been a strong justification yet for allocating the time.

On Wed, Nov 6, 2013 at 10:01 AM, Peter Lepeska <[email-masked]> wrote:
>> > Pretty much everyone acknowledges that HPACK is more complex than we’d like,
>> > but we don’t yet have an alternate proposal that’s gathered more interest.
>> >
>>
>> > individual headers when sending, and that it adds complexity. We haven’t yet
>> > ruled it out; the issue you raised is still open, but the approach so far
>> > has been to see how well delta coding works before considering adding other
>> > techniques or replacing it.
>> >
>>
>> >>> encoder is written in a very smart way),
>> >>>

---

From: Peter Lepeska <[email-masked]>
Date: Wed, 6 Nov 2013 13:46:27 -0500

Okay thanks. I really like the idea in general and I think it could be
further optimized without adding a lot of complexity. And, on the other
hand, could be made still simpler without sacrificing a lot of performance.

Peter

On Wed, Nov 6, 2013 at 1:04 PM, James M Snell <[email-masked]> wrote:

> >> >>> The SETTINGS frame is used to transmit the static request and
> response
> >> >>> headers.
> >> >>>
> >> >>> The HEADERS frame is used to transmit the dynamic request and
> response
> >> >>> headers.
> >> >>>