Subject: [hybi] 8/16/32/64-bit is not optimal?

From: "Shelby Moore" <[email-masked]>
Date: Mon, 23 Aug 2010 23:52:42 -0400

Although I explained in prior posts today why I reasonedly prefer
15/63-bit, I will not try to block concensus on 7/16/63-bit, which was my
former best choice. In most aspects, the choice between the two is
splitting hairs.

Since we no longer need the CML bit, then we have 4 reserved bits now in
those two choices.

However, I have changed my 'for' vote to an 'against' vote for the
8/16/32/64-bit choice, and I will object to this choice unless someone can
explain some rational for it?

The 8/16/32/64-bit choice is inferior in almost every way to 7/16/63-bit.
If you need the extra reseerved bits, then add a byte to 7/16/63-bit for
reserved bits, then the header will be same size. 7/16/63-bit always has
lower CPU overhead. The only advantages I see for 8/16/32/64-bit is it
could support 128-bit and 256-bit easily.

Can anyone else enumerate any rational for 8/16/32/64-bit choice?

Imho, it would really help the list to understand your thinking if you
continue to vote for that choice, considering we are not yet to concensus
in our voting results.  We need some way to push concensus, so we need to
justify our vote here, so we know the reasons for our differences.

---

From: John Tamplin <[email-masked]>
Date: Tue, 24 Aug 2010 00:20:08 -0400

> Since we no longer need the CML bit, then we have 4 reserved bits now in

It isn't clear that is agreed, but regardless does not differentiate between
the two.

Note that I prefer the 7/16/63 -- what follows are the pros for 8/16/32/64,
and why I would not object to it.

> reserved bits, then the header will be same size.

Except if the payload is more than 125 bytes, in which case 7/16/63 uses at
least one extra byte (2 if you add a reserved byte).  Also, 8/16/32/64
supports a 32-bit length option, which eliminates objections that some had
to the 7/16/63 option.

> 7/16/63-bit always has lower CPU overhead.

I'm not sure that follows -- with a typical implementation, you replace two
compares/branches (and likely another branch depending on how the compiler
lays out the code) with a single computed jump (probably via table lookup)
so it is probably about the same and will vary depending on the
architecture.  Regardless, I think you are getting hung up on fractions of a
nanosecond.  For the cases where such timings are important, it is likely to
be implemented in an ASIC or custom silicon anyway.

> The only advantages I see for 8/16/32/64-bit is it

Irrelevant, as we have no need for lengths that long, and I don't see any
difference in the ease of extending either if we did need them.

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

---

From: "Brian Smith" <[email-masked]>
Date: Tue, 24 Aug 2010 03:53:14 -0500

John Tamplin wrote:
> Except if the payload is more than 125 bytes, in which case
> 7/16/63 uses at least one extra byte (2 if you add a reserved
> byte).  Also, 8/16/32/64 supports a 32-bit length option,
> which eliminates objections that some had to the 7/16/63
> option.

I thought the goal was to maximize the amount of data you can fit into a 128 byte or 256 byte packet, reduced by the TCP/IP header size. The extreme case occurs when the TCP/IP header is compressed down to 2 bytes and the FACH->DCH threshold is 256, leaving 254 bytes available to the application to use without penalty. If we subtract one byte for a WebSockets-layer length field, then ideally lengths up to and including 253 should be encoded in one byte.

But, also, lengths of 119 or less can be encoded in up to 9 bytes without the frame spilling over into another packet or triggering DCH even when the FACH->DCH threshold is 128 bytes. That means that a one-byte length encoding would only be critical for lengths 120-253 (134 values). Based on that, I came up with the following encoding:

If the first byte X is 0x03 through 0xFF, then the length is 120+X-3. Examples: the byte 0x03 encodes a length of 120, the byte 0xFF encodes a length of 372.

If the first byte is 0x00, then the next two bytes are a big-endian encoding of a value X. If X < 117 the X is the length of the frame. Otherwise, the length of the frame is 373+X-117. For example, 0x00 0x00 0x00 is zero, 0x00 0x00 0x74 is 116, 0x00 0x00 0x75 is 373, and 0x00 0xFF 0xFF is 65,791. (The purpose of this is to ensure there is only one way of encoding each length.)

If the first byte is 0x01, then the next four bytes are a big-endian encoding of a value X and the length of the frame is 65,792 + X.

If the first byte is 0x02, then the next eight bytes are a big-endian encoding of a value X, and the length is calculated analogously to the case where the first byte was 0x01.

Regards,
Brian

---

From: "Shelby Moore" <[email-masked]>
Date: Tue, 24 Aug 2010 10:55:58 -0400

