Subject: [hybi] voting on frame length ideas

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

I am not sure this is the best way to accomplish it or how it will work for
people without Google accounts, but I created a Google Moderator series to
help evaluate consensus for various frame length ideas.

https://www.google.com/moderator/#15/e=2809f&t=2809f.40

Feel free to add new ideas if I missed one, and vote for (the checkbox) any
idea you would be happy with, vote against (the X) any idea you would not be
happy with, and for any idea you wouldn't object to but don't feel
particularly in favor of just don't vote on it at all.

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

---

From: John Tamplin <[email-masked]>
Date: Mon, 23 Aug 2010 02:48:49 -0400

> help evaluate consensus for various frame length ideas.

BTW, if you are unable to vote there or don't want to, you can reply to this
thread with your votes on the options.

---

From: Julian Reschke <[email-masked]>
Date: Mon, 23 Aug 2010 09:27:40 +0200

On 23.08.2010 01:55, John Tamplin wrote:
> ...
> Feel free to add new ideas if I missed one, and vote for (the checkbox)
> any idea you would be happy with, vote against (the X) any idea you
> ...

The IETF doesn't vote (<http://www.ietf.org/tao.html#getting.things.done>).

But call it an "informal poll", then this could be useful in finding out 
where we are.

Best regards, Julian

---

From: "Shelby Moore" <[email-masked]>
Date: Mon, 23 Aug 2010 06:48:29 -0400

This will summarize all my input and conclusion on the frame size header
issue. This corrects numerous errors and incoherence in my prior posts on
this issue.  Please read, it is worth it.

> The IETF doesn't vote
> (<http://www.ietf.org/tao.html#getting.things.done>).
>

Gentlepeople, let me see if I can help move us towards concensus. I have
only been trying to help on this frame header issue for about 2 days, so
please give me reasonable chance/patience, before judging me.

Technical points follow the "Justication" section.

Justification
=============

Some have publicly expressed negatively about the delay in reaching
concensus, two people told me privately that I was adding too much verbage
and delaying the process.  I remind them:

http://www.ietf.org/tao.html#getting.things.done

"'rough consensus', meaning that a very large majority of those who care
must agree"

"strongly held objections must be debated until most people are satisfied
that these objections are wrong"

"The lack of formal voting has caused some very long delays for some
proposals, but most IETF participants who have witnessed rough consensus
after acrimonious debates feel that the delays often result in better
protocols."

We do not yet have 'rough concensus' evidenced by the distribution of the
informal poll:

It is my understanding that this is caused by a lack of complete
understanding of the issues, not by a valid difference of opinion. In
fact, most disagreement in life derives from incomplete communication.
When we think someone else is 'wrong', 99% of the time it is merely the
opposing sides do not yet understand the logic of each other. This is why
I continue trying to explain my logic, because I think others do not yet
understand. Some on the list may have dismissed my points as being
'irrelevant' to their opinion, but I think this is because they do not yet
fully understand my points. So with that belief in mind, I will now try to
explain my logic again more carefully. Because unless someone can point
out a flaw in my logic, I think I have considered ALL the concerns
expressed by the list and proposed the ONLY option which meets all of them
with the best quantitative fit. Unfortunately, this logic is convoluted,
so I hope I can explain it non-ambiguiously. Based on the informal poll,
it seems I either failed on my prior attempts, or someone failed to refute
my logic. The above paragraph is long-winded, and it is to make sure
people don't misconstrue my objectives and method of communication here. I
am not arguing for my original choice, Option #2, I am now arguing for
this list's not yet clearly articulated choice. If anyone can put a hole
in my logic below, then it will help us reach mutual understanding, so
that the list's choice will converge.

Technical Points
================

1) Originally I thought "Option #2 - 7/16/63-bit" was fully optimized:

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

because it provided the least possible header overhead in all reasonably
expected scenarios of frame size, known to me at the time, and it removed
the discontinuity in header overhead at 127+ frame size, as compared to
the slightly[1] less optimized "Option #1 - 7/63-bit".

