Subject: [hybi] MUX complications

From: Greg Wilkins <[email-masked]>
Date: Thu, 14 Apr 2011 15:15:58 +1000

All,

I've had a bit of a look at John tamplin's x-google-mux extension and
I have to say that it's a little bit scary at the complexity required
to implement MUX as an extension.  This is a great pity as I think
that with only a few tweaks it would have been much easier to support
in the base protocol and that most opinions I've seen expressed lately
agree that MUX is going to be vital for any widespread deployment and
scaling of websockets.

The problem is that the framing and extension mechanism that we have
in websockets is just not good enough to actually do MUX, so
x-google-mux essentially ignores those mechanism and is implemented as
a new framing layer within the payload  that then carries another
layer of websocket framing.    This is not to criticise the design (or
designers), as I think the current websocket framing is just not good
enough for MUX.

WS provides frames like:

    [ opcode  {} { application payload} ]

which can be fragmented like:

   [ ! opcode   {}  { application } ]   [ ! cont.   {}  { pay } ]   [
cont.  {}  { load } ]

I think we all imagined that when it came to MUX, we'd just be able to
put the channel ID in the ext data like:

  [ opcode   {chan 1} {application payload} ]

and if it was fragmented it would look like:

   [ ! opcode  {chan 1}  { application } ]   [ cont.   {chan 1}  { payload } ]

and if it was interleaved with another channel it would look like:

   [ ! opcode   {chan 1}  { application } ]   [ ! opcode   {chan 2}  {
other } ]   [ cont.   {chan 1}  { payload } ]   [ cont.   {chan 2}  {
data } ]

But the problem with this, is that that interleaved stream of frames
is not a legal sequence of frames because you cannot follow an
non-final-opcode frame with another frame carrying an opcode, nor can
you follow a final continuation frame with another final continuation
frame.

The situation get's worse when you consider that intermediaries can
fragment and aggregate packets, so you might receive a stream like:

   [ ! opcode   {chan 1}  { app } ]  [! cont {}{lication} ]   [ !
opcode   {chan 2}  { other chan 1 payload } ]   [ cont.   {chan 2}  {
data } ]

So frames can arrive without channel IDs and other frames can be
aggregated so that extension data ends up being buried in the payload.

The fragmentation mechanism is basically useless for MUX !

The solution that John is working on is to ignore the websocket frames
and work at a message level, where a WS message will use opcode 0xf
and will carry 1 or more MUX blocks like:

 [ 0xf {} {   (muxCode chanId data)...(muxCode chanId data)  }

If the mux code is 0, then that is a data block and it carries a
normal websocket frame, for example

[ 0xf {} { ( 0 chanId  opcode  {} { application payload}  ) } ]

Now the inner websocket messages may be fragmented so we could see
something like:

[ 0xf {} { ( 0 chanId  !opcode  {} { application}  0 chanId !cont {}
{pay} 0 chanId cont {} {load} ) } ]

or the outher websocket message could be fragmented so we could see
something like:

[!0xf {} { ( 0 chanId  !opcode  {} { applic } ]   [ cont {} {ation}  0
chanId !cont {} {pay} 0 chanId cont {} {load} ) } ]

Note that the extension mechanism is hardly uses, other than the 0xf
opcode - but that is not even needed as you could just as easily have
said that all binary frames are mux frames.

But I think the design of x-google-mux does work, and it may well be
the best that we can do with the current websockets.   But this is a
huge disappointment because:

 1) MUXed data is wrapped in 3 layers of framing, WS, then mux blocks
then WS again.
 2) Neither the fragmentation nor extension data fields are used, and
it was part of there design that they were there for MUX.
 3) There is the possibility that the inner websocket frames are
themselves MUXed and thus could thenselve contain another layer of MUX
blocks and WS framing.  It could be turtles all the way down[1]

It is a huge pity that we could not agree to have at least minimal
support for MUX in the base protocol, as it would not need much to
make it work via intermediaries.  If we just added a channel ID field
to the basic framing, then we could give the intermediaries some rules
about fragmentation/aggregation - copy the channel ID when fragmenting
- don't aggregate different channel IDs.    We need not define how
channels are created, flow control or anything like that, but just a
smear of channel awareness so intermediaries do not make the existing
framing unusable for MUX.

