Subject: Deadlocking in the transport

From: Martin Thomson <[email-masked]>
Date: Wed, 10 Jan 2018 17:17:14 +1100

Building a complex application protocol on top of QUIC continues to
produce surprises.

Today in the header compression design team meeting we discussed a
deadlocking issue that I think warrants sharing with the larger group.
This has implications for how people build a QUIC transport layer.  It
might need changes to the API that is exposed by that layer.

This isn't really that new, but I don't think we've properly addressed
the problem.

## The Basic Problem

If a protocol creates a dependency between streams, there is a
potential for flow control to deadlock.

Say that I send X on stream 3 and Y on stream 7.  Processing Y
requires that X is processed first.

X cannot be sent due to flow control but Y is sent.  This is always
possible even if X is appropriately prioritized.  The receiver then
leaves Y in its receive buffer until X is received.

The receiver cannot give flow control credit for consuming Y because
it can't consume Y until X is sent.  But the sender needs flow control
credit to send X.  We are deadlocked.

It doesn't matter whether the stream or connection flow control is
causing the problem, either produces the same result.

(To give some background on this, we were considering a preface to
header blocks that identified the header table state that was
necessary to process the header block.  This would allow for
concurrent population of the header table and sending message that
depended on the header table state that is under construction.  A
receiver would read the identifier and then leave the remainder of the
header block in the receive buffer until the header table was ready.)

## Options

It seems like there are a few decent options for managing this.  These
are what occurred to me (there are almost certainly more options):

1. Don't do that.  We might concede in this case that seeking the
incremental improvement to compression efficiency isn't worth the
risk.  That is, we might make a general statement that this sort of
inter-stream blocking is a bad idea.

2. Force receivers to consume data or reset streams in the case of
unfulfilled dependencies.  The former seems like it might be too much
like magical thinking, in the sense that it requires that receivers
conjure more memory up, but if the receiver were required to read Y
and release the flow control credit, then all would be fine.  For
instance, we could require that the receiver reset a stream if it
couldn't read and handle data.  It seems like a bad arrangement
though: you either have to allocate more memory than you would like or
suffer the time and opportunity cost of having to do Y over.

3. Create an exception for flow control.  This is what Google QUIC
does for its headers stream.  Roberto observed that we could
alternatively create a frame type that was excluded from flow control.
If this were used for data that had dependencies, then it would be
impossible to deadlock.  It would be similarly difficult to account
for memory allocation, though if it were possible to process on
receipt, then this *might* work.  We'd have to do something to address
out-of-order delivery though.  It's possible that the stream
abstraction is not appropriate in this case.

4. Block the problem at the source.  It was suggested that in cases
where there is a potential dependency, then it can't be a problem if
the transport refused to accept data that it didn't have flow control
credit for.  Writes to the transport would consume flow control credit
immediately.  That way applications would only be able to write X if
there was a chance that it would be delivered.  Applications that have
ordering requirements can ensure that Y is written after X is accepted
by the transport and thereby avoid the deadlock.  Writes might block
rather than fail, if the API wasn't into the whole non-blocking I/O
thing.  The transport might still have to buffer X for other reasons,
like congestion control, but it can guarantee that flow control isn't
going to block delivery.

## My Preference

Right now, I'm inclined toward option 4. Option 1 seems a little too
much of a constraint.  Protocols create this sort of inter-dependency
naturally.

There's a certain purity in having the flow control exert back
pressure all the way to the next layer up.  Not being able to build a
transport with unconstrained writes is potentially creating
undesirable externalities on transport users.  Now they have to worry
about flow control as well.  Personally, I'm inclined to say that this
is something that application protocols and their users should be
exposed to.  We've seen with the JS streams API that it's valuable to
have back pressure available at the application layer and also how it
is possible to do that relatively elegantly.

I'm almost certain that I haven't thought about all the potential
alternatives.  I wonder if there isn't some experience with this
problem in SCTP that might lend some insights.

---

From: Willy Tarreau <[email-masked]>
Date: Wed, 10 Jan 2018 07:48:20 +0100

Hi Martin,

On Wed, Jan 10, 2018 at 05:17:14PM +1100, Martin Thomson wrote:
> Right now, I'm inclined toward option 4.

Well, I'm lagging a bit too much to have a valuable opinion, but all
I can say is that from a protocol design perspective, this option
totally makes sense. Starting to send when you depend on something
which is blocked doesn't make real sense. In fact it could even be
argued that in such dependencies cases, the flow control could be
shared, i.e. Y could offer some of its budget to X to ensure it can
make progress resulting in the two ultimately being unblocked. I know
it would imply a number of painful changes though and I'm just talking
about threory here.

Regards,
Willy

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 9 Jan 2018 22:49:28 -0800

Martin,

You are right that this isn't a new concern, and that this is worth noting
somewhere, perhaps in the applicability/API doc.

The crux of this issue is that there's structure in application data that
the transport is unaware of. Specifically, there are dependencies among
application data units that is opaque to the transport. Using the transport
buffers as a part of handling these dependencies seems like a bad idea,
especially since the transport is likely to make decisions about flow
window updates based on rate at which data is consumed out of the receive
buffer(s). GQUIC does this, and so does every respectable TCP receiver
implementation.

The SCTP API avoids this problem by not allowing the application to read
specific stream data out of the socket buffers. The receiving app receives
data that could belong to any stream and has to demux after reading out of
the socket. (Note that SCTP does not have per-stream flow control, so the
receive side here is more like SPDY/TCP, modulo HoL blocking at the
transport.)

Protocols that create inter-stream dependency should be able to express
that in priorities down to the transport, which I believe is expected to be
part of the API. I believe that handles this issue, doesn't it?

- jana

---

From: Subodh Iyengar <[email-masked]>
Date: Wed, 10 Jan 2018 06:55:01 +0000

Nice catch.

Option 4. is possible without protocol support I believe and this coincidentally is also the API that mvfst implements, i.e. our API counts buffered data as well towards the flow control for API writes.

Although even with this it seems very gotcha behavior which is not super obvious which people will definitely be burned by. I'm in favor of something like 3 which could potentially allow the receiver to signal to the sender to create an exception to the connection flow control for some streams when it gets into deadlocked states. There are some races with this, but it could be designed to work.

Subodh

________________________________
From: QUIC <[email-masked]> on behalf of Jana Iyengar <[email-masked]>
Sent: Tuesday, January 9, 2018 10:49:28 PM
To: Martin Thomson
Cc: QUIC WG
Subject: Re: Deadlocking in the transport

Martin,

You are right that this isn't a new concern, and that this is worth noting somewhere, perhaps in the applicability/API doc.

