Subject: [quicwg/base-drafts] Stream ID sequential order may create head of queue blocking (#435)

From: huitema <[email-masked]>
Date: Wed, 12 Apr 2017 18:01:50 -0700

The transport draft says in Section 10.2 that "Streams MUST be created in sequential order." This is logical. Suppose now that an application sends the STREAM-DATA opening stream 5 in one packet number X, and then the opening of stream 7 in the next packet, number X+1. This is a fairly natural thing to do, for example, for QUIC over DNS, where each transaction opens its own stream. 

Suppose now that packet number X is lost. Packet X+1 will be processed. The receiver will see for the first time a reference to stream 7, without having seen stream 5. In a strict reading of the spec, since streams MUST be created in sequential order, the receiver should signal an error, since streams have been created out of order. But that's fiendish. Or maybe it should queue the stream 7 packet until stream 5 has been open, but that would cause head of queue blocking. Or maybe it should not care about the MUST, and just open stream 7.

Now, of course, if the receiver is willing to accept stream ID opened out of order, we can have different problems. How much out of order is too much? You may want to say "1", but consider that a client could easily pack a dozen DNS requests and as many stream opening in a single packet. If that packet is lost, there is a gap of a dozen stream ID.

Not sure what the right solution should be. 

-- 
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/435

---

From: Marten Seemann <[email-masked]>
Date: Wed, 12 Apr 2017 18:55:37 -0700

I don't see any problem here. Since streams are created sequentially, a receiver can open all streams with lower IDs when a such reordered packet arrives. By doing so, the concurrent steak limit is enforced implicitly.

This is how we implemented it in quic-go. Note that this also works out nicely if you expose an Accept() API for new 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/435#issuecomment-293755295

---

From: huitema <[email-masked]>
Date: Thu, 13 Apr 2017 10:20:32 -0700

Marten, I agree that there is no real problem if the client does indeed create streams in order. But I am concerned with an adversarial client creating streams out of order. Suppose that the server, like you suggest, "open all streams with lower IDs". Suppose that the adversarial client opens stream 5, and then stream 1000005. Are you going to open 1 million streams? Will that not have a significant impact on server performance?

-- 
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/435#issuecomment-293965920

---

From: MikkelFJ <[email-masked]>
Date: Thu, 13 Apr 2017 10:43:59 -0700

There are two solutions currently going as I understand. The current draft-01 with limit on concurrent active streams which the receiver announces to the sender. So the receiver will drop the stream or the connection if the limit is exceeded. However, there are race conditions. So the new proposal is for the receiver to annouce the maximum id accepted. It can increase this as older streams are being closed.

Both of these view points assumes that streams are like toilet paper so to speak, you just pull the next available. However, if you have an application that wants to assign semantics to the stream id, then things get problematic. For example you might want to download download profile images for the nearest 10000 connections in a social network. Either you have to associate a profile with each stream, and then the stream is not a simple image, or you assume that the stream id maps to a profile index. Then you set max stream to 10100 and add 100 to the profile index and keep the lower streams for special purposes. Then you 10000 streams concurrently. Though not by malicous intent,  a server might overwhelm the client. So it might want to limit the number of concurrent streams even if the limit is set higher. But there is no way to do this with fixed limit solution, and with the concurrent solution you are forced to send the lower identifiers first, which could be fine. But if you later have stream 10000 - 20000 for dripping activity feeds, concurrency wont work.

These scenarios are essentially not supported by QUIC. You could multiplex activity feeds over fewer 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/435#issuecomment-293971954

---

From: huitema <[email-masked]>
Date: Thu, 13 Apr 2017 11:35:17 -0700

OK. I get that we clients are supposed to abide by the "concurrent stream limit" set by the server, and that will prevent silly stream openings. On the other hand, I get it now, after reading the draft several times. Which means that at minimum there is a documentation problem.

1) The "concurrent stream limit" transport parameter is first mentioned in section 7.3.1.  Transport Parameter Definitions. Except that it is called "concurrent streams" in 7.3.1, and then referred to as "concurrent stream limit" in the rest of the document. I suggest updating 7.3.1 so the parameter is called "concurrent stream limit".

2) The text in section 10.2 is hard to read. The first line of the last paragraph says "All streams, including stream 1, count toward this limit." But what "this" points to is undefined. I propose to rewrite that to "All streams, including stream 1, count toward the concurrent stream limit." Maybe with a forward pointer to the next section.

-- 
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/435#issuecomment-293985549

---

From: huitema <[email-masked]>
Date: Thu, 13 Apr 2017 12:12:58 -0700

Also, It might be nice to write something about stream number attacks in the Security section. For example, if an implementation just picks a very large value for the concurrent stream limit, it might be subject to denial of service attacks.

-- 
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/435#issuecomment-293995289

---

From: MikkelFJ <[email-masked]>
Date: Sat, 15 Apr 2017 03:41:00 -0700

It is quite difficult to track if it is valid for peer to initiate a stream. Even if you have a limit of, say, 10 concurrent streams, the peer streams might be stream id 2, 6, 100006, 100008. If you then see a stream id of 8, or stream id 100004, you have no idea if the stream was closed or a valid new stream unless you remember all previously opened streams, which is not feasible in praxis. Assuming streams only exists in a limited range won't work, because stream id 1 obviously cannot conform to that.

In addition, the requirement that streams must be opened in sequential order is vague. Does this mean the next higher value, or any value higher than previous? This is important if you use packet sequences or time to attempt to constrain the window where you track closed streams. It is also important if you use a interval set because you can issue an error if the set grows large, but only if by sequential in the strict sense.

This problem is largely the same whether you use a concurrency limit or a fixed upper stream id limit because eventually that limit will have a high value.

-- 
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/435#issuecomment-294285450

---

From: Martin Thomson <[email-masked]>
Date: Mon, 17 Apr 2017 22:17:09 -0700

Marking this as editorial.  We have protections against attacks like this (stream 10 being opened causes 2, 4, 6, and 8 to open).  It's just not consistently documented.  That fix was added relatively recently.

-- 
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/435#issuecomment-294683375

---

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 19:02:48 -0700

My understanding is that this is addressed by the changes in #421.

-- 
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/435#issuecomment-297887283

---

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 19:02:48 -0700

Closed #435.

-- 
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/435#event-1061435271