Re: Report on Unidirectional Streams in Minq

Eric Rescorla <> Sun, 01 October 2017 21:04 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id D3E20134B1E for <>; Sun, 1 Oct 2017 14:04:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id DxU1mIED8ZHs for <>; Sun, 1 Oct 2017 14:04:03 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4002:c05::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 49FD0134B22 for <>; Sun, 1 Oct 2017 14:04:03 -0700 (PDT)
Received: by with SMTP id i83so691001ywb.7 for <>; Sun, 01 Oct 2017 14:04:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=uYa1UPf1uTXLsFpjPOCcQAVJ76F66WpE/KeGjp8wQVc=; b=EJ6ithkRooMJDxACezhSpgVxIlNEWggcpNYoyDsKPZrx+nGLtzWcOh61aNCiBd55X0 rdsJRipRlsNpLlyJgCuepSe9uBoLvKslUPco8X96HTydCdGpUuRqYDlaj4xL9ZkvzWUL 3EcaDCAAUILDE2nCqTRigetzJyyikBewdJ3kRgg/ol0zeDQFclOcBydIdHUi7thj42rV INr0atqccxP2p2qxM1DuUMrT5CrwUOE2sasT5KSTgBEXaZnASdUoOaTvrZ13rFsB5vh9 kodMj4rYEWSekw+Bt5KwVn72z1kZavXCh5+SmDx5k+gANqsPa/W5JdmJC0qMo5598NRP bO3w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=uYa1UPf1uTXLsFpjPOCcQAVJ76F66WpE/KeGjp8wQVc=; b=c639+hHaxaI+cV+SpbE1Qzds7aimvKHSY/V49aKEsSUFZEu7maye/Y8X45M7rzuQnz 17Gmbvi1Y9+N6MQFsK9eihUuI9meiX/HzsHGYxtLHmdRK8UQ9mthbTNLfaA6SBo8RCu9 HYzCNIcMU2AD6rJ5OGfdcBa/KUeQX7XEHAKCNSfseL3GC2IJShbGYk8uZZyeBU7Lpprp 7Xr80MF8ty8BQhktJAKpr7GdHgPffHR4cXmnJTWE8lGCSgVe7ARIT3xd+3Bs+qDf6oyL hV/UW8xVHbH8+4vpc+C7ui9wdZM9mQwO4zjOYZkl1s8PAfCT7bnoMoG+PO5HAtOZ6onH m5BA==
X-Gm-Message-State: AMCzsaXylIE8+osxM4ITijPS8blcx8yw/Lj+wyJjD2NjOsEJV3NDcrzm e497oodcFsIRUtvnhY0EobtlbGEX9L6CCQ+nMoBxwA==
X-Google-Smtp-Source: AOwi7QBZBgoUykzuKnCfbyoSx8ttxzjWTAfI5fKezItTXOJDDyul7iBy+8BXhrejggtwy8xfxa8e818W178pDU1AMnU=
X-Received: by with SMTP id p12mr282320ybm.462.1506891842354; Sun, 01 Oct 2017 14:04:02 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Sun, 1 Oct 2017 14:03:21 -0700 (PDT)
In-Reply-To: <>
References: <> <>
From: Eric Rescorla <>
Date: Sun, 1 Oct 2017 14:03:21 -0700
Message-ID: <>
Subject: Re: Report on Unidirectional Streams in Minq
To: =?UTF-8?Q?Mikkel_Fahn=C3=B8e_J=C3=B8rgensen?= <>
Content-Type: multipart/alternative; boundary="089e0828b4f0fa9630055a8298be"
Archived-At: <>
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sun, 01 Oct 2017 21:04:08 -0000

I'm not sure I have any useful insights on this, as my implementation
handles them more or less the same. Can you explain why you think this
would be different with unidirectional versus bidirectional?


On Sun, Oct 1, 2017 at 1:38 PM, Mikkel Fahnøe Jørgensen <>