The crux of this issue is that there's structure in application data that the transport is unaware of. Specifically, there are dependencies among application data units that is opaque to the transport. Using the transport buffers as a part of handling these dependencies seems like a bad idea, especially since the transport is likely to make decisions about flow window updates based on rate at which data is consumed out of the receive buffer(s). GQUIC does this, and so does every respectable TCP receiver implementation.

The SCTP API avoids this problem by not allowing the application to read specific stream data out of the socket buffers. The receiving app receives data that could belong to any stream and has to demux after reading out of the socket. (Note that SCTP does not have per-stream flow control, so the receive side here is more like SPDY/TCP, modulo HoL blocking at the transport.)

Protocols that create inter-stream dependency should be able to express that in priorities down to the transport, which I believe is expected to be part of the API. I believe that handles this issue, doesn't it?

- jana

On Tue, Jan 9, 2018 at 10:17 PM, Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:
Building a complex application protocol on top of QUIC continues to
produce surprises.

## The Basic Problem

## Options

## My Preference

---

From: "Brian Trammell (IETF)" <[email-masked]>
Date: Wed, 10 Jan 2018 08:04:52 +0100

hi Martin, all,

> On 10 Jan 2018, at 07:17, Martin Thomson <[email-masked]> wrote:
> 

Indeed, we ran into a closely related problem with IPFIX. IPFIX itself had no flow control, so reordering and unreliable transport of dependent information (in this case, templates and the data they describe) was a matter of ambiguous interpretation, not deadlock. But most of the substantive changes between the Proposed Standard (RFC 5101) and Internet Standard (RFC 7011) versions of the protocol had to do with fixing how collectors handled potentially unordered or missing template information (see section 8 of 7011 if you're interested in details).

The IPFIX case is further complicated because it runs over TCP (in order, reliable, single stream, so template ambiguity is not a problem), SCTP (where there can be stream dependencies; 5101 allowed anything on any stream at any time, 6526 suggested a refinement where every template ID got its own stream, thereby ordering template change messages, and 7011 specified generalized ordering), and UDP (where template ID reuse is only permitted after a long delay).

> inter-stream blocking is a bad idea.

As I noted in the chat during the Vancouver interim, both for the specific case of header compression, as well as in general, I am an emphatic and enthusiastic supporter of "don't do that". Introducing stream dependencies takes a trivially implementable dictionary-transfer protocol and turns it into something that is very, very difficult to get right, and "implementability by people outside the QUIC Interop Slack channel" is a primary technical requirement of the protocol spec.

> suffer the time and opportunity cost of having to do Y over.

This is the approach we used in IPFIX, with varying success. We have the advantage that every IPFIX message can be ordered by its export timestamp and sequence number, so we basically tell collectors to use a buffer of unspecified size to reorder messages, to consider them in the order they should have been sent in, and to freak out if that still leads to detectable ambiguity.

AFAIK, nobody successfully uses template deletion and ID reuse in practice unless there are relatively long delays between them.

> abstraction is not appropriate in this case.

This seems to me to be inexcusably ugly.

In any case, this would need to be generalized to be an "application-layer control information frame", and there would need to be big red stickers all over it, because it would be so tempting to abuse, because such abuse would almost always work in test.

> like congestion control, but it can guarantee that flow control isn't

I'm not sure how I see this is fundamentally different from "don't do that" from the transport protocol's point of view.

> much of a constraint.  Protocols create this sort of inter-dependency

Do we have any actual numbers on how much efficiency can actually be squeezed out of allowing compression dictionaries to create unbounded dependencies between streams on common, non-pathological workloads?

Cheers,

Brian

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 10 Jan 2018 02:05:43 -0500

> part of the API. I believe that handles this issue, doesn't it?

When it comes to priorities, the QUIC I-D gives implementations
some leeway [1].  One cannot guarantee that a conforming
implementation will not deadlock.

  - Dmitri.

1. https://tools.ietf.org/html/draft-ietf-quic-transport-08#section-10.6

---

From: Ian Swett <[email-masked]>
Date: Wed, 10 Jan 2018 08:46:06 -0500

I would agree that #4 is the right direction.  GQUIC also does #4, because
it forces all headers to be written before any requests that may depend
upon them are written.

If the application knows there is a dependency, it should be the
application's responsibility to deal with it, not the transport's, which
also points to #4(or maybe #1).

I also think there are use cases for data transfer that is not a stream and
does not consume flow control, but I don't think they solve every problem
and I don't think they should be necessary here.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 10 Jan 2018 05:51:26 -0800

Blocking at source is not practical if feeding several very large files via
a mmap pointer to the API for deferred round robin transmission so all
files get equal opportunity to get through. In this case only small pieces
could be delivered at a time before the allocation must check if there is
are more transmission credits.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 10 January 2018 at 14.46.36, Ian Swett ([email-masked]) wrote:

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 10 Jan 2018 06:53:21 -0800

For what it is worth, my APACK-02 proposal attempts to solve the problem by
blocking at source, but only for this particular use of QUIC.

https://github.com/dvidelabs/apack/blob/master/apack-02.md#encoder-blocking

If the header compression overall ensures to not use more than certain
amount of credits before blocking, and if the other streams make sure to
not consume any more that the overall credit minus the header block, then
this should suffice from a cursory view.

As to my previous example with large files, the api needs to have some sort
of resource management to ensure background feeds do not over allocate. An
actual complex stream dependency scheme is probably not a good idea, but
streams could be divided into resource groups with allotted bandwidth.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 10 January 2018 at 14.51.26, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

Kind Regards,
Mikkel Fahnøe Jørgensen

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Wed, 10 Jan 2018 09:47:03 -0800

> part of the API. I believe that handles this issue, doesn't it?
I thought priorities wouldn't solve the problem, but now I am not so sure.

Here's an example we've been using in the compression design group:

 o   Client sends requests A, B and on streams A, B.
 o   Server receives requests, sends responses A, B.
       o the compression scheme allows inter-stream dependencies, so B's
compressed header ends up depending on A's.   There
          is a small prefix in each compressed header block the tells the
client this.  The idea is that the client can read the prefix,
          but will not read the rest until the dependency is satisfied on
its end.
       o suppose A's header was only partially written so far (this is what
we assumed, but I'm not sure this makes sense if A has priority over B)
       o and that due to sending A+B's (partial) responses the server is
now connection-level flow control blocked.
o  Before the client receives A's header, client decides to cancel A, so it
does STOP_SENDING/RST_STREAM on A.
        o e.g. the resource A is no longer desired, perhaps because the
user scrolled and A no longer needed to render the on-screen area.
 o   server receives STOP_SENDING/RST_Swhere the proxy treats streams as
opaque and forwards dataTREAM on A, it resets it's side of A.
       o this will undo A's outstanding flow-control debt, but that will
not be enough to resend A's full header (on another stream), since the
adjustment to
          the connection level only corresponds to the partial header sent
so far.

I think priorities actually do help solve this in the following sense.   It
makes a variation of #4.   A write can occur, even without immediately
consuming flow control, but the priority does ensure it will get flow
control when it needs it.
This isn't necessarily HQ priorities though.   A workable, but less
performant variation, might be to say that if the transport does buffer
writes, it must service buffered writes in a global FIFO order.

With priorities, the part where A sends a partial header seems invalid.
 The header compression does have requirements that headers be encoded
strictly sequentially, so partial header write doesn't make sense there.

The counter example given was a proxy, but I'm not sure that it is
reasonable to guarantee that QUIC proxies can always be oblivious to
mapping level semantics.  In the case of HTTP and header compression, it
seems especially counter-intuitive to me, since most cases will not have a
1:1 upstream downstream connection topology.

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

---

From: Ted Hardie <[email-masked]>
Date: Wed, 10 Jan 2018 10:40:48 -0800

Howdy,

I think there are two cases being intermingled here, and I think it would
be useful to pull them back apart.  Comments to that end in-line.

> credit to send X.  We are deadlocked.
I think there are two cases here.  In case one, the transport itself cannot
consume Y until X is sent, because X is needed to make Y's content
semantically available to the transport.  In that case, the deadlock case
you give is a truly fatal error and building a transport that allowed this
error case to occur would be a very bad notion.

The second case is one in which the protocol using the transport cannot
access Y's semantic content until X is received.  In that case, it has
three potential strategies.  One is not to permit the dependency to occur
at all; as you note, lots of applications have inherent dependencies or
common optimizations (e.g. FEC) that use this strategy.  This turns into a
limit in the scope of what can use QUIC if this is the required strategy.

Two is is for the using application/protocol to set up and manage its own
buffers so that it can take Y out of the receive buffer and wait for X to
arrive without blocking the transport.  While that might be magical
thinking for some using protocols of QUIC, it's not clear that it always
would be, as an application protocol built with QUIC as a transport in mind
could do it.  There are video cases I've worked on in the past where this
buffer-at-layer-above-the-network was the default, because multiple
networks were simultaneously being used to build the video playout buffer.

Three is to manage the writes to the network so the deadlock is unlikely to
occur (your option 4, or something that manages priorities with sufficient
strictness that it guarantees X is always available when Y is).

For the case you're describing, I think strategy 3/option 4 is right.  But
I don't think we ought to rule out strategy one and two for all using
protocols.  If you have a protocol that doesn't require or can easily avoid
these dependencies being split across streams, you get option one for
cheap.  If you have an application/protocol that's built with the idea of
the application managing its own buffers for resolving these dependencies,
two is practical rather than magical.

Just my two cents,

Ted

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 10 Jan 2018 11:34:11 -0800

On Wed, Jan 10, 2018 at 9:47 AM, Charles 'Buck' Krasic <[email-masked]>
wrote:

[pruning]

> writes, it must service buffered writes in a global FIFO order.

I agree. That's what I meant by priorities solving it -- that the shared
resource (connection-level flow buffer), if consumed in priority order at
the sender, avoids this deadlock. This  assumes that the application can
express this to the transport of course.

> 1:1 upstream downstream connection topology.

Yup, agreed.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 10 Jan 2018 14:47:17 -0500

> express this to the transport of course.

Even if the application can express it, the transport is not guaranteed
to consume the data in priority order: see the specification [1].

  - Dmitri.

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 10 Jan 2018 12:04:11 -0800

> to consume the data in priority order: see the specification [1].

I don't see the text in that section that says otherwise. Under what
conditions does the transport invert application stream priorities?

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 10 Jan 2018 15:06:46 -0500

> conditions does the transport invert application stream priorities?

This is the text:

  " When deciding which streams to dedicate resources to, QUIC
  " SHOULD use the information provided by the application.
    ^^^^^^

  - Dmitri.

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 10 Jan 2018 12:14:13 -0800

SHOULD is pretty strong. It's not a guarantee, but then a transport
implementation that doesn't do it is expected to know what it's doing.
We could include language in this section about priorities being important
to avoid deadlocks when an application has dependencies across streams.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 10 Jan 2018 15:23:57 -0500

> implementation that doesn't do it is expected to know what it's doing.

If an application protocol is based on an assumption that the transport's
SHOULD is really a MUST, then you end up with an application that works
with some transport implementations, but not other -- conforming! --
implementations.

> to avoid deadlocks when an application has dependencies across streams.

What would this advice be?  "Consume *all data* from higher priority
streams before consuming data from lower priority streams?"

  - Dmitri.

---

From: Roberto Peon <[email-masked]>
Date: Wed, 10 Jan 2018 20:26:57 +0000

Another option:
Allow a flow-control ‘override’ which allows a receiver to state that they really want data on a particular stream, and ignore the global flow control for this.

How you’d do it:
A receiver can send a flow-control override for a stream. This includes the stream id to which the global window temporarily does not apply, the receiver’s current stream flow-control offset, and the offset the receiver would wish to be able to receive.
A receiver must continue to (re)send the override (i.e. rexmit) until it is ack’d. It cannot send other flow-control for that stream until the override is ack’d.
Thus:
  global-flow-control-override: <stream-id> <current-flow-control-offset>, <override-flow-control-offset>

The sender (which receives the override) credits the global flow control with the difference between the data sent beyond the receivers currently-known flow-control offset upon receipt of the override.
This synchronizes the global state between the receiver and the sender.
The sender can then send the data on the stream (without touching any other flow control data).

Why:
This allows for a receiver to resolve priority inversions which would otherwise lead to deadlock, even when the data/dep leading to this was not known to the transport. This extends beyond such issues beyond just header compression.

Since the global flow-control exists to protect the app from resource exhaustion, this poses no additional risk to the application.
Simply increasing the global flow control provides less strong guarantees—any stream might consume it, which doesn’t resolve the dep inversion. Rejiggering priorities can help to resolve this, but would require the sender to send priorities to the client, which is problematic w.r.t.races and just a web of ick. 

Having a custom frame type is also a less strong guarantee as it requires the knowledge that the dep exists to be present at the time of sending, which is often impossible.

-=R

On 1/9/18, 10:17 PM, "QUIC on behalf of Martin Thomson" <[email-masked] on behalf of [email-masked]> wrote:

    

    ## The Basic Problem

    

    

    ## Options

    

    ## My Preference

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 10 Jan 2018 12:32:18 -0800

> with some transport implementations, but not other -- conforming! --

I agree, but we aren't specifying the entire API, and I'm not sure that we
want to resolve all potential API inconsistencies here.

> streams before consuming data from lower priority streams?"

Yes, to avoid deadlock.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 10 Jan 2018 15:40:55 -0500

How about a reserve bandwidth function in the API. Header transport could
reserve the minimum needed to ensure a deadlock, and another reserve for
the general traffic. This isolates bandwith consumption from other streams.

I hinted at this earlier. Just like you can share to the total bandwidth
across streams, you can share bandwidth across resource groups, where each
stream belongs to a resource group.

You can provide priorities to groups, but that should not mean the highest
priority takes all. It would be inconvenient and could lead to other
deadlocks. Deficit Round Robin can be applied to groups.

https://en.wikipedia.org/wiki/Deficit_round_robin

Kind Regards,
Mikkel Fahnøe Jørgensen

On 10 January 2018 at 21.32.25, Jana Iyengar ([email-masked]) wrote:

Yes, to avoid deadlock.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 10 Jan 2018 15:50:07 -0500

On Wed, Jan 10, 2018 at 12:32:18PM -0800, Jana Iyengar wrote:
> On Wed, Jan 10, 2018 at 12:23 PM, Dmitri Tikhonov wrote:
> >

We are not discussing the API; we are discussing the transport behaviors
that the application can or cannot rely upon.

> > streams before consuming data from lower priority streams?"

Let's make sure that we are talking about the same idea.  It seems that
what you are suggesting is either:

    A. The transport layer not allow the application to read from
       a stream if a higher-priority stream data is available for
       reading; or

    B. If the application wants to read from a lower-priority stream
       first, the transport layer will pretend that the higher-stream
       data has been read.  In other words, the high-stream data will
       be set aside somehow, giving the peer flow control credits for
       sending more.

Both seem suboptimal to me -- did you have something else in mind?

  - Dmitri.

---

From: Christian Huitema <[email-masked]>
Date: Wed, 10 Jan 2018 11:06:52 -1000

> Both seem suboptimal to me -- did you have something else in mind?

The problem arise because of over commitment of resource. Specifically,
it arises if the MAX DATA limit is lower the sum of the MAX STREAM DATA
limits. If MAX DATA was defined implicitly as the sum of MAX STREAM
DATA, we could have a very simple API between application and transport.
The application gives credits on the stream that it is ready to accept
data, and the transport just follows that.

I understand that from a resource point of view it is sub-optimal. The
smaller MAX DATA can be tied to a buffer pool not yet allocated to
specific streams, and there is some possibility to get the application
going with less than 2 bandwidth*delay products of buffers. But then,
this optimization is precisely what leads to deadlock conditions when
the transport does not quite get the priorities of the application, or
when the sender does not quite get the priorities of the receiver.

So we have two alternatives. One is to make the API more "expressive" so
the application can tell the transport exactly which order and
priorities can be applied. The other is to make the API less complex by
just mandating that MAX DATA be large than the sum of MAX STREAM DATA.
Or possibly removing MAX DATA altogether.

-- Christian Huitema

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Jan 2018 08:54:03 +1100

> Do we have any actual numbers on how much efficiency can actually be squeezed out of allowing compression dictionaries to create unbounded dependencies between streams on common, non-pathological w…

Dmitri ran some tests with QMIN, which doesn't create dependencies,
and found that for a time compression efficiency degraded noticeably
if it couldn't create dependencies.  I'll let Dmitri speak to that
point.  The shortcoming rectifies itself reasonably quickly, though
Roberto makes the point that this is precisely the point where
compression matters most.  It's a point that the header compression
folks are still debating.

(The dependencies wouldn't be unbounded.  One advantage of the
mechanism that QMIN proposes is that these dependencies are pretty
narrowly constrained and well understood.)

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Jan 2018 09:00:35 +1100

On Thu, Jan 11, 2018 at 5:40 AM, Ted Hardie <[email-masked]> wrote:
> access Y's semantic content until X is received.  In that case, it has three
> potential strategies.  One is not to permit the dependency to occur at all;
> as you note, lots of applications have inherent dependencies or common
> optimizations (e.g. FEC) that use this strategy.  This turns into a limit in
> the scope of what can use QUIC if this is the required strategy.
>
> arrive without blocking the transport.  While that might be magical thinking
> for some using protocols of QUIC, it's not clear that it always would be, as
> an application protocol built with QUIC as a transport in mind could do it.
> There are video cases I've worked on in the past where this
> buffer-at-layer-above-the-network was the default, because multiple networks
> were simultaneously being used to build the video playout buffer.

Yes, there will be cases where the content can be read, AND that that
content won't impose a resource penalty on the receiver such that it
is still able to release flow control credit for that read.  Those
applications can likely manage.  As you say, a video application has
to maintain memory for decoding N frames and it could take data from
frame X+1 and run it partway through the decoder pipeline up to the
point that X arrives.  That's just an exception to this general
problem.

> For the case you're describing, I think strategy 3/option 4 is right.  But I
> don't think we ought to rule out strategy one and two for all using
> these dependencies being split across streams, you get option one for cheap.
> If you have an application/protocol that's built with the idea of the
> application managing its own buffers for resolving these dependencies,  two
> is practical rather than magical.

Sure.  I'd expect to have that protocol opt in to that sort of
exceptional handling, because having it as a default is hazardous.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Jan 2018 09:08:00 +1100

>> streams before consuming data from lower priority streams?"

Priorities in h2 were always guidelines.  You (and I think Buck as
well) are suggesting that a dependency would be something that the
transport could be bound by.  That creates a dangerous schism between
interpretation of priorities.

In h2, if Y depends on X, a server can still send Y first.  It will
likely do so if Y is ready to go before X.  That is, generally, h2
favours forward progress over strict adherence to priority ordering.

I agree that the case that we're talking about at the transport layer
is substantively different, but if we don't have other language for
what we're doing, we create the potential for some really bad
confusion about this mechanism.  This is exacerbated by the fact that
QUIC doesn't have any concrete priority mechanism built in.  QUIC
depends on the application protocol to feed it priority information,
and that naturally tends toward having hq (and h2) dictate priority.
hq will likely use the h2 idiom, which won't fit well with this
notion.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 10 Jan 2018 17:36:42 -0500

On Thu, Jan 11, 2018 at 08:54:03AM +1100, Martin Thomson wrote:
> > Do we have any actual numbers on how much efficiency can actually be
> > squeezed out of allowing compression dictionaries to create unbounded
> > dependencies between streams on common, non-pathological workloads?
> 

What we have is a set of simulation results comparing QMIN (conservative:
no blocking) with QCRAM and QPACK (optimistic: blocking allowed).  I used
two web session traces: one visiting www.netbsd.org (small trace) and
another visiting www.facebook.com (larger trace).  I will paste parts of
two reports:

1> I integrated my QMIN library [1] into Alan's proxygen simulator [2] to
1> assess QMIN's compression performance.  Specifically, we want to see how
1> QMIN performs a) in a short-lived connection and b) in a longer connection.
1> I generated two HAR files:
1> 
1>   - I typed in www.netbsd.org into the Location bar of my browser and
1>     waited for the page to load.  This resulted in 18 requests, 17 of
1>     them to www.netbsd.org and 1 to www.paypalobjects.com.
1> 
1>   - I signed in to Facebook and clicked about a dozen links.  This resulted
1>     in 383 requests: about 100 to www.facebook.com, about 280 to fbcdn.net,
1>     and a few odd ones like facebook.net and fbsbx.com.
1> 
1> I left all loss-related simulator options unset for the initial test, as we
1> just want to look at the ideal environment compression performance first.
1> The dynamic table capacity is set to 4 KB.  The results are as follows:
1> 
1> (The simulator implements the latest QPACK and QMIN drafts; its QCRAM
1> implementation dates to June -- but it is better than nothing.)
1> 
1> Table 1: Compression performance comparison, no packet loss
1> 
1>                 HPACK          QPACK          QCRAM          QMIN
1> 
1>   netbsd        1265/6555      1309/6555      1361/6555      2202/6555
1>                 Ratio: 80      Ratio: 80      Ratio: 79      Ratio: 66
1> 
1>   facebook,     58528/243576   61753/243576   61386/243576   63782/243576
1>   blended [a]   Ratio: 75      Ratio: 74      Ratio: 74      Ratio: 73
1> 
1>   facebook,     59325/243576   62594/243576   63462/243576   67492/243576
1>   unblended     Ratio: 75      Ratio: 74      Ratio: 73      Ratio: 72
1> 
1>   a: "blended" means that the simulator pretends that facebook.com and
1>      fbcdn.net is the same domain name.  This is true by default; to
1>      disable, pass -blend=false on the command line.  The unblended
1>      simulation is closer to reality.
1> 
1>   How to read this table:   Each entry is a compressed version of the last
1>   three lines of the simulator output:
1>     Uncompressed Bytes: 243576                67492/243576
1>     Compressed Bytes: 67492         ====>     Ratio: 72
1>     Compression Ratio: 72

