Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

From: Jamie Lokier <[email-masked]>
Date: Thu, 7 Jun 2012 04:44:40 +0100

Arman Djusupov wrote:
> 
>    Resending would be required when the allocation of a logical channel
>    has failed on the server or the intermediary due to any kind of mux
>    related error. For example: “Maximum number of logical channels per
>    physical connection has been reached “ or “Intermediary cannot reach
>    the destination endpoint”. The current draft requires that if an
>    AddChannelResponse is received with a failed flag, the client attempts
>    to open a new physical connection. Since the browser must keep the mux
>    extension transparent it cannot let the JS application handle the
>    recovery from mux related errors.

If there is a max_simultaneous_handshakes - why not recast that as
"initial new-channels window" - meaning a flow control grant, which is
updated by further grants from the server.  (Very similar to the flow
control per channel).

Then it means initially you can set a number, and subsequently, the
server will control the rate of admission of new channels.  Then it
can regulate it at a smaller or larger value, be conservative if
appropriate until a client has proven not to be an attack, etc.

There's basically zero message overhead, as the grant update would
follow AddChannelResponse if the server wants to maintain a constant
number in flight.

Having redefined max_simultaneous_handshakes that way....

It removes the need to re-send due to "maximum number of channels
reached" - because it can't happen.  The token is a promise.  (If the
server can't take it, there's a fault so it's a reason for a hard error).

"Intermediate cannot reach destination endpoint" ought to be a
non-retry error for the same reason that it would be for an HTTP
intermediary.  I guess this is debatable.

But assuming that debate was won :-) there would be no reason for re-sending.

That said, it doesn't really matter, the client is free to limit the
amount of data it sends before a channel is confirmed, to an amount it
considers reasonable to store.

A goal that I think is worthwhile are zero-latency-creation channels,

That is where a JS would be free to create channels, with no
round-trip overhead to start a request-response pattern over them.

It's currently paradoxical that HTTP (and especially SPDY) use one
_less_ round-trip to send short AJAX-style requests from independent
code (or independent pages), compared with multiplexed WebSocket.

Zero-latency-creation channels would make WS behave at least as well
as AJAX in the small-request-response pattern, which is after all
extremely common.

>    I like the idea of using the total pre-handshake quota for all logical
>    channels. This would allow high throughput channels to utilize a common
>    pre-handshake quota when other channels do not require to send any data
>    prior to receiving an AddChannelResponse. I believe that this solution
>    would be more optimal than having a pre-handshake quota per logical
>    channel.

It's more flexible for the client, which can choose to abuse it or
not.  I like the idea - but... does it make any problems for the
server?

The server may know it has enough memory for N bytes per channel
buffer, but it may not have a data structure which can efficiently
assign M*N bytes to a single channel (for example due to memory
fragmentation or pre-allocation issues, or simply how "malloc" works).
It might also want to prevent M*N for heuristic reasons such as
channel fairness - which it is already responsible for when channels
are up and running.

In my view, the server must have the ability to constrain the initial
parameters of each channel that the client can assume.  It would be
fine to allow the server to grant a total pre-handshake quota, as an
optional extra, but there should definitely be some constraint on
pre-handshake per-channel data.  But I do favour that being non-zero.

>    However, this solution would require the client to subtract the
>    required value from the common quota and specify this value in
>    the AddChannelRequest header, so that the server knows from which
>    initial value to start counting the remote side quota.

Isn't it clear without it?  The client sends pre-handshake data, the
server moves it from the common pool to the new channel buffer,
potentially freeing up space in the common pool (if it wants), and the
server simply treats the data, for flow control window purposes, as if
it came after the channel was set up.  Everyone agrees.

Anyway, the client shouldn't have to pause/delay sending data after
AddChannelRequest, until the response, if there is sufficient quota to
keep sending.  Specifying the amount used in the request would seem to
enforce that delay, which is unnecessary in principle.

>    There should also be a way to restore the common quota, e.g. in
>    AddChannelResponse the server can send a header which would
>    specify the value that should be added to the common
>    pre-handshake quota.

If there is a common pre-handshake data quota, I agree with this.
However, it should not be attached specifically to AddChannelResponse.
Rather, the server should be able to increase this amount granted at
any time, so have its own message.

It parallels what I suggested at the start of this mail, about making
the physical handshake quota be a window that is maintained by flow
control grants from the server, rather than a fixed in-flight
constant, in the same way as per-channel flow control does.

All the best,
-- Jamie

---

From: "Arman Djusupov" <[email-masked]>
Date: Thu, 7 Jun 2012 15:14:23 +0300

The common pre-handshake quota mechanics need to be simplified. 

A server's buffer pool capacity is very volatile. There is no reliable way to predict what capacity the server will have in a few seconds. Whatever complex decision process the server uses to estimate its buffer availability, at the moment when a buffer has to be acquired this estimation will be already outdated. When the server code cannot really know what amount of memory will be available during the next handshake, what is the point of giving a client an estimation on the server's buffering capacity?

Since there is no run-time precision, the reasonable solution is to set those limits based on either optimistic or pessimistic expectations and worst case scenarios.
 
During the initial handshake the server can negotiate a value that would indicate the maximum amount of initial quota the client can use before the handshake is complete. So before handshaking the client simply sets its quota to this value. The server will be spending its buffers as normal knowing that the client didn't violate any initial agreements. So there would be no additional common quota calculation on the server side. 

If a large number of clients establish logical channels concurrently and each uses an initial quota, the server may run out of buffers (unless it has the capacity to provide buffering to all new channels being established). I'm not too much concerned about it. Whatever we do, there will always be a case when the server may run out of buffers.

My expectation is that by using more complex algorithms for the initial quota we won't really make it more reliable.

With best regards,
Arman

-----Original Message-----
From: Jamie Lokier [mailto:[email-masked]] 
Sent: Thursday, June 07, 2012 6:45 AM
To: Arman Djusupov
Cc: 'Takeshi Yoshino'; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

>    recovery from mux related errors.

If there is a max_simultaneous_handshakes - why not recast that as "initial new-channels window" - meaning a flow control grant, which is updated by further grants from the server.  (Very similar to the flow control per channel).

