Subject: Re: [hybi] Flow control quota

From: Martin Sustrik <[email-masked]>
Date: Fri, 01 Jun 2012 10:43:19 +0200

On 31/05/12 13:01, Arman Djusupov wrote:
> When the per-frame compression extension is being used on a logical channel,
> it is impossible to create a frame of exactly the desired size. A few bytes
> of quota will always be unutilized unless some padding is used. The mux
> specification prohibits sending frames bigger than the available quota. When
> per-frame compression is applied on the payload before mux, this payload
> cannot be fragmented any more. Even if we make compression extension mux
> aware, it cannot produce a 1 byte compressed frame, it can only flag a frame
> as uncompressed and simply send 1 byte. In general, sending 1 byte in a
> separate frame is not desirable.

That seems to suggest there's some kind of mis-layering happening here. 
Frames are used for flow control. Does it make sense to use them for 
compression as well? Shouldn't the compression rather happen on top of 
mutliplexing layer?

The situation is similar to compressing the payload in TCP packets. It 
is feasible, but in corner cases it can clash with MTU limits, cause 
re-fragmentation etc. The clean solution would be to layer compression 
on top of TCP layer.

Martin

---

From: Takeshi Yoshino <[email-masked]>
Date: Fri, 1 Jun 2012 20:04:21 +0900

Hi Arman,

Thanks for point out these risks.

OK, we should note that the quota need to be replenished to some quantity
without waiting for full consumption, maybe with the example of compression
extension you mentioned.

On Thu, May 31, 2012 at 8:01 PM, Arman Djusupov <[email-masked]> wrote:

> Extensions that set RSV bits prohibit frame fragmentation. This causes a
> general incompatibility issue with mux FC when an extension is applied
> before the mux. We need to consider whether there is a solution to this.
>

Yes, the multiplexing code need to feed back to extensions behind it to
control fragment size.

Limiting quota to very small value such as 1 byte persistently is not
practical. The bandwidth will be quota / RTT. It's really slow. I think
that warning the risk of dead lock is enough.

---

From: Takeshi Yoshino <[email-masked]>
Date: Fri, 1 Jun 2012 21:33:11 +0900

On Fri, Jun 1, 2012 at 5:43 PM, Martin Sustrik <[email-masked]> wrote:

> The situation is similar to compressing the payload in TCP packets. It is
> feasible, but in corner cases it can clash with MTU limits, cause
> re-fragmentation etc. The clean solution would be to layer compression on
> top of TCP layer.

Mux want to control fragmentation while per-frame compression locks down
fragmentation. Yes, it's not healthy to use of per-frame compression before
mux.

Shall we discourage this layering (preframe-compress then mux)?

---

From: "Arman Djusupov" <[email-masked]>
Date: Fri, 1 Jun 2012 17:15:19 +0300

Unfortunately making extensions mutually aware of each other at the
implementation level does not prevent problems from being encountered by a
mux intermediary that receives a frame with an RSV bit set. An intermediary
is not permitted to fragment a frame with an RSV bit set especially when the
extension is unknown. If such a frame is larger than the available quota
then the intermediary would have to wait until the quota becomes larger than
the frame size before it can send it. This will result in the frame never
being sent if its size is larger than the flow control window.

A practical example of this problem is that a mux intermediary might end up
being unable to forward compressed frames larger than the flow control
window, unless it first decompresses them and refragments them.

I am trying to figure out a general purpose solution that would allow us to
deal with non-fragmentable frames, even if the extension that is applied to
them is unknown. So far I have two ideas:

1.

Allow the sender to send a frame with an RSV bit set even if it is bigger
that the available quota. In such a case the quota becomes negative and from
that moment on the sending side MUST wait until the quota becomes positive
before sending the subsequent frame. This way the flow control would work
and the sender would be able to send a frame that is larger than the
available quota but cannot be fragmented.

Flow control is not intended to limit the maximum frame size, but rather to
prevent a logical channel from exclusively using a physical connection. This
solution would satisfy this requirement. A logical channel would wait as
long as necessary until the quota becomes positive. This would let other
channels use the physical connection. However, this solution would not
prevent a sender from forcing the receiver to buffer an amount of bytes that
is a larger than the amount it had agreed to buffer. But the amount of extra
buffering required would not exceed the size of a single frame so a mux
intermediary would at least be able to forward frames of reasonable size. 

2.

An alternative solution is to introduce a WebSocket fragmentation extension.
Using this extension, multiplexing intermediaries would advertise the
maximum frame size limit for non-mux clients. Non-mux clients that want
their connections to be multiplexed by an intermediary would have to stick
to the frame size limits required by that intermediary. By supporting this
extension WebSocket client/browser vendors will be able to make their
clients mux-intermediary-friendly. This would help not only in
non-mux-client-to-mux-intermediary scenarios (and flow control in general)
but would also permit us to advertise a frame size limit in any scenario
where such limits are present. This was discussed by the WG but didn't made
it into RFC 6455, the idea at that time was that it could go in a separate
extension. So currently we have section 10.4 that requires implementations
to protect themselves against exceeding frame size limits. A fragmentation
extension would enable us to advertise these limits.