The second report addresses compression performance during the first few
flights:

2> What I do have, however, is my short netbsd session (a HAR of which I
2> emailed to the group in an earlier email).  This is as good a starting
2> point as any for drilling down into the compression performance of the
2> first few header blocks.  The netbsd trace contains 17 requests to
2> www.netbsd.org; they belong to three distinct flights:
2> 
2>     1. Request index.html (1 request)
2>     2. Request CSS and JS (3 requests)
2>     3. Request images (13 requests)
2> 
2> It would be informative to examine compression performance in each of
2> the flights.
2> 
2> Since the meeting of Dec 4, Alan added a cumulative compression ratio
2> reporting to the proxygen simulator [2].  In addition, I added a
2> per-header block compression ratio reporting to the QMIN encoder library.
2> First, compression performance comparison:
2> 
2> Table 1: Cumulative compression performance comparison
2> 
2>  Req #      QPACK       QCRAM       QMIN
2>                                    
2>      1      241/39      225/42      303/27
2>                                    
2>      2      78/58       74/60       219/35
2>      3      46/67       44/68       195/39
2>      4      47/72       52/72       188/42
2>                                    
2>      5      52/75       52/75       110/49
2>      6      55/77       55/76       96/53
2>      7      55/78       55/78       96/57
2>      8      54/79       54/78       95/59
2>      9      50/80       50/79       91/61
2>     10      55/80       55/80       96/63
2>     11      56/81       56/80       97/64
2>     12      63/81       63/80       104/65
2>     13      52/81       52/81       93/66
2>     14      51/82       51/81       92/67
2>     15      47/82       47/81       88/67
2>     16      46/82       46/82       87/68
2>     17      79/82       77/81       94/69
2> 
2> How to read this table: the two numbers separated by the slash are the size
2> of the encoded header block followed by the cumulative compression ratio.
2> These values are parsed from the simulator output:
2>     
2>   Encoded request=0 for host=www.netbsd.org block size=225 cumulative \
2>   compression ratio=42
2> 
2>     translates to
2> 
2>   225/42
2> 
2> (Note that the cumulative compression of all three does not match previously
2> reported results: this is because I do not take the last request into account
2> here, as it is going to a different domain.)

