Subject: Re: [quicwg/base-drafts] Stream creation order (#634)

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 25 Sep 2017 19:29:11 -0700

@martinthomson writes:
> In writing up the unidirectional stream proposal, I concluded that this was still a valuable restriction to have.

Why?

-- 
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/634#issuecomment-332068026

---

From: Martin Thomson <[email-masked]>
Date: Mon, 25 Sep 2017 22:04:13 -0700

The same reason it is valuable now, but more so.  The strict ordering restriction ensures that you can cheaply and reliably determine whether a stream is idle, open, or closed.  Open streams need a bunch of state.  If that state exists, the stream is open.  Idle streams are those that don't have state and have higher numbers than all open streams.  Closed streams are those that don't have state and have a lower number than any open stream.

Also, the only reason that you might want to open out of order is if you attached some sort of semantic to the stream ID.  I think doing that is a mistake.

-- 
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/634#issuecomment-332087267

---

From: MikkelFJ <[email-masked]>
Date: Tue, 26 Sep 2017 01:02:53 -0700

Could this "sequential" wording be made more precise? Is it OK to open stream 100, then 200, then 400, or should it be 100, 102, 104, ...

-- 
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/634#issuecomment-332118778

---

From: MikkelFJ <[email-masked]>
Date: Tue, 26 Sep 2017 08:05:03 +0000 (UTC)

It matters because you have a period where you still accept stream frames before considering them an error - and if there are holes in the stream range it might confuse the logic determing this.

-- 
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/634#issuecomment-332119272

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 26 Sep 2017 12:07:18 +0000 (UTC)

>  The strict ordering restriction ensures that you can cheaply and reliably determine whether a stream is idle, open, or closed.

I do not see how that is possible.  Here is an example: server receives a request that opens stream 11, yet the largest peer-initiated stream it knows about is 7.  Does it mean that a) client skipped stream 9  -- and thus is in violation of protocol -- or b) previous packet got lost?

> Also, the only reason that you might want to open out of order is if you attached some sort of semantic to the stream ID.

Not necessarily.  One can imagine a scenario in which a multi-threaded program keeps a pool of stream IDs that could be opened and distributes these IDs among threads.  The threads perform some preliminary work -- streams are opened in the same order that these threads complete.

There are probably other reasons why an implementation may want to be able to control the order in which streams are created.

-- 
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/634#issuecomment-332177520

---

From: ianswett <[email-masked]>
Date: Tue, 26 Sep 2017 13:10:02 +0000 (UTC)