2) However, feedback on the list was that a (negotiated at connection
handshake) maximum frame size was necessary for at least 2 orthogonal
reasons. Some want to reject larger frames as a DoS and/or general
security filter (afaics a _STRICT_ maximum is better here too):

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

I will make multiple orthogonal points below, invalidating one of them may
or may not invalidate all.

Others want to eliminate as much possible CPU overhead in the
pre-processing the frame header (even for single-core implementations),
and orthogonally is that UNAVOIDABLY MUST precede passing the processing
to another core (for multi-core):

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

I explained (with some prior errors corrected herein) that an unreasonable
outcome of not minimizing all (not just any conditionals) the CPU cost of
pre-processing the frame header, is that the network bandwidth could be
wasted. This is always true and the waste is proportion to the ratio of
the CPU time (including multi-core signaling+shunting overhead time) to
process the header, divided by the time to send the entire frame over the
network (could this be eliminated with NIC buffering incoming frames in
parallel with DMA?). Thus the waste increases as frame size decreases.

And I explained that to eliminate the relatively high (as compared to
other header pre-processing) CPU cost of conditional branches (aka
comparisons), a _STRICT_ maximum frame size is required:

http://www.ietf.org/mail-archive/web/hybi/current/msg03510.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03517.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03511.html

John Tamplin questioned whether the conditionals CPU cost was significant,
but I think he was arguing the point of whether the speed of CPU is
increasing faster than the network bandwidth, and I now realize and make
the point above that the waste is any CPU cost, regardless of relative
rate of improvement in network versus CPU speed.

John Tamplin made the point that for intermediaries, they will ignore the
WebSocket frames and just process the TCP packets. I am responding now, to
say that isn't true always, for example refragmentation.

Also, there is a related orthogonal point which is convoluted to explain.
The ability to use all the multi-cores (if not due to a bottleneck at the
network bandwidth plus the aforementioned waste) can be limited by the
average (and thus perhaps the maximum) frame size. The limit can be if avg
is too small causing signalling+shunting load to cause performance to
decrease if more cores are employed. Tangentially, the limit can be if avg
is too high, requiring intra-frame (splitting) parallelization, which
depends on the intra-core signalling cost due to complexity of the
state-machine for the frame data processing (extension protocols, any
application on top, etc).

Thus I explained that due to its internal economics, an implementation
might be optimized with its maximum size larger than 126 if there were no
costs of doing so, but perhaps not if the cost of processing conditionals
combined with the fact that 98% of frames are less than 126, justified
setting a _STRICT_ maximum size of 126, if that eliminated the
conditionals. Remember above I pointed out that the _STRICT_ maximum size
was a benefit when coupled with frame size that uses conditionals, because
it allows the implementation to control its costs and maximize its
economics. But the problem is that if we choose an option which can only
do 0 - 126 size with conditionals eliminated by the _STRICT_ maximum size,
then the (implementation self-optimization) optimization is a disaster,
because it means a large frame has to be fragmented by the sender to 126
byte frames! However, the receiving implementation probably did not have
any benefit of limiting the maximum frame size to 126, except for the
minimization of the conditionals cost.

So ladies and gentlemen, that is why I proposed "Option 15/63-bit" (I
formerly called it "Option 1/15-bit"). Do you understand now?

The 15-bit (32767 bytes) size when conditionals are eliminated by
optimization of the _STRICT_ maximum size, is more than sufficient to
prevent the above disaster scenario.  Also it has negligible (2%? [1])
costs relative to the prior best option, "Option #2 - 7/16/63-bit":

http://www.ietf.org/mail-archive/web/hybi/current/msg03482.html
(see near bottom of the post, extra byte for 0-126, save byte 126-32766)

So clearly "Option 15/63-bit" is superior to "Option #2 - 7/16/63-bit".

3) After I proposed "Option 15/63-bit", a new option was proposed "Option
8/16/32/64-bit". I can't yet decide between these two options, so I voted
for both of them in the informal poll (and voted against all other
options, except "Option #2 - 7/16/63-bit"). The "Option 8/16/32/64-bit"
gives more reversed bits, but it adds a CPU cost of loading the LenLen,
loading a value of 1 and left shifting by LenLen. The "Option
8/16/32/64-bit" does not have any explicit conditionals that can be
eliminated with a _STRICT_ maximum size, but a _STRICT_ maximum size is
still required, else there will be an UNNECESSARY conditional to test if
frame size is greater than maximum size (for those implementations that
gain from such). Thus I am reasonably confident that "Option
8/16/32/64-bit" is superior to "Option 15/63-bit", but I am waiting to
hear any other feedback on the list about this comparison.

