Subject: Header Compression

From: RUELLAN Herve <[email-masked]>
Date: Wed, 5 Jun 2013 19:17:27 +0000

Roberto and I have been discussing for some time and we have created a joint proposal for Header Compression.

The resulting spec is available at:
https://github.com/http2/compression-spec

The main features of this proposal are:
- One single table for indexing headers as (name, value) pairs.
- HeaderDiff-based serialization (indexed header, literal header with either no indexing, addition indexing, or replacement indexing).
- Delta2-based diff between two successive header sets.
- Possibility of bounding table size.
- Least recently written eviction strategy when an insertion cause table size limit to be reached.

We will present it in details at the next interim meeting. Until then, all questions and comments are welcome.

Hervé.

---

From: James M Snell <[email-masked]>
Date: Wed, 5 Jun 2013 12:31:49 -0700

At first read, this definitely looks like an improvement. I will be
taking another pass over the bohe draft before next week and will be
working on side-by-side implementations of both bohe and this updated
proposal in time for next weeks face to face.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 5 Jun 2013 12:37:20 -0700

> Roberto and I have been discussing for some time and we have created a joint proposal for Header Compression.

Excellent.  Can you please submit an internet draft?  It might help to
have something stable to reference.  (And I think that the IETF
process boffins might be appeased by this too.)

---

From: Ryan Hamilton <[email-masked]>
Date: Wed, 5 Jun 2013 12:59:52 -0700

Is there a rendered version of the XML file available?

On Wed, Jun 5, 2013 at 12:17 PM, RUELLAN Herve
<[email-masked]>wrote:

> - HeaderDiff-based serialization (indexed header, literal header with
> either no indexing, addition indexing, or replacement indexing).

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 6 Jun 2013 10:35:55 +1000

Yes, what Martin said. Sorry if I didn't make that clear before.

Cheers,

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

---

From: Yoav Nir <[email-masked]>
Date: Thu, 6 Jun 2013 06:17:38 +0000

I've sent a pull request. For now, you can find it at:
https://github.com/yoavnir/compression-spec/blob/7f67f0dbecdbe65bc22f3e3b57e2d5adefeb08dd/compression-spec.txt

Yoav

On Jun 5, 2013, at 10:59 PM, Ryan Hamilton <[email-masked]<mailto:[email-masked]>> wrote:

On Wed, Jun 5, 2013 at 12:17 PM, RUELLAN Herve <[email-masked]<mailto:[email-masked]>> wrote:
Roberto and I have been discussing for some time and we have created a joint proposal for Header Compression.

Hervé.

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 6 Jun 2013 11:43:16 +0000

Yes there are now both HTML and txt version available:
http://http2.github.io/compression-spec/compression-spec.html
http://http2.github.io/compression-spec/compression-spec.txt

Hervé.

> -----Original Message-----
> From: Ryan Hamilton [mailto:[email-masked]]
> Sent: mercredi 5 juin 2013 22:00
> To: RUELLAN Herve
> Cc: [email-masked]
> Subject: Re: Header Compression
> 
> 	Roberto and I have been discussing for some time and we have
> created a joint proposal for Header Compression.
>

---

From: Martin Thomson <[email-masked]>
Date: Thu, 6 Jun 2013 09:45:40 -0700

> http://http2.github.io/compression-spec/compression-spec.txt

Could you please visit https://datatracker.ietf.org/idst/upload.cgi
and go through the motions for us.  It's a procedural matter that
shouldn't take more than a couple of minutes.

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 8 Jun 2013 00:32:34 +0900

Hi,

> questions and comments are welcome.

I have a question about "reference set of headers" in section 3.3.
Differential Coding.
It seems that reference set of headers are only referred in this section
and I failed to see how it works.
I may be wrong but I don't see it in Appendix B. Example. It only refers to
the update to the header table.
Is the reference set of headers equal to header table? It seems it is not.
Could you add each state of "reference set of headers" and its working set
in the example so that the reader
can understand how it works? Sorry if this is the silly question, but it
might help the reader like me.

