Subject: [quicwg/base-drafts] Implicitly opened streams add complexity (#896)

From: ianswett <[email-masked]>
Date: Mon, 23 Oct 2017 07:32:05 -0700

PR#894 reminded me that implicitly opened streams add complexity to the stream text and I'm not aware of any real value.

Efficient implementations would have to store a small amount of data to indicate a stream ID less than the largest had not been used, but I think that's true either way.

I realize there are cases when one COULD use this as a feature(ie: in protocols where both sides send info right after the TCP handshake), but you could also just wait for the stream frame to arrive.

I realize this has been brought up before, but now that we've resolved the uni/bidi direction, I think it makes sense to reconsider whether this is a feature or a bug.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896

---

From: MikkelFJ <[email-masked]>
Date: Mon, 23 Oct 2017 15:17:44 +0000 (UTC)

Makes sense. The only thing is guidance on how large gaps in yet not seen streams before treating it as an error.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338693591

---

From: ianswett <[email-masked]>
Date: Mon, 23 Oct 2017 08:22:22 -0700

I think the MAX_STREAM_ID should mean we don't need any special text on gaps.  It's typically most efficient to use streams in order for both peers, so hopefully most implementations will do that.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338695228

---

From: MikkelFJ <[email-masked]>
Date: Mon, 23 Oct 2017 08:28:06 -0700

True. But the requirement of opening in order should probably also go the way of the Dodo then: https://github.com/quicwg/base-drafts/issues/634

But ... then it is impossible to track which streams have never been seen and which streams have been closed because you cannot save all that state when the stream count gets high. If streams are openened in order, you can do some heuristics - but again, then some guidelines are needed. How do we deal with that?

Also note related issue: https://github.com/quicwg/base-drafts/issues/662

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338697186

---

From: Marten Seemann <[email-masked]>
Date: Mon, 23 Oct 2017 17:08:31 +0000 (UTC)

Can we use this to get rid of the mod 4 stream ID logic that was necessary for unidirectional streams, and the even/odd change?

There’s still the issue that e.g. a reordered MAX_DATA frame would open the stream, and you don’t know if this is a unidirectional stream, so the API would have to wait until a STREAM_FRAME (which would have a uni flag then) arrives before returning that stream to the application. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338728993

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 23 Oct 2017 10:53:29 -0700

I kind of like implicit open, you say it adds no value. I've mentioned before why implicit open is simpler to implement and less prone to deadlock. 

With implicit open I have to store 3 state parameters:
* next openable stream
* Structures for streams that are open (lazily allocated)
* Stream ids for streams that are unopened

Whenever a stream is closed I can send a MAX_STREAM_ID immediately, since I can get rid of state, and I only keep track of state for streams that are open.

however without implicit open, the implementation is a bit more complicated and more similar to flow control. My thoughts are that I would have to store:
* streams currently closed
* lowest closed stream

I would be able to advance MAX_STREAM_ID only when lowest closed stream moves forward. This seems more prone to deadlock. Do people have alternate implementations ideas that could work better for the non-implicit open case?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338742829

---

From: ianswett <[email-masked]>
Date: Mon, 23 Oct 2017 10:55:59 -0700

Martin's PR #894 seems to suggest streams can be opened in any order, but you're right that this makes the order of creation much less important.

@marten-seemann I think the mod 4 stream ID logic really falls out of the choice to have separate namespaces for unidirectional and bidirectional streams, with separate MAX_STREAM_IDs and such.  

One of the benefits of separate namespaces is that MAX_DATA would have a stream ID that specifies whether it's unidirectional or bidi, so you'd know which it was.  But you're correct that MAX_DATA needs to open a stream(regardless of whether we implicitly open streams), which is weird, but I think the only reasonable option to avoid stream flow control states from getting out of sync.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338743557

---

From: ianswett <[email-masked]>
Date: Mon, 23 Oct 2017 11:02:02 -0700

@siyengar I think the implementation should be identical, since something like what you describe is the easiest way to efficiently implement this.  The only difference is whether a stream can be written to once a higher stream ID has been seen.  

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338745346

---

From: MikkelFJ <[email-masked]>
Date: Mon, 23 Oct 2017 18:09:55 +0000 (UTC)

> I would be able to advance MAX_STREAM_ID only when lowest closed stream moves forward.

This is a bit unfortunate if you have tempoary streams mixed with long running streams.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338747633

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 23 Oct 2017 18:10:52 +0000 (UTC)

@ianswett ya what i'm worried about is 1 long polling http request stream stalling the entire connection. My sketch of an implementation is the implementation I can think of which is faithful to the max stream id state limit, i.e. I store only as much state as stream id allows. I'm mostly wondering if people have other ideas for efficient implementation which is not susceptible to the deadlock. If it can't be implemented efficiently without the deadlock or relaxing the meaning of stream limit then it seems not so great to allow streams to be opened in any order.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338747914

---

From: ianswett <[email-masked]>
Date: Mon, 23 Oct 2017 11:44:38 -0700

@siyengar I'll try to clarify what I have in mind.

- A hash map of streams, stream_id -> stream*
- Largest Opened Stream

Assuming the hash_map has an efficient size operation, you know how many streams less than Largest Opened Stream are currently or could soon be in use, so you can still increase MAX_STREAM_ID after a stream is closed.

I would expect one would insert null into the hash map when a Stream has been implicitly created to minimize memory usage.  Without implicit open, you do the same, and the only difference is you can't write on a stream that has a null entry, whereas today you can write on that stream.  There's also probably a change in when you get the OnStreamCreated(stream_id) callback or the equivalent.

Does that make sense, or am I missing something?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338758007

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 23 Oct 2017 20:42:07 +0000 (UTC)

in this construction, how would you know whether a stream that is not in the hash map is closed or unopened?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338790192

---

From: ianswett <[email-masked]>
Date: Mon, 23 Oct 2017 20:43:59 +0000 (UTC)

If it's closed, there would be no entry.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338790665

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 23 Oct 2017 20:49:57 +0000 (UTC)

@ianswett ya i think that your method could work

* stream structures for opened streams (lazily allocated)
* list of stream ids for unopened streams
* largest opened stream

The key idea here is that you don't have to keep track of streams higher than largest opened stream even if they are unopened. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338792265

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 23 Oct 2017 21:01:56 +0000 (UTC)

if you look at this construction it's basically equivalent to the construction of implicit open which I mentioned before, the only difference is that you're not allowing the receiver to send bytes on that stream.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338795573

---

From: ianswett <[email-masked]>
Date: Mon, 23 Oct 2017 16:50:41 -0700

Completely agreed.  The goal of this issue is to decide whether implicit open is a feature or a bug, given it is very similar in implementation.  The fact one can write on a stream prior to receiving anything on that stream just seems weird to me.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338829217

---

From: Martin Thomson <[email-masked]>
Date: Tue, 24 Oct 2017 01:49:46 +0000 (UTC)

For my benefit, how is this different from #634?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338847072

---

From: ianswett <[email-masked]>
Date: Tue, 24 Oct 2017 10:15:05 +0000 (UTC)

I think of them as two questions which I don't 'think' have a large effect on each other:
1) Should streams be implicitly opened?
2) Must streams be created in order?