Another alternative is that does not put Channels into the base
protocol, is that we make the ext data a little more visible to the
intermediaries and define rules for how it is fragmented and
aggregated.    It could just be simple rules like: duplicate extension
data into each fragment and never aggregate frames that have different
extension data.

Eitherway, I think the inability of a MUX extension to use the base
frames indicates that we have got something very wrong.  I know there
is a strong desire to just ship it and be done with it, but I really
think we need to realise that we've dropped the ball on this one.  Why
have an extension mechanisms if it is essentially unusable?

regards

PS. again I really don't mean to rain on John Tamplins parade.
x-google-mux is probably about as good as you can do with the current
draft.

[1] http://en.wikipedia.org/wiki/Turtles_all_the_way_down

---

From: Andy Green <[email-masked]>
Date: Thu, 14 Apr 2011 08:12:40 +0100

On 04/14/2011 06:15 AM, Somebody in the thread at some point said:

Hi -

> to implement MUX as an extension.  This is a great pity as I think

It is scary, but actually more than halfway through the implementation 
most of the issues are coming from having to refactor the existing code 
somewhat to match the needs of it.  It is fitting well into the 
extension arrangements in libwebsocket, ie, all the mux code except 
generic callbacks is in one extension source file.  Various other things 
needed breaking in half for re-use and new states adding, etc.

> in the base protocol and that most opinions I've seen expressed lately

I am not sure about that and I think we have to take a lot of care 
assuming we saw all the subtleties.

> [ 0xf {} { ( 0 chanId  opcode  {} { application payload}  ) } ]

Yeah notice that the mux block part does not contain a "mux block 
length".  The characteristic of x-google-mux is that the mux block 
length is implied by the content and must be parsed out.  This saves 
bytes on the wire, which matters, but means there is no casual parsing 
of mux content possible.  (And the payload content of the muxed block 
may itself represent recursively muxed content, so there is another mux 
block header, something implied only by the state history of the child 
channels.

It was surprising but thinking about it, the consumer of this 
recursively muxed stream MUST already hold matching structure and state. 
  There's no point adding bytes to the stream to tag it, you would end 
up being able to parse it but not knowing how to use it.

> chanId !cont {} {pay} 0 chanId cont {} {load} ) } ]

What's the problem there?

> said that all binary frames are mux frames.

Well he has control frames too that manage quota and adding and dropping 
subchannels, they happen under opcode 0xf as well.

>   1) MUXed data is wrapped in 3 layers of framing, WS, then mux blocks

Ha no that's the simple case -->

> blocks and WS framing.  It could be turtles all the way down[1]

Right.  And as I say above, you are required to parse that recursively 
to even understand where the next mux block starts as it stands.  It is 
reasonable inside direct endpoint - endpoint context because you are 
receiving it in order to parcel it out, but it makes intermediaries have 
to do all that work too.

> make it work via intermediaries.  If we just added a channel ID field

Sorry why can't an intermediary use this mux scheme?  It's not exactly 
trivial but it is doable.

> have an extension mechanisms if it is essentially unusable?

No I think whatever the mux extension looked like, it would always be an 
"uber-framing" one way or the other.

You don't mention the quota management, but actually that's another 
brain-boggler.  Only after trying to think of alternatives for a while 
did I realize it's probably a reasonable way (although the coding could 
be improved to use knowledge on both sides about lengths that had been 
sent in the past to basically signal an ACK to renew that much quota 
just using a few bits riding shotgun on other traffic TCP/IP style).

-Andy

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 14 Apr 2011 19:15:53 +1000

> I am not sure about that and I think we have to take a lot of care assuming
> we saw all the subtleties.

I'm not saying that a few tweaks is all that is required to implement MUX.
I'm saying that a few tweaks might be sufficient to prevent the
current spec creating intermediaries that will break MUX that uses ws
framing.