Then it means initially you can set a number, and subsequently, the server will control the rate of admission of new channels.  Then it can regulate it at a smaller or larger value, be conservative if appropriate until a client has proven not to be an attack, etc.

There's basically zero message overhead, as the grant update would follow AddChannelResponse if the server wants to maintain a constant number in flight.

It removes the need to re-send due to "maximum number of channels reached" - because it can't happen.  The token is a promise.  (If the server can't take it, there's a fault so it's a reason for a hard error).

"Intermediate cannot reach destination endpoint" ought to be a non-retry error for the same reason that it would be for an HTTP intermediary.  I guess this is debatable.

That said, it doesn't really matter, the client is free to limit the amount of data it sends before a channel is confirmed, to an amount it considers reasonable to store.

That is where a JS would be free to create channels, with no round-trip overhead to start a request-response pattern over them.

It's currently paradoxical that HTTP (and especially SPDY) use one _less_ round-trip to send short AJAX-style requests from independent code (or independent pages), compared with multiplexed WebSocket.

Zero-latency-creation channels would make WS behave at least as well as AJAX in the small-request-response pattern, which is after all extremely common.

>    would be more optimal than having a pre-handshake quota per logical

It's more flexible for the client, which can choose to abuse it or not.  I like the idea - but... does it make any problems for the server?

The server may know it has enough memory for N bytes per channel buffer, but it may not have a data structure which can efficiently assign M*N bytes to a single channel (for example due to memory fragmentation or pre-allocation issues, or simply how "malloc" works).
It might also want to prevent M*N for heuristic reasons such as channel fairness - which it is already responsible for when channels are up and running.

In my view, the server must have the ability to constrain the initial parameters of each channel that the client can assume.  It would be fine to allow the server to grant a total pre-handshake quota, as an optional extra, but there should definitely be some constraint on pre-handshake per-channel data.  But I do favour that being non-zero.

>    initial value to start counting the remote side quota.

Isn't it clear without it?  The client sends pre-handshake data, the server moves it from the common pool to the new channel buffer, potentially freeing up space in the common pool (if it wants), and the server simply treats the data, for flow control window purposes, as if it came after the channel was set up.  Everyone agrees.

Anyway, the client shouldn't have to pause/delay sending data after AddChannelRequest, until the response, if there is sufficient quota to keep sending.  Specifying the amount used in the request would seem to enforce that delay, which is unnecessary in principle.

If there is a common pre-handshake data quota, I agree with this.
However, it should not be attached specifically to AddChannelResponse.
Rather, the server should be able to increase this amount granted at any time, so have its own message.

It parallels what I suggested at the start of this mail, about making the physical handshake quota be a window that is maintained by flow control grants from the server, rather than a fixed in-flight constant, in the same way as per-channel flow control does.

All the best,
-- Jamie

---

From: Takeshi Yoshino <[email-masked]>
Date: Wed, 13 Jun 2012 19:18:33 +0900

> updated by further grants from the server.  (Very similar to the flow

Good idea. I'll take it.

Specifying the amount used in the request would seem to
> enforce that delay, which is unnecessary in principle.

Sorry, why?

---

From: Takeshi Yoshino <[email-masked]>
Date: Wed, 13 Jun 2012 19:37:17 +0900

Adopting both common and channel-wise pre-handshake quota sounds too much.
I slightly prefer to take only one of them.

I was wondering if the risk of head-of-line blocking on pre-handshake quota
is significant or not. That's why I proposed two-parameter method in the
first mail in this thread rather than common pre-handshake quota.

Any other opinions?

---

From: "Arman Djusupov" <[email-masked]>
Date: Wed, 13 Jun 2012 15:35:41 +0300

Agree, I also came to this conclusion. It's better if there is simply a
per-channel pre-handshake quota. The server should not send any  "quota"
value in its AddChannelResponse. It should be assumed to be always equal to
the pre-handshake quota agreed.

This solution would be fine with me.

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Wednesday, June 13, 2012 1:37 PM
To: Arman Djusupov
Cc: Jamie Lokier; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

Adopting both common and channel-wise pre-handshake quota sounds too much. I
slightly prefer to take only one of them.

Any other opinions?

---

From: "Arman Djusupov" <[email-masked]>
Date: Thu, 14 Jun 2012 11:54:57 +0300

We should not overestimate the difference between pessimistic and optimistic
scenarios. The major difference is in the amount of quota they grant to the
remote side. In the pessimistic case the receiver sends a small quota,
assuming that it will be able to buffer all input in a worst case scenario.
While in the optimistic the case receiver sends a larger quota based on the
rate with which it was able to process incoming frames so far, not relying
entirely on its buffering capacity. Both strategies might work fine and both
might end up in failure. In the worst case scenario when the receiver runs
out of buffers both should be ready to fall back to TCP flow control or to
discard data.

If the mux client can send data up to the pre-handshake quota after the
AddChannelRequest without waiting for an AddChannelResponse, this would
already minimize the roundtrip in case when the data that has to be sent is
not larger than the pre-handshake quota. If this data is larger than the
pre-handshake quota than a delay may happen (it depends on how fast the
server is going to send the AddChannelResponse and the first FC frame). The
same applies to an HTTP server that does not use any mux, the client would
not be able to send a complete request if the server is not going to process
or buffer it right way. Servers usually buffer inbound requests up to some
limit and then wait for the working thread to pick up the request and
process it, only then can the client send the remaining data. In case of
HTTP such a quota is enforced by the TCP flow control, due to the server's
refusal to buffer the complete request. HTTP also supports the Expect:
100-Continue header and 100-Continue response which practically constitute
flow control. 

In other words it is fine to impose pre-handshake quota limits. In cases
when this causes delays it is natural, such delays would happen with mux or
without it.

With best regards,
Arman

-----Original Message-----
From: Jamie Lokier [mailto:[email-masked]] 
Sent: Wednesday, June 13, 2012 8:55 PM
To: Takeshi Yoshino
Cc: Arman Djusupov; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

Takeshi Yoshino wrote:
>    On Thu, Jun 7, 2012 at 12:44 PM, Jamie Lokier <[1][email-masked]>
>    wrote:
> 
>    Arman Djusupov wrote:
>    >
>    >    Resending would be required when the allocation of a logical
>    >    channel has failed on the server or the intermediary due to
>    >    any kind of mux related error. For example: Maximum number
>    >    of logical channels per physical connection has been reached
>    >    or Intermediary cannot reach the destination endpoint. The
>    >    current draft requires that if an AddChannelResponse is
>    >    received with a failed flag, the client attempts to open a
>    >    new physical connection. Since the browser must keep the mux
>    >    extension transparent it cannot let the JS application
>    >    handle the recovery from mux related errors.
> 
>      "initial new-channels window" - meaning a flow control grant,
>      which is updated by further grants from the server.  (Very
>      similar to the flow control per channel).
> 
>    Good idea. I'll take it.

Excellent :-)

