Subject: Deadlock avoidance proposal

From: "Lubashev, Igor" <[email-masked]>
Date: Tue, 23 Jan 2018 03:49:43 +0000

The problem with deadlocking QUIC streams is the possibility that the sender (or proxy) will "use up" connection flow control credits on lower-priority streams, blocking the receiver from making forward progress with any streams.  The receiver has no mechanism to direct/force the sender to send on preferred streams.

I would like to propose a concept of "stream data credit" - the concept of extra flow control credits that can only be used by a specific stream.  A STREAM_DATA_CREDIT frame would update such credits (see below).  Data sent on a stream will consume its own credits as much as it can and connection credits (updated by MAX_DATA) for the rest of the data.

The updated connection flow control accounting:

"
For each stream, "used connection credits" is "MAX(the_largest_received_offset - stream_data_credits, 0)".

The sum of "used connection credits" on all streams -
including streams in terminal states, but excluding stream 0 - MUST NOT exceed
the value advertised by a receiver (i.e. MAX_DATA).  An endpoint MUST terminate a connection
with a QUIC_FLOW_CONTROL_RECEIVED_TOO_MUCH_DATA error if it used more connection credits
than the maximum data value that it has sent, unless this is a result of a
change in the initial limits (see {{zerortt-parameters}}).
"

The receiver will be able to grant dedicated credits to the high-priority stream w/o requiring the sender or the intermediary to know anything about the semantics of the protocol and without worrying that the sender/intermediary will "squander" the credits on unimportant streams.

==========================================================================

STREAM_DATA_CREDIT frame.

The frame updates Data Credit for a stream.

~~~
0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Stream ID (i)                        ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Data Credit (i)                        ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~~~

The fields in the STREAM_DATA_CREDIT frame are as follows:

Stream ID:

: The stream ID of the stream that is affected encoded as a variable-length
  integer.

Data Credit:

: A variable-length integer indicating the new total data credit for the stream.

For each stream Data Credit starts with 0.  The sender can only increase Data Credit in subsequent STREAM_DATA_CREDIT frames for the same stream, but loss and reordering can cause STREAM_DATA_CREDIT frames to be received out of order.  STREAM_DATA_CREDIT frames that do not advance Data Credit for the stream MUST be ignored.

==========================================================================

Comments?

  *   Igor

---

From: "Lubashev, Igor" <[email-masked]>
Date: Tue, 23 Jan 2018 17:27:13 +0000

I think one can take this idea one step further.

Right now, flow control on a stream is limiting stream_data_offset to
  MIN(stream_max_data, connection_max_data - SUM(stream_data_offset))

The new alternative would be limiting stream_data_offset to
  MAX(stream_max_data, connection_max_data - SUM(stream_data_offset))

A simple way this would work is that the receiver would designate, say, 75% of connection buffer space to the "common" connection pool (and try to keep it at that level via MAX_DATA frames) and 25% of the buffer space - to per-streams buffers.  That way, no stream can be starved just because the sender has chosen to send data on some other stream earlier.  In this scheme, the total_buffer_space, per_stream_buffer_size, max_concurrent_streams can determine commn_buffer_size.   An alternative way to manage space would be reserving some per-stream buffers only for "high-priority" streams that cannot be blocked - the scheme to use could be an application's decision.

  *   Igor

From: Lubashev, Igor [mailto:[email-masked]]
Sent: Monday, January 22, 2018 10:50 PM
To: [email-masked]; [email-masked]
Subject: Deadlock avoidance proposal

"

~~~
0                   1                   2                   3

Stream ID:

Data Credit:

Comments?

  *   Igor

---

From: Roberto Peon <[email-masked]>
Date: Tue, 23 Jan 2018 20:54:51 +0000

The stream-data-credit would need to be expressed as a stream offset (this resolves the races and allows the math you have down there to work properly). I suspect this is what you mean in the first place.

Otherwise, looks good. This would fall under the ‘allow more buffering at the application’ bullet Martin had, but I believe that is a reasonable thing to do if it is constrained and directed by the application (which could decide to cancel a stream too).

Since flow control is e2e, this doesn’t impact memory at a proxy.

What this doesn’t solve is the detection problem—if there are multi-parties going through any chokepoint, that chokepoint would need to advertise that it was blocked on flow control to the entities which were draining data from it. An application could infer that this might be happening by not receiving data, but that could happen because the sender is slow rather than being blocked.

-=R

From: QUIC <[email-masked]> on behalf of "Lubashev, Igor" <[email-masked]>
Date: Tuesday, January 23, 2018 at 2:50 PM
To: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Deadlock avoidance proposal

