Subject: [quicwg/base-drafts] Use a "stream" for transmitting CIDs (#1826)

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 18:47:11 +0000 (UTC)

Transmission of new and retired CIDs is something that do not need low latency, but it seems like it is going to have lot of code specific to the purpose.

Looking at #1799, I am starting to wonder if we could use a "stream" to carry the new and retiring CIDs (sorry for suggesting to change the approach at a late moment).

**The proposed design**

Like the CRYPTO frame that carries the TLS messages, We will have a CID frame that carries the CID messages. This is essentially a "CID stream" much like the "CRYPTO stream."

The format of a CID frame will be equivalent to the CRYPTO frame.

A CID message has the following structure. Type is either NEW_CID (0) or RETIRE_CID (1).

```
 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Type (8)   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Length (i)                         ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       CONNECTION ID (*)                     ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
```

Instead of flow-control based on octets, the number of CIDs given to the peer by the use of the NEW_CID messages will be governed by a MAX_NEW_CID frame that is equivalent to the MAX_STREAM_ID frame, except for the fact that it carries the number of CIDs.

**The Upsides**

Code reuse _and_ design reuse.

We can reuse a lot of code. Basically, we only need glue code and codec for the CID messages. All the code that relates to retransmission and back-pressure can be reused. We are also reusing a design that we are familiar with.

These aspects lead to less issues.

**The Downsides**

Head-of-line blocking in the delivery of CIDs. But I do not think that is an issue in practice.

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

---

From: Nick Banks <[email-masked]>
Date: Tue, 02 Oct 2018 11:52:09 -0700

You assume code reuse, but that is not necessarily the case. I'd prefer not to add this much overhead just for CIDs. Especially this late in the process.

-- 
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/1826#issuecomment-426389452

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 02 Oct 2018 11:52:35 -0700

I proposed something very similar (use a special stream) at the very first CID DT meeting a couple of months ago.  Everyone else was against 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/1826#issuecomment-426389575

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 18:57:42 +0000 (UTC)

@nibanks My argument would be that because we are this late in the process, it is good to reuse an existing design rather than trying to fix issues with a special-purpose mechanism that none of us have implemented.

@dtikhonov Yeah I am sorry for that. Later changes (i.e. sending "retire" as an explicit signal and the reintroduction of sequence numbers to NEW_CID) made me inclined to the design.

-- 
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/1826#issuecomment-426391184

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 02 Oct 2018 19:02:55 +0000 (UTC)

> My argument would be that because we are this late in the process, it is preferable to reuse an existing mechanism rather than trying to fix issues with a special-purpose mechanism that none of us have implemented.

+1

> Later changes (i.e. sending "retire" as an explicit signal and the reintroduction of sequence numbers to NEW_CID) made me inclined to the design.

OK.  I support this proposal, which makes two of us, @kazuho.

-- 
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/1826#issuecomment-426392862

---

From: Marten Seemann <[email-masked]>
Date: Tue, 02 Oct 2018 12:09:44 -0700

This sounds like an interesting proposal. I really like the idea of the MAX_NEW_CID frame, not because it would lead to code reuse (at least not for me), but because we're using the same design both for flow control bytes and for stream IDs.

I'm wondering if we really need two different framing layers here (one for the CID frame and one for the CID message). Could we just introduce a sequence number for NEW_CID (which would be limited by MAX_NEW_CID), and keep RETIRE_CID as separate frame?

-- 
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/1826#issuecomment-426394905

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 12:16:21 -0700

> I'm wondering if we really need two different framing layers here (one for the CID frame and one for the CID message). Could we just introduce a sequence number for NEW_CID (which would be limited…

IMO, the costs with that approach are:
* Without using a "stream", you'd need to do book-keeping of each CID being received by the NEW_CID frame, because the frames can arrive out-of-order. "Stream" guarantees in-order-delivery and therefore you only need to maintain a counter.
* Not carrying NEW_CID and RETIRE_CID as a "message" on top of "streams" also means that you would have a retransmission logic specific to those frames.

-- 
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/1826#issuecomment-426396820

---

From: Marten Seemann <[email-masked]>
Date: Tue, 02 Oct 2018 12:22:57 -0700

> Without using a "stream", you'd need to do book-keeping of the CID-sequence number relation being received by the NEW_CID frame, because the frames can arrive out-of-order. "Stream" guarantees in-order-delivery and therefore you only need to maintain a counter.

At least in my implementation, I'd have to write a separate implementation of that CID "stream", unless we reuse an actual QUIC stream, so as far as I can see, it wouldn't make a big difference.

> Not carrying NEW_CID and RETIRE_CID as a "message" on top of "streams" also means that you would have a retransmission logic specific to those frames.

Why is that? They'd just be normal retransmittable frames, wouldn't they?

-- 
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/1826#issuecomment-426398819

---

From: MikkelFJ <[email-masked]>
Date: Tue, 02 Oct 2018 12:26:16 -0700

Conceptually I like the idea, however:

They are not streams, and they will be an odd special case in the stream logic. All the nice automatic handling via stream semantics become one big special case. You can give at a pseudo stream id and feed it into the the pipeline unless you starting with modulo 8 stream id's.

I'm not saying the alternative isn't just as bad, but I don't see this as an easy win.

-- 
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/1826#issuecomment-426399735

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 12:29:42 -0700

@marten-seemann @mikkelfj The proposed encoding of "CID stream" is exactly the same as that of the "CRYPTO stream". Why cannot you reuse that the same way you would reuse an actual QUIC stream?

> Why is that? They'd just be normal retransmittable frames, wouldn't they?

IIUC, there are two ways to send states. One is to retransmit frames. The other is to transmit the current state when necessary. For stacks that implement the latter approach, NEW_CID and RETIRE_CID will be a special-purpose logic. I am not saying that it is hard. But "retransmission of frames" is not all the stacks have as a concept.

-- 
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/1826#issuecomment-426400728

---

From: MikkelFJ <[email-masked]>
Date: Tue, 02 Oct 2018 19:40:07 +0000 (UTC)

Yes, that also worries me a bit. But CRYPTO has a limited lifespan and can be done in a hacked custom implementation without interfering with a highly tuned stream implementation. you could also hack the CID stream, but that is then another and longer living hack. 

-- 
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/1826#issuecomment-426403707

---

From: MikkelFJ <[email-masked]>
Date: Tue, 02 Oct 2018 12:44:19 -0700

If stream frames need to be ordered, I think tagging a serial on them as proposed in the above is simpler. Then you have no FIN bit or RST whatever to consider. Nor can you write across packet boundaries. Etc. I think your stream proposal already does most of that, so it is actually far from a stream abstraction.

-- 
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/1826#issuecomment-426404958

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 12:47:08 -0700

> But CRYPTO has a limited lifespan and can be done in a hacked custom implementation without interfering with a highly tuned stream implementation. you could also hack the CID stream, but that is then another and longer living hack.

I am not sure if that is true, considering the fact that CRYPTO stream for 1-RTT packets lives forever.

> If stream frames need to be ordered, I think tagging a serial on them as proposed in the above is simpler. Then you have no FIN bit or RST whatever to consider.

CRYPTO stream that "CID stream" reuses does not have FIN or RST.

-- 
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/1826#issuecomment-426405814

---

From: Nick Banks <[email-masked]>
Date: Tue, 02 Oct 2018 12:51:23 -0700

I still feel that making them a stream is more overhead than necessary. For instance, if you sent three new CIDs to the peer and the first is lost, if you have a stream design, the second two stay around longer than necessary on the sender side.

Overall, I'm still not sure of the problem that currently exists that this is the solution to. What doesn't work with the current model that would require this design to fix? I feel like we're at a phase where we should start taking changes required to fix a particular problem, not changes that (some believe) make for a cleaner design.

-- 
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/1826#issuecomment-426406979

---

From: MikkelFJ <[email-masked]>
Date: Tue, 02 Oct 2018 12:52:06 -0700

> I am not sure if that is true, considering the fact that CRYPTO stream for 1-RTT packets lives forever.

I was afraid you'd say that (I haven't reached the HS part in detail).

