Subject: [hybi] summary of frame length options

From: John Tamplin <[email-masked]>
Date: Wed, 25 Aug 2010 17:34:08 -0400

>From the request I made for a consensus call on length encoding, there has
been a request to summarize the various options that are have been
presented.  Below, I will go through each of them an provide a brief
description and some sample (not optimized) code for decoding the length.
 Note that I am only including those options which support 63-bit frame
lengths, as there seemed to be strong objections to anything that required
fragmentation, and in all cases for the 64-bit value the high bit is
required to be zero, for support of languages such as Java which do not have
an unsigned 64-bit integral type.  The framing is intended to be as in
http://www.ietf.org/mail-archive/web/hybi/current/msg03371.html so the
assumption is there are 3 reserved bits available in the header, and some of
these proposals provide less (which may require extending the header to get
the extensibility desired).

For reference, an informal poll on most of these options lives at
https://www.google.com/moderator/#15/e=2809f&t=2809f.40 and the order
presented is the order shown there, based on expressed preferences of a
small sample.  The names used are the various options supported for bit
lengths, which is both unique and somewhat descriptive.

I will post my own arguments for or against each of these options in a
separate message.

 ===== 7/16/63 =====

> Use 7 bits in the frame header, and if the value is 0-125, that is the
length.  If the value is 126, then the next 2 bytes are a 16-bit length.  If
the value is 127, the next 8 bytes are a 63-bit length (the high bit must be
zero).

long long len = readByte() & 127;

> switch (len) {

>   case 126:

>     len = readUnsignedShort();

>     break;

>   case 127:

>     len = readLongLong();

>     break;
}

===== 8/16/32/63 =====

> Allocate two bits in the header to store log2(length-length), and use the
other reserved bit as part of the single-byte length.  Thus, this proposal
requires adding another byte to the header, getting 8 reserved bits.

// unlike the other code snippets, this reads the entire header
unsigned short hdr = readUnsignedShort();
long long len;

> switch (hdr & LEN_LEN_MASK) {
  case LEN_LEN_8:
    len = readByte();
    break;
  case LEN_LEN_16:
    len = readUnsignedShort();
    break;
  case LEN_LEN_32:
    len = readUnsignedLong();
    break;
  case LEN_LEN_64:
    len = readLongLong();
    break;

> }

===== 8/63 =====

> Use 8 bits in the frame header (so one fewer reserved bit available), and
if the value is 0-254, that is the length.  If the value is 255, the next 8
bytes are a 63-bit length (the high bit must be zero).

long long len = readByte();

> if (len == 255) {

>   len = readLongLong();

> }

===== 15/63 =====

> Add a third byte to the header, and use 15 bits of it for the length.  If
the value is 0-32766, that is the length.  If the value is 32767, then the
next 8 bytes are a 63-bit length (the high bit must be zero).

long long len = readUnsignedShort();
if (len == 32767) {
  len = readLongLong();
}

===== 8/16/63 =====

> Use 8 bits in the frame header (so one fewer reserved bit available), and
if the value is 0-253, that is the length.  If the value is 254, then the
next 2 bytes are a 16-bit length.  If the value is 255, the next 8 bytes are
a 63-bit length (the high bit must be zero).

long long len = readByte();

> switch (len) {

>   case 254:

>     len = readUnsignedShort();

>     break;

>   case 255:

>     len = readLongLong();

>     break;

> }

==== 7/63 =====

> Use 7 bits in the frame header, and if the value is 0-126, that is the
length.  If the value is 127, the next 8 bytes are a 63-bit length (the high
bit must be zero).

long long len = readByte() & 127;

> if (len == 127) {

>   len = readLongLong();

> }

===== n*7 =====

> Use 8 bits in the frame header (assigning RSV2 in the most recent proposal
to be part of the length field).  If the high bit is set in that byte, shift
the current length seven bits and read the next byte.  Leading 0x80 bytes
are disallowed, and at most 9 length bytes may be included

int byte = readByte();

> if (byte == 0x80) // fail

> long long len = byte;

> for (int i = 1; (byte & 0x80) && i < 9; ++i) {

>   byte = readByte();

>   len = (len << 7) | (byte & 0x7f);

> }

> if (byte & 0x80) // fail

=====  hyperoptimized 8/16/32/63 =====
This is a more complicated proposal designed to optimize the number of
frames which could fit into a 3G FACH packet (~128-256 bytes depending on
carrier settings), and it is hard to describe succinctly.  Basically, use a
1-byte length for lengths where you are most at risk for crossing the FACH
boundary, and use longer lengths for other values (including shorter ones
where you are sure to have plenty of room for the header).  I also don't
have a good name for it.

long long len = readByte();
switch (len) {
  case 0:
     len = readUnsignedShort();
     if (len >= 117) {
       len += 373-117;
     }
     break;
  case 1:
     len = readUnsignedLong() + 65792;
     break;
  case 2:
     len = readLongLong() + 4295033088;
     // overflow checks?
     break;
  // 3-255 encodes lengths of 120-372.
  default:
     len += 117;
     break;
}

If I have left out or misrepresented any proposals here, feel free to post a
correction.

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

---

From: John Tamplin <[email-masked]>
Date: Wed, 25 Aug 2010 18:25:58 -0400

So these are my personal opinions about the pros and cons of each suggested
format.  Note that I will remove the 7/63 and n*7 options from further
consideration, because they had numerous vocal opponents on the list and
have many more negative votes than positive ones in Moderator.

Background info:

   - Sample traces from Wave and GWT Quake indicate that once compression is
   enabled, more than 98% of all messages will fit in ~126 bytes.  GWT Quake
   payloads were highly compressible even though it was sending binary data
   (largely consisting of floats, though encoded as UTF8 characters since v75
   didn't have binary support), and it seems likely that apps envisioned using
   WebSocket are likely to have highly compressible payloads, such as chat
   messages, tweets, JSON serialized objects, etc. so I would expect the
   compression ratio to remain very high once compression is supported.
   - 3G wireless networks have a low power FACH mode which can only transmit
   from 128-256 bytes (depending on carrier settings), including the TCP/IP
   header.  Sending larger packets costs both power and time to bring the radio
   up to the higher level.
   - We have discussed two methods of extension and seem pretty well divided
   between the choices: 1) allocate an opcode to new extensions, which would
   then carry the data in the payload before the "next layer" opcode and its
   payload, or 2) add extension metadata outside of the payload, with a bit in
   the header to indicate its presence.  In the case of #1, we would likely
   want to add additional bits to the opcode field.  We might also choose to do
   a mix of #1 and #2, using opcodes for mandatory extensions and metadata for
   optional ones.  We have also discussed many options for compression support
   -- one of them was per-frame compression, which would likely need a
   per-frame bit to be efficient.  So, it is likely we will allocate at least 2
   reserved bits with things that are already under discussion, not considering
   things we haven't thought of.  Certainly many of the future needs we come up
   with could fit into whatever extension scheme we settle on, but there may be
   things where that is too expensive as well.  Thus, I don't personally
   consider any option that leaves us less than two reserved bits in the header
   as acceptable.  That means that unless we decide not to include the complete
   message length in the base protocol, the 8/16/32/63, 8/63, and 8/16/63
   options will require allocating an extra byte to the header (and in turn
   give us additional reserved bits over the other options, but at the cost of
   increasing the minimum frame size).

If we assume that existing packet traces of Wave and GWT Quake are likely to
be representative of most WebSocket applications, and we assume that mobile
networks will grow in importance, I think that means we need to worry more
about how to encode short messages such that they stay short.  For example,
15/63 will save a byte compared to 7/16/63 in the case of frame lengths
above 125, but if that is less than 2% of the frames and it costs a byte
over the 98% of frames under 126 bytes, then we have actually increased the
average frame by 0.96 bytes rather than made any savings.  Certainly, we
don't know that will hold, and if it turns out that average frame size is
higher it may in fact be a good idea.