10.4.  Implementation-Specific Limits

   Implementations that have implementation- and/or platform-specific

   limitations regarding the frame size or total message size after

   reassembly from multiple frames MUST protect themselves against

   exceeding those limits.  (For example, a malicious endpoint can try

   to exhaust its peer's memory or mount a denial-of-service attack by

   sending either a single big frame (e.g., of size 2**60) or by sending

   a long stream of small frames that are a part of a fragmented

   message.)  Such an implementation SHOULD impose a limit on frame

   sizes and the total message size after reassembly from multiple

   frames.

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Friday, June 01, 2012 3:33 PM
To: Martin Sustrik
Cc: Arman Djusupov; [email-masked]
Subject: Re: [hybi] Flow control quota

---

From: Martin Sustrik <[email-masked]>
Date: Mon, 04 Jun 2012 14:47:39 +0200

Hi Arman,

I am not following the hybi mailing list thoroughly, so I am not 
familiar with the technical details... However, it seems that the 
problem here is that it's possible to use any combination of extensions.

This pattern doesn't work well. The problem is that with the growing 
number of extensions the number of possible combinations and 
(mis)interactions between them is growing exponentially, so it's 
basically impossible to deliver a fully functional stack.

The approach that standard Internet protocols take is separating the 
functionality into layers where each layer can be filled by only a 
single protocol at a time. E.g. if you are using TCP at L4 for a 
particular connection you can't use SCTP at the same time.

I don't understand the details of WS, so I don't want to make any strong 
proposals, but maybe separating the extensions into several well-defined 
layers where each layer can be occupied only by a single extension 
instance may help.

Martin

On 01/06/12 16:15, Arman Djusupov wrote:
> implementation level does not prevent problems from being encountered by
> a mux intermediary that receives a frame with an RSV bit set. An
> intermediary is not permitted to fragment a frame with an RSV bit set
> especially when the extension is unknown. If such a frame is larger than
> the available quota then the intermediary would have to wait until the
> quota becomes larger than the frame size before it can send it. This
> will result in the frame never being sent if its size is larger than the
> flow control window.
>
> A practical example of this problem is that a mux intermediary might end
> up being unable to forward compressed frames larger than the flow
> control window, unless it first decompresses them and refragments them.
>
> I am trying to figure out a general purpose solution that would allow us
> to deal with non-fragmentable frames, even if the extension that is
> applied to them is unknown. So far I have two ideas:
>
> 1.
>
> Allow the sender to send a frame with an RSV bit set even if it is
> bigger that the available quota. In such a case the quota becomes
> negative and from that moment on the sending side MUST wait until the
> quota becomes positive before sending the subsequent frame. This way the
> flow control would work and the sender would be able to send a frame
> that is larger than the available quota but cannot be fragmented.
>
> Flow control is not intended to limit the maximum frame size, but rather
> to prevent a logical channel from exclusively using a physical
> connection. This solution would satisfy this requirement. A logical
> channel would wait as long as necessary until the quota becomes
> positive. This would let other channels use the physical connection.
> However, this solution would not prevent a sender from forcing the
> receiver to buffer an amount of bytes that is a larger than the amount
> it had agreed to buffer. But the amount of extra buffering required
> would not exceed the size of a single frame so a mux intermediary would
> at least be able to forward frames of reasonable size.
>
> 2.
>
> An alternative solution is to introduce a WebSocket fragmentation
> extension. Using this extension, multiplexing intermediaries would
> advertise the maximum frame size limit for non-mux clients. Non-mux
> clients that want their connections to be multiplexed by an intermediary
> would have to stick to the frame size limits required by that
> intermediary. By supporting this extension WebSocket client/browser
> vendors will be able to make their clients mux-intermediary-friendly.
> This would help not only in non-mux-client-to-mux-intermediary scenarios
> (and flow control in general) but would also permit us to advertise a
> frame size limit in any scenario where such limits are present. This was
> discussed by the WG but didn’t made it into RFC 6455, the idea at that
> time was that it could go in a separate extension. So currently we have
> section 10.4 that requires implementations to protect themselves against
> exceeding frame size limits. A fragmentation extension would enable us
> to advertise these limits.
>
> *From:*Takeshi Yoshino [mailto:[email-masked]]
> *Sent:* Friday, June 01, 2012 3:33 PM
> *To:* Martin Sustrik
> *Cc:* Arman Djusupov; [email-masked]
> *Subject:* Re: [hybi] Flow control quota
>
> On Fri, Jun 1, 2012 at 5:43 PM, Martin Sustrik <[email-masked]
> <mailto:[email-masked]>> wrote:
>
> fragmentation. Yes, it's not healthy to use of per-frame compression
> before mux.
>

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 4 Jun 2012 15:54:44 +0200

Arman,