If you say no to the second, then streams should really not be implicitly created, but even if you say yes to the second, the peer doesn't need to implicitly create them.

Personally, I do like in order creation, though I don't think there's much of a way to enforce it, and I do not like implicitly opened streams.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338943174

---

From: MikkelFJ <[email-masked]>
Date: Tue, 24 Oct 2017 05:59:09 -0700

> The fact one can write on a stream prior to receiving anything on that stream just seems weird to me.

I think it would be very good to treat it as a fatal error if the server sends on a client initiated stream bidi before the client has sent any data on that stream, and vice versa. And on any uni stream at point. And vice versa for server intiated.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-338981149

---

From: ekr <[email-masked]>
Date: Tue, 24 Oct 2017 14:21:20 +0000 (UTC)

On Tue, Oct 24, 2017 at 5:59 AM, MikkelFJ <[email-masked]> wrote:

> I think it would be very good to treat it as a fatal error if the server
> sends on a client initiated stream bidi before the client has sent any data
> on that stream, and vice versa. And on any uni stream at point. And vice
> versa for server intiated.
>

I have heard Ian say this too, but I haven't heard a good rationale for
this other than it seems ugly. There are TCP-based protocols where the
passive opener speaks first (telnet) or simultaneously (ssh) and the
accept() is the trigger to speak, and so this would be a straightforward
mapping to QUIC.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-339006922

