Subject: [hybi] Dave's Framing Proposal

From: Dave Cridland <[email-masked]>
Date: Thu, 05 Aug 2010 21:52:35 +0100

I thought I'd name mine, saves confusion. I gave it a nice neutral  
name, too. I wanted to call it "Dave's Really Great Framing  
Proposal", but I decided not to.

First off, feature negotiation is external. Presumably we'd do it in  
the framing layer. I'd include both compression (at stream level) and  
TLS (likewise) here. I believe that external negotiation is not  
contentious. I think the latter two may be, but I'd like to have  
optional TLS as well as mandatory TLS (ie, "StartTLS" as well as  
port-based old-school).

As for the framing itself, rather than describe actual bitfields, I  
thought I'd describe some properties.

1) Have a single leading octet, which has a frame type.

a) This frame type says if it's a leading chunk, a completing text, a  
completing blob, or a control.

b) If it's a control, then some of the remaining bits are used to  
indicate what it is, including Final Frame, Ping, Pong, etc.

c) There should be some bits left over (and therefore reserved, MUST  
zero, MUST ignore).

2) A stream identifier, set to 0x01 in the version of the standard.  
Other values MUST cause the frame to be discarded by receivers.  
Intermediaries MUST ignore this value.

3) A 16-bit, network order, extension length field. This describes  
how much of the packet is extension data (ie, designed for the stack  
to process) rather than payload data. This field MUST NOT exceed the  
length of the frame's payload.

4) A 16-bit, network order, payload length field. This describes the  
entire payload, including any extension data. A naïve intermediary  
MAY therefore ignore the extension length in order to forward frames;  
however if it chooses to refragment frames it MUST take into account  
the extension length.

5) Extension data. Note that we need to handle multiple extension  
data, therefore this field needs to be internally TLVed consistently.

6) Payload data.

I think this outlines something which:

A - Is likely to serve for the foreseeable future - it contains  
sufficient extension/expansion space to adapt as we find new  
requirements. Note I've specifically ignored multiplexing and Greg's  
MIME proposal, yet both have potential space.

B - Can be treated simply by intermediaries, particularly naïve ones.

Downside is that it's 6 octets, but I can't see an obvious way of  
avoiding this without either having a variable-length header, or  
dropping some features.

I know this will not please everyone completely, and that's okay. I'm  
more curious, though, as to whether this is likely to be workable for  
everyone if pushed.

Dave.
-- 
Dave Cridland - mailto:[email-masked] - xmpp:[email-masked]
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade

---

From: Douglas Otis <[email-masked]>
Date: Thu, 05 Aug 2010 14:15:49 -0700

> 1) Have a single leading octet, which has a frame type.
This tag should keep data framing state separate from bits describing 
content.  As such, at least 3 bits could be dedicated for framing state. 
Such as "start", "end", "concatenated".
> completing blob, or a control.
Frame type can signal initial frame, intermediary frame, and/or ending 
frame for the stream, as well as low level content descriptors.
> indicate what it is, including Final Frame, Ping, Pong, etc.
The explicitly defined initial frame could always represent 
meta-information, where frames can also be concatenated within the 
enclosed message. This would keep the frame header information limited 
to using 4 bytes.
> Intermediaries MUST ignore this value.
Okay.
> 3) A 16-bit, network order, extension length field. This describes how 
> much of the packet is extension data (ie, designed for the stack to 
> process) rather than payload data. This field MUST NOT exceed the 
See above.  Consider the possibility of having frame concatenation, 
where the first frame always exchanges meta-information, even when given 
a zero length.
> entire payload, including any extension data. A naïve intermediary MAY 
> therefore ignore the extension length in order to forward frames; 
The meta-data should also use TLV structures, but this should not impact 
the actual data payload.
> 6) Payload data.
-Doug

---

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

Dave,

trying to reduce your proposal to it's essentials and avoid debates
about length encoding etc...

I think the main essence of  what you are saying is that all frames should be:

 opcode + meta-length + total-length + meta data + data

But you have also declared some fixed lengths etc. which I feel might
detract from the core proposal.

For instance, I think we could achieve most of you want with variable
length encoding as follows:

   opcode + var-length + var-meta-length + metadata + data

So for a simple helloworld message, the bytes would be

  0x00 0x0B 0x00 'hello world'

We could still have a fragment bit in the opcode

  0x40 0x06 0x00 'hello '
  0x00 0x05 0x00 'world'

But we could also negotiate an extension to add a channel ID to every
frame (for example 0x1234)

  0x40 0x08 0x02 0x12 0x34 'hello '
  0x00 0x07 0x02 0x12 0x34 'world'

I like the variable length version of this proposal (let's call it
"Daves even more awesome proposal") because it has a very simple base
case.  Even for the most complex of cases, the framing is pretty
simple and infrastructure can deal with it.

However, there will still be complexity in how the extensions are
negotiated and how they interact with op-codes.  Me may also need to
negotiate op-codes and could even need a variable length op-code, so
the header is just 3 variable length integers (hmm less keen on that).

cheers

---