I think a solution could be to allow the sender to send a control
message, "No remaining Quota" meaning that the sender would send more
data if it had more quota.

This control method could be used in this case where there are not
sufficient window bytes available so as to allow a minimal frame to be
sent.

This control frame is also useful even if the quota is completely
consumed because if you follow the flow control discussion over on the
SPDY lists, you will see that fixed quotas will restrict the usage of
available bandwidth.  Thus I suspect that we will need to go to
dynamic window sizes.   If the sender can tell the receiver that it
has consumed it's window (and no the receiver can't tell that itself
because of network latency), then that can inform any receiver
decisions to increase the window size.

cheers

---

From: "Arman Djusupov" <[email-masked]>
Date: Mon, 4 Jun 2012 17:58:00 +0300

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. 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.

Yes, the number of extensions may grow and some of them might be mutually
exclusive, that's why WebSocket supports negotiation of the extensions stack
so that each side can validate whether it can apply the requested set of
extensions in the given order. But I firmly believe that mux and per frame
compression are not mutually exclusive extensions.

With best regards,
Arman

-----Original Message-----
From: Martin Sustrik [mailto:[email-masked]] 
Sent: Monday, June 04, 2012 3:48 PM
To: Arman Djusupov
Cc: 'Takeshi Yoshino'; [email-masked]
Subject: Re: [hybi] Flow control quota

Hi Arman,

I am not following the hybi mailing list thoroughly, so I am not familiar
with the technical details... However, it seems that the problem here is
that it's possible to use any combination of extensions.

This pattern doesn't work well. The problem is that with the growing number
of extensions the number of possible combinations and (mis)interactions
between them is growing exponentially, so it's basically impossible to
deliver a fully functional stack.

The approach that standard Internet protocols take is separating the
functionality into layers where each layer can be filled by only a single
protocol at a time. E.g. if you are using TCP at L4 for a particular
connection you can't use SCTP at the same time.

I don't understand the details of WS, so I don't want to make any strong
proposals, but maybe separating the extensions into several well-defined
layers where each layer can be occupied only by a single extension instance
may help.

Martin

On 01/06/12 16:15, Arman Djusupov wrote:
> implementation level does not prevent problems from being encountered 
> by a mux intermediary that receives a frame with an RSV bit set. An 
> especially when the extension is unknown. If such a frame is larger 
> than the available quota then the intermediary would have to wait 
> until the quota becomes larger than the frame size before it can send 
> it. This will result in the frame never being sent if its size is 
> larger than the flow control window.
>
> A practical example of this problem is that a mux intermediary might 
> end up being unable to forward compressed frames larger than the flow 
> I am trying to figure out a general purpose solution that would allow 
> us to deal with non-fragmentable frames, even if the extension that is 
> quota becomes positive before sending the subsequent frame. This way 
> the flow control would work and the sender would be able to send a 
> frame that is larger than the available quota but cannot be fragmented.
>
> Flow control is not intended to limit the maximum frame size, but 
> rather to prevent a logical channel from exclusively using a physical 
> would not exceed the size of a single frame so a mux intermediary 
> would at least be able to forward frames of reasonable size.
>
> 2.
>
> clients that want their connections to be multiplexed by an 
> intermediary would have to stick to the frame size limits required by 
> that intermediary. By supporting this extension WebSocket 
> client/browser vendors will be able to make their clients
mux-intermediary-friendly.
> This would help not only in non-mux-client-to-mux-intermediary 
> scenarios (and flow control in general) but would also permit us to 
> advertise a frame size limit in any scenario where such limits are 
> present. This was discussed by the WG but didn't made it into RFC 
> 6455, the idea at that time was that it could go in a separate 
> extension. So currently we have section 10.4 that requires 
> implementations to protect themselves against exceeding frame size 
> limits. A fragmentation extension would enable us to advertise these
limits.
> Mux want to control fragmentation while per-frame compression locks 
> down fragmentation. Yes, it's not healthy to use of per-frame 
> compression before mux.
>

---

From: "Arman Djusupov" <[email-masked]>
Date: Mon, 4 Jun 2012 18:53:44 +0300

Sending a control message requesting flow control quota would be too slow.
It would make the sending side wait for a full RT before it can send the
frame. Sticking to a frame size below the flow control window is a simpler
solution. If both sides would use a maximum frame size that is smaller than
the flow control window, then the receiving side would send a flow control
quota every time the estimated quota on the sending side drops below the
maximum frame size. This should eliminate the risk of a deadlock.

Another alternative I have mentioned in the past is to let the sender send a
frame over the quota capacity, if the frame is larger than the quota. Then
the sender would have to wait for the quota to be fully replenished before
it can send more frames. This may result in a large frame that exceeds the
available quota, but this situation would either be overcomeable or the
receiver would have to drop the logical channel. According to the WebSocket
specification the receiver can drop a connection when it decides that the
remote side abuses its limits. Since this can happen to a normal connection,
it's ok if it can happen to a logical channel too.