Personally, the hyperoptimized 8/16/63 option seems too complex for minimal
gain and easy to get wrong to me so I would object to it, though I do
appreciate the ability to keep larger frames under the FACH threshold and
could perhaps be persuaded if others liked it.  If we think the traces are
representative, the ability to get larger frames in the FACH threshold isn't
an important advantage over 7/16/63, as it will only affect a very small
portion of the frames.

I still like the 7/16/63 option - it seems a nice mix of keeping the base
header small (2 bytes for frames under 126 bytes), while still preserving
reasonable efficiency for intermediate size frames (such as if a sender is
using a fixed buffer size and writing a frame when it fills).

The 8/16/32/63 option doesn't waste bits for larger lengths, but it does
increase the size of small frames by one byte.  I don't really feel that the
32-bit length option buys much, since if you are sending 64k of data the
extra 4 bytes used to send a 63-bit length instead of 32-bits is negligible.
 It does provide extra reserved bits, and a number of people seemed to
prefer it, so that would be my second favorite option since the extra
reserved bits give us more expansion options.

15/63 uses the same number of bytes for small frames as 8/16/32/63, but
doesn't provide the intermediate length options nor the extra reserved bits
that it does.

Next there are the 8/63 and 8/16/63 options, which to me don't give
sufficient benefit over the 7/*/63 options to justify allocating a precious
reserved bit to them.

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 26 Aug 2010 14:24:33 +1000

John,

thanks for the great summary. However, I think it would be good to
revisit the reasons from the rejection of n*7, as I think that many
opposed to it may re-evaluate now that it is clear that there is not a
simple widely accepted replacement (eg 16 ).

Personally I would be happy with  8/63, 7/63, n*7 (or 16), with no
strong preference between them.

cheers

---

From: John Tamplin <[email-masked]>
Date: Thu, 26 Aug 2010 00:35:58 -0400

> simple widely accepted replacement (eg 16 ).

My objection to it is that it is more complicated (in writing the sample
code I had to go over it several times before I was convinced it was
correct, where the others are all immediately obvious), it has error states
that have to be checked for, and the intermediate lengths are of negligible
value.

> strong preference between them.

It seems there were objections raised by a vocal minority about not having
any intermediate length between 1 and 8 bytes, so I am not sure how much
support there is for [78]/63 (while 8/63 isn't too bad on the Moderator
poll, it looks like I am the only one that voted for 7/63 with 7 voting
against).

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 26 Aug 2010 14:55:41 +1000

John,

oh there was a poll? sorry I missed that in all the noise (plus a vacation).
So ignore my previous message as more noise, as I really don't mind
which one we use, so long as we pick one soon and move on.

> poll, it looks like I am the only one that voted for 7/63 with 7 voting

I'll add my "vote" to 8/63 then.

cheers

---

From: "Brian Smith" <[email-masked]>
Date: Thu, 26 Aug 2010 10:38:04 -0500

John Tamplin wrote:
> • Sample traces from Wave and GWT Quake indicate that once
> compression is enabled, more than 98% of all messages will fit
> in ~126 bytes.  GWT Quake payloads were highly compressible
> even though it was sending binary data (largely consisting of
> floats, though encoded as UTF8 characters since v75 didn't have
> binary support), and it seems likely that apps envisioned using
> WebSocket are likely to have highly compressible payloads,
> such as chat messages, tweets, JSON serialized objects, etc.
> so I would expect the compression ratio to remain very high
> once compression is supported.

I think compression is one thing that cannot be efficiently encoded if it is tacked on later.

After decompression, these frames are much larger than 126 bytes, right? Probably larger than 255. Note that the length of the *compressed* data is not what the people demanding a length header were asking for. They are asking for the length of the *uncompressed* data so they can allocate the right amount of memory for their DOMString. (Decompression buffers are always going to be the same size, for all practical purposes, and zlib works more efficiently when you know the length of the decompressed data beforehand.) Consequently, tacking the compressed length onto the front of a compressed frame is just wasting space. 

Please consider the following change, which can be applied to any of the schemes presented:

Instead of interpreting the length field as an unsigned integer that represents the *compressed* length of a frame, interpret the length field as a signed integer that represents the difference of the current frame's *decompressed* length from the *decompressed* length of the previous frame of the same type. (The length difference field X of the first frame of each type would be added to 255.)
 
Note that almost every data format lets you pad data to a fixed length. For example, if you have JSON data that takes less than 128 bytes, you can just append spaces to it to make it 128 bytes long. Consequently, an application cares deeply about the compactness of the (compressed) data can ensure that nearly every frame is the same length--in other words, almost every application can ensure that almost every length difference field is 0 for almost every frame. Accordingly, it makes sense to optimize that.

Consider the following:

1. Encode the frame type in six bits.
2. Encode the compressed/decompressed flag in 1 bit, 1 = DELFATE, 0 = uncompressed.
3. Encode the "length is the same" flag in 1 bit. If the "length is the same" flag is 1, then no explicit length field is sent. Otherwise, the length difference field is sent as described above, using the working group's favorite encoding for (now signed) numbers that could be astronomically large but are almost always very small. (I would say that the complicated encoding I gave before is no longer necessary so I suggest excluding that from consideration.)

Then, the vast majority of frames headers will fit in one byte and applications that care about the FACH-DCH will have even more capacity to put to good use (e.g. authentication tags).

Regards,
Brian

---

From: John Tamplin <[email-masked]>
Date: Thu, 26 Aug 2010 11:56:53 -0400

> I think compression is one thing that cannot be efficiently encoded if it

Why so?  We have reserved bits in the frame which can be used for per-frame
compression (negotiating the algorithm details in the handshake).  We could
also compress everything in the stream without using that (though we risk
the expense of trying to compress incompressible data and the damage that
would do to the decompression dictionary).

> After decompression, these frames are much larger than 126 bytes, right?
> Probably larger than 255.

I have given the numbers before, but a not insignificant percentage of the
frames are under 126 even before compression (78% Wave S->C, 1.2% Wave C->S,
36% GWT Quake S->C, 99% GWT Quake C->S).

> Note that the length of the *compressed* data is not what the people
> demanding a length header were asking for. They are asking for the length of
> the *uncompressed* data so they can allocate the right amount of memory for
> their DOMString. (Decompression buffers are always going to be the same
> size, for all practical purposes, and zlib works more efficiently when you
> know the length of the decompressed data beforehand.) Consequently, tacking
> the compressed length onto the front of a compressed frame is just wasting
> space.
>

Good point.  So, if we keep the CML it would be defined as the length of the
top-level message that was passed to the WebSocket layer.  So, that would
make it useful on single-frame messages if they are compressed.  An
intermediary that fragments a compressed message would simply pass along any
CML that was already there, and if the intermediary did the compression it
would introduce the CML containing the pre-compression size.

> Instead of interpreting the length field as an unsigned integer that
> represents the *compressed* length of a frame, interpret the length field as
> a signed integer that represents the difference of the current frame's
> *decompressed* length from the *decompressed* length of the previous frame
> of the same type. (The length difference field X of the first frame of each
> type would be added to 255.)
>

Given the debates we had about even having compression in the base protocol,
I do not think we can define the frame length to be in terms of compression
at all. Also, having to remember state across messages seems problematic.  A
stream of frames can only be interpreted if you saw them from the beginning.
 Imagine a corporate proxy that inspects the WebSocket frames for bad
things, and is rebooted.  How can it even begin to interpret the data it
sees if all frames are delta encoded?

> Note that almost every data format lets you pad data to a fixed length. For
> example, if you have JSON data that takes less than 128 bytes, you can just
> append spaces to it to make it 128 bytes long. Consequently, an application
> cares deeply about the compactness of the (compressed) data can ensure that
> nearly every frame is the same length--in other words, almost every
> application can ensure that almost every length difference field is 0 for
> almost every frame. Accordingly, it makes sense to optimize that.
>

The application isn't the one that knows what is being added to the frames
-- if the user agent has negotiated some extension that adds variable data
to the frame, there is no way the application can know the right padding
level.

Besides, if I add spaces to my frame to avoid sending the length byte(s),
how have I actually saved any bytes?  If it is under 128 bytes anyway, even
one padding byte costs as much as just sending the length.

---

From: "Brian Smith" <[email-masked]>
Date: Thu, 26 Aug 2010 12:46:38 -0500

John Tamplin wrote:
> Why so?  We have reserved bits in the frame which can be
> used for per-frame compression (negotiating the algorithm
> details in the handshake).  We could also compress everything
> in the stream without using that (though we risk the expense
> of trying to compress incompressible data and the damage
> that would do to the decompression dictionary).

...

> So, if we keep the CML it would be defined as the length
> of the top-level message that was passed to the WebSocket
> layer.  So, that would make it useful on single-frame messages
> if they are compressed.  An intermediary that fragments a
> compressed message would simply pass along any CML that
> was already there, and if the intermediary did the compression
> it would introduce the CML containing the pre-compression size.

Adding the CML to a single-frame message just because it is compressed is counterproductive to the compression. If the CML is sent, it might as well replace the frame length. The frame length is unimportant when you have the CML, unless you have multiplexing. If compression, fragmentation, and multiplexing are all added later then the frame header is going to end up stealing space from the application data unless fundamental aspects of the frame header encoding change when these features are added. That is what I meant by my statement quoted above.
 
> > Instead of interpreting the length field as an unsigned integer
> > that represents the *compressed* length of a frame, interpret
> > the length field as a signed integer that represents the difference
> > of the current frame's *decompressed* length from the
> > *decompressed* length of the previous frame of the same type.
> > (The length difference field X of the first frame of each type
> > would be added to 255.)
>
> Given the debates we had about even having compression in the
> base protocol, I do not think we can define the frame length to be
> in terms of compression at all.

If the protocol doesn't end up having compression, then just remove "decompressed" from the description. If/when compression is added, add "decompressed" back in.

> Also, having to remember state across messages seems problematic.
> A stream of frames can only be interpreted if you saw them from the
> beginning.  Imagine a corporate proxy that inspects the WebSocket
> frames for bad things, and is rebooted.  How can it even begin to
> interpret the data it sees if all frames are delta encoded?

This is no different than the problems that IP compression, TLS, or ROHC compression cause the proxy. And, WebSockets will cause it to have the same same problem if/when compression is added.

> > The application isn't the one that knows what is being added to
> > the frames -- if the user agent has negotiated some extension
> > that adds variable data to the frame, there is no way the
> > application can know the right padding level.

It can just ask the UA how much overhead there will be, it can ask the UA to use a specific byte (usually 0x20) as a padding byte, or it can just not worry about the optimization. UAs can't be adding surprising things anyway if the application has any chance of staying in the FACH mode on a mobile device.

> how have I actually saved any bytes?  If it is under 128 bytes anyway,
> even one padding byte costs as much as just sending the length.

An application that cares about the FACH->DCH boundary could avoid ever sending a length, so instead of being able to send up to 126 bytes per frame, it can send up to 127. This is as big as the gain from using a one-byte length encoding for small packets instead of a two-byte length encoding. Compared to the 64-bit fixed length encoding, it saves up to 8 bytes, whereas the best alternatives presented so far can never save more than 7.

Cheers,
Brian

---

From: John Tamplin <[email-masked]>
Date: Thu, 26 Aug 2010 14:04:25 -0400

On Thu, Aug 26, 2010 at 1:46 PM, Brian Smith <[email-masked]> wrote:

> Adding the CML to a single-frame message just because it is compressed is
> counterproductive to the compression. If the CML is sent, it might as well
> replace the frame length. The frame length is unimportant when you have the
> CML, unless you have multiplexing. If compression, fragmentation, and
> multiplexing are all added later then the frame header is going to end up
> stealing space from the application data unless fundamental aspects of the
> frame header encoding change when these features are added. That is what I
> meant by my statement quoted above.
>

Fragmentation is not added later -- it is listed in the requirements
document, and all proposals have had some form of fragmentation support.  In
the VII proposal I made, that fragmentation support was in the form of a
single MORE bit saying this was not the final frame of a message, and
support for the complete message length which could be supplied on a
fragmented message so you still know the overall message length.

The message length is not the same as the frame length.  If you have the
message length but not the frame length, you can't tell where the next frame
starts.

The simple approach for multiplexing would be to simply use the normal
framing for the logical channel frame (not repeating the length but getting
it from that frame's header), in which case yes, keeping the frame header
small is that much more important.  It would be possible, however, for the
mux frame to define a different way of encoding that if it became necessary.

> An application that cares about the FACH->DCH boundary could avoid ever
> sending a length, so instead of being able to send up to 126 bytes per
> frame, it can send up to 127. This is as big as the gain from using a
> one-byte length encoding for small packets instead of a two-byte length
> encoding. Compared to the 64-bit fixed length encoding, it saves up to 8
> bytes, whereas the best alternatives presented so far can never save more
> than 7.
>

Bytes still aren't free even if they are under the FACH threshold.  If I am
sending lots of 1-2-byte messages (perhaps keystrokes), having to send them
as 126 bytes with padding is going to waste tons of bandwidth.

---

From: Dave Cridland <[email-masked]>
Date: Thu, 26 Aug 2010 20:19:25 +0100

On Thu Aug 26 18:46:38 2010, Brian Smith wrote:
> An application that cares about the FACH->DCH boundary could avoid  
> ever sending a length, so instead of being able to send up to 126  
> bytes per frame, it can send up to 127. This is as big as the gain  
> from using a one-byte length encoding for small packets instead of  
> a two-byte length encoding. Compared to the 64-bit fixed length  
> encoding, it saves up to 8 bytes, whereas the best alternatives  
> presented so far can never save more than 7.

Except that it's not pure packet size as such, but queue length, and  
it's not entirely clear to me that the network doesn't raise you to  
DCH just for using FACH a lot. Or because it's Tuesday, come to that  
- it's not clear to me that the network actually needs a good reason  
at all.

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: "Brian Smith" <[email-masked]>
Date: Thu, 26 Aug 2010 14:33:41 -0500

John Tamplin wrote:
> The message length is not the same as the frame length. 
> If you have the message length but not the frame length,
> you can't tell where the next frame starts.

Based on what's been agreed upon so far, the frame length isn't important for anything, so that's OK. 
 
> Bytes still aren't free even if they are under the FACH
> threshold.  If I am sending lots of 1-2-byte messages
> (perhaps keystrokes), having to send them as 126 bytes
> with padding is going to waste tons of bandwidth.

You wouldn't have to pad them to 126 bytes. Or, you could pad some and not others. Or, you could avoid using the "same length" bit completely.

Even if that specific optimization isn't a win, I do think the main part of the idea (differential encoding of the lengths) would be useful. 

My main point is that frame header can be compressed much further using techniques similar to the ones used for IP header compression without much additional complexity, so such techniques should be investigated.

Regards,
Brian

---

From: John Tamplin <[email-masked]>
Date: Thu, 26 Aug 2010 16:04:46 -0400

> for anything, so that's OK.

I am assuming we must be talking about different things, because otherwise I
don't see how what you are suggesting can work.

Imagine we have a 100-byte message.  It gets sent as two 50-byte frames.
 So, on the wire it looks like this:

      hdr(frameLen=50,more=1) message[0-49]    hdr(frameLen=50 more=0)
message[50-99]

if you send the message length instead of the frame length, I don't see how
you are able to tell when the payload from the first frame ends and where
the header for the second frame starts.

My main point is that frame header can be compressed much further using
> techniques similar to the ones used for IP header compression without much
> additional complexity, so such techniques should be investigated.
>

For small frames, most proposals have a 2-byte header, so there isn't much
room the header can be compressed even theoretically.  For large frames,
saving a byte or two is irrelevant.

---

From: "Shelby Moore" <[email-masked]>
Date: Thu, 26 Aug 2010 20:19:03 -0400

> I think compression is one thing that cannot be efficiently encoded if it

Incorrect. below...

> Probably larger than 255. Note that the length of the *compressed* data is
> not what the people demanding a length header were asking for. They are
> asking for the length of the *uncompressed* data so they can allocate the
> right amount of memory for their DOMString. (Decompression buffers are
> always going to be the same size, for all practical purposes, and zlib
> works more efficiently when you know the length of the decompressed data
> beforehand.) Consequently, tacking the compressed length onto the front of
> a compressed frame is just wasting space.

That is because you are trying to conflate the framing/fragmentation and
the data layer.  Put the uncompressed size as a prefix in your data, and
read it back out on the other side when you read your data.  Here is how
it should work if we do it correctly:

http://www.ietf.org/mail-archive/web/hybi/current/msg03729.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03722.html

---

From: "Brian Smith" <[email-masked]>
Date: Fri, 27 Aug 2010 09:05:46 -0500

John Tamplin wrote:
> Brian Smith <[email-masked]> wrote:
> > John Tamplin wrote:
> > Based on what's been agreed upon so far, the frame length
> > isn't important for anything, so that's OK.
>
> I am assuming we must be talking about different things,
> because otherwise I don't see how what you are suggesting
> can work.

> Imagine we have a 100-byte message.  It gets sent as two
> 50-byte frames.  So, on the wire it looks like this:
>
 >    hdr(frameLen=50,more=1) message[0-49]    
>     hdr(frameLen=50 more=0) message[50-99]
>
> if you send the message length instead of the frame length,
> I don't see how you are able to tell when the payload from
> the first frame ends and where the header for the second
> frame starts.

If the receiver is given the message length instead of the frame length, in the first frame, then the "more" flag is not needed. Since there is no multiplexing, the next frame is guaranteed to be the same type and to be a continuation of the first frame. Consequently, there's nothing about the second frame that the receiver can't infer from the first frame except the frame length, which is unimportant, so the second frame doesn't need a header at all. Consequently, the frames can be compressed to:

    hdr(messageLen=100) message[0-49]    
    message[50-99]

In other words, based on what's agreed on so far, there's no need for every frame to have its own header and really there's no need for the receiver to know about fragmentation if it can process messages in a streaming or chunked fashion.  That is, the receiver doesn't need to be able to distinguish the above from:

    hdr(messageLen=100) message[0-24]
    message[25-49]
    message[50-74]
    message[75-99]

or:

    hdr(messageLen=100) message[0-99]

> For small frames, most proposals have a 2-byte header,
> so there isn't much room the header can be compressed
> even theoretically.  For large frames, saving a byte or
> two is irrelevant.

Yes, but this ignores all the metadata that's being pushed outside the header or which is otherwise being omitted from discussion in order to make the framing seem simple in the hopes of ending the debate. When more features are added that metadata has to go somewhere.

Cheers,
Brian

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 10:55:50 -0400

>>     hdr(frameLen=50 more=0) message[50-99]

There is no need for the 'more' bit, as that conflates the frame and
message layers unnecessarily with dire implications. The 'message' layer
needs to insert a content-length of 100 in the first frame, or just read
until it encounters an "EOM" marker.

See all my posts here:

http://www.ietf.org/mail-archive/web/hybi/current/maillist.html#03770
http://www.ietf.org/mail-archive/web/hybi/current/msg03770.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03769.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03768.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03767.html

>> the first frame ends and where the header for the second

See non-conflated solution above.

> If the receiver is given the message length instead of the frame length,

It is not 'either or'.  There are 2 receivers.  The lower frame layer is
one receiver, it reads the frame sizes.  The higher messaging
(application, aka data) layer reads its sizes.

If you conflate those two layers and sizes, assuming you want full
generality in your messaging layer, you will never get a reasonable
(simple and non-brittle) multiplexing into this.

You may be able to conflate the two layers and make the messaging layer
brittle for future expansion.  As well, you will make it brittle for
compositing on lower layers, i.e. you wouldn't be able to able to replace
the framing layer and/or the TCP layer easily.

> in the first frame, then the "more" flag is not needed. Since there is no
> multiplexing, the next frame is guaranteed to be the same type and to be a
> continuation of the first frame. Consequently, there's nothing about the
> second frame that the receiver can't infer from the first frame except the
> frame length, which is unimportant, so the second frame doesn't need a
> header at all. Consequently, the frames can be compressed to:
>

You are stuck in that 'either or' conflation matrix.  You are bouncing
between two different ways to conflate the two layers, both of which are
not going to satisfy everyone here, because conflation never does.

John says to put a more bit in order to conflate (which kills out-of-order
multiplexing, and statelessness requirement, which has many dire
implications).  You say to put the message size in the first frame to
conflate (which kills framing).

[snip]

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 11:17:03 -0400

Additionally, the 'more' (CMLP) bit is not more efficient than putting the
message size in the message layer.

Because the CMLP bit still requires 8 extra bytes for the message size. 
Might as well just put it in the message itself, and then you don't
conflate the two layer.  There is no reason the framing layer needs to
know the message size (it is meaningless to the framing layer and useless
and harmful as well).

Also by not conflating it, we can actually make an optimization that makes
it even more efficient for small messages:

http://www.ietf.org/mail-archive/web/hybi/current/msg03769.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03748.html

I am very confident that the orthogonal frame with blackbox payload, and
orthogonal message layers is optimal for us.  We will never get concensus
without it.

> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>
>

---

From: John Tamplin <[email-masked]>
Date: Fri, 27 Aug 2010 11:19:13 -0400

>    hdr(messageLen=100) message[0-99]

Ok, I see what you are suggesting now -- basically take advantage of
the fact that we are running over TCP and let it take care of the
details while making receivers simpler.  Some extensions such as
multiplexing will need to add more explicit framing boundaries, but
that can be defined in those frames.

Combining this with a variant of Greg's suggested framing:
 * 0 or more metadata opcodes
    * 1 bit - 1 indicating a metadata opcode
    * 7 bits - metadata opcode
    * metadata length (encoding TBD)
    * n bytes - metadata
 * 1 bit - 0 indicating leaf opcode
 * 7 bits - opcode
 * length (encoding TBD, perhaps 8/16/63)
 * length bytes - payload data interpreted according to leaf opcode,
noting that it may be sent in multiple "fragments" on the wire

[This is just a renaming and slight rearrangement of Greg's proposal,
you would likely just define the metadata opcodes to all have the high
bit set].

So a simple message would look like this, and could be fragmented arbitrarily:
   - hdr(metadata=[mime-type="text/plain", ...] opcode=text,
msglen=100) "100 bytes of UTF8 text"

A compression extension giving the above frame might look like:
   - hdr(metadata=[uncompressed-length-bytes=100,
mime-type="text/plain", ...] opcode=compressed, msglen=14)
orig-opcode=text, [13 compressed bytes]

A multiplexed message would need to have explicit framing, but that
would be up to the mux extension:
   - hdr(opcode=mux, msglen=n)
       - ctl=0 stream_id=1 len=30
payload=[hdr(metadata=[mime-type="text/plain", ...], opcode=text,
msglen=100) "first 30-hdr bytes of UTF8 text"]
       - ctl=0 stream_id=2 len=14 payload=["last 14 bytes of a
previous message on this stream"]
       - ctl=1 stream_id=3 control=flow-control window-size=32k

The demuxer could simply write the pieces it received on each stream
to the outbound connection for that stream as it received it, no need
to worry about fragmentation.  A mux-capable endpoint would deliver
the fragments to a streaming API or buffer up the entire message for
delivery to a message-based API just as it would in the non-mux case.

The one downside is there is no way to interrupt a long message and
insert some control frame (such as responding to a ping it just
received, a hypothetical flow-control extension [though I suspect that
would likely be only between muxes and so could be part of the mux
extension], etc).  However, that may be worth giving up for the
advantages this approach brings.

---

From: Ian Fette (イアンフェッティ) <[email-masked]>
Date: Fri, 27 Aug 2010 09:13:41 -0700

On Fri, Aug 27, 2010 at 8:19 AM, John Tamplin <[email-masked]> wrote:

> > In other words, based on what's agreed on so far, there's no need for
> every frame to have its own header and really there's no need for the
> receiver to know about fragmentation if it can process messages in a
> streaming or chunked fashion.  That is, the receiver doesn't need to be able
> to distinguish the above from:
> >

Editor hat off, personal hat on:

Nit: This proposal is really hard to read and understand.

This seems way more complex for intermediaries and endpoints with e.g.
multiplexing. I personally don't see why we keep vacillating, your previous
proposal looked much better. I am also very worried about punting
fragmentation to an extension, as we have debated both on this list and at
the face to face, intermediaries being ignorant of fragmentation will cause
all sorts of problems. The previous proposal had very low overhead, this
adds significant complexity and loss of clarity for very little benefit.

-Ian

---

From: John Tamplin <[email-masked]>
Date: Fri, 27 Aug 2010 12:26:18 -0400

> advantages this approach brings.

Actually, Roberto pointed out the fatal flaw I had forgotten -- you
can't send a dynamically generated message without buffering all of it
up front so you know the message length.

---

From: Scott Ferguson <[email-masked]>
Date: Fri, 27 Aug 2010 09:37:09 -0700

> that can be defined in those frames.

That's missing the whole point of fragmenting. Fragmenting is needed 
when you don't know the message length. Let me repeat that because 
people seem to be confused no matter how many times it's explained:

  Fragmenting is needed when you DON'T KNOW THE MESSAGE LENGTH A PRIORI.

When you know the message length, you don't need fragmenting. Multiple 
write() calls for the payload of a frame have nothing to do with 
fragmenting.

Omniscient senders don't need to fragment.

Brian's suggestion boils down to: assume senders always know the message 
length of the payload before serializing. With that assumption, you 
don't need fragmenting. Well, duh.

-- Scott

---

From: Scott Ferguson <[email-masked]>
Date: Fri, 27 Aug 2010 09:44:06 -0700

> Nit: This proposal is really hard to read and understand.

+1

> multiplexing. I personally don't see why we keep vacillating, your 
> previous proposal looked much better. I am also very worried about 
> punting fragmentation to an extension, as we have debated both on this 
> list and at the face to face, intermediaries being ignorant of 
> fragmentation will cause all sorts of problems. The previous proposal 
> had very low overhead, this adds significant complexity and loss of 
> clarity for very little benefit.

+1

-- Scott
>     [email-masked] <mailto:[email-masked]>
> ------------------------------------------------------------------------
>

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 12:44:41 -0400

> I am also very worried about punting
> all sorts of problems.

It is unreasonable (or impossible) to make fragmentation an extension:

http://www.ietf.org/mail-archive/web/hybi/current/msg03780.html

Solution for potentially making framing (not fragmentation) negotiable
depends on the framing layer and messaging layer to be orthogonal (as I
have proposed):

http://www.ietf.org/mail-archive/web/hybi/current/msg03782.html

However, I am not arguing that we must support optional framing now. I am
just saying that option will be available to us (if we don't conflate the
layers, and that is by far not the most important reason not to conflate
them).

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 27 Aug 2010 09:46:33 -0700

On Fri, Aug 27, 2010 at 9:37 AM, Scott Ferguson <[email-masked]> wrote:

> That's missing the whole point of fragmenting. Fragmenting is needed when
> you don't know the message length. Let me repeat that because people seem to
> be confused no matter how many times it's explained:
>

This.

In addition, fragmentation in WebSockets isn't like fragmentation in IP
where
the purpose is accomodating (unknown) MTU sizes by intermediaries. TCP
already
takes care of that. In this case, fragmentation is primarily about streamed
encoding
of data of unknown length, just like HTTP chunked encoding.

-Ekr

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 12:53:25 -0400

>> when

That is not the only reason we need fragmentation.  We also need it to
scale the network with multiplexing extension.  If fragmenting is not in
the frame, then multiplexing will have to go in between the frame layer
and TCP, which will be very messy.

>> When you know the message length, you don't need fragmenting.

More precisely, then you don't need framing, or you mean you can conflate
the framing and messaging layer in that case.

>> Multiple

Exactly what I mean above.

> of data of unknown length, just like HTTP chunked encoding.

Exactly!  That is why you shouldn't put a stateful 'more' (CMLP) bit in
the framing layer:

http://www.ietf.org/mail-archive/web/hybi/current/msg03775.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03776.html

---

From: "Brian Smith" <[email-masked]>
Date: Fri, 27 Aug 2010 11:58:39 -0500

Scott Ferguson wrote:
> length of the payload before serializing. With that assumption, you don't need
> fragmenting. Well, duh.

You don't need a whole frame header to describe a chunk of a message unless you also have multiplexing of some kind.
For example, you could say that messageLen==0 means that the contents of the message consist of multiple chunks of the form [chunk-length][message of chunk-length bytes], ending when chunk-length==0. So, a zero-length messages would look like [type][0][0]. That's why I said I don't think features like multiplexing and compression can be added on later without changing the frame encoding. IMO, it doesn't make sense to try to design the frame header without also having a design for multiplexing (and compression) at least.

Regards,
Brian

---

From: "Brian Smith" <[email-masked]>
Date: Fri, 27 Aug 2010 12:02:36 -0500

> msglen=100) "100 bytes of UTF8 text"

This is why I think compression has to be considered fundamental to the design instead of an extension. Otherwise, you cannot compress these larger pieces of extension metadata like the mime type.

Regards,
Brian

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 13:04:08 -0400

> You don't need a whole frame header to describe a chunk of a message
> unless you also have multiplexing of some kind.

Correct you don't need framing then:

> For example, you could say that messageLen==0 means that the contents of
> the message consist of multiple chunks of the form [chunk-length][message
> of chunk-length bytes], ending when chunk-length==0. So, a zero-length
> messages would look like [type][0][0]. That's why I said I don't think
> features like multiplexing and compression can be added on later without
> changing the frame encoding.

Here is why that is a wrong assumption:

http://www.ietf.org/mail-archive/web/hybi/current/msg03787.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03785.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03780.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03778.html

> IMO, it doesn't make sense to try to design
> the frame header without also having a design for multiplexing (and
> compression) at least.
>
> Regards,
> Brian
>

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 13:06:44 -0400

> This is why I think compression has to be considered fundamental to the
> design instead of an extension. Otherwise, you cannot compress these
> larger pieces of extension metadata like the mime type.

Incorrect.

If the message layer is orthogonal to the frame layer, then the
compression has nothing to do with how the compressed message is broken
into fragments along the way.

When a message receiver wants to decompress, it calls the framing layer to
get the data.  And goes about decompressing.

---

From: John Tamplin <[email-masked]>
Date: Fri, 27 Aug 2010 13:07:13 -0400

On Fri, Aug 27, 2010 at 1:02 PM, Brian Smith <[email-masked]> wrote:

> design instead of an extension. Otherwise, you cannot compress these larger
> pieces of extension metadata like the mime type.
>

I think if we really want to compress parts of the framing, we might as well
just compress the entire stream in which case no part of compression is
present in each frame.  Having a compression extension (or a bit indicating
a frame is compressed) is useful only to *avoid* having to compress things
like the framing which likely will pollute the compression dictionary to
little benefit, or if you want to be able to compress some frames (ie, text)
but not ones that don't compress well.

The primary reason the current proposal doesn't try and address compression
is because there seems to be wide differences of opinion between the utility
of per-stream and per-frame compression, or even having it at all.

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 13:12:34 -0400

>> larger

Serial compression at framing layer is silly.  It would kill much of the
performance benefits of multiplexing, as you would have to decompress
everything just to get the next frame. And the frame header is already
compressed, what is benefit of compressing it? (they only thing in the
frame layer is a header and blackbox payload)  There are probably many
other reasons it is silly.

Tangent: If you want security, run WebSocket on top of TLS.

---

From: "Brian Smith" <[email-masked]>
Date: Fri, 27 Aug 2010 12:30:38 -0500

John Tamplin wrote:
> The primary reason the current proposal doesn't try and
> address compression is because there seems to be wide
> differences of opinion between the utility of per-stream
> and per-frame compression, or even having it at all.

If you have per-stream compression, then the length encoding given in the latest draft (fixed 64-bit integer) is probably going to beat all the specialized encodings that are being argued about in almost every instance where it is important, because you can compress

     type-byte 0x00 0x00 0x00 0x0 0x00 0x00 0x00 length-byte

down to a fraction of a single byte. So, I think the idea of deferring the debate on compression until the frame header encoding is resolved is counterproductive.

I understand the desire to have more fine-grained control over how sections of the stream are compressed, but instead of debating mechanisms for doing that for every networking protocol, IMO the people concerned should work on extending the DEFLATE format to handle these use cases. For the need you presented (per-fragment compression control with low overhead for uncompressed blocks and an way to prevent uncompressible blocks from affecting the compression context), such an extension to DEFLATE would be absurdly simple to specify and implement (in zlib, at least). Of course it would take a long time to be widely deployed for use in all protocols, but having a way to fall back to the current standard DEFLATE and/or no compression at all would be good enough and probably about what you'll end up with anyway if an improved DEFLATE format wasn't pursued.

Regards,
Brian

---

From: John Tamplin <[email-masked]>
Date: Fri, 27 Aug 2010 13:34:20 -0400

On Fri, Aug 27, 2010 at 1:30 PM, Brian Smith <[email-masked]> wrote:

> down to a fraction of a single byte. So, I think the idea of deferring the
> debate on compression until the frame header encoding is resolved is
> counterproductive.
>

The basic problem is that trying to debate everything at once is
counterproductive, as we don't seem to make any progress at all.  Sure,
maybe we could get a more optimized total solution if we designed the entire
system all at once.  However, a perfect but non-existing solution loses to a
good and existing one.

Also, making compression an extension to the base spec means that those
arguing against it on complexity or code size grounds can safely stay out of
the discussion on how to implement it, confident that they don't have to
worry about ever having to support it if they don't negotiate it.

---

From: Sylvain Hellegouarch <[email-masked]>
Date: Fri, 27 Aug 2010 20:35:48 +0200

> system all at once.  However, a perfect but non-existing solution loses to a
At this stage I'm even wondering if there are many people still following
this debate at all.

- Sylvain

-- 
- Sylvain
http://www.defuze.org
http://twitter.com/lawouach

---

From: "Roy T. Fielding" <[email-masked]>
Date: Fri, 27 Aug 2010 12:06:36 -0700

On Aug 27, 2010, at 10:34 AM, John Tamplin wrote:

> The basic problem is that trying to debate everything at once is counterproductive, as we don't seem to make any progress at all.  Sure, maybe we could get a more optimized total solution if we designed the entire system all at once.  However, a perfect but non-existing solution loses to a good and existing one.

The basic problem is that people are trying to design by committee
in a standards forum, which is about as silly as it gets.

Everyone has an opinion.  Figure out what people are willing
to implement, not just opine upon, and we will start making
progress on consensus.  Once the implementations are available
for testing, then we can converge (or not).  If everyone wants
to implement their own framing syntax, then there is no need
for a standard.  If everyone is willing to adopt the most
performant of syntax, then there is no need for debate.
If there are two or three variations that have preference
(usually what happens when folks only interested in small
messages interact with those only interested in big messages),
then specify two or three protocols.

Meanwhile, stop sending iterations upon iterations of framing
proposals to the mailing list -- it has become impossible to
track the arbitrary changes being made.  Write a draft, or use
the wiki.  I'd rather have fifty variations on framing in a
single draft (which can be culled over time) than a permathread
of dislocated opinions.

Personally, I don't think any of the proposals are worth
standardizing because I don't believe reinventing TCP over
another TCP or TLS port is rational.  It will be blocked
because the interactions have poor visibility.  If you want
to avoid being blocked, the protocol needs to be constrained
in ways similar to HTTP's constrained semantics.  Otherwise,
it would make more sense to just adopt SSH and be done.

....Roy

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 15:17:18 -0400

> At this stage I'm even wondering if there are many people still following

I predicted that, because the engineering process is too difficult to do
by group in email:

http://www.ietf.org/mail-archive/web/hybi/current/msg03687.html

It is sad, because I have already provided the VERY SIMPLE solution that
addresses everyone's concerns:

http://www.ietf.org/mail-archive/web/hybi/current/msg03798.html
(read all the links contained within above please)

Yet John has just started a new thread to continue the conflation and more
"goose chasing":

http://www.ietf.org/mail-archive/web/hybi/current/msg03799.html

In order to do proper design, we must FIRST take a broad stroke view as
Jamie Lokier was doing in his discussion with me.  Then later we can come
back and optimize the nitpicking details.

John I hope you don't get offended if I say frankly, you go off on endless
details ("goose chases") and don't stay focused on the main thing that
needs to be decided FIRST.

WHICH IS:

Are we going to conflate the fragmentation-frame-header with the
message-size-header or not?

I already have shown clearly that we should not conflate.  No one has been
able to provide one reason we should, except for waiting for a response
from Jamie Lokier on this:

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 15:29:33 -0400

> another TCP or TLS port is rational.

I was also pondering this too.  Why can't the multiplexers work at the TCP
packet layer?  Can someone please answer that?

>  It will be blocked
> in ways similar to HTTP's constrained semantics.

Why is Greg's proposed message grammar (header) not visible enough?

Are you saying the fragmentation ruins visibility?

>  Otherwise,

That would just be blocked too, because the intermediaries can read and
filter it.

---

From: John Tamplin <[email-masked]>
Date: Fri, 27 Aug 2010 17:01:08 -0400

> single draft (which can be culled over time) than a permathread

As requested, I created a document of my current proposal (which
includes examples of extensibility) at:

https://docs.google.com/document/edit?id=1DIeJM-tRfJskE2-U3B7er2StU__1JqQsQg-lZC9UvY0&hl=en&authkey=CLStzbkI

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 28 Aug 2010 09:09:53 +1000

John,

great document!  I wont say a word more on framing and will support
what you have in that document.

I have some quibbles about your description of the extension data (ie
I think multi-plexing is just an sub-case of meta-data - so I'd like
to see the meta-data proposal become part of the base protocol), but
I'll shut  up on those points for now, so we can hopefully make some
progress on the framing.

cheers

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 19:44:31 -0400

> I'll shut  up on those points for now, so we can hopefully make some

What framing are you referring to?  The message framing or the
fragmentation framing?  Or it going to be the a monolith?  Does
fragmentation have anything to do with message parsing?  I don't think so.
 And it is forced to be conflated with message parsing then you will have
a broken multiplexing.  Are you listening Robert Peon?

Here is my proposal:

https://docs0.google.com/document/edit?id=1nL9VauetwYgYtpgSVRmm8_SgH7K2P15GwaGMEbAizGs&authkey=CLOirMAE#

---

From: Gabriel Montenegro <[email-masked]>
Date: Fri, 27 Aug 2010 23:50:29 +0000

Hi John,

Great summary. On the 98% of all messages being <= 126 octets, did your traces assume IPv4 or IPv6? The header now being 40 versus 20 octets, this might have an effect. Of course, given header compression (e.g., RoHC), it may not be an issue, specially as IPv6 headers are usually more compressible than v4, but I was wondering if you had a feel for any effect this will have.

Thanks,

Gabriel

From: [email-masked] [mailto:[email-masked]] On Behalf Of John Tamplin
Sent: 25 August, 2010 3:26 PM
To: Hybi
Subject: Re: [hybi] summary of frame length options

So these are my personal opinions about the pros and cons of each suggested format.  Note that I will remove the 7/63 and n*7 options from further consideration, because they had numerous vocal opponents on the list and have many more negative votes than positive ones in Moderator.

Background info:

  *   Sample traces from Wave and GWT Quake indicate that once compression is enabled, more than 98% of all messages will fit in ~126 bytes.  GWT Quake payloads were highly compressible even though it was sending binary data (largely consisting of floats, though encoded as UTF8 characters since v75 didn't have binary support), and it seems likely that apps envisioned using WebSocket are likely to have highly compressible payloads, such as chat messages, tweets, JSON serialized objects, etc. so I would expect the compression ratio to remain very high once compression is supported.
  *   3G wireless networks have a low power FACH mode which can only transmit from 128-256 bytes (depending on carrier settings), including the TCP/IP header.  Sending larger packets costs both power and time to bring the radio up to the higher level.
  *   We have discussed two methods of extension and seem pretty well divided between the choices: 1) allocate an opcode to new extensions, which would then carry the data in the payload before the "next layer" opcode and its payload, or 2) add extension metadata outside of the payload, with a bit in the header to indicate its presence.  In the case of #1, we would likely want to add additional bits to the opcode field.  We might also choose to do a mix of #1 and #2, using opcodes for mandatory extensions and metadata for optional ones.  We have also discussed many options for compression support -- one of them was per-frame compression, which would likely need a per-frame bit to be efficient.  So, it is likely we will allocate at least 2 reserved bits with things that are already under discussion, not considering things we haven't thought of.  Certainly many of the future needs we come up with could fit into whatever extension scheme we settle on, but there may be things where that is too expensive as well.  Thus, I don't personally consider any option that leaves us less than two reserved bits in the header as acceptable.  That means that unless we decide not to include the complete message length in the base protocol, the 8/16/32/63, 8/63, and 8/16/63 options will require allocating an extra byte to the header (and in turn give us additional reserved bits over the other options, but at the cost of increasing the minimum frame size).
If we assume that existing packet traces of Wave and GWT Quake are likely to be representative of most WebSocket applications, and we assume that mobile networks will grow in importance, I think that means we need to worry more about how to encode short messages such that they stay short.  For example, 15/63 will save a byte compared to 7/16/63 in the case of frame lengths above 125, but if that is less than 2% of the frames and it costs a byte over the 98% of frames under 126 bytes, then we have actually increased the average frame by 0.96 bytes rather than made any savings.  Certainly, we don't know that will hold, and if it turns out that average frame size is higher it may in fact be a good idea.

Personally, the hyperoptimized 8/16/63 option seems too complex for minimal gain and easy to get wrong to me so I would object to it, though I do appreciate the ability to keep larger frames under the FACH threshold and could perhaps be persuaded if others liked it.  If we think the traces are representative, the ability to get larger frames in the FACH threshold isn't an important advantage over 7/16/63, as it will only affect a very small portion of the frames.

I still like the 7/16/63 option - it seems a nice mix of keeping the base header small (2 bytes for frames under 126 bytes), while still preserving reasonable efficiency for intermediate size frames (such as if a sender is using a fixed buffer size and writing a frame when it fills).

The 8/16/32/63 option doesn't waste bits for larger lengths, but it does increase the size of small frames by one byte.  I don't really feel that the 32-bit length option buys much, since if you are sending 64k of data the extra 4 bytes used to send a 63-bit length instead of 32-bits is negligible.  It does provide extra reserved bits, and a number of people seemed to prefer it, so that would be my second favorite option since the extra reserved bits give us more expansion options.

15/63 uses the same number of bytes for small frames as 8/16/32/63, but doesn't provide the intermediate length options nor the extra reserved bits that it does.

Next there are the 8/63 and 8/16/63 options, which to me don't give sufficient benefit over the 7/*/63 options to justify allocating a precious reserved bit to them.

