Subject: FW: New Version Notification for draft-bishop-quic-http-and-qpack-01.txt

From: Mike Bishop <[email-masked]>
Date: Wed, 18 Jan 2017 00:07:57 +0000

With the recent publication of the WG -01 drafts, I've updated my QPACK draft to -01 as well.  Notable non-editorial changes:

  *   Realized we didn’t need the ability for the encoder to declare a table size if the encoder is explicitly managing the table.  Therefore, I can steal the “size change” instruction rather than the “never-indexed” instruction.  Resolves one of the major drawbacks.
  *   Removed the proposed HTTP/QUIC mapping, since that’s now largely incorporated into the WG document.  Replaced with a much shorter section on how to slot QPACK into hq-01.
  *   Clarified how changes to maximum table size during a live connection are handled, especially in light of the settings-synchronization text that’s been added to hq-01.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Tuesday, January 17, 2017 4:01 PM
To: Mike Bishop <[email-masked]>
Subject: New Version Notification for draft-bishop-quic-http-and-qpack-01.txt

A new version of I-D, draft-bishop-quic-http-and-qpack-01.txt

has been successfully submitted by Mike Bishop and posted to the IETF repository.

Name:                  draft-bishop-quic-http-and-qpack

Revision:              01

Title:                      Header Compression for HTTP/QUIC

Document date:               2017-01-17

Group:                  Individual Submission

Pages:                   10

URL:            https://www.ietf.org/internet-drafts/draft-bishop-quic-http-and-qpack-01.txt

Status:         https://datatracker.ietf.org/doc/draft-bishop-quic-http-and-qpack/

Htmlized:       https://tools.ietf.org/html/draft-bishop-quic-http-and-qpack-01

Diff:           https://www.ietf.org/rfcdiff?url2=draft-bishop-quic-http-and-qpack-01

Abstract:

   HTTP/2 [RFC7540] uses HPACK [RFC7541] for header compression.

   However, HPACK relies on the in-order message-based semantics of the

   HTTP/2 framing layer in order to function.  Messages can only be

   successfully decoded if processed by the decoder in the same order as

   generated by the encoder.  This draft refines HPACK to loosen the

   ordering requirements for use over QUIC [I-D.ietf-quic-transport].

Please note that it may take a couple of minutes from the time of submission until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: Martin Thomson <[email-masked]>
Date: Thu, 19 Jan 2017 16:29:19 +1300

Thanks for putting this together Mike.

I think that this is the right direction to go for QUIC.  It is
marginally more complex than HPACK, but only to the extent necessary
(modulo one issue below).

I notice you mention "incremental indexing" in a few places still,
that probably needs fixing.

For QPACK-ACK, presumably this is sent on stream 3?2?  I think that
you should invert the meaning and only include bits for entries that
still have a value (at the time of sending).  This allows a sender to
verify that deletion has happened, but also allows this to be a
cumulative message rather than an incremental one.  It might also
allow for a smaller message if a sender packs all their more stable
values at the low end of the table - deletes at the end of table don't
need to be signaled at all.

Editorially, I think that this is the right way to present this now
for the working group, but ultimately I think that I would prefer to
see a more standalone document.  If that means replicating text from
HPACK, I think that would be better than having gaps.  It would also
give us the chance to make some of those long-outstanding changes we
promised to the static table; maybe even informed by new and more
relevant data from h2.

An issue that needs some thought: a reset stream might include a
reference to an index entry.  However that reference won't be repaired
in the event of loss after a reset.  We need a strategy for dealing
with that and I can't think of one offhand.

I found the description of the states a little confusing.  In
particular, the mixing of encoder and decoder state descriptions was
hard to follow.  Separating those would be better, I think.  The
encoder only needs to know what entries exist, what entries are dead
but consuming space, and what entries are free.  The decoder needs
more precise accounting about the number of uses and when the uses hit
a delete threshold.

The actual algorithm can be quite elegant: At the decoder, counters
for use_count and delete_count, plus the slots for name and value, are
sufficient.  I think that's all you need aside from maybe an index
number slot, so it's probably OK not to change the 32 octet-per-entry
allowance from HPACK, even though you need to add these counters.