The quota should not be fixed and it does not have to be fixed. The
receiving side can dynamically grow the flow control window when more
buffering capacity is available and stop sending FC frames when there is no
buffer space available. Overcoming quota starvation is all up to flow
control optimization, if the receiver is optimistic and proactive in sending
quotas to the sender then the quota will not drop to 0. The sender doesn't
really need to tell the receiver that it has run out of quota, if the
receiver counts the bytes received from the sender it already knows how many
bytes are left in the sender's quota. 

With best regards,
Arman

-----Original Message-----
From: Greg Wilkins [mailto:[email-masked]] 
Sent: Monday, June 04, 2012 4:55 PM
To: Arman Djusupov
Cc: Takeshi Yoshino; Martin Sustrik; [email-masked]
Subject: Re: [hybi] Flow control quota

Arman,

I think a solution could be to allow the sender to send a control message,
"No remaining Quota" meaning that the sender would send more data if it had
more quota.

This control method could be used in this case where there are not
sufficient window bytes available so as to allow a minimal frame to be sent.

This control frame is also useful even if the quota is completely consumed
because if you follow the flow control discussion over on the SPDY lists,
you will see that fixed quotas will restrict the usage of available
bandwidth.  Thus I suspect that we will need to go to
dynamic window sizes.   If the sender can tell the receiver that it
has consumed it's window (and no the receiver can't tell that itself because
of network latency), then that can inform any receiver decisions to increase
the window size.

cheers

---

From: Jamie Lokier <[email-masked]>
Date: Thu, 7 Jun 2012 03:23:12 +0100

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:
> 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.
> 
                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

---

From: "Arman Djusupov" <[email-masked]>
Date: Thu, 7 Jun 2012 14:02:56 +0300

We have been trying to find some sort of workaround in order to avoid
enveloping the WebSocket frame within a mux frame. If mux was a separate
layer then a WebSocket frame would need to be enveloped within a mux frame
including the WebSocket frame header. This would resolve the unfragmentable
frame issue. But this would also mean that in most cases WebSocket would be
writing two headers per frame. Writing a frame header twice (once for mux
and once the actual frame header) would have a performance overhead. Note
that enveloping the frame would produce considerable bandwidth usage when
lots of small messages are being enveloped.

However the performance overhead of mux in such a case is not tested yet. We
can try to experiment with this design. A mux frame should be able to
include fragments or multiple WebSocket frames that belong to the same
channel. If the length of an enveloped frame is less that length of the mux
frame then the mux frame contains more than one enveloped frames. If the
number of bytes remaining in a mux frame is less than the length of the last
enveloped frame encountered, then the frame is fragmented and the remaining
bytes are expected to arrive in a subsequent mux frame of the same channel.

Going towards this direction is a big change from the original spec design,
so I wasn't even considering it. But if the group decides that it needs to
be evaluated, I can try working on this direction.

With best regards,
Arman

-----Original Message-----
From: Jamie Lokier [mailto:[email-masked]] 
Sent: Thursday, June 07, 2012 5:23 AM
To: Arman Djusupov
Cc: 'Martin Sustrik'; [email-masked]
Subject: Re: [hybi] Flow control quota

Hi everyone,

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

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 
                 ^^^^^^^^^^^^^^^^^^^^^^^^

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

> 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.
                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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.

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.

and demux like this:

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.)

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:

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

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 7 Jun 2012 14:41:15 +0200

I think we have made a rod for our own back with the RSV bits.

Because they are in the frame header, they make extensions very
vulnerable to fragmentation.

For example, if the compressed bit was in the payload rather than the
frame header, then it could be fragmented by extensions below the
compression extension without consequences  - so long as it was
reassembled in the way that Jamie describes.

The moment an extension uses a RSV bit, this means that the frame
cannot be fragmented by anything that does not understand the
extension - and even that results in problems because fragmenting a
compressed frame is not just a matter of setting the RSV bit on all
the fragments - as the data needs to be split into self contained
compressed chunked if the spirit of the framing is to be respected.

maybe we would be best to leave the RSV bits dark for now and do all
extension signalling in the payload?

regards

On 7 June 2012 13:02, Arman Djusupov <[email-masked]> wrote:
> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi

-- 
Greg Wilkins <[email-masked]>
www.webtide.com
Developer advice, services and support
from the Jetty & CometD experts.

---

From: "Arman Djusupov" <[email-masked]>
Date: Fri, 8 Jun 2012 14:06:56 +0300

By ignoring the RSV bits we don't resolve the problem of compressed frames
being unfragmentable. Even if the compression flag was in the payload it
would still not allow us to reassemble a compressed frame once it was
fragmented. Since a compressed frame has its final 4 bytes stripped off, the
receiver needs to know the frame boundary prior to its fragmentation in
order to append the final 4 bytes at the proper place.

We could perform a compression flush at the end of the message boundary
rather than on each frame. In this case the final frame of the message would
indicate the end of the self-contained compressed chunk and every frame
would be fragmentable. This is actually more in tune with the WS spec where
each frame is not required to  contain interpretable data. But as far as the
mux extension is concerned this would still be just a workaround since there
might be other frame-level extensions that require the frame to be
preserved.