---

From: John Tamplin <[email-masked]>
Date: Fri, 27 Aug 2010 19:55:22 -0400

On Fri, Aug 27, 2010 at 7:50 PM, Gabriel Montenegro
<[email-masked]> wrote:
> Great summary. On the 98% of all messages being <= 126 octets, did your
> traces assume IPv4 or IPv6? The header now being 40 versus 20 octets, this
> might have an effect. Of course, given header compression (e.g., RoHC), it
> may not be an issue, specially as IPv6 headers are usually more compressible
> than v4, but I was wondering if you had a feel for any effect this will
> have.

That was measuring strictly WebSocket payload data, not considering
WebSocket or lower-layer framing.  The goal of my traces were
primarily to assess the impact of compression on real-world WebSocket
apps, and then later using that data to support the debate over how to
encode WebSocket payload lengths.  Certainly when considering the
overall overhead of small frames or trying to stay at FACH power
levels in 3G networks, the total packet size matters, but it doesn't
really change anything at the WebSocket layer.

When I asked the Android guys I knew, they said header compression was
not currently being done on mobile networks (that was ~6 months ago,
it might have changed since then), but I would suspect that eventually
they will implement RoHC.

---

From: "Shelby Moore" <[email-masked]>
Date: Fri, 27 Aug 2010 20:15:13 -0400