A value of 0 for use_count indicates that the field is unused and can
be allocated to safely.  A value of 0 for delete_count indicates that
a delete hasn't been requested.  When an insert or reference happens
(including the first insert): ++use_count; when a delete is requested,
set delete_count.  In both cases, also add a check for delete_count ==
use_count, in which case you free the entry.

The encoder doesn't need to use the delete_count, but it does need to
remember that the slot existed previously - and how big it was - so
that it doesn't reuse it before the decoder confirms that it's OK to
do so.  Switching delete_count for a size counter would do for that
purpose.

There's nothing preventing an encoder from using high index numbers.
That could be quite inefficient and potentially dangerous for a
decoder that wasn't prepared for it.  Do we need a cap on the index
value just to prevent silliness?  (table_size /32) would be the
absolute largest sensible value.

On 18 January 2017 at 13:07, Mike Bishop <[email-masked]> wrote:
> With the recent publication of the WG -01 drafts, I've updated my QPACK
> draft to -01 as well.  Notable non-editorial changes:
>
> Realized we didn’t need the ability for the encoder to declare a table size
> if the encoder is explicitly managing the table.  Therefore, I can steal the
> “size change” instruction rather than the “never-indexed” instruction.
> Resolves one of the major drawbacks.
> Removed the proposed HTTP/QUIC mapping, since that’s now largely
> incorporated into the WG document.  Replaced with a much shorter section on
> how to slot QPACK into hq-01.
> Clarified how changes to maximum table size during a live connection are
> handled, especially in light of the settings-synchronization text that’s
> been added to hq-01.
>
>
>
> URL:
> https://www.ietf.org/internet-drafts/draft-bishop-quic-http-and-qpack-01.txt
>
> Status:
> https://datatracker.ietf.org/doc/draft-bishop-quic-http-and-qpack/
>
> Htmlized:
> https://tools.ietf.org/html/draft-bishop-quic-http-and-qpack-01
>
> Diff:
> https://www.ietf.org/rfcdiff?url2=draft-bishop-quic-http-and-qpack-01
>
>
>
> Abstract:
>
> Please note that it may take a couple of minutes from the time of submission
> until the htmlized version and diff are available at tools.ietf.org.
>
>
>
> The IETF Secretariat
>
>

---

From: Mike Bishop <[email-masked]>
Date: Thu, 19 Jan 2017 06:31:56 +0000

Yes, QPACK-ACK is on the connection control stream, which is stream 3; that's mentioned by name, but not by stream number.

In an unpublished previous version, the ACK was a bitmap of all slots in the table, indicating occupied or not, as you suggest.  What caused it to change is this unlikely-but-possible scenario:

·        Encoder inserts to slot A

o   This frame is delayed

·        Encoder deletes slot A

o   This frame is also delayed

·        Encoder receives a QPACK-ACK indicating that A is empty

At this point, without querying the transport to see which frames have/haven’t been acknowledged, the encoder doesn’t know whether delete(A) has complete successfully, or insert(A) hasn’t happened yet.  In order to mitigate that, the encoder originally wasn’t allowed to send delete(A) until it had seen a QPACK-ACK frame indicating the slot as occupied.

Alternatively, since you know that stream 3 is always in order, you could say that you can’t consider the delete to have occurred until you have seen the slot filled in at least one QPACK-ACK, then empty in at least one QPACK-ACK.  But then decoders have to make sure not to send a QPACK-ACK frame that reflects both an add and a delete to the same slot.  That seems like it gets into more recordkeeping than I wanted, but might be a viable solution:  Keep a list of all slots with changes since your last QPACK-ACK; if you encounter a duplicate you MUST emit the QA frame and make the duplicate the first change accumulating toward your next QPACK-ACK.

By switching to an incremental QPACK-ACK, the state machine becomes really simple – encoders just insert and trust that the delete counter will cover it.  Decoders can accumulate as much as they want into a single QPACK-ACK frame, because the sender isn’t allowed to issue instructions that would generate duplicates.