At the same time Jamie's solution to allow mux to envelope and fragment all
frames on the wire also pushes the problem to the next layer. When
compression would be used with mux, the receiving side would have to buffer
and assemble the fragments of the frame prior to decompressing it. So, on
one side, the mux flow control algorithm would consider the data as received
and would send the quota to the remote side. At the same time,  the frame
being received would have to be buffered while its final chunk is still on
the wire. So an intermediary or server performing decompression would have
to be smart enough to decompress and forward whatever possible, buffering
only the final part of frame that it is still impossible to decompress.

Since we don't have better ideas, currently I see us having 2 options:

1. Permit the sender to send above the quota if the frame that has to be
sent is not fragmentable, resulting in the quota going negative. The sender
will have to wait for the quota to go positive before it can send the next
frame. The receiver has to make sure that it supplements the sender's quota
to a normal flow control window value once it detects that the sender has
sent a frame above the quota. As long as circumstances are normal the size
of the frame sent above the quota would be normal (e.g. more or less equal
to the size of the frames sent previously). If the receiver detects an abuse
of this functionality it may discard all frames and drop the logical
channel.

2. Permit the mux extension to fragment frames of any type and to reassemble
those frames to their original state on the receiving side. This is probably
the most flexible solution in case if we can find an optimal format for
writing those enveloped frames.

A solution for the 2nd option:
We need to encapsulate frame fragments into a mux message. In this case all
mux frames would have their FIN bit set to 1 and opCode set to 2 (binary),
so the payload of a mux frame will be transparent to all intermediaries that
do not support mux. Mux frames would retain the current format and would
have channelID in their extension data. In addition to that each mux message
that corresponds to the first fragment of the original frame would include
the frame length, opCode, FIN flag and RSV bits of the original frame;
subsequent mux frames would include only the payload of the fragment.

This format would introduce an additional overhead of 16 to 72 bits per
original frame.

This are just some option, I would be happy to read more ideas.

With best regards,
Arman

-----Original Message-----
From: Greg Wilkins [mailto:[email-masked]] 
Sent: Thursday, June 07, 2012 3:41 PM
To: Arman Djusupov
Cc: Jamie Lokier; [email-masked]
Subject: Re: [hybi] Flow control quota

Because they are in the frame header, they make extensions very vulnerable
to fragmentation.

For example, if the compressed bit was in the payload rather than the frame
header, then it could be fragmented by extensions below the compression
extension without consequences  - so long as it was reassembled in the way
that Jamie describes.

The moment an extension uses a RSV bit, this means that the frame cannot be
fragmented by anything that does not understand the extension - and even
that results in problems because fragmenting a compressed frame is not just
a matter of setting the RSV bit on all the fragments - as the data needs to
be split into self contained compressed chunked if the spirit of the framing
is to be respected.

regards

On 7 June 2012 13:02, Arman Djusupov <[email-masked]> wrote:
> enveloping the WebSocket frame within a mux frame. If mux was a 
> separate layer then a WebSocket frame would need to be enveloped 
> within a mux frame including the WebSocket frame header. This would 
> resolve the unfragmentable frame issue. But this would also mean that 
> in most cases WebSocket would be writing two headers per frame. 
> Writing a frame header twice (once for mux and once the actual frame 
> header) would have a performance overhead. Note that enveloping the 
> frame would produce considerable bandwidth usage when lots of small
messages are being enveloped.
>
> However the performance overhead of mux in such a case is not tested 
> yet. We can try to experiment with this design. A mux frame should be 
> able to include fragments or multiple WebSocket frames that belong to 
> the same channel. If the length of an enveloped frame is less that 
> length of the mux frame then the mux frame contains more than one 
> enveloped frames. If the number of bytes remaining in a mux frame is 
> less than the length of the last enveloped frame encountered, then the 
> frame is fragmented and the remaining bytes are expected to arrive in a
subsequent mux frame of the same channel.
>
> Going towards this direction is a big change from the original spec 
> design, so I wasn't even considering it. But if the group decides that 
> it needs to be evaluated, I can try working on this direction.
>
> With best regards,
> Arman
>
>
>> should be applied in a specific order. In this particular case the 
>> mux specification provides two ways of applying the per frame 
>> compression
demonstrates.
> One large compressed frame/fragement, and all other channels are 
> starved - nobody will use mux if it's that unreliable!
> counterproductive (but you can still save those bytes, just make sure it's
purely a syntax optimisation.).
> 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

---

From: John Tamplin <[email-masked]>
Date: Fri, 8 Jun 2012 09:03:20 -0400

> This are just some option, I would be happy to read more ideas.

The original mux proposal introducing another framing layer which is
essentially your #2.  I rewrote it to something close to the current
proposal because lots of people didn't like it.