Also if you conflate the fragmentation and multiplexing with the message
data metadata and parsing, then for those agents that refuse to negotiate
fragmentation and/or multiplexing, they may be exposed a lot of complexity
in the specification (and maybe even in implementation depending how you
structure it) that they don't need to be.

Why can't you keep multiplexing and fragmenting orthogonal?  Is there some
reason the multiplexer needs to knowledge of the contents of the message? 
Afaik, the multiplexer only cares about maximizing throughput and load
(balancing) and doesn't normally care about what is inside the message
content.  If it needs to parse the message content, it can, but why force
that conflation?

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 28 Aug 2010 08:08:22 +0200

> https://docs.google.com/document/edit?id=1DIeJM-tRfJskE2-U3B7er2StU__1JqQsQg-lZC9UvY0&hl=en&authkey=CLStzbkI

This proposal looks quite good : simple enough for minimal implementations,
and flexible enough to permit later add-ons. Nice work!

BTW, when reading the description of the pong message, I realized that
we should limit the size of the payload it will return, because some
implementations will probably just memorize the ping then return it,
and will have lots of problems with huge messages. I think that we could
for instance declare that ping/pong are reserved to 7-bit lengths. But
that's just a detail for now, what's important is to get the framing right.

Regards,
Willy

---

From: Graham Klyne <[email-masked]>
Date: Mon, 30 Aug 2010 10:22:51 +0100