> Thanks,
> I only skimmed this superfast, but one the observations appear to not
> cover one of my key points:
> You can create and close uni-streams at at very high rate of many streams
> per packet, without waiting for peer response, assuming the ACK framework
> handles retransmission. Any insights on this?
> Kind Regards,
> Mikkel Fahnøe Jørgensen
> On 1 October 2017 at 22.32.02, Eric Rescorla ( wrote:
> Hi folks,
> As promised I spent a bunch of time hacking unidirectional streams
> into Minq and I'm here to report back [0]. Specifically, I
> implemented:
>   - PR#643 -- Unidirectional Streams
>   - PR#720 -- Add bidirectional streams on top of unidirectional
>   - A bidirectional stream API that mostly mimics Minq's original API
>     for -05.
> The following is kind of a wall of text, so you could also skip this
> and refer to my slides [1].
> Minq's master object is the Connection, which has a list of Streams
> indexed by stream ID. Applications register a handler with the
> connection to be notified of new events.
>    type ConnectionHandler interface {
>     // The connection has changed state to state |s|
>     StateChanged(s State)
>     // A new stream has been created (by receiving a frame
>     // from the other side. |s| contains the stream.
>     NewStream(s *Stream)
>     // Stream |s| is now readable.
>     StreamReadable(s *Stream)
>    }
> Streams get created in two ways:
> - Locally via Connection.CreateStream()
> - Remotely, in which case the application is notified via a callback to
>   ConnectionHandler.NewStream().
> Streams themselves have the APIs you would expect, namely, Read(),
> Write(), Close(), Reset(), etc. You get notified of stream readability
> by a callback to ConnectionHandler.StreamReadable(), at which point
> you can do Stream.Read(). As expected, Stream.Read() returns
> WOULDBLOCK when no data ia available
> As noted above, we start with the Connection object (only relevant fields
> shown):
>    type Connection struct {
>     handler          ConnectionHandler
>     streams          []*Stream
>     maxStream        uint32
> outputClearQ     []frame // For stream 0
> outputProtectedQ []frame // For stream >= 0
>    }
> As you can see, streams are in an array slice, so they're contiguously
> indexed by stream ID. Right now, I have no provision for reclaiming
> the unused bottom part of the array, but it would be straightforward
> to index by |streamId| - |minStream|, which I think is consistent with
> the design implied by the requirement to create streams in sequence.
> Because Streams are bidirectional, each stream actually consists of a
> pair of half streams.
>    type streamHalf struct {
>     s             *stream           // pointer to parent
>     log           loggingFunction
>     dir           direction         // Sending or receiving
>     closed        bool              // Is the half-stream closed
>     offset        uint64            // The
>     chunks        []streamChunk
>     maxStreamData uint64
>    }
>    // Internal object to allow unit testing.
>    type stream struct {
>     id         uint32
>     log        loggingFunction
>     state      streamState
>     send, recv *streamHalf
>   blocked    bool // Have we returned blocked
>    }
>    // Public API object, which needs access to the Connection
>    type Stream struct {
>     c *Connection
>     stream
>    }
> Outgoing data is enqueued into |stream.chunks|, and then periodically
> the connection polls the stream for all the chunks which are permitted
> by stream-level flow control and enqueues them into
> |Connection.outputClearQ| or |Connection.outputProtectedQ|. At this
> point, the connection owns the data and is responsible for
> transmitting it, subject to connection-level flow control, and
> (presumably) congestion control once I have that implemented [2].
> Incoming data gets queued (sorted) into |stream.chunks| for later
> reassembly at the time when someone calls I'm not sure
> I love this, because it means I don't have a good view of the incoming
> queue size (which I'd need to account for separately), but it allowed
> me to share data structures between incoming and outgoing, which
> seemed kind of natural when I did it (this architecture is replicated
> in the unidirectional streams design, but it's probably less natural
> there).
> With the unidirectional branch, Minq offers two APIs. The first is a
> straightforward mapping of PR#720, in which we have two objects:
>   SendStream -- used for writing
>   RecvStream -- used for reading
> As before, we have a handler object, but it's directional now:
>    type ConnectionHandler interface {
>     // The connection has changed state to state |s|
>     StateChanged(s State)
>     // A new receiving stream has been created (by receiving a frame
>     // from the other side. |s| contains the stream.
>     NewRecvStream(s *RecvStream)
>     // Stream |s| is now readable.
>     StreamReadable(s *RecvStream)
>    }
> Obviously SendStreams are locally created and RecvStreams are remotely
> created. SendStreams can be created using
> Connection.CreateSendStream() and you learn about remotely created
> RecvStreams by a callback to ConnectionHandler.NewRecvStream().
> Second-created streams can be marked as "related" to a single
> first-created stream, using Connection.CreateRelatedSendStream() with
> the appropriate RecvStream as the argument [3]. Streams have a
> Related() API to tell you if they are related to some other stream.
> The {Send,Recv}Stream APIs are about what you'd expect. You can
> Write() on SendStream and Read() on RecvStream(). Right now, you can
> Close() and Reset() SendStreams, but not do anything on RecvStreams()
> or than ignore them. Eventually I'll probably offer
> RecvStream().Mute() or something to let you send STOP_SENDING.
> Minq also includes a bidirectional API that's layered on top of
> unidirectional streams. I've created a Connection2 structure that's
> intended as a wrapper around Connection [4]:
>    type Connection2 struct {
>     Connection
>     shim    *connection2ShimHandler
>     streams []*Stream // Odd for client originated, even for server.
>    }
>    type Stream struct {
>     id   uint32
>     send *SendStream
>     recv *RecvStream
>    }
> Basically, Stream is just a pair of SendStream and RecvStream and
> Connection2 does the bookkeeping to keep them connected (I even do the
> odd/even ID thing that QUIC-05 has). Connection2 has the same handler
> API as Minq for QUIC-05, and the shim is responsible for translating
> unidirectional events into bidirectional events.
> Internally, what's going on here is that when you call CreateStream()
> Minq creates a Stream with a nil RecvStream. When a new remote stream
> is detected, we check RecvStream.Related(). If they are related to an
> existing SendStream then we will in the relevant |Stream.send| slot.
> Otherwise, we create a new SendStream that's related to the incoming
> stream and notify the application of the creation of the new
> bidirectional stream.
> Note that this all works fine if one side does the undirectional API
> and one does the bidirectional API. My test programs actually exercise
> this. Of course, there's an assumption that the peer conforms to a 1:1
> mapping. If we define unidirectional streams, we'll need some protocol
> mechanism to know if the other side is exercising this level of
> increased flexibility or not. I can imagine a number of options here
> (e.g., ALPN).  We could also forbid 1:N mappings but I think that
> would be a mistake as it's a cool feature/benefit of doing
> unidirectional.
> The entire bidirectional wrapper shim is < 150 lines of Go code.
> (
> Converting my test application to this API was a matter of just
> changing class names, e.g., s/Connectionb/Connection2/.
> In my implementation, I assume that at the time Minq hears about a
> stream, you know if its related to a given existing stream.  That way
> you can immediately either associate it with that stream or make a new
> local stream. In my implementation, I always send Related Stream Id
> and assume that you never get an "unrelated" stream frame before a
> "related" one. The spec doesn't really require that right now, and
> offline MT suggested just sending related with offset=0 but I think
> that's a mistake, because it means that you need to hold stream frames
> in some provisional "undetermined" state until you get that frame. I
> would suggest instead that we require that you include the field until
> one of the frames is ACKed.
> Sending and receiving streams still share a lot of common components:
>     type baseStream struct {
>     state         streamState
>     id            uint32
>     log           loggingFunction
>     offset        uint64
>     chunks        []streamChunk
>     maxStreamData uint64
>     isRelated     bool
>     related       uint32
>     }
>     type sendStream struct {
>     baseStream
>     blocked bool
>     }
>     type recvStream struct {
>     baseStream
>     }
> Most of this is the same as with bidirectional streams.  As above,
> it's probably possible to make them more asymmetrical.
> The connection maintains separate lists of sending and receiving
> streams and it's straightforward to create and access them without
> worrying about the odd/even stuff.
> At the end of the day, I think this shows that these designs aren't
> really that disssimilar. I was able to convert Minq to unidirectional
> streams in about 16 total hours of work (basically a long plane flight
> plus the next morning). While I had to make a bunch of changes to the
> internal structures, basically none of them modified anything tricky,
> and in particular the flow control mechanics and the like are
> basically unchanged, except for a bunch of mechanical-type
> transformations like referring to |sendStream.chunks| instead of
> |stream.send.chunks|. The only really new protocol machinery is the
> new frame format for related streams.
> There are a few pros/cons that are worth noting about these designs.
> - Without a bidirectional API, having unidirectional streams is more
>   work for the programmer. However, with an API shim, the difference
>   is trivial.
> - Because undirectional streams are inherently more flexible, it's
>   possible for the sides to try to use different mappings, e.g., one
>   side expects paired and the other expects 1:N. We'll need some way
>   of making sure that doesn't happen, maybe ALPN?
> - The "Related Stream ID" frame indicator needs fleshing out a bit.
>   From the application's perspective, it should never hear about a
>   stream without knowing its related status. And as noted above, I
>   think it would be best if we required that all "first flight" stream
>   frames that are related include the fied
> - Undirectional streams kind of sharpen the confusion about exactly
>   what kinds of "closure" we want to allow. Specifically, what should
>   implementations be able to say about their willingness to receive?
>   Right now we have STOP_SENDING, but that doesn't influence the
>   sender's state. I don't think undirectional streams make this worse,
>   they just require us to think it through some more. They do simplify
>   the implementation of the closure state machine: in my QUIC-05 code,
>   whenever one side closes I have to have checks to see if I should be
>   transitioning to CLOSED or HALF-CLOSED, etc, which is odd because
>   the directions are basically independent.  It would probably be
>   easier even in QUIC-05 not to reify these states but just to
>   determine the state from the composition of the individual
>   sub-states
> - Unidirectional streams don't need the kind of annoying odd-even
>   mechanics, which was easier to code up (just having to create all
>   the lower-numbered streams of the same parity is kind of a pain).
>   One additional benefit here is that with QUIC-05 there are several
>   messages which involve implicit stream creation (e.g.,
>   STREAM_MAX_DATA, and RST_STREAM) and so you need to check whether
>   the stream is one that should have been created locally or
>   remotely. This just doesn't happen with bidirectional streams; I do
>   implement odd/even mechanics but because the other side has to have
>   its stream ids increment by one, I can make sure that they have the
>   right IDs by construction and just check to see if the stream exists
>   in these cases.  I'd like to see us get rid of odd/even no matter
>   what.
> - Unidirectional streams also helps avoid some of the corner cases around
>   bidirectional streams. Specifically, suppose I am the client and
>   I get MAX_STREAM_DATA as the first frame on stream 2. Am I allowed
>   to just start sending or not? You can sort of get into this situation
>   with unidirectional streams, but because it's explicit, one might
>   hope that the application semantics would require clear specification.
> - As noted above, bidirectional streams are more flexible because they
>   let you have mappings that you can't have with unidirectional
>   streams (unpaired, 1:N).
> Happy to answer more questions if people have them. Otherwise we can
> talk about this in Seattle.
> -Ekr
> [0]
> [1]
> 404898fa2d2f0a9f9bd244d2c945e66ea88502a2/interim-17-10/
> Unidirectional%20Streams%20in%20Minq.pdf
> [2] Thanks to Patrick McManus for suggesting this design.
> [3] In C++, you would have a single function with a default argument of
>     |nullptr| but Go doesn't support that, hence two different arguments.
> [4] For implementation reasons, it's actually using Connection as a mixin,
>     which means it's simultaneously possible to use the unidirectional
>     and bidirectional APIs, but that's going to cause a lot of confusion.
>     A real implementation would probably have to either commit to one
>     or the other or do a real wrapper, so you could only use one set of
>     APIs, at the cost of having to do more forwarded methods.