I think the fundamental issue is not having a separate message-level
framing rather than using one layer of framing for both messages and
frames, which was necessary for efficiency with small messages (which data
with the two apps we had at the time, Wave and GwtQuake, indicated would be
the bulk of the frames; it would be interesting to see the data again now
that there are some deployed apps) and to get consensus on simplicity.

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

---

From: Takeshi Yoshino <[email-masked]>
Date: Wed, 13 Jun 2012 15:50:46 +0900

> order to append the final 4 bytes at the proper place.

Yes. Current per-frame compression extensions is using both frame boundary
information and RSV1 bit.

I took this way to make it easy to flush a part of a message with 4 byte
optimization on most platforms. Thinking again, this optimization is very
useful only for small messages. To flush a part of a big message, this
optimization would be negligible.

IIRC, there's nothing so important that prevents us from changing it from
per-frame to per-message. Per-message spec would allow users to concatenate
SYNC_FLUSH-ed chunks, remove the 4 byte at the end of the message, split
the resulting string at arbitrary point to generate fragments and send
them. We may use only the RSV1 on the first fragment of the message.

> might be other frame-level extensions that require the frame to be

It's also an option that we give up frame-level extensions other than mux.

> being received would have to be buffered while its final chunk is still on

At least, deflate can be processed progressively as each frame arrives even
if the spec is modified to be per-message as described above. Let's just
give up use of the core WebSocket frame boundary to pass the unit of
compression (or any other feature). Let's use some compression-specific
framing inside message body if necessary. RSV bits are still available but
would be message-wise feature. What do you think?

Compression after mux still need to be per-frame basis.

---

From: Martin Sustrik <[email-masked]>
Date: Wed, 13 Jun 2012 11:29:32 +0200

> It's also an option that we give up frame-level extensions other than mux.

That makes sense IMO. Fragmentation is an integral part of multiplexing. 
Using it for other purposes is just asking for trouble.

Martin

---

From: "Arman Djusupov" <[email-masked]>
Date: Wed, 13 Jun 2012 15:17:01 +0300

We can resolve the problem with per-frame compression by aligning
compression to the message boundary. 

But by doing so we dodge the problem with non fragmentable frames that might
be produced by any future extension that is unknown to the intermediary. For
example we may need a reliable streaming extension that numbers all the
frames and adds the frame number in the extension data so that it can resume
sending the message if the connection fails. Such an extension would not
support fragmentation so it would set the RSV bit of each frame to prevent
it from being fragmented by intermediaries. As long as the parent
specification allows extensions to place their data at the beginning of the
frame payload, this extension's data would not be recoverable if the frame
is fragmented, so such an extensions would be incompatible with mux.

It's ok if some extensions are not compatible with mux intermediaries, since
the WebSocket specification allows intermediaries to refuse extensions that
are not known to them. But ideally mux should be transparent to all
extensions, so that mux intermediaries can be unobtrusively introduced at
any point of the communication path without placing any restrictions on the
extensions that may be used and the type of payload being exchanged.

So I think we should take a bit more time to think on how we can resolve the
problem with mux without changing per-frame compression. The second problem
is that changing per-frame compression so that it is applied on the message
boundaries would create an issue if it is applied after mux. Since after mux
there are no message boundaries any more as message frames are intermixed,
the compression would have to be applied on each frame separately. So
effectively per-frame compression extensions would have two modes of
operation, which would be very hard to define in a specification. It would
practically make it a requirement that this per-frame compression extension
be aware that mux is being used. IMO having such coupling between extensions
would be a bad design.

It's preferable that we define a clean/final solution to the problem, so
that whatever extensions are in use in 2050, " good old mux" is still
applicable. I'm trying to work out Jemie's suggestion to let mux be
transparent to intermediaries but haven't figured out any cheap way of
enveloping the frame fragment yet.

With best

-----Original Message-----
From: Martin Sustrik [mailto:[email-masked]] 
Sent: Wednesday, June 13, 2012 12:30 PM
To: Takeshi Yoshino
Cc: Arman Djusupov; [email-masked]
Subject: Re: [hybi] Flow control quota

Martin

---

From: Takeshi Yoshino <[email-masked]>
Date: Fri, 22 Jun 2012 17:19:41 +0900

> sending the message if the connection fails. Such an extension would not

