Subject: [hybi] Framing Take V - extensibility

From: Ian Fette (イアンフェッティ) <[email-masked]>
Date: Thu, 5 Aug 2010 00:50:42 -0700

I'd like to take a stab at a proposal for an extensible base frame, that
will let us leave out discussion of multiplexing and other protocol
complexities, but let us implement them as extensions in an efficient manner
later on.

Stating assumptions up front:

1. I am assuming a variable length "length" field. This is a change from the
preference I expressed at Maastricht and the preference I heard most people
express at Maastricht, but frankly I don't have the stamina for an argument
here and value making progress more than a fixed-length "length". The
proposal could easily be changed to be "fixed-length" if people feel
strongly.

2. I am assuming that people will want to write protocol-level extensions
that include a fixed amount of extension-specific data per frame (such as a
stream ID in multiplexing, an indication that the data is "chunked," an
indication that the data is "compressed", and so forth.)

3. I am assuming that people will want to write protocol-level extensions
that include a variable amount of extension-specific data per frame (such as
MIME types, where the length of the MIME type varies based on the MIME type
- e.g. "text/plain" is shorter than "application/octet-stream".)

4. I am assuming that we want to indicate whether the data is intended for
the text-based or binary-based JS API.

5. I am assuming that we want to support fragmentation if it makes sense to
send the data in fragments, e.g. the result is a database query that is
coming in parts I want to dispatch ASAP. In composing this email I
originally tried to leave it out, but fragmenting a message seems like
something that could be very useful e.g. for an intermediary with memory
constraints or for a server sending dynamically generated data. To be
honest, the arguments against fragmentation that were most compelling were
"There may be data that is more efficient for me as a client to send
un-fragmented, and a 64K max frame size prohibits me from doing so." This
proposal makes it possible for you to sendfile() an arbitrary length file if
you want, but also allows a server to send dynamic data in fragments when
that makes sense. I am hoping this is a reasonable compromise.

6. I am assuming that we want extensions to not change the basic framing,
e.g. there should be some basic framing that is consistent whether or not
extensions are in use.

So, if a client or server wants to declare support for no extensions, the
protocol boils down to the following:

-------------------------------------------------------------------
| frag(1) reserved(3) op(4) | length (8 | 16 | 24 | 32 ...)        |
-------------------------------------------------------------------
|                              Data                                |
-------------------------------------------------------------------

 ws-frame            = frame-fragment
                       frame-reserved
                       frame-opcode
                       frame-length
                       octet-data

 frame-fragment      = %x0 ; 1 bit not a fragment
                     | %x1 ; 1 bit fragment

 frame-reserved      = %x0 ; 3 bits

 frame-opcode        = %x0 ; text data frame
                     | %x1 ; binary data frame
                     | %x2 ; ping
                     | %x3 ; pong
                     | %xf ; final frame

 frame-length        = unlimited-integer

 unlimited-integer   = *( %x80-FF ) %x00-7F
                       ; concatenate 7 low order bits from each octet
                       ; to form a binary integer

 octet-data          = *( %x00-FF )

In short, it's about as basic as I think we can get it, and is pretty
similar to what Greg sent out a week ago, with the addition of defining
fragmentation and ping/pong.

What I would like to also define is how this protocol can be extended.

What I propose is similar to, but slightly different from, what both Jamie,
I, and others have proposed in earlier threads. Similar to in that the
extension data goes in the "data" section of the base protocol, different in
that it supports (in what I hope to be a nice manner) both fixed- and
variable-length extension data.

The exact format of the below I don't care about quite as much, it's the
idea I'm trying to get across more than anything else. If someone has syntax
suggestions, by all means.

Opening Handshake:
Client sends a list of extensions it supports and would like to use. Assume
ordering has significance where that makes sense, e.g. if two extensions
serve the same purpose, the client would prefer to use the first one
specified over the second. Some of these extensions require a fixed number
of bits in each frame (F1-4 in my example), some of these extensions require
a variable number of bits in each frame (V5-8), and some require no bits in
the frame (N9-10). [NB: I am not trying to require that extension names be
prefixed with F/V/N, it is for illustrative purposes only.]

Client: "Extensions: F1, F2, F3, F4, V5, V6, V7, V8, N9, N10" (assume F1-4
and V5-8 are extension names)

Server responds with a list of extensions that will be used, ordering is
also significant (e.g. if data is compressed by extension COMPRESS and
encrypted by extension ENCRYPT and the server responds with "Extensions:
ENCRYPT, COMPRESS" assume that extensions are applyed in a layered manner to
the data, with COMPRESS being applied on the inner layer, e.g.
ENCRYPT(COMPRESS(DATA))." [NB: Suggestions for better syntax/wording
welcome, I'm trying to get across a point, I'm not claiming to be an awesome
syntax writer.]

