Subject: RE: Splitting QPACK

From: Mike Bishop <[email-masked]>
Date: Mon, 30 Jan 2017 02:46:49 +0000

Expanding audience.  I'm not entirely convinced the complexity is worthwhile, but this is where I would head if we're comfortable with it.  However, the added complexity buys us something.  This solves the RST problem without the weird behavior of saying that RSTs on the data stream imply the real state of the request, for example.  It also mostly solves the deadlock issue (so long as the dedicated stream has priority over everything else when you're allowed to send, you can't cause a deadlock on the request streams.

Also, if we go this way, the remaining reasons to separate headers and data seem to have disappeared, and we might be able to get down to one stream per request.

From: Mike Bishop
Sent: Thursday, January 26, 2017 5:01 AM
To: 'Martin Thomson' <[email-masked]>; 'Jana Iyengar' <[email-masked]>; Patrick McManus <[email-masked]>
Subject: Splitting QPACK

I took a shot on the plane at splitting QPACK up differently.  I reserve one stream (TBD exactly which) to do all table manipulations, and everything on the streams only references the table.  That solves the RST vulnerability nicely... but diverges even further from HPACK and brings us back toward HOLB potentially existing between all streams (assuming that most streams need to add something to the table).

Take a look at https://mikebishop.github.io/http-misc-extensions/split_qpack/draft-bishop-quic-http-and-qpack.html and see what you think, though.  Halfway between a thought experiment and a serious proposal.

---

From: Ryan Hamilton <[email-masked]>
Date: Sun, 29 Jan 2017 19:11:48 -0800

On Sun, Jan 29, 2017 at 6:46 PM, Mike Bishop <[email-masked]>
wrote:

> Also, if we go this way, the remaining reasons to separate headers and
> data seem to have disappeared, and we might be able to get down to one
> stream per request.
>
>
We'd still need some mechanism, within a stream, to delimit headers data
from body data, right? Using two QUIC streams solves this problem nicely.​
I don't love adding more intra-stream framing, if we can avoid it.

---

From: Mike Bishop <[email-masked]>
Date: Mon, 30 Jan 2017 03:45:07 +0000

Yes, it would mean bringing back the DATA frame from HTTP/2.  Given that we already have intra-stream framing (on one stream of two), that didn’t seem like a big loss to me.  However, I can believe that there are performance efficiencies to be gained from being able to dispense with framing once you get to the body.

From: Ryan Hamilton [mailto:[email-masked]]
Sent: Sunday, January 29, 2017 7:12 PM
To: Mike Bishop <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: Re: Splitting QPACK

On Sun, Jan 29, 2017 at 6:46 PM, Mike Bishop <[email-masked]<mailto:[email-masked]>> wrote:
Also, if we go this way, the remaining reasons to separate headers and data seem to have disappeared, and we might be able to get down to one stream per request.

We'd still need some mechanism, within a stream, to delimit headers data from body data, right? Using two QUIC streams solves this problem nicely.​ I don't love adding more intra-stream framing, if we can avoid it.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 29 Jan 2017 20:29:10 -0800

On Sun, Jan 29, 2017 at 7:11 PM, Ryan Hamilton <[email-masked]> wrote:
> from body data, right? Using two QUIC streams solves this problem nicely. I
> don't love adding more intra-stream framing, if we can avoid it.

Correct me if I'm wrong, but the additional stream shouldn't add any
more latency as it will be opened together with the first one. Why do
we need to get down to one stream per request?

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Ryan Hamilton <[email-masked]>
Date: Sun, 29 Jan 2017 20:32:47 -0800

Exactly. Adding HTTP/2 DATA frame overhead (or perhaps something similar)
is not the end of the world by any means and if we end up going that route,
so be it. On the other hand, by using the existing stream_id field of the
QUIC STREAM frame, we'll be able to differentiate headers from body without
burning any extra bytes on the wire, so that appeals to me.

On Sun, Jan 29, 2017 at 7:45 PM, Mike Bishop <[email-masked]>
wrote:

> Yes, it would mean bringing back the DATA frame from HTTP/2.  Given that
> we already have intra-stream framing (on one stream of two), that didn’t
> seem like a big loss to me.  However, I can believe that there are
> performance efficiencies to be gained from being able to dispense with
> framing once you get to the body.
>
>
>
> *From:* Ryan Hamilton [mailto:[email-masked]]
> *Sent:* Sunday, January 29, 2017 7:12 PM
> *To:* Mike Bishop <[email-masked]>
> *Cc:* IETF QUIC WG <[email-masked]>
> *Subject:* Re: Splitting QPACK
>
>
>
>
>

---

From: Patrick McManus <[email-masked]>
Date: Mon, 30 Jan 2017 15:32:19 +0100

Mike - I like the new text quite a lot. It gives encoders a clear chance to
decide when to risk holb and when to just inline things in literals; I
think that flexibility is going to be key in working out the most effective
approach. The horizon bits also read simpler than the unbounded reference
counted model discussed in Tokyo even if it is more complex than the
existing stream 3 approach. This is where I had been hoping we would end up.

In the grand scheme of things losses would likely be a very low percentage
of the overall bytes where a loss could create a holb event - and even then
it needn't be global. Good show.

As for the 2 vs 1 stream discussion, I still prefer the 2 stream approach
but its not a huge deal to me.

hope your traveling is safe and swift.

On Mon, Jan 30, 2017 at 5:32 AM, Ryan Hamilton <[email-masked]> wrote:

> On Sun, Jan 29, 2017 at 7:45 PM, Mike Bishop <[email-masked]
> > wrote:
>
>> On Sun, Jan 29, 2017 at 6:46 PM, Mike Bishop <
>> [email-masked]> wrote:
>>
>> from body data, right? Using two QUIC streams solves this problem nicely.
>> ​ I don't love adding more intra-stream framing, if we can avoid it.
>>
>>
>>
>
>

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 31 Jan 2017 10:52:02 +0900

2017-01-30 12:45 GMT+09:00 Mike Bishop <[email-masked]>:
> Yes, it would mean bringing back the DATA frame from HTTP/2.  Given that we
> already have intra-stream framing (on one stream of two), that didn’t seem
> like a big loss to me.  However, I can believe that there are performance
> efficiencies to be gained from being able to dispense with framing once you
> get to the body.

My two cents go to using single stream for both headers and body,
since I'd be worried of the maximum amount of memory that would be
consumed by the per-stream receive windows.

If we could send headers and body on a single stream then it would
mean that the maximum number of streams that an endpoint becomes half
when compared to current approach. That would in turn mean that the
maximum amount of memory that needs to be allocated for the receive
windows becomes half, or that the size of per-stream receive windows
can be doubled while keeping the maximum same to the current draft.

> Also, if we go this way, the remaining reasons to separate headers and data
> seem to have disappeared, and we might be able to get down to one stream per
> request.
>
>
>

-- 
Kazuho Oku

---

From: Ian Swett <[email-masked]>
Date: Tue, 31 Jan 2017 10:19:16 -0500

If the only reason to use 2 streams is to avoid framing, I think I'd rather
have the framing and switch to 1 stream for headers and body, since
compressed headers have framing associated with them anyway.  My previous
understanding was that two streams were used because the headers stream
couldn't be cancelled, but putting all the table manipulations solves that.

But there may be other reasons why 2 streams are preferable.

On Mon, Jan 30, 2017 at 8:52 PM, Kazuho Oku <[email-masked]> wrote:

> we
> data

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 31 Jan 2017 09:10:15 -0800

Catching up slowly. Thanks for putting this together. I think I like the
idea of simply using a stream where ordering is useful. Two points:
- I like the Horizon idea, but I'm not convinced that the flexibility buys
you much. In the simplest case, the encoder would simply state the last
request that uses the entry, right? I would expect, in teh common case,
that stating this number is sufficient. I understand that listing streams
buys you space earlier in teh case of loss/reordering, but the added
complexity seems high, and I'm generally concerned that implementations
might get this wrong.
- I don't understand why headers have to go in the same stream as data. The
model you propose still allows for headers to go in a separate headers
stream, while only table-manipulating entries go in the "QPACK" stream,
right? The primary value of having headers go in a separate stream from the
data was always to avoid framing. We will have to do gymnastics to get
QPACK right across requests -- but if we assume that inserts and deletes
are less common than references to the headers (as any reasonable
compression algorithm should assume), then we should see things happen on
the QPACK stream once in a while, and references occur more frequently on
the request header streams.

On Tue, Jan 31, 2017 at 7:19 AM, Ian Swett <[email-masked]> wrote:

> If the only reason to use 2 streams is to avoid framing, I think I'd
> rather have the framing and switch to 1 stream for headers and body, since

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Tue, 31 Jan 2017 09:46:29 -0800

On Mon, Jan 30, 2017 at 5:52 PM, Kazuho Oku <[email-masked]> wrote:

> When memory is a concern, I think an implementation should consider
auto-tuning the receive window sizes.    The Google QUIC code does this.
   Under such a regime, the total amount of memory used by receive buffers
has more to do with aggregate BDP than number of streams.

-- 
Charles 'Buck' Krasic | Software Engineer | [email-masked] | +1 (408)
412-1141

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Tue, 31 Jan 2017 09:53:22 -0800

One more thought/question about a dedicated stream for updates.    Would it
penalize the compression of HoL avoiding further, in the sense that what
would be an incremental update today would be an update on the control
stream, along with a literal on the data stream?  I.e. minimum two literals
for most entries added to the table?

On Tue, Jan 31, 2017 at 9:46 AM, Charles 'Buck' Krasic <[email-masked]>
wrote:

> 412-1141 <(408)%20412-1141>
>
>

---

From: Mike Bishop <[email-masked]>
Date: Tue, 31 Jan 2017 20:50:37 +0000

Yes, if the encoder was both determined never to HOLB and did it that way.  I think more realistic might be to say that writing something small to the headers stream and writing the full header set to the request stream at the same time, they’re very likely to wind up in the same packet.  Depending on the integration you have with your transport stack, there might even be a way for an implementation to guarantee that, but that’s beyond the scope of a protocol document.

From: Charles 'Buck' Krasic [mailto:[email-masked]]
Sent: Tuesday, January 31, 2017 9:53 AM
To: Kazuho Oku <[email-masked]>
Cc: Mike Bishop <[email-masked]>; IETF QUIC WG <[email-masked]>; Ryan Hamilton <[email-masked]>
Subject: Re: Splitting QPACK

One more thought/question about a dedicated stream for updates.    Would it penalize the compression of HoL avoiding further, in the sense that what would be an incremental update today would be an update on the control stream, along with a literal on the data stream?  I.e. minimum two literals for most entries added to the table?

On Tue, Jan 31, 2017 at 9:46 AM, Charles 'Buck' Krasic <[email-masked]<mailto:[email-masked]>> wrote:

On Mon, Jan 30, 2017 at 5:52 PM, Kazuho Oku <[email-masked]<mailto:[email-masked]>> wrote:

When memory is a concern, I think an implementation should consider auto-tuning the receive window sizes.    The Google QUIC code does this.      Under such a regime, the total amount of memory used by receive buffers has more to do with aggregate BDP than number of streams.

>
>
> From: Ryan Hamilton [mailto:[email-masked]<mailto:[email-masked]>]
> To: Mike Bishop <[email-masked]<mailto:[email-masked]>>
> Cc: IETF QUIC WG <[email-masked]<mailto:[email-masked]>>

--
Kazuho Oku

--
Charles 'Buck' Krasic | Software Engineer | [email-masked]<mailto:[email-masked]> | +1 (408) 412-1141<tel:(408)%20412-1141>

--
Charles 'Buck' Krasic | Software Engineer | [email-masked]<mailto:[email-masked]> | +1 (408) 412-1141

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Tue, 31 Jan 2017 15:06:42 -0800

On Tue, Jan 31, 2017 at 12:50 PM, Mike Bishop <[email-masked]>
wrote:

> Yes, if the encoder was both determined never to HOLB and did it that
> way.  I think more realistic might be to say that writing something small
> to the headers stream and writing the full header set to the request stream
> at the same time, they’re very likely to wind up in the same packet.
>

Ok I get it now.  For the header that causes a table insert, it would be
ill-advised to use a hpack literal on the headers stream.   There's no
point guarding HoL blocking among things that that will end up in the same
packet anyway.

> Depending on the integration you have with your transport stack, there
> might even be a way for an implementation to guarantee that, but that’s
> beyond the scope of a protocol document.
>
>
>

> *From:* Charles 'Buck' Krasic [mailto:[email-masked]]
> *Sent:* Tuesday, January 31, 2017 9:53 AM
> *To:* Kazuho Oku <[email-masked]>
> *Cc:* Mike Bishop <[email-masked]>; IETF QUIC WG <
> [email-masked]>; Ryan Hamilton <[email-masked]>
> One more thought/question about a dedicated stream for updates.    Would
> it penalize the compression of HoL avoiding further, in the sense that what

---

From: Martin Thomson <[email-masked]>
Date: Wed, 1 Feb 2017 10:28:59 +1100

On 1 February 2017 at 10:06, Charles 'Buck' Krasic <[email-masked]> wrote:
> ill-advised to use a hpack literal on the headers stream.   There's no point
> guarding HoL blocking among things that that will end up in the same packet
> anyway.

The hazard is where you have multiple concurrent uses in short order.
If packetization causes the insert and the reference to appear in
different packets, you have a HOLB exposure.

As Mike observes, the odds of having a reference that causes an insert
split between two packets is low.  Well, depending on how you
construct packets.  You can minimize this by generating interleaved
STREAM frames, but that has a bunch of overhead associated with it.

It all depends on how much you want to spend to avoid stalling in the
case of packet loss.  I can imagine using different strategies based
on observed packet loss, but then I can also imagine flying cars and
we all know how common those are.

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Tue, 31 Jan 2017 16:23:35 -0800

On Tue, Jan 31, 2017 at 3:28 PM, Martin Thomson <[email-masked]>
wrote:

> point

Yea.  I can imagine that the trade-offs may play out differently for
requests vs responses.

Considering the O(100) *requests* example Patrick mentioned.

There could be a very good chance that after compression many packets
contain headers from several distinct requests.   The subset of requests
packed into a common packet now share fate, so no point giving up
compression efficiency by coding them independently of each other.   *if*
it were the case that all the requests fit into a single packet, then
clearly any HoL avoidance would be strictly losing tactic.

In the *response* direction it is quite different.  Suppose the request
were for images, such that the bodies were all one or more packets large.
 If the bodies were consistently written along with the corresponding
response headers, the chance of two response headers sharing fate (by
virtue of serializing into the same packet) may be effectively zero.     In
that case, having the response headers encoded independent of each other
could be quite valuable (still modulo compression efficiency).

We clearly need some measurements...

---

From: Patrick McManus <[email-masked]>
Date: Wed, 1 Feb 2017 07:29:15 +0100

or to put it another related way - the value of hpack has always been in
avoiding cwnd stalls. quic breaks down the old abstractions and an encoder
can certainly better take into account cwnd, the amount of data it thinks
it will be sending, and how it wants to combine frames in packets. that's
pretty powerful in balancing the tradeoffs here.

off hand it seems clients doing the o(100) thing would be highly incented
early on, but later might not need to accommodate such bursts and would use
different strategies.. similarly servers might only use compression rarely.

beyond to compress or not, different choices might be made in how tightly
each packet is stuffed again based on cwnd.