Roy T. Fielding wrote:
> ... Otherwise,

This feels like one of those moments of clarity:  why _not_ just do this?

Pro:
- open source client code exists
- I don't imagine it would be that much harder compared with other options 
proposed to adapt the existing code for use in existing browsers
- server-side support exists in spades
- this approach would open up the range of service access by web clients, via
SSH tunneling
- security is substantially taken care of (up to the point that websocket
applications are trusted/trustworthy)
- given an SSH-based mechanism, other existing protocols can be used to provide
extra capabilities if and as required

Possible downsides I see are:
- would the API be over-complex for simple browser applications?  I don't know,
but I imagine client-side support for tunneling might add some complexity.
- the protocol would not be accessible to applications in non-enhanced browser
environments, in the way that one can access HTTP from client-side code (but I
think this is true of the other proposals).
- would need to think some about security constraints; e.g. some analogue to 
same-origin restriction when making non-HTTP connections

Which leaves me wondering:  how simple could one make a specification for
SSH-over-HTTP?  (Or IP-over-HTTP/S [1]?)  This might provide a migration path
for applications running in non-enhanced browsers.

#g
--

[1] http://msdn.microsoft.com/en-us/library/dd358571(PROT.10).aspx

This would appear to be implemented, though presumably not open source:

[[[
The information in this specification is applicable to the following Microsoft
products:

Windows® 7 operating system

Windows Server® 2008 R2 operating system
]]]