Caveat: QCRAM and QPACK drafts have changed significantly since then.
QMIN performance can be improved slightly while still keeping its
non-blocking behavior.

> folks are still debating.

The opposite view is that packet loss in the beginning would have a worse
impact than compression inefficiency.  I am sorry to say that we do not
have good simulation data to go on.

> narrowly constrained and well understood.)

Yes.  That is, QMIN does not introduce any stream dependencies.

  - Dmitri.

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 10 Jan 2018 14:39:24 -0800

> hq will likely use the h2 idiom, which won't fit well with this

Yes, I think there's easy misinterpretation here -- something I realized
today as I've had conversations about this. What I meant was specifically
at the API between the app and the transport, at the sender. This is
basically saying that to avoid deadlock due to dependencies across streams,
the transport write API must allow the app to express strict priorities.

As Buck pointed out, I think this is an extention to option (4) in that it
is useful when data beyond what's allowed by the flow controller is
buffered at the transport sender.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Jan 2018 09:42:23 +1100

On Thu, Jan 11, 2018 at 9:39 AM, Jana Iyengar <[email-masked]> wrote:
> today as I've had conversations about this. What I meant was specifically at
> the API between the app and the transport, at the sender. This is basically
> saying that to avoid deadlock due to dependencies across streams, the
> transport write API must allow the app to express strict priorities.