From: Dave Cridland <[email-masked]>
Date: Thu, 05 Aug 2010 23:22:26 +0100

>  opcode + meta-length + total-length + meta data + data
I'm saying that all frames have a fixed-size header, which includes a  
fixed-size length field denoting the size of the payload.

This is:

magic[1] + stream[1] + meta-length[2] + total-length[2] +  
meta[meta-length] + payload[total-length - meta-length]

>   0x00 0x07 0x02 0x12 0x34 'world'

Also no extensions change the header size, so intermediaries can be  
as dumb, and rarely upgraded, as they want.

Dave.

---

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

Dave,

I understand that you are advocating fixed length fields.

But I think your proposal has value even if it was implemented with
variable lengths, so I think it worthwhile to consider your proposal
in two parts so that any goodness that it might have with metadata per
frame will not be lost in endless debates about length encodings.

cheers

On 6 August 2010 08:22, Dave Cridland <[email-masked]> wrote:
> magic[1] + stream[1] + meta-length[2] + total-length[2] + meta[meta-length]
> + payload[total-length - meta-length]
>
> Also no extensions change the header size, so intermediaries can be as dumb,
> and rarely upgraded, as they want.
>
> Dave.
> --

---

From: Dave Cridland <[email-masked]>
Date: Fri, 06 Aug 2010 00:18:27 +0100

> I understand that you are advocating fixed length fields.
Indirectly.

I'm advocating a fixed, and constant, length header. That is, with  
this design, the header is now, and ever shall be, 6 octets, with the  
last two octets uniformly indicating the remaining data in the frame.  
That needs fixed-width length fields to make it work, so therefore I  
am advocating them.

> frame will not be lost in endless debates about length encodings.

I don't think there is nearly as much.

Dave.

---

From: Dave Cridland <[email-masked]>
Date: Fri, 06 Aug 2010 00:23:58 +0100

> I don't think there is nearly as much.

To put it another way, I'm not terribly interested in "I think I'd  
like this more if". I'm not even that interested in "This is great".

I'm only interested in "I cannot use such a design because".

Dave.

---

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

On Thu, Aug 5, 2010 at 4:23 PM, Dave Cridland <[email-masked]> wrote:

> To put it another way, I'm not terribly interested in "I think I'd like
> this more if". I'm not even that interested in "This is great".
>
I find it a bit hard with all these proposals going around to evaluate the
tradeoffs of N+1 over N. Could you state why you find your proposal to be
advantageous to "Take V" [1], key differences, and why those key differences
matter? I don't mean to say my proposal is great / really great / perfect,
just that I am having trouble understanding what you see as advantages in
your proposal? In V, I tried to leave out as much contentious things as
possible such that for a client/server/intermediary who wish to be
blissfully ignorant of extensions, normal messages are as small as possible,
and intermediaries that don't understand the extensions don't even see that
there is extension data (modulo fragmentation, which would be rather
perilous as an extension).

At the end of the day we do need to build some sort of consensus, so I
personally took an approach I hoped would meet people's requirements and
give on some of the other things I felt strongly about (like fixed-length
length encoding) so that we could move towards consensus (hopefully).

[1] http://www.ietf.org/mail-archive/web/hybi/current/msg02924.html

>
> Dave.
> --
> Dave Cridland - mailto:[email-masked] - xmpp:[email-masked]<[email-masked]>
> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>

---

From: Dave Cridland <[email-masked]>
Date: Fri, 06 Aug 2010 09:52:08 +0100

On Fri Aug  6 00:30:53 2010, Ian Fette (イアンフェッティ)  
> perilous as an extension).
Right.

A few people (including Roberto) made the compelling (to me) argument  
that a fixed header size led to simple intermediaries - it becomes,  
potentially, a single read and a DMA transfer between NICs. There's  
been lots of discussion concerning concentrators, for instance, so  
I'm relatively convinced by this.

Like you, I also wanted an immutable header, such that an  
intermediary need not maintain much state about a connection.  
However, I worked on the assumption that a MUX id would be useful at  
a higher level, as I think it's reasonably clear that demux and remux  
of WebSockets is a potentially useful characteristic.

By explicitly giving an offset to the data (or the length of the  
extension data), this also allows safe refragmentation by essentially  
naïve intermediaries.

Note that by suggesting both fixed and variable extensions, where the  
negotiation ordering of extensions is deeply significant, you force  
intermediaries wishing to eavesdrop (or add, or remove) extensions to  
maintain state on each session - by using a TLV arrangement (which I  
left unspecified) this is still possible, albeit much less efficient  
that the two functions above.

> length encoding) so that we could move towards consensus  

As did I - I did actually want to use a 32-bit length originally, but  
the consensus seemed in favour of 16-bit or variable. The consensus  
seems to be changing, now, again. I'm personally remaining of the  
opinion that using HTTP for bulk transfer seems sanest, but I find  
myself in a minority. I have no problem with increasing the header  
size, as long as it remains reasonable - my main goal is to ensure  
that applications can be built which can communicate effectively  
while remaining under the 3G FACH threshold of around 128 octets -  
this would mean "web apps" which can run all day on a typical  
smartphone. If the extension and data lengths were increased to 32  
and 64 octets, that would take us up to around the 16 byte mark,  
which is practical, if heavy.

