Subject: Issue #155: Capping header compression index values

From: James M Snell <[email-masked]>
Date: Mon, 1 Jul 2013 13:58:21 -0700

https://github.com/http2/http2-spec/issues/155

When using Literal Representations with Incremental Indexing as
defined by the current Header Compression draft, a long lived
connection could potentially end up with rather large table index
values... Specifically, every Literal-with-Incremental causes the
table index to increment by one monotonically without limit. Index
positions are represented using a variable length integer syntax that
has no upper limit, as the index position increases, the number of
bytes necessary to represent the index on the wire increases. The
result is that as the number of Literal-with-Incremental operations
increase, the efficiency of our compression will slowly but certainly
decrease.

The solution, of course, is to favor substitution indexing as much as
possible within long running connections.

One possible strategy is to use incremental indexing only until a
fixed range of index positions have been used (1...n). After that
range has been exhausted, use substitution indexing starting back from
the initial position in the range... Where this strategy might become
unworkable, however, is when items within that fixed range are
evicted. It is currently not clear in the header compression draft
whether a Literal-with-Substitution-Indexing is allowed to reuse an
index position that has previously been evicted.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 1 Jul 2013 14:22:56 -0700

On 1 July 2013 13:58, James M Snell <[email-masked]> wrote:
> values...

I don't understand what you are trying to get out of raising this issue.

The table and related mechanisms just exist.  We aren't specifying
algorithms for using these mechanisms, any more than we say what
content you put on your blog.  Some techniques will get better results
than others.

I hope that your request here doesn't imply that you are advocating a
particular compression algorithm.

---

From: James M Snell <[email-masked]>
Date: Mon, 1 Jul 2013 14:26:17 -0700

I posted the issue to track and document it. Whether or not there is
anything that can or ought to be done is to be determined.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 1 Jul 2013 14:27:21 -0700

> anything that can or ought to be done is to be determined.

I still don't know what "it" is.

---

From: James M Snell <[email-masked]>
Date: Mon, 1 Jul 2013 14:40:55 -0700

The "it" is that index values can grow without limit if the
compression implementation is not properly tuned.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 1 Jul 2013 15:35:53 -0700

> compression implementation is not properly tuned.

There is a limit.  The available space diminishes with each addition.
Assuming empty string for both name and value, the default space of
2^12 can hold only 2^7 entries before running out of space, since each
entry is assigned a 2^5 octet overhead.  At that point, old values
drop off the end as new ones arrive.  That seems manageable to me.
2^5 or 2^6 might be better, since they fit in the prefix space, but
what's an extra byte between friends?

I don't see this as a problem at all.

---

From: James M Snell <[email-masked]>
Date: Mon, 1 Jul 2013 15:40:37 -0700

I had missed the renumbering statement in the current draft. Seeing that
now the issue goes away somewhat.