Server: "Extensions: F1, F3, F4, V6, V7, N10"

Server also responds with an ordering for extension metadata, and the bit
offset for fixed-length extension data. Fixed-length extension data
always precedes variable length metadata so that it remains at a fixed
offset in the start of "Data".

Example:
Server: "Offsets: F1:0:1, F3:8:15, F4:2:2, V6:, V7:"

The interpretation of this is that F1's metadata is at (Data & 0x03), F3's
metadata is at (Data[0] & 0x0FF00, F4's metadata is at 0x04, and V6 is a
length-prefixed (unlimited-integer) set of metadata for V6, followed by a
length-prefixed (unlimited-integer) set of metadata for V7.

As an example of how this could be used: Imagine F1 is an extension
indicating whether the text is UTF-8, UTF-16, UTF-32, or Latin-1. F2 is some
extension the server doesn't want to support. F3 is a multiplexing extension
that requires 1 byte for stream ID. F4 is an extension indicating whether
the data is compressed. V6 is a mime-type extension and V7 is some other
arbitrary extension.

To see if the text is UTF-8,16,32, or Latin-1, the server would take the
first byte of "Data" and AND it with 0x3 to obtain the appropriate flags.
To get the stream ID, the server would take the second byte of Data (or,
conceptually take all of Data and and it with "0x00 FF 00 00 00 00 ......
and shift it 1 byte"
To get the state of whether the data is compressed, the sever would take the
first byte and AND it with 0x4 and shift.
To get the MIME types (v6), the server would read the LENGTH of the mime
types extension data from byte 3 (and byte 4 and byte 5  --  variable
length), and then read that much data after the length.
To get whatever data is for V7, the server would read the LENGTH from right
after V6's DATA, and then read that many bytes.

The actual data itself would start after V7's DATA.

Open to suggestions for how to express this more cleanly/efficiently, while
ensuring that fixed-length metadata remains at fixed offsets across all
frames.

With this approach, I believe the base protocol for servers and clients who
declare themselves ignorant of extensions is about as simple as we can make
it, allows for people to send fragmented or unfragmented data as it makes
sense (and I believe both sides have given arguments that I hope are
convincing for the other side as to why they may want to send fragmented or
unfragmented data from their "endpoint"), and allows for extensibility. I
have tried to accommodate the views I've heard expressed on the mailing list
and in person, and believe that this should meet all of the use cases I've
heard described thus far, including compression and multiplexing as
efficient extensions, MIME metadata for clients and servers who wish to
exchange it at the protocol level, and even control frames (via a control
frame extension, where presumably the server and client who understand that
extension would agree that this is "control data" based on some "extension
data").

Thoughts welcome.

-IanF

---

From: Arman Djusupov <[email-masked]>
Date: Thu, 05 Aug 2010 12:26:10 +0300

Ian Fette (イアンフェッティ) wrote:
> I'd like to take a stab at a proposal for an extensible base frame, 
> that will let us leave out discussion of multiplexing and other 
> protocol complexities, but let us implement them as extensions in an 
> efficient manner later on.

Most of this proposal is fine with me. When large messages are already buffered, the variable length allows them to be sent without having to chunk them.
 
> The interpretation of this is that F1's metadata is at (Data & 0x03), 
> F3's metadata is at (Data[0] & 0x0FF00, F4's metadata is at 0x04, and 
> V6 is a length-prefixed (unlimited-integer) set of metadata for V6, 
> followed by a length-prefixed (unlimited-integer) set of metadata for V7.

I don't think that it is necessary to negotiate offsets. Since both sides are familiar with the extensions and since the order in which they are applied is defined, both sides will know what meta-data to expect and in which order. In any case if an extension transforms the frame content (for example compression) then there is very little value in knowing what offset other extension metadata had in the data prior to its transformation. Imagine an intermediary transparently applying compression to all frames that it relays. How will it re-calculate those offsets?

I suggest that both sides just negotiate the extensions and the order in which they are applied. Then each extension is responsible for writing and reading their portion of the meta-data into/from the frame and de-enveloping the data if necessary, so the frame is pipelined through all extensions until fully processed.

Arman

---

From: Ian Fette (イアンフェッティ) <[email-masked]>
Date: Thu, 5 Aug 2010 02:37:17 -0700

On Thu, Aug 5, 2010 at 2:26 AM, Arman Djusupov <[email-masked]> wrote:

> Most of this proposal is fine with me. When large messages are already
> buffered, the variable length allows them to be sent without having to chunk
> them.
>
>
>  Example:
> I don't think that it is necessary to negotiate offsets. Since both sides
> are familiar with the extensions and since the order in which they are
> applied is defined, both sides will know what meta-data to expect and in
> which order. In any case if an extension transforms the frame content (for
> example compression) then there is very little value in knowing what offset
> other extension metadata had in the data prior to its transformation.
> Imagine an intermediary transparently applying compression to all frames
> that it relays. How will it re-calculate those offsets?
>
> I suggest that both sides just negotiate the extensions and the order in
> which they are applied. Then each extension is responsible for writing and
> reading their portion of the meta-data into/from the frame and de-enveloping
> the data if necessary, so the frame is pipelined through all extensions
> until fully processed.
>
>
To the extent that's possible that would be fine with me.

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 5 Aug 2010 19:43:10 +1000

Ian,

Firstly I totally agree with the basic framing you have proposed with
fragmentation and variable length. I think having fragmentation in the
base protocol is simpler than any extension that might implement
fragmentation. I also think having fragmentation in the base will mean
that all new intermediaries that are written to be ws aware will no
about fragments. Having intermediaries unaware of fragments is asking
for trouble if they try to do something value-add.

I think fixed length is simpler, but variable length is petty simple
also, specially if I'm allowed to fragment if I don't want to go too
big.
I really hope we can reach consensus on the basics soon.

With regards to your extension mechanism, I have a couple of issues with it.

Firstly is is moderately complex, specially when compared to the
martinesque proposal of just adding an op-code for a MIME frame. If
the only extensions we can think of are compression and multiplexing,
then it feels very heavy weight.  However, I think it is likely that
there will be extensions created by load balancers, SSL offloaders and
aggregators, so the negotiation may be worth it.

The I think for some extensions, it will be a little confusing to have
both an opcode and meta-data in the same frame. If the meta data is
saying the data is compressed, but the op-code is 0x00, then an
intermediary or debugger might try to look at the data as utf-8 text.
I'd much rather a system that if the data is extended then it is clear
to all implementations that either they know about the extension OR
they data should be opaque to them and they either ignore or simply
forward the frame.  I think robertos proposal of per frame meta data
also suffers from this problem.

Julians proposal does not suffer from this, because it negotiates new
op codes, so extended frames will never have a standard opcode.

My current preference is Martins proposal of simply adding an opcode
for a MIME encoded frame.

If we really want to allow ultra efficient extensions, then Julians
proposal to negotiate extra opcodes would allow an arbitrary data
frame content to be negotiated - this can be used together with
Martins proposal.

cheers

2010/8/5 Ian Fette (イアンフェッティ) <[email-masked]>:
> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>
>

---

From: Arman Djusupov <[email-masked]>
Date: Thu, 05 Aug 2010 14:49:50 +0300

> also suffers from this problem.

If an extension requires transformation, an extension-aware implementation should automatically change the bit from text to binary once the extension is applied to the frame. When the transport does apply compression to the frame it's not only a text-to-binary transformation, the length of the data also changes. So we must assume that the implementer of an extension-aware transport will be responsible for setting all flags and length properly.

> op codes, so extended frames will never have a standard opcode.

In the case when multiple extensions are pipelined on the same frame it would be difficult to judge in which order they are applied by just looking at the frame's opcodes.

Let's say we have an intermediary that applies compression, encryption and reliable delivery headers. Reliable delivery is applied only to the first frame of the message and ignores the rest, compression is applied to all frames that are bigger than 1KB, while encryption is applied to all frames without distinction. So we need a smart algorithm to assign opcodes to variations such as reliable+compressed+encrypted, compressed+encrypted, reliable+encrypted, encrypted variations.

> for a MIME encoded frame.

I think that locking the extended frame to MIME would hurt performance for some extensions. An extension might just want to add a sequenceID to the first frame of each message, so it basically needs just a 4 byte offset. Using MIME would force all extensions to expect a MIME in the frame, which might result in poor performance.

> frame content to be negotiated - this can be used together with 

Why not just reserve 1 opcode for "extended frame" and leave the rest to the extension pipeline defined by the negotiation. So, those that need MIME will require MIME, and those that do not need any meta-data at all will add nothing to the frame.

Arman

---

From: Julian Reschke <[email-masked]>
Date: Thu, 05 Aug 2010 14:01:39 +0200

On 05.08.2010 11:43, Greg Wilkins wrote:
> ...
> ...

For the record: not my proposal (I haven't looked at this topic at all, 
so I'm not even sure what the proposal is :-)).

Best regards, Julian

---

From: Ian Fette (イアンフェッティ) <[email-masked]>
Date: Thu, 5 Aug 2010 05:30:11 -0700

> I really hope we can reach consensus on the basics soon.
I sincerely hope so too :)

> aggregators, so the negotiation may be worth it.
Yeah, I'm not totally thrilled with the complexity, that said: I do believe
that there will be extensions that want to be able to access fixed-sized
data at a fixed offset, multiplexing being just one example. I also believe
there are cases for variable-length extension data. It's true that we could
cast everything as a key:value variable-length pairing, but then you lose
efficiency, and it would suck to have to parse everything out if you don't
actually care about e.g. the data, but instead just want to look at some of
the extension data (such as a stream ID) and forward the frame on.

> also suffers from this problem.
Well, you sort of have this: If you look at extensions as being layered, and
you are unaware of the semantics of the outer layer, then all the inner data
effectively is just a binary blob that you can't reason about (and still
fits in with the base protocol because it is exactly the "data" segment of
the base protocol). If you do understand the outer extension, you can
essentially peel the onion until you hit an extension you don't understand.

> F3's

---

From: Ian Fette (イアンフェッティ) <[email-masked]>
Date: Thu, 5 Aug 2010 05:30:57 -0700

On Thu, Aug 5, 2010 at 4:49 AM, Arman Djusupov <[email-masked]> wrote:

>> both an opcode and meta-data in the same frame. If the meta data is saying
>> the data is compressed, but the op-code is 0x00, then an intermediary or
>> debugger might try to look at the data as utf-8 text.
>> I'd much rather a system that if the data is extended then it is clear to
>> all implementations that either they know about the extension OR they data
>> should be opaque to them and they either ignore or simply forward the frame.
>>  I think robertos proposal of per frame meta data also suffers from this
>> problem.
>>
>
> If an extension requires transformation, an extension-aware implementation
> should automatically change the bit from text to binary once the extension
> is applied to the frame. When the transport does apply compression to the
> frame it's not only a text-to-binary transformation, the length of the data
> also changes. So we must assume that the implementer of an extension-aware
> transport will be responsible for setting all flags and length properly.
>
>
>  Julians proposal does not suffer from this, because it negotiates new op
>> codes, so extended frames will never have a standard opcode.
>>
>
> In the case when multiple extensions are pipelined on the same frame it
> would be difficult to judge in which order they are applied by just looking
> at the frame's opcodes.
>
> Let's say we have an intermediary that applies compression, encryption and
> reliable delivery headers. Reliable delivery is applied only to the first
> frame of the message and ignores the rest, compression is applied to all
> frames that are bigger than 1KB, while encryption is applied to all frames
> without distinction. So we need a smart algorithm to assign opcodes to
> variations such as reliable+compressed+encrypted, compressed+encrypted,
> reliable+encrypted, encrypted variations.
>
>
>  My current preference is Martins proposal of simply adding an opcode for a
>> MIME encoded frame.
>>
>
> I think that locking the extended frame to MIME would hurt performance for
> some extensions. An extension might just want to add a sequenceID to the
> first frame of each message, so it basically needs just a 4 byte offset.
> Using MIME would force all extensions to expect a MIME in the frame, which
> might result in poor performance.
>
>
>> proposal to negotiate extra opcodes would allow an arbitrary data frame
>> content to be negotiated - this can be used together with Martins proposal.
>>
>
> Why not just reserve 1 opcode for "extended frame" and leave the rest to
> the extension pipeline defined by the negotiation. So, those that need MIME
> will require MIME, and those that do not need any meta-data at all will add
> nothing to the frame.
>
>
+1

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Thu, 05 Aug 2010 18:59:06 +0200

* Ian Fette wrote:
>constraints or for a server sending dynamically generated data.

There is a difference between splitting one message into multiple frames
and splitting a message into multiple chunks in the same frame. What is
the motivation behind preferring the former to the latter here (other
than considerations for possible evolutions of the protocol where frames
of one kind may be interleaved with frames of some other kind, or where
frames may be delivered entirely out of order)?

A 1:1 relationship between "message" and "frame", as chunking would
maintain, avoids some questions such as "What if a text frame is split
in the middle of a UTF-8 sequence?" or "What if you have an incomplete
text frame and get a binary frame before the end of the text frame?".
-- 
Björn Höhrmann · mailto:[email-masked] · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/

---

From: Greg Wilkins <[email-masked]>
Date: Fri, 6 Aug 2010 08:38:00 +1000

> text frame and get a binary frame before the end of the text frame?".

I think it is very important to establish that fragmentation of a
message into multiple frames must not effect the semantics of that
message in any way.

Thus UTF-8 multi-byte sequences may be split over multiple frames, but
not over multiple messages.

regards

---

From: Ian Fette (イアンフェッティ) <[email-masked]>
Date: Thu, 5 Aug 2010 16:14:24 -0700

> not over multiple messages.

To support something like multiplexing, where you have a frame from A, a
frame from B, a frame from A, a frame from B interleaved to form two
complete messages, you need most of the extension data at that point in each
frame (e.g. you need to know is this frame from stream A or stream B). I am
not sure how you would "chunk" a message and yet still be able to interleave
data from two different streams safely without that data (assuming I am
correctly understanding your distinction between "chunking" and
"fragmentation").

I agree with Greg fully that fragmentation of a message into multiple frames
should not affect any message semantics.