Let us contemplate how the _STRICT_ maximum size impacts the 63-bit
sendFile() optimization?  An implementation will choose to minimize its
costs, so we have to consider the selfish economics of what ever we
choose. Perhaps with "Option 8/16/32/64-bit" we can tolerate the one
conditional and make maximum sizes a hint, not _STRICT_?

[1] I write that only 'slightly', because John Tamplin had provided a
distribution of frame sizes from some real world applications, which
claims that only 2% of frame sizes will be greater than 126. I write
'claims', because statistics of the present, do not always predict the
future (aka Murphy's Law). One thing I just realized now, is I forgot to
check/ask John the mean and std deviation of frame size? To better
quantify the impact of adding 1 byte to the header as the other options
do.

---

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

On Mon, Aug 23, 2010 at 3:27 AM, Julian Reschke <[email-masked]>wrote:

> The IETF doesn't vote (<http://www.ietf.org/tao.html#getting.things.done
> >).
>

Sorry, this was only intended as an informal poll because I couldn't figure
out from the emails which proposals had what level of support.

---

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

> out from the emails which proposals had what level of support.

John, I appreciated the your effort on the informal poll, because it
enabled me to see that we were far from concensus, and that more
explanation/discussion was needed.  Also the format you used enabled me to
change my vote as I gained more understanding.

I want to thank you for doing that.

---

From: John Tamplin <[email-masked]>
Date: Mon, 23 Aug 2010 10:55:54 -0400

> change my vote as I gained more understanding.

Participation has been limited so far, but I think it does mean we can
discard the v76-style length and {7,8}/63-bit schemes from further
consideration, as they have a sole proponent and multiple negative votes
against them.

---

From: "Shelby Moore" <[email-masked]>
Date: Mon, 23 Aug 2010 11:03:19 -0400

> consideration, as they have a sole proponent and multiple negative votes

+1

I meant to suggest that.

---

From: John Tamplin <[email-masked]>
Date: Mon, 23 Aug 2010 11:25:03 -0400

On Mon, Aug 23, 2010 at 6:48 AM, Shelby Moore <[email-masked]> wrote:

> opposing sides do not yet understand the logic of each other.

In this case, I think it is more likely that we have different use-cases in
mind.  Clearly someone who wants to process millions of WS frames per second
is going to have a different perspective from someone who wants to easily
implement a WS server in python to service a handful of requests per hour.
 It is unlikely those two will agree on how it should be done on their own
accord.

> minimization of the conditionals cost.

I think it is ludicrous to suggest that an implementation would advertise a
maximum frame length of 126 just so its code for option #2 would look like:

int len=readByte();

rather than:

long long len = readByte();
switch (len) {
  case 126:
     len = readUnsignedShort();
     break;
  case 127:
     len = readLongLong();
     break;
}

while the former is certainly faster, that neglects the overhead of having
to process thousands of frames instead of one, which is what this would
require the sender to do when it needed to send a frame larger than 125
bytes.  Even if the receiver didn't care about costs to the sender or the
intervening networks, the receiver on net spends far more CPU time per
payload byte than if it just did the checks.

In addition, I think the receiver would still have to check that the length
byte was not 126 or 127, because their is no guarantee that the sender is
playing by the rules.

> costs relative to the prior best option, "Option #2 - 7/16/63-bit":

I still think you can't get away from validating the input length, which
means you still have conditionals.

Regardless, I think the cost of a compare and an untaken branch is
absolutely negligible when comparing the other costs of processing a frame.

> loading a value of 1 and left shifting by LenLen.

Rather than calculating a number of bytes to read for the length, it seems
more likely it will be:

short header = readUnsignedShort();
long long len;
// possibly shifting to make it 0-3 for table jump implementations
switch(header & 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;
}

