Subject: [hybi] WS ABNF

From: "Thomson, Martin" <[email-masked]>
Date: Mon, 15 Feb 2010 09:12:53 +0800

Hi Ian,

A few ABNF comments for WS (-75 draft).

1. The ABNF for "the wire protocol as allowed by this specification" does not permit binary frames.

     frame         = text-frame / binary-frame
     binary-frame  = %x80 length *%x00-FF
     length        = %x00 / %x01-7f / ( %x81-FF *%x80-FF %x00-7F )

This is a canonical length encoding in that it doesn't allow for leading zeroes.

2. Value range alternatives (Section 3.4 of RFC 5234) should not include a second "%x".

3. The definition for text-frame in the "the wire protocol including error-handling and forward-compatible parsing rules" could be readily simplified to

    text-frame   = %x00-7F *%x00-FE %xFF

I assume that %x80-7E, as included, is in error and %xFE was the intended end of this range.

--Martin

---

From: Dave Cridland <[email-masked]>
Date: Tue, 16 Feb 2010 08:49:25 +0000

> This is a canonical length encoding in that it doesn't allow for  

Am I alone in seeing two design errors here?

Firstly, I see no benefit in having two different framing types. I do  
see a marginal benefit in having multiple frame types, but the idea  
of distinct framing just strikes me as a bad idea, and prone to  
error. I think the correct design decision here is that "bytes is  
bytes", and to the wire, all frames are binary and octet counted. I'm  
not against an end marker, incidentally, although I'm not convinced  
it's needed except in early stages of implementation.

Secondly, is that really a bespoke new method for integer  
representation on the wire? What is the overriding benefit over a  
network byte order 32-bit integer? I see that it can be 1-N octets,  
and therefore will typically save 1-3 octets - I'm assuming we're not  
expecting to ship more than 256M in a frame, where the trade off is.

But the chances of this making a measurable difference are very slim,  
whereas the perils of decoding a new integer representation seem  
extraordinarily high, especially given that it's a nicely unbounded  
integer. IMAP implementations used to have enough trouble when asked  
to allocate 4G for a literal, after all, but at least I'm unaware of  
them having decoding difficulty. OTOH, with 5 octets, I can now setup  
a frame length of 32G, and I can't see anything suggesting that this  
is even a bad idea, let alone illegal protocol.

I have other comments - I'm bewildered that a server responding with  
"HTTP/1.1 101 Web Socket Protocol Handshake." will fail to interop  
with compliant clients, for instance - but I'm intending to leave  
these for a later mail - just be warned these are coming.

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: Julian Reschke <[email-masked]>
Date: Tue, 16 Feb 2010 10:05:21 +0100

Dave Cridland wrote:
> ...
> integer. IMAP implementations used to have enough trouble when asked to 
> allocate 4G for a literal, after all, but at least I'm unaware of them 
> having decoding difficulty. OTOH, with 5 octets, I can now setup a frame 
> length of 32G, and I can't see anything suggesting that this is even a 
> bad idea, let alone illegal protocol.
> ...

It's not really new; something similar (or even the same thing?) is used 
in HTTP chunked encoding.

Best regards, Julian

---

From: Dave Cridland <[email-masked]>
Date: Tue, 16 Feb 2010 09:48:03 +0000

On Tue Feb 16 09:05:21 2010, Julian Reschke wrote:
> Dave Cridland wrote:
>> ...
>> But the chances of this making a measurable difference are very  
>> slim, whereas the perils of decoding a new integer representation  
>> seem extraordinarily high, especially given that it's a nicely  
>> unbounded integer. IMAP implementations used to have enough  
>> trouble when asked to allocate 4G for a literal, after all, but at  
>> least I'm unaware of them having decoding difficulty. OTOH, with 5  
>> octets, I can now setup a frame length of 32G, and I can't see  
>> anything suggesting that this is even a bad idea, let alone  
>> illegal protocol.
>> ...
> 
> It's not really new; something similar (or even the same thing?) is  
> used in HTTP chunked encoding.

Chunked uses a (straightforward, if excitingly unique) ASCII hex  
representation of the size of the following chunk, and chunked  
terminates with an empty chunk (and the trailer).

I don't see that as similar in the slightest, I'm afraid.

It's passingly similar to UTF-8 codepoints, I suppose, and something  
about it nags me into thinking of BER, and the self-termination is  
vaguely reminiscent of the encoding used for codepoints in punycode,  
albeit not nearly as clever.

But UTF-8, BER, and Punycode all have good reasons for their  
encodings. I see no good reason for inventing a new one here - but  
this may simply be that I've missed the discussion. Feel free to  
educate me. :-)

Dave.

---

From: Julian Reschke <[email-masked]>
Date: Tue, 16 Feb 2010 10:57:09 +0100

> I don't see that as similar in the slightest, I'm afraid.

Well, it is similar in that it's a variable length encoding.