(I also stumbled upon http://tools.ietf.org/html/rfc3093, then noticed the date
on the RFC - but maybe: many a true word spoken in jest?)

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 30 Aug 2010 21:23:25 +1000

The problem with using SSH is that sshd normally runs on port 22 and
from the sshd manual:

     sshd listens for connections from clients.  It is normally
started at boot from /etc/init/ssh.conf.
     It forks a new daemon for each incoming connection.  The forked
daemons handle key
     exchange, encryption, authentication, command execution, and data exchange.

Forking a heavy weight process for each connection is not going to scale.

Also as SSH is the primary way that we connect to our remote servers,
we are not going to be able to significantly change the way port 22 is
handled.

cheers

---

From: Alexey Melnikov <[email-masked]>
Date: Mon, 30 Aug 2010 12:28:26 +0100

Hi Greg,
I don't have any particular skin in this game, but I thought I should 
comment on this:

>we are not going to be able to significantly change the way port 22 is
I think you are confusing an implementation with a protocol. SSH 
protocol can be profiled for the desired use.

-- 
IETF Application Area Director, <http://www.ietf.org/iesg/members.html>
Internet Messaging Team Lead, <http://www.isode.com>
JID: same as my email address

---

From: John Tamplin <[email-masked]>
Date: Mon, 30 Aug 2010 10:45:31 -0400

