Subject: Alternative Header Compression Update..

From: James M Snell <[email-masked]>
Date: Tue, 9 Jul 2013 17:40:02 -0700

All,

Even tho we decided at the face-to-face to move forward with the
header compression draft as the starting point with header compression
in http/2 for the implementation draft, I definitely remain skeptical
of the overall design of the scheme. I have voiced my reservations in
the past and after implementing the current header compression scheme,
my reservations about it's design remain.

Combining elements of my previous explorations here with ideas from
the current header compression draft, I have posted another update to
the "Stored Header Encoding" draft.

  http://www.ietf.org/id/draft-snell-httpbis-bohe-11.txt

This details an alternative scheme that ditches the differential
encoding and the reference set, uses a fixed range of header table
indices (0x00-FF), and uses a least-recently-written eviction strategy
without renumbering. This approach is significantly less complicated
to implement at the cost of only a small handful of additional bytes
on the wire.

- James

---

From: Michael Sweet <[email-masked]>
Date: Wed, 10 Jul 2013 09:09:34 -0400

James,

On Jul 9, 2013, at 8:40 PM, James M Snell <[email-masked]> wrote:
> ...

Actually, I think the typed encoding will probably yield enough savings to offset any increase in size, for example the date header going from 29 octets to ~6 in the variable integer encoding (or 8/11 for the RFC 2579 encoding - see below).

I like the 256-entry single header table approach.  Of course, I have some feedback... :)

1. Would be nice if you could just include the Unsigned Variable Length Integer Syntax section from the other header compression draft wholesale so this draft stands on its own. Add a notice at the beginning "(This is copied from draft-ietf-httpbis-header-compression-NN)" so people know it is the same encoding.  Then the reference to it becomes informative.

2. Would also be nice to use the same figure format as the compression and http2 drafts... (see below)