The fact that inserts might have been lost due to a reset is a wrinkle I hadn’t considered, and not one I have a ready solution to. That’s a serious issue applicable to HPACK in the current draft -01 as well.  We’ll have to think about that one – there are a lot of bright people here, so I’m sure someone will come up with something.  If nothing else, given that headers are usually small, we could say that only the data streams get RST, never the header streams.

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]]
Sent: Wednesday, January 18, 2017 7:29 PM
To: Mike Bishop <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: FW: New Version Notification for draft-bishop-quic-http-and-qpack-01.txt

I think that this is the right direction to go for QUIC.  It is marginally more complex than HPACK, but only to the extent necessary (modulo one issue below).

I notice you mention "incremental indexing" in a few places still, that probably needs fixing.

For QPACK-ACK, presumably this is sent on stream 3?2?  I think that you should invert the meaning and only include bits for entries that still have a value (at the time of sending).  This allows a sender to verify that deletion has happened, but also allows this to be a cumulative message rather than an incremental one.  It might also allow for a smaller message if a sender packs all their more stable values at the low end of the table - deletes at the end of table don't need to be signaled at all.

Editorially, I think that this is the right way to present this now for the working group, but ultimately I think that I would prefer to see a more standalone document.  If that means replicating text from HPACK, I think that would be better than having gaps.  It would also give us the chance to make some of those long-outstanding changes we promised to the static table; maybe even informed by new and more relevant data from h2.

An issue that needs some thought: a reset stream might include a reference to an index entry.  However that reference won't be repaired in the event of loss after a reset.  We need a strategy for dealing with that and I can't think of one offhand.

I found the description of the states a little confusing.  In particular, the mixing of encoder and decoder state descriptions was hard to follow.  Separating those would be better, I think.  The encoder only needs to know what entries exist, what entries are dead but consuming space, and what entries are free.  The decoder needs more precise accounting about the number of uses and when the uses hit a delete threshold.

The actual algorithm can be quite elegant: At the decoder, counters for use_count and delete_count, plus the slots for name and value, are sufficient.  I think that's all you need aside from maybe an index number slot, so it's probably OK not to change the 32 octet-per-entry allowance from HPACK, even though you need to add these counters.

A value of 0 for use_count indicates that the field is unused and can be allocated to safely.  A value of 0 for delete_count indicates that a delete hasn't been requested.  When an insert or reference happens (including the first insert): ++use_count; when a delete is requested, set delete_count.  In both cases, also add a check for delete_count == use_count, in which case you free the entry.

The encoder doesn't need to use the delete_count, but it does need to remember that the slot existed previously - and how big it was - so that it doesn't reuse it before the decoder confirms that it's OK to do so.  Switching delete_count for a size counter would do for that purpose.

That could be quite inefficient and potentially dangerous for a decoder that wasn't prepared for it.  Do we need a cap on the index value just to prevent silliness?  (table_size /32) would be the absolute largest sensible value.

On 18 January 2017 at 13:07, Mike Bishop <[email-masked]<mailto:[email-masked]>> wrote:

> With the recent publication of the WG -01 drafts, I've updated my

> QPACK draft to -01 as well.  Notable non-editorial changes:

> Realized we didn’t need the ability for the encoder to declare a table

> size if the encoder is explicitly managing the table.  Therefore, I

> can steal the “size change” instruction rather than the “never-indexed” instruction.

> incorporated into the WG document.  Replaced with a much shorter

> section on how to slot QPACK into hq-01.

> Clarified how changes to maximum table size during a live connection

> are handled, especially in light of the settings-synchronization text

> that’s been added to hq-01.

> From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]]

> To: Mike Bishop <[email-masked]<mailto:[email-masked]>>

> Subject: New Version Notification for

> draft-bishop-quic-http-and-qpack-01.txt

> has been successfully submitted by Mike Bishop and posted to the IETF

> repository.

> https://www.ietf.org/internet-drafts/draft-bishop-quic-http-and-qpack-

> 01.txt

>    However, HPACK relies on the in-order message-based semantics of

> the

>    successfully decoded if processed by the decoder in the same order

> as

> Please note that it may take a couple of minutes from the time of

> submission until the htmlized version and diff are available at tools.ietf.org.