> Yeah notice that the mux block part does not contain a "mux block length".
>  The characteristic of x-google-mux is that the mux block length is implied
> by the content and must be parsed out.

Yes - which means that the mux block parser will need to itself be a
WS parser.  I'm guessing that the simplest solution will be to wrap
them all up in a single parser that works for WS or muxBlocks
containing WS frames.

> What's the problem there?

Nothing - I'm explaining how it works.

> subchannels, they happen under opcode 0xf as well.

But those could also be sent in normal binary frames.   In fact there
is very little in this that could not be done as a sub-protocol rather
than an extension (except that sub protocols would go to the
javascript application).

> Right.  And as I say above, you are required to parse that recursively to
> even understand where the next mux block starts as it stands.

it is cool - but scary.

> trivial but it is doable.

Yes intermediaries will be able to implement MUX themselves.
But there will also be ones that do not, and they are the ones that
are forcing this recursive MUX.

> "uber-framing" one way or the other.

Why?   The simple rules I described about aggregation and
fragmentation should be sufficient to make normal WS frames usable in
a MUX extension.  Sure there are lots of complex problems to solve,
such as channel life cycles and flow control - but at least the basic
framing need not be reinvented.

> brain-boggler.  Only after trying to think of alternatives for a while did I
> realize it's probably a reasonable way (although the coding could be
> improved to use knowledge on both sides about lengths that had been sent in
> the past to basically signal an ACK to renew that much quota just using a
> few bits riding shotgun on other traffic TCP/IP style).

Sure - I think this stuff is good.  But I'm not advocating having
anything like that in the base protocol.  I'd like to see just enough
to make the base frames usable and avoid the need for MUX blocks and
nested framing.

cheers

---

From: Andy Green <[email-masked]>
Date: Thu, 14 Apr 2011 11:20:16 +0100

On 04/14/2011 10:15 AM, Somebody in the thread at some point said:
> On 14 April 2011 17:12, Andy Green<[email-masked]>  wrote:

I think the idea is that you negotiated the mux extension on a 
particular link so you can see funny non-base-protocol stuff coming in 
there.  That is in fact how extensions are meant to work, even if you 
look at the extension data area you can't interpret it outside of the 
context of which extensions were negotiated for that specific link.

> them all up in a single parser that works for WS or muxBlocks

I don't think it matters, how it ends up either way is that the mux spec 
drives the architecture of the base code in a way that you are unlikely 
to predict from just reading the base spec.  So it won't fly to look at 
mux extension just as a simple add-on, stuff like recursion has deep 
ramifications into how the parser works, how and when per-connection mux 
extension data is allocated, etc etc.

> than an extension (except that sub protocols would go to the

This is the "uber framing" question again... if you can mux mux'd 
channels, then you need an OOB context to issue the control messages 
into, if it's all flat with mux management messages just part of the 
normal stream it can't do recursive muxing.

>> even understand where the next mux block starts as it stands.

It's mostly scary because it messes up assumptions we might be holding 
on to about how our base implementation should be architected.  For 
example I was looking at a trivial implementation in Javascript IIRC the 
other week, the author of that will have his head explode when 
confronted with the mux spec.  That guy will probably react to this by 
calling it "too complicated" etc.  He's right in as far as it's not a 
weekend project to do it like maybe the simplest base spec 
implementation is.

> are forcing this recursive MUX.

Once the code is written for mux parsing at all, it can be shared for 
intermediary action easily enough I think.

> framing need not be reinvented.

The mux management and channel index content is for is not part of the 
muxed content, so it's always "out of band".  If there is no OOB 
concept, you can't mux a mux'd channel.

-Andy

---

From: John Tamplin <[email-masked]>
Date: Thu, 14 Apr 2011 09:42:51 -0400

> designers), as I think the current websocket framing is just not good

I am not sure why you say it ignores the framing/extension mechanism -- we
have three vectors of extension in the WebSocket framing: opcodes, reserved
bits, and an extension area, and it uses an extension opcode.  It reuses the
base framing rather than create its own framing for inner blocks.

