Subject: SETTINGS_HEADER_TABLE_SIZE and ACK

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 18 Oct 2013 21:31:13 +0900

SETTINGS_HEADER_TABLE_SIZE is used to inform the size of header
table to the other endpoint. Since the size of header table of
the decoder side has to be matched to the one in the encoder
side (otherwise, header table out-of-sync on eviction or
out-of-bound index), the received peer may not want to accept the
larger buffer size due to whatever reason (e.g., resource
constraints or variable buffer size is not implemented, etc).

The HPACK-03 has a text to allow the receiver to choose smaller
values in the acknowledgement, but now SETTINGS with ACK flags
must not have any settings value, the peer is forced to accept
the offer.

The SETTINGS_HEADER_TABLE_SIZE is special among the other
settings. The others affect the receiver's capability, but it can
regulate itself not to use more resources it wants (e.g.,
SETTINGS_MAX_CONCURRENT_STREAMS is informed as 500, but the
receiver only uses 100). For SETTINGS_HEADER_TABLE_SIZE, there is
no way but to just obey the informed value.

Best regards,
Tatsuhiro Tsujikawa

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 18 Oct 2013 16:03:47 +0000

The sender can use only a part of the header table.
For example, with a SETTINGS_HEADER_TABLE_SIZE of 4k, it may use only 2k for storing entries.
The receiver will have a 4k table, storing more entries than the sender. These entries stored only by the receiver are not a problem, as the sender will never refer to them, but only to those it has in its table.
There is a difficulty to access the entries from the static table: to know the index of the first entry in the static table, the sender needs to know how many entries are present in the whole table of the receiver. It can manage this by tracking the size of the entries in the part it doesn't use: this allows it to evict entries from the table as would the receiver, and therefore to know how many entries are in the header table.

Hervé.

