Re: [hybi] Flow control quota

[Jamie Lokier <[e-mail]>]

Hi everyone,

I haven't been following the hybi list for a while (it was too
depressing/exhausting), but I'm really pleased to see deadlock-free,
starvation-free mux is being taken more seriously now.  I guess SPDY's
helped with that.

The problem being described in this thread occurs because the layers
aren't really being kept separate.

If they are properly separated, everything works, and it's easier to
implement and even a bit faster on the network.

I see a lot of confusion about the role and purpose of "fragments".
Particularly the idea that where something produces fragments, those
must literally correspond with the wire protocol, despite having
another transformative layer before the wire.

Arman Djusupov wrote:
> According to the WebSocket specification extensions are layered and should
> be applied in a specific order. In this particular case the mux
> specification provides two ways of applying the per frame compression
> extension: compression can be applied either before or after the mux
> extension. In the first case the frame being multiplexed is already
> compressed and should not be fragmented.
                 ^^^^^^^^^^^^^^^^^^^^^^^^

Mux should be able to further fragment - in a way that compression does not see.

> This allows intermediaries to de-multiplex frames without
> decompressing them. In the second case the mux frame is compressed
> along with the mux header, so it cannot be de-multiplexed unless it
> is first decompressed. Supporting both options is beneficial.
> 
> In any case the problem preventing  unfragmentable frames from being relayed
> over flow-controlled logical connections should be resolved. The per frame
> compression is not the only case when it might be impossible to fragment a
> frame. A mux intermediary should either be able to control the size of the
> frame that the sending side produces or should be able to fragment them.
                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Imo, that's the only sensible answer.

Anything else leads to a spiral of hacks - see this thread for examples!

Basically the output of compression is a stream of "unfragmentable"
things.  But several things, mux being one, need ability to break up
the data stream where it's useful - which is the point of fragments.

Deadlock-free mux pretty much _requires_ per-channel flow control and
fragmentation at the mux.  And it should be visible only to the mux.

Compression (and other layers) need to be _strictly_ separate.  But in
these discussions they've been combined in a fuzzy way, which makes
everything complicated.

I guess it was a misguided attempt to keep the wire concepts simple
(fit everything into "frames" and "fragments"), which actually makes
it more complicated.

It doesn't really matter whether compression is layered above or
below, both work fine, as long as it's a separate layer.

If you treat mux like this:

    1. Zero or more "stream of fragments" (of next layer up) in.
    2. One "stream of fragments" (of mux protocol) out.

and demux like this:

    1. One "stream of fragments" (of mux protocol) in.
    2. Zero or more "stream of fragments" (of next layer up) down.

Where "mux protocol" means it's encapsulating channel numbers, flow
control and fragmentation, everything behaves nicely.

There is no need of oddities like negative flow control tokens,
wasteful round trips, no deadlock, starvation, buffer overflow at
intermediaries due to large fragments or bandwidth limitations.

It just works(tm).  (Well you do have to implement a good mux - but
that's all, it's confined to the mux implementation.)

For compression above the mux, this means:

    - Compression layer outputs a stream of compressed fragments.
    - Mux takes it in, and produces its _own_ stream of mux fragments.
    - Demux takes that, and recombines to make the original fragments.
    - Decompression gets what it needed.

Compression below the mux is similar, but the other way.  See?

In many cases the fragement boundaries of the two layers will
coincide, but it shouldn't be assumed or restricted to that.  If there
is a desire to encode _that case_ efficiently, that's fine, as long as
it's just an encoding.

It breaks the whole point of flow-control and deadlock-avoidance if
the layers have to maintain the same boundaries - as this thread
demonstrates.  One large compressed frame/fragement, and all other
channels are starved - nobody will use mux if it's that unreliable!
Certainly not cooperatively/opportunistically.

Or, if you limit the compression size to the whole path's capacity -
that's also a waste (of compression opportunity).  In that case, the
attempt to save a few bytes in the header encoding is
counterproductive (but you can still save those bytes, just make sure
it's purely a syntax optimisation.).

Oh, one other thing: It's best if compression is free to make the best
compression decisions without blocking _other_ things that need
fragmentation below - namely control frames, that must be sendable,
and maybe prioritisable.

As a practical matter, I'm thinking it makes sense for the compression
layer to see things this way:

   1. Receive stream of application frames (WS messages).
         -> Compressor ->
   2. Stream of "frames" (not fragments) out, meaning "non-fragmentable".
         -> Decompresor ->
   3. Emit stream of application frames (WS messages)

The "frames" in 2 above are compression-protocol messages, and do not
have to correspond with application messages.  They are actually the
output that current compression proposals would call "fragments".

The only difference, really, is syntax in the pipeline when passed to
the layer below.  So actually this is a very small change.  The
compression method, decisions it makes, etc. are unchanged.

My summary:

Keep the mux and other layers separate, not leaky, and all the muxy
things (flow control etc.) can be implemented in the mux layer alone.

Everything will work, and the implementation will be simpler as well
(more modular, less dependencies).

When a layer (such as compression) outputs a stream of things with
essential boundaries, treat it as stream of frames, don't conflate it
with "fragments" at the wire level - even if it did involve splitting
the WS application's original messages.  Keep the relationship between
these frames and application (or higher layer) frames internal to the
compression layer and protocol (same for other layers).

It is much better to maintain clear semantics: frame boundaries are
immutable because the upper layer requires them, fragment boundaries
are _always_ allowed to be split and merged for optimal transport
decisions, and they only correspond _literally_ to the wire protocol
for the lowest layer in the stack.

As the wire protocol is now defined, it doesn't match up well with the
above semantics, but it's a syntax (header encoding) issue only.

It will even go faster on the network due to freeing up each component
to do the best for its part.  Think about the different combinations
of layers when several fragments/frames are in flight, and also
multi-hop paths.  They all benefit.

All the best,
-- Jamie