> - server-side support exists in spades

But that server-side support has nothing to do with WebSocket.  Would
you prefer your WebSocket support to be included in sshd or your web
server?  If you implement the protocol in the web server and run over
a different port, what do you gain over using TLS?  The web servers
and browsers likely already have TLS libraries built in, but it seems
unlikely to have SSH.

The current requirements for WebSocket is to support connection
establishment via HTTP Upgrade.  Eventually I suspect there will be
additional options, such as TLS-NPN or perhaps even a dedicated
WebSocket port, and at that point we could include an SSH-based option
if that were deemed useful.

---

From: Gabriel Montenegro <[email-masked]>
Date: Mon, 30 Aug 2010 16:44:34 +0000

Worrying about small messages (and 7-bit encoding) matters most if the total packet including all headers fits within FACH limits.   BTW, RoHC has been recommended for years by 3GPP/PP2 and WiMAX, but I guess it will be deployed only with the advent of IMS as part of LTE. It is mandatory in OneVoice (aka Voice-over-LTE, VoLTE).

> -----Original Message-----
> From: John Tamplin [mailto:[email-masked]]
> Sent: Friday, August 27, 2010 4:55 PM
> To: Gabriel Montenegro
> Cc: Hybi
> > Great summary. On the 98% of all messages being <= 126 octets, did
> > your traces assume IPv4 or IPv6? The header now being 40 versus 20
> > octets, this might have an effect. Of course, given header compression
> > (e.g., RoHC), it may not be an issue, specially as IPv6 headers are
> > usually more compressible than v4, but I was wondering if you had a
> > feel for any effect this will have.
> 
> WebSocket or lower-layer framing.  The goal of my traces were primarily to
> assess the impact of compression on real-world WebSocket apps, and then later
> using that data to support the debate over how to encode WebSocket payload
> lengths.  Certainly when considering the overall overhead of small frames or
> trying to stay at FACH power levels in 3G networks, the total packet size matters,
> but it doesn't really change anything at the WebSocket layer.
> 
> When I asked the Android guys I knew, they said header compression was not
> currently being done on mobile networks (that was ~6 months ago, it might have
> changed since then), but I would suspect that eventually they will implement
> RoHC.
> 
> --
> John A. Tamplin

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 31 Aug 2010 07:24:00 +1000