I think what you fundamentally don't like is that intermediaries have to
understand the extensions in order to do something with a message, which I
have argued is a requirement since the beginning, and it is still in the
spec that an intermediary may not fragment or otherwise mutate a message
which contains extensions it doesn't understand.  So, I think it actually
would be possible to define a channel ID in the extension data and require
that fragmentation of a MUXd frame duplicates the channel ID.  However, as
you point out that doesn't allow you to interleave frames from different
channels, unless you say the fragment state is maintained separately per
channel, and I think baking that into the base protocol is definitely going
too far.  Also, you would still need to deal with control messages for
adding/dropping individual channels and for flow control, and it seems
better to aggregate them into the frame containing MUX'd data where
possible.

If you don't think this is a reasonable use of an extension opcode, then
what exactly would you think is a good use for it?

> said that all binary frames are mux frames.

Not if you wanted to be able to send binary frames, or other
as-yet-undefined frame types.

>  1) MUXed data is wrapped in 3 layers of framing, WS, then mux blocks

There is no wrapping of MUX data blocks -- they are just a prefix to a frame
on a logical channel.  It seems preferable to reuse the logical channel
framing rather than to invent a new framing and have to talk about how to
carry as-yet-unspecified extension data from the logical channel frame in
this new framing.

> it was part of there design that they were there for MUX.

If you look back at the original examples I gave when we were agreeing on
the framing, something very similar to the x-google-mux proposal was given
as an example of how it could be implemented using the proposed framing, so
I don't see why this proposal is apparently a surprise to you.  The
fragmentation is indeed needed for MUX, and if the shared channel is busy
the MUX is going to be fragmenting the logical channel messages, and the
proposal makes use of that by in fact reusing the exact framing for the
logical channels.  Also, the combined MUX message itself could be fragmented
by a later intermediary, since as any other WS frame the sender doesn't know
if some intermediary needs to fragment it further.

> framing unusable for MUX.

As mentioned earlier, I don't think you can solve the problem by just
defining a few unused fields in the base protocol -- I think you would
essentially have to define much of the MUX behavior in the base protocol.
 The above would not be sufficient, as you would also have to require that
intermediaries keep track of fragmentation state on a per-channel basis.

> data into each fragment and never aggregate frames that have different