Best regards,

Tatsuhiro Tsujikawa

---

From: James M Snell <[email-masked]>
Date: Sun, 9 Jun 2013 13:26:15 -0700

All, I've updated the Stored Header Encoding (aka bohe) draft...

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

The main change is to the typed value encoding (switch to a 3-bit
identifier rather than 2-bit), and a few examples.

This draft ought to be viewed as an alternative to the joint header
compression draft Herve and Roberto have proposed (still waiting on
the I-D to be published for that one tho). There are a number of
distinct differences between the approaches:

1. This approach does not have the "differential encoding". This means
that the compression ratio is slightly worse but is far less
complicated to implement.
2. This approach includes the typed value codecs. Yes, the typed
values have not been considered to be a priority thus far but they are
built in to this approach and offer significant improvements to
encoding size independent of the compression ratio.
3. This approach includes a Huffman-encoding for text headers that
supports arbitrary UTF-8 codepoints
4. This approach uses a smaller dynamic storage range than the
alternative which trades slightly less compression efficiency for
fewer (and easier) state management requirements by the endpoints.
5. Of much lower priority at this point in time, but worth noting...
As part of the typed value codecs, this naturally provides for
multiple values per header, allowing for interesting new possibilities
such as http://tools.ietf.org/html/draft-snell-httpbis-mget-00

- James

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 11 Jun 2013 14:05:25 +0000

I just did it :
http://www.ietf.org/id/draft-ruellan-http-header-compression-00.txt

Hervé.

> From: Martin Thomson [mailto:[email-masked]]
> Sent: jeudi 6 juin 2013 18:46
> To: RUELLAN Herve
> Cc: Ryan Hamilton; [email-masked]
> and go through the motions for us.  It's a procedural matter that shouldn't
> take more than a couple of minutes.

---

From: Ted Hardie <[email-masked]>
Date: Tue, 11 Jun 2013 09:33:43 -0700

> http://www.ietf.org/id/draft-ruellan-http-header-compression-00.txt
Hi Herve,

A couple of quick comments.  First, for the TODO in your security
considerations section, I think you should probably expand on the text in
the overview, which describes the attack on Deflate and unpack why the
current scheme is resistant to similar attacks.  Second, the document
describes substitution and insertion, but does not describe deletion.   If
a party wishes to remove a header (note:  not change to a null value) is
this possible and, if so, what's the process?

regards,

Ted Hardie

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 17 Jun 2013 16:35:42 +0000

Hi,

This is not a silly question: I updated the example to quickly and forgot to take into account the diff encoding of header sets. I will correct it in a future version.

Thanks for noticing this.

Hervé.
________________________________
From: Tatsuhiro Tsujikawa [[email-masked]]
Sent: Friday, June 07, 2013 17:32
To: RUELLAN Herve
Cc: [email-masked]
Subject: Re: Header Compression

Hi,

On Thu, Jun 6, 2013 at 4:17 AM, RUELLAN Herve <[email-masked]<mailto:[email-masked]>> wrote:
Roberto and I have been discussing for some time and we have created a joint proposal for Header Compression.

I have a question about "reference set of headers" in section 3.3. Differential Coding.
It seems that reference set of headers are only referred in this section and I failed to see how it works.
I may be wrong but I don't see it in Appendix B. Example. It only refers to the update to the header table.
Is the reference set of headers equal to header table? It seems it is not.
Could you add each state of "reference set of headers" and its working set in the example so that the reader
can understand how it works? Sorry if this is the silly question, but it might help the reader like me.

Best regards,

Tatsuhiro Tsujikawa

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 17 Jun 2013 16:43:03 +0000

Hi Ted,