The problem with deadlocking QUIC streams is the possibility that the sender (or proxy) will “use up” connection flow control credits on lower-priority streams, blocking the receiver from making forward progress with any streams.  The receiver has no mechanism to direct/force the sender to send on preferred streams.

I would like to propose a concept of “stream data credit” – the concept of extra flow control credits that can only be used by a specific stream.  A STREAM_DATA_CREDIT frame would update such credits (see below).  Data sent on a stream will consume its own credits as much as it can and connection credits (updated by MAX_DATA) for the rest of the data.

“
For each stream, “used connection credits” is “MAX(the_largest_received_offset - stream_data_credits, 0)”.

The sum of “used connection credits” on all streams -
“

The receiver will be able to grant dedicated credits to the high-priority stream w/o requiring the sender or the intermediary to know anything about the semantics of the protocol and without worrying that the sender/intermediary will “squander” the credits on unimportant streams.

~~~
0                   1                   2                   3

Stream ID:

Data Credit:

Comments?

  *   Igor

---

From: "Lubashev, Igor" <[email-masked]>
Date: Tue, 23 Jan 2018 22:07:59 +0000

*   The stream-data-credit would need to be expressed as a stream offset (this resolves the races and allows the math you have down there to work properly). I suspect this is what you mean in the first place.

Yes, the stream-data-credit in this proposal is expressed in ever-increasing offsets.

  *   Otherwise, looks good. This would fall under the ‘allow more buffering at the application’ bullet Martin had, but I believe that is a reasonable thing to do if it is constrained and directed by the application (which could decide to cancel a stream too).
  *   Since flow control is e2e, this doesn’t impact memory at a proxy.

Exactly

  *   What this doesn’t solve is the detection problem.

If you look at my follow-up proposal (which is effectively changing the meaning of max_stream_data to mean stream_data_credit), you may not need to have robust deadlock detection, because deadlocks due to transport cannot happen.  The only deadlocks possible with the follow-up scheme are deadlocks due to the application’s circular dependency, not sender’s choice of which stream to send first

-=R

From: QUIC <[email-masked]<mailto:[email-masked]>> on behalf of "Lubashev, Igor" <[email-masked]<mailto:[email-masked]>>
Date: Tuesday, January 23, 2018 at 2:50 PM
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Deadlock avoidance proposal

“

~~~
0                   1                   2                   3

Stream ID:

Data Credit:

Comments?

  *   Igor

---

From: Roberto Peon <[email-masked]>
Date: Tue, 23 Jan 2018 22:56:15 +0000

This need not be protocol-visible so long as the flow-control-override/stream-data-credit exists—instead, this is an implementation strategy.
-=R

From: QUIC <[email-masked]> on behalf of "Lubashev, Igor" <[email-masked]>
Date: Wednesday, January 24, 2018 at 4:28 AM
To: "Lubashev, Igor" <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: RE: Deadlock avoidance proposal

A simple way this would work is that the receiver would designate, say, 75% of connection buffer space to the “common” connection pool (and try to keep it at that level via MAX_DATA frames) and 25% of the buffer space – to per-streams buffers.  That way, no stream can be starved just because the sender has chosen to send data on some other stream earlier.  In this scheme, the total_buffer_space, per_stream_buffer_size, max_concurrent_streams can determine commn_buffer_size.   An alternative way to manage space would be reserving some per-stream buffers only for “high-priority” streams that cannot be blocked – the scheme to use could be an application’s decision.

  *   Igor

“

~~~
0                   1                   2                   3

Stream ID:

Data Credit:

Comments?

  *   Igor

---

From: Roberto Peon <[email-masked]>
Date: Tue, 23 Jan 2018 23:33:53 +0000

We must assume that any finite buffer can be consumed. Thus, any partitioning of the available memory which is finite cannot prevent this from occurring. When it occurs, it may induce indefinite head-of-line-blocking on all flow-controlled upstream nodes in the topology.

In other words, the problem is not preventable with any mechanism we introduce within the protocol. At best we can make it detectable and provide mechanisms to limit the damage when it happens.

The stream-data-credit stuff is a good mechanism to limit the damage while still allowing for finite memory use, but it is useful only when/if an application knows that some action is required.

There are alternate mechanisms that would also be useful: cancelling a stream, for instance.
-=R
p.s. the real problem is that we’ve delegated the ownership of the data to the intermediary by allowing the sender to flush its bytes upon receiving p2p acks. The best solution here would be e2e acks (whether application-layer or transport or both).

From: "Lubashev, Igor" <[email-masked]>
Date: Wednesday, January 24, 2018 at 9:08 AM
To: Roberto Peon <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: RE: Deadlock avoidance proposal