But you are right (and before I didn't play close enough attention) that 
it's yet another new encoding, that people need to learn.

BR, Julian

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 17 Feb 2010 08:18:28 +1100

> Am I alone in seeing two design errors here?

Nope - I've been hammering away on these issues for months!

> see a marginal benefit in having multiple frame types, but the idea of
> distinct framing just strikes me as a bad idea, and prone to error. I
> think the correct design decision here is that "bytes is bytes", and to
> the wire, all frames are binary and octet counted. I'm not against an
> end marker, incidentally, although I'm not convinced it's needed except
> in early stages of implementation.

I think sentinel marking is not desirable.  We've had enough problems
with protocols being vulnerable to injection attacks without introducing
another.

I think it is crazy to have a protocol where user supplied data can
fool the protocol framing by providing illegal UTF-8.

length based framing is able to efficiently carry all that is required.

> Secondly, is that really a bespoke new method for integer representation
> on the wire? What is the overriding benefit over a network byte order
> 32-bit integer? I see that it can be 1-N octets, and therefore will
> typically save 1-3 octets - I'm assuming we're not expecting to ship
> more than 256M in a frame, where the trade off is.
> 

+1

> "HTTP/1.1 101 Web Socket Protocol Handshake." will fail to interop with
> compliant clients, for instance - but I'm intending to leave these for a
> later mail - just be warned these are coming.

+100000000000000000000000000000000

cheers

---

From: "Thomson, Martin" <[email-masked]>
Date: Wed, 17 Feb 2010 07:45:29 +0800

> Am I alone in seeing two design errors here?

Nope.  But as Greg points out, there's been resistance to re-design.

I only wanted to point out factual errors, but I'm glad that I've inadvertently caused folks to think about the bigger picture at the same time ;)

---

From: Jamie Lokier <[email-masked]>
Date: Wed, 17 Feb 2010 02:53:38 +0000

> terminates with an empty chunk (and the trailer).

One crucial difference with chunked is, if you think the recipient
will break with a chunk >=2GB (say), you can arbitrarily limit the
maximum chunk size by introducing splits.

But of you actually have an 8GB WebSocket message, a 32-bit length
would introduce an arbitrary limit guaranteed to break.

I know that's not intended normal WebSocket usage.