This implies that frame boundary is preserved end-to-end (or we may say
it's preserved extension-to-extension).

Some extensions may just require per-message signaling. Some may require
signaling not aligned to message boundary. Your example might be in the
latter group. Boundaries each extension want to place and use may differ.
Now I think that sharing WebSocket fragmentation defined in RFC 6455
between such extensions is not realistic. But we do have it. For what we
can utilize it?
- partial flush
or
- partial flush and multiplexing

Regardless if we use fragmentation for mux or not, I'd suggest that we stop
using the frame boundary signal for compression, and refrain from using the
boundary of fragmentation and RSV bits and extension data field as
per-frame (per-processing-unit) signaling for future extensions, too.

Extension data is not the only place extensions may touch. Extensions may
transform application data. Per-frame compression does it. No worry.
"reliable streaming extension" may embed sequence and the size of the chunk
in application data. We tend to miss the frame boundary information, but
let's accept new overhead for extensions to represent their processing unit.

> extensions that may be used and the type of payload being exchanged.

The ideal mux does require encapsulation (#2). As John said, it was hard to
sell. Maybe, we can call for opinions again.

I'm ok with full encapsulation though I doubt refragmentability (without
parsing mux) after mux is really important.

> be aware that mux is being used. IMO having such coupling between

Hmm...

---

From: Jamie Lokier <[email-masked]>
Date: Sat, 23 Jun 2012 03:39:15 +0100

Martin Sustrik wrote:
> That makes sense IMO. Fragmentation is an integral part of
> multiplexing. Using it for other purposes is just asking for
> trouble.

Without fragmentation, that means a non-multiplexing proxy can't send
a control message to say why it's dropping the connection, in the
middle of a large message.  E.g. to distinguish between
connection-reset (RST), connection-closed (FIN), and connection TCP
keepalive timeout; something which the receiver can distinguish when
there's no proxy.

Connections with a proxy in the way should be able to relay the same
error conditions as without one, but they can't forward those "direct"
over TCP, they have to be converted to control messages.

I'm not saying that's important, just that it's an effect of
fragmentation that doesn't depend on mux.

-- Jamie

---

From: Takeshi Yoshino <[email-masked]>
Date: Mon, 25 Jun 2012 17:46:09 +0900

I think use of "message" boundary is safe. So, I'd

1. remove MASK bit, (extended) payload length, masking-key (if any) from
the original frame
2. put the remaining bytes into one WebSocket message (opcode=2 as you
said) together with channel ID

On Fri, Jun 8, 2012 at 8:06 PM, Arman Djusupov <[email-masked]> wrote:

> do not support mux.

still true

> Mux frames would retain the current format and would
> have channelID in their extension data.

Moved to the top of the encapsulating message.

>  In addition to that each mux message

> the frame length,

Replaced with the encapsulating message's message length information.

> opCode, FIN flag and RSV bits of the original frame;
>

still true.

> This format would introduce an additional overhead of 16 to 72 bits per

Additional overhead will be 1 octet per original frame.

---

From: Takeshi Yoshino <[email-masked]>
Date: Mon, 25 Jun 2012 18:28:41 +0900

> > multiplexing. Using it for other purposes is just asking for

Based on the context, I think that Martin just agreed with me in terms of
avoiding use of fragmentation for other extensions such as compression but
didn't mean that fragmentation should be exclusive for multiplexing.

> keepalive timeout; something which the receiver can distinguish when

Thanks. The fact that multiplexing itself locks fragmentation is sometimes
problematic. This is one example for that.

---

From: Martin Sustrik <[email-masked]>
Date: Mon, 25 Jun 2012 11:39:52 +0200

On 25/06/12 11:28, Takeshi Yoshino wrote:
> On Sat, Jun 23, 2012 at 11:39 AM, Jamie Lokier <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>     Martin Sustrik wrote:
> Based on the context, I think that Martin just agreed with me in terms
> of avoiding use of fragmentation for other extensions such as
> compression but didn't mean that fragmentation should be exclusive for
> multiplexing.

Yes. Exactly. Fragments can be used by layers below (WS protocol as 
such) but not by the layers above (other extensions, applications etc.)

Compare that to TCP/IP:

Packets are defined at IP level and used for control messages (SYN, RST, 
...) by TCP. They are also used for transporting fragmented data.

However, no layer on top (compression on top of TCP, application using 
TCP) can mess with the fragmentation.

Martin

---

From: Takeshi Yoshino <[email-masked]>
Date: Wed, 27 Jun 2012 16:44:19 +0900

Here's the text for the proposed scheme.

====

6.  Framing

   This extension encapsulates each frame of a multiplexed connection
   into a binary message with Payload Data obtained by concatenating the
   following data in the order they are listed:

   1.  The logical channel ID for the multiplexed connection.

   2.  FIN, RSV1, RSV2, RSV3 and opcode of the original frame.

   3.  Unmasked "Payload Data" of the original frame.

====

8.  Examples

   0x82 0x0d 0x01 0x81 "Hello world"

      This is a non-fragmented text message of "Hello world" on channel
      1 encapsulated into a non-fragmented message.

   0x02 0x07 0x01 0x81 "Hello" 0x80 0x06 " world"

      This is a fragmented encapsulating message converying a non-
      fragmented text frame "Hello world" on channel 1.

   0x82 0x07 0x01 0x01 "Hello" 0x82 0x05 0x02 0x81 "bye" 0x82 0x08 0x01
   0x80 " world"

      This example shows how data for two channels are interleaved.
      There're three non-fragmented encapsulating messages.  The first
      and third one convey each of two frames of a fragmented text
      message of "Hello world" on channel 1.  The second one conveys a
      non-fragmented text message of "bye" on channel 2.

---

From: "Arman Djusupov" <[email-masked]>
Date: Wed, 27 Jun 2012 11:56:24 +0300

This format will produce an overhead of just 1 byte per encapsulated frame.
The only thing that worries me is that the mux extension produces opcode 2
frames, FIN frames and continuation frames in random order. For non-mux
intermediaries this would look like mess, since it would be getting multiple
subsequent frames with opcode 2 without FIN frames between them which is a
violation of RFC 6455 (mux specification eliminate this requirement).

But I'm still fine with this solution. A little inconvenience is small price
to pay for better bandwidth utilization.

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Wednesday, June 27, 2012 10:44 AM
To: Arman Djusupov
Cc: Greg Wilkins; [email-masked]
Subject: Re: [hybi] Flow control quota

====

6.  Framing

====

8.  Examples

   0x80 " world"

---

From: Takeshi Yoshino <[email-masked]>
Date: Wed, 27 Jun 2012 18:31:36 +0900

On Wed, Jun 27, 2012 at 5:56 PM, Arman Djusupov <[email-masked]> wrote:

> This format will produce an overhead of just 1 byte per encapsulated
> frame. The only thing that worries me is that the mux extension produces
> opcode 2 frames, FIN frames and continuation frames in random order. For
> non-mux intermediaries this would look like mess, since it would be getting
> multiple subsequent frames with opcode 2 without FIN frames between them
> which is a violation of RFC 6455 (mux specification eliminate this
> requirement).
>

Ah, no. This format doesn't violate it.

The extension
1. receives messages (maybe already fragmented) from multiplexed virtual
connections
2. adjusts fragmentation by re/de-fragment them and interleaves them
considering quota, fairness, position to insert multiplex control blocks
etc.
3. inserts multiplex control blocks between them
4. tag them with channel ID
5. build an encapsulating message for each of them
6. the resulting messages may also be fragmented if necessary

Each of interleaved data finally forms a message (a regular
(non-interleaved) sequence of fragments) which looks normal for
non-mux-capable intermediaries.

---

From: "Arman Djusupov" <[email-masked]>
Date: Wed, 27 Jun 2012 15:04:35 +0300

This encapsulation would allow a muxed message to be further fragmented by
an intermediary and so resolves the per-frame compression issue when it is
used after mux since it would be able to sync on proper message boundaries.

But it doesn't seem that the original frame boundaries can be recovered
after de-multiplexing as the frame is getting encapsulated after
re-fragmentation. So we completely abandon the idea to preserve the original
frames boundaries? (I don't mind, I just want to clarify).

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Wednesday, June 27, 2012 12:32 PM
To: Arman Djusupov
Cc: Greg Wilkins; [email-masked]
Subject: Re: [hybi] Flow control quota

The extension

---

From: Takeshi Yoshino <[email-masked]>
Date: Thu, 28 Jun 2012 14:07:08 +0900

On Wed, Jun 27, 2012 at 9:04 PM, Arman Djusupov <[email-masked]> wrote:

> an intermediary
Yes

> and so resolves the per-frame compression issue when it is used after mux
> since it would be able to sync on proper message boundaries.****
>
> **
>
I have no idea why you connected the sentences with "so", but yes. There
would be no problem with applying per-frame compression after this new mux.

But after the per-frame compression, fragmentation will be locked.

>  But it doesn’t seem that the original frame boundaries can be recovered
> re-fragmentation. So we completely abandon the idea to preserve the
> original frames boundaries? (I don’t mind, I just want to clarify).
>
Yes. As I stated here
http://www.ietf.org/mail-archive/web/hybi/current/msg09720.html, I'm going
to also change the compression algorithm to per-message one. Then, there
would be no fragmentation lock for any combination.

We can
- add per-message flag to encapsulating message that indicates it has the
final chunk of the encapsulated frame
- change the quota mechanism from per-frame basis to per-byte basis
to make the mux to keep frame boundary.

But I prefer the former.

---

From: "Arman Djusupov" <[email-masked]>
Date: Thu, 28 Jun 2012 11:33:11 +0300

Sorry, I was just rephrasing the text and forgot the "so" in that place.

Agree.

> to make the mux to keep frame boundary.

What do you mean by "per-byte" basis? Current flow control quota is already
expressed in bytes.

With best regards,

Arman

---

From: Takeshi Yoshino <[email-masked]>
Date: Thu, 28 Jun 2012 18:13:46 +0900

**
>
> > - add per-message flag to encapsulating message that indicates it has
> the final chunk of the encapsulated frame****
>
> > - change the quota mechanism from per-frame basis to per-byte basis****
>
> > to make the mux to keep frame boundary.****
>
> ** **
>
> What do you mean by “per-byte” basis? Current flow control quota is
> already expressed in bytes.
>

Sorry. Now the text for quota is saying like "when the size of the frame is
XX, don't send the frame otherwise it's ok to send the frame". I meant that
with this change, the quota mechanism tells go/no-go for each byte, not for
each frame.