Exactly

-=R

“

~~~
0                   1                   2                   3

Stream ID:

Data Credit:

Comments?

  *   Igor

---

From: "Lubashev, Igor" <[email-masked]>
Date: Tue, 23 Jan 2018 23:51:22 +0000

If you have finite buffer memory AND allow all of that buffer memory to be used for any stream, you cannot avoid deadlocks.  However, if you dedicate some buffer memory to each stream (does not need to be much – just needs to be enough for one “message”), you can always make progress on your highest-priority stream.

The trade-off is that some memory may end up unused (memory dedicated to streams that do not have anything to send).

If you want to increase your memory utilization even further, you may end up doing blocked-stream detection (responding to STREAM_BLOCKED frames) and give extra memory to those streams “just-in-time”.

- Igor

From: Roberto Peon [mailto:[email-masked]]
Sent: Tuesday, January 23, 2018 6:34 PM
To: Lubashev, Igor <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: Deadlock avoidance proposal

From: "Lubashev, Igor" <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, January 24, 2018 at 9:08 AM
To: Roberto Peon <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: RE: Deadlock avoidance proposal

Exactly

-=R

“

~~~
0                   1                   2                   3

Stream ID:

Data Credit:

Comments?

  *   Igor

---

From: "Lubashev, Igor" <[email-masked]>
Date: Wed, 24 Jan 2018 00:00:14 +0000

*   We must assume that any finite buffer can be consumed. Thus, any partitioning of the available memory which is finite cannot prevent this from occurring. When it occurs, it may induce indefinite head-of-line-blocking on all flow-controlled upstream nodes in the topology.

To be more specific, “it may induce indefinite head-of-line-blocking on all flow-controlled upstream nodes in the topology” is incorrect.  “Indefinite” blocking means deadlock.  HOL blocking – possible; deadlock – no.

A deadlock is when NO stream can make any progress without killing some stream.  If each stream has “dedicated” memory buffer (or the client is willing to dedicate a memory buffer to the highest-priority blocked stream), the highest-priority stream will not block – the receiver will consume it, free that stream-private buffer, and sender will send more data to that stream.

  *   Igor

From: Lubashev, Igor [mailto:[email-masked]]
Sent: Tuesday, January 23, 2018 6:51 PM
To: Roberto Peon <[email-masked]>; [email-masked]; [email-masked]
Subject: RE: Deadlock avoidance proposal

- Igor

From: Roberto Peon [mailto:[email-masked]]
Sent: Tuesday, January 23, 2018 6:34 PM
To: Lubashev, Igor <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: Deadlock avoidance proposal

Exactly

-=R

“

~~~
0                   1                   2                   3

Stream ID:

Data Credit:

Comments?

  *   Igor

---

From: Roberto Peon <[email-masked]>
Date: Wed, 24 Jan 2018 00:45:38 +0000

Yes. That is why I'm saying that this is a strategy that is up to an implementation.

For a naive receiver, which does not self-examine to see that it is blocking things, the STREAM_BLOCKED can allow a reaction within an RT.

The tradeoff, thus, is an RTT of delay when in the degraded state of having a full buffer for a naive implementation.

That may still be cheaper than causing connection reconnects as it would need to rexmit the in-flight data as well as losing the congestion context/state.

Allocating 25% (or some similar amount) of memory to prevent an uncommon-case of blocking seems suboptimal. That memory could instead be used for the common case, whether caching or additional connections...

-=R

________________________________
From: Lubashev, Igor <[email-masked]>
Sent: Tuesday, January 23, 2018 3:51:22 PM
To: Roberto Peon; [email-masked]; [email-masked]
Subject: RE: Deadlock avoidance proposal

- Igor

Exactly

-=R

“

“

~~~

0                   1                   2                   3

|                        Stream ID (i)                        ...

|                        Data Credit (i)                        ...

~~~

Stream ID:

  integer.

Data Credit:

Comments?

  *   Igor

---

From: Roberto Peon <[email-masked]>
Date: Wed, 24 Jan 2018 00:52:59 +0000

I'm trying to avoid bikeshedding :)

There is connection-level blockage, and stream-level blockage.

One can cause the other, but not *every* involved connection may be affected.

With finite memory, blockage/deadlock cannot be prevented.

The only 'real' solution is e2e acks (separate from p2p flow control), allowing intermediaries to discard data p2p, suffering only a decrease in efficiency, i.e. to have the sender buffer data until the ultimate receiver has received it.

Everything else is a patch, not that I'd personally object to patches...

-=R