What is "different" extension data?  Remember that intermediaries cannot
even distinguish what is extension data from application data if they don't
understand the negotiated extensions.  To do otherwise would require some
tagging of the extension data (including defining it as per-message or
per-fragment, where obviously per-fragment data can't be fragmented), which
would be expensive and restrictive for future uses of extension data.

-- 
John A. Tamplin
Software Engineer (GWT), Google

---

From: Greg Wilkins <[email-masked]>
Date: Fri, 15 Apr 2011 10:43:00 +1000

John

I didn't intend for my message to be a critique of the x-google-mux
design.   I think it is a good design given the base protocol.

On 14 April 2011 23:42, John Tamplin <[email-masked]> wrote:
> bits, and an extension area, and it uses an extension opcode.

I'm not saying that you have used the ext opcode badly, only that your
design could have been made to work without any of the extension
vectors, so they are not an enabling feature of the base protocol. But
I do like the use of the 0xF opcode instead of the binary frame, as it
allows channel 1 to be sent normally. So that is a good use of the ext
opcode - just not a necessary one.

> understand the extensions in order to do something with a message.

Partially yes.   But my main concern is the nested/recursive framing
of WS inside WS.

I don't think it makes good use of the framing/ext mechanisms we put
into the base protocol, which I think indicates that those features
are not usable enough and should either be fixed or scrapped.

> which I
> which contains extensions it doesn't understand.

Ah - so that is something I missed.     I'm OK with that restriction
as I think any intermediary that is changing fragmentation is probably
an intermediary that is doing aggregation anyway.  But as you say
below....

> So, I think it actually
> channel,

Exactly.   One of the motivations for fragmentation was to support
mux, but without interleaving we find that it can't support mux, so we
must have framing inside framing.

> I think baking that into the base protocol is definitely going too far.

Why?  We don't need to require that base protocol can do MUX, only
that a MUX extension can change some of the framing semantics.

This could be as simple as saying that apparently illegal sequences of
fragments are allowed if there are extensions that can sort them out.
This would allow fragments to be interleaved and channel IDs to be in
the extension data and used by the endpoints to do the aggregation.
Intermediaries would not be allowed to aggregate because they don't
know the extension.

Tools that don't know about the extension might be a little confused -
but they too should not aggregate if they don't know the extensions.

> what exactly would you think is a good use for it?

It is a good use - just not a necessary one for the extension to work.
 ie having extensible opcode was not a necessary condition for having
such an extension.

> carry as-yet-unspecified extension data from the logical channel frame in

I consider a prefix to be wrapping in another layer of framing.
But I agree that reusing the WS framing for the channel is a
reasonable thing to do if you can't use the base framing for that
purpose.

> if some intermediary needs to fragment it further.

Sorry but I missed that in the volume of email here.   I had always
assumed that the extension data area was going to be used for channel
IDs and I remember plenty of examples suggesting that. So sorry I
didn't pay more attention earlier.

> intermediaries keep track of fragmentation state on a per-channel basis.

But as you have pointed out, we already do not allow intermediaries to
fragment/aggregate if they don't understand the extensions.  So we are
mostly there.
All we need now is to allow interleaving of fragments, and I think
that can be done without any binary change.  We only need to say that
it is not illegal to send a sequence of fragments that can only be
aggregated by use of an extension.   Intermediaries that don't
understand the extension can still forward the fragments unchanged.

I'm not saying that we should have MUX in the base framing.  I just
think that we need the base framing to be usable for MUX and thus to
remove the need for nested framing.

cheers

---

From: Andy Green <[email-masked]>
Date: Fri, 15 Apr 2011 08:17:33 +0100

> opcode - just not a necessary one.

Notice though that you can only play the ch1 = base protocol game when 
there are no other subchannels up.

> reasonable thing to do if you can't use the base framing for that

Right, it's that which creates the OOB framing.  You can call it a 
prefix or whatever since the bytes go out in an ordered stream but it's 
acting as a wrapper.

> remove the need for nested framing.

Well it's as simple as using one of the reserved bits in the first frame 
byte of the base framing to say it's a mux block header.  But I'm not 
sure what it actually buys us.

-Andy

---

From: Greg Wilkins <[email-masked]>
Date: Fri, 15 Apr 2011 18:33:04 +1000

On 15 April 2011 17:17, Andy Green <[email-masked]> wrote:
> byte of the base framing to say it's a mux block header.  But I'm not sure
> what it actually buys us.

I think it buys us simplicity, less buffering, less framing, no
masking already masked content etc.

If we can reuse the base framing, then for each channel we need to
keep the state:
 + opcode
 + buffer of payload received so far
once the last frame comes in, we pass the buffered payload to the
application, just as we do for the non mux case.

With nested framing, then for each channel we need to keep the state:
 + buffer of payload received so far
once the last frame comes in, we have to parse the buffer to a
websocket protocol stack that itself may be muxed and will have it own
set of channels with payloads that need to be buffered etc.

cheers

---

From: Andy Green <[email-masked]>
Date: Fri, 15 Apr 2011 10:19:52 +0100

On 04/15/2011 09:33 AM, Somebody in the thread at some point said:
> On 15 April 2011 17:17, Andy Green<[email-masked]>  wrote:

'Simplicity' of what?  It certainly doesn't suddenly make all the 
brainache go away about mux.  I guess you could say 'simpler, unified 
frame coding'.

It's neutral for buffering as discussed below.

Far from 'less framing' on the wire it will demand more framing bytes or 
reducing max mux subchannels from 8192 to 127 since current 2-byte mux 
block header will have to comply with explicitly setting the base spec 
reserved bits in the first and second byte to achieve compatibility. 
Not saying that's not worth doing just let's understand we are not 
getting 'less framing' by doing it we're adding a little bloat.

> masking already masked content etc.

The existing mux spec already 'defines' that only the outer transport 
should be masked, although that seems crappy considering one guy's outer 
transport may become the next guy's inner muxed channel it should work I 
guess.

> application, just as we do for the non mux case.

You have to keep that state anyway... sorry if I am missing your point.

> set of channels with payloads that need to be buffered etc.

"once the last frame comes in, we have to parse the buffer to a 
websocket protocol stack"  -- why?  You can parse the thing packet by 
packet as it comes in, issuing bytes to your state machine.  Then there 
is no global buffering at all and the parsing is faster since it's not 
all done at the end.  What is it you think you have to wait for at the 
end before you can begin to parse?

-Andy

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 18 Apr 2011 11:52:58 +1000

On 15 April 2011 19:19, Andy Green <[email-masked]> wrote:
> 'Simplicity' of what?

Instead of sending something like

  [!0xf {} { ( 0 chanId  !opcode  {} { applic } ]   [ cont {} {ation}
0 chanId !cont {} {pay} 0 chanId cont {} {load} ) } ]

we could send

 [!opcode {chanId} {application } ]   [ !cont {chanId} {pay} ]   [
cont {chanId} {load} ]

>  It certainly doesn't suddenly make all the brainache
> go away about mux.  I guess you could say 'simpler, unified frame coding'.

My making the nested framing go away, it means our aching brains can
focus more on the difficulties of MUX (flow control etc) rather than
nested/recursive parsers and state machines.

> It's neutral for buffering as discussed below.

I don't think so.  Typically a parser is going to have input buffers
and output buffers - parse raw on the wire bytes to produce parsed
bytes.   If you have to string 3 (or recursively more) parsers
together, then I can see many intermediary buffers being used.
With a lot of smarts, you can probably flatten out the
recursive/chained parsers into a single parser - but that is a big
task that you need to start by throwing away your existing WS parser
and starting again.

> reducing max mux subchannels from 8192 to 127 since current 2-byte mux block
> header will have to comply with explicitly setting the base spec reserved
> bits in the first and second byte to achieve compatibility. Not saying
> that's not worth doing just let's understand we are not getting 'less
> framing' by doing it we're adding a little bloat.

I don't understand this point.   I'm not suggesting changing the
chanId encoding that John has proposed (which is variable length).
I'm just saying put it in the extension data rather than in a MUX
block frame/prefix.

> The existing mux spec already 'defines' that only the outer transport should
> be masked, although that seems crappy considering one guy's outer transport
> may become the next guy's inner muxed channel it should work I guess.

With my proposal a MUXing intermediary need no unmux or remux.  We
only need to pad the mux ext data to 4 bytes and then the intermediary
can keep the same mask key, add the masked mux channel Id, and then
reused the payload in its already masked form.

> You have to keep that state anyway... sorry if I am missing your point.

Yes we keep that state anyway (I listed it both times).     The
difference is that if we reuse the base framing then MUX becomes a
transformation from wire data to application data.   With the nested
framing MUX is a transformation from wire data to wire data and needs
recursive (or smart iterative) handling.

> "once the last frame comes in, we have to parse the buffer to a websocket
> protocol stack"  -- why?  You can parse the thing packet by packet as it
> comes in, issuing bytes to your state machine.  Then there is no global
> buffering at all and the parsing is faster since it's not all done at the
> end.  What is it you think you have to wait for at the end before you can
> begin to parse?

Yep I think it can be done this way.  But it will pretty smart
implementation of WS parsers/generators.

If you receive something like:

  [!0xf {} { ( 0 chanId  !0xf  {} { 0 chanId !0xf  {} {0}  } } ]

then you parser is going to have to remember that it is 3 levels of
mux down with the meta data for the 3 layer not yet received, and that
there are two channel Id's in play, with the first channel Id really
acting as a name space for the second channel Id which might not be
unique for the connection.

It is doable - but it's not simple.

We already have the restriction that an intermediary can't fragment or
aggregate if it does not understand all the extensions.   So for my
proposal, all we need to add is that we can send arbitrary sequences
of interleaved fragments that an extension will well order.

cheers