On 30 August 2010 21:28, Alexey Melnikov <[email-masked]> wrote:
> I think you are confusing an implementation with a protocol. SSH protocol
> can be profiled for the desired use.

The issue here is not the use of ssh, but the shared use of port 22.
Sure SSH could be used on another port, but that would not be useful
as we need to use a port that will be open through firewalls.

Once we are sharing port 22, we have to be aware that it is already
used for remote login (and things like rsync).  I don't know of
anything running over ssh that is designed to handle many thousands of
connections.   I'm sure there are technical solutions that would make
it possible, but I don't think we can assume that the ssh community
would necessary welcome a new elephant size use-case coming into their
domain.

It may be possible, but it's not a silver bullet.

cheers

---

From: Graham Klyne <[email-masked]>
Date: Tue, 31 Aug 2010 15:59:48 +0100

John Tamplin wrote:
> server?

I really don't care.  I just want to be able to write browser-based applications 
that can access a wider range of facilities and interaction modes than are 
available through current HTTP.  Whether that happens via the HTTP daemon or 
some other program on the server matters little.

> If you implement the protocol in the web server and run over

What matters to me is having the capability available to my browser-based code.

I suppose, if I could just create a TCP connection direct from browser code (to 
any port) that would work. I guess I didn't take this like of thinking to its
conclusion.  Some form of security support would be a requirement, preferably in 
the browser-provided implementation, which may be why I found SSH attractive.

I know it's pretty easy to write simple TCP socket server and tunnel to it via 
SSH to provide secure access.  I've never written server code to use TLS, but I 
suppose it's not so hard, so that would be a reasonable option for me.

> if that were deemed useful.

I don't want *all* of these options, just one of them.  To the extent that it 
rides on existing capabilities seems to me to be a good thing (if only because 
that short-circuits some debate about what those capabilities should be).  But 
if strong consensus is emerging around an option based on HTTP upgrade, that's 
fine by me too.

#g

---

From: Gabriel Montenegro <[email-masked]>
Date: Tue, 31 Aug 2010 18:10:29 +0000

I think we need to deliver on HTTP Upgrade. Having a clear alternative that works over (but is not limited to) both port 80 and 443 is important. Port 80 remains important within the enterprise and on occasions when you already have IPsec (so why use TLS). This is what the group started as and is the only chance of having something in short order. As Alexey point out in his message http://www.ietf.org/mail-archive/web/hybi/current/msg03063.html the TLS option or others can continue, but those will certainly take more time. 

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Graham Klyne
> Sent: Tuesday, August 31, 2010 8:00 AM
> To: John Tamplin
> Cc: Hybi
> Subject: Re: [hybi] Why not just use ssh?
> 
> John Tamplin wrote:
> > If you implement the protocol in the web server and run over a
> > different port, what do you gain over using TLS?  The web servers and
> > browsers likely already have TLS libraries built in, but it seems
> > unlikely to have SSH.
> 
> conclusion.  Some form of security support would be a requirement, preferably
> in the browser-provided implementation, which may be why I found SSH
> attractive.
> 
> I know it's pretty easy to write simple TCP socket server and tunnel to it via SSH
> to provide secure access.  I've never written server code to use TLS, but I
> I don't want *all* of these options, just one of them.  To the extent that it rides
> on existing capabilities seems to me to be a good thing (if only because that
> short-circuits some debate about what those capabilities should be).  But if
> strong consensus is emerging around an option based on HTTP upgrade, that's
> fine by me too.
> 
> #g
>

---

From: Roberto Peon <[email-masked]>
Date: Tue, 31 Aug 2010 11:20:20 -0700

Yes, please.
-=R

On Tue, Aug 31, 2010 at 11:10 AM, Gabriel Montenegro
<[email-masked]>wrote:

> I think we need to deliver on HTTP Upgrade. Having a clear alternative that
> works over (but is not limited to) both port 80 and 443 is important. Port
> 80 remains important within the enterprise and on occasions when you already
> have IPsec (so why use TLS). This is what the group started as and is the
> only chance of having something in short order. As Alexey point out in his
> message http://www.ietf.org/mail-archive/web/hybi/current/msg03063.htmlthe TLS option or others can continue, but those will certainly take more
> time.
>

---

From: Peter Saint-Andre <[email-masked]>
Date: Tue, 31 Aug 2010 12:23:11 -0600

On 8/31/10 12:10 PM, Gabriel Montenegro wrote:

> I think we need to deliver on HTTP Upgrade. 

+1

/psa

---

From: Adam Barth <[email-masked]>
Date: Tue, 31 Aug 2010 12:18:50 -0700

> I think we need to deliver on HTTP Upgrade. Having a clear alternative that works over (but is not limited to) both port 80 and 443 is important. Port 80 remains important within the enterprise and…

TLS works over any port.  The point of using TLS alone is to block
cross-protocol attacks.  If we provide both TLS and non-TLS options,
the attackers will choose the non-TLS option for their attackers
whereas the folks who actually want to connect to the server more than
60-some percent of the time will use the TLS option.  Offering both is
a lose-lose.

Adam