________________________________
From: Lubashev, Igor <[email-masked]>
Sent: Tuesday, January 23, 2018 4:00:14 PM
To: Lubashev, Igor; Roberto Peon; [email-masked]; [email-masked]
Subject: RE: Deadlock avoidance proposal

  *   Igor

- Igor

Exactly

-=R

“

“

~~~

0                   1                   2                   3

|                        Stream ID (i)                        ...

|                        Data Credit (i)                        ...

~~~

Stream ID:

  integer.

Data Credit:

Comments?

  *   Igor

---

From: "Lubashev, Igor" <[email-masked]>
Date: Wed, 24 Jan 2018 01:33:32 +0000

Merging threads.

I think we are in a general agreement here.

The features of the proposal are:
(a) Connection-level blockage (exhaustion of shared credits) does not cause stream-level blockage (if the receiver is willing to allocate some dedicated buffer memory to the stream, either in advance or after STREAM_BLOCKED);
(b) Application-level logic can cause stream-level blockage (by refusing to read, which will exhaust any finite buffer).

And I really like your suggestion that a naive receiver can use STREAM_BLOCKED as a signal to the application to decide whether it wants to unblock a particular stream by temporarily giving it an extra buffer allocation.  And since this is likely to be a very uncommon case, a naïve receiver may perform ok.

  *   Igor

P.S.

I think the last proposal "limiting stream_data_offset to MAX(stream_max_data, connection_max_data - SUM(stream_data_offset))" may actually simulate the way we want to manage buffers better then the current design.  Either the transport is managing its own buffers, in which case it is happy to dedicate all/most of them to the "common connection pool" w/o per-stream limits and let the sender decide how to use them.  Or the transport is actually managing per-stream buffers belonging to applications, in which case the transport does not want to impose an arbitrary restriction on streams (in a form of the "MAX_DATA") and, instead, it may actually wish to "throw in" some extra buffers of its own for the "common pool".

From: Roberto Peon [mailto:[email-masked]]
Sent: Tuesday, January 23, 2018 7:46 PM
To: Lubashev, Igor <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: Deadlock avoidance proposal

-=R

From: Roberto Peon [mailto:[email-masked]]
Sent: Tuesday, January 23, 2018 7:53 PM
To: Lubashev, Igor <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: Deadlock avoidance proposal

-=R

________________________________
From: Lubashev, Igor <[email-masked]<mailto:[email-masked]>>
Sent: Tuesday, January 23, 2018 4:00:14 PM
To: Lubashev, Igor; Roberto Peon; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: RE: Deadlock avoidance proposal

To be more specific, "it may induce indefinite head-of-line-blocking on all flow-controlled upstream nodes in the topology" is incorrect.  "Indefinite" blocking means deadlock.  HOL blocking - possible; deadlock - no.

A deadlock is when NO stream can make any progress without killing some stream.  If each stream has "dedicated" memory buffer (or the client is willing to dedicate a memory buffer to the highest-priority blocked stream), the highest-priority stream will not block - the receiver will consume it, free that stream-private buffer, and sender will send more data to that stream.

  *   Igor

From: Lubashev, Igor [mailto:[email-masked]]
Sent: Tuesday, January 23, 2018 6:51 PM
To: Roberto Peon <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: RE: Deadlock avoidance proposal

If you have finite buffer memory AND allow all of that buffer memory to be used for any stream, you cannot avoid deadlocks.  However, if you dedicate some buffer memory to each stream (does not need to be much - just needs to be enough for one "message"), you can always make progress on your highest-priority stream.

If you want to increase your memory utilization even further, you may end up doing blocked-stream detection (responding to STREAM_BLOCKED frames) and give extra memory to those streams "just-in-time".

- Igor

p.s. the real problem is that we've delegated the ownership of the data to the intermediary by allowing the sender to flush its bytes upon receiving p2p acks. The best solution here would be e2e acks (whether application-layer or transport or both).

  *   Otherwise, looks good. This would fall under the 'allow more buffering at the application' bullet Martin had, but I believe that is a reasonable thing to do if it is constrained and directed by the application (which could decide to cancel a stream too).
  *   Since flow control is e2e, this doesn't impact memory at a proxy.

Exactly

  *   What this doesn't solve is the detection problem.

If you look at my follow-up proposal (which is effectively changing the meaning of max_stream_data to mean stream_data_credit), you may not need to have robust deadlock detection, because deadlocks due to transport cannot happen.  The only deadlocks possible with the follow-up scheme are deadlocks due to the application's circular dependency, not sender's choice of which stream to send first

-=R

"

"

~~~

0                   1                   2                   3

|                        Stream ID (i)                        ...

|                        Data Credit (i)                        ...

~~~

Stream ID:

  integer.

Data Credit:

Comments?

  *   Igor