First, the TODO for the security considerations section was put here because I believed the header compression spec would be quickly integrated into the main HTTP/2.0 spec. This will not be the case (it will be referenced from the main spec), therefore, I will do the TODO.

Second, it is a design choice not to have deletion: the mean of removing a header is to replace it with a new one. Another possibility is to use the automatic dropping of headers to remove the headers that were the oldest to be added to the table (see penultimate paragraph of section 3.1 Header Table).

Hervé.
________________________________
From: Ted Hardie [[email-masked]]
Sent: Tuesday, June 11, 2013 18:33
To: RUELLAN Herve
Cc: Martin Thomson; Ryan Hamilton; [email-masked]
Subject: Re: Header Compression

On Tue, Jun 11, 2013 at 7:05 AM, RUELLAN Herve <[email-masked]<mailto:[email-masked]>> wrote:
I just did it :
http://www.ietf.org/id/draft-ruellan-http-header-compression-00.txt

Hervé.

Hi Herve,

A couple of quick comments.  First, for the TODO in your security considerations section, I think you should probably expand on the text in the overview, which describes the attack on Deflate and unpack why the current scheme is resistant to similar attacks.  Second, the document describes substitution and insertion, but does not describe deletion.   If a party wishes to remove a header (note:  not change to a null value) is this possible and, if so, what's the process?

regards,

Ted Hardie

> From: Martin Thomson [mailto:[email-masked]<mailto:[email-masked]>]
> Cc: Ryan Hamilton; [email-masked]<mailto:[email-masked]>
> On 6 June 2013 04:43, RUELLAN Herve <[email-masked]<mailto:[email-masked]>> wrote:

---

From: Ted Hardie <[email-masked]>
Date: Thu, 20 Jun 2013 15:57:52 -0700

On Mon, Jun 17, 2013 at 9:43 AM, RUELLAN Herve
<[email-masked]>wrote:

>
> Second, it is a design choice not to have deletion: the mean of removing a
> header is to replace it with a new one. Another possibility is to use the
> automatic dropping of headers to remove the headers that were the oldest to
> be added to the table (see penultimate paragraph of section 3.1 Header
> Table).
>
>
Sorry for the delay in responding.  Just to make sure I understand:

I have a header "Example: ".  It's in position 3 in the index.  I want to
remove "Example: ".  To do so, I update position 3 with a new header, say,
"Fleen: ".  The Fleen header can be a no-op, a duplicate of another header,
or something I care about now and did not before.

Is that about right?

If so, I don't think the draft is clear on this point.   I think making an
explicit statement that there is no "delete" operation but that a similar
aim can be accomplished by updating an index position with a new header,
including a no-op header, would be useful.

regards,

Ted Hardie

> Hervé.
>  ------------------------------
> *From:* Ted Hardie [[email-masked]]
> *Sent:* Tuesday, June 11, 2013 18:33
> *To:* RUELLAN Herve
> *Cc:* Martin Thomson; Ryan Hamilton; [email-masked]
> *Subject:* Re: Header Compression
>
>  On Tue, Jun 11, 2013 at 7:05 AM, RUELLAN Herve <
> [email-masked]> wrote:
>
>> I just did it :

---

From: Roberto Peon <[email-masked]>
Date: Fri, 21 Jun 2013 15:51:34 -0700

I think that you are perhaps confused between deleting something from the
state and deleting something from the headers.

In the former case it is accomplished by replacing an entry with another.
In the latter, it is done by referencing that entry again with an indexed
instruction, causing it to be removed from the set of 'active' headers.

Or, I could be the confused one :)

-=R
On Jun 20, 2013 3:59 PM, "Ted Hardie" <[email-masked]> wrote:

> On Mon, Jun 17, 2013 at 9:43 AM, RUELLAN Herve <[email-masked]
> > wrote:
>
>>
>> Second, it is a design choice not to have deletion: the mean of removing
>> a header is to replace it with a new one. Another possibility is to use the