Stream creation order

[janaiyengar]

Dmitri Tikhonov writes on the mailing list:

"Section 10.1 of draft-ietf-quic-transport-03 states that “Streams MUST be created in sequential order.” My question is: why mandate stream creation order, since the other side may receive out-of-order packets? Let the implementation do what it wants with Stream IDs – as long as it does not go over the limit, all should be well.

This phrase is a holdover from the previous version; this requirement seems to be unnecessary since issue #435 has been resolved."

I think this is right. Now that we have also replaced concurrent streams, this seems quite unnecessary. This will clean up some more text, but I wanted to air this issue here before turning it into a PR.

[martinthomson]

In writing up the unidirectional stream proposal, I concluded that this was still a valuable restriction to have. Besides, creating streams out of order in that model isn't necessary.

[dtikhonov]

@martinthomson writes:

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

Why?

[martinthomson]

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.

[mikkelfj]

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, ...

[mikkelfj]

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.

[dtikhonov]

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.

[ianswett]

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.

[RyanTheOptimist]

I completely agree.

…

On Tue, Sep 26, 2017 at 6:10 AM, ianswett ***@***.***> 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. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#634 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ASp6ygbFEncB5EyBuTYtCxxfaaLsxJNKks5smPeogaJpZM4N73Yh> .

[dtikhonov]

@ianswett writes:

I would agree that this is still valuable.

Why?

[janaiyengar]

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.

[mikkelfj]

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 <notifications@github.com> 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) 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 commented. Reply to this email directly, view it on GitHub<#634 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AALzN1fFt6gkIbpzIThG4vW0c29qcvzzks5smp5rgaJpZM4N73Yh>.

[mikkelfj]

Sorry if spamming, mail app acting out.

…

________________________________ From: janaiyengar <notifications@github.com> 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) 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 commented. Reply to this email directly, view it on GitHub<#634 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AALzN1fFt6gkIbpzIThG4vW0c29qcvzzks5smp5rgaJpZM4N73Yh>.

[dtikhonov]

@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.

[dtikhonov]

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

[MikeBishop]

I think I can partially explain it. Each stream for which you're tracking state consumes some memory. You can elide out large 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.

[dtikhonov]

@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.

[martinthomson]

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?

[dtikhonov]

@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 is plausible -- why put in constraints that would make in infeasible?

[mikkelfj]

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 (notifications@github.com) 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 <#634 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AALzN2pXkXrsiGrJ9qMIbn2DEKtRaKaLks5smquVgaJpZM4N73Yh> .

[ThomasSwindells]

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:notifications@github.com] Sent: 28 September 2017 03:19 To: quicwg/base-drafts <base-drafts@noreply.github.com> Cc: Subscribed <subscribed@noreply.github.com> Subject: Re: [quicwg/base-drafts] Stream creation order (#634) 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, view it on GitHub<#634 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AYUiYlMerfA0aFMs2b8dn_RWUtLTwVZ5ks5smwIegaJpZM4N73Yh>.