Ahh, excellent, then I think at least we two are in agreement.  It
seems like there is an emerging acceptance of the problem and proposed
approach, I guess we might start considering how to address it.

I think that this needs to be in the main spec.  Failing to document
this sort of pitfall could be fatal.  Does anyone disagree?

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 10 Jan 2018 14:55:08 -0800

> approach, I guess we might start considering how to address it.

I think so. I've heard some other approaches aired that folks may want to
discuss however.

> this sort of pitfall could be fatal.  Does anyone disagree?

I agree that we should document this, especially since it's expected to be
a common design pattern. Since we don't express dependencies among streams,
we have to ensure that an app that wishes to do so doesn't do the wrong
thing. I think we definitely should draw attention to this point, but I'm
not sure that we need to be very prescriptive here for what the app should
do, but I think we should use strong language for what a transport
implementation should do.

We should also mention that an app that chooses to not read out of a stream
buffer may cause negative interactions with any autotuning mechanisms
implemented to tune window update magnitude and frequency.

---

From: Mike Bishop <[email-masked]>
Date: Wed, 10 Jan 2018 22:55:46 +0000

No disagreement.  When choosing which stream *with pending data* to make progress on, I think choosing the higher-priority stream is necessary rather than advisory.  With H2, we're talking about client preferences about server responses which might not be ready yet, so it's always advisory to the server.  Here, we're talking about the application's preferences about its own data that it has already handed off.  That's something that happened within the HTTP/2 implementation, so there was no agreement or contract needed.