I certainly take your point about moving toward consensus. At the  
moment, we seem to be running very fast in circles. The Coriolis  
effect is very pretty, but I usually see it while things are going  
down the drain.

Dave.

---

From: Jamie Lokier <[email-masked]>
Date: Fri, 6 Aug 2010 17:51:46 +0100

Dave Cridland wrote:
> >I find it a bit hard with all these proposals going around to
> >evaluate the tradeoffs of N+1 over N. Could you state why you find
> >your proposal to be advantageous to "Take V" [1], key differences,
> >and why those key differences matter? I don't mean to say my
> >proposal is great / really great / perfect, just that I am having
> >trouble understanding what you see as advantages in your proposal?
> >In V, I tried to leave out as much contentious things as possible
> >such that for a client/server/intermediary who wish to be
> >blissfully ignorant of extensions, normal messages are as small as
> >possible, and intermediaries that don't understand the extensions
> >don't even see that there is extension data (modulo fragmentation,
> >which would be rather perilous as an extension).
> >
>
> Right.
> 

I think the above is based on a false assumption.  IP and TCP headers
are variable size and it does not prevent fast DMA transfer between NICs.

> that the two functions above.

I think the above is not (necessarily) true.  You've probably seen
recent responses to Greg from me, suggesting this:

    length multiplex-opcode stream-id [whatever...]

Where "whatever" may be chunk-opcode, compression, etc. or just
a simple message.

If an intermediary is purely demux and remuxing streams, it does not need to
inspect the "whatever".  It just needs to use the stream-id and
forward based on that and the length.

If it is also rechunking, which it should, then it'll need to look
inside this:

    length multiplex-opcode stream-id chunk-opcode final=? [whatever...]

Either way, the mux header for forwarding decisions fits into a fixed
number of bytes.  It's not fixed length, but a fixed length read() is
sufficient to get it and make forwarding, chunking and filtering decisions.

If an intermediary wishes to eavesdrop (or add, or remove) other
extensions, they'll need to parse variable length extension one way or
another.

Do you think that's mistaken?

> myself in a minority.

While I agree with using HTTP for bulk transfer (though there may be a
case for HTTP-over-websocket if it multiplexes well), I expect the
following fragility with a 16-bit message size limit:

Designer writes some app code which sends messages to the browser.  They
are HTML fragment updates, wiki document edits or whatever.

Everything works for 1 year.  All updates/edits are <1kB in testing,
and <4kB in widespread use.

One day, some user makes a large change to some document at once, and
the entire software stack breaks because it tries to send a 70kB HTML
update.  The designers didn't anticipate it (and they've all left the
company).  The users didn't expect a large edit to break - because
edits have always been fine, and it's tiny by modern computer standards.

Or maybe it just broke because a user changed the template generating
HTML fragments to add a bit of style, pushing the size of existing
messages over the edge.

The observed symptom is messy, infinite retries, exceptions, or wrong
data shown in the browser.  Users enjoy a broken app, or maybe they
don't even realise it's lost something they thought was committed -
until it's too late.  User doesn't have any idea why it broke, of course.

Problem would have been avoided if WebSocket didn't have a small
message size limit, or if the app designers had planned for it and
implemented their own message concatenation.  But designers don't tend
to do those things for rare, "nobody would ever" corner cases - they
are always pressed for time, and move on when it's working well enough.

There's no "correct" answer, but imho we should strive to avoid
fragility when it's easily avoided.

Greg puts it well: Either a large value that won't be reached (64-bit
ish), or a smaller value that is often reached (to ensure deployed
code tests those branches), not something in between that encourages
easily deployed latent implementation bugs.

-- Jamie

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 9 Aug 2010 11:09:49 +1000

> following fragility with a 16-bit message size limit:

I agree that HTTP over websockets is an interesting future
possibility, but it would need multiplexing and thus would need
fragmentation.  Thus it would not be limited if the max frame size was
32b or 16b.

It is really important to make a distinction between max frame size
and max message size.   The only real benefit of having a large max
frame size is that it  makes it easy for a sender to send very large
known content (eg big file). However, if fragmentation is supported,
then it will not guarantee that it will arrive in one big frame, as an
intermediary might decide that it wishes to fragment the large message
(for any number of reasons, including multiplexing, aggregation,
memory management etc.)

I'm happy to support  a huge frame size, but I don't think having a
small or medium size max frame would significantly limit the usage, so
long as we support simple fragmentation.

I also agree that with the current browser API I struggle to think of
usages that will need really huge messages, however I also note that
the first Jetty implementation of variable length binary frames put
the length into a signed 32bit integer.  Within a week of release,
somebody writing a non browser client hit the bug in jetty that I
didn't handle the signed bit correctly, so they were sending > 2GB
content.  No idea what for, but I certainly had to switch to a 64 bit
signed long.

cheers