>CRYPTO stream that "CID stream" reuses does not have FIN or RST.

Which just proves my point, that it is a special case with special handling. I actually think it may be fine to do special handling for stream frames as well, as long as we don't call it streams and instead optimize it for what it is rather than a leaking abstraction.

-- 
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/1826#issuecomment-426407272

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 13:09:20 -0700

@nibanks 
> I still feel that making them a stream is more overhead than necessary. For instance, if you sent three new CIDs to the peer and the first is lost, if you have a stream design, the second two stay…

It is true that head-of-line blocking exists. But IMO it is not an issue latency-wise (because there is no need to race for 1-RTT for delivering / retiring CIDs) nor memory-wise (because CIDs are so small compared to stream buffers and because there would only be few CIDs inflight.

> Overall, I'm still not sure of the problem that currently exists that this is the solution to. What doesn't work with the current model that would require this design to fix? I feel like we're at a…

FWIW, my view is that the proposal retains the new model (i.e. retirement of CIDs always transmitted as an explicit signal), at the same time changing the transmission framework of the CIDs to a mechanism that have proven record (rather than introducing a framework specific to the purpose).

As I have stated earlier, it is beneficial to use a proven method because we are at a later moment like this, instead of trying to fix all the design issues of a framework specific to transmitting CIDs that we haven't seen any interop.

-- 
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/1826#issuecomment-426412476

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 02 Oct 2018 13:16:20 -0700

> the proposal retains the new model (i.e. retirement of CIDs always transmitted as an explicit signal), at the same time changing the transmission framework of the CIDs to a *mechanism that have proven record (rather than introducing a framework specific to the purpose)*.

[Emphasis added.]

Agree 100%.

-- 
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/1826#issuecomment-426414558

---

From: Marten Seemann <[email-masked]>
Date: Tue, 02 Oct 2018 13:18:06 -0700

> As I have stated earlier, it is beneficial to use a proven method because we are at a later moment like this, instead of trying to fix all the design issues of a framework specific to transmitting…

The proven method here is the use of the MAX_NEW_CID frame (because we have that kind of frame for flow control and stream IDs). I'm not sure if putting things on a "stream" will actually simplify implementations.

Maybe we can combine your proposal of the MAX_NEW_CID with my proposal of adding a sequence number?

-- 
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/1826#issuecomment-426415126

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 02 Oct 2018 13:30:55 -0700

> I proposed something very similar (use a special stream)...

To elaborate on my thinking about this.

In my mind, using an actual stream (with STREAM and MAX_STREAM_DATA frames) eliminates the need for new frame types.  Imagine a special flow-controlled CID stream.  For simplicity, assume CIDs are 8 bytes long.  If the flow control window is 64 bytes, writing 32 bytes to the stream (4 CIDs) will trigger a MAX_STREAM_DATA from the peer.  This is the signal to write more CIDs to the stream.  If the peer is not consuming the CIDs, MAX_STREAM_DATA is not sent and no CIDs are emitted.

The original objections to this was that the transport layer does not *own* the streams.  I don't know how to respond to this.  It seems that adding new frame types and protocol-like specifications around them for every new thing that we think to add to QUIC is not the most pragmatic thing to do.  Take the CRYPTO frames, for example: chances are, they are just wrappers on the stream mechanism anyway.

Perhaps a stream-based CID mechanism could be made into an extension which would use a new type of unidirectional stream for this purpose.

On the other hand, it seems we're going around in circles -- redesigning the design of the Design Team...

-- 
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/1826#issuecomment-426419088

---

From: Marten Seemann <[email-masked]>
Date: Tue, 02 Oct 2018 20:43:29 +0000 (UTC)

> In my mind, using an actual stream (with STREAM and MAX_STREAM_DATA frames) eliminates the need for new frame types. Imagine a special flow-controlled CID stream. For simplicity, assume CIDs are 8…

That seems like a misuse of streams to me. You could end up with CID frames split up in the middle. I'm not saying that this wouldn't work, it just doesn't seem like a nice way to engineer a solution to me.

> The original objections to this was that the transport layer does not own the streams. I don't know how to respond to this. It seems that adding new frame types and protocol-like specifications around them for every new thing that we think to add to QUIC is not the most pragmatic thing to do. Take the CRYPTO frames, for example: chances are, they are just wrappers on the stream mechanism anyway.

They're not, in my implementation.
To me, using frames and protocol-like specification for new protocol features seems like exactly the way things 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/1826#issuecomment-426422980

---

From: Mike Bishop <[email-masked]>
Date: Tue, 02 Oct 2018 14:03:14 -0700

I'm dubious about the stream approach.  You could model it like flow control, but unlike flow control, there's also the retire issue -- stream data is never really "retired."  Also, while there are reasons we want all sequence numbers to be generated in order, there's no reason you need to block using CID 7 because you haven't seen CID 6.

-- 
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/1826#issuecomment-426429346

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 14:07:26 -0700

@MikeBishop FWIW, I do not think that flow control of CIDs is essential, even though I included that in this proposal. CRYPTO streams do not have flow control, and "CID frames" would work fine without flow control too (assuming that we continue allowing the receiver to "forget" CIDs).

> there's also the retire issue -- stream data is never really "retired." 

Would you mind elaborating on this? For the CID, the proposal has a RETIRE message. But I assume you are referring to something else.

> Also, while there are reasons we want all sequence numbers to be generated in order, there's no reason you need to block using CID 7 because you haven't seen CID 6.

That's correct. But it is still a requirement for book keeping. My point is that it would be worthwhile to consider reusing the "streams" approach, if we are to require book keeping using sequence numbers in a situation where HoLB is not a concern.

-- 
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/1826#issuecomment-426430637

---

From: Mike Bishop <[email-masked]>
Date: Tue, 02 Oct 2018 14:17:05 -0700

You're still building the new/retire machinery inside this proposal, because it's needed and existing streams don't have that concept.  So you have those messages *inside* a stream-like structure.  I'm having trouble seeing what this actually makes simpler; I think having frames that affect state is a more natural fit to how QUIC works.

-- 
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/1826#issuecomment-426433584

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 14:22:36 -0700

The benefit of using "streams" as a conveyer of new/retire messages is that you aren't required to the bookkeeping on the receiver side.

Current design (also #1799) requires the receiver of the CIDs to track the sequence numbers of CIDs to see that if the newly received CID is a retransmit. Stream has the logic to detect and ignore retransmits; reusing that simplifies the design.

-- 
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/1826#issuecomment-426435050

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 02 Oct 2018 22:22:02 +0000 (UTC)

FWIW, the details of detecting the retransmissions of NCID frame is still under discussion in #1821. Changing to a stream-based approach closes all the corner cases that we need to care.

-- 
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/1826#issuecomment-426450266

---

From: janaiyengar <[email-masked]>
Date: Tue, 16 Oct 2018 15:52:18 -0700

Discussed, this might be overkill. Closing.

-- 
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/1826#issuecomment-430428811

---

From: janaiyengar <[email-masked]>
Date: Tue, 16 Oct 2018 15:52:19 -0700

Closed #1826.

-- 
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/1826#event-1908146667