So long as the dependency is strictly on a higher-priority stream and the transport layer is handling priorities strictly when choosing what to send in a flow-control-limited situation, I think we avoid the deadlock.  That is, when X depends on Y, if new flow control credit is guaranteed to cause Y to make forward progress (and the other side is continuing to read from Y's stream), the other side would eventually be able to process X.

This isn't a protocol element, but an implementation element that's necessary for the protocol to be fully functional.

-----Original Message-----
From: QUIC [mailto:[email-masked]] On Behalf Of Martin Thomson
Sent: Wednesday, January 10, 2018 2:42 PM
To: Jana Iyengar <[email-masked]>
Cc: QUIC WG <[email-masked]>; Charles 'Buck' Krasic <[email-masked]>
Subject: Re: Deadlocking in the transport

On Thu, Jan 11, 2018 at 9:39 AM, Jana Iyengar <[email-masked]> wrote:
> Yes, I think there's easy misinterpretation here -- something I 
> realized today as I've had conversations about this. What I meant was 
> specifically at the API between the app and the transport, at the 
> sender. This is basically saying that to avoid deadlock due to 
> dependencies across streams, the transport write API must allow the app to express strict priorities.

Ahh, excellent, then I think at least we two are in agreement.  It seems like there is an emerging acceptance of the problem and proposed approach, I guess we might start considering how to address it.

I think that this needs to be in the main spec.  Failing to document this sort of pitfall could be fatal.  Does anyone disagree?

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 10 Jan 2018 17:56:23 -0500

I agree with the idea which I find it important. But I disagree with strict
priorities. It should be possible to for lower priorities to communicate
with reduced throughput which is readily handled by a pacing algorithm.
There need to be some guarantees for priority 0 though.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Jan 2018 10:59:47 +1100

> There need to be some guarantees for priority 0 though.

See what I mean when I said that talking about this in terms of
priorities is hazard?  If you have a concrete dependency, then
reducing throughput doesn't solve the issue.  At best, it might hide
the issue by reducing probability.

The language problem is that we can sometimes express a dependency in
a priority scheme, such as the one in h2.  This is fundamentally
different to that particular scheme in that it isn't something that
can be fudged or ignored.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Wed, 10 Jan 2018 19:08:57 -0500

I’m not sure we disagree, but it is hard to formulate exact.

An example is a bus and 2 car lanes, and a bicycle lane. You don’t stop all
traffic to ensure a bus can get through, but you reserve some capacity for
priority.

My concern is that you create a presidential cortege where you close the
highway for all other traffic for some hard to predict interval. It might
solve the primary deadlock but could generate others, and have other
unintended side effects.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 11 January 2018 at 00.59.48, Martin Thomson ([email-masked])
wrote:

---

From: Martin Thomson <[email-masked]>
Date: Thu, 11 Jan 2018 11:11:01 +1100

I don't think that those analogies are accurate in this context.
Maybe a better analogy would be a truck and the oversized trailer it
pulls.  You can't put the oversized trailer into three adjacent lanes
before the truck.

---

From: "Lubashev, Igor" <[email-masked]>
Date: Thu, 11 Jan 2018 04:54:14 +0000

Mandating a strict priority order on the sender may cause an increase in HOL blocking, if the contents of a higher-priority stream are not needed by all lower-priority streams. That happens when a higher-priority stream has MAX_STREAM_DATA that allows the sender to keep transmitting on that stream exclusively for 1-2 rtt, but one of the early packets is lost. The entire connection is blocked till that one loss is repaired.

The value of MAX_STREAM_DATA cannot be reduced below 1-2 rtt-worth of data, in case the higher-priority stream is the only stream with data.

A transport wishing to minimize HOL blocking may decide to allocate bandwidth in an other than strict priority order. Or the transport API would need to be very versatile to convey strict stream dependency graphs as well as stream priorities.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 11 Jan 2018 00:52:53 -0500

On Wed, Jan 10, 2018 at 10:55:46PM +0000, Mike Bishop wrote:
> No disagreement.  When choosing which stream *with pending data* to make
> progress on, I think choosing the higher-priority stream is necessary
> rather than advisory.  With H2, we're talking about client preferences
> about server responses which might not be ready yet, so it's always
> advisory to the server.  Here, we're talking about the application's
> preferences about its own data that it has already handed off.
> That's something that happened within the HTTP/2 implementation,
         ^^^^^^^^^^^^^^^^^^^^^^^
> so there was no agreement or contract needed.

What is that something that happened? and to which HTTP/2 implementation?

  - Dmitri.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 12 Jan 2018 04:55:03 +1100

Mike's point is that we didn't address this particular problem in h2.
We left it up to implementations to manage.

It's possible that we had this problem of dependencies between
streams, but only at the highest layers (that is, above HTTP) where
the problem already has well-established patterns for managing it.
Those being firmly along the lines of "don't do that".

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 11 Jan 2018 16:52:52 -0800

Roberto,

I'm not convinced that we need something as heavy-weight as this...
specifically, flow control so far has been in the receiver's control, which
is also the thing that owns the resource it is trying to limit exhaustion
of. This moves it out to the sender, which would require a receiver to now
commit memory based on what a sender believes is important. Reasoning about
this seems non-trivial. I worry about how all this degree of freedom will
get abused, and potential sharp edges.

If we can ensure priority consumption of the shared resource, that seems
adequate to resolve the problem on hand. Do you think something more is
required?

- jana

On Wed, Jan 10, 2018 at 12:26 PM, Roberto Peon <[email-masked]> wrote:

> Another option:
> Allow a flow-control ‘override’ which allows a receiver to state that they
> really want data on a particular stream, and ignore the global flow control
> for this.
>
> How you’d do it:
> A receiver can send a flow-control override for a stream. This includes
> the stream id to which the global window temporarily does not apply, the
> receiver’s current stream flow-control offset, and the offset the receiver
> would wish to be able to receive.
> A receiver must continue to (re)send the override (i.e. rexmit) until it
> is ack’d. It cannot send other flow-control for that stream until the
> override is ack’d.
> Thus:
> The sender (which receives the override) credits the global flow control
> with the difference between the data sent beyond the receivers
> currently-known flow-control offset upon receipt of the override.
> This allows for a receiver to resolve priority inversions which would
> otherwise lead to deadlock, even when the data/dep leading to this was not
> known to the transport. This extends beyond such issues beyond just header
> compression.
>
> Since the global flow-control exists to protect the app from resource
> exhaustion, this poses no additional risk to the application.
> Simply increasing the global flow control provides less strong
> guarantees—any stream might consume it, which doesn’t resolve the dep
> inversion. Rejiggering priorities can help to resolve this, but would
> require the sender to send priorities to the client, which is problematic
> w.r.t.races and just a web of ick.
>
> Having a custom frame type is also a less strong guarantee as it requires
> the knowledge that the dep exists to be present at the time of sending,
> which is often impossible.
>
> -=R
>
> On 1/9/18, 10:17 PM, "QUIC on behalf of Martin Thomson" <
> [email-masked] on behalf of [email-masked]> wrote:
>

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Jan 2018 01:02:53 +0000

The receiver would be the one to provide the override; The sender could hint to the receiver that it should wish this by signaling it is blocked (or deadlocked) on flow control.
-=R

From: Jana Iyengar <[email-masked]>
Date: Thursday, January 11, 2018 at 4:53 PM
To: Roberto Peon <[email-masked]>
Cc: Martin Thomson <[email-masked]>, QUIC WG <[email-masked]>
Subject: Re: Deadlocking in the transport

Roberto,

I'm not convinced that we need something as heavy-weight as this... specifically, flow control so far has been in the receiver's control, which is also the thing that owns the resource it is trying to limit exhaustion of. This moves it out to the sender, which would require a receiver to now commit memory based on what a sender believes is important. Reasoning about this seems non-trivial. I worry about how all this degree of freedom will get abused, and potential sharp edges.

If we can ensure priority consumption of the shared resource, that seems adequate to resolve the problem on hand. Do you think something more is required?

- jana

On Wed, Jan 10, 2018 at 12:26 PM, Roberto Peon <[email-masked]<mailto:[email-masked]>> wrote:
Another option:
Allow a flow-control ‘override’ which allows a receiver to state that they really want data on a particular stream, and ignore the global flow control for this.

How you’d do it:

Why:

-=R

On 1/9/18, 10:17 PM, "QUIC on behalf of Martin Thomson" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

    ## The Basic Problem

    ## Options

    ## My Preference

---

From: "Lubashev, Igor" <[email-masked]>
Date: Fri, 12 Jan 2018 01:28:25 +0000

Transport cannot solve the problem of deadlocking due to a higher protocol’s data priority on its own.  The application would need to cooperate carefully.

The problem is that it is not only the receiver that is influencing flow control, because sender transport has buffers as well.  The sender transport can refuse to accept higher-priority data from the application, if its buffers are already full with lower-priority data.

So you can end up with receiver refusing to grant additional credits for stream Y (because it cannot process stream Y w/o stream X).  If the sender’s buffers are full of stream Y data, it cannot send that data and cannot accept any additional data (for stream X).

The application must be careful not to enqueue stream Y data to the transport before it enqueues all data from stream X that stream Y data depends on.

  *   Igor

From: Roberto Peon [mailto:[email-masked]]
Sent: Thursday, January 11, 2018 8:03 PM
To: Jana Iyengar <[email-masked]>
Cc: QUIC WG <[email-masked]>; Martin Thomson <[email-masked]>
Subject: Re: Deadlocking in the transport

From: Jana Iyengar <[email-masked]<mailto:[email-masked]>>
Date: Thursday, January 11, 2018 at 4:53 PM
To: Roberto Peon <[email-masked]<mailto:[email-masked]>>
Cc: Martin Thomson <[email-masked]<mailto:[email-masked]>>, QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: Re: Deadlocking in the transport

Roberto,

- jana

How you’d do it:

Why:

-=R

    ## The Basic Problem

    ## Options

    ## My Preference

---

From: Mirja Kühlewind <[email-masked]>
Date: Fri, 12 Jan 2018 17:03:42 +0100

I disagree. I think it can be good to provide the transport hints about dependencies in application data which then could be used by the transport to optimize the sent-out scheduling, but I don’t think the transport should provide guarantees for ordered processing between streams. For me the whole point of having streams in the transport is to resolve dependencies between independent data.

Therefore, I think it would probably be good to mention this deadlock problem in the main draft but I don’t think we should add strict priorities as a transport feature to QUIC. There are several ways how an application can avoid (don’t have dependencies by using the same stream for dependent data or wait until data has be sent before sending dependent data) or resolve (read all streams and implement an additional application layer buffer) such a deadlock and these should be explained in the applicability document respectively.

My 2c,
Mirja

> Am 10.01.2018 um 23:42 schrieb Martin Thomson <[email-masked]>:
>

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Jan 2018 18:01:16 +0000

The transport *CANNOT* provide ordering guarantees w.r.t. prioritization because flows are end-to-end, whereas connections are point to point.
Flow-control, being a property of flows, ends up being asserted end-to-end though the mechanism at each hop is point-to-point.

Consider the ‘standard’ client->proxy->server topology.
If the server asserts flow control, the proxy must respect it. 
As the client<->proxy hop is asynchronous from the proxy<->server hop in most circumstances with a loadbalancing (i.e. shared flow) proxy, the proxy cannot guarantee flow-control window will be available for sending to the server even when flow control window is available from the client<->proxy.

Preemption/cancellation/retry, the addition of more resources, or finer management of resources can be used to resolve the (transitive) deadlock.

The sub-case of compression may be solvable without solving the general case as compression is point-to-point.
-=R

On 1/12/18, 8:04 AM, "QUIC on behalf of Mirja Kühlewind" <[email-masked] on behalf of [email-masked]> wrote:

    
    My 2c,
    Mirja

---

From: Roberto Peon <[email-masked]>
Date: Fri, 12 Jan 2018 18:53:02 +0000

I'm talking about this in the context of e2e application-level deadlocks.

If we simply increase the global flow control window when things are blocked , the wrong stream may make forward progress; there is no way to indicate a particular stream should make forward progress.

This may be ok-- The standard way this is resolved today is a timeout, error, and retry.

Since detecting and resolving all of these races is not reasonably solvable, this (timeout, retry) is the ultimate mechanism for any application to resolve issues anyway.

Imho, the 'blocked on flow control' message, if reliably sent by blocked senders, will give info on shared-resource (i.e. proxy-> server) deadlocks, and thus better inform actors' timeouts.

-=R

Sent via the Samsung Galaxy S7, an AT&T 4G LTE smartphone

-------- Original message --------
From: "Lubashev, Igor" <[email-masked]>
Date: 1/11/18 5:28 PM (GMT-08:00)
To: Roberto Peon <[email-masked]>, Jana Iyengar <[email-masked]>
Cc: QUIC WG <[email-masked]>, Martin Thomson <[email-masked]>
Subject: RE: Deadlocking in the transport

  *   Igor

Roberto,

- jana

How you’d do it:

Why:

-=R

    ## The Basic Problem

    ## Options

    ## My Preference

---

From: Martin Thomson <[email-masked]>
Date: Mon, 15 Jan 2018 09:41:01 +1100

I am reminded again that intermediation is why we can't have nice things.

Yes, you are right, an intermediary cannot perfectly propagate flow
control state.  That means that even if either endpoint does what it
can to avoid a deadlock, the intermediary might end up creating that
deadlock anyway.  In that case, the most expedient solution is to
terminate the dependent stream and start over.

In part, it's the ignorance of the intermediary that causes this
particular problem.  If the intermediary was aware of the protocol
details then it might be able to recognize and avoid these situations,
but that seems a little too much to expect of intermediaries. Ruling
out the entire class of intermediary that operates purely at the
transport layer is extremely harsh.

What is more likely here is that we describe this situation, explain
that it is impossible to prevent in the presence of intermediation,
and explain how to kill the right streams in order to ensure forward
progress doesn't stall indefinitely.

I'd caution against an over-reliance on BLOCKED-style messages because
they will mark the blocked stream as a problem, where the best way to
proceed is to kill dependent streams.  That is, the blocked stream is
the one most likely to hold critical state; killing that might not
unbind the blockage.  But again, identifying the right stream to kill
requires a degree of additional sophistication, effectively tracking
the dependency graph.  What seems most likely - at least in the hq
case - is that requests will have the timers and those are what will
get killed.  That works better if compression updates are on separate
streams from requests, but the other mechanisms work reasonably well
too.

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 17 Jan 2018 13:43:57 -0800

We will discuss this at the interim, but one comment, inline.

> progress doesn't stall indefinitely.

Exactly because intermediaries make things difficult, it's important to be
certain that the intermediary behavior we are discussing is one that
there's a strong argument for supporting. We have spent countless cycles on
designing around uncertain and unknown intermediary behaviors in various
parts of the IETF, and I don't want us to recreate these boogeymen. I think
it's reasonable to rule out classes of middleboxes if we don't have strong
arguments for supporting them.

---

From: Ian Swett <[email-masked]>
Date: Wed, 17 Jan 2018 17:36:45 -0500

+1 million

---

From: Martin Thomson <[email-masked]>
Date: Thu, 18 Jan 2018 18:21:35 +1100

Yes, what Ian said (and more to what Jana said).  I think that we've
some proportion of the working group who are operating on one set of
assumptions and another on a different set of assumptions on this
subject.  Until now, that didn't bother me much.  After all, that's
normal for a whole range of issues.

Now there's a concrete problem, so let's dig into this properly.

FWIW, I don't think that we'll resolve this particular issue in
Melbourne, but I hope that we can at least start that process.  This
promises to be interesting.

On Thu, Jan 18, 2018 at 9:36 AM, Ian Swett <[email-masked]> wrote:
>> certain that the intermediary behavior we are discussing is one that there's
>> a strong argument for supporting. We have spent countless cycles on

---

From: Mirja Kühlewind <[email-masked]>
Date: Thu, 18 Jan 2018 10:29:14 +0100

Hi all,

while I agree that we need to decide which middlebox behavior we want to 
support, I don't really think this is a middlebox issue. If the 
transport you are using is offering you an interface where you can send 
data over independent streams (which was the goal to avoid HOL blocking) 
but the application sends not-independent data over the streams, it is 
an application-layer issue to handle that.

Regarding middlebox behavior, I think we should support transport level 
proxies because especially in mobile networks where the link 
characteristics are quite different from the rest of the network this 
seems still to be the appropriate solution. However, I would wish that 
we could separate transport state from end-to-end payload encryption and 
would not need to terminate both...

Mirja

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Thu, 18 Jan 2018 11:28:08 -0800

[ speaking for myself only ]

On Thu, Jan 18, 2018 at 1:29 AM, Mirja Kühlewind <
[email-masked]> wrote:

> support, I don't really think this is a middlebox issue. If the transport
> you are using is offering you an interface where you can send data over
> independent streams (which was the goal to avoid HOL blocking) but the
> application sends not-independent data over the streams, it is an
> application-layer issue to handle that.
>
>
Depending on ones perspective, the congestion level flow control in QUIC
could be seen as imposing cross-stream dependency.   It is conflict between
those transport dependencies and the application's inter-stream
dependencies that leads to trouble.    Perhaps it is a bit overly
restrictive to define a stream interface that only supports truly
independent application streams (?).

> characteristics are quite different from the rest of the network this seems
> still to be the appropriate solution. However, I would wish that we could
> separate transport state from end-to-end payload encryption and would not
> need to terminate both...
>
>
Sorry, but this particular example smells of a bogeyman to me (?).   Isn't
partitioning of the transport encryption scheme is pretty unlikely at this
point?   If so, doesn't it follow that using 'transport only proxies'  to
adapt to wireless link characteristics  pretty infeasible, because in
practice such network devices would not have access to transport level
crypto keys?   [ Unlike CDN operated proxies, which have the certs for
their customer origins ].

>>>> there's

---

From: Roberto Peon <[email-masked]>
Date: Thu, 18 Jan 2018 19:46:22 +0000

I don’t believe that anything we specify in the protocol can solve the issue w.r.t. flow control and intermediaries (in  which the application framework itself might count as an intermediary).
At best we may mitigate the issue by offering a strategy that offers better outcomes than “try, timeout, retry.”

We have a concrete case here in compression. In particular, compression may be point-to-point and entirely within the domain of the protocol implementations, but flow-control is exerted end-to-end and beyond the domain of the protocol.
If compression/compression data is to be flow-controlled, then it is worth thinking about compression-specific mitigations which are better than ‘try, timeout, retry.’

-=R

On 1/17/18, 11:22 PM, "Martin Thomson" <[email-masked]> wrote:

---

From: Martin Thomson <[email-masked]>
Date: Fri, 19 Jan 2018 10:10:59 +1100

Let's be really crisp about what we mean here.

I think that we have used "middlebox" to refer to those things that
are on path, but do not hold keys.

In contrast, this is an issue that affects intermediation by entities
that terminate the security association.  These entities hold keys.
Specifically, this is an issue when those intermediaries only
understand QUIC-the-transport-protocol, and not the thing that is
running atop it.

I separately have a little trouble with the assertion that you might
want to terminate transport on path.  Managing trust there is
basically intractable (ask around for the history of "trusted proxy"
discussions in HTTP if you don't believe me).  Also, that sort of
termination is a large part of why QUIC encrypts.

On Thu, Jan 18, 2018 at 8:29 PM, Mirja Kühlewind
<[email-masked]> wrote:
> proxies because especially in mobile networks where the link characteristics
> are quite different from the rest of the network this seems still to be the
> appropriate solution. However, I would wish that we could separate transport
> state from end-to-end payload encryption and would not need to terminate
> both...
>
> Mirja
>
>
>
>