> I thought the goal was to maximize the amount of data you can fit into a
> 128 byte or 256 byte packet, reduced by the TCP/IP header size. The
> extreme case occurs when the TCP/IP header is compressed down to 2 bytes
> and the FACH->DCH threshold is 256, leaving 254 bytes available to the
> application to use without penalty. If we subtract one byte for a
> WebSockets-layer length field, then ideally lengths up to and including
> 253 should be encoded in one byte.

If that is the goal and 4 reserved bits (including 'More') is sufficient,
then 15/63 is optimal:

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

BYTES  RANGE        OPTION      RESERVED BITS (including 'More')
----------------------------------------------------------------
2      0-125        7/16/63     4
4      126-65535    7/16/63     4
3      0-255        8/16/32/64  9
4      256-65535    8/16/32/64  9
3      0-32766      15/63       4

Both 15/63 and 8/16/32/64 need 3 bytes for 0-255, but 15/63 doesn't need 4
bytes for 255+.  The FACH cell phone thesholds will probably increase over
time!  YOU SEE WHY I HAVE BEEN SAYING IT IS OPTIMAL!

Also 15/63 has lower relative CPU load.  I will soon try to quantify how
much lower. And I am referring to the ratio, not the nominal difference.

> But, also, lengths of 119 or less can be encoded in up to 9 bytes without
> the frame spilling over into another packet or triggering DCH even when
> the FACH->DCH threshold is 128 bytes. That means that a one-byte length
> encoding would only be critical for lengths 120-253 (134 values). Based on
> that, I came up with the following encoding:
>
> If the first byte X is 0x03 through 0xFF, then the length is 120+X-3.
> Examples: the byte 0x03 encodes a length of 120, the byte 0xFF encodes a
> length of 372.
>
> If the first byte is 0x00, then the next two bytes are a big-endian
> encoding of a value X. If X < 117 the X is the length of the frame.
> Otherwise, the length of the frame is 373+X-117. For example, 0x00 0x00
> 0x00 is zero, 0x00 0x00 0x74 is 116, 0x00 0x00 0x75 is 373, and 0x00 0xFF
> 0xFF is 65,791. (The purpose of this is to ensure there is only one way of
> encoding each length.)
>
> If the first byte is 0x01, then the next four bytes are a big-endian
> encoding of a value X and the length of the frame is 65,792 + X.
>
> If the first byte is 0x02, then the next eight bytes are a big-endian
> encoding of a value X, and the length is calculated analogously to the
> case where the first byte was 0x01.

What is the maximum value that can be represented with 3 bytes?

What is the relative CPU load, i.e. can you show us the optimal C code?

---

From: "Brian Smith" <[email-masked]>
Date: Tue, 24 Aug 2010 11:04:35 -0500

Shelby Moore wrote:
> > John Tamplin wrote:
> > I thought the goal was to maximize the amount of data you can fit into
> > a 128 byte or 256 byte packet, reduced by the TCP/IP header size. The
> > extreme case occurs when the TCP/IP header is compressed down to 2
> > bytes and the FACH->DCH threshold is 256, leaving 254 bytes available
> > to the application to use without penalty. If we subtract one byte for
> > a WebSockets-layer length field, then ideally lengths up to and
> > including 253 should be encoded in one byte.
> 

Implicit in this scheme is the idea that there are no such reserved bits.
The scheme I gave can be extended to allow for other data encodings that
require explicit flag values by additionally reserving any or all of the
values 0x03-0x77 (3-119) as indicators that a different encoding is being
used. This would still allow 120-253 to be encoded in one byte when default
values for flags are used.

If explicit flags, or channel indicators for multiplexing, or other
additional data needs to be encoded in the header, then those requirements
should be nailed down as much as possible before trying to choose an
encoding. This is basically a data compression problem and in data
compression you get bad results if you compress each field individually and
then round each compressed field off to a whole byte. Instead you should
generally compress all such fields together, as much as possible.

With that in mind, why can't the working group just proceed with a fixed
64-bit encoding of the length for now, and then come back at the end of the
process and specify a more compact representation of the frame header once
all the contents of that header are known and other issues such as data
compression are resolved? That way everybody can build prototypes that
aren't optimal in the edge cases, but which work and even interoperate in
the interim.

> > 0x00 0xFF 0xFF is 65,791. 
> 

65,791 with no explicit flags, if only 0x00, 0x01, and 0x02 are reserved as
identifiers for the length encoding.

Cheers,
Brian

---

From: gustav <[email-masked]>
Date: Tue, 24 Aug 2010 18:17:55 +0200

> aren't optimal in the edge cases, but which work and even interoperate in
You currently have interop in several web browsers beta builds, do you
seriously want to break that just to use another temporary design ?!.
Do you think the browsers and others want to re implement and test it when
they know it will be very temporary ?.