The idea isn't entirely random, it's prompted by some general principles of
flow control which apply in a lot of situations; see my "some thoughts"
further down.

The original paragraph said:

>> AddChannelRequest, until the response, if there is sufficient quota 
>> to keep sending.  Specifying the amount used in the request would 
>> seem to enforce that delay, which is unnecessary in principle.

Consider this scenario:

   This is WebSocket, so it's quite likely client and server
   application processes are generating a continuous flow of messages
   in each direction, with a wide variety of timings.  In all cases we
   would like to minimise latency, and with mux we also want 

   Client process (C) generates initial data stream.

   The first bytes available from the client process are included in
   the initial channel request.

   Server process (S) can begin processing those initial bytes, and
   generates a stream of response bytes.  Those will follow
   immediately after the channel response.

   Client process (C) is still generating data 0.1 second later, 0.2, 0.3...

   But round-trip time is 2 seconds.

If the client is allowed to send initial data with AddChannelRequest, but
then not allowed to send more data until it receives the AddChannelResponse,
there is a pause in the flow: data produced at 0.1, 0.2, 0.3 seconds cannot
be sent until 2 seconds pass, cannot be processed by the server etc.

This is the unnecessary delay.  Client should be able to send more data up
to the presumed initial-channel data window, in packets after the
AddChannelRequest.  This also means client must be able to choose the
channel identifier (for sending at least).

If those are little request messages over WebSocket, then it will be
*4* seconds before they get responses, due to doubling the round trip.
(On mobile networks, the delays are often larger.)

This additional overhead is not present without the Mux protocol, or to
applications doing their own app-mux instead.  So the Mux adds overheads on
top of non-Mux, and may even accumulate multiple such delays per-Mux/Demux
hop (multiple proxies), which is quite bad.

Since it's unnecessary, it shouldn't do it.  There is no practical
complexity to implementations allowing data after the request as opposed to
just with the request itself.

The protocol is possibly simpler that way: The request doesn't need to
handle a data payload.  All initial data can follow in their own messages.