3. Representing timestamps as milliseconds since the traditional UNIX epoch is problematic since it requires support for large integers (at least 42 bits to get us to the traditional 2038 end year, more if you want to keep going past then...) and AFAIK isn't widely used in standards for actual representation of a date/time. RFC 2579 defines a DateAndTime format that is 8 (UTC) or 11 (local time) octets long and is easy to map to/from typical OS APIs without the use of large integers. Granted, it doesn't give you more than 10ths of seconds, but I think that should be enough for HTTP. (We use this format in IPP - I'd rename "Timestamp" to "DateAndTime" if you decide to make this change...)

4. I'm not super-keen on grouping the headers into 4 bins ahead of time, since that increases encoder storage requirements.  Also, there isn't a way to just replace the value for an existing indexed header in your current draft.  Perhaps a hybrid approach where the indexed representation can have 1-to-64 indexes and the others encode a single name/value?  Something like this:

    Non-Indexed Literal Representation
    (Name Length > 0)

      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    | 0   0 |   Name Length (6+)    |
    +-------+-----------------------+
    | Name String                   |
    +---+---+---+-------------------+
    | Value Type| Value Length (5+) |
    +-----------+-------------------+
    | Value String                  |
    +-------------------------------+

    Indexed Literal Representation
    (Name Length > 0)

      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    | 0   1 |   Name Length (6+)    |
    +-------+-----------------------+
    | Name String                   |
    +---+---+---+-------------------+
    | Value Type| Value Length (5+) |
    +-----------+-------------------+
    | Value String                  |
    +-------------------------------+

    Indexed Representation
    (Count = 1 to 64)

      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    | 1   0 |   Count - 1 (6)       |
    +-------+-----------------------+
    | Name/Value Index 1 (8)        |
    ...                          ....
    | Name/Value Index N (8)        |
    +-------------------------------+

    Indexed Literal Replacement Representation
    (Name Length > 0 to replace name and value)

      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    | 1   1 |   Name Length (6+)    |
    +-------+-----------------------+
    | Name String                   |
    +-------------------------------+
    | Index (8)                     |
    +---+---+---+-------------------+
    | Value Type| Value Length (5+) |
    +-----------+-------------------+
    | Value String                  |
    +-------------------------------+

    Indexed Literal Replacement Representation
    (Name Length = 0 to just replace value)

      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    | 1   1 | 0   0   0   0   0   0 |
    +-------+-----------------------+
    | Index (8)                     |
    +---+---+---+-------------------+
    | Value Type| Value Length (5+) |
    +-----------+-------------------+
    | Value String                  |
    +-------------------------------+

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: James M Snell <[email-masked]>
Date: Wed, 10 Jul 2013 09:05:53 -0700

> James,
[snip]
> Actually, I think the typed encoding will probably yield enough savings to offset any increase in size, for example the date header going from 29 octets to ~6 in the variable integer encoding (or 8…

The type codecs definitely save quite a bit with highly variable
header fields that tend to get sent as literals often (date,
last-modified, content-length, etc). For fairly static header fields,
the difference is minimal for any individual header. Where you start
to see the gap widen is over long running connections, where the
average number of bits on the wire trends higher. It's worth it,
however, IMHO.

> 2. Would also be nice to use the same figure format as the compression and http2 drafts... (see below)

Will do both in the next iteration.

> 3. Representing timestamps as milliseconds since the traditional UNIX epoch is problematic since it requires support for large integers (at least 42 bits to get us to the traditional 2038 end year,…

Millisecond precision has been on the HTTP wish-lists of many
application developers for a very long time, including mine and I
believe the additional requirements are worth it. That said, I've been
considering an alternative approach that is based on a single byte era
prefix. This would encode the timestamp into two parts, a 8-bit prefix
followed by a uvarint <= (2^32)-1. For now, I just picked a format
that would work, with the intent of revisiting it once typed codecs
come up for formal discussion after the august interop event.

> 4. I'm not super-keen on grouping the headers into 4 bins ahead of time, since that increases encoder storage requirements.  Also, there isn't a way to just replace the value for an existing indexe…

A small amount of buffering is required with the grouping approach,
but the encoder controls how much. An encoder that chooses less
buffering would see a bit more encoding overhead. An encoder could
choose to encode each header individually, without grouping, at the
cost of one additional octet per header.

The Indexed Literal Replacement can be used to replace just the value
of an existing header... for instance, suppose I have an existing
entry at position #1 with name="foo", value=1. I want to keep the same
name but replace the value with 2, I would send:

  C0 01 20 01 02

The first octet identifies this as an Indexed Literal Replacement
group with one item.
The second octet identifies the Index position being replaced
The third specifies that the value is an Integer, with the five-least
significant bits set to zero, indicating that a name index reference
is provided by the fourth octet
The fourth octet is the name index reference. We're pointing the index
#01 (the same index that's being replaced)
The fifth octet provides the new value.

Because the name resolution is done before the replacement, the name
is reused and just the value is replaced.

- James

---

From: Mike Bishop <[email-masked]>
Date: Wed, 10 Jul 2013 18:22:40 +0000

One advantage of removing the reference set is that Gabor's streaming proposal can be taken even further -- HEADERS frames from different streams can be interleaved with other frame types, because the headers they add to a stream are emitted as the frame is processed and the header table is always in a consistent state.

Whether this would be desirable or useful, however, seems unclear.  HEADERS frames must still be processed in order for compression views to be consistent, and for HTTP semantics must precede any DATA on the same stream.

Typo in your doc, bottom of p.3:  Indexed and Indexed Literal have the same prefix code.  Per 3.5, Indexed Literal should be 11.

-----Original Message-----
From: James M Snell [mailto:[email-masked]] 
Sent: Tuesday, July 9, 2013 5:40 PM
To: [email-masked]
Subject: Alternative Header Compression Update..

All,

Even tho we decided at the face-to-face to move forward with the header compression draft as the starting point with header compression in http/2 for the implementation draft, I definitely remain skeptical of the overall design of the scheme. I have voiced my reservations in the past and after implementing the current header compression scheme, my reservations about it's design remain.

Combining elements of my previous explorations here with ideas from the current header compression draft, I have posted another update to the "Stored Header Encoding" draft.

This details an alternative scheme that ditches the differential encoding and the reference set, uses a fixed range of header table indices (0x00-FF), and uses a least-recently-written eviction strategy without renumbering. This approach is significantly less complicated to implement at the cost of only a small handful of additional bytes on the wire.

- James

---

From: Michael Sweet <[email-masked]>
Date: Wed, 10 Jul 2013 14:29:47 -0400

James,

> come up for formal discussion after the august interop event.

*If* millisecond precision is needed I would still prefer to see a real date + time encoding and not "seconds since an epoch".

---

From: James M Snell <[email-masked]>
Date: Wed, 10 Jul 2013 11:31:00 -0700

> One advantage of removing the reference set is that Gabor's streaming proposal can be taken even further -- HEADERS frames from different streams can be interleaved with other frame types, because…

Yes... streaming encoding is possible in my stored header encoding
approach as well. It definitely makes for a much nicer approach, IMHO.

> Whether this would be desirable or useful, however, seems unclear.  HEADERS frames must still be processed in order for compression views to be consistent, and for HTTP semantics must precede any D…

Well, if nothing else, it simplifies the encoding and decoding process
and makes it significantly easier to achieve O(1) performance for most
of the operations.

> Typo in your doc, bottom of p.3:  Indexed and Indexed Literal have the same prefix code.  Per 3.5, Indexed Literal should be 11.

Thx.. will be fixed in the next iteration :-)

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 11 Jul 2013 15:13:56 +1200

> Whether this would be desirable or useful, however, seems unclear.  HEADERS frames must still be processed in order for compression views to be consistent, and for HTTP semantics must precede any D…

IMHO this is both desirable and useful.

Consider a load balancer which receives multiple hundreds of streams 
near simultaneously from as many servers and needs to deliver those 
frames to the one client connection. Being able to encode and serialize 
the frames as they arrive regardless of order means the balancer is not 
required to hold anything in queues waiting for followup frames no 
matter how the server read() are interleaved.

The clause mandating that HEADERS #h1 and HEADERS #h2 of a 2-block 
headers (stream #s1) be sequentially serialized on the wire is just 
adding needless complexity. Any compressor state changes which HEADERS 
of a separate stream (#s2) will cause if inserted between those #h1 and 
#h2 will be changes that would occur anyway if it were scheduled last 
after #h2. We also gain the potential benefit where HEADERS #1 of each 
stream might share some detail (long "Cookie"? long ":path"?) which 
otherwise could be evicted by HEADERS #h2 on stream #s1 and thus saving 
even more bandwidth on stream #s2.

Amos

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 11 Jul 2013 16:55:18 +0000

James,

The 256-entry table acting as a circular buffer is probably a cleaner solution than what is currently in the compression spec.

For the low-level encoding of entries, I think I prefer encoding each entry separately using a few bits to signal which encoding is used. This is much simpler to use, and I would think slightly more compact.

Hervé.

> Sent: mercredi 10 juillet 2013 02:40
> To: [email-masked]
> Even tho we decided at the face-to-face to move forward with the header
> compression draft as the starting point with header compression in http/2 for
> the implementation draft, I definitely remain skeptical of the overall design
> of the scheme. I have voiced my reservations in the past and after
> implementing the current header compression scheme, my reservations
> about it's design remain.
> 
> Combining elements of my previous explorations here with ideas from the
> current header compression draft, I have posted another update to the
> "Stored Header Encoding" draft.
> 
> This details an alternative scheme that ditches the differential encoding and
> the reference set, uses a fixed range of header table indices (0x00-FF), and
> uses a least-recently-written eviction strategy without renumbering. This
> approach is significantly less complicated to implement at the cost of only a
> small handful of additional bytes on the wire.
> 
> - James

---

From: James M Snell <[email-masked]>
Date: Thu, 11 Jul 2013 10:32:20 -0700

Well, looking at Indexed references currently, the 256-entry table
means that every index position can be represented using a single
octet. If we represent each entry separately that means we would end
up always using two bytes to represent index positions > 127. If we
look at an example: Let's suppose we want to specify index references
for items 20, 40, 130, 140, 150 and 160...

Separately encoding using the current header compression scheme would be:

  94 a8 ff 03 ff 0d ff 17 ff 21

Using the grouped approach, we would encode as...

  86 14 28 82 8c 96 a0

Encoders are given the choice of whether to use the groups or not. If
the groups are not used, we end up encoding with 2 bytes per indexed
reference which means only two additional bytes relative to encoding
separately:

  80 14 80 28 80 82 80 8c 80 96 80 a0

While this is not as compact as the first option, I generally prefer
it because I don't need to worry about the variable length integer
encoding when I know my index position will never exceed FF.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Jul 2013 10:52:58 -0700

On 11 July 2013 10:32, James M Snell <[email-masked]> wrote:
> up always using two bytes to represent index positions > 127.

That's not valuable information until I know the typical table size
that I might like to maintain.  127 actually seems like a pretty big
number to me.