> The "Option

The advantage of 8/16/32/64 vs 15/63 is the availability of more reserved
bits, and savings when the size is >= 32767 (with a significant savings up
to 4G).  Otherwise, 15/63 is the same number of bytes up to frame lengths of
255, shorter for 256-32766, and longer for 3277+.  It is hard to assign a
value to the reserved bits, and the rest comes to the expected distribution
of message sizes above 256 bytes.  My traces don't help much there, because
the largest frame I observed in the Wave and GWT Quake traces is 1393 bytes,
and the number of samples above 256 are very small.

> conditional and make maximum sizes a hint, not _STRICT_?

If the receiver only has a fixed 64k buffer and you send it a 128k frame,
what is it supposed to do?  I don't see any recourse besides dropping the
connection.  Doubly so if it told the sender during the handshake that was
the largest frame size it could accept.

> quantify the impact of adding 1 byte to the header as the other options

Mean/stddev from the sample traces:

   - Wave C->S uncompressed: 287/80, compressed: 39.8/29.7;  S->C
   uncompressed: 213/234, compressed: 34/33.4
   - GWT Quake C->S uncompressed: 51.6/22.6, compressed: 24.7/6.2;   S->C
   uncompressed: 225/139, compressed: 39/34.8

---

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

>  It is unlikely those two will agree on how it should be done on their own

In my experience will be always be able to converge, because never I have
I found that I have to compromise non-optimally on design.  It is always a
problem of not seeing the optimal design, before eventually finding the
optimal one that works well for everyone. If not, it means conflation has
been pushed into the layer being designed and one needs to take a broader
view and fix the conflation first.

The acrimony comes from clinging to conflation and not able to see that
can do the same thing just as efficiently without conflation.

>      len = readUnsignedShort();

I do not think is it ludicrous for an implementation to choose the option
that gives it the highest throughput.

I do not expect an implementation to be coded with concern as to the load
on the senders CPU, when it conflicts with its own internal efficiency. 
Economics and game theory.

> bytes.

The receiver's economics are orthogonal to the sender's economics in this
case.

>  Even if the receiver didn't care about costs to the sender or the

Please read what I originally wrote again.  I took that into consideration
and still the disaster result occured in my game theory.  Consider all the
variables in the game theory. If I was not clear/coherent/lucid, maybe you
can point that out.

> byte was not 126 or 127, because their is no guarantee that the sender is

I already refuted that:

If the receiver expects to be attacked, then checking the size field
guarantees nothing.

> means you still have conditionals.

Incorrect.  See above.

> absolutely negligible when comparing the other costs of processing a

Someone else in list said otherwise.  Any way, we lose nothing (negligible
2-4% loss) by getting rid of the conditional branches.  And we gain more
reserved bits and other advantages with the "Option 8/16/32/64-bit".

Are you arguing both sides of the fence in the post below?

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

Is the extra byte costly or not?

>      len = readUnsignedLong();

Yikes! Why?  Why not use the left shift, it is much more efficient than a
branch.  Branches destroy CPU pipelining.

[snip, because agreed]

> the largest frame size it could accept.

Agreed, so I see no advantage to making maximum size not _STRICT_.

>    uncompressed: 225/139, compressed: 39/34.8

Thank you. So I was roughly correct to use 50 before and estimate a
negligible 2% cost for adding a byte.  Even at 4%, that is still
negligible in overall scheme of things.

---

From: John Tamplin <[email-masked]>
Date: Mon, 23 Aug 2010 12:50:50 -0400

> that gives it the highest throughput.

I think that depends on what you call througput.  If you mean frames/second,
then clearly it should always indicate a size of 1 so it can get the most
possible frames.  If you mean payload bytes/second, then I disagree --
having one 100k frame and doing an extra compare instruction is going to get
far more payload bytes through in the same time than processing 100k 1-byte
frames, even if it doesn't include a comparison.

> Economics and game theory.

There was no such assumption, see above.

> If the receiver expects to be attacked, then checking the size field

Not checking it means a sender that ignored the maximum frame size could get
the receiver out of sync with framing boundaries.  Experience has shown many
attacks to follow from such problems.