Some thoughts on the subject of flow control and channel setup:

   - Receive without blocking other flows (channels) is a semantic
     requirement, not just a nicety.  Otherwise the flows don't have
     the same behaviour as separate TCP connections.

     Applications (including event-driven scripts) that use separate
     connections, expect them to behave quite independently, meaning
     data on one can't permanently block the flow of data on another.

     If Mux connections aren't that independent, supposedly
     independent operations can get in a tangle waiting on messages
     from each other.  (Even in a browser app, with just one server).
     (I wrote out more detail but it went on a bit long.)

     It is horrible to debug when that happens, it's one of those
     "nearly always doesn't happen, spend hours trying to understand
     why the app is broke" things, and we should never inflict it on
     anyone.  It's just a bad model, and unnecessary.

     But it's worse if Mux is a hidden optimisation, in the browser
     and/or intermediaries, as it changes the semantics.  Going from
     no-deadlock to deadlock possible is a change of semantics.

     That is the most important reason for pessimistic flow control:
     It is necessary for Mux to have the same semantics as non-Mux,
     before it can be safely deployed as a hidden transport
     optimisation.

     (Same applies to mux in SPDY, HTTP/2 etc.)

     (The various proposed standards could do with more explanation of
     why channel flow control is so important, and why it must use the
     patterns it uses to get independent flow semantics.)

   - The basic method is to never block TCP at the receiver while you
     have more than 1 flow muxed over it.  Blocking TCP is fine when
     you have only 1 flow.  But new channel setup requests are,
     logically, another flow, and so are control messages (such as
     clean shutdown).  So the 1 flow case doesn't happen, except
     during initial handshake.

   Assuming all that:

   - Pessimistic flow control, aka. grants or promises to receive
     without blocking other channels.  This keeps the complexity low
     at the sender.  The receiver is responsible for allocating its
     memory and managing fairness.  The principle applies just as well
     to connection setup counts, and initial channel data, as to
     regular channel data.

   - Optimistic flow control (commands to allow sending more than the
     receiver can accept), mean the sender may need to abort and
     re-send (or flows will become deadlocked).  These are more
     complex for everyone, but in some circumstances provide
     on-average less latency (and sometimes the other way).

     But think about it: TCP doesn't do this, and it's fine without it.
     (It uses an exponentially rising method of handing out more
     window as long as there is no congestion.)

     So is this ever worth the complication?  I don't know, but I
     would suggest anything like this be explored as an experimental
     extension, on top of the basic pessimistic methods.

   - "Xon/xoff" start-stop style flow control is a disaster: the
     receiver cannot guarantee to store all that it receives before
     the stop token reaches the sender, so TCP will block the flow
     instead and there's no way forward until the receiver gains more
     memory.  Which it won't if it's deadlocked.  This is a form of
     optimistic flow control.

   - Start-stop and optimistic need pessimistic flow control anyway!!

     Otherwise, if TCP is blocked due to over-sending what the
     receiver cannot buffer, there's no way "stop" or "re-send later"
     messages can get through in that direction.  Think about it.

   - Summing up: You *have* to have pessimistic flow control tokens at
     some stage.  You can build other things on top, but there is no
     avoiding this if you want the protocol to be unable to get stuck.
     (I'm fairly confident of this but would love to be proven wrong.)

   - Whoever is initiating a new channel should select the channel id
     for binding data blocks together, and be allowed to send more
     data immediately after the initiating request (subject to normal
     flow control).

     This effectively makes the channel exist immediately, so the
     initiator can send data as as it generates it.

     Otherwise, the initiator can send an initial "pulse" of data,
     followed by a round-trip delay until it can send more, which may
     not match the pattern of data generation, and causes mux to add
     latency, sometimes accumulating per-hop, in places where it isn't
     necessary.

     Example: Without the delay, it is possible to send HTTP-style
     requests and responses, creating a new channel for each request,
     as efficient as pipelining with independent response orders, with
     all the benefits of flow control etc.  With the round-trip delay,
     this is not an efficient pattern, and the application will likely
     devise its own request muxing protocol over a single channel,
     sometimes accidentally reproducing some of the deadlock/flow
     control scenarious discussed above.

   - When assigning new channels, it's useful to have a data window
     known in advance (or negotiated) for new channels.  It could be
     shared among all new channels or per-channel immediately; does
     not matter.  Although a protocol where channels are setup first
     seems simpler, it does not actually save any memory at the
     receiver (which needs to have dedicated memory per-channel for
     the control structures anyway), nor make it any simpler.

   - Finally, whether to use pessimistic flow control for channel
     requests, or allow them to be rejected for resource reasons and
     tell the sender to try again later, or on another TCP connection.

     The discussion above about pessimistic vs. optimistic applies to
     these as well.  Just like data, channels use memory and their
     setup has similar flow control issues.  So the same flow control
     mechanisms can apply to channel setup allowances.  That's the
     "initial new-channels window" idea.

     However, here there's a stronger case for at least evaluating
     optimistic with retry.  Think about the way a web server
     regulates the load from new TCP connections, with an unknown
     number of clients: It simply ignores new TCP SYN packets, when
     there are too many connections.  Clients retry, and back off
     exponentially, thus regulating the load over a considerable range
     (it's not perfect).  This works because clients back off
     exponentially, and servers use the minimum of resources for
     denied requests (i.e. ignore them).

     With pessimistic flow control of new channels, an initiator will
     wait until it gets a message saying it can use another one.
     While everything is running smoothly, that's a good balancing of
     resources.

     But if there's a load spike, and at the same time TCP stalls at a
     series of retransmits due to congestion, after the load spike the
     message saying it's ok to use more channels may be delayed for a
     long time, such as 30s, because of the TCP stall waiting for the
     next retransmit.

     In that situation, a client may find making a new TCP connections
     and start Mux over it can get a new channel more quickly.  I
     don't know if, in that situation, it is better to allow
     optimistic channel setup requests on the existing TCP connection
     instead of a new TCP, or if there is no point because a stalled
     TCP would delay the request anyway.

     As with data flow control, I would suggest making the optimistic
     variation (setup requests with refusal and retry) an experimental
     extension, and the pessimistic variation the basic standard.
     Experiments may show if the optimistic extension is net positive
     or negative at high loads; it's not obvious to me which.

All the best,
-- Jamie

---

From: Takeshi Yoshino <[email-masked]>
Date: Thu, 14 Jun 2012 17:55:46 +0900

>> updated by further grants from the server.  (Very similar to the flow

I'm designing algorithm to realize this. My current idea is as follows.
Just a first strawman. It's very complicated.

- New channel window is a set of slots for new channel creation attempts
-- Each slot corresponds to one future/in-flight AddChannelRequest
-- Each slot (Slot_k) has pre-handshake quota (PQ_k)
-- When received, say, NewChannelQuota block, add a new slot. The new slot
has pre-handshake quota of 0
- When received, say, PreHandshakeQuota block, split it up and add to slots
so that PQ_k are leveled (older ones first) among all slots
- To issue an AddChannelRequest with channel ID X, the client picks oldest
unused slot (Slot_i) for it
- The client MAY send pre-handshake data for the channel X up to PQ_i
- When received the corresponding AddChannelResponse,
-- send quota for X is set to (PQ_i) - (total pre-handshake data sent) +
(initial send quota assigned by the AddChannelResponse)
-- Slot_i is removed from the new channel window

Goals are:

- make it able to increase the pre-handshake send quota for already
allocated slots
- give pre-handshake quota equally to all active slots
- carry over remaining pre-handshake quota into post-handshake quota
- deterministic, not affected by timing

---

From: "Arman Djusupov" <[email-masked]>
Date: Thu, 14 Jun 2012 12:58:54 +0300

The quota header in AddChannelResponse is not needed, the server can
supplement the client quota using normal flow control frames. This would
simplify it a bit. If the server needs to grant additional quota right after
the AddChannelResponse, it can send an FC block in the same frame with the
AddChannelResponse. The FC block format is more efficient than the literal
format of the AddChannelResponse header.

A more simple description would be that the client simply sets its quota to
the PQ-I value and continues using it until it gets an FC block from the
server that would increment it. The server keeps track of the number of
active slots on the client side so it knows the current PQ-I value and also
starts keeping track of the client quota based on the PQ-I value.

Why to split up the quota? This leave room for strange cases when the quota
is not divisible by the number of channels. Why not simply set or add a
value to each already allocated slot? 

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Thursday, June 14, 2012 11:56 AM
To: Jamie Lokier
Cc: Arman Djusupov; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

On Wed, Jun 13, 2012 at 7:18 PM, Takeshi Yoshino <[email-masked]>
wrote:

Good idea. I'll take it.

I'm designing algorithm to realize this. My current idea is as follows. Just
a first strawman. It's very complicated.

Goals are:

---

From: Takeshi Yoshino <[email-masked]>
Date: Fri, 15 Jun 2012 12:18:48 +0900

On Thu, Jun 14, 2012 at 6:58 PM, Arman Djusupov <[email-masked]> wrote:

> (initial send quota assigned by the AddChannelResponse)****
>
> ** **
>
> simplify it a bit. If the server needs to grant additional quota right
> after the AddChannelResponse, it can send an FC block in the same frame
> with the AddChannelResponse. The FC block format is more efficient than the
> literal format of the AddChannelResponse header.
>

OK

> ****
>
> - When received, say, PreHandshakeQuota block, split it up and add to
> slots so that PQ_k are leveled (older ones first) among all slots
>
> ** **
>
> Why to split up the quota? This leave room for strange cases when the
> quota is not divisible by the number of channels. Why not simply set or add
> a value to each already allocated slot?
>

I tried to make it able to gradually decrease PQ_i for new slots when the
server is overloaded.

If PreHandshakeQuota adds the same value to each allocated slot, PQ_i for a
new channel needs to be initialized to the same value as the other slots'
on NewChannelQuota. Otherwise, PQ_i values are in-balanced between the new
one and the others. Then, ... there's no way to  decrease PQ_i.

We may add a new channel with slightly smaller PQ_i to allow for
suppression. This works, but one of its cons is that we cannot level PQ_i
of allocated slots even when the server gets less loaded again because the
PreHandshakeQuota keeps high slots high and low slots low.

---

From: "Arman Djusupov" <[email-masked]>
Date: Fri, 15 Jun 2012 11:21:14 +0300

Since we go that far in flexibility why not just give the client a quota and
let it distribute it in the channels any way the client likes. This way the
client will be able to give a higher or lower priority to newly established
channels. The client will need to state the amount of quota it assigned to a
channel slot when sending an AddChannelRequest. So when receiving a
PreHandshakeQuota the client does not level it between available slots, but
uses a share of this quota later when creating a new channel. This would be
a simplified common quota.

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Friday, June 15, 2012 6:19 AM
To: Arman Djusupov
Cc: Jamie Lokier; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

OK

If PreHandshakeQuota adds the same value to each allocated slot, PQ_i for a
new channel needs to be initialized to the same value as the other slots' on
NewChannelQuota. Otherwise, PQ_i values are in-balanced between the new one
and the others. Then, ... there's no way to  decrease PQ_i.

We may add a new channel with slightly smaller PQ_i to allow for
suppression. This works, but one of its cons is that we cannot level PQ_i of
allocated slots even when the server gets less loaded again because the
PreHandshakeQuota keeps high slots high and low slots low.

---

From: Takeshi Yoshino <[email-masked]>
Date: Tue, 19 Jun 2012 14:49:16 +0900

On Fri, Jun 15, 2012 at 5:21 PM, Arman Djusupov <[email-masked]> wrote:

> Since we go that far in flexibility why not just give the client a quota
> and let it distribute it in the channels any way the client likes. This way
> the client will be able to give a higher or lower priority to newly
> established channels. The client will need to state the amount of quota it
> assigned to a channel slot when sending an AddChannelRequest. So when
> receiving a PreHandshakeQuota the client does not level it between
> available slots, but uses a share of this quota later when creating a new
> channel. This would be a simplified common quota.
>

I still wonder if grabbing per-channel basis quota control away from
server-side (which post-handshake quota allows for) makes sense or not.
Pre-handshake data processing may be designed similarly as post-handshake.

Algorithm based on your proposal would be like this:

- NC_WIN = 0
-- # of future/in-flight AddChannelRequest <= NC_WIN
-- When received, say, NewChannelQuota block, add the value to NC_WIN
- PQ = 0
-- When received, say, PreHandshakeQuota block, add the value to PQ
- To issue an AddChannelRequest with channel ID X
-- On AddChannelRequest, the client declares the amount of PQ to assign for
X (IQ_X)
-- PQ = PQ - IQ_X
-- The quota for channel X is initialized to be IQ_X (can be used for both
pre- and post-handshake data)
- When received the corresponding AddChannelResponse, NC_WIN = NC_WIN - 1

Very simple. Assignment to channels is done by client-side (different from
post-handshake). Am I understanding correctly?

---

From: Arman Djusupov <[email-masked]>
Date: Tue, 19 Jun 2012 10:06:34 +0300

Yes, that's correct.
 
Only I would do NC_WIN = NC_WIN - 1 before AddChannelResponse is received, to indicate that the slot is considered occupied when an AddChannelRequest is outstanding, since the client already uses the channel ID to send pre-handshake data.
 
Giving a client control over distributing the quota is not bad, since this value is limited by the common quota. E.g. if the client has a file to upload it could use all available quota when beginning to send it and before the AddChannelResponse is received. The server only cares that the client does not use more of buffer space than that granted to it; the server does not care how the client distributes the quota along the channels. Using this model does not prohibit leveling the quota along all channel slots.
 
For reasons of simplicity and API limitations, browsers may simply always level the quota along the channels, or they might prefer to slightly delay sending the AddChannelRequest to check what is the size of the first message being sent so that the AddChannelRequest with IQ_X = message size is sent along with the first message, to avoid an extra roundtrip.

With best regards,
Arman

On Jun 19, 2012, at 8:49 AM, Takeshi Yoshino wrote:

> Since we go that far in flexibility why not just give the client a quota and let it distribute it in the channels any way the client likes. This way the client will be able to give a higher or lower priority to newly established channels. The client will need to state the amount of quota it assigned to a channel slot when sending an AddChannelRequest. So when receiving a PreHandshakeQuota the client does not level it between available slots, but uses a share of this quota later when creating a new channel. This would be a simplified common quota. 
> 
> 
> I still wonder if grabbing per-channel basis quota control away from server-side (which post-handshake quota allows for) makes sense or not. Pre-handshake data processing may be designed similarly as post-handshake.
> 
> -- On AddChannelRequest, the client declares the amount of PQ to assign for X (IQ_X)
> -- PQ = PQ - IQ_X
> -- The quota for channel X is initialized to be IQ_X (can be used for both pre- and post-handshake data)
> Very simple. Assignment to channels is done by client-side (different from post-handshake). Am I understanding correctly?
>

---

From: Takeshi Yoshino <[email-masked]>
Date: Thu, 21 Jun 2012 21:26:42 +0900

On Tue, Jun 19, 2012 at 4:06 PM, Arman Djusupov <[email-masked]> wrote:

> For reasons of simplicity and API limitations, browsers may simply always
> level the quota along the channels, or they might prefer to slightly delay
> sending the AddChannelRequest to check what is the size of the first
> message being sent so that the AddChannelRequest with IQ_X = message size
> is sent along with the first message, to avoid an extra roundtrip.
>

Considering the concern Jamie showed, how about sending some FlowControl
frame variant indicating the end of pre-handshake data after pre-handshake
frames? The client consumes total pre-handshake data quota it has for the
new channel as it like. And then, sends the end-of-pre-handshake-data
frame. It can be after or before receiving AddChannelResponse for the
request. The server knows how much pre-handshake data quota has been spent
for the new channel attempt by summing the data size of frames before the
end-of-pre-handshake-data frame. Delaying AddChannelRequest is fine but not
so flexible enough to address the concern Jamie showed.

---

From: "Arman Djusupov" <[email-masked]>
Date: Fri, 22 Jun 2012 09:05:29 +0300

Hello Takeshi,

This will result in the protocol having two different stages of
communication. One stage before the handshake during which flow control
should be based on the common quota, and a second stage after the
end-of-pre-handshake-data frame is received during which flow control is
based on the logical channel quota. I'm ok with this solution, but I have
the impression that this is a bit of overkill.

It will be difficult to implement in a high concurrency multithreaded
environment. I can't say if there are any practical problems until I try
implementing it. But there might be difficulties that are not evident now.
In general it's becoming a bit more complex than simply working with a
self-assigned initial quota. 

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Thursday, June 21, 2012 3:27 PM
To: Arman Djusupov
Cc: Jamie Lokier; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

For reasons of simplicity and API limitations, browsers may simply always
level the quota along the channels, or they might prefer to slightly delay
sending the AddChannelRequest to check what is the size of the first message
being sent so that the AddChannelRequest with IQ_X = message size is sent
along with the first message, to avoid an extra roundtrip.

Considering the concern Jamie showed, how about sending some FlowControl
frame variant indicating the end of pre-handshake data after pre-handshake
frames? The client consumes total pre-handshake data quota it has for the
new channel as it like. And then, sends the end-of-pre-handshake-data frame.
It can be after or before receiving AddChannelResponse for the request. The
server knows how much pre-handshake data quota has been spent for the new
channel attempt by summing the data size of frames before the
end-of-pre-handshake-data frame. Delaying AddChannelRequest is fine but not
so flexible enough to address the concern Jamie showed.

---

From: Takeshi Yoshino <[email-masked]>
Date: Fri, 22 Jun 2012 15:18:29 +0900

As we're going to add, say, NewChannelQuotaUpdate command which replenishes
new channel quota, another idea is assigning a channel ID by the server on
NewChannelQuotaUpdate. This way, the server can give pre-handshake quota to
each potential channel slot by the same manner as post-handshake quota
assignment. Pre-handshake quota can be carried over seamlessly.

Takeshi

On Fri, Jun 22, 2012 at 3:05 PM, Arman Djusupov <[email-masked]> wrote:

> Hello Takeshi,****
> the impression that this is a bit of overkill.****
>
> ** **
>
> self-assigned initial quota. ****
>
> ** **
>
> With best regards,****
>
> Arman****
>
> ** **
>
> *From:* Takeshi Yoshino [mailto:[email-masked]]
> *Sent:* Thursday, June 21, 2012 3:27 PM
>
> *To:* Arman Djusupov
> *Cc:* Jamie Lokier; [email-masked]
> *Subject:* Re: [hybi] Multiplexing: Pre-AddChannelResponse quota****
>
> ** **
>
> On Tue, Jun 19, 2012 at 4:06 PM, Arman Djusupov <[email-masked]> wrote:*
> ***
>
> is sent along with the first message, to avoid an extra roundtrip.****
>
> ** **
>
> so flexible enough to address the concern Jamie showed.****
>

---

From: "Arman Djusupov" <[email-masked]>
Date: Fri, 22 Jun 2012 11:20:05 +0300

Good idea.

Hmm, actually this model can also work without the server assigning channel
IDs. The server simply needs to provide an initial quota to the slot and
then we have to allow the server to send FC frames to the client's logical
channel before the handshake is complete. So as soon as server receives an
AddChannelRequest and learns the channel ID, it would be sending normal FC
frames to the client. This way the FC would also work as usual both before
and after the handshake. The only difference from the current spec is that
the channel should be considered as established once an AddChannelRequest
received by the server. FC for the logical channel should start from the
moment when the server learns channel ID.

If the server sends a FC frame as soon as it receives an AddChannelRequest,
it should arrive to the client before the client uses all initial quota, so
the transmission should not stop. If there is a delay in communication it
would happen only due to the initial quota being too small for the
transmission rate. But such delays are inevitable both before and after
handshake. It depends entirely on the link speed and amount of quota
granted.

This way the client would be able to transmit as much as the server can
receive without waiting for an AddChannelResponse. I like this idea, it is
simple and would work fine.

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Friday, June 22, 2012 9:18 AM
To: Arman Djusupov
Cc: Jamie Lokier; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

Takeshi

Hello Takeshi,

With best regards,

Arman

To: Arman Djusupov

---

From: Jamie Lokier <[email-masked]>
Date: Fri, 22 Jun 2012 11:19:54 +0100

Arman Djusupov wrote:
>    Good idea.
> 
>    Hmm, actually this model can also work without the server assigning
>    channel IDs.

Yes, that's very useful in making the protocol simple without blocking
at any point.

As a general principle: "Initiator chooses id" removes delays in all
sorts of patterns, such as muxing, request-response, remote object
allocation, etc.

In this case the client is the initiator, however if there will ever
be channels initiated from the server side, the server should choose
channel id in that case.

>    The server simply needs to provide an initial quota to the
>    slot and then we have to allow the server to send FC frames to the
>    client’s logical channel before the handshake is complete. So as soon
>    as server receives an AddChannelRequest and learns the channel ID, it
>    would be sending normal FC frames to the client. This way the FC would
>    also work as usual both before and after the handshake. The only
>    difference from the current spec is that the channel should be
>    considered as established once an AddChannelRequest received by the
>    server. FC for the logical channel should start from the moment when
>    the server learns channel ID.
> 
>    If the server sends a FC frame as soon as it receives an
>    AddChannelRequest, it should arrive to the client before the
>    client uses all initial quota, so the transmission should not
>    stop. If there is a delay in communication it would happen only
>    due to the initial quota being too small for the transmission
>    rate. But such delays are inevitable both before and after
>    handshake. It depends entirely on the link speed and amount of
>    quota granted.
> 
>    receive without waiting for an AddChannelResponse. I like this idea, it
>    is simple and would work fine.

Looks very good to me :-)

Using elements of the established-channel protocol as much as possible
is key to a simple handshake and minimal delays.

It's also shorter to describe in specs, and shorter code.

Anything which improves the performance of established channels (such
as expanding the flow control window heuristically for link bandwidth
(like recent TCP does), choosing good windows, sharing memory among
channels etc.) will also improve the performance at the early stage.

Similar principles apply pre-handshake to the channel assignment
itself, which is why using the same kind of control for *number* of
channels assignable works quite well, and it also benefits from
similar heuristics.

(In principle round-trip delay elimination can go further up the chain
through WS, HTTP, TLS and even TCP setup, but various aspects of
specification make it difficult.)

-- Jamie

---

From: Takeshi Yoshino <[email-masked]>
Date: Fri, 22 Jun 2012 19:54:13 +0900

On Fri, Jun 22, 2012 at 5:20 PM, Arman Djusupov <[email-masked]> wrote:

> channel IDs. The server simply needs to provide an initial quota to the
> slot and then we have to allow the server to send FC frames to the client’s
> logical channel before the handshake is complete.
>

Without the server assigning some identifier for the new slot (doesn't need
to be the channel ID to be used after channel open, but some identifier),
we cannot match the slot and the pre-handshake FC frames.

Sorry but could you elaborate your idea? Maybe, you said here that we'll be
able to send FC after receiving AddChannelRequest and before sending back
AddChannelResponse?

What I had in my mind is like this:

(C) receives Physical channel server's opening handshake
(C) receives NewChannelSlot[ID=1]
(C) receives NewChannelSlot[ID=2]
(C) receives NewChannelSlot[ID=3]

Now (C) can issue three AddChannelRequests but may not send any
pre-handshake data.

(C) receives FlowControl[ID=1, quota=1024]
(C) receives FlowControl[ID=2, quota=1024]
(C) receives FlowControl[ID=3, quota=1024]

Now (C) is allowed to send pre-handshake data up to 1024 for each of
allocated slots.
Here, the client attempts to open a new logical channel using the first
allocated slot.

(C) sends AddChannelRequest[ID=1]
(C) sends TextData[len=512]
(C) receives AddChannelResponse[ID=1, success]
(C) receives NewChannelSlot[ID=4]
(C) receives FlowControl[ID=1, quota=1024]

Now channel 1 is open and its quota  is 1536.

---

From: Jamie Lokier <[email-masked]>
Date: Fri, 22 Jun 2012 13:17:38 +0100

Takeshi Yoshino wrote:
>    Without the server assigning some identifier for the new slot (doesn't
>    need to be the channel ID to be used after channel open, but some
>    identifier), we cannot match the slot and the pre-handshake FC frames.
>    Sorry but could you elaborate your idea? Maybe, you said here that
>    we'll be able to send FC after receiving AddChannelRequest and before
>    sending back AddChannelResponse?

Why not just send NewChannelSlots[ADD=3], instead of 3
NewChannelSlot messages?

The slot messages are wasteful if the server is happy to accept 1000
low-usage slots from the beginning.

>    Now (C) is allowed to send pre-handshake data up to 1024 for each of

Why not just send NewChannelSlots[ADD=3,PER_CHANNEL_QUOTA=1024]?

(Or SHARED_QUOTA, whatever seems to work best.)

>    (C) sends AddChannelRequest[ID=1]

Replace with:

    (C) sends AddChannelRequest[CLIENT_ASSIGNED_ID=1]

(where the ID is whatever the client says it should be - or it might
follow some rule such as incrementing from 1 each new one).

>    (C) sends TextData[len=512]

Yes.  The channel data quota on the client is now 512.

>    (C) receives AddChannelResponse[ID=1, success]

Yes.  But the ID is what the client assigned.  The server can also
send response data immediately after this, if it has some very
quickly.

>    (C) receives NewChannelSlot[ID=4]

Replace with:

    (C) receives NewChannelSlots[ADD=1,PER_CHANNEL_QUOTA=1024].

(Or it can be a flag in the AddChannelResponse parameters in the
common case where it's COUNT=1 and the data quotas haven't changed,
but that's just a special case to compress a message.)

This is the same method as flow control for bytes in a channel, but
for new channel counts.  Send out messages granting more room.

>    Now channel 1 is open and its quota  is 1536.

Yes.

So the main differences between your and my scheme here is:

  - the client assigns IDs
  - the server sends one count update, not a message for each slot

In both schemes, new channel assignment is "pessimistic" in the sense
that channel requests can't block the socket or get rejected at the
mux level.

If it turns out to that network scaling behaviour improves with
"optimistic" requests that can fail and be retried, it can be built on
top of this in various ways, such as NewChannelSlotsAck for when slots
are reduced (negative ADD, round trip before server is allowed to
block) or AddChannelDropped (client must retry, here or elsewhere, and
it's guaranteed the server did not act on the data sent; allows server
to remove quota immediately instead of round-trip).  However TCP works
fine without this sort of "quota retraction", using gradually
increasing window if needed to share memory, so I don't know that it's
useful and I would bet on low-quality clients reacting buggily to it.

-- Jamie

---

From: "Arman Djusupov" <[email-masked]>
Date: Fri, 22 Jun 2012 15:18:47 +0300

My idea was that the server can deliver the pre-handshake quotas using the
NewChannelSlot frame and update it only once it has received the
AddChannelRequest with the channel ID assigned by the client. The server
does not need to update this value often anyway, it is best to update it
once a new channel has been created. If the server sends the additional
quota using the FC frame as soon as it has received the AddChannelRequest,
then there will be no delay, granted that the pre-handshake-quota quota was
large enough.

So it would look like this:

(C) receives NewChannelSlot[pre-handshake-quota=1024]

(C) receives NewChannelSlot[pre-handshake-quota =1024]

(C) receives NewChannelSlot[pre-handshake-quota =1024]

Now (C) can issue three AddChannelRequests and may send some pre-handshake
data.

(C) sends AddChannelRequests(channelID = 2), AddChannelRequests(channelID =
3), AddChannelRequests(channelID = 4)  // server may assume the slots are
used in the queue order

As soon as the server receives the AddChannelRequests it sends a FC frame
for each channel without any delay and before even evaluating those
requests.

(C) receives FlowControl[ID=2, quota=2048]

(C) receives FlowControl[ID=3, quota=2048]

(C) receives FlowControl[ID=4, quota=2048]

Now (C) adds 2048 quota to each allocated logical channel while already
sending data so that it can send more data without delay. As long as the
server can receive more data it will be sending more FC frames with more
quota.

Here is an example that shows how the client attempts to open a new logical
channel using the first allocated slot.

--- Physical Channel Handshake-

(C) receives NewChannelSlot[pre-handshake-quota=1024]
// slot for a new channel

(C) receives FlowControl[ID=1, quota=1024]
// quota for first channel (irrelevant to  the sample, but has to be there)

-- Second Logical Channel 

(C) sends AddChannelRequest[ID=2]

(C) receives FlowControl[ID=2, quota=1024]
// channel#2 quota now equal to 1536

(C) receives AddChannelResponse[ID=2, success]

(C) receives FlowControl[ID=2, quota=1024]
// channel#2 quota now equal to 2560

We simply eliminate the pre-handshake quota and post-handshake quota. Flow
control starts from the first byte sent after sending the AddChannelRequest
irrespective of when or whether the AddChannelResponse is received. The
initial quota value is defined by the NewChannelSlot message and is
supplemented by normal FC frames with a channel ID that is equal to the one
specified by the AddChannelRequest.

In this case we don't need slot IDs. The next slot will always be the next
slot in the queue.

I don't think we need to update a slot quota before it is used, because in
order to use this functionality the server would have to broadcast new
quotas every time some buffer space is released. This will make it a
real-time "quota feed", I really don't think any server would spend
resources on keeping the client slot quotas up to date with the server
capacity. It's more reasonable to give a slot some nice initial quota value
and then update it as soon as possible once the client has used the slot.

With best regards,

Arman

From: Takeshi Yoshino [mailto:[email-masked]] 
Sent: Friday, June 22, 2012 1:54 PM
To: Arman Djusupov
Cc: Jamie Lokier; [email-masked]
Subject: Re: [hybi] Multiplexing: Pre-AddChannelResponse quota

Hmm, actually this model can also work without the server assigning channel
IDs. The server simply needs to provide an initial quota to the slot and
then we have to allow the server to send FC frames to the client's logical
channel before the handshake is complete.

Without the server assigning some identifier for the new slot (doesn't need
to be the channel ID to be used after channel open, but some identifier), we
cannot match the slot and the pre-handshake FC frames.

---

From: Takeshi Yoshino <[email-masked]>
Date: Mon, 25 Jun 2012 11:19:18 +0900

> Why not just send NewChannelSlots[ADD=3,PER_CHANNEL_QUOTA=1024]?
This is fine if we don't need a way to increase pre-handshake quota for the
slots after allocating them e.g. when the server gets more room for
processing after the allocation.

Yes.

---

From: Takeshi Yoshino <[email-masked]>
Date: Mon, 25 Jun 2012 11:29:34 +0900

OK, I understood your thoughts, Jamie, Arman.

I'll take in your idea.

On Fri, Jun 22, 2012 at 9:18 PM, Arman Djusupov <[email-masked]> wrote:

> I don’t think we need to update a slot quota before it is used, because in
> real-time “quota feed”, I really don’t think any server would spend
> capacity. It’s more reasonable to give a slot some nice initial quota value

---

From: Jamie Lokier <[email-masked]>
Date: Tue, 26 Jun 2012 23:28:30 +0100

Takeshi Yoshino wrote:
>    On Fri, Jun 22, 2012 at 9:17 PM, Jamie Lokier <[1][email-masked]>
>    wrote:
> 
>    This is fine if we don't need a way to increase pre-handshake quota for
>    the slots after allocating them e.g. when the server gets more room for

So how do you do it in your scheme - resend FlowControl for each slot?

In that case, do this:

   NewChannelSlots[ADD=0,PER_CHANNEL_QUOTA=2048]

I suggest the per-channel quota, is a single value available to all
new channels, not a different value per channel.  Does it make sense
to have different new-channel "sizes"?

ADD increments the available quota for new channels, while
PER_CHANNEL_QUOTA sets that, I guess.  It's not allowed to reduce the
data quota, unless we have an "optimistic" mechanism for retracting
flow control in other ways as well, which a hop-by-hop extension might
do.  The message is, in effect, a flow control allocation to each new
channel that hasn't been created yet.

However, I wonder, if it decides to have more memory, why would the
server increase the per-channel data quota instead of increasing the
number of available slots?  Is there a reason for one over the other?

There may still a case for a shared pool of pre-handshake data quota
instead, but it would need to be carefully done because memory can't
be carved up arbitrarily; a per-channel overhead factor would be needed.

-- Jamie

---

From: Takeshi Yoshino <[email-masked]>
Date: Wed, 27 Jun 2012 12:16:06 +0900

> So how do you do it in your scheme - resend FlowControl for each slot?

Yes

> new channels, not a different value per channel.

This also works.

>  Does it make sense

No. I don't think it makes sense.

I suggested that for leveling imbalanced quotas. Imbalance of quotas
happens when the server replenishes new channel slots but with smaller
quota due to temporary decrease of processing capacity. After some seconds,
the capacity may recover. Then, such a flexible pre-handshake quota
replenishing method allows for leveling them (remaining old slots and the
newly allocated slots with smaller quota) again.

That's the reason I've put the idea on the table, but I can live without
this functionality.

> PER_CHANNEL_QUOTA sets that, I guess.

Yes.

>  It's not allowed to reduce the

Yes. I'd clarify "hasn't been created yet" by "has not sent
AddChannelResponse" for server-side and "has not received
AddChannelResponse" for client-side.

> number of available slots?  Is there a reason for one over the other?

I have no idea. It should depend on the app's requirements.