---

From: MikkelFJ <[email-masked]>
Date: Tue, 24 Oct 2017 21:15:48 +0000 (UTC)

The thing is that you set limit to stream transmission you are willing to accept from the peer. The streams that you initiate is something that you manage. If the peer starts broadcasting on streams you have no intention to ever manage, only after completing a number other streams, then the peer is in fact having a card blance for overloading your stream state.

Also, as you say, it is ugly because you can't make assumptions on stream state based on a single action: either starting an own stream, or receiving data from a peer stream.

As to having channels where the peer can respond early. Telnet is roughly a single channel so the point does not extend to quick. You could model telnet with two uni-directional streams, or you could send an early ready message to allow the peer to transmit.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-339134094

---

From: Martin Thomson <[email-masked]>
Date: Tue, 24 Oct 2017 22:58:06 -0700

Here's my take on this, noting that I don't actually care for the complexity, see below:

In-order opening ensures that the passive endpoint (the one not opening streams) isn't surprised.  Ordered opens ensures that it is possible to look at the largest stream ID and the set of open streams and make decisions about what to put in MAX_STREAM_ID.  Without that, you have to account for unopened streams as well or you might be surprised when the opening peer uses all those streams.

We can't enforce in order opening in the general case in the presence of loss.  If two packets are lost containing the frames that open streams X and X + i, the recipient has no way of knowing which packet contained which frame.  And once you get to retransmissions, either could appear first.

That doesn't help a great deal with implicit opening.  The reason that I think we have implicit open is largely as a consequence of being able to assume in order opening.  If X+3i opens, then you can safely assume that you just missed the packets for X+2i and proceed on that basis.  It might be that the endpoint can perform resource allocations, and bump MAX_STREAM_DATA based on its new understanding of what streams are in use. 

I tend to see implicit opens as not being absolutely necessary, but rather creating an incentive to use streams in order.

In most protocols, there's not a lot you can do with an implicitly opened stream, but @ekr shared an example of one protocol that can use the information.

I think that @ekr's point about opening as a distinct action from the transmission of data is an interesting one that we should consider separately.  As much as I love huge-ball-of-string protocol engineering, it seems like we can make a decision about the use case without drawing all this mess into the discussion.  In the general case we don't want to rely on implicit signals for that, though it seems reasonable to allow implicit signals to be used in the event that we decide to retain the idea of implicit open.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-339223186

---

From: ianswett <[email-masked]>
Date: Thu, 26 Oct 2017 20:02:07 +0000 (UTC)

Explicit signals are definitely better than implicit in my book, but I agree we want to encourage in order stream usage.  MAX_STREAM_ID removes our need to count the number of open streams, so we don't have to move reserved streams into the open state immediately.

In the case of TCP, there is an explicit signal, which is a TCP handshake.  QUIC has explicit signals too(STREAM frames), so we should use them.  Martin raised a good point about empty stream frame potentially being useful here(#901).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-339784080

---

From: Igor Lubashev <[email-masked]>
Date: Fri, 27 Oct 2017 15:50:28 -0700

Here is my take on this.

1. Streams MUST be created in order (by the creator)

2. As far as QUIC API is concerned, there is NO such thing as IMPLICITLY opened streams.  There should not even be such a state documented in the spec.  Instead, the non-creator side of the app should be prepared that streams will not be opened in order (due to reordering/loss).

3. As far as QUIC Transport _implementation_ is concerned, it is helpful to keep track of "unopened" streams before MAX_STREAM_ID to facilitate MAX_STREAM_ID updates.

P.S.  The violation of the MUST in (1) may not be detected reliably, but it may cause eventual starvation due to the lack of MAX_STREAM_ID updates.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/896#issuecomment-340115337