> Someone else in list said otherwise.

Which you are taking out of context and extending it far beyond the
circumstances it was intended.  You also attributed that person to support
your proposal, which in fact they did not.  Regardless, it would be best to
speak your own opinions rather than restating someone elses.

> Any way, we lose nothing (negligible

Between these options, there is an extra byte for small frames regardless.

> branch.  Branches destroy CPU pipelining.

You are going to have branches anyway.  Your suggestion would be (inlining
the loop for clarity):

short header = readUnsignedShort();
long long len;
int lenlen = (header & LEN_LEN_MASK) >> LEN_LEN_SHIFT;
int lengthBytes = 1 << lenlen;
while (lengthBytes-- > 0) {
  lenlen = (lenlen << 8) | readByte();
}

Even if you unroll the loop and branch to different points in the reading
code, there is still a branch there:

It is really pretty basic -- if you have a variable number of bytes for the
length, there will be branches regardless.  If the number of branches are
small, you can optimize for the branch-not-taken case, which will have
minimal impact on the pipeline on most architectures in the 98% case.

---

From: "Shelby Moore" <[email-masked]>
Date: Mon, 23 Aug 2010 13:38:17 -0400

> consideration, as they have a sole proponent and multiple negative votes

I think the changes you made are misleading:

"Option #2B - 8/16/63-bit length Read the first length byte, if 0-253,
that is the length. If 254, the next two bytes are the length. Otherwise,
read the next 8 bytes (high bit must be zero) and that is the length."

That does not explain that the penality is that we lost 1 reserved bit and
only have 2 reserved bits remaining.  You argued strongly against that
option before correct?  Did you drop your objective to losing the 3rd
reserved bit?  Maybe you can just add that disadvantage and reset the
voting for that item?

---

From: John Tamplin <[email-masked]>
Date: Mon, 23 Aug 2010 14:18:07 -0400

> I think the changes you made are misleading:

Neither I or Julian made the proposal 2B you are referring to.

---

From: "Shelby Moore" <[email-masked]>
Date: Mon, 23 Aug 2010 15:16:58 -0400

>> > I think it is ludicrous to suggest that an implementation would
>> advertise
>> > a

The key epiphany is that it is a threshold issue with many interdependent
variables, which I can tell you haven't realized yet (given what you wrote
above). Around the threshold of 126, the choice might go either way
depending on the internal design and components and the external network
speed. Please go read what I originally wrote more carefully. I have
explained too many times already.  I know the list is getting tired of me
replying. I think I explained it already well enough.

Besides it is bad engineering to not add another byte and leave some
margin for error:

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

> There was no such assumption, see above.

See above again too.

> attacks to follow from such problems.

It doesn't matter if you check the size, the size may be a lie too. I
can't believe I had to say that 4 times already. Really you can't see
that?

> speak your own opinions rather than restating someone elses.

I have not said any one supports my proposal.  And here are the posts and
I think it is pretty clear that he talks about CPU speed, and says "126"
threshold may miss the sweet spot (we don't know if he is only referring
to network bandwidth or to his prior point about CPU speed, but
nevertheless I think the threshold at 126 is too low and is unnecesary
risk for no gain):

http://www.ietf.org/mail-archive/web/hybi/current/msg03439.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03418.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03453.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03435.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03434.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03429.html
http://www.ietf.org/mail-archive/web/hybi/current/msg03422.html

Rather I think you may be conflating this message, which was a different
question as your focus wasn't on the CPU efficiency:

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

> Between these options, there is an extra byte for small frames regardless.

So what does that byte cost us in risk??

See above. It costs us that the threshold around 126 is dangerous:

* data serializer might not be as efficient as you measured before
* maximum frame thresholding has only the 126 choice
* and who knows what else we didn't think of

Does NASA design rockets with 0% tolerance for failure?

> minimal impact on the pipeline on most architectures in the 98% case.

Good point!  I hadn't thought that part out yet (mind has been too busy on
these other issues).

So it looks like my original proposal of "Option 15/63-bit" is best if we
care about minimum CPU load on the frame header processing.

If frames end up being as small as you hope, that could be significant.