Re: Feedback from first read of QUIC/HTTP draft 08

[Mikkel Fahnøe Jørgensen <[e-mail]>]

> 8. The HPACK, to be replaced, doc is hard to parse


There are three HPACK replacement proposals (neither of which is
referenced by [draft-ietf-quic-http-08]): QPACK, QCRAM, and QMIN.
Which one are you referring to?

I’m just referring to the fact that I’m aware the HPACK is not the long
term solution, but this was the document I was referring to. I have not
been looking into Q* yet.

> and it doesn't sound like it is as complicated as it reads.
> Hopefully a future QUIC equivalent would be a bit easier to
> digest.

If you offered some specific examples, I think it would be appreciated:
we want to make the documents comprehensible on the first read.


My intuition is that HPACK could largely be described by the following
text, although details may be a bit off as I haven’t digged into all the
details:

HPACK represents HTTP headers in a compact form. Every valid name string
and value string can be stored as a HPACK field. A valid name or value
string conforms to HTTP 1.1 strings without space, ‘:’ and CRLF delimited.
A name may also be a pseudo-name starting with ‘:’ for example ‘:method’
used in HTTP/2.

The fields are conceptually ordered similar to how the text representation
is ordered in HTTP 1.1 such that a similar header can be recreated after
decoding. The result of decoding a HPACK stream is exactly such a list, and
updated internal state which makes the next exchange smaller in size. This
internal state is kept in the dynamic name table discussed below.

Some header names are used often and have a dedicated encoding in a static
table. Some names are less general but may still be reused across requests,
such names can be stored in a dynamic table for reuse. And finally some
names should not compressed for security reasons or because it is not
deemed efficient. The sender (encoder) decides which form to use, but can
only choose the static form if the name is in the static table. Names are
always case insensitive.

The header values are always just explicit strings that are not compressed
(or are they? - did not get that far in the text). We refer to such a
string as ValueString.

For security reasons and implementation simplicity, the format is simple
and not extensible. Instead HPACK as a whole may be replaced by another
compression if needed. HPACK depends on the sender (encoder) sending all
operations in a specific order such that the decoder can reverse the
encoding unambiguously.

In the following the three forms of name encoding are discussed further,
followed by how the entire list is encoded.

The static table is list of known names that is a assigned an index between
1 and K, where K is the length of the static table. Each name is
represented as an integer index into this table. We call this value
StaticName.

The following may not be exactly correct, but this is how I imagine it work
from a quick skim.

The dynamic table has a fixed size which is negotiated. The size may
change, but always in a way that both sender and receiver is aware of it
and only in a way the receiver permits. If the sender grows the table
beyond the granted limit, this is a fatal error. The current size of the
dynamic table is N. The table may not use all entries. If a name is stored
in the table it is represented by the integer DynamicName which is in the
range (1 + K … N + K). The size N may be zero in which case no names are
encoded as a dynamic name. Otherwise the table is filled up such that the
first name is given the value N + K, the next name the value N + K - 1
until the table fills up. After that, the process starts over with the next
value again being N + K and so forth. The decoder has enough information to
maintain the table as it changes. The encoded issues commands to add names
to the table but does not explicitly evict names. The encoder can grow or
shrink the table with a single command. In either case the new size takes
effect once the table wraps the next time around. We refer to the dynamic
table size N as the integer DynamicTableSize.

When an encoder adds a name to the dynamic table, it does not send the name
explicitly but via a huffman compression scheme based on static huffman
codes. The net effect is a command with a bit string containing the
compressed name to be added to the dynamic table. No index information is
needed because the decoder is in sync. The encoder, by definition, does not
need to add names to static table so there is no corresponding operation.
We refer to the huffman encoded name as DynamicNameString.

Finally the name can be stored explicitly without compression. There is no
update command for this. We refer to an explicit string as ExplicitName.

The encoding is a stream of commands which we list below, followed by a
wire format representation.

PushDynamicHeader(DynamicNameSring)

ResizeDynamicTable(DynamicTableSize)

AddImplicitHeader(StaticName | DynamicName, ValueString)

AddExplicitHeader(ExplicitName, ValueString)

Done()


The encoder sends a list of commands in a very specific order. An
implementation is free to choose how it orders these commands, except
Done() comes last and AddImplicitHeader must only be called when there is a
valid entry in the table being addressed.

The decoder processes these commands in order and aborts the operation in
case of any violation. The result of the decoding process is an order list
of name/value pairs with exactly one field for each AddImplicit/Explicit
commands. In addition the decoder now potentially has a populated dynamic
table that can be reused by the next request which must be handled strictly
after the previous in order to maintain sync. If the decoder wants to
reduce or increase its dynamic table it can send this information to the
decoder via command X (TBD). This is an async operation. The decoder cannot
require the sender to go below a previous sent limit, but it can allow it
to grow larger and advise it to shrink. The initial dynamic table size is
an out of band parameter similar to the huffman table and the static table.


An example is the following HTTP1.1 header where the status line with the
GET method is replaced by HTTP/2 pseudo names:

… example to follow …

The dynamic table then looks like: ...


The Huffman encoding is the list of symbols in appendix A along with the
huffman algorithm,

The static table is the list names in appendix B, or another set of names
if agreed out of band.

The wire format of ValueString is …

The wire format of  DynamicName is …

The wire format of ExplicitString is ….

The wire format of command X header is …

Appendix...