I would agree that this is still valuable.  Unless there is an extremely compelling reason to remove the restriction(which I don't believe we have), we should keep it.

-- 
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/634#issuecomment-332192861

---

From: Ryan Hamilton <[email-masked]>
Date: Tue, 26 Sep 2017 13:50:32 +0000 (UTC)

I completely agree.

On Tue, Sep 26, 2017 at 6:10 AM, ianswett <[email-masked]> wrote:

> I would agree that this is still valuable. Unless there is an extremely
> compelling reason to remove the restriction(which I don't believe we have),
> we should keep it.
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/quicwg/base-drafts/issues/634#issuecomment-332192861>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ASp6ygbFEncB5EyBuTYtCxxfaaLsxJNKks5smPeogaJpZM4N73Yh>
> .
>

-- 
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/634#issuecomment-332204392

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 27 Sep 2017 02:54:42 -0700

@ianswett writes:
> I would agree that this is still valuable.

Why?

-- 
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/634#issuecomment-332471168

---

From: janaiyengar <[email-masked]>
Date: Wed, 27 Sep 2017 19:13:51 +0000 (UTC)

I'm hearing the argument for keeping this restriction, which is that it allows for a simpler implementation. It doesn't break the protocol if the sender doesn't open streams sequentially. Together, these seem to suggest that we should keep this restriction, but make it a SHOULD from a MUST.

-- 
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/634#issuecomment-332626142

---

From: MikkelFJ <[email-masked]>
Date: Wed, 27 Sep 2017 12:30:55 -0700

SHOULD would void any transport level simplifications so you might as well remove the constraint if not strictly enforced. If course specific app protocols may differ but transport is still affected.

________________________________
From: janaiyengar <[email-masked]>
Sent: Wednesday, September 27, 2017 9:13:47 PM
To: quicwg/base-drafts
Cc: MikkelFJ; Comment
Subject: Re: [quicwg/base-drafts] Stream creation order (#634)

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub<https://github.com/quicwg/base-drafts/issues/634#issuecomment-332626142>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AALzN1fFt6gkIbpzIThG4vW0c29qcvzzks5smp5rgaJpZM4N73Yh>.

-- 
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/634#issuecomment-332630536

---

From: MikkelFJ <[email-masked]>
Date: Wed, 27 Sep 2017 12:32:42 -0700

Sorry if spamming, mail app acting out.

—

-- 
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/634#issuecomment-332630997

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 27 Sep 2017 13:10:00 -0700

> It matters because you have a period where you still accept stream frames before considering them an error - and if there are holes in the stream range it might confuse the logic determing this.

Which stream frames do you mean?  If stream frames for the streams that are in the "hole," then I do not see where the confusion would be:  A stream frame for a stream that is not yet open opens that stream.  If the stream count goes over the limit, a connection error is flagged and the connection is aborted.

-- 
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/634#issuecomment-332640629

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 27 Sep 2017 20:12:15 +0000 (UTC)

@janaiyengar, @mikkelfj -- could you please elaborate on the simplification part?

-- 
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/634#issuecomment-332641161

---

From: Mike Bishop <[email-masked]>
Date: Wed, 27 Sep 2017 22:39:36 +0000 (UTC)

I think I can partially explain it.  Each stream for which you're tracking state consumes some memory.  You can elide out large contiguous chunks by saying that:

- Lowest idle stream ID is X
- Of streams < X, any stream not in my state table is closed
- Table contains any idle or open streams < X

If an implementation is implementing tracking in this way, the arrival of stream 200 when X=100 means inserting 100,102,...,198 into the table as idle, then 200 as open.  By mandating that they be used in order, even if reordering occurs, you are less likely to do large chunks of this work at a time (you might get 108 when X=100, but not 200) and if you *do* have to do a large chunk of work the work is still timely because you know all those streams have data in-flight so you would have been doing the work in a few packets anyway.

-- 
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/634#issuecomment-332675911

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 28 Sep 2017 02:11:49 +0000 (UTC)

@MikeBishop, I see -- thank you for the explanation.  @martinthomson must have been also alluding to this 
when he wrote that "open streams need a bunch of state."  The draft says that

> opening a stream causes all lower-numbered streams in the same direction to become open.

Now I disagree with arguments for mandating stream creation order on _two_ counts -- implementation and protocol specification.

***I. Implementation.***

The way to track open streams that you describe is suboptimal.  The assertion that "open streams need a bunch of state" is not true: this is because stream transition from idle to open states can be treated in a purely conceptual fashion.  Real stream state -- that is, some data structures and linkages -- does not have to be allocated until the first frame received for that stream.  This is how we chose to implement it at LiteSpeed, guided by a sort of rule of thumb "delay doing work until you have to."

As a side note, doing a large chunk of work to allocate stream resources is not always timely: consider the case when a connection is closed shortly after this chunk of work is performed.  This is more likely to occur than not in this situation, as a large hole in the sequence of incoming stream IDs may be a symptom of network issues.

***II. Protocol Specification***

A protocol should strive to be simpler rather than more complex.  If something is not required by the protocol itself -- which the order of stream creation is not -- it does not belong in the specification.  The protocol specification should not be a place where the way to implement something is mandated.  This may prevent a clever implementer from employing some optimization mechanism that the protocol authors had not thought about.

-- 
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/634#issuecomment-332707015

---

From: Martin Thomson <[email-masked]>
Date: Thu, 28 Sep 2017 02:19:11 +0000 (UTC)

Your implementation point there seems to motivate the opposite.  As Mike said, receiving stream X might open stream X-2, but the receiver doesn't have to do anything at that point.

Here's a different way to think about this: why do you want to open streams out of 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/634#issuecomment-332708135

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 28 Sep 2017 02:30:11 +0000 (UTC)

@martinthomson, my point was that an efficient stream-tracking logic is not difficult achieve even in the face of out-of-order stream creation.  Let the implementer figure out what to do, not mandate how to do it.

I do not want to create streams out of order -- HTTP over QUIC does not require it.  Nevertheless, I think that [the scenario I described above](https://github.com/quicwg/base-drafts/issues/634#issuecomment-332177520) is plausible -- why put in constraints that would make in infeasible?

-- 
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/634#issuecomment-332709703

---

From: MikkelFJ <[email-masked]>
Date: Thu, 28 Sep 2017 00:03:13 -0700

stream frame simplification - it’s been a while since I had time to work on
my implementation so it is from rough memory, and - I haven’t read the full
discussion in this thread - so please bear with me:

Once a stream state closes there is a period where you still have to accept
incoming stream frames for the pariticular stream id. This might be
retransmission of stream data in reverse direction stream data or stream
control frames with flow control etc. Those frames may be silently
discarded or handled as per protocol. After a while those frames should be
considered a serious error resulting in connection termination because
clearly the peer isn’t paying attention.

The simplest way to handle this is to track a lower bound on stream ID. For
this reason it is also really important that “sequential”   means next
higher value and not just an arbitrary higher number (I made a comment on
some issue asking for clarification on this).

If stream ID's are unordered, it is necessary to keep track of all recently
active streams. The rate of new streams can be high, and the lifetime low,
so the dictionary can potentially hold millions of streams.

Another concern is new streams. These must be rejected if they have already
been closed. For unordered streams this is intractable because you need to
keep a dictionary holding billions of random stream id.

OTOH - if unordered streams are permitted AND it is permitted to reuse
stream ID’s after a while (past grace period of pending stream frames),
then stream IDs can be used for context, such as file id on a host.This
still requires a dictionary of all recently closed streams, but it is not
intractable.

Further, ordereded stream ID’s are significant when using unidirectional
partial reliable streams where each part of a virtual stream (message) is a
new stream ID. Here ordering of stream IDs provide the necessary sequencing
- of course a protocol is free to impose this constraint, and it doesn’t
affect transport.

If streams move to unidirectional only, this changes a lot because you only
need to keep the lower level ack logic and the stream context can be closed
immediately after sending FIN or RST. I strongly recommend moving to
unidirectional only.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 27 September 2017 at 22.09.57, Dmitri Tikhonov ([email-masked])
wrote:

@mikkelfj <https://github.com/mikkelfj> writes:

It matters because you have a period where you still accept stream frames
before considering them an error - and if there are holes in the stream
range it might confuse the logic determing this.

Which stream frames do you mean? If stream frames for the streams that are
in the "hole," then I do not see where the confusion would be: A stream
frame for a stream that is not yet open opens that stream. If the stream
count goes over the limit, a connection error is flagged and the connection
is aborted.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<https://github.com/quicwg/base-drafts/issues/634#issuecomment-332640629>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AALzN2pXkXrsiGrJ9qMIbn2DEKtRaKaLks5smquVgaJpZM4N73Yh>
.

-- 
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/634#issuecomment-332746949

---

From: ThomasSwindells <[email-masked]>
Date: Thu, 28 Sep 2017 08:16:33 +0000 (UTC)

If you are treating streams as being message and have multiple producer threads of those messages then being able to allocate each thread its own pool of stream ids removes some message by message synchronization requirements. You could also assign different blocks of message ids to different cpu cores to have a quick and easy way to keep processing affinity. Admittedly none are killer requirements, but spinning your question round, why would you want to impose strict serialization of the system if you don’t have to?

From: Martin Thomson [mailto:[email-masked]]
Sent: 28 September 2017 03:19
To: quicwg/base-drafts <[email-masked]>
Cc: Subscribed <[email-masked]>
Subject: Re: [quicwg/base-drafts] Stream creation order (#634)

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub<https://github.com/quicwg/base-drafts/issues/634#issuecomment-332708135>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AYUiYlMerfA0aFMs2b8dn_RWUtLTwVZ5ks5smwIegaJpZM4N73Yh>.

-- 
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/634#issuecomment-332763510