> -----Original Message-----
> From: Tatsuhiro Tsujikawa [mailto:[email-masked]]
> Sent: vendredi 18 octobre 2013 14:31
> To: [email-masked]
> Subject: SETTINGS_HEADER_TABLE_SIZE and ACK
> 
> SETTINGS_HEADER_TABLE_SIZE is used to inform the size of header table to
> the other endpoint. Since the size of header table of the decoder side has to
> be matched to the one in the encoder side (otherwise, header table out-of-
> sync on eviction or out-of-bound index), the received peer may not want to
> accept the larger buffer size due to whatever reason (e.g., resource
> The HPACK-03 has a text to allow the receiver to choose smaller values in the
> acknowledgement, but now SETTINGS with ACK flags must not have any
> settings value, the peer is forced to accept the offer.
> 
> The SETTINGS_HEADER_TABLE_SIZE is special among the other settings. The
> others affect the receiver's capability, but it can regulate itself not to use
> more resources it wants (e.g., SETTINGS_MAX_CONCURRENT_STREAMS is
> informed as 500, but the receiver only uses 100). For
> SETTINGS_HEADER_TABLE_SIZE, there is no way but to just obey the
> informed value.
> 
> Best regards,
> Tatsuhiro Tsujikawa

---

From: Roberto Peon <[email-masked]>
Date: Fri, 18 Oct 2013 09:23:42 -0700

We should definitely clarify this further in the spec, since it is causing
confusion.

How about an implementation considerations section where we talk about how
implementations might leverage the spec in various scenarios?
On Oct 18, 2013 9:06 AM, "RUELLAN Herve" <[email-masked]> wrote:

> The receiver will have a 4k table, storing more entries than the sender.
> These entries stored only by the receiver are not a problem, as the sender
> will never refer to them, but only to those it has in its table.
> There is a difficulty to access the entries from the static table: to know
> the index of the first entry in the static table, the sender needs to know
> how many entries are present in the whole table of the receiver. It can
> manage this by tracking the size of the entries in the part it doesn't use:
> this allows it to evict entries from the table as would the receiver, and
> therefore to know how many entries are in the header table.
>
>
> Hervé.
>

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 19 Oct 2013 01:26:27 +0900

> will never refer to them, but only to those it has in its table.

OK, I understand that this is possible with the 0-index addition scheme.
The encoder also takes care of the reference set, if the entry slips away
from the 2K, then it needs to emit indexed repr to toggle off.

> therefore to know how many entries are in the header table.
Right. I feel this is a bit more complicated for the already complicated
enough HPACK spec. It would be good to add the above text to the draft so
that the implementer know the reasoning.

Best regards,
Tatsuhiro Tsujikawa

---

From: Martin Thomson <[email-masked]>
Date: Fri, 18 Oct 2013 09:53:59 -0700

> implementations might leverage the spec in various scenarios?

I think that it's more than that.  An encoder doesn't have to track
the entire table, but they do need to track sizes if they ever intend
to use the static table.  As long as they don't intend to reuse the
entries, then they don't have to keep the actual values.  An encoder
doesn't need to track entry sizes unless they want to use the static
table.

I think that's the only consequences to this for an encoder.  The cost
to the encoder is pitifully small when compared to the work and
commitment required by a decoder.  Just make a note of this and move
on.

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 19 Oct 2013 11:25:52 +0900

How about put static table before dynamic table. Then encoder does not need
to track the size of the entry beyond its boundary. It still needs to take
care reference set toggle though.

Best regards,
Tatsuhiro Tsujikawa

---

From: Roberto Peon <[email-masked]>
Date: Fri, 18 Oct 2013 20:48:31 -0700

That would harm the resultant output size, potentially a fair bit, since we
should expect that the dynamic table entries are more likely to be
referenced, they should be lower in the address space.
-=R

On Fri, Oct 18, 2013 at 7:25 PM, Tatsuhiro Tsujikawa
<[email-masked]>wrote:

> How about put static table before dynamic table. Then encoder does not
> need to track the size of the entry beyond its boundary. It still needs to
> take care reference set toggle though.
>
> Best regards,
> Tatsuhiro Tsujikawa
>

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 19 Oct 2013 18:08:12 +0900

On Sat, Oct 19, 2013 at 12:48 PM, Roberto Peon <[email-masked]> wrote:

> That would harm the resultant output size, potentially a fair bit, since
> we should expect that the dynamic table entries are more likely to be

I did experimented it and surprisingly, it does not harm and instead it
slightly improves the compression for the 4 data set in http_samples repo.

If we are going to add more headers to static tables, it might be safe to
keep dynamic table to the front.

The required steps for an encoder to use partial memory after usual
eviction steps will look like this:

HEADER_TABLE_SIZE : <size which remote decoder chosen>
LOCAL_HEADER_TABLE_SIZE : <size which local encoder chosen,
                           less than or equal to HEADER_TABLE_SIZE>

local_table_len : <the number of header entries in header table, whose
                   capacity is strictly less than or equal to
                   LOCAL_HEADER_TABLE_SIZE limit>

local_table_bufsize : <the buffer size in LOCAL_HEADER_TABLE_SIZE
                       which is calculated independent of whole table
                       buffer size.>

# Free up resources encoder does not want to pay and manage reference set
# state as necessary.
for i in range(local_table_len - 1, -1, -1):
    if local_table_bufsize + header_space(new_header)
              <= LOCAL_HEADER_TABLE_SIZE:
       break
    entry = table_get_entry(i)
    if reference_set_contains(entry):
        if entry.implied:
            # emit impiled header explicitly
            emit_indexed_repr_twice(i)
            entry.implied = False
        # Toggle off from the reference set in the remote
        emit_indexed_repr(i)
        referense_set_remove(entry)
    local_table_bufsize -= 32 + entry.name_len + entry.value_len
    local_table_len -= 1
    free_name_value(entry) # Do your memory management if they are
referenced
                           # from somewhere

if local_table_bufsize < header_space(new_header):
    entry = create_entry_without_allocate_name_value(new_header)
    emit_index_repr(0) # Toggle off from reference set in the remote
    table_push_front(entry)
else:
    entry = create_entry(new_header)
    table_push_front(entry)
    local_table_bufsize += 32 + entry.name_len + entry.value_len
    local_table_len += 1

The tricky part is that encoder requires another care about reference set
synchronization. Without proper treatment, they are leaked to the successive
header set.

Best regards,
Tatsuhiro Tsujikawa

>
>
> On Fri, Oct 18, 2013 at 7:25 PM, Tatsuhiro Tsujikawa <
> [email-masked]> wrote:
>