But imagine someone writes a trivial WebSocket services which recieves
the name of a file (say, it's just an example), and sends back the
contents of the file as a message.  Imagine it was written intended
for small files, but someone decided to use it for bigger ones one day
because it was convenient to do so, and it turned out to work fine.

Then one day, someone else puts an 8GB file there and expects it to
work.  Why should it be fine for 3GB files but fail for an 8GB file?

> albeit not nearly as clever.

Maybe for generality (no fixed limit), but it might have been an
attempt to use fewer bytes for small messages.  Considering most
messages are expected to be small(*), that's not entirely illogical.

(*) - The WebSocket JavaScript API philosophy pretty much requires this,
although other clients aren't bound in the same way.

-- Jamie

---

From: Pieter Hintjens <[email-masked]>
Date: Wed, 17 Feb 2010 09:22:18 +0100

> work.  Why should it be fine for 3GB files but fail for an 8GB file?

Because 4GB should be enough for anybody?

Seriously, it is trivial to define block lengths that can be 1, 2, 4,
8 bytes long.

0-0xFE - 1-byte length
0xFF 0-0xFFFE - escape + 2-byte length
0xFF 0xFF 0xFF 0-0xFFFFFFFE - escape + 4-byte length
etc.

Just because some theoretical developer might get this wrong is not an
argument for making a more complex (fragile) design which allows user
data to imitate framing data.

-Pieter

---

From: Dave Cridland <[email-masked]>
Date: Wed, 17 Feb 2010 09:03:17 +0000

> Nope.  But as Greg points out, there's been resistance to re-design.
The fundamental design - you connect back to the HTTP server and end  
up with a very bare-bones message-passing protocol to an application  
named (or addressed, if you prefer) in URI style - seems very sound.  
Certainly preferable to what we have now (BOSH, Comet, etc), whilst  
remaining within the known security model of the web, with  
single-origin etc.

Some of the details of this design, however - framing, and the  
apparently brittle nature of the initial negotiation - seem likely to  
cause long-term problems. These details need changing *NOW*, to avoid  
early implementors being left with a legacy implementation.

Dave.

---

From: Dave Cridland <[email-masked]>
Date: Wed, 17 Feb 2010 10:17:28 +0000

> work.  Why should it be fine for 3GB files but fail for an 8GB file?

Because websocket messages would (then) be limited to 4G, just as  
IMAP limits emails to 4G (yet the rest of the mailsystem doesn't).  
I'm not aware of this *ever* causing a problem. I'm not aware of -  
amongst the vast numbers of people who seem to enjoy picking holes in  
IMAP - anyone complaining about that limit even theoretically, or  
complaining that the literal octet count is represented in ASCII.

Arbitary limits aren't bad - and the websocket protocol has them in  
the shape of a limited number of message types, which I don't see you  
complaining about.

If you genuinely think it is a serious issue, then beef it up to a  
network byte order 64-bit, or use ASCII if you really want it  
unlimited. I'll look forward to you explaining to people that a  
bigint library is mandatory for websocket implementation, though,  
that'll give me a lot of giggles.

Or simply describe how protocol users can, if needs be, break up  
large files into multiple messages for processing, which might prove  
easier. You could even build this into the protocol, something like a  
flags after the message type where the lowest bit is a "continued"  
flag.

I remain pretty skeptical that such a flag is needed, although the  
notion of having flags in general appeals.

> messages are expected to be small(*), that's not entirely illogical.

Not on the face of it, no. A naïve look would see that a whole 1-3  
octets are shaved off the wire, and that can't be a bad thing in and  
of itself.

The trouble is that it's vanishingly rarely saving any TCP packets,  
which would be interesting and useful, and nor is it saving any  
messages, which is essentially beyond the scope of the protocol.  
Those two *do* save appreciable amounts of bandwidth.

Dave.

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 17 Feb 2010 23:27:36 +1100

Dave Cridland wrote:

> I'll look forward to you explaining to people that a bigint library is
> mandatory for websocket implementation.

Actually that is a very good argument as it goes directly to one
of the oft stated design goals of websocket - that it is easy to implement.

The requirement for an unlimited integer length (or just for the need
to impose a limit in the middle of a loop that reads the value), it
is directly contradictory to this design goal.

regards

---

From: Scott Ferguson <[email-masked]>
Date: Wed, 17 Feb 2010 09:03:42 -0800

Dave Cridland wrote:
> Because websocket messages would (then) be limited to 4G, just as IMAP 
> limits emails to 4G (yet the rest of the mailsystem doesn't). I'm not 
> aware of this *ever* causing a problem. I'm not aware of - amongst the 
> vast numbers of people who seem to enjoy picking holes in IMAP - 
> anyone complaining about that limit even theoretically, or complaining 
> that the literal octet count is represented in ASCII.
Chunked/fragment encoding is needed anyway because you don't want to 
force the sender to buffer an arbitrarily large message before sending 
it. And once you have chunking/fragmenting, the size of the fragment is 
irrelevant to the size of the full message.
> messages, which is essentially beyond the scope of the protocol. Those 
> two *do* save appreciable amounts of bandwidth.
This isn't complicated.  Just use a chunk/fragment encoding that looks like

  len ::= [\x80-\xff]{0,3}[\x00-\x7f]

The 0-terminating chunk takes up a single byte, small messages (< 128) 
only need two bytes of overhead, chunk lengths are limited to 32-bits 
(actually 28-bits but it doesn't matter), the total message size is 
arbitrarily large, and it's trivial to implement.

Or something like utf-8 if you want the first byte to specify the number 
of bytes:

  len0 ::= [\x00-\x7f]
  len1 ::= [\x80-\x9f] [\x00-\xff]
  len2 ::= [\xa0-\xbf] [\x00-\xff]{2}
  len3 ::= [\xc0-\xdf] [\x00-\xff]{3}

Or just use a fixed 2-byte length prefix.

If it's important to add message types (and that would be cleaner as a 
different layer), that's just a single extra byte of overhead.

-- Scott

---

From: Dave Cridland <[email-masked]>
Date: Wed, 17 Feb 2010 17:18:56 +0000

On Wed Feb 17 17:03:42 2010, Scott Ferguson wrote:
>> octets are shaved off the wire, and that can't be a bad thing in  
>> and of itself.
>> 
>> The trouble is that it's vanishingly rarely saving any TCP  
>> packets, which would be interesting and useful, and nor is it  
>> saving any messages, which is essentially beyond the scope of the  
>> protocol. Those two *do* save appreciable amounts of bandwidth.
> This isn't complicated. 

Yes, yes it is. It's hugely more complex than it has any right or  
reason to be.

>  Just use a chunk/fragment encoding that looks like
> 
> The 0-terminating chunk takes up a single byte, small messages (<  
> 128) only need two bytes of overhead, chunk lengths are limited to  
> 32-bits (actually 28-bits but it doesn't matter), the total message  
> size is arbitrarily large, and it's trivial to implement.
> 
> 
Not even remotely as trivial as encoding it as a 32-bit network byte  
order integer. My point is that a compact representation is, here,  
simply not needed. In UTF-8, it *is* needed, because the potential  
savings are 75%, but here, the message itself is the bulk of the  
transfer, and there is no point in wasting effort in making length  
encoding harder than it needs to be to save a percentage point or two.

> If it's important to add message types (and that would be cleaner  
> as a different layer), that's just a single extra byte of overhead.

As I read it, there are already message types. I'm not wed to them  
being there, although I can see the utility of having message types  
and identifiers at a relatively low level. (It's useful both in BEEP  
and XMPP, for example).

Dave.

---

From: Scott Ferguson <[email-masked]>
Date: Wed, 17 Feb 2010 09:43:59 -0800

> Yes, yes it is. It's hugely more complex than it has any right or 

It's something like 6 lines of code to parse.  I don't consider that 
hugely complex. Even parsing an HTTP chunk length is more complicated 
than this.

> encoding harder than it needs to be to save a percentage point or two.

The complexity is essentially the same. I agree that the savings are 
trivial, but the implementation is trivial as well.

>
>> If it's important to add message types (and that would be cleaner as 
>> a different layer), that's just a single extra byte of overhead.
>
Well, XMPP isn't exactly low-level :)

-- Scott