Thinking about flow control

Showing 1-192 of 192 messages
Thinking about flow control Roberto Peon 5/17/12 1:44 PM
All--

We've been having a number of private conversations about flow control.
The flow control that has been deployed in SPDY/3 seems to work, but it has some definite flaws and suboptimalities.
Basically, it only allows for per-stream flow control.

Per-stream flow control is certainly necessary; without it we'd have head-of-line blocking or infinite-buffering requirements at proxies, which is untenable.
On its, own, however, if we are still worried about infinite buffering and wish to increase the stream limit, per-stream flow control isn't enough. 

So, we probably need per-connection flow-control so that we can manage the total amount of buffering necessary, while still allowing for large enough per-stream flow-control windows to ensure that we can at least fill up the TCP connection.


We're hoping to get comments in over the next two weeks (at most), and then begin spec revisions and possibly experimentation with new flow control in (and for) SPDY/4.

So... comments? Ideas?
-=R
Re: [spdy-dev] Thinking about flow control agl 5/17/12 1:47 PM
On Thu, May 17, 2012 at 4:44 PM, Roberto Peon <fe...@google.com> wrote:
> So, we probably need per-connection flow-control so that we can manage the
> total amount of buffering necessary

Why is TCP's per-connection flow control insufficient?


Cheers

AGL
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/17/12 1:54 PM
one reason is spdy flow control only covers data frames.. so a server
could protect itself from too much concurrent upload without impacting
its ability to serve get/etc..



Re: [spdy-dev] Thinking about flow control Patrick McManus 5/17/12 2:19 PM
On Thu, 2012-05-17 at 13:44 -0700, Roberto Peon wrote:

>
>
> We're hoping to get comments in over the next two weeks (at most), and
> then begin spec revisions and possibly experimentation with new flow
> control in (and for) SPDY/4.
>
>
> So... comments? Ideas?
> -=R

I'm certainly in favor of doing something as the new flow control params
as used with the small windows currently on google.com definitely slow
down certain scenarios. If an aggregate session window allows the server
to safely use larger per-stream windows then that's a good fix.

I'd suggest that the new global window can both shrink and expand
(presumably via an explicit settings frame analogous to initial window),
and that per stream window_updates be changed to allow shrinking of the
window not just expanding it.

use case for that - its hard to know what the BDP really is, so if you
want fully streamed transfer its tempting to set the window extremely
large so spdy flow control is not the choke point.. if for some reason
the local data sink stops accepting data temporarily you can slam the
window shut with a negative delta and only actually end up buffering
~BDP of data instead of "extremely large".

-Patrick

Re: [spdy-dev] Thinking about flow control Roberto Peon 5/17/12 2:27 PM


Agreed. In all cases where we overestimate, we may cause HOL blocking, but that is always true so long as we're on top of TCP.

One other thing that I was thinking about was that we could have default window sizes which differed based on the stream priority.
We'd react in hopefully one-RTT, so the question there is: Is it worth the additional complexity given the addition of the connection-based flow-control?

-=R
 

-Patrick


Re: [spdy-dev] Thinking about flow control Tatsuhiro Tsujikawa 5/17/12 6:35 PM


2012/05/18 6:19 "Patrick McManus" <mcm...@ducksong.com>:

Do you mean use only per-connection flow control?
Then +1.
It achieves the control of total number of buffering, which is the very issue the flow control was introduced.

Re: [spdy-dev] Thinking about flow control Patrick McManus 5/18/12 4:54 AM

> Do you mean use only per-connection flow control?
> Then +1.
> It achieves the control of total number of buffering, which is the
> very issue the flow control was introduced.
>

No - I'm suggesting we need both per-session and per-stream flow
control.

We need per stream flow control because different data sinks in the set
of multiplexed streams may consume data at a different rate, and you
want to be able to stop buffering one without impacting the other.

On the client side this could be a plugin vs a core rendering component
- or even a media component that has had the pause button pushed. A
proxy is obviously connected in diverse ways (with diverse bandwidth) on
the back side while multiplexing on the front, and an origin server
might be multiplexing 1 receiver that is writing to a big data warehouse
and one that is using its input for lookup in a light in memory hash.

If we add a session wide window - then we can do this stream control
with the windowing we have, or honestly we could do it with per stream
txon/txoff and that might lead to better quality implementations.


Re: [spdy-dev] Thinking about flow control Simone Bordet 5/18/12 5:12 AM
Hi,

On Thu, May 17, 2012 at 10:44 PM, Roberto Peon <fe...@google.com> wrote:
> All--
>
> We've been having a number of private conversations about flow control.
> The flow control that has been deployed in SPDY/3 seems to work, but it has
> some definite flaws and suboptimalities.
> Basically, it only allows for per-stream flow control.
>
> Per-stream flow control is certainly necessary; without it we'd have
> head-of-line blocking or infinite-buffering requirements at proxies, which
> is untenable.

Yes.

> On its, own, however, if we are still worried about infinite buffering and
> wish to increase the stream limit, per-stream flow control isn't enough.

I am not sure I understand this paragraph. Can you expand ?

The current SETTINGS for the initial window size, when received,
applies to all active streams, so it's already more at the connection
level rather than at the stream level (i.e. you cannot update the
initial window size of only one stream).

Thanks,

Simon
--
http://cometd.org
http://intalio.com
http://bordet.blogspot.com
----
Finally, no matter how good the architecture and design are,
to deliver bug-free software with optimal performance and reliability,
the implementation technique must be flawless.   Victoria Livschitz
Re: [spdy-dev] Thinking about flow control Peter Lepeska 5/18/12 6:39 AM
"Essentially, the proxy needs a way to advertise the amount of room it has in its outgoing buffers, which it can't easily do with TCP's flow-control."

Yes it can. When a proxy server's buffer grows to a certain threshold, it just stops posting buffers to the receive socket connected to the web server. When this happens the TCP stack buffer fills up (since no packets are being pulled off by the user mode process), and TCP starts sending smaller receive windows in its ACKs to the web server, which slows down its send rate. This seems fine to me.

I'm still not understanding what problem we are trying to solve by adding another layer of flow control to the TCP session.

Peter

On Thu, May 17, 2012 at 5:00 PM, Roberto Peon <fe...@google.com> wrote:
TCP's flow-control alone would allow HOL blocking to occur in cases where the proxy->server connections were full for only some streams because the userspace process of the server doesn't control advertisements of its ingress window.
Essentially, the proxy needs a way to advertise the amount of room it has in its outgoing buffers, which it can't easily do with TCP's flow-control.

-=R

On Thu, May 17, 2012 at 1:47 PM, Adam Langley <a...@chromium.org> wrote:
On Thu, May 17, 2012 at 4:44 PM, Roberto Peon <fe...@google.com> wrote:
> So, we probably need per-connection flow-control so that we can manage the
> total amount of buffering necessary

Why is TCP's per-connection flow control insufficient?


Cheers

AGL


Re: [spdy-dev] Thinking about flow control Ryan Hamilton 5/18/12 8:34 AM


On Fri, May 18, 2012 at 6:39 AM, Peter Lepeska <bizzb...@gmail.com> wrote:
"Essentially, the proxy needs a way to advertise the amount of room it has in its outgoing buffers, which it can't easily do with TCP's flow-control."

Yes it can. When a proxy server's buffer grows to a certain threshold, it just stops posting buffers to the receive socket connected to the web server. When this happens the TCP stack buffer fills up (since no packets are being pulled off by the user mode process), and TCP starts sending smaller receive windows in its ACKs to the web server, which slows down its send rate. This seems fine to me.

I'm still not understanding what problem we are trying to solve by adding another layer of flow control to the TCP session.

Imagine a browser has a SPDY session open to a proxy.  In this session, imagine that there is a large POST upload in progress.  Further, imagine that the server that the proxy needs to relay the POST data to is slower than than client.  At this point the proxy needs to either buffer indefinitely (which clearly does not scale) or it needs to pause the upload.  If the only flow control knob at the proxy's disposal is at the TCP level, it can clearly pause the entire session.  However, this will prevent any other streams from making any  progress.  You might be surprised how often this situation comes up.

You can also spin the example around, as Patrick did earlier, and imagine that the server is using a stream to send streaming media to the client...  Same potential problem.

Cheers,

Ryan

Re: [spdy-dev] Thinking about flow control Simone Bordet 5/18/12 9:25 AM
Hi,

On Fri, May 18, 2012 at 5:34 PM, Ryan Hamilton <r...@google.com> wrote:
>
>
> On Fri, May 18, 2012 at 6:39 AM, Peter Lepeska <bizzb...@gmail.com> wrote:
>>
>> "Essentially, the proxy needs a way to advertise the amount of room it has
>> in its outgoing buffers, which it can't easily do with TCP's flow-control."
>>
>> Yes it can. When a proxy server's buffer grows to a certain threshold, it
>> just stops posting buffers to the receive socket connected to the web
>> server. When this happens the TCP stack buffer fills up (since no packets
>> are being pulled off by the user mode process), and TCP starts sending
>> smaller receive windows in its ACKs to the web server, which slows down its
>> send rate. This seems fine to me.
>>
>> I'm still not understanding what problem we are trying to solve by adding
>> another layer of flow control to the TCP session.
>
>
> Imagine a browser has a SPDY session open to a proxy.  In this session,
> imagine that there is a large POST upload in progress.  Further, imagine
> that the server that the proxy needs to relay the POST data to is slower
> than than client.  At this point the proxy needs to either buffer
> indefinitely (which clearly does not scale) or it needs to pause the upload.
>  If the only flow control knob at the proxy's disposal is at the TCP level,
> it can clearly pause the entire session.  However, this will prevent any
> other streams from making any  progress.  You might be surprised how often
> this situation comes up.

I do not follow. The proxy should flow-control the browser.

> You can also spin the example around, as Patrick did earlier, and imagine
> that the server is using a stream to send streaming media to the client...
>  Same potential problem.

Same solution: the proxy flow-controls the server.

Back to upload example: browser sends a window-sized data frame, and
can't send more until it gets a window update.
Proxy receives the data frame, forwards to upstream server.
If the server is SPDY aware, the proxy will get a window update, and
upon receiving that, it sends the window update to the browser, which
will send another data frame.
If the server is not SPDY aware, the proxy writes to it and only when
the write is fully completed (to leverage TCP backpressure), then the
proxy sends a window update to the browser.

Similarly for server to client.

I feel I am missing something, but can't see it ?
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 5/18/12 9:33 AM


Perhaps I was confused.  I was responding to your question:

> I'm still not understanding what problem we are trying to solve by adding
> another layer of flow control to the TCP session.

To do this, I presented two situations where a browser talking to a proxy would want to stop a single stream in a SPDY session but allow other SPDY streams to progress.  TCP-only flow control does not provide this facility.  However, you replied to my message with this:

> If the server is SPDY aware, the proxy will get a window update, and
> upon receiving that, it sends the window update to the browser, which
> will send another data frame.
> If the server is not SPDY aware, the proxy writes to it and only when
> the write is fully completed (to leverage TCP backpressure), then the
> proxy sends a window update to the browser.

Both of these examples include WINDOW_UPDATE frames which are, of course, at the SPDY layer, not the TCP layer.  I think I don't understand the question you are asking?  Do you agree with the need for a particular stream in a SPDY session to be paused which others can proceed?

Cheers,

Ryan

 
Re: [spdy-dev] Thinking about flow control Simone Bordet 5/18/12 9:44 AM
Hi,

On Fri, May 18, 2012 at 6:33 PM, Ryan Hamilton <r...@google.com> wrote:
> Perhaps I was confused.  I was responding to your question:
>
>> I'm still not understanding what problem we are trying to solve by adding
>> another layer of flow control to the TCP session.

Was not me, was Peter :)

> To do this, I presented two situations where a browser talking to a proxy
> would want to stop a single stream in a SPDY session but allow other SPDY
> streams to progress.  TCP-only flow control does not provide this facility.

Sure.

>  However, you replied to my message with this:
>
>> If the server is SPDY aware, the proxy will get a window update, and
>> upon receiving that, it sends the window update to the browser, which
>> will send another data frame.
>> If the server is not SPDY aware, the proxy writes to it and only when
>> the write is fully completed (to leverage TCP backpressure), then the
>> proxy sends a window update to the browser.
>
> Both of these examples include WINDOW_UPDATE frames which are, of course, at
> the SPDY layer, not the TCP layer.  I think I don't understand the question
> you are asking?  Do you agree with the need for a particular stream in a
> SPDY session to be paused which others can proceed?

I agree, and that's what the current flow-control is for.

I do not clearly see the case for a SPDY session level flow control,
in addition to SPDY stream level flow control.
See also my other email in reply to Roberto asking for more details.

We just want be part of the loop: we can't comment if we don't
understand the use case :)

Thanks,
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 5/18/12 10:05 AM


On Fri, May 18, 2012 at 9:44 AM, Simone Bordet <sbo...@intalio.com> wrote:
Hi,

On Fri, May 18, 2012 at 6:33 PM, Ryan Hamilton <r...@google.com> wrote:
> Perhaps I was confused.  I was responding to your question:
>
>> I'm still not understanding what problem we are trying to solve by adding
>> another layer of flow control to the TCP session.

Was not me, was Peter :)

Doh!  Well, that explains why I was confused :>  Sorry about that.  I'll let the other comment further on the session-level flow control debate.

Cheers,

Ryan
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/18/12 10:09 AM
On Fri, 2012-05-18 at 18:44 +0200, Simone Bordet wrote:

> I do not clearly see the case for a SPDY session level flow control,
> in addition to SPDY stream level flow control.

My understanding is that giving every stream a window equal to
session-buffers-available represents a scary overcommitment for the
server if every stream decided to utilize it at the same time. It also
creates an unwelcome incentive to minimize the number of parallel
streams.

Likewise, dividing the session buffers available into small shares for
each stream often results in some streams easily running out of window
space while other streams waste their allocations.

You'll see that google.com has been using small 12KB initial windows -
which are too small to allow full rate uploads for many common BDPs. The
flow control proposal arises out of the need to fix that bottleneck
while still informing the client of the server's available bufferspace
(which is presumably > 12KB).

Having 2 levels of flow control lets you separate the concerns: the
session value is about total buffers available, the per-stream value is
about letting different streams proceed at different rates (and that's
why I think it can be done with xon/xoff in the presence of a session
window).

-Patrick

Re: [spdy-dev] Thinking about flow control Tatsuhiro Tsujikawa 5/18/12 10:14 AM
Thank you for answering.
I understand that stream sink has different consume rate.
Then we need a way to tell the other endpoint the initial window size
for each stream, no?
In the SPDY/3 spec, SETTINGS frame sets initial window size for all
streams in a session.
The one good point of introducing per-session flow control is that we
can use larger
initial window size for stream so that flow control does not slow down
the transfer.
If the endpoint know the particular stream sink is slow, then it has
to tell the other endpoint about it by shrinking window size for it.
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 5/18/12 10:17 AM
Right, that is what the WINDOW_UPDATE frame is for.  It changes the window size for a particular stream.

Cheers,

Ryan

Re: [spdy-dev] Thinking about flow control Tatsuhiro Tsujikawa 5/18/12 10:25 AM
But WINDOW_UPDATE delta-window-size only allows positive value:

Delta-Window-Size: The additional number of bytes that the sender can
transmit in addition to existing remaining window size. The legal
range for this field is 1 to 2^31 - 1 (0x7fffffff) bytes.

My concern is that in SPDY/3, all streams have the same initial window
size, for example, 64KB.
We can increase window size by WINDOW_UPDATE (I'm not sure we can exceed initial
window size by sending WINDOW_UPDATE), but we cannot decrease window
size by that frame.

Tatsuhiro

> Cheers,
>
> Ryan
>
Re: [spdy-dev] Thinking about flow control William Chan 5/18/12 10:26 AM
There is no negative delta currently in the SPDY/3 spec:
"Delta-Window-Size: The additional number of bytes that the sender can transmit in addition to existing remaining window size. The legal range for this field is 1 to 2^31 - 1 (0x7fffffff) bytes."
 

-Patrick


Re: [spdy-dev] Thinking about flow control Mike Belshe 5/18/12 10:30 AM
Is there data that accompanies this claim?

I'm mostly siding with Langley's question - that TCP's flow control should work for the overall layer.  Its simple and should suffice just fine.  It sounds like you're trying to flow control between multiple systems now.  (e.g. client -> proxy -> backend server).  This is a mistake - in the end, this will be a mistake - its over-optimizing for the proxy at the expense of the endpoints, because the only way to do this is to add round trips of latency onto the user.

I'll again caution against thinking flow control is easy.  It sounds easy, but its complicated with really subtle implications.

Mike


On Thu, May 17, 2012 at 1:44 PM, Roberto Peon <fe...@google.com> wrote:

Re: [spdy-dev] Thinking about flow control William Chan 5/18/12 10:32 AM
Just to clarify, you don't have to *shrink* the window size per-se, but just not send more WINDOW_UPDATEs, or send ones with smaller deltas.
 
>
>
> Right, that is what the WINDOW_UPDATE frame is for.  It changes the window
> size for a particular stream.
>

But WINDOW_UPDATE delta-window-size only allows positive value:

Delta-Window-Size: The additional number of bytes that the sender can
transmit in addition to existing remaining window size. The legal
range for this field is 1 to 2^31 - 1 (0x7fffffff) bytes.

My concern is that in SPDY/3, all streams have the same initial window
size, for example, 64KB.
We can increase window size by WINDOW_UPDATE (I'm not sure we can exceed initial
window size by sending WINDOW_UPDATE), but we cannot decrease window
size by that frame.

Tatsuhiro

> Cheers,
>
> Ryan
>

Re: [spdy-dev] Thinking about flow control Patrick McManus 5/18/12 10:37 AM
On Fri, 2012-05-18 at 10:26 -0700, William Chan (陈智昌) wrote:
>        
>         I'd suggest that the new global window can both shrink and
>         expand
>         (presumably via an explicit settings frame analogous to
>         initial window),
>         and that per stream window_updates be changed to allow
>         shrinking of the
>         window not just expanding it.
>        
>         use case for that - its hard to know what the BDP really is,
>         so if you
>         want fully streamed transfer its tempting to set the window
>         extremely
>         large so spdy flow control is not the choke point.. if for
>         some reason
>         the local data sink stops accepting data temporarily you can
>         slam the
>         window shut with a negative delta and only actually end up
>         buffering
>         ~BDP of data instead of "extremely large".
>
>
> There is no negative delta currently in the SPDY/3 spec:
> "Delta-Window-Size: The additional number of bytes that the sender can
> transmit in addition to existing remaining window size. The legal
> range for this field is 1 to 2^31 - 1 (0x7fffffff) bytes."
>  

right! that's why I said.. "window_update be changed to allow
shrinking".. :)

But I'm now thinking that, assuming a new per-session window, the
per-stream windows can be replaced with simpler per-stream xon/xoff
notifications. You don't have to worry about sizing those to network
conditions, so it will be more robust.





Re: [spdy-dev] Thinking about flow control Mike Belshe 5/18/12 10:38 AM


On Fri, May 18, 2012 at 10:09 AM, Patrick McManus <mcm...@ducksong.com> wrote:
On Fri, 2012-05-18 at 18:44 +0200, Simone Bordet wrote:

> I do not clearly see the case for a SPDY session level flow control,
> in addition to SPDY stream level flow control.

My understanding is that giving every stream a window equal to
session-buffers-available represents a scary overcommitment for the
server if every stream decided to utilize it at the same time. It also
creates an unwelcome incentive to minimize the number of parallel
streams.

Likewise, dividing the session buffers available into small shares for
each stream often results in some streams easily running out of window
space while other streams waste their allocations.

You'll see that google.com has been using small 12KB initial windows -
which are too small to allow full rate uploads for many common BDPs. The
flow control proposal arises out of the need to fix that bottleneck
while still informing the client of the server's available bufferspace
(which is presumably > 12KB).

The 64KB default is supposed to make flow control so rare that it almost never gets in the way while also providing a reasonable backstop.

One thing I hate about SPDY flow control is it gives too much control to the proxy (similar to how we don't want proxies to be able to turn off compression at the user's expense).   I hope Chrome and Firefox implement a minimum window size clamp of 32KB or something to prevent these shenanigans.

Mike



Having 2 levels of flow control lets you separate the concerns: the
session value is about total buffers available, the per-stream value is
about letting different streams proceed at different rates (and that's
why I think it can be done with xon/xoff in the presence of a session
window).

-Patrick


Re: [spdy-dev] Thinking about flow control William Chan 5/18/12 10:39 AM
Does this work? How do you know they've received the xoff notification? Do we need sequence numbers in streams? How do you detect a broken peer so you can send them an error?
 

Re: [spdy-dev] Thinking about flow control Patrick McManus 5/18/12 10:53 AM
On Fri, 2012-05-18 at 10:38 -0700, Mike Belshe wrote:

>
> The 64KB default is supposed to make flow control so rare that it
> almost never gets in the way while also providing a reasonable
> backstop.
>

it's hard to square that rarity at 64KB with the entire presence of the
TCP window scaling option which is needed past the same threshold.

just 8mbit/sec at 100ms of latency needs 100KB of BDP. That's hardly a
corner case, right?




Re: [spdy-dev] Thinking about flow control Patrick McManus 5/18/12 11:01 AM
On Fri, 2012-05-18 at 10:39 -0700, William Chan (陈智昌) wrote:

>
> Does this work? How do you know they've received the xoff
> notification?

you can't verify it, other than at some extreme point as the total
session window provides the real backstop. but when do you really care?

do you really have a partitioned set of resources available to some
streams but not others (in which case I agree, we need per stream
windows), or do you just want to pushback and stop the sending asap (in
which case xoff ought to be sufficient).

For the most part the resource in question is ram and ram is mostly
fungible.



Re: [spdy-dev] Thinking about flow control William Chan 5/18/12 11:01 AM
One thing that Roberto neglected to mention from our private conversations is also trying to improve latency, and to what degree flow control is useful here. Let me call your attention to a few points:

* SPDY/3 is faster than SPDY/2 for *some* webpages - Google has data on some of our properties to support this. We don't have data (yet) on cases where it is hurting our page load times. But don't take that to mean that that could not happen.
  - It turns out that you may incur bufferbloat by returning responses too quickly. SPDY/3 (as a side-effect) helps fight the problem due to per-stream flow control windows that restrain streams. Then if you get a high priority resource request later (let's say there's a script at the bottom of a document behind a gazillion large images), it won't be stuck behind all the other data in the bloated buffers.
  - Obviously, if the flow control windows are too small, then we're not filling the pipe as quickly as we could, and thus flow control can make certain pages *slower*.
* We don't have data on what percent of the web would see improvements with the current 64k window size, and what percent would have no impact, and what percent would get slower. It'd be interesting to see.
* Note that the original goal for flow control was to better manage buffers (rather than rely on TCP flow control, which would lead to HoL blocking), not prevent this bufferbloat.
* Note that just because there is space in the peer's per-stream rwin, it does not mean that a sender *has* to use that space. It theoretically could self-throttle if it expects that there is bufferbloat (maybe examine inter-packet arrival times?).
* But if the receiver believes the sender has a naive implementation, perhaps it's better to force the sender not to cause bufferbloat by constraining it with smaller window sizes via SETTINGS for per-stream window sizes. Or, perhaps better would be to do so via theoretical SPDY/4 per-session flow control window sizes.
* Also note that individual streams *can* have different rwins. You control them individually via WINDOW_UPDATE deltas. Why would you want to do this? How about long-lived streams vs short-lived streams (the current common case). Long-lived streams like big downloads/uploads or tunneling (SPDY over SPDY for example) may require different window sizes.
* These considerations all become more complicated given networks with higher variance in relevant characteristics, like mobile networks.

Anyway, I just wanted to point out that the implementation choices are complicated. It'd be great to hear discussion from folks (and more data if possible) about what good implementations *should* do.

On Thu, May 17, 2012 at 1:44 PM, Roberto Peon <fe...@google.com> wrote:
All--

We've been having a number of private conversations about flow control.
The flow control that has been deployed in SPDY/3 seems to work, but it has some definite flaws and suboptimalities.
Basically, it only allows for per-stream flow control.

Per-stream flow control is certainly necessary; without it we'd have head-of-line blocking or infinite-buffering requirements at proxies, which is untenable.
On its, own, however, if we are still worried about infinite buffering and wish to increase the stre
...
Re: [spdy-dev] Thinking about flow control William Chan 5/18/12 11:11 AM
On Fri, May 18, 2012 at 11:01 AM, Patrick McManus <mcm...@ducksong.com> wrote:
On Fri, 2012-05-18 at 10:39 -0700, William Chan (陈智昌) wrote:

>
> Does this work? How do you know they've received the xoff
> notification?

you can't verify it, other than at some extreme point as the total
session window provides the real backstop. but when do you really care?

do you really have a partitioned set of resources available to some
streams but not others (in which case I agree, we need per stream
windows), or do you just want to pushback and stop the sending asap (in
which case xoff ought to be sufficient).

I'm not exactly clear on what you mean by partitioned set of resources available to some streams but not others, but if I understand correctly, then yes, I suspect that this can happen, in particular with proxies. If you don't agree, then perhaps I need more clarity on what you mean.
 
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/18/12 11:18 AM
On Fri, 2012-05-18 at 11:11 -0700, William Chan (陈智昌) wrote:

>
> I'm not exactly clear on what you mean by partitioned set of resources
> available to some streams but not others, but if I understand
> correctly, then yes, I suspect that this can happen, in particular
> with proxies. If you don't agree, then perhaps I need more clarity on
> what you mean.
>  

>

you have a session window of N for M streams.

do you really care if 1 stream consumes more than 1/Mth of that, as long
as the session doesn't exceed N? (or even 1/2 or whatever..) I do
understand the need to give feedback to individual streams that they
shouldn't send because that data won't be acked right away (thus xoff).

from my pov the peer has been given a quota of N, how they want to split
that up can be up to them.

I don't hate per stream windows, its just a knob that's hard to set
right so if it can be removed that's a good thing. Maybe it can't be
removed :)

Re: [spdy-dev] Thinking about flow control Peter Lepeska 5/18/12 11:35 AM
Hi Ryan,

I understand why SPDY needs to do per stream flow control. That part makes sense to me and is well illustrated by your example. But I thought this thread was about adding another layer of flow control to the TCP session itself. That part seems redundant with what TCP is already doing.

Thanks,

Peter

On Fri, May 18, 2012 at 11:34 AM, Ryan Hamilton <r...@google.com> wrote:


On Fri, May 18, 2012 at 6:39 AM, Peter Lepeska <bizzb...@gmail.com> wrote:
"Essentially, the proxy needs a way to advertise the amount of room it has in its outgoing buffers, which it can't easily do with TCP's flow-control."

Yes it can. When a proxy server's buffer grows to a certain threshold, it just stops posting buffers to the receive socket connected to the web server. When this happens the TCP stack buffer fills up (since no packets are being pulled off by the user mode process), and TCP starts sending smaller receive windows in its ACKs to the web server, which slows down its send rate. This seems fine to me.

I'm still not understanding what problem we are trying to solve by adding another layer of flow control to the TCP session.

Imagine a browser has a SPDY session open to a proxy.  In this session, imagine that there is a large POST upload in progress.  Further, imagine that the server that the proxy needs to relay the POST data to is slower than than client.  At this point the proxy needs to either buffer indefinitely (which clearly does not scale) or it needs to pause the upload.  If the only flow control knob at the proxy's disposal is at the TCP level, it can clearly pause the entire session.  However, this will prevent any ot
...
Re: [spdy-dev] Thinking about flow control Simone Bordet 5/19/12 10:29 AM
Hi,

On Fri, May 18, 2012 at 8:18 PM, Patrick McManus <mcm...@ducksong.com> wrote:
> you have a session window of N for M streams.
>
> do you really care if 1 stream consumes more than 1/Mth of that, as long
> as the session doesn't exceed N? (or even 1/2 or whatever..) I do
> understand the need to give feedback to individual streams that they
> shouldn't send because that data won't be acked right away (thus xoff).
>
> from my pov the peer has been given a quota of N, how they want to split
> that up can be up to them.
>
> I don't hate per stream windows, its just a knob that's hard to set
> right so if it can be removed that's a good thing. Maybe it can't be
> removed :)

What do you suggest to avoid that one stream that takes 90% of N does
not starve other streams (e.g. I am streaming a movie, but it's
boring, so I want to do a little browsing meanwhile) ?
Also, you seem to suggest a mechanism to increase the per-stream
window (that starts at a default < N, but eventually may increase up
to N), right ?
While for decreasing the per-stream window you suggest negative window updates.

I am worried about the fact that there may be the need for some
inter-stream communication to adjust the per-stream window size (e.g.
stream1 takes most of N, but as soon as another transfer is requested,
stream1 needs to be shrunk in order to give some room to stream2), but
perhaps I am not understanding it right.

Thanks,

Simon
--
http:/...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/19/12 6:30 PM
On 5/19/2012 1:29 PM, Simone Bordet wrote:
> Hi,
>
> On Fri, May 18, 2012 at 8:18 PM, Patrick McManus<mcm...@ducksong.com>  wrote:
>> you have a session window of N for M streams.
>>
>> do you really care if 1 stream consumes more than 1/Mth of that, as long
>> as the session doesn't exceed N? (or even 1/2 or whatever..) I do
>> understand the need to give feedback to individual streams that they
>> shouldn't send because that data won't be acked right away (thus xoff).
>>
>> from my pov the peer has been given a quota of N, how they want to split
>> that up can be up to them.
>>
>> I don't hate per stream windows, its just a knob that's hard to set
>> right so if it can be removed that's a good thing. Maybe it can't be
>> removed :)
> What do you suggest to avoid that one stream that takes 90% of N does
> not starve other streams (e.g. I am streaming a movie, but it's
> boring, so I want to do a little browsing meanwhile) ?

If you send tx-off when you pause the movie then you'll end up buffering
BDP. (or less if it isn't sending at line rate).

If, instead of txon/txoff, you had a per-stream-window smaller than BDP
then the stream can never flow at line rate, almost by definition. And
you would of course buffer less for that one stream. I don't think the
risk of accidentally constraining the transfer rate is worth that, but
it would be the argument in favor of per stream windows.

If, instead of txon/txoff, you had a per-stream window greater than BDP
the stream would buffer more than BDP before it was stopped. This could
be mitigated down to BDP if we had negative deltas.

BDP is very hard to know - so its hard to make the per stream window
size choice accurately as an implementor and that lets people
accidentally slow things down without a lot of insight into why.  I've
definitely already seen this once with spdy/3 and I suspect the more
chances there are to select window sizes the more often they will be
selected too small.




> Also, you seem to suggest a mechanism to increase the per-stream
> window (that starts at a default<  N, but eventually may increase up
> to N), right ?
> While for decreasing the per-stream windo...
Re: [spdy-dev] Thinking about flow control Simone Bordet 5/21/12 8:14 AM
Hi,

On Sun, May 20, 2012 at 3:30 AM, Patrick McManus <mcm...@ducksong.com> wrote:
> If you send tx-off when you pause the movie then you'll end up buffering
> BDP. (or less if it isn't sending at line rate).

But I am not pausing the movie.
I am watching the movie, but meanwhile I start a big download, for example.
How do you transfer part of the session window taken by the movie
stream to the download stream ?

> If, instead of txon/txoff, you had a per-stream-window smaller than BDP then
> the stream can never flow at line rate, almost by definition. And you would
> of course buffer less for that one stream. I don't think the risk of
> accidentally constraining the transfer rate is worth that, but it would be
> the argument in favor of per stream windows.
>
> If, instead of txon/txoff, you had a per-stream window greater than BDP the
> stream would buffer more than BDP before it was stopped. This could be
> mitigated down to BDP if we had negative deltas.
>
> BDP is very hard to know - so its hard to make the per stream window size
> choice accurately as an implementor and that lets people accidentally slow
> things down without a lot of insight into why.  I've definitely already seen
> this once with spdy/3 and I suspect the more chances there are to select
> window sizes the more often they will be selected too small.

Not sure you offered a solution ? :)

Just to play the devil's advocate here: are we not reinventing TCP on
top of SPDY ?
With all the problems it carries (e.g. bufferbloat), and additional
ones (how to share bandwidth among streams) ?

Can we get a clearer explanation of what Google found in its measuremen...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/21/12 8:44 AM
On Mon, 2012-05-21 at 17:14 +0200, Simone Bordet wrote:

> But I am not pausing the movie.
> I am watching the movie, but meanwhile I start a big download, for example.
> How do you transfer part of the session window taken by the movie
> stream to the download stream ?
>

I don't think that's a great use of flow control. imo flow control is
about not overrunning the consumer's buffers. Your scenario is using it
to try and manage bandwidth sharing (you don't need more buffers to
support the different streams as the aggregate bandwidth hasn't
changed). I don't think it should manage stream rates - but if the group
thinks it should then I agree txon/txoff ain't going to fill the bill. I
think priorities are a better approach to bandwidth issues and spdy
needs to make them dynamically manageable.

> Just to play the devil's advocate here: are we not reinventing TCP on
> top of SPDY ?

to some degree (hopefully a minor one) the multiplexing demands this.
Definitely a price to be paid for the benefit of being able to actually
improve the web today. (instead of doing a sctp like approach)

> Can we get a clearer explanation of what Google found in its measurement ?
>

google can share their own data points, but I can attest that a gmail
attachment over spdy/3 against a 12KB per-stream window can be 3x slower
with latencies in the high (but not insane) range of 200ms. and 12kb is
what we've seen deployed to this point - roberto suggested that a
per-session window would allow a ...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 5/21/12 9:50 AM
I realize that this email thread is primarily about adding another layer of flow control to SPDY that operates at the SPDY session level but I'm still trying to understand if even the per stream flow control is necessary.

So it seems like the main problem per stream flow control is meant to solve is head of line blocking. To be specific, the problem is when you have a low and a high priority stream active and the low priority stream is transferring a lot of data from a fast content server and the high priority stream is only sending intermittently. In this case, there can be a full 64KB of low priority data in flight across the TCP connection when the high priority data needs to be sent over the TCP connection. If the first packet of the 64KB gets dropped, then the high priority data has to wait at least until the low priority block gets re-transmitted. 

Per stream flow control mitigates (but does not solve) this by preventing the low priority data from ever using the full TCP connection so that the number of low priority bytes in front of the high priority data is smaller. The drawback is that the low priority stream never gets to use the full connection, even when there is no high priority data to send. Is this description correct? And is this the primary use case for per stream flow control?

Has it been considered to use multiple SPDY sessions, one TCP connection per priority level at any given time, so that two streams with different priorities are never competing for bandwidth over the same TCP connection?

Not asking anyone in particular. Just trying to think through the problem. My apologies if I'm taking the discussion backwards a bit.

Thanks,

Peter

On Mon, May 21, 2012 at 11:44 AM, Patrick McManus <mcm...@ducksong.com> wrote:
On Mon, 2012-05-21 at 17:14 +0200, Simone Bordet wrote:

> But I am not pausing the movie.
> I am watching the movie, but meanwhile I start a big download, for example.
> How do you transfer part of the session window taken by the movie
> stream to the download stream ?
>

I don't think that's a great use of flow control. imo flow control is
about not overrunning the consumer's buffers. Your scenario is using it
to try and manage bandwidth sharing (you don't need more buffers to
support the different streams as the aggregate bandwidth hasn't
changed). I don't think it should manage stream rates - but if the group
thinks it should then I agree txon/txoff ain't going to fill the bill. I
think priorities are a better approach to bandwidth issues and spdy
needs to make them dynamically manageable.

> Just to play the devil's advocate here: are we not reinventing TCP on
> top of SPDY ?

to some degree (hopefully a minor one) the multiplexing demands this.
Definitely a price to be paid for the benefit of being able to actually
improve the web today. (instead of doing a sctp like approach)

> Can we get a clearer explanation of what Google found in its measurement ?
>

google can share their own data points, but I can attest that a gmail
attachment over spdy/3 against a 12KB per-stream window can be
...
Re: [spdy-dev] Thinking about flow control Eric 5/21/12 10:06 AM
Hi,

To add more clarity here is an example. A large file is being uploaded. Let's say the server is not able to store the file fast enough. Then with a standard http transmission the receive buffer fills up and the upload waits for more buffer space.

With speedy this means the server stops reading the buffer then all requests will be blocked. This leaves few options:
1. Handle infinite buffer (not really doable)
2. Have someway to block further requests on the stream by notify all reads blocked/unblocked (on/off switch which could trigger new connection)
3. Have someway to block buffering for a stream (moves buffer/blocking from TCP to protocol handling level) 

Eric Ceres
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/21/12 10:17 AM


Nah, this is nowhere near as complicated as TCP. We're only solving a flow-control issue here.
 
With all the problems it carries (e.g. bufferbloat), and additional
ones (how to share bandwidth among streams) ?

If this is done right, we won't have bufferbloat (or, if we do, it would still be better than the bufferbloat which would be happening with many TCP connections).

-=R
 

Can we get a clearer explanation of what Google found in its measurement ?

Thanks !
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/21/12 10:23 AM


On Mon, May 21, 2012 at 9:50 AM, Peter Lepeska <bizzb...@gmail.com> wrote:
I realize that this email thread is primarily about adding another layer of flow control to SPDY that operates at the SPDY session level but I'm still trying to understand if even the per stream flow control is necessary.

So it seems like the main problem per stream flow control is meant to solve is head of line blocking. To be specific, the problem is when you have a low and a high priority stream active and the low priority stream is transferring a lot of data from a fast content server and the high priority stream is only sending intermittently. In this case, there can be a full 64KB of low priority data in flight across the TCP connection when the high priority data needs to be sent over the TCP connection. If the first packet of the 64KB gets dropped, then the high priority data has to wait at least until the low priority block gets re-transmitted. 

Well, per-stream flow control is necessary to prevent HOL blocking through proxies, since the proxies will demux your multiplexed session, and then remux onto other connections (any of which will have different path-restrictions or buffer requirements). Most loadbalancers are proxies.

 

Per stream flow control mitigates (but does not solve) this by preventing the low priority data from ever using the full TCP connection so that the number of low priority bytes in front of the high priority data is smaller. The drawback is that the low priority stream never gets to use the full connection, even when there is no high priority data to send. Is this description correct? And is this the primary use case for per stream flow control?

Has it been considered to use multiple SPDY sessions, one TCP connection per priority level at any given time, so that two streams with different priorities are never competing for bandwidth over the same TCP connection?

It has been considered and, at least so far, rejected as impractical. Basically, each TCP connection likely goes to a different machine for any decent scale deployment (most of which use loadbalancers). You end up losing too much latency, you add significant cost, and you end up with much more potential buffer bloat.

 

Not asking anyone in particular. Just trying to think through the problem. My apologies if I'm taking the discussion backwards a bit.

Its a good thought, and if we find that the problems with multiplexing are insurmountable it will likely be tried. We're not there yet, though!
-=R
 

Thanks,

Peter

On Mon, May 21, 2012 at 11:44 AM, Patrick McManus <mcm...@ducksong.com> wrote:
On Mon, 2012-05-21 at 17:14 +0200, Simone Bordet wrote:

> But I am not pausing the movie.
> I am watching the movie, but meanwhile I start a big download, for example.
> How do you transfer part of the session window taken by the movie
> stream to the download stream ?
>

I don't think that's a great use of flow control. imo flow control is
about not overrunning the consumer's buffers. Your scenario is using it
to try and manage bandwidth sharing (you don't need more buffers to
support the different streams as the aggregate bandwidth hasn't
changed). I don't think it should manage stream rates - but if the group
thinks it should then I agree txon/txoff ain't going to fill the bill. I
think priorities are a better approach to bandwidth issues and spdy
needs to make them dynamically manageable.

> Just to play the devil's advocate here: are we not reinventing TCP on
> top of SPDY ?

to some degree (hopefully a minor one) the multiplexing demands this.
Definitely a price to be paid for the benefit of being able to actually
improve the web today. (instead of doing a sctp like approach)

> Can we get a clearer expl
...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 5/21/12 10:25 AM
That example helps a lot. So per stream flow control in this example is about managing buffering on the SPDY server and the SPDY client for uploads and downloads respectively. If that is the case, then it should only kick in when the network is faster than the receiving end point, which in this case is the content server receiving the uploaded file, right?

So then in summary there are two use cases for per stream flow control -- 1) mitigating HOL blocking and 2) managing buffering by providing feedback on receiver rate of data acceptance. Any others?

The problem with #1 is that it slows down low priority connections even when there is no high priority data to send. For #2, there has to be some type of feedback because as you said infinite buffering is not an option but at least the per stream flow control only has to kick in when the receiving end point is slow.

Anyone please correct anything incorrect about the above understanding,

Peter
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 10:25 AM


On Mon, May 21, 2012 at 10:06 AM, Eric Ceres <eric...@gmail.com> wrote:
Hi,

To add more clarity here is an example. A large file is being uploaded. Let's say the server is not able to store the file fast enough. Then with a standard http transmission the receive buffer fills up and the upload waits for more buffer space.

With speedy this means the server stops reading the buffer then all requests will be blocked. This leaves few options:
1. Handle infinite buffer (not really doable)
2. Have someway to block further requests on the stream by notify all reads blocked/unblocked (on/off switch which could trigger new connection)
3. Have someway to block buffering for a stream (moves buffer/blocking from TCP to protocol handling level) 

So the goal is to allow the sender to keep sending high-priority and 'fast' streams, based on some info about the receiver buffers and how much of each stream is buffered. 

If SPDY had session-level flow control, the sender would know how much 
total buffer space is available - and slow down some streams, stop sending lower priority, etc - but still be able to send higher priority streams until receiver buffer is completely filled. At that point - it can't send anything else.

With the current per-stream, the problem is that the receiver ( or proxy ) needs a buffer that is the sum of all streams windows, for the worse-case when all streams are stalled.

With extra session-level you can have a smaller buffer in the receiver, and if the client may adapt the sending. But eventually you can still get to a worse-case state where the receiver buffer is all full and you can't send anything new stream. In which case if the client knows it's happened, it can either open a new connection or cancel some of the streams.

Costin
...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 5/21/12 10:59 AM
" Well, per-stream flow control is necessary to prevent HOL blocking through proxies, since the proxies will demux your multiplexed session, and then remux onto other connections (any of which will have different path-restrictions or buffer requirements). Most loadbalancers are proxies. "

I'm having trouble understanding how proxies exacerbate the problem of HOL blocking. Can you provide a little more detail on this example? Is it b/c a proxy adds its own buffering and therefore increases the amount of low priority data, over and above a single TCP send window, that can be ahead of high priority data on the stream?

Thanks,

Peter
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/21/12 11:20 AM


On 18 May 2012 19:09, Patrick McManus <mcm...@ducksong.com> wrote:
Having 2 levels of flow control lets you separate the concerns: the
session value is about total buffers available, the per-stream value is
about letting different streams proceed at different rates (and that's
why I think it can be done with xon/xoff in the presence of a session
window).

Patrick,

Can you confirm deny if the following paraphrasing captures what you mean by xon/xoff.

Your hypothesis is that we can achieve near maximum TCP/IP throughput, but without HOL channel blocking by having two levels of flow control.  The outer flow control is applied to the session as a whole and once some threshold is reached, then channels will start being given Xoff messages to stop them sending more data.     So which channels would received the Xoff?  The next one to send a data packet or the ones with the most recent usage?

When would a Xon be sent? after a time delay? once all queued data is sent? once queued data is reduced below some threshold?

Do you think it would be possible to use TCP itself as the outer flow control?  Ie let all channels send as much data as they like until the next frame would block the TCP/IP stream.  At this point Xoff's would be issued to the busiest channels and data would be queued for the non-busy channels... until such point as they become busy and are Xoffed or until the buffers are full and all channels are Xoffed.    Xons would be issued as the buffers are emptied (to the least busy channels first). I think such an algorithm would represent a small amount of HOL blocking as it would allow a b
...
Re: [spdy-dev] Thinking about flow control William Chan 5/21/12 11:50 AM
If a proxy receives data for a stream X, but its backend cannot consume the data anymore, then without per-stream flow control or infinite buffering, the proxy must stop reading the TCP connection. Thus, stopping the reading of data for stream X requires stopping the reading of the entire TCP connection, so stream X causes HoL blocking of all other stream data behind it in the TCP connection.
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/21/12 12:11 PM
On Mon, 2012-05-21 at 20:20 +0200, Greg Wilkins wrote:
>
>
> On 18 May 2012 19:09, Patrick McManus <mcm...@ducksong.com> wrote:
>         Having 2 levels of flow control lets you separate the
>         concerns: the
>         session value is about total buffers available, the per-stream
>         value is
>         about letting different streams proceed at different rates
>         (and that's
>         why I think it can be done with xon/xoff in the presence of a
>         session
>         window).
>
> Patrick,
>
> Can you confirm deny if the following paraphrasing captures what you
> mean by xon/xoff.
>
> Your hypothesis is that we can achieve near maximum TCP/IP throughput,
> but without HOL channel blocking by having two levels of flow control.
> The outer flow control is applied to the session as a whole and once
> some threshold is reached, then channels will start being given Xoff
> messages to stop them sending more data.  

pretty much

>   So which channels would received the Xoff?  The next one to send a
> data packet or the ones with the most recent usage?
>

not specified by the protocol - the receiver can implement it any way
they want. I would expect that the receiver would xoff a stream who's
data sink had built a stream specific buffer too large. (i.e. was not
consuming at line rate). I'm not naive, I understand that this is a sort
of windowing in itself but for configuration it separates out the
necessary BDP component for making the stream run at line rate, which I
hope we all agree is the goal under normal circumstances, and that's the
knob people are going to intuitively buffer too low and not future
proof.

When someone asks themselves "how many buffers do I allocate to the data
base process" are they asking themselves contextually "how many buffers
do I allocate for the DB and at what speed and latency?" I'm going to
say they don't do that and that's an impossibly hard question to ask an
admin anyhow. Much better to say "how many buffers on top of those
required by the network for full data rate" will you allocate to this
stream?

The full session buffer limit can backstop you if you really don't have
the resources to run in a high BDP environment.

> When would a Xon be sent? after a time delay? once all queued data is
> sent? once queued data is reduced below some threshold?
>

from the pov of the protocol - it isn't specified. I would expect some
watermark approach.

> Do you think it would be possible to use TCP itself as the outer flow
> control?

Maybe; but probly not.

I think its a little tricky for a server (or the server side of a proxy)
to do things like 1] exhaust tcp rwin, 2] xoff all senders, 3] update
initial window via settings to prevent new senders and 4] reopen tcp
rwin a bit to process GETs and pings and goaways etc..

The client in that situation is going to have data buffe...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 12:26 PM


Can the decision be made on the sender side instead ?

The receiver would send back info about total buffer size and any stream that has more is using more than x% of the buffer (or some other measure).  

So instead of 2 flow controls - one for stream, one per channel, you would just send more detailed info about the buffer and top stream status, and let the client chose what to send next and what to suspend. I think client or backend are better to decide if they have enough info.

Costin

 
I
hope we all agree is the goal under normal circumstances, and that's the
knob people are going to intuitively buffer too low and not future
proof.

When someone asks themselves "how many buffers do I allocate to the data
base process" are they asking themselves contextually "how many buffers
do I allocate for the DB and at what speed and latency?" I'm going to
say they don't do that and that's an impossibly hard question to ask an
admin anyhow. Much better to say "how many buffers on top of those
required by the network for full data rate" will you allocate to this
stream?

The full session buffer limit can backstop you if you really don't have
the resources to run in a high BDP environment.

> When would a Xon be sent? after a time delay? once all queued data is
> sent? once queued data is reduced below some threshold?
>

from the pov of the protocol - it isn't specified. I would expect some
watermark approach.

> Do you think it would be possible to use TCP itself as the outer flow
> control?

Maybe; but probly not.

I think its a little tricky for a server (or the server side of a proxy)
to do things like 1] exhaust tcp rwin, 2] xoff all senders, 3] update
initial window via sett
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/21/12 12:34 PM
Detail about the buffer is what flow control exposes, though, right?
The client always chooses what to send and what not to send anyway. A receiver never has control over the sender, they can merely give them policy and hope the sender acts upon it.

We'll always need per-stream flow control. No avoiding that. Anything which accurately signals the number of bytes per stream which it is safe to send, and which provides a constant and predictable overall memory usage on the receiver for all streams will do.

I'm having a hard time reconciling your suggestion with this. If we do the per-stream flow control, and can't do 2 levels of flow control, what data would we send which wouldn't BE flow control that would allow the server to be assured (with a well behaved client) to use no more buffer than it wishes to use?

-=R
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 1:57 PM
On Mon, May 21, 2012 at 12:34 PM, Roberto Peon <fe...@google.com> wrote:
Detail about the buffer is what flow control exposes, though, right?
The client always chooses what to send and what not to send anyway. A receiver never has control over the sender, they can merely give them policy and hope the sender acts upon it.

Right now the proxy controls things by setting window - I assume if a client doesn't obey flow control the server will close the connection, it's not quite 'client decide what to send'.

Yes, the details (inputs) would be the same for any solution - max buffer of the receiver, current window for each stream, how much of the total and per-stream buffer is used.

My suggestion is to send all this data to client - instead of sending info about how much each stream is allowed to send, send data about how much of each stream is buffered and the total buffer size.

For example: the proxy has a 1M buffer per connection. Client can choose to send 900K of one stream, than wait for the flow control frame, and keep sending high-priority or small requests. If the large upload doesn't make any progress in 10 min, it can chose to cancel it, or not send any more bytes until it makes progress. 

Benefits:

- A smart client will have more choices on what it sends - in particular it may chose to drop some streams. I think that's the main difference - if few  large uploads gets stale for a long time, there is nothing in the current per-stream / per-channel flow control that would help, the only help is to drop the stale upload.

- a dumb client doesn't need to do anything - can just ignore the flow control and the TCP flow control will do its job.

- the server doesn't have to send data for all streams - only for the streams that use large buffers or are stalled ( fewer bytes ).

- the initial per stream window is close to the total buffer size of the proxy ( instead of small per stream window to account for the worse case of all streams getting buffered )

- the code may be simpler on the server, and for equivalent functionality it may be simple on the client.




We'll always need per-stream flow control. No avoiding that. Anything which accurately signals the number of bytes per stream which it is safe to send, and which provides a constant and predictable overall memory usage on the receiver for all streams will do.

Yes, you need to know the buffering status per-stream - maybe not for all streams, and it doesn't have to be 'per stream flow control'. You just send info about the buffer usage on the proxy, client can make any choice as long as it respects total buffer size.


 

I'm having a hard time reconciling your suggestion with this. If we do the per-stream flow control, and can't do 2 levels of flow control, what data would we send which wouldn't BE flow control that would allow the server to be assured (with a well behaved client) to use no more buffer than it wishes to use?

Server will send total buffer size (once), than periodically will send stream status info. For example any time it would send a 'window update' now, or only if the buffer use is > 50%. 

The data is about the same with the current flow control - how many bytes can be sent by the client safely (now) versus how many bytes are currently buffered (in my proposal). The frequency can be the same - or you can send flow info only when you need to (now window updates are required for each stream, or client will be forced to stop sending). The decision on when to allow sending is similar - except it's done by client using the info from server, instead of server. 

Costin
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 2:06 PM
If I'm too confusing, my proposal is:

- remove the current per stream window

- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

- server will send flow control packets with a list of stream IDs and how much bytes are buffered for each stream. There are few options on which streams to include in the flow control packet, and when to send this packet.

- client will not send more than [total buffer] until it receives a flow control packet with a stream-based window update. When it receives a flow control packet - it can chose what stream to send based on free space, priorities, etc - as long as total in-flight bytes fit total buffer.

- client should also detect if some streams are 'stalled' - no progress for X minutes, too much data buffered - and may time-out them so it can send other streams.

It's still a combination of connection and stream flow control.

Costin
...
Re: [spdy-dev] Thinking about flow control William Chan 5/21/12 2:09 PM
This doesn't make sense to me. You say "remove the current per stream window" and then you say "it's still a combination of connection and stream flow control".

On Mon, May 21, 2012 at 2:06 PM, Costin Manolache <cos...@gmail.com> wrote:
If I'm too confusing, my proposal is:

- remove the current per stream window

- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

- server will send flow control packets with a list of stream IDs and how much bytes are buffered for each stream. There are few options on which streams to include in the flow control packet, and when to send this packet.

This sounds like per stream window updates. Why do you say "remove the current per stream window"?
 

- client will not send more than [total buffer] until it receives a flow control packet with a stream-based window update. When it receives a flow control packet - it can chose what stream to send based on free space, priorities, etc - as long as total in-flight bytes fit total buffer.

With a per-stream window and per-session window, a sender could still do this. When space opens up in the per-session window, the sender is obviously allowed to choose which stream to send data over, assuming that per-stream window has space.
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 2:41 PM
On Mon, May 21, 2012 at 2:09 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
This doesn't make sense to me. You say "remove the current per stream window" and then you say "it's still a combination of connection and stream flow control".

It replaces the current definition of per-stream window - right now each stream window/flow is sent individually, all streams have the same initial window, and the information sent back is how much it's allowed to sent for the stream.

It still has per-stream flow control - in the sense that you send back how much is buffered for each stream ( all or or only streams that have >x bytes or % buffered ). 
 


On Mon, May 21, 2012 at 2:06 PM, Costin Manolache <cos...@gmail.com> wrote:
If I'm too confusing, my proposal is:

- remove the current per stream window

- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

- server will send flow control packets with a list of stream IDs and how much bytes are buffered for each stream. There are few options on which streams to include in the flow control packet, and when to send this packet.

This sounds like per stream window updates. Why do you say "remove the current per stream window"?

The window updates will be per session. 

The 'per stream window' is replaced by info about how much is currently buffered for the stream, combined with info about total session buffer available. 


 
 

- client will not send more than [total buffer] until it receives a flow control packet with a stream-based window update. When it receives a flow control packet - it can chose what stream to send based on free space, priorities, etc - as long as total in-flight bytes fit total buffer.

With a per-stream window and per-session window, a sender could still do this. When space opens up in the per-session window, the sender is obviously allowed to choose which stream to send data over, assuming that per-stream window has space.

Yes, but I guess it's a more direct decision when you know total buffer and 
how much each stream has buffered. And when you start new streams - they won't be limited by a small per-stream window, but by per-session window.

You can probably infer from the stream window how much of that stream is buffered and if the stream is stale.


Costin 
...
Re: [spdy-dev] Thinking about flow control William Chan 5/21/12 2:58 PM
On Mon, May 21, 2012 at 2:41 PM, Costin Manolache <cos...@gmail.com> wrote:
On Mon, May 21, 2012 at 2:09 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
This doesn't make sense to me. You say "remove the current per stream window" and then you say "it's still a combination of connection and stream flow control".

It replaces the current definition of per-stream window - right now each stream window/flow is sent individually, all streams have the same initial window, and the information sent back is how much it's allowed to sent for the stream.

It still has per-stream flow control - in the sense that you send back how much is buffered for each stream ( all or or only streams that have >x bytes or % buffered ). 
 


On Mon, May 21, 2012 at 2:06 PM, Costin Manolache <cos...@gmail.com> wrote:
If I'm too confusing, my proposal is:

- remove the current per stream window

- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

- server will send flow control packets with a list of stream IDs and how much bytes are buffered for each stream. There are few options on which streams to include in the flow control packet, and when to send this packet.

This sounds like per stream window updates. Why do you say "remove the current per stream window"?

The window updates will be per session. 

The 'per stream window' is replaced by info about how much is currently buffered for the stream, combined with info about total session buffer available. 


 
 

- client will not send more than [total buffer] until it receives a flow control packet with a stream-based window update. When it receives a flow control packet - it can chose what stream to send based on free space, priorities, etc - as long as total in-flight bytes fit total buffer.

With a per-stream window and per-session window, a sender could still do this. When space opens up in the per-session window, the sender is obviously allowed to choose which stream to send data over, assuming that per-stream window has space.

Yes, but I guess it's a more direct decision when you know total buffer and 
how much each stream has buffered. And when you start new streams - they won't be limited by a small per-stream window, but by per-session window.

Don't you know how much each stream has buffered via per-stream flow control windows? And the existence of a per-session window obviates the need for small initial per-stream windows. You can make them larger now. 64k is a reasonable default still (if you disagree, let's fix it then), and the SETTINGS frame lets you adjust it to a more appropriate value within one RTT for the server rwin, and zero RTTs for the client rwin.

I guess I don't understand how communicating a percentage of stream buffer size is better than a per-stream flow control window size. The latter approach lets you dynamically adjust the window size on a per-stream basis in a more elegant matter IMO.
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/21/12 3:01 PM
I think they both achieve the same goal. The server can lie about the amount of buffer it has available to accomplish any of the goals that it would have done. The question thus resolves to: which is easier to implement.
I'd guess that the current window-based way is easier and cheaper since the window-updates are delta-encodings for the state changes.

Did you think this would allow something else Costin? I readily admit I could be missing something :)

-=R
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 4:17 PM


On Mon, May 21, 2012 at 2:58 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Mon, May 21, 2012 at 2:41 PM, Costin Manolache <cos...@gmail.com> wrote:
On Mon, May 21, 2012 at 2:09 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
This doesn't make sense to me. You say "remove the current per stream window" and then you say "it's still a combination of connection and stream flow control".

It replaces the current definition of per-stream window - right now each stream window/flow is sent individually, all streams have the same initial window, and the information sent back is how much it's allowed to sent for the stream.

It still has per-stream flow control - in the sense that you send back how much is buffered for each stream ( all or or only streams that have >x bytes or % buffered ). 
 


On Mon, May 21, 2012 at 2:06 PM, Costin Manolache <cos...@gmail.com> wrote:
If I'm too confusing, my proposal is:

- remove the current per stream window

- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

- server will send flow control packets with a list of stream IDs and how much bytes are buffered for each stream. There are few options on which streams to include in the flow control packet, and when to send this packet.

This sounds like per stream window updates. Why do you say "remove the current per stream window"?

The window updates will be per session. 

The 'per stream window' is replaced by info about how much is currently buffered for the stream, combined with info about total session buffer available. 


 
 

- client will not send more than [total buffer] until it receives a flow control packet with a stream-based window update. When it receives a flow control packet - it can chose what stream to send based on free space, priorities, etc - as long as total in-flight bytes fit total buffer.

With a per-stream window and per-session window, a sender could still do this. When space opens up in the per-session window, the sender is obviously allowed to choose which stream to send data over, assuming that per-stream window has space.

Yes, but I guess it's a more direct decision when you know total buffer and 
how much each stream has buffered. And when you start new streams - they won't be limited by a small per-stream window, but by per-session window.

Don't you know how much each stream has buffered via per-stream flow control windows? And the existence of a per-session window obviates the need for small initial per-stream windows. You can make them larger now. 64k is a reasonable default still (if you disagree, let's fix it then), and the SETTINGS frame lets you adjust it to a more appropriate value within one RTT for the server rwin, and zero RTTs for the client rwin.

Would 64K be the default for both session and stream windows ?

I guess my proposal is almost equivalent - if you know the stream window and client window you can calculate how much is buffered. After you fill the session window you need to wait for session and stream window updates in both cases.


I guess I don't understand how communicating a percentage of stream buffer size is better than a per-stream flow control window size. The latter approach lets you dynamically adjust the window size on a per-stream basis in a more elegant matter IMO.

I think it's more direct to tell the client the relevant information - how big is the proxy buffer and how much of each stream is buffered. 

The 'percentage' was an optimization - you don't need to send flow control for streams that go trough / have very low buffers, or if the proxy buffer has plenty of space. The per-stream flow will only kick in when it's needed.
You can still do delta-encoding for stream and session. 


What would be the meaning of 'per stream window' - it's no longer amount you are allowed to send for that stream - you need to consider the session window and all other streams windows. It's this computation that I think would be cleaner if you work in reverse, with how much is buffered instead of the 'window' which is no longer a direct indication of how much to send.

But if you can find a good explanation of the stream window and how it interact with the session window it would be less confusing.

Costin
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 4:25 PM


On Mon, May 21, 2012 at 3:01 PM, Roberto Peon <fe...@google.com> wrote:
I think they both achieve the same goal. The server can lie about the amount of buffer it has available to accomplish any of the goals that it would have done. The question thus resolves to: which is easier to implement.

Agreed.
 
I'd guess that the current window-based way is easier and cheaper since the window-updates are delta-encodings for the state changes.

I think a 'dumb client' would be simpler with my proposal - it would just ignore all flow control packets. The TCP flow control would ensure the 'per session' buffer is used. 

In both cases a smart client needs to keep track of how much they can send on each stream - based on session window and stream window, which in both cases is a proxy for how fast that stream is and how much is buffered. 

In the current flow,the information is received as one packet per stream, when the stream is making progress, plus one new packet for session.
In my proposal - the almost same information will be sent in a single packet, which will only be sent if the session buffer is to big. 

In the good case - all streams floating around - my proposal wouldn't send any stream flow control packet, only the session info.

Costin
...
Re: [spdy-dev] Thinking about flow control William Chan 5/21/12 4:35 PM
On Mon, May 21, 2012 at 4:17 PM, Costin Manolache <cos...@gmail.com> wrote:


On Mon, May 21, 2012 at 2:58 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Mon, May 21, 2012 at 2:41 PM, Costin Manolache <cos...@gmail.com> wrote:
On Mon, May 21, 2012 at 2:09 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
This doesn't make sense to me. You say "remove the current per stream window" and then you say "it's still a combination of connection and stream flow control".

It replaces the current definition of per-stream window - right now each stream window/flow is sent individually, all streams have the same initial window, and the information sent back is how much it's allowed to sent for the stream.

It still has per-stream flow control - in the sense that you send back how much is buffered for each stream ( all or or only streams that have >x bytes or % buffered ). 
 


On Mon, May 21, 2012 at 2:06 PM, Costin Manolache <cos...@gmail.com> wrote:
If I'm too confusing, my proposal is:

- remove the current per stream window

- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

- server will send flow control packets with a list of stream IDs and how much bytes are buffered for each stream. There are few options on which streams to include in the flow control packet, and when to send this packet.

This sounds like per stream window updates. Why do you say "remove the current per stream window"?

The window updates will be per session. 

The 'per stream window' is replaced by info about how much is currently buffered for the stream, combined with info about total session buffer available. 


 
 

- client will not send more than [total buffer] until it receives a flow control packet with a stream-based window update. When it receives a flow control packet - it can chose what stream to send based on free space, priorities, etc - as long as total in-flight bytes fit total buffer.

With a per-stream window and per-session window, a sender could still do this. When space opens up in the per-session window, the sender is obviously allowed to choose which stream to send data over, assuming that per-stream window has space.

Yes, but I guess it's a more direct decision when you know total buffer and 
how much each stream has buffered. And when you start new streams - they won't be limited by a small per-stream window, but by per-session window.

Don't you know how much each stream has buffered via per-stream flow control windows? And the existence of a per-session window obviates the need for small initial per-stream windows. You can make them larger now. 64k is a reasonable default still (if you disagree, let's fix it then), and the SETTINGS frame lets you adjust it to a more appropriate value within one RTT for the server rwin, and zero RTTs for the client rwin.

Would 64K be the default for both session and stream windows ?

I suspect we can make the session window larger than 64K. I'm open to suggestions here.
 

I guess my proposal is almost equivalent - if you know the stream window and client window you can calculate how much is buffered. After you fill the session window you need to wait for session and stream window updates in both cases.


I guess I don't understand how communicating a percentage of stream buffer size is better than a per-stream flow control window size. The latter approach lets you dynamically adjust the window size on a per-stream basis in a more elegant matter IMO.

I think it's more direct to tell the client the relevant information - how big is the proxy buffer and how much of each stream is buffered. 

The 'percentage' was an optimization - you don't need to send flow control for streams that go trough / have very low buffers, or if the proxy buffer has plenty of space. The per-stream flow will only kick in when it's needed.
You can still do delta-encoding for stream and session. 


What would be the meaning of 'per stream window' - it's no longer amount you are allowed to send for that stream - you need to consider the session window and all other streams windows. It's this computation that I think would be cleaner if you work in reverse, with how much is buffered instead of the 'window' which is no longer a direct indication of how much to send.

But if you can find a good explanation of the stream window and how it interact with the session window it would be less confusing.

I guess I'm not sure what's confusing about the interaction with the stream window and the session window. When writing stream data in a naive implementation, the amount you'd write is amount_to_write = min(stream_data_length, stream_window_size, session_window_size). Then stream_window_size -= amount_to_write and session_window_size -= amount_to_write. A more advanced implementation may examine the remaining session window size to see how much space is left and the stream priority, and based on info like that, may opt to write less (or zero) stream data if the session window is small and/or the stream priority is low.

If we wanted to allow dynamically resizing the session window size apart from per stream windows, then we'd have to introduce a separate SESSION_WINDOW_UPDATE or something. Or add a new field to the WINDOW_UPDATE frame for the amount to adjust the session window.
...
Re: [spdy-dev] Thinking about flow control Hasan Khalil 5/21/12 4:47 PM
On Mon, May 21, 2012 at 7:35 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
If we wanted to allow dynamically resizing the session window size apart from per stream windows, then we'd have to introduce a separate SESSION_WINDOW_UPDATE or something. Or add a new field to the WINDOW_UPDATE frame for the amount to adjust the session window.

Or neither: send a WINDOW_UPDATE for stream 0.

    -Hasan
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/21/12 7:03 PM
On Mon, May 21, 2012 at 4:35 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Mon, May 21, 2012 at 4:17 PM, Costin Manolache <cos...@gmail.com> wrote:


On Mon, May 21, 2012 at 2:58 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Mon, May 21, 2012 at 2:41 PM, Costin Manolache <cos...@gmail.com> wrote:
On Mon, May 21, 2012 at 2:09 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
This doesn't make sense to me. You say "remove the current per stream window" and then you say "it's still a combination of connection and stream flow control".

It replaces the current definition of per-stream window - right now each stream window/flow is sent individually, all streams have the same initial window, and the information sent back is how much it's allowed to sent for the stream.

It still has per-stream flow control - in the sense that you send back how much is buffered for each stream ( all or or only streams that have >x bytes or % buffered ). 
 


On Mon, May 21, 2012 at 2:06 PM, Costin Manolache <cos...@gmail.com> wrote:
If I'm too confusing, my proposal is:

- remove the current per stream window

- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

- server will send flow control packets with a list of stream IDs and how much bytes are buffered for each stream. There are few options on which streams to include in the flow control packet, and when to send this packet.

This sounds like per stream window updates. Why do you say "remove the current per stream window"?

The window updates will be per session. 

The 'per stream window' is replaced by info about how much is currently buffered for the stream, combined with info about total session buffer available. 


 
 

- client will not send more than [total buffer] until it receives a flow control packet with a stream-based window update. When it receives a flow control packet - it can chose what stream to send based on free space, priorities, etc - as long as total in-flight bytes fit total buffer.

With a per-stream window and per-session window, a sender could still do this. When space opens up in the per-session window, the sender is obviously allowed to choose which stream to send data over, assuming that per-stream window has space.

Yes, but I guess it's a more direct decision when you know total buffer and 
how much each stream has buffered. And when you start new streams - they won't be limited by a small per-stream window, but by per-session window.

Don't you know how much each stream has buffered via per-stream flow control windows? And the existence of a per-session window obviates the need for small initial per-stream windows. You can make them larger now. 64k is a reasonable default still (if you disagree, let's fix it then), and the SETTINGS frame lets you adjust it to a more appropriate value within one RTT for the server rwin, and zero RTTs for the client rwin.

Would 64K be the default for both session and stream windows ?

I suspect we can make the session window larger than 64K. I'm open to suggestions here.

Any reason to have the stream window smaller than the session window ? 
Can't think of any use case. 

 
 

I guess my proposal is almost equivalent - if you know the stream window and client window you can calculate how much is buffered. After you fill the session window you need to wait for session and stream window updates in both cases.


I guess I don't understand how communicating a percentage of stream buffer size is better than a per-stream flow control window size. The latter approach lets you dynamically adjust the window size on a per-stream basis in a more elegant matter IMO.

I think it's more direct to tell the client the relevant information - how big is the proxy buffer and how much of each stream is buffered. 

The 'percentage' was an optimization - you don't need to send flow control for streams that go trough / have very low buffers, or if the proxy buffer has plenty of space. The per-stream flow will only kick in when it's needed.
You can still do delta-encoding for stream and session. 


What would be the meaning of 'per stream window' - it's no longer amount you are allowed to send for that stream - you need to consider the session window and all other streams windows. It's this computation that I think would be cleaner if you work in reverse, with how much is buffered instead of the 'window' which is no longer a direct indication of how much to send.

But if you can find a good explanation of the stream window and how it interact with the session window it would be less confusing.

I guess I'm not sure what's confusing about the interaction with the stream window and the session window. When writing stream data in a naive implementation, the amount you'd write is amount_to_write = min(stream_data_length, stream_window_size, session_window_size).

Then stream_window_size -= amount_to_write and session_window_size -= amount_to_write. A more advanced implementation may examine the remaining session window size to see how much space is left and the stream priority, and based on info like that, may opt to write less (or zero) stream data if the session window is small and/or the stream priority is low.

A non-naive implementation would look at all outgoing streams, sorted by priority, and attempt to divide the stream_window_size somehow - maybe give priority to SYN_STREAM packets, etc.

And it may consider which streams are 'stale' == no change in window size, i.e. the server is stuck and proxy needs to cache it.  


 

If we wanted to allow dynamically resizing the session window size apart from per stream windows, then we'd have to introduce a separate SESSION_WINDOW_UPDATE or something. Or add a new field to the WINDOW_UPDATE frame for the amount to adjust the session window.

The use case would be a proxy server that may cache more if the load is low. 

But the main issue (IMHO) is how to chose the amount to send for each stream, based on stream window, priority and remaining buffer space. 
The proxy buffer can be considered fixed size when the decision is made, the 'stream window' is a proxy for how much of that stream is buffered - and that indicates how likely that stream is to clog the pipe. 

I don't think the 'naive' implementation will work so well if you have many streams going slowly ( few uploads plus some new requests ), unless you somehow reduce the window for each of the slow streams - but that won't work for the initial window size. So you need to reduce the initial window.

Costin 
...
Re: [spdy-dev] Thinking about flow control William Chan 5/21/12 7:47 PM
Maybe you missed my email here: https://groups.google.com/forum/#!msg/spdy-dev/JB_aQPNI7rw/3Kata9-QeI0J. If the peer is naive, then it may be advantageous to have a smaller per-stream win.
 

 
 

I guess my proposal is almost equivalent - if you know the stream window and client window you can calculate how much is buffered. After you fill the session window you need to wait for session and stream window updates in both cases.


I guess I don't understand how communicating a percentage of stream buffer size is better than a per-stream flow control window size. The latter approach lets you dynamically adjust the window size on a per-stream basis in a more elegant matter IMO.

I think it's more direct to tell the client the relevant information - how big is the proxy buffer and how much of each stream is buffered. 

The 'percentage' was an optimization - you don't need to send flow control for streams that go trough / have very low buffers, or if the proxy buffer has plenty of space. The per-stream flow will only kick in when it's needed.
You can still do delta-encoding for stream and session. 


What would be the meaning of 'per stream window' - it's no longer amount you are allowed to send for that stream - you need to consider the session window and all other streams windows. It's this computation that I think would be cleaner if you work in reverse, with how much is buffered instead of the 'window' which is no longer a direct indication of how much to send.

But if you can find a good explanation of the stream window and how it interact with the session window it would be less confusing.

I guess I'm not sure what's confusing about the interaction with the stream window and the session window. When writing stream data in a naive implementation, the amount you'd write is amount_to_write = min(stream_data_length, stream_window_size, session_window_size).

Then stream_window_size -= amount_to_write and session_window_size -= amount_to_write. A more advanced implementation may examine the remaining session window size to see how much space is left and the stream priority, and based on info like that, may opt to write less (or zero) stream data if the session window is small and/or the stream priority is low.

A non-naive implementation would look at all outgoing streams, sorted by priority, and attempt to divide the stream_window_size somehow - maybe give priority to SYN_STREAM packets, etc.

SYN_STREAM frames do not have any data payload, only header payload.
 

And it may consider which streams are 'stale' == no change in window size, i.e. the server is stuck and proxy needs to cache it.  


 

If we wanted to allow dynamically resizing the session window size apart from per stream windows, then we'd have to introduce a separate SESSION_WINDOW_UPDATE or something. Or add a new field to the WINDOW_UPDATE frame for the amount to adjust the session window.

The use case would be a proxy server that may cache more if the load is low. 

But the main issue (IMHO) is how to chose the amount to send for each stream, based on stream window, priority and remaining buffer space. 
The proxy buffer can be considered fixed size when the decision is made, the 'stream window' is a proxy for how much of that stream is buffered - and that indicates how likely that stream is to clog the pipe. 

Yes, this is an interesting implementation discussion. And it's also interesting to discuss since we know that not all implementations will be equal. As I suggested in my earlier earlier, there's a tradeoff between giving a peer control to do more optimal and horrible things, and taking away that control to prevent stupid shit, yet also prevent a smarter peer implementation. It's an interesting discussion to have about what / how powerful of knobs to provide.
 

I don't think the 'naive' implementation will work so well if you have many streams going slowly ( few uploads plus some new requests ), unless you somehow reduce the window for each of the slow streams - but that won't work for the initial window size. So you need to reduce the initial window.

I don't grok this statement. Can you rephrase?
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/22/12 12:41 AM


On 21 May 2012 23:06, Costin Manolache <cos...@gmail.com> wrote:
If I'm too confusing, my proposal is
- remove the current per stream window
- server will declare it's total buffer  ( with a reasonable default - 64k or 1M), and use a per-connection window.

I'm now concerned about any approach that has a window size - be it session or stream based.   Any window size is a guess that will mostly be wrong.  Either the guess will be too small, in which case we can't use all the capacity of a tcp connection and we create the incentive to use multiple connections (in effect getting multiple windows).  If the guess is two large, then we will be able to go fast enough to trigger TCP flow control, which may have some fairness issues.

Instead, I think a simple xon/xoff approach as suggested by Patrick merits at least some further consideration (although I understand he suggested it in conjunction with a session window) to see if it can avoid creating a window guess.

If we say that any component along a connection is allowed to send an xoff if it detects congestion then I believe that we can allow the connection to run at full speed and significantly reduce the impact of (but not avoid completely) HOL blocking.   The problem is that by the time an Xoff is received and processed, TCP flow control may already have been invoked.  Worse still, the transmission of the Xoff may itself be delayed by heavy traffic going the other way.

However, I content that even with a window, this is a situation that can occur because a window guess may always be larger than the available network capacity (and large guesses will be favoured to attempt to use all of a connections capacity).  So even with a window, tcp flow control can kick in when a small percentage of the window has been sent.    I'd much rather a situation where the sender detects that tcp flow control is taking place and issues some local Xoffs rather than steadfastly plugging on trying to send the remaining quota it has in its window (and thus causing HOL blocking anyway).

The upside of xon/xoff is that a xoff can be generated anywhere along the connection.   The sender itself can generate local xoffs to its producers if it detects tcp flow control on it's writes. A proxy can send xoffs if its buffers are full ...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/22/12 12:51 AM
Also while we are considering windows, it is worth while reading Mikes paper on slow starts in TCP  http://dev.chromium.org/spdy/An_Argument_For_Changing_TCP_Slow_Start.pdf?attredirects=0
Surely if we put windows into SPDY, then we are just recreating that same problem? How big to make the initial windows and creating an incentive to use multiple sessions in order to get multiple initial windows.

cheers...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/22/12 2:56 AM

Some more reading of interest is http://www.ietf.org/rfc/rfc4254.txt.  This is the SSH connection protocol that supports multiplexed channels using individual window sizes - more or less what SPDY/3 has.  It also has an optimisation to support xon/xoff of individual channels.

There is also a paper about how these window sizes can cause significant performance problems and how dynamically resizing the windows can improve throughput
http://www.psc.edu/networking/projects/hpn-ssh/papers/hpnssh-postertext.pdf

cheers...
Re: [spdy-dev] Thinking about flow control Daniel Stenberg 5/22/12 4:53 AM
On Tue, 22 May 2012, Greg Wilkins wrote:

> Some more reading of interest is http://www.ietf.org/rfc/rfc4254.txt.  This
> is the SSH connection protocol that supports multiplexed channels using
> individual window sizes - more or less what SPDY/3 has.  It also has an
> optimisation to support xon/xoff of individual channels.
>
> There is also a paper about how these window sizes can cause significant
> performance problems and how dynamically resizing the windows can improve
> throughput
> http://www.psc.edu/networking/projects/hpn-ssh/papers/hpnssh-postertext.pdf

Yes, SSH does indeed have more or less the exact same windowing that SPDY has,
which in turn seems to mimic what TCP itself offers.

I'm the primary developer of libssh2 which is the SSH library used for SCP and
SFTP transfers with for example curl and I just felt I should add two minor
details when comparing SPDY to SSH and reading the PDF mentioned above. In
general SSH and SPDY have a lot in common: secure from the start, multiple
channels over a single physical, flow control per stream etc.

1 - Lots of people use SFTP for file transfers over SSH. But SFTP has its own
slew of added complexity that makes it a bad comparison. A good comparison
between SPDY and SSH needs to be based on plain SSH channels, such as an SCP
transfer.

2 - The PDF above makes specific remarks and improve...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/22/12 5:34 AM
On Mon, 2012-05-21 at 19:47 -0700, William Chan (陈智昌) wrote:

>        
>        
>         Any reason to have the stream window smaller than the session
>         window ?
>         Can't think of any use case.
>
>
> Maybe you missed my email here: https://groups.google.com/forum/#!
> msg/spdy-dev/JB_aQPNI7rw/3Kata9-QeI0J. If the peer is naive, then it
> may be advantageous to have a smaller per-stream win.
>  

the concern I have with that approach is that it addresses an
algorithmic shortcoming of the sender via a configuration on the
receiver. If the sender improves its algorithm it doesn't help anything
because it can't unilaterally change the window advertised by the
receiver and we are painted into a corner. As you say - the sender isn't
obligated to use the whole window just because its there... if the
implementor of that sender thinks restraint is the right thing to do -
then go for it. If another implementor thinks filling high BDP pipes is
the ...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/22/12 5:51 AM


On 22 May 2012 13:53, Daniel Stenberg <dan...@haxx.se> wrote:
2 - The PDF above makes specific remarks and improvement recommendations based on internal design decisions and source code in OpenSSH. They are not strictly enforced by the SSH protocol and other implementations will have different algorithms to adjust the window size.

Daniel,

In your experience with ssh would you say that all implementations that want high throughput have opted for dynamic window sizes?

Does the protocol itself specify as default assumed window size or do all implementations have to advertise the window size they want during handshake?

cheers

Re: [spdy-dev] Thinking about flow control Daniel Stenberg 5/22/12 6:30 AM
On Tue, 22 May 2012, Greg Wilkins wrote:

> In your experience with ssh would you say that all implementations that want
> high throughput have opted for dynamic window sizes?

I'm afraid I don't think I have enough data to say that with a definite
certainty, as I haven't paid enough attention to those specific details and
perhaps also because OpenSSH is such a dominant implementation in use.

We have achieved much higher throughput over SSH by advertising very large
windows (at least in the hundreds of Kbyte) and we've always done dynamic
sizing.

But what I think makes my primary use of SSH not so good to compare with SPDY
and the way we're talking about the flow control here is that I'm primarily
author a single SSH consumer which mainly uses a single channel. I don't have
that much experience with having multiple consumers of different channels,
each performing differently, and I haven't heard a lot from such users either.

> Does the protocol itself specify as default assumed window size or do all
> implementations have to adverti...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/22/12 8:10 AM
On Tue, May 22, 2012 at 4:53 AM, Daniel Stenberg <dan...@haxx.se> wrote:
On Tue, 22 May 2012, Greg Wilkins wrote:

Some more reading of interest is http://www.ietf.org/rfc/rfc4254.txt.  This is the SSH connection protocol that supports multiplexed channels using individual window sizes - more or less what SPDY/3 has.  It also has an optimisation to support xon/xoff of individual channels.

There is also a paper about how these window sizes can cause significant
performance problems and how dynamically resizing the windows can improve
throughput
http://www.psc.edu/networking/projects/hpn-ssh/papers/hpnssh-postertext.pdf

Yes, SSH does indeed have more or less the exact same windowing that SPDY has, which in turn seems to mimic what TCP itself offers.

TCP has not only flow control windows, but also re-transmit, a router can drop IP packets if they're stuck. I don't think SPDY can work as well as TCP does with only flow control. 

My proposal was to provide as much information as possible to the sender about the status of the connection and buffering. If a sender can detect that one of the streams is 'stuck' and clogging the buffers, and it has a higher priority stream to send - it can abort the slow stream.

Typical example will be uploads - in many cases ( with range, etc ) it's safe to interrupt an upload and restart it later. If you have a large sync/upload operation in background you want it to go as fast as possible but not interrupt normal browsing. 

The sender has a list of streams with different priorities, with data waiting to be sent. What information should it have to make the best decision about how much of each to send, or which stream to abort ?  

My understanding of 'stream window' was that it's an indication of how much to send from the stream (without clogging the pipes for other streams). Pretty easy, but if you add 'session flow control' it gets quite complicated, the stream window no longer means that you can send that much data.


Costin
 

I'm the primary developer of libssh2 which is the SSH library used for SCP and SFTP transfers with for example curl and I just felt I should add two minor details when comparing SPDY to SSH and reading the PDF mentioned above. In general SSH and SPDY have a lot in common: secure from the start, multiple channels over a single physical, flow control per stream etc.

1 - Lots of people use SFTP for file transfers over SSH. But SFTP has its own slew of added com
...
Re: [spdy-dev] Thinking about flow control William Chan 5/22/12 8:36 AM
the most important thing, more power to them!
...
Re: [spdy-dev] Thinking about flow control Danner Stodolsky 5/22/12 7:19 PM
For the multiplexed control situations we've been discussing, I've always been partial systems with a per-stream minimum reservation + a shareable burst that the sender can partition. The burst-size is sized by the receiver based on BDP estimate and/or resource constraints and should be both growable and shrinkable. The per-stream minimum reservation fits well with the current window settings mechanism. Burst space is returned to sender via an window-update type frame.

By both limiting the number of streams and the burst size, the reciever can bound memory needs. 

As a concrete example: A SPDY server supports 100 concurrent streams per connection, with a per-stream window of 8K and a burst of 1MB. This bounds memory usage at 1M * 100*8K = 1.8MB while allowing any individual stream to quickly ramp to up to 1MB, if needed. 

Obviously, the sender can use feedback from tcp flow control to try to avoid buff
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/29/12 7:46 AM
Simone and I have been debating offline various flow control algorithms and have not reached any significant conclusions. However I have come up with some formalisation of how we can rate various flow control proposals.

IMNSHO the primary factors that should rate flow control algorithms  are:

1.1 Uses full all available bandwidth
The whole point of SPDY is to make the web faster, so if there is a willing stream producer, a willing stream consumer and available capacity in the pipe between SPDY implementations, then we should allow that capacity to be used up to and possibly even slightly beyond TCP/IP flow control.

1.2 No infinite postponement of a stream
The behaviour of one stream should not be able to infinitely postpone the delivery of data on another stream. We can control the behaviour of compliant SPDY senders and receivers, but we cannot control the behaviour of stream consumers and producers (the application).  Thus we have to consider that stream producers and consumers may act maliciously (either by design, by error or by force majeure (eg DNS resolution suddenly blocks)).   This does not mean that we have to avoid congesting the TCP pipe, just so long as we know the other end (the SPDY receiver) will eventually uncongest the pipe even if a stream consumer is not reading data - ie that the SPDY receiver has sufficient buffers.

1.3 Little incentive to use multiple connections
One of the problems with HTTP that has driven the development of SPDY is to remove the incentive for clients to use multiple connections.  Any per connection limit (such as TCP/IP slow start windows) are incentives to have multiple connections.  For example if we allocate a default initial per connection window, then a client that opens 2 connections will get twice times that limit and better initial performance.  Worse still, because of TCP/IP slow start, once you open 2 connections, you'll probably open 6 or 8 to get multiple slow start window allocations as well.

1.4 No infinite buffering
When an endpoint accepts a connection and/or a stream, it must be able to know the maximum memory that it has to commit to provide in order to satisfy the specification.  If accepting a connection/stream can result in unlimited memory commitments then we are open to denial of service attacks and unpredictable application performance.

The secondary factors that we should consider are many, but I think they should include:

2.1 Complexity
Avoiding complexity is a motherhood statement.  Yes we want to be as simple as possible, but not to the point were we significantly compromise the primary factors.  At the end of they day, there is likely to be perhaps a few hundred or a few thousand SPDY implementations that will provide infrastructure for millions of developers - better we suck up some complexity rather than fail a primary objective.

2.2 Fairness
Another motherhood statement. Yes we want to be fair between streams, but fair is really subjective and difficult to quantify.  Is taking frames from streams in a round robin manner fair?  some would say yes, but others would say that a stream that has not participated in any recent rounds should have more of a share than one that has sent in every round. I think the primary concern in the protocol spec is to avoid the possibility of infinite postponement and then we can mostly leave fairness measures to be implementation details/features.

2.3 Priorities
See fairness.  If we can't work out what fair is, then it is even harder to work out what priorities mean.   I think priorities are a nice to have feature, but should not compromise the primary objectives.


The other thing I've concluded is that there is no perfect solution.  Even if the flow controlling algorithm was to ask an all knowing connection GOD if a frame could be sent or not, if that GOD gives free will to the stream consumers then GOD is fallible.  GOD might see a single stream that is flowing well and allow it to keep sending frames right up to the capacity of a fat pipe, but then just as another frame is opened the consumer of the first frame may stop reading and all the data in the fat  pipe will have to be buffered so that the new stream can send some frames.  But that buffering may consume almost all the memory reservation of the receiver, so that now GOD cannot allow the new stream to go at a full rate because the receivers buffers are almost full and he cannot risk the new stream suddenly stopping consuming like the first did.

Once we accept that an all knowing algorithm can still be fallible in the face of  streams with free will, then we just have to accept that we are looking for the best approximation of a perfect solution.

So the current 64KB window per stream actually rates pretty well on most of these concerns, except for one: 1.1 A 64KB window on a fast pipe will limit bandwidth utilisation if there is any significant latency; 1.2 A stream cannot be blocked by another stream not being consumed; 1.3 Resources are allocated per stream, so there is little incentive to use multiple connections, and with TCP slow start there is an incentive to use an already warmed up SPDY connection over a new one; 1.4 implementations know the commitment is 64KB to accept a new stream;  2.1 it's moderately simple; 2.2 so long as the sender does not create long frame queues, it can be fair in a round robin sense; 2.3 priorities could be implemented to affect round robin fairness.

So the only think we really a missing is the ability to use the full capacity of a TCP connection.  The 64KB has already been demonstrated to slow throughput .

The proposals to introduce a per connection window or burst allowance do look attractive, but my concern is that they sacrifice 1.4 to meet 1.1.  Ie any per connection limit will create an incentive to open multiple connections in order to obtain the benefits of multiple per connection allocations of resources.

Instead,  I think that we should look at a system that allows a connection to grow the per stream window if the pipe supports the extra bandwidth.  More over, that new streams created on that connection should be allocated the same grown window (perhaps adjusted down a little for the number of streams), so that they do not need to slow start and there is an incentive to open a new stream on an existing connection rather than create a new one...
Re: [spdy-dev] Thinking about flow control Simone Bordet 5/29/12 8:38 AM
Hi,

On Tue, May 29, 2012 at 4:46 PM, Greg Wilkins <gr...@intalio.com> wrote:
> Simone and I have been debating offline various flow control algorithms and
> have not reached any significant conclusions. However I have come up with
> some formalisation of how we can rate various flow control proposals.

I agree with the criteria.

In case of fast pipes, TCP buffers can be enlarged with kernel tuning
in order to support the fast pipe.
So, I don't see that bad that we have a per-connection window, as long
as we can tune that (and that's an implementation detail), or find a
way to communicate new values discovered dynamically (e.g. a new
SETTINGS flag) interacting with TCP congestion.
The requirement of tuning the per-connection window is equivalent (and
probably done in consequence) of tuning the TCP buffers in case of a
fast pipe.

Having such limit will limit 1.1 (which is bad), and limit 1.4 (which
is good). Can't see yet how to get both satisfied.
Bullet 1.3 can be forbidden by the spec (but then, who cares if the
HTTP spec suggests no more than 2 connections per domain ? Everybody
uses 6, so even if it's forbidden, it may be ignored ?).
But I agree that the solution should disincentive to open additional
connections.

Note that TCP can autotune itself, see net.ipv4.tcp_rmem and
net.ipv4.tcp_wmem parameters in Linux.
Perhaps we can mimic that autotuning capability, but it's becoming
scary how much we're reimplementing the TCP bits on top of SPDY. But
perhaps I am too impressionable :)

Simon ...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/29/12 9:29 AM


Instead,  I think that we should look at a system that allows a connection to grow the per stream window if the pipe supports the extra bandwidth.  More over, that new streams created on that connection should be allocated the same grown window (perhaps adjusted down a little for the number of streams), so that they do not need to slow start and there is an incentive to open a new stream on an existing connection rather than create a new one.   Growing the initial window size does not violate 1.4 as the size is known when a stream is accepted (and perhaps can be adjusted down if resources are short).

So how can we detect if a stream window can be grown?  Sending the entire window before receiving a window update is not sufficient, as that can equally indicate a slow consumer or a fast pipe.  Perhaps sending the entire window without seeing any TCP/IP flow control is one way? ie we can grow our stream windows until we reach either a limit or we see tcp/ip flow control?    Assuming we can come up with a way to decide when to grow, then I think this style of flow control rates OK: 1.1 windows can grow to TCP capacity; 1.2 Streams cannot block other streams; 1.3 incentive to used warmed up connection 1.4 memory requirements
...
Re: [spdy-dev] Thinking about flow control William Chan 5/29/12 9:39 AM


So how can we detect if a stream window can be grown?  Sending the entire window before receiving a window update is not sufficient, as that can equally indicate a slow consumer or a fast pipe.  Perhaps sending the entire window without seeing any TCP/IP flow control is one way? ie we can grow our stream windows until we reach either a limit or we see tcp/ip flow control?    Assuming we can come up with a way to decide when to grow, then I think this style of flow control rates OK: 1.1 windows can grow to TCP capacity; 1.2 Streams cannot block other streams; 1.3 incentive to used warmed up connection 1.4 memory requirements known when accepting stream; 2.1 moderate complexity; 2.2 writer can implement fairness in frame selection 2.3; priorities can be used to influence fair frame selection.

Anyway... let me not get ahead of myself proposing solutions... what do people think for the criteria for rating flow control algorithms?

Very nice.

IMO the most interesting case is when a number of consumers get very slow - for a longer time ( minutes ). You must ke
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/29/12 9:44 AM

Nice writeup! I think that is a great way to rate and consider solutions!

I think that bufferbloat (which should be a real worry) might want an explicit mention . It sorta fits into your categorizations/goals but has implications for latency jitter and measurement (and fairness, but you have a category/goal for that)

A proposed flow-control window update solution:

Whenever a stream has more data that it wishes to send right now and the tcp connection  is writable and the stream is restricted from sending by flow control, send an update for the stream indicating this to the other side.
This update could be a size update of size 0, or it could be another frame.

On the receiver side, receipt of this would indicate the sender is throttled by SPDY's flow control.

Figuring out the appropriate window for that stream would be  implementation dependent, but, as a guideline, it should probably be the maximum window size for any stream you've recently increased or 50% more, whichever is greater. Of course, window updates should be done only so long as the receiver has space in b

This is meant to be a simple guideline that will hopefully work fairly well.

If good estimates for rtt and bw are available, use that to bound the max possible send size. If the size of the tcp window is known, use that as a max upper bound.

-=R

...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/29/12 10:25 AM




IMO the most interesting case is when a number of consumers get very slow - for a longer time ( minutes ). You must keep bound memory (1.4), but still support 1.1 and 1.2, while the slow steams are already using most of the memory.

I would add a

2.4 Don't penalize the good streams for the faults of the bad ones. 
A bad stream is a stream where consumer suddenly stops accepting bytes or slows down, on a stream that has a large window and lots of cached bytes.

What I'm trying to get is ability to drop frames in intermediaries, and have some re-transmit. It may sound like a big complexity - but there are quite a few systems doing this, in particular TCP.

I'm not sure I understand what you mean by this. When you say intermediary, do you mean a transparent one? If the intermediary is actually an endpoint of the SPDY connection, then it clearly can do anything it wants (dropping frames, etc).

I mean the SPDY receiver. It can be a proxy or the final server, but it needs to buffer frames until the final endpoint (servlet, next backend) can consume them. 

...
Re: [spdy-dev] Thinking about flow control William Chan 5/29/12 10:34 AM


In the current flow control proposals ( per stream, or per connection ) you can't drop frames, you can stop sending window updates, but you must keep in memory all frames you received until they are consumed.

Yes.
 


Also, are you saying you want the client to retransmit to the intermediary? SPDY is over a "reliab
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/29/12 1:44 PM


 


Also, are you saying you want the client to retransmit to the intermediary? SPDY is over a "reliable" connection, so any dropped packets should already be retransmitted. Can you clarify further?

Yes, TCP is "reliable" and has its own flow control, including the ability to drop packets when it needs to.

SPDY frames are over TCP - so the frames can't be dropped, once you receive a frame you must keep it in (bound - 1.4) memory until the actual endpoint consumes them.

We are copying 1/2 of TCP - the flow control window, but are missing the other 1/2, dropping packets and re-transmission. IP packets are dropped because they get "lost", but also if router buffers are full or they timeout.

Why would we need to drop frames and retransmit them? The receiver is able to communicate its buffer sizes via the stream windows. If there is any problem, it should communicate it via a RST_STREAM.

RST_STREAM is a fine way to drop frames of stuck streams. Maybe we should just define a  status code 'slow stream using too many buffers'.

The receiver can send its buffer size - but you can still get into a state where a lot of streams are slow and use the max buffer size they are allowed to use. If the total per-connection memory is filled with slow stream at some point the good streams no longer have space.

 
...
Re: [spdy-dev] Thinking about flow control William Chan 5/29/12 3:43 PM
I was surprised to see we don't have a RST_STREAM code for the server to indicate that it wants to abort it for whatever reason. I think we should add one like that, but we don't need one as specific as 'slow stream using too many buffers'. Or is INTERNAL_ERROR appropriate here? That'd be similar to a HTTP 5XX error, and it can be delivered at any point. But I guess I don't really like that, as I like INTERNAL_ERROR to indicate a bug only, and I think servers can abort a stream without it necessarily being an implementation bug.
 

The receiver can send its buffer size - but you can still get into a state where a lot of streams are slow and use the max buffer size they are allowed to use. If the total per-connection memory is filled with slow stream at some point the good streams no longer have space.

I think I see what you're saying now. If the stream is totally hung, then yes, you want to abort it so you can forcibly reclaim the memory. Fair enough. This is equivalent to the HTTP case of just closing the socket to abort.
 

 
I do not believe we should allow dropping frames and retransmitting them individually.

Not individual frames - but a proxy for example should be able to send a RST_STREAM or similar message indicating that a stream is too slow and is using too much of the buffer space. 

Ideally this will not be a simple RST_STREAM followed by another full upload attempt of the entire stream - you could improve by sending an indication of how much has been consumed, and
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/29/12 3:47 PM


On 29 May 2012 22:44, Costin Manolache <cos...@gmail.com> wrote:

I think documenting that RST_STREAM can be used for flow control would make us more similar with HTTP, where stuck TCP connections may be aborted if the proxy needs the memory. 

We just have to be very careful about idempotent streams being reset, else we end up in the current HTTP pipeline problems.

But if the problem of idem potency can be solved, then RST is probably the only way we can reduce buffers allocated to a stuck stream.     Although it will still rely on HTTP retry semantics and user interactions.

cheers

Re: [spdy-dev] Thinking about flow control Roberto Peon 5/29/12 3:51 PM


On Tue, May 29, 2012 at 3:47 PM, Greg Wilkins <gr...@intalio.com> wrote:


On 29 May 2012 22:44, Costin Manolache <cos...@gmail.com> wrote:

I think documenting that RST_STREAM can be used for flow control would make us more similar with HTTP, where stuck TCP connections may be aborted if the proxy needs the memory. 

We just have to be very careful about idempotent streams being reset, else we end up in the current HTTP pipeline problems.

Yes. I think that the amount of complexity that this adds is large, especially for application writers :/
 

But if the problem of idem potency can be solved, then RST is probably the only way we can reduce buffers allocated to a stuck stream.     Although it will still rely on HTTP retry semantics and user interactions.

I don't see how it could be reasonably solved, thou
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/29/12 9:12 PM


On Tue, May 29, 2012 at 3:47 PM, Greg Wilkins <gr...@intalio.com> wrote:
One relatively easy solution - used on older versions of android - is to have the client hold to the data it sent, and the proxy or server to indicate how much was consumed, with negative numbers indicating that client needs to resend some data. 

For example you want to upload a 1M file, you start sending frames up to the window size ( say 128k ), but you don't delete/GC the frames you sent until you get the next window update from server. The window update will have an extra field indicating how much was consumed.

If the stream gets very slow - the server will send a window update with a very small window, and a negative number of bytes consumed, and empty the buffers used by that stream. The client will just resend the data at the slower speed.

If the consumer is fast - server can increase the window size, and keep sending updates on how much was consumed, and the client will free the 're-transmit' memory when server indicates it was consumed. 

It sounds complicated because I'm not explaining it right :-) This actually becomes more interes
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/30/12 3:36 AM
On 30 May 2012 06:12, Costin Manolache <cos...@gmail.com> wrote:
> One relatively easy solution - used on older versions of android - is to
> have the client hold to the data it sent, and the proxy or server to
> indicate how much was consumed, with negative numbers indicating that client
> needs to resend some data.
>
> For example you want to upload a 1M file, you start sending frames up to the
> window size ( say 128k ), but you don't delete/GC the frames you sent until
> you get the next window update from server. The window update will have an
> extra field indicating how much was consumed.
>
> If the stream gets very slow - the server will send a window update with a
> very small window, and a negative number of bytes consumed, and empty the
> buffers used by that stream. The client will just resend the data at the
> slower speed.
>
> If the consumer is fast - server can increase the window size, and keep
> sending updates on how much was consumed, and the client will free the
> 're-transmit' memory when server indicates it was consumed.
>
> It sounds complicated because I'm not explaining it right :-) This actually
> becomes more interesting if you want to keep the streams flowing while the
> TCP connection is interrupted.
>
> The cost is that both sender and receiver will need to buffer window-size of
> data.


Costin,

My gut reaction is YUCK!!!!  this is re implementing even more or TCP.
But then on consideration, perhaps with a bit of complexity added, it
might not be that bad.

We really only need to start buffering sent data when a streams window
has grown to be a significant percentage of the total available
buffers.  So we might be able to say that we will never shrink a
stream window below 64KB, so if a stream never sends more than that
much data, then no send buffers are needed.   So it is kind of a
tradeoff deal, we will let a stream use a large share of the bandwidth
and buffers, but only on the terms that it buffers its excess sends so
that we can reduce the window if need be.  If we are operating in a
mode with many active streams, then hopefully no stream would need to
take such a large window, so no send buffering would be needed.

Even when send buffering is needed, in many cases the implementation
will be able to do that efficiently using the o...
Re: [spdy-dev] Thinking about flow control Simone Bordet 5/30/12 3:47 AM
Hi,

On Wed, May 30, 2012 at 6:12 AM, Costin Manolache <cos...@gmail.com> wrote:
> One relatively easy solution - used on older versions of android - is to
> have the client hold to the data it sent, and the proxy or server to
> indicate how much was consumed, with negative numbers indicating that client
> needs to resend some data.
>
> For example you want to upload a 1M file, you start sending frames up to the
> window size ( say 128k ), but you don't delete/GC the frames you sent until
> you get the next window update from server. The window update will have an
> extra field indicating how much was consumed.

You don't want to send window updates until you're sure data has being
consumed by the application.
Otherwise you're duplicating what the TCP ACK is saying, and it is of
no interest to the sender.

I think we should strive for much more simplicity here: if one stream
has occupied the whole connection window, and does not send window
updates, then it's the same situation as being TCP congested: there is
nothing you can do apart timing out that stream and reset it.

Simon
--
http://cometd.org
http://intalio.com
http://bordet.blogspo...
Re: [spdy-dev] Thinking about flow control Simone Bordet 5/30/12 3:53 AM
Hi,

On Tue, May 29, 2012 at 6:44 PM, Roberto Peon <fe...@google.com> wrote:
> A proposed flow-control window update solution:
>
> Whenever a stream has more data that it wishes to send right now and the tcp
> connection  is writable and the stream is restricted from sending by flow
> control, send an update for the stream indicating this to the other side.
> This update could be a size update of size 0, or it could be another frame.
>
> On the receiver side, receipt of this would indicate the sender is throttled
> by SPDY's flow control.

What the receiver can do with this information ?

I think the work is entirely on the sender, who has to figure out the
connection window, and have some logic to redistribute that window
among the streams.

Simon
--
http://cometd.org
http://intalio.com
http://bordet.blogspot.com
----
Finally, no matter how good the architecture and design are,
to deliver bug-free software with optimal performance and reliability,
the im...
Re: [spdy-dev] Thinking about flow control Alek Storm 5/30/12 4:10 AM
I'd like to advocate something completely different: a modified round-robin scheme that is guaranteed to use all available bandwidth, ensures that no stream is infinitely postponed, rewards streams that have not sent data recently, and allows for fine-grained prioritization/compensation for data processing rates that vary by stream at the other endpoint. First, since there will always be a per-connection window in the form of TCP flow control, we can do away with per-stream windows, the only justification for which seemed to be avoiding infinite buffering.

Each stream has both a "current window" and a "round delta". When it is a particular stream's turn in the round-robin to send data, it sends a number of bytes equal to its current window or the number of bytes sitting in its output buffer, whichever is smaller. Its current window is then decremented by however many bytes it sent. After each stream's turn, the current windows of every stream are incremented by their round deltas. In this manner, no stream can monopolize the session, and streams which send less data than their current window would allow in a given round are rewarded in the next with a larger-than-normal window. In addition, since every stream is more-or-less constantly sending data as long as its output buffer is non-empty, the connection will be saturated with data until every stream is blocked, waiting to compute more data to send.

Consider an extreme case: Five streams are currently open, but only one has been sending data for quite some time; the others are silent. Each round, it sends its current window, decrements it to zero, then increments it by its round delta five times while the others pass on the opportunity to send data, then the round repeats. Suddenly, one of the other streams begins transmitting - its current window has been accumulating for so long that it is allowed to send a large amount of data at once. This is fair, because the other stream has been sending data exclusively for some time. After its current window is exhausted, the other stream goes back to transmitting. It's also an argument for a (reasonably large) cap on the size of current windows - perhaps a multiple of its round delta.

Despite the lack of per-stream fixed windows as in spdy/3, this scheme allows receivers to control precisely how much throughput they'd like to handle for a given stream by specifying each one's round delta individually, taking into account both its priority and the estimated speed at which its buffer can be drained (how fast incoming data can be processed). There are multiple ways to implement this communication; I'm unsure of the optimal choice. Note that no matter how inefficiently the client allocates round deltas, full connection bandwidth will always be utilized.

Since there is always a per-connection window, whether in TCP or both TCP and SPDY, there will always be an incentive to circumvent it by opening multiple connections. I don't believe any proposal will be able to solve this, but the problem is mitigated by the advantage of using a pre-warmed TCP connection. This also means that infinite buffering is a red herring (I think).

What do you guys think? I'd love to hear any feedback at all.

Thanks,
Alek

P.S. In the v3 spec, WINDOW_UPDATE specifically states that receivers must buffer all control frames. Wouldn't this be a problem if the sender transmits a large SYN_STREAM or SYN_REPLY, or several large HEADERS? Why can't the window delta just specify the total number of bytes in all frames tied to a specific stream?

Instead,  I think that we should look at a system that allows a connection to grow the per stream window if the pipe supports the extra bandwidth.  More over, that new streams created on that connection should be allocated the same grown window (perhaps adjusted down a little for the number of streams), so that they do not need to slow start and there is an incentive to open a new stream on an existing connection rather than create a new one.   Growing the initial window size does not violate 1.4 as the size is known when a stream is accepted (and perhaps can be adjusted down if resources are short).

So how can we detect if a stream window can be grown?  Sending the entire window before receiving a window update is not sufficient, as that can equally indicate a slow consumer or a fast pipe.  Perhaps sending the entire window without seeing any TCP/IP flow control is one way? ie we can grow our stream windows until we reach either a limit or we see tcp/ip flow control?    Assuming we can come up with a way to decide when to grow, then I think this style of flow control rates OK: 1.1 windows can grow to TCP capacity; 1.2 Streams cannot block other streams; 1.3 incentive to used warmed up connection 1.4 memory requirements known when accepting stream; 2.1 moderate complexity; 2.2 writer can implement fairness in frame selection 2.3; priorities can be used to influence fair frame selection.

Anyway... let me not get ahead of myself proposing solutions... what do people think for the criteria for rating flow control algorithms?

cheers











Instead,  I think that we should look at a system that allows a connection to grow the per stream window if the pipe supports the extra bandwidth.  More over, that new streams created on that connection should be allocated the same grown window (perhaps adjusted down a little for the number of streams), so that they do not need to slow start and there is an incentive to open a new stream on an existing connection rather than create a new one.   Growing the initial window size does not violate 1.4 as the size is known when a stream is accepted (and perhaps can be adjusted down if resources are short).

So how can we detect if a stream window can be grown?  Sending the entire window before receiving a window update is not sufficient, as that can equally indicate a slow consumer or a fast pipe.  Perhaps sending the entire window without seeing any TCP/IP flow control is one way? ie we can grow our stream windows until we reach either a limit or we see tcp/ip flow control?    Assuming we can come up with a way to decide when to grow, then I think this style of flow control rates OK: 1.1 windows can grow to TCP capacity; 1.2 Streams cannot block other streams; 1.3 incentive to used warmed up connection 1.4 memory requirements known when accepting stream; 2.1 moderate complexity; 2.2 writer can implement fairness in frame selection 2.3; priorities can be used to influence fair frame selection.

Anyway... let me not get ahead of myself proposing solutions... what do people think for the criteria for rating flow control algorithms?

cheers











Instead,  I think that we should look at a system that allows a connection to grow the per stream window if the pipe supports the extra bandwidth.  More over, that new streams created on that connection should be allocated the same grown window (perhaps adjusted down a little for the number of streams), so that they do not need to slow start and there is an incentive to open a new stream on an existing connection rather than create a new one.   Growing the initial window size does not violate 1.4 as the size is known when a stream is accepted (and perhaps can be adjusted down if resources are short).

So how can we detect if a stream window can be grown?  Sending the entire window before receiving a window update is not sufficient, as that can equally indicate a slow consumer or a fast pipe.  Perhaps sending the entire window without seeing any TCP/IP flow control is one way? ie we can grow our stream windows until we reach either a limit or we see tcp/ip flow control?    Assuming we can come up with a way to decide when to grow, then I think this style of flow control rates OK: 1.1 windows can grow to TCP capacity; 1.2 Streams cannot block other streams; 1.3 incentive to used warmed up connection 1.4 memory requirements known when accepting stream; 2.1 moderate complexity; 2.2 writer can implement fairness in frame selection 2.3; priorities can be used to influence fair frame selection.

Anyway... let me not get ahead of myself proposing solutions... what do people think for the criteria for rating flow control algorithms?

cheers












On Tuesday, May 29, 2012 9:46:18 AM UTC-5, Greg Wilkins wrote:
Simone and I have been debating offline various flow control algorithms and have not reached any significant conclusions. However I have come up with some formalisation of how we can rate various flow control proposals.

IMNSHO the primary factors that should rate flow control algorithms  are:

1.1 Uses full all available bandwidth
The whole point of SPDY is to make the web faster, so if there is a willing stream producer, a willing stream consumer and available capacity in the pipe between SPDY implementations, then we should allow that capacity to be used up to and possibly even slightly beyond TCP/IP flow control.

1.2 No infinite postponement of a stream
The behaviour of one stream should not be able to infinitely postpone the delivery of data on another stream. We can control the behaviour of compliant SPDY senders and receivers, but we cannot control the behaviour of stream consumers and producers (the application).  Thus we have to consider that stream producers and consumers may act maliciously (either by design, by error or by force majeure (eg DNS resolution suddenly blocks)).   This does not mean that we have to avoid congesting the TCP pipe, just so long as we know the other end (the SPDY receiver) will eventually uncongest the pipe even if a stream consumer is not reading data - ie that the SPDY receiver has sufficient buffers.

1.3 Little incentive to use multiple connections
One of the problems with HTTP that has driven the development of SPDY is to remove the incentive for clients to use multiple connections.  Any per connection limit (such as TCP/IP slow start windows) are incentives to have multiple connections.  For example if we allocate a default initial per connection window, then a client that opens 2 connections will get twice times that limit and better initial performance.  Worse still, because of TCP/IP slow start, once you open 2 connections, you'll probably open 6 or 8 to get multiple slow start window allocations as well.

1.4 No infinite buffering
When an endpoint accepts a connection and/or a stream, it must be able to know the maximum memory that it has to commit to provide in order to satisfy the specification.  If accepting a connection/stream can result in unlimited memory commitments then we are open to d
...
Re: [spdy-dev] Thinking about flow control Mike Belshe 5/30/12 8:04 AM


On Tue, May 29, 2012 at 7:46 AM, Greg Wilkins <gr...@intalio.com> wrote:
Simone and I have been debating offline various flow control algorithms and have not reached any significant conclusions. However I have come up with some formalisation of how we can rate various flow control proposals.

IMNSHO the primary factors that should rate flow control algorithms  are:

1.1 Uses full all available bandwidth
The whole point of SPDY is to make the web faster, so if there is a willing stream producer, a willing stream consumer and available capacity in the pipe between SPDY implementations, then we should allow that capacity to be used up to and possibly even slightly beyond TCP/IP flow control.

1.2 No infinite postponement of a stream
The behaviour of one stream should not be able to infinitely postpone the delivery of data on another stream. We can control the behaviour of compliant SPDY senders and receivers, but we cannot control the behaviour of stream consumers and producers (the application).  Thus we have to consider that stream producers and consumers may act maliciously (either by design, by error or by force majeure (eg DNS resolution suddenly blocks)).   This does not mean that we have to avoid congesting the TCP pipe, just so long as we know the other end (the SPDY receiver) will eventually uncongest the pipe even if a stream consumer is not reading data - ie that the SPDY receiver has sufficient buffers.

1.3 Little incentive to use multiple connections
One of the problems with HTTP that has driven the development of SPDY is to remove the incentive for clients to use multiple connections.  Any per connection limit (such as TCP/IP slow start windows) are incentives to have multiple connections.  For example if we allocate a default initial per connection window, then a client that opens 2 connections will get twice times that limit and better initial performance.  Worse still, because of TCP/IP slow start, once you open 2 connections, you'll probably open 6 or 8 to get multiple slow start window allocations as well.

1.4 No infinite buffering
When an endpoint accepts a connection and/or a stream, it must be able to know the maximum memory that it has to commit to provide in order to satisfy the specification.  If accepting a connection/stream can result in unlimited memory commitments then we are open to denial of service attacks and unpredictable application performance.

I think the desire is more specific "no infinite buffering without requiring a proxy to close individual streams".  If you're willing to close the mal-behaving stream, the solution is much easier.


The secondary factors that we should consider are many, but I think they should include:

2.1 Complexity
Avoiding complexity is a motherhood statement.  Yes we want to be as simple as possible, but not to the point were we significantly compromise the primary factors.  At the end of they day, there is likely to be perhaps a few hundred or a few thousand SPDY implementations that will provide infrastructure for millions of developers - better we suck up some complexity rather than fail a primary objective.

2.2 Fairness
Another motherhood statement. Yes we want to be fair between streams, but fair is really subjective and difficult to quantify.  Is taking frames from streams in a round robin manner fair?  some would say yes, but others would say that a stream that has not participated in any recent rounds should have more of a share than one that has sent in every round. I think the primary concern in the protocol spec is to avoid the possibility of infinite postponement and then we can mostly leave fairness measures to be implementation details/features.

2.3 Priorities
See fairness.  If we can't work out what fair is, then it is even harder to work out what priorities mean.   I think priorities are a nice to have feature, but should not compromise the primary objectives.


The other thing I've concluded is that there is no perfect solution.  Even if the flow controlling algorithm was to ask an all knowing connection GOD if a frame could be sent or not, if that GOD gives free will to the stream consumers then GOD is fallible.  GOD might see a single stream that is flowing well and allow it to keep sending frames right up to the capacity of a fat pipe, but then just as another frame is opened the consumer of the first frame may stop reading and all the data in the fat  pipe will have to be buffered so that the new stream can send some frames.  But that buffering may consume almost all the memory reservation of the receiver, so that now GOD cannot allow the new stream to go at a full rate because the receivers buffers are almost full and he cannot risk the new stream suddenly stopping consuming like the first did.

Once we accept that an all knowing algorithm can still be fallible in the face of  streams with free will, then we just have to accept that we are looking for the best approximation of a perfect solution.

So the current 64KB window per stream actually rates pretty well on most of these concerns, except for one: 1.1 A 64KB window on a fast pipe will limit bandwidth utilisation if there is any significant latency; 1.2 A stream cannot be blocked by another stream not being consumed; 1.3 Resources are allocated per stream, so there is little incentive to use multiple connections, and with TCP slow start there is an incentive to use an already warmed up SPDY connection over a new one; 1.4 implementations know the commitment is 64KB to accept a new stream;  2.1 it's moderately simple; 2.2 so long as the sender does not create long frame queues, it can be fair in a round robin sense; 2.3 priorities could be implemented to affect round robin fairness.

So the only think we really a missing is the ability to use the full capacity of a TCP connection.  The 64KB has already been demonstrated to slow throughput .

The proposals to introduce a per connection window or burst allowance do look attractive, but my concern is that they sacrifice 1.4 to meet 1.1.  Ie any per connection limit will create an incentive to open multiple connections in order to obtain the benefits of multiple per connection allocations of resources.

The current flow control is simply a tradeoff.  It trades 1.1 to have 1.4.  (personally, I think this is a poor trade)
 

Instead,  I think that we should look at a system that allows a connection to grow the per stream window if the pipe supports the extra bandwidth.  More over, that new streams created on that connection should be allocated the same grown window (perhaps adjusted down a little for the number of streams), so that they do not need to slow start and there is an incentive to open a new stream on an existing connection rather than create a new one.   Growing the initial window size does not violate 1.4 as the size is known when a stream is accepted (and perhaps can be adjusted down if resources are short
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/30/12 9:22 AM


On Wed, May 30, 2012 at 3:47 AM, Simone Bordet <sbo...@intalio.com> wrote:
Hi,

On Wed, May 30, 2012 at 6:12 AM, Costin Manolache <cos...@gmail.com> wrote:
> One relatively easy solution - used on older versions of android - is to
> have the client hold to the data it sent, and the proxy or server to
> indicate how much was consumed, with negative numbers indicating that client
> needs to resend some data.
>
> For example you want to upload a 1M file, you start sending frames up to the
> window size ( say 128k ), but you don't delete/GC the frames you sent until
> you get the next window update from server. The window update will have an
> extra field indicating how much was consumed.

You don't want to send window updates until you're sure data has being
consumed by the application.

Why ? Window updates indicate there is space for more bytes in the buffers, not that the bytes have been consumed.

 
Otherwise you're duplicating what the TCP ACK is saying, and it is of
no interest to the sender.

The problem is duplicating only part of TCP flow control. ACK is a part of flow control, just like the window update. TCP relies on packet drops and ACKs to determine what to send and how fast.

Even in HTTP the sender has to be able to deal with drops and re-transmits. The status code is a form of ACK, and plenty of problems have been caused by not dealing properly with drops and retries in http.

Bufferbloat is mentioned quite a bit - maybe we should look at ECN ( congestion notification ), which is the alternative to ACK and dropping packets.  

SPDY duplicates stuff from lower layers - multiplexing, a part of flow control.  It's likely to duplicate some of the problems and make other worse by not duplicating enough :-)


Costin


I think we should strive for much more simplicity here: if one stream
has occupied the whole connection window, and does not send window
updates, then it's the same situation as being TCP congested: there is
nothing you can do apart timing out that stream and reset it.
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/30/12 10:43 AM


On Wed, May 30, 2012 at 9:22 AM, Costin Manolache <cos...@gmail.com> wrote:


On Wed, May 30, 2012 at 3:47 AM, Simone Bordet <sbo...@intalio.com> wrote:
Hi,

On Wed, May 30, 2012 at 6:12 AM, Costin Manolache <cos...@gmail.com> wrote:
> One relatively easy solution - used on older versions of android - is to
> have the client hold to the data it sent, and the proxy or server to
> indicate how much was consumed, with negative numbers indicating that client
> needs to resend some data.
>
> For example you want to upload a 1M file, you start sending frames up to the
> window size ( say 128k ), but you don't delete/GC the frames you sent until
> you get the next window update from server. The window update will have an
> extra field indicating how much was consumed.

You don't want to send window updates until you're sure data has being
consumed by the application.

Why ? Window updates indicate there is space for more bytes in the buffers, not that the bytes have been consumed.

For any decent implementation, so long as the bytes in the buffers aren't blocking any other stream, this is good enough, and certainly no worse that TCP.
For a proxy, 'consumed by the application' translates to 'moved ingress bytes to egress bytes'.
 

 
Otherwise you're duplicating what the TCP ACK is saying, and it is of
no interest to the sender.

The problem is duplicating only part of TCP flow control. ACK is a part of flow control, just like the window update. TCP relies on packet drops and ACKs to determine what to send and how fast.

Even in HTTP the sender has to be able to deal with drops and re-transmits. The status code is a form of ACK, and plenty of problems have been caused by not dealing properly with drops and retries in http.

Bufferbloat is mentioned quite a bit - maybe we should look at ECN ( congestion notification ), which is the alternative to ACK and dropping packets.  

SPDY duplicates stuff from lower layers - multiplexing, a part of flow control.  It's likely to duplicate some of the problems and make other worse by not duplicating enough :-)

rexmits are a necessary part of TCP because of packet loss. We have a reliable transport that already does rexmit for us. We shouldn't need to reimplement that-- it is a fair bit of additional complexity and I believe that we don't need it to solve our problems.

In particular, the scheme I proposed earlier should address all of the issues we've brought up so far. Roughly, it is:

Assume:
   we have per-stream window sizes.
   we have per-connection window sizes.
  A sender can send up to (min(per-stream, per-connection)) bytes.

"a stream is blocked"  means that the sender for that stream:
  * can write to the socket (i.e. the socket is writable and there is space in the TCP egress buffers)
  * has no higher priority stream that is currently sending (and thus blocking this stream because of prioritization)
  * there are bytes to be sent on this stream.

The algorithm is then (pseudocode):

OnWritable(socket, stream_id):
  if (bytes_to send && socket_writable && clear_to_send_this_priority):
    max_window = min(connection_flow_control_window),
                              flow_control_window[stream_id]))
    bytes_sent = send(socket, bytes_to_send, min(bytes_to_send.len(), max_window))
    if (StillWritable(socket) && bytes_to_send.len() > max_window):
      SendBlockedFrame(socket, stream_id, bytes_to_send.len() - max_window)
      last_time_blocked[stream_id] = Now()

OnWindowUpdate(stream_id, window_update_frame):
  flow_control_window[stream_id] += window_update_frame.stream_update_size;
  connection_flow_control_window += window_update_frame.overall_update_size;
  
  // If we were blocked
  if (bytes_to_send.len() > 0 && last_time_blocked[stream_id] > 0):
    time_blocked = Now() - last_time_blocked[stream_id]
    SendUnblockedFrame(socket, stream_id, bytes_to_send.len(), time_blocked)
    max_window = min(connection_flow_control_window),
                              flow_control_window[stream_id]))   
    if max_window >= bytes_to_send.len():
      last_time_blocked[stream_id] = 0
    else:
      last_time_blocked[stream_id] = Now()
 
In natural language:
if a sender is ever blocked, then it should send a frame to the receiver indicating the stream ID which is blocked, with then amount of bytes it would wish to send, but couldn't because of flow-control.
When a sender receives a window update frame, it should indicate how many bytes are blocked and for how long

The receiver, upon receipt of such a frame, could increase the various window sizes as indicated by the frames which tell the receiver the number (and possible duration) of the blocked bytes (hopefully up to a maximum as estimated by the BDP).

This scheme doesn't require much additional complexity, and it meets all of the ratings targets proposed by Greg earlier.
This
...
Re: [spdy-dev] Thinking about flow control William Chan 5/30/12 11:34 AM
First let me say that I think the re-implementing rexmit at the SPDY level when SPDY operates over a reliable transport is a mistake. I think most people agree that's a mistake. If anyone other than Costin supports rexmit at the SPDY level, please speak up.
"how many bytes are blocked" is not well defined. Let's say the sender is reading from a file, whose length he doesn't know. Is "how many bytes are blocked" just the next chunk size he would have sent in the next send() call, or is it rather the remaining amount of data on the stream? It's not clear to me that this heuristic is useful. Also, what's the "how long" used for? Preventing starvation?
 

The receiver, upon receipt of such a frame, could increase the various window sizes as indicated by the frames which tell the receiver the number (and possible duration) of the blocked bytes (hopefully up to a maximum as estimated by the BDP).

I think I need more clarification on the server-side motivations here. Are you saying you want the client to provide information as to which streams need more buffers? Just to be clear, in this proposal, are we trying to address a deficiency compared to HTTP over TCP connections, or are we trying to provide better facilities to do better buffer management than is possible with HTTP over TCP?

FWIW, I'm lean towards Mike's POV more, although I do concede a need for flow control (and per-session windows in addition to per-stream windows). But I think that these windows should be sized so they only come into play in the less common cases (most streams are short-lived) and would like to see Chromium and Firefox and other SPDY clients agree on minimum sizes to require, so we prevent stupid servers from making things unnecessarily slow. And I think per-session+per-stream windows give enough knobs for the server to manage things appropriately, and don't really see a need for further knobs
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/30/12 11:49 AM


"Packet loss" also means "dropped because of full buffers".
We also have a transport that does flow control - yet we are duplicating that ( in part - without the part that deals with congestion). 
Not sure I understand - you can't increase any window if the per-connection buffers are full. 

The sender has sent initial window of all the streams, up to filling the per connection window. There is no more space in the proxy ( maybe for control frames which are not subject to frame control). 
 


This scheme doesn't require much additional complexity, and it meets all of the ratings targets proposed by Greg earlier.
This scheme rapidly converges on the appropriate window size without too much overshoot.

I really don't see how this can work. Maybe if 'per connection' buffers equals per-stream window * max number of streams - in which case what's the point of per connection flow control ? 

Wel
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/30/12 12:13 PM


Agreed. We're duplicating it because we'd be required to do infinite buffering at proxies without it. That problem is not being solved by the transport, unfortunately :/
If the proxy has no more space, then noone should be sending more bytes and things are working properly.
If the proxy has space in its buffers, it indicates such by increasing the per-connection window size.
If the proxy is blockage for a particular stream, it doesn't update the window size for that stream, but otherwise the per-stream window size should be the per-connection window size.

Does that clarify it?

-=R
 
 


This scheme doesn't require much additional complexity, and it meets all of the ratings targets proposed by Greg earlier.
This scheme rapidly converges on the appropriate window size without too much overshoot.

I really don't see how this can work. Maybe if
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/30/12 12:21 PM


Any of the above. The larger the blockage, the less interesting the signal, however. Blockages which are less than BDP send some very useful and interesting data...
The 'how long' is useful in estimating bandwidth demand, or for implementations of fairness, depending on the receiver implementation.

 
 

The receiver, upon receipt of such a frame, could increase the various window sizes as indicated by the frames which tell the receiver the number (and possible duration) of the blocked bytes (hopefully up to a maximum as estimated by the BDP).

I think I need more clarification on the server-side motivations here. Are you saying you want the client to provide information as to which streams need more buffers? Just to be clear, in this proposal, are we trying to address a deficiency compared to HTTP over TCP connections, or are we trying to provide better facilities to do better buffer management than is possible with HTTP over TCP?

The client knows how much it needs to send for each stream. The server, of course, doesn't know this. The 'I'm blocked" mechanism will be useful for servers which don't have the ability to hack the kernel to discover TCP parameters by allowing a reasonably accurate assessment of how much smaller the flow control window is as compared to BDP.
 

FWIW, I'm lean towards Mike's POV more, although I do concede a need for flow control (and per-session windows in addition to per-stream windows). But I think that these windows should be sized so they only come into play in the less common cases (most streams are short-lived) and would like to see Chromium and Firefox and other SPDY clients agree on minimum sizes to require, so we prevent stupid servers from making things unnecessarily slow. And I think per-session+per-stream windows give enough knobs for the server to manage things appropriately, and don't really see a need for further knobs.

If we set the per-connection window size to roughly the BDP (or slightly more), and we set the per-stream window size to roughly the per-connection window
...
Re: [spdy-dev] Thinking about flow control Simone Bordet 5/30/12 12:35 PM
Hi,

On Wed, May 30, 2012 at 7:43 PM, Roberto Peon <fe...@google.com> wrote:
> In natural language:
> if a sender is ever blocked, then it should send a frame to the receiver
> indicating the stream ID which is blocked, with then amount of bytes it
> would wish to send, but couldn't because of flow-control.

I don't follow this point.
If the sender is blocked, how can it send a frame to the receiver ?

And even supposing that the receiver somehow receives it, what use can
it make of it ?
If a receiver is bound to a slow application, it knows that (it reads
more for that stream than the application consumes), and I can't
imagine what can it do with the information that it's flow controlled
- it probably already knows that by its own.

Thanks,

Simon
--
http://cometd.org
http://intalio.com
http://bordet.blogspot.com
----
Finally, no matter how good the architecture and design are,
to deliver bug-free software with optimal performance and reliability,
the i...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/30/12 12:48 PM


On Wed, May 30, 2012 at 12:35 PM, Simone Bordet <sbo...@intalio.com> wrote:
Hi,

On Wed, May 30, 2012 at 7:43 PM, Roberto Peon <fe...@google.com> wrote:
> In natural language:
> if a sender is ever blocked, then it should send a frame to the receiver
> indicating the stream ID which is blocked, with then amount of bytes it
> would wish to send, but couldn't because of flow-control.

I don't follow this point.
If the sender is blocked, how can it send a frame to the receiver ?

"a stream is blocked"  means that the sender for that stream:
  * can write to the socket (i.e. the socket is writable and there is space in the TCP egress buffers)
  * has no higher priority stream that is currently sending (and thus blocking this stream because of prioritization)
  * there are bytes to be sent on this stream.


And even supposing that the receiver somehow receives it, what use can
it make of it ?
If a receiver is bound to a slow application, it knows that (it reads
more for that stream than the application consumes), and I can't
imagine what can it do with the information that it's flow controlled
- it probably already knows that by its own.

The receiver can:
1) Allocate more buffer space for a particular stream vs another stream
2) Increase the per-connection flow control window, and, importantly:
3) Estimate the amount of additional bytes-on-the-wire necessary to meet the BDP.

The receiver can't know that something is flow controlled unless the sender informs it. 

The intent is:
To be able to do a decent estimate of BDP when necessary.
...
Re: [flip-dev] Re: [spdy-dev] Thinking about flow control Jim Roskind 5/30/12 12:57 PM
On Wed, May 30, 2012 at 10:43 AM, Roberto Peon <fe...@google.com> wrote:

...
This scheme rapidly converges on the appropriate window size without too much overshoot.

Comments? Are there holes to be poked-in here?
-=R


I like Roberto's proposal.

I see it as being helpful in a certain class of cases, involving upload from client to server (or client to proxy).

In that case, the client may be immediately aware of the size of a stream's complete byte count (a.k.a., file size).  It seems that it can only be helpful to warn a server about an impending upload.  Advance, and precise info, beats the heck out of delayed info ("now the buffer is full") and inprecise info ("we have no idea how bad this is going to get").

I like the
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/30/12 1:10 PM
My point is that the proposals I've seen are not _duplicating_ - just pick a subset. 

And I don't agree it 'requires infinite buffering' - it requires the same amount of buffering that HTTP would require, all other knobs being equal. 
They are not working properly - you may have higher priority streams that can't go trough, and 'bad' streams preventing good streams. Very similar with the buffer bloat, and for similar reasons. 

In contrast plain HTTP would work just fine in this situation - the bad streams will hit TCP flow control, the new streams will keep working. 

 
If the proxy has space in its buffers, it indicates such by increasing the per-connection window size.
If the proxy is blockage for a particular stream, it doesn't update the window size for that stream, but otherwise the per-stream window size should be the per-connection window size.

Yes, but that stream still uses bytes ( equals with last window ). Enough of those streams and the connection is useless. 

It's replicating the buffer bloat problem almost identically, and all this just to make SPDY memory use lower than the equivalent HTTP memory use on the proxy. 


Costin
 

Does that clarify it?

-=R
 
 


This scheme doesn't requi
...
Re: [spdy-dev] Thinking about flow control Mike Belshe 5/30/12 3:04 PM
This thread has gotten confusing, maybe someone can make a concrete proposal as to what we're talking about at this point?

My current summary:

I liked Greg's summary of the goals of flow control.

I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

Justification:
a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.
b) The server doesn't get huge uploads very often; so there isn't much to throttle here anyway.
c) DoS is an exception that can be detected and dealt with, and flow control doesn't solve it anyway.
d) If your backend server is down causing backlogs in your proxy, you can write code to deal with that (e.g. failover) or nuke the stream.  Why expose it out to the whole protocol?

Mike
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/30/12 3:24 PM


On Wed, May 30, 2012 at 3:04 PM, Mike Belshe <mbe...@chromium.org> wrote:
This thread has gotten confusing, maybe someone can make a concrete proposal as to what we're talking about at this point?

My current summary:

I liked Greg's summary of the goals of flow control.

I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

+1 ( on removing all flow control and killing streams that miss-behave ).


Costin
...
Re: [spdy-dev] Thinking about flow control Alek Storm 5/30/12 4:16 PM
On Wed, May 30, 2012 at 5:04 PM, Mike Belshe <mbe...@chromium.org> wrote:
I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

So a stream can be killed halfway through transmitting a large amount of data? How will the sender know when it is safe to retransmit without the stream getting killed again? And they'll have to retransmit the entire block from the beginning - everything that was sent in the killed stream is lost. That sounds remarkably inefficient.

Justification:
a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.

Absolutely not; see Patrick's examples (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/-Hnjp94xjG4J) near the beginning of this thread. A lack of per-stream flow control would become even more of a problem as web applications become more media-rich. I believe clients would begin to compensate by opening multiple TCP connections - not for a greater share of the server's bandwidth, but for stream-specific flow control.

d) If your backend server is down causing backlogs in your proxy, you can write code to deal with that (e.g. failover) or nuke the stream.  Why expose it out to the whole protocol?

That doesn't help forward proxies, which don't have control over upstream servers (see Ryan's excellent explanation at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/FGYat2VU22IJ). And I'm sure clients would not be pleased with repeatedly having their upload streams killed and restarting the upload from scratch because the proxy has no way to notify them of the size of its input buffers. With multiple downstream clients doing this at once, the proxy could become overwhelmed and unintentionally DoS'd.

Alek
...
Re: [spdy-dev] Thinking about flow control William Chan 5/30/12 4:26 PM
On Wed, May 30, 2012 at 3:04 PM, Mike Belshe <mbe...@chromium.org> wrote:
This thread has gotten confusing, maybe someone can make a concrete proposal as to what we're talking about at this point?

I propose per-stream flow control windows + per-session flow control windows where the windows are very healthily sized so we don't hit them for 90% of streams (most of them are short-lived after all).


My current summary:

I liked Greg's summary of the goals of flow control.

I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

Justification:
a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.

Agreed.
 
b) The server doesn't get huge uploads very often; so there isn't much to throttle here anyway.

Most servers will not, very true, but some will get them very often. Very example, a system that heavily uses the Google Drive web app (let's say ChromeOS for example) will send a lot of large uploads to the Google Drive server.

Also, don't get too focused on the upload direction. The download direction also matters. For example, a forward proxy speaking SPDY to a SPDY origin server. The proxy wants to keep reading from the SPDY origin server, but then it might get infinite buffering or HoL blocking due to different client download bandwidths. Imagine if one of the clients is mobile! Is the solution really to always nuke the proxy<=>origin server stream that is servicing the mobile client?
...
Re: [spdy-dev] Thinking about flow control Jim Roskind 5/30/12 4:54 PM
On Wed, May 30, 2012 at 3:24 PM, Costin Manolache <cos...@gmail.com> wrote:


On Wed, May 30, 2012 at 3:04 PM, Mike Belshe <mbe...@chromium.org> wrote:
This thread has gotten confusing, maybe someone can make a concrete proposal as to what we're talking about at this point?

My current summary:

I liked Greg's summary of the goals of flow control.

I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

+1 ( on removing all flow control and killing streams that miss-behave ).

The big problem IMO is that large uploads are indeed common. Given how TCP will suck up a giant buffer (by deliberately bloating buffers along the route), SPDY connections can and do become so bloated that latency is soon untenable.  If you kill such a misbehaving(??) "hog" stream, you will have castrated the protocol in several ways.

Do we really want to tell an application to open a separate (non-SPDY?) connection for a big upload?

IMO, we should look at this problem, understand it, and try to help with it (or prove it is impossible to help).

Jim
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/30/12 5:07 PM
It is annoying, but we're doing multiplexing through proxies, and if we're serious about providing a reliable service through them (and I AM), then we need flow control.
I believe that proxies, both forward (mobile) and reverse (loadbalancers) will become more common as time progresses. Ensuring that they will work reliably seems important for the future of the protocol. Dropping the connection randomly, especially when we have little idea of the nature of the transaction, seems a poor choice. As Alek implies, it is an uncomfortable situation when you have to retry, and is definitely not work conserving.

As for what am proposing:

Keep the per-stream window, because we need it to avoid HOL blocking.
Add a per-tcp-connection window.
A sender can send a maximum of:
    min(stream_flow_control_window, per_connection_flow_control_window) bytes at any point in time.
Whenever the sender finds that it is restricted from sending by flow control (and only by flow control), then it should tell the other side so that the window can (possibly) grow.

-=R
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/30/12 6:53 PM
Goal #1 here has to be "do no harm".. by which I mean a system that
doesn't accidentally constrain the sending rate in the absence of a real
resource problem. I think the current per stream window fails on that
count because it doesn't adjust according to the BDP conditions -
instead relying on constants. We've got at least a couple data points
that show exactly that happening on v3. If we use TCP as a guide, almost
all of TCP's magic constants are pain points (syn retry timeout, IW, min
RTO) even though they are widely configurable to whatever constant the
admin wants - while the adpative parts of tcp (fast retransmit, even RTO
itself) are more robust (if imperfect).

But I do see clear use cases for flow control. Proxies receiving large
uploads are clearly one. My approach to server push is another one -
they are conceptually very similar in the sense that the other end is
going to send unsolicited data at you and you might want to put a lid on
how much that will be until you know if you have a place to put it, if
it satisfies auth requirements etc.. 100-continue in HTTP/1.1 is
evidence we've been here before even without multiplexed hol issues, right?


On 5/30/2012 8:07 PM, Roberto Peon wrote:
>
> As for what am proposing:
>
> [a] Keep the per-stream window, because we need it to avoid HOL blocking.
> [b] Add a per-tcp-connection window.
> [c] A sender can send a maximum of:
>     min(stream_flow_control_window,
> per_connection_flow_control_window) bytes at any point in time.
> [d] Whenever the sender finds that it is restricted from sending by
> flow control (and only by flow control), then it should tell the other
> side so that the window can (possibly) grow.
>

[I labeled those a, b, c, d for easy reference - otherwise that's
roberto's language]

Overall I think this works with a few tweaks.

[a] I  think that a negative delta message is something that we
absolutely must add. A negative update essentially allows deployment of
giant (~infinite) windows (hopefully defaulted that way) that can be
reduced to 0 quickly - which effectively gives the same functionality as
txon/txoff. The value of txon/txoff is that it is BDP independent which
is part of where the current scheme falls down.

[b] I'm ok with this, but let's size the default very aggressively for
the Intern...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/30/12 9:29 PM


[b] I'm ok with this, but let's size the default very aggressively for the Internet of tomorrow and let special cases like proxies deal with the fallout of the race condition after handshake where clients can generate syn before reading settings.  Anything that doesn't deal with 10s of megabits/sec at 100msec of latency is going to, imo, breakdown notably.
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/30/12 9:53 PM




[c] yes

[d] sure.. I think the jury is out on that one, but it is probably a good piece of feedback to be able to experiment with.

Note that [d] allows for adjustment of [b] in the case that we get it wrong, even on implementations that don't have access to TCP-level data on windowing, BDP, etc.
-=R
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/30/12 10:08 PM
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 5/31/12 1:56 AM
On 31 May 2012 02:07, Roberto Peon <fe...@google.com> wrote:
> Keep the per-stream window, because we need it to avoid HOL blocking.

+1

> Add a per-tcp-connection window.

I'm unclear on what a per-tcp-connection window gives us.   It might
help avoid congesting the connection, but I don't think that is an
issue. So long as we stay within the per-stream windows, we know the
receiver is prepared to buffer the data sent and thus we will not HOL
block.

If the per-tcp-connection is an attempt to set a limit on the memory
used by one connection - then that is just an incentive to create more
connections.  The memory commitment should be the same for 1
connection with 20 streams or 2 connections with 10.

In the interests of simplicity I'd like to see the concept of growing
stream windows worked out without a connection window.  We can then
evaluate and see if a connection window is really really needed.


> A sender can send a maximum of:
>     min(stream_flow_control_window, per_connection_flow_control_window)
> bytes at any point in time.
> Whenever the sender finds that it is restricted from sending by flow control
> (and only by flow control), then it should tell the other side so that the
> window can (possibly) grow.

+1 on growing per-stream windows.  But I don't think we want to get
too much into the specific algorithms used as I'm sure they will
change over time. However, I do think we should say that Initial size
for new streams should be  based on the grown size of previous and/or
existing streams on the conne...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/31/12 6:37 AM
On Thu, 2012-05-31 at 10:56 +0200, Greg Wilkins wrote:
> On 31 May 2012 02:07, Roberto Peon <fe...@google.com> wrote:
> > Keep the per-stream window, because we need it to avoid HOL blocking.
>
> +1
>
> > Add a per-tcp-connection window.
>
> I'm unclear on what a per-tcp-connection window gives us.  

a per-connection spdy window as a backstop allows the per stream windows
to be sized more aggressively without creating blocking problems for
control or downstream traffic.

Last I checked google.com was using 12KB v3 per stream windows. That's
much smaller than most BDPs so tasks such as uploading gmail attachments
are artificially delayed as extra rtt delays to manage the window
updates are incurred. It's easy to see in practice and very much the
antithesis of spdy principles. As I understand it, the lack of a per
session window is at the root of why this is undersized.

128KB would be a better value (that's just 10mbit/sec at 100ms rtt -
still too small for a one size fits all value) but its understandable
that a commitment (but unlikely utilization) of 12MB per connection
spread over 100 potential streams is undesirable. And of course we want
to encourage higher stream counts than 100.

If, in the absence of a per-tcp spdy window, the proxy did use
128KB/stream windows and also used tcp rwin to limit its own actual
buffering that would create a tcp level head of line blocking situation.
Control packets (ping, goaway) would not flow, nor would GET requests
that don't impact these buffers at all. The tcp level window is inferior
to a per-tcp spdy window in this way.

as an example, a proxy with a per-tcp spdy window of 512KB and per
stream windows of 256KB lets an upload proceed (up to) 20x faster than
the 12KB version that has been used, while cutting the proxy's buffer
commitment in half assuming max 100 streams. It also encourages a
greater number than 100 streams, as the buffering commitment remains the
same across the session and the fact that the session window is shared
among more streams will not really impact transfer speeds as it should
be bottlenecked by the actual bandwidth available which those streams
needs to obviously be sharing in a physical sense anyhow.

On a meta-level what I like about the scope of this change is that it is
driven by real deployment experience. This stuff is wa...
Re: [spdy-dev] Thinking about flow control Mike Belshe 5/31/12 8:43 AM


On Wed, May 30, 2012 at 4:16 PM, Alek Storm <alek....@gmail.com> wrote:
On Wed, May 30, 2012 at 5:04 PM, Mike Belshe <mbe...@chromium.org> wrote:
I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

So a stream can be killed halfway through transmitting a large amount of data? How will the sender know when it is safe to retransmit without the stream getting killed again? And they'll have to retransmit the entire block from the beginning - everything that was sent in the killed stream is lost. That sounds remarkably inefficient.

This isn't a normal case, of course, and I don't know why it would happen.  The server is out of memory or resources, so it starts killing.  (just like it does today!)


Justification:
a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.

Absolutely not; see Patrick's examples (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/-Hnjp94xjG4J) near the beginning of this thread. A lack of per-stream flow control would become even more of a problem as web applications become more media-rich. I believe clients would begin to compensate by opening multiple TCP connections - not for a greater share of the server's bandwidth, but for stream-specific flow control.

Bah.  Show me the data. The client can naturally throttle by not making requests.  If we wanted that world, we'd stick with HTTP and multiple connections.  The client wants it as fast as it can get it.  Flow control is not the way to handle prioritization, and once you've hit flow control, it takes a round trip to unwind it (e.g. slow).

I have yet to see any use of client-side flow control which is faster than without flow control.


 

d) If your backend server is down causing backlogs in your proxy, you can write code to deal with that (e.g. failover) or nuke the stream.  Why expose it out to the whole protocol?

That doesn't help forward proxies, which don't have control over upstream servers (see Ryan's excellent explanation at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/FGYat2VU22IJ). And I'm sure clients would not be pleased with repeatedly having their upload streams killed and restarting the upload from scratch because the proxy has no way to notify them of the size of its input buffers. With multiple downstream clients doing this at once, the proxy could become overwhelmed and unintentionally DoS'd.

No.  If you have a wimpy proxy, limit concurrent requests to 6 just like browsers do today.  This means that you've got one TCP socket with 6 requests instead of 6 TCP sockets like you had with HTTP.  So it's strictly better than what we had before - if your proxy can't handle that then it can't handle HTTP either :-)  Now, you're right, if you want to support 100 concurrent streams, you need to make sure your proxy can handle that (I argue this is trivial for most existing deployments)...  Let's make no mistake - SPDY will require more resources if you want to send more streams through it faster.  That's not an accident.  But if your server can't handle it, there are already throttles.

Anyway, I'm not completely against flow control.  I'm against complex, unproven flow control schemes.  The current proposal argues for a simple mechanism; intentionally reducing per-stream max throughput in exchange for reduced buffering. 

Mike
...
Re: [spdy-dev] Thinking about flow control Eric 5/31/12 9:20 AM
I think maybe Patrick's suggestion of txon/txoff to pause a frame is good enough for HOL issues this with priority should allow full utilization of the pipe without much complexity.

This would require the spdy receiver to be able to buffer x + tcp buffer size where x is at what point it sends the txon/txoff (to work perfectly would need to stop reading the receive buffer until you reasonable assume the txoff is processed for HOL issues).  If you receive more than x + tcp buffer you can always kill that stream and start discarding the data (this would be only in case of bad behaving client that ignores txoff).

Comparing this to Greg's primary objectives:

1.1 Uses full available bandwidth

- yes

1.2 No infinite postponement of a stream

- not infinite, should postpone for an assumed ttl (maybe 500 ms in a lazy implementation) to ensure txoff is registered.

1.3 Little incentive to use multiple connections

- I think it coveres this.

1.4 No infinite buffering

- Requires buffering of tcp socket buffer + some internal amount to realize to HOL block.   This is equivalent to what would happen if each request was multiplexed into different tcp connections.


2.1 Complexity

- Close to 0 complexity, on/off swi
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 5/31/12 9:33 AM


On May 31, 2012 8:44 AM, "Mike Belshe" <mbelshe...@chromium.org> wrote:
>
>
>
> On Wed, May 30, 2012 at 4:16 PM, Alek Storm <alek.storm...@gmail.com> wrote:


>>
>> On Wed, May 30, 2012 at 5:04 PM, Mike Belshe <mbelshe...@chromium.org> wrote:
>>>
>>> I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.
>>>
>>> I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.
>>
>>
>> So a stream can be killed halfway through transmitting a large amount of data? How will the sender know when it is safe to retransmit without the stream getting killed again? And they'll have to retransmit the entire block from the beginning - everything that was sent in the killed stream is lost. That sounds remarkably inefficient.
>
>
> This isn't a normal case, of course, and I don't know why it would happen.  The server is out of memory or resources, so it starts killing.  (just like it does today!)
>
>>
>>> Justification:
>>> a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.
>>
>>
>> Absolutely not; see Patrick's examples (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/-Hnjp94xjG4J) near the beginning of this thread. A lack of per-stream flow control would become even more of a problem as web applications become more media-rich. I believe clients would begin to compensate by opening multiple TCP connections - not for a greater share of the server's bandwidth, but for stream-specific flow control.
>
>
> Bah.  Show me the data. The client can naturally throttle by not making requests.  If we wanted that world, we'd stick with HTTP and multiple connections.  The client wants it as fast as it can get it.  Flow control is not the way to handle prioritization, and once you've hit flow control, it takes a round trip to unwind it (e.g. slow).
>
> I have yet to see any use of client-side flow control which is faster than without flow control.

Proxies are both clients and servers.

>
>
>  
>>
>>
>>> d) If your backend server is down causing backlogs in your proxy, you can write code to deal with that (e.g. failover) or nuke the stream.  Why expose it out to the whole protocol?
>>
>>
>> That doesn't help forward proxies, which don't have control over upstream servers (see Ryan's excellent explanation at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/FGYat2VU22IJ). And I'm sure clients would not be pleased with repeatedly having their upload streams killed and restarting the upload from scratch because the proxy has no way to notify them of the size of its input buffers. With multiple downstream clients doing this at once, the proxy could become overwhelmed and unintentionally DoS'd.
>
>
> No.  If you have a wimpy proxy, limit concurrent requests to 6 just like browsers do today.  This means that you've got one TCP socket with 6 requests instead of 6 TCP sockets like you had with HTTP.  So it's strictly better than what we had before - if your proxy can't handle that then it can't handle HTTP either :-)  Now, you're right, if you want to support 100 concurrent streams, you need to make sure your proxy can handle that (I argue this is trivial for most existing deployments)...  Let's make no mistake - SPDY will require more resources if you want to send more streams through it faster.

This isn't true. A common pattern is long polling cometd connections. Assuming WS support in SPDY arrives, this will become even more common.

Even ignoring cometd, different streams have different target hosts and each has a different connection with different loss and flow characteristics. This changes the cost.

> That's not an accident.  But i

...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/31/12 9:34 AM


On Thu, May 31, 2012 at 8:43 AM, Mike Belshe <mbe...@chromium.org> wrote:


On Wed, May 30, 2012 at 4:16 PM, Alek Storm <alek....@gmail.com> wrote:
On Wed, May 30, 2012 at 5:04 PM, Mike Belshe <mbe...@chromium.org> wrote:
I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

So a stream can be killed halfway through transmitting a large amount of data? How will the sender know when it is safe to retransmit without the stream getting killed again? And they'll have to retransmit the entire block from the beginning - everything that was sent in the killed stream is lost. That sounds remarkably inefficient.

This isn't a normal case, of course, and I don't know why it would happen.  The server is out of memory or resources, so it starts killing.  (just like it does today!)


Justification:
a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.

Absolutely not; see Patrick's examples (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/-Hnjp94xjG4J) near the beginning of this thread. A lack of per-stream flow control would become even more of a problem as web applications become more media-rich. I believe clients would begin to compensate by opening multiple TCP connections - not for a greater share of the server's bandwidth, but for stream-specific flow control.

Bah.  Show me the data. The client can naturally throttle by not making requests.  If we wanted that world, we'd stick with HTTP and multiple connections.  The client wants it as fast as it can get it.  Flow control is not the way to handle prioritization, and once you've hit flow control, it takes a round trip to unwind it (e.g. slow).

I have yet to see any use of client-side flow control which is faster than without flow control.


 

d) If your backend server is down causing backlogs in your proxy, you can write code to deal with that (e.g. failover) or nuke the stream.  Why expose it out to the whole protocol?

That doesn't help forward proxies, which don't have control over upstream servers (see Ryan's excellent explanation at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/FGYat2VU22IJ). And I'm sure clients would not be pleased with repeatedly having their upload streams killed and restarting the upload from scratch because the proxy has no way to notify them of the size of its input buffers. With multiple downstream clients doing this at once, the proxy could become overwhelmed and unintentionally DoS'd.

No.  If you have a wimpy proxy, limit concurrent requests to 6 just like browsers do today.  This means that you've got one TCP socket with 6 requests instead of 6 TCP sockets like you had with HTTP.  So it's strictly better than what we had before - if your proxy can't handle that then it can't handle HTTP either :-)  Now, you're right, if you want to support 100 concurrent streams, you need to make sure your proxy can handle that (I argue this is trivial for most existing deployments)...  Let's make no mistake - SPDY will require more resources if you want to send more streams through it faster.  That's not an accident.  But if your server can't handle it, there are already throttles.

Anyway, I'm not completely against flow control.  I'm against complex, unproven flow control schemes.  The current proposal argues for a simple mechanism; intentionally reducing per-stream max throughput in exchange for reduced buffering. 

+1 

My comments are shaped by mobile networks - slow, unreliable, TCP connections 'stuck' with no RST and lots of other bad things. I agree proxies are very important, and I think good flow control is worth a bit of complexity. Bufferbloat is proof.  

I am ok with the idea of per-connection flow control - as a way to avoid the TCP flow control, so control frames or higher-priority streams can go trough. 

What I don't like about the proposal is congestion handling, and I strongly disagree that we can just ignore it because it only happens in 0.01% of cases. Doing the same thing HTTP does - terminate the stream - seems a reasonable and simple solution, and it's not worse than what clients need to handle now. A large upload will fail on HTTP too, and will need to be retried from start ( unless Range: is used ). I think we can do better than that, but with complexity and/or memory costs.
But defining one extra code on RST seems simple enough, and the client already handles that.

I also don't like the small per-stream window and the interaction between the per stream and per session windows. 
To take some numbers from a previous example, if you have 512K per connection and 256K per stream - and assume the 512K is 'hard' ( i.e. not dealing with (d) - client may ask for more, but server can't provide ). 
How would this work with 3 uploads ? 


Costin
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/31/12 9:41 AM


> That's not an accident.  But if your server can't handle it, there are already throttles.


>
> Anyway, I'm not completely against flow control.  I'm against complex, unproven flow control schemes.  The current proposal argues for a simple mechanism; intentionally reducing per-stream max throughput in exchange for reduced buffering. 

My opinion:
The current scheme was a mistake. We messed up. We should make a small rev to the protocol, call that spdy/4, and retire spdy/3 before it gets any more usage.

+1  :-)

 
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/31/12 10:31 AM
On Thu, 2012-05-31 at 09:34 -0700, Costin Manolache wrote:

>
> To take some numbers from a previous example, if you have 512K per
> connection and 256K per stream - and assume the 512K is 'hard' ( i.e.
> not dealing with (d) - client may ask for more, but server can't
> provide ).
> How would this work with 3 uploads ?
>

The assumption is that 256K covers line rate (e.g. 20mbit at 100ms rtt)
because you want a single flow to be able to go at line rate.

having 3 streams instead of 1 doesn't change the line rate bottleneck -
each stream's share of line rate bandwidth is reduced (because they are
sharing the same pipe) and so is their bdp and in turn their windowing
requirement for moving at full speed. So their aggregate window of 512kb
will keep the total transfer moving at line rate even though any
individual stream might certainly have access to less than 256kb (e.g.
170kb if shared equally but there is no problem with sharing it
unequally). One stream could stall completely (by filling up 256KB of
window) and the others would still be able to proceed normally having
256KB to share between them. The difference between the per-connection
window size and the per-stream window size basically determines how many
streams can backup (and how far) without restricting sending rates. At
th...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/31/12 11:36 AM


On Thu, May 31, 2012 at 10:31 AM, Patrick McManus <mcm...@ducksong.com> wrote:
On Thu, 2012-05-31 at 09:34 -0700, Costin Manolache wrote:

>
> To take some numbers from a previous example, if you have 512K per
> connection and 256K per stream - and assume the 512K is 'hard' ( i.e.
> not dealing with (d) - client may ask for more, but server can't
> provide ).
> How would this work with 3 uploads ?
>

The assumption is that 256K covers line rate (e.g. 20mbit at 100ms rtt)
because you want a single flow to be able to go at line rate.

having 3 streams instead of 1 doesn't change the line rate bottleneck -
each stream's share of line rate bandwidth is reduced (because they are
sharing the same pipe) and so is their bdp and in turn their windowing
requirement for moving at full speed. So their aggregate window of 512kb
will keep the total transfer moving at line rate even though any
individual stream might certainly have access to less than 256kb (e.g.
170kb if shared equally but there is no problem with sharing it
unequally). One stream could stall completely (by filling up 256KB of
window) and the others would still be able to proceed normally having
256KB to share between them.

If both in and out flow at line rate all is good, the issue is how it works when flow control kicks in. 

For example, if the target server for the uploads ( gmail for example ) is congested, all 3 streams 'out' rate will be very small. Can you provide some example of how it'll work - what will the server send, what will the client do.

Also, let's assume the client also want to make a small search (POST) - while the 3 streams are congested. The 512K session buffer is all full, the 3 streams still have stream window ( for example each is at 189K buffered, bellow their 256K stream window). To simplify let's assume the proxy doesn't have extra RAM ( which would be the case if a downstream server has problems ).

I don't think the example is extreme - slow servers and congestion happens, maybe in 1% of the time - but that's when flow control is needed in the first place.

Costin
 
The difference between the per-connection
window size and the per-stream window size basically determines how many
streams can b
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/31/12 1:19 PM
On Thu, 2012-05-31 at 11:36 -0700, Costin Manolache wrote:

>
>
> Also, let's assume the client also want to make a small search (POST)
> - while the 3 streams are congested. The 512K session buffer is all
> full, the 3 streams still have stream window ( for example each is at
> 189K buffered, bellow their 256K stream window).

If the three streams are in aggregate consuming the whole set of 512KB
of session buffers then a new stream cannot send a new POST until some
room has been cleared. But it doesn't need to wait for the streams to be
wholly drained - any small window update could be used by the client as
the basis for sending the new (higher priority) post. Sending more data
would require buffers the receiver is unwilling to provide - thus the
flow control. Nothing surprising there.

Once you're stuck there are lots of slow ways of injecting new buffers
into the system to let new flows work and old flows work at slower
rates(*).. they all suffer from rtt based ramp ups, that's why its
important that the default scenario allow line rate to flow until
buffers-bigger-than-bdp are actually exhausted. Even if the receiver
chooses not to cleverly inject buffers in the system they will free
slowly over time and the freed buffers can be shared in a prioritized
fashion among the now-4 streams. no big deal - the system sent faster
than the receiver could deal with and it had to back off. That's a far
better problem to have than not sending fast enough because you're
afraid of overwhelming the receiver - slow start has taught me that
wastes oodles of bandwidth in practice.

I agree with Mike that if we want to move a lot of data quickly you need
to be prepared for it to back up on you and provide large buffers in
case that happens. the biggest danger here is undersizing things - as v3
has shown. the session buffer tweak makes that less likely to happen,
while still providing a bound, so that's good.

-Pat

(*) this is where the negative deltas come into play.. you can slow down
the streams that hav...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/31/12 3:06 PM


On Thu, May 31, 2012 at 1:19 PM, Patrick McManus <mcm...@ducksong.com> wrote:
On Thu, 2012-05-31 at 11:36 -0700, Costin Manolache wrote:

>
>
> Also, let's assume the client also want to make a small search (POST)
> - while the 3 streams are congested. The 512K session buffer is all
> full, the 3 streams still have stream window ( for example each is at
> 189K buffered, bellow their 256K stream window).

If the three streams are in aggregate consuming the whole set of 512KB
of session buffers then a new stream cannot send a new POST until some
room has been cleared. But it doesn't need to wait for the streams to be
wholly drained - any small window update could be used by the client as
the basis for sending the new (higher priority) post. Sending more data
would require buffers the receiver is unwilling to provide - thus the
flow control. Nothing surprising there.

In HTTP - the POST will just get trough full speed without problems. If the client makes a new SPDY connection - the POST and any request going to other backends than the congested ones will work. 
Even in the v3 flow control ( no per-connection ) - the POST will work. 

And it's still not clear to me how this case will play in terms of protocol - will the proxy start sending negative windows for the 3 streams ? When ? Should the client give priority to new streams ( the POST ) even if the per-connection window is full and the existing streams still have per-stream window available ? 


 

Once you're stuck there are lots of slow ways of injecting new buffers
into the system to let new flows work and old flows work at slower
rates(*).. they all suffer from rtt based ramp ups, that's why its
important that the default scenario allow line rate to flow until
buffers-bigger-than-bdp are actually exhausted. Even if the receiver
chooses not to cleverly inject buffers in the system they will free
slowly over time and the freed buffers can be shared in a prioritized
fashion among the now-4 streams. no big deal - the system sent faster
than the receiver could deal with and it had to back off. That's a far
better problem to have than not sending fast enough because you're
afraid of overwhelming the receiver - slow start has taught me that
wastes oodles of bandwidth in practice.

I agree with Mike that if we want to move a lot of data quickly you need
to be prepared for it to back up on you and provide large buffers in
case that happens. the biggest danger here is undersizing things - as v3
has shown. the session buffer tweak makes that less likely to happen,
while still providing a bound, so that's good.

Than why not remove the undersized thing ( the v3 per-stream flow control ), and do just connection window. 

The per-connection window update can have some info about each stream status, so that the sender can make a better decision and avoid head of line. I suppose that's the 'negative stream window deltas' - but so far I don't understand how they all work together. 


Costin
...
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 5/31/12 3:10 PM


Without per-stream flow control, we don't solve the head of line blocking problem, right?  (As explained here https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/FGYat2VU22IJ)

Cheers,

Ryan
 
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 5/31/12 3:32 PM


Isn't the 'head of line blocking' back if we add session flow control? I think that's what the example is showing - we just replaced TCP flow control to the session flow control, with same effect. The main difference is that we can still send control frames. 

Negative per-stream windows may help a bit - but the non-congested stream will still be very slow ( compared with the equivalent speed on HTTP or with multiple SPDY connections ). All new streams will use the small space created when slow streams go downstream - but the congested streams will fill again the buffers, the negative window just slows them down, but they can still send when there is space in the connection buffers. ( at least with what I understand of the proposed flow )


Costin
 

Cheers,
...
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 5/31/12 3:36 PM


It depends on the window sizes.  If the per-stream window size is equal to the session window size, then yes, we still have the same problem.  However, if the per-stream window size is somewhat smaller than the session window size, then I think that problem is mitigated.

Cheers,

Ryan
 

Negative per-stream windows may help a bit - but the non-congested stream will still be very slow ( compared with the equivalent speed on HTTP or with multiple SPDY connections ). All new streams will use the small space created when slow streams go downstream - but the congested streams will fill again the buffers, the negative window just slows them down, but they can still send when there is space in the connection buffers. ( at least with what I understand of the proposed flow )


Costin
 
...
Re: [spdy-dev] Thinking about flow control William Chan 5/31/12 4:13 PM
No they won't. If they're slow, don't send WINDOW_UPDATEs for them, or send smaller ones. There's no need to insist that implementations have to be silly and blindly send WINDOW_UPDATEs upon receipt of data, nor that the WINDOW_UPDATE deltas have to reopen the stream window to its default size. Free up more space in the session window but keep the congested stream window shut/small until the next hop consumes more bytes and frees up buffers.
 


Costin
 
...
Re: [spdy-dev] Thinking about flow control Alek Storm 5/31/12 5:08 PM
On Thu, May 31, 2012 at 11:20 AM, Eric C <eric...@gmail.com> wrote:
I think maybe Patrick's suggestion of txon/txoff to pause a frame is good enough for HOL issues this with priority should allow full utilization of the pipe without much complexity.

This would require the spdy receiver to be able to buffer x + tcp buffer size where x is at what point it sends the txon/txoff (to work perfectly would need to stop reading the receive buffer until you reasonable assume the txoff is processed for HOL issues).  If you receive more than x + tcp buffer you can always kill that stream and start discarding the data (this would be only in case of bad behaving client that ignores txoff).

Comparing this to Greg's primary objectives:

1.1 Uses full available bandwidth

- yes

No. From the time the txoff is sent to the time it's received, that stream could have sent up to one BDP's worth of data that now has to be resent at the next txon. That's wasted bandwidth that could have been used by other streams.

Furthermore, in the case of an endpoint that's resource-constrained but on a fat pipe (like a server under heavy load), the BDP could exceed the size of its output buffers - it'll only be able to send one buffer-sized chunk at a time, under-utilizing the available bandwidth.

1.2 No infinite postponement of a stream

- not infinite, should postpone for an assumed ttl (maybe 500 ms in a lazy implementation) to ensure txoff is registered.

I'd recommend the ROUND_TRIP_TIME setting (i.e. double the end-to-end delay); Patrick himself cautioned against hard-coded values.

1.3 Little incentive to use multiple connections

- I think it coveres this.

1.4 No infinite buffering

- Requires buffering of tcp socket buffer + some internal amount to realize to HOL block.   This is equivalent to what woul
...
Re: [spdy-dev] Thinking about flow control Eric 5/31/12 5:52 PM


On May 31, 2012, at 5:08 PM, Alek Storm <alek....@gmail.com> wrote:

On Thu, May 31, 2012 at 11:20 AM, Eric C <eric...@gmail.com> wrote:
I think maybe Patrick's suggestion of txon/txoff to pause a frame is good enough for HOL issues this with priority should allow full utilization of the pipe without much complexity.

This would require the spdy receiver to be able to buffer x + tcp buffer size where x is at what point it sends the txon/txoff (to work perfectly would need to stop reading the receive buffer until you reasonable assume the txoff is processed for HOL issues).  If you receive more than x + tcp buffer you can always kill that stream and start discarding the data (this would be only in case of bad behaving client that ignores txoff).

Comparing this to Greg's primary objectives:

1.1 Uses full available bandwidth

- yes

No. From the time the txoff is sent to the time it's received, that stream could have sent up to one BDP's worth of data that now has to be resent at the next txon. That's wasted bandwidth that could have been used by other streams.

EC: once you hit system resource limits you will have wasted bandwidth yes it wastes some bandwidth when the other end hits a resource issue. The reat of the time there is no waste of bandwidth which can occur with adding windows. As discussed 1.1 and 1.4 do not work together the goal is to get 1.4 without hurting 1.1.


Furthermore, in the case of an endpoint that's resource-constrained but on a fat pipe (like a server under heavy load), the BDP could exceed the size of its output buffers - it'll only be able to send one buffer-sized chunk at a time, under-utilizing the available bandwidth.

I feel like your furthermore is a feature not an issue. There's always a limiting factor. If a server is overloading flooding it with data doesn't help. You need to back off. 



1.2 No infinite postponement of a stream

- not infinite, should postpone for an assumed ttl (maybe 500 ms in a lazy implementation) to ensure txoff is registered.

I'd recommend the ROUND_TRIP_TIME setting (i.e. double the end-to-end delay); Patrick himself cautioned against hard-coded values.

EC: I agree as well - that was just there offering a simple implentation if err is unknown. 


1.3 Little incentive to use multiple connections

- I think it coveres this.

1.4 No infinite buffering
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 5/31/12 6:53 PM
On 5/31/2012 7:13 PM, William Chan (陈智昌) wrote:
>
> No they won't. If they're slow, don't send WINDOW_UPDATEs for them, or
> send smaller ones. There's no need to insist that implementations have
> to be silly and blindly send WINDOW_UPDATEs upon receipt of data, nor
> that the WINDOW_UPDATE deltas have to reopen the stream window to its
> default size. Free up more space in the session window but keep the
> congested stream window shut/small until the next hop consumes more
> bytes and frees up buffers.
>

+1

you could also send a negative delta to slow down a stream that was
observed to be backing up before it used up its entire window (and a
bigger share of the session window). That's an important attribute -
fast by default with action needed to slow things down. But having the
ability to send that signal makes it easier to size the buffers large
enough that we can be sure they'll be > bdp and therefore line rate in
the uncongested common case. Th...
Re: [spdy-dev] Thinking about flow control Alek Storm 5/31/12 6:58 PM
On Thu, May 31, 2012 at 7:52 PM, Eric Ceres <eric...@gmail.com> wrote:
On May 31, 2012, at 5:08 PM, Alek Storm <alek....@gmail.com> wrote:
No. From the time the txoff is sent to the time it's received, that stream could have sent up to one BDP's worth of data that now has to be resent at the next txon. That's wasted bandwidth that could have been used by other streams.
EC: once you hit system resource limits you will have wasted bandwidth yes it wastes some bandwidth when the other end hits a resource issue. The reat of the time there is no waste of bandwidth which can occur with adding windows. As discussed 1.1 and 1.4 do not work together the goal is to get 1.4 without hurting 1.1.

AS: The TCP per-connection window regulates system resource limits; per-stream flow control is used for avoiding HoL blocking - txon/txoff will be sent much more often than you may think. For example, a proxy relaying a large POST upload to a slow server (the poster child for per-stream flow control) would frequently have to send txoff to the client, wait for the server to process some data, then send txon to resume.

The bandwidth efficiencies of both txon/txoff and the current per-stream window degrade as RTT increases because they rely on frequent endpoint-to-endpoint communication. My own proposal (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/jYpwr7BDJx4J) allows receivers to fine-tune how frequently they would like to receive data on a given stream without assigning each stream a fixed in-memory size (which has nothing to do with the system resource limit), and requires no extra periodic round trips. Unfortunately, no one has responded to it yet.

Furthermore, in the case of an endpoint that's resource-constrained but on a fat pipe (like a server under heavy load), the BDP could exceed the size of its output buffers - it'll only be able to send one bu
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 6/1/12 9:57 AM


On Thursday, May 31, 2012 6:58:50 PM UTC-7, Alek Storm wrote:
On Thu, May 31, 2012 at 7:52 PM, Eric Ceres <eric...@gmail.com> wrote:
On May 31, 2012, at 5:08 PM, Alek Storm <alek....@gmail.com> wrote:
No. From the time the txoff is sent to the time it's received, that stream could have sent up to one BDP's worth of data that now has to be resent at the next txon. That's wasted bandwidth that could have been used by other streams.
EC: once you hit system resource limits you will have wasted bandwidth yes it wastes some bandwidth when the other end hits a resource issue. The reat of the time there is no waste of bandwidth which can occur with adding windows. As discussed 1.1 and 1.4 do not work together the goal is to get 1.4 without hurting 1.1.

AS: The TCP per-connection window regulates system resource limits; per-stream flow control is used for avoiding HoL blocking - txon/txoff will be sent much more often than you may think. For example, a proxy relaying a large POST upload to a slow server (the poster child for per-stream flow control) would frequently have to send txoff to the client, wait for the server to process some data, then send txon to resume.

I'm also not happy with the idea of txon/txoff. It would require multiple frames per RTT to make things appear in the least bit smooth, and worse, it simply doesn't offer the same set of guarantees. If doing txon/txoff, what is my max buffer size? I just don't and can't know. What happens if there is my txoff command just happens to require a rexmit due to packet loss? Crapola, buffer can't handle it, stream must be reset.
I believe that the scheme results in far more impementation complexity.
 

The bandwidth efficiencies of both txon/txoff and the current per-stream window degrade as RTT increases because they rely on frequent endpoint-to-endpoint communication. My own proposal (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/jYpwr7BDJx4J) allows receivers to fine-tune how frequently they would like to receive data on a given stream without assigning each stream a fixed in-memory size (which has nothing to do with the system resource limit), and requires no extra periodic round trips. Unfortunately, no one has responded to it yet.

I haven't responded because I believe it ends up being the same as the session+stream windows, with round-robin of stream-sends (hopefully at a priority level), and because I think it overconstrains the solution-set:

While the flow-control windows are necessary for correctness, I'd like for the spec to give wiggle-room for implementations to come up with better schedulers for when to send. I don't want to mandate any round-robin scheme, because I can imagine schemes where this isn't the best thing for an implementation to do.

Another way to put it is: I don't know if mandating fairness by the spec is a good thing. I do agree that it should *allow* for it, however.

Basically, I want (and hopefully you do too) the minimum possible set of behavioral requirements on the protocol such that bytes will eventually get from point A to point B successfully, but with sufficient flexibility in semantics that future engineers (armed with more real-world experience) can adapt implementations to suit the needs of the time or application.

 -=R



...
Re: [spdy-dev] Thinking about flow control Patrick McManus 6/1/12 10:36 AM
On 6/1/2012 12:57 PM, Roberto Peon wrote:

> and worse, it simply doesn't offer the same set of guarantees. If
> doing txon/txoff, what is my max buffer size?

instead of guranteeing your max buffer size is less than N, it
guarantees it is > BDP (and tries to make it approx BDP.) That is it
favors speed over RAM constraints of proxies, while still providing a
soft mechanism to manage the latter. Given the propensity of people
choosing N that is too small to satisfy line rate conditions, you could
argue that this auto tuning is a better property for the protocol
overall. Running at line rate by default is certainly what I want to
see. Slow me down if need be, but don't make me ask permission
beforehand to use the full bandwidth available.

simultaneous stream and session windows provide fast by default too (and
potentially more smoothly  in congested scenarios as you point out) if
the stream windows are big enough.

I guess the question is, with the addition of session windows and
negative stream deltas, are you willing to run stream windows (and set
the default) at something that supports at least 20mbit/sec at 100ms
rtt? I can't imag...
Re: [spdy-dev] Thinking about flow control Roberto Peon 6/1/12 10:47 AM


I guess the question is, with the addition of session windows and negative stream deltas, are you willing to run stream windows (and set the default) at something that supports at least 20mbit/sec at 100ms rtt? I can't imagine defining a new protocol that didn't start at least there - so if the new semantics don't make you feel comfortable deploying that I think we need to look for a different framework entirely.

One of the fundamental goals of the protocol and this whole effort is to decrease latency. Not allowing connections to be fully utilized doesn't meet that goal. We're failing to meet that goal right now, thus this discussion.

Do I want to allocate ~2MB/connection? I don't know yet. If I have space, sure. I'd want to be sure that the connection can be utilized at line rate within 1 RTT. I'd also want any default settings persisted so that the protocol default != the subsequent connection default. I don't want there to be any magic constants, and I also want the failure/retry rate to be very low.
I think that is a fair tradeoff, given that assuming too much space by default can also increase latency by increasing the failure rate (and cause other interesting problems).
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/1/12 11:31 AM
On Fri, Jun 1, 2012 at 12:36 PM, Patrick McManus <mcm...@ducksong.com> wrote:
On 6/1/2012 12:57 PM, Roberto Peon wrote:

and worse, it simply doesn't offer the same set of guarantees. If doing txon/txoff, what is my max buffer size?

instead of guranteeing your max buffer size is less than N, it guarantees it is > BDP (and tries to make it approx BDP.) That is it favors speed over RAM constraints of proxies, while still providing a soft mechanism to manage the latter. Given the propensity of people choosing N that is too small to satisfy line rate conditions, you could argue that this auto tuning is a better property for the protocol overall. Running at line rate by default is certainly what I want to see. Slow me down if need be, but don't make me ask permission beforehand to use the full bandwidth available.

BDP is variable over the lifetime of a connection. The closer you make your buffer size to BDP, the more likely the sender will accidentally overflow your buffer and you'll have to reset and restart the stream. The farther you make your buffer size from BDP, the more you're wasting memory. Is it too much to ask for a flow control scheme that doesn't demand that tradeoff? I don't think so.

simultaneous stream and session windows provide fast by default too (and potentially more smoothly  in congested scenarios as you point out) if the stream windows are big enough.

I guess the question is, with the addition of session windows and negative stream deltas, are you willing to run stream windows (and set the default) at something that supports at least 20mbit/sec at 100ms rtt? I can't imagine defining a new protocol that didn't start at least there - so if the new semantics don't make you feel comfortable deploying that I think we need to look for a different framework entirely.

No, the users of the web framework I contribute to (Tornado) can't afford a 2MB commitment to every stream, since the design goal of Tornado is to solve the C10K problem. 10,000 concurrent requests at 2MB each adds to 20GB. In this (ve
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 6/1/12 11:35 AM


No, the users of the web framework I contribute to (Tornado) can't afford a 2MB commitment to every stream, since the design goal of Tornado is to solve the C10K problem. 10,000 concurrent requests at 2MB each adds to 20GB. In this (very real) scenario, a user would have to downsize stream windows to maybe 1/10th of BDP (200KB) in order to fit in memory. I did the math; there would be more silence on the data link than there would be data transmiss
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/1/12 12:47 PM
On Fri, Jun 1, 2012 at 11:57 AM, Roberto Peon <fe...@google.com> wrote:
On Thursday, May 31, 2012 6:58:50 PM UTC-7, Alek Storm wrote:
The bandwidth efficiencies of both txon/txoff and the current per-stream window degrade as RTT increases because they rely on frequent endpoint-to-endpoint communication. My own proposal (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/jYpwr7BDJx4J) allows receivers to fine-tune how frequently they would like to receive data on a given stream without assigning each stream a fixed in-memory size (which has nothing to do with the system resource limit), and requires no extra periodic round trips. Unfortunately, no one has responded to it yet.

I haven't responded because I believe it ends up being the same as the session+stream windows, with round-robin of stream-sends (hopefully at a priority level), and because I think it overconstrains the solution-set:

While the flow-control windows are necessary for correctness, I'd like for the spec to give wiggle-room for implementations to come up with better schedulers for when to send. I don't want to mandate any round-robin scheme, because I can imagine schemes where this isn't the best thing for an implementation to do.

Another way to put it is: I don't know if mandating fairness by the spec is a good thing. I do agree that it should *allow* for it, however.

Basically, I want (and hopefully you do too) the minimum possible set of behavioral requirements on the protocol such that bytes will eventually get from point A to point B successfully, but with sufficient flexibility in semantics that future engineers (armed with more real-world experience) can adapt implementations to suit the needs of the time or application.

You're right, my proposal was overreaching. I'd like to propose a far simpler solution that, unlike per-stream windows (especially with negative delta), doesn't demand unreasonable amounts of memory, and isn't less efficient for slow streams. Since preventing infinite buffering is handled at the TCP level, per-stream windows are used to control for differences between the rates at which the receiver can process each stream - preventing HoL blocking.

The receiver should be able to let the sender know explicitly the estimated rate at which it can process incoming data for each stream. This is beautifully simple - instead of constantly managing stream windows, flow control frames only need to be sent when the processing rate for a stream changes, and RTTs are never incurred by interrupted streams. Because the sender has been informed of the differences in stream processing rates, it can use whatever strategy it likes to prevent HoL blocking on the receiver - whether fairness (or any other criterion) is taken into account is left up to the implementor.

What do you think?

 -=R



Fu
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 6/1/12 2:14 PM
On Fri, 2012-06-01 at 10:47 -0700, Roberto Peon wrote:

> On Fri, Jun 1, 2012 at 10:36 AM, Patrick McManus <
>         I guess the question is, with the addition of session windows
>         and negative stream deltas, are you willing to run stream
>         windows (and set the default) at something that supports at
>         least 20mbit/sec at 100ms rtt? I can't imagine defining a new
>         protocol that didn't start at least there - so if the new
>         semantics don't make you feel comfortable deploying that I
>         think we need to look for a different framework entirely.


>
> Do I want to allocate ~2MB/connection? I don't know yet.

maybe I just misunderstood you - but 20mbit/sec at 0.1sec is 2mbit or
250KByte, not 2MB. Does that order of magnitude change your feelings?

Obviously in low resource situations you would always want to do
something smaller, but I'm trying to get a sense for if this is
something that is workable for you on normal basis as a realistic
target.

> I also think that this (the first RTT may be constrained, but the next
> not) is fair given use-cases. I don't really care if my upload is 1RTT
> slower only for the first time I ever talk to the site.
>

The notion of the default value is not so much about the first RTT, as
that is limited by IW no doubt (true for both sides of the coin whether
you want to put a cap on buffers or whether you want to send faster the
IW is effectively the window until a settings frame arrives),  but about
building a protocol people will robustly deploy without bottlenecks.

 This is an issue that we're all very focused on right now, but at the
end of the day the defaults are going to rule a great many
implementations and those defa...
Re: [spdy-dev] Thinking about flow control Roberto Peon 6/1/12 2:31 PM


On Fri, Jun 1, 2012 at 2:14 PM, Patrick McManus <mcm...@ducksong.com> wrote:
On Fri, 2012-06-01 at 10:47 -0700, Roberto Peon wrote:

> On Fri, Jun 1, 2012 at 10:36 AM, Patrick McManus <
>         I guess the question is, with the addition of session windows
>         and negative stream deltas, are you willing to run stream
>         windows (and set the default) at something that supports at
>         least 20mbit/sec at 100ms rtt? I can't imagine defining a new
>         protocol that didn't start at least there - so if the new
>         semantics don't make you feel comfortable deploying that I
>         think we need to look for a different framework entirely.


>
> Do I want to allocate ~2MB/connection? I don't know yet.

maybe I just misunderstood you - but 20mbit/sec at 0.1sec is 2mbit or
250KByte, not 2MB. Does that order of magnitude change your feelings?

It makes me 8X happier. :)
 

Obviously in low resource situations you would always want to do
something smaller, but I'm trying to get a sense for if this is
something that is workable for you on normal basis as a realistic
target.

> I also think that this (the first RTT may be constrained, but the next
> not) is fair given use-cases. I don't really care if my upload is 1RTT
> slower only for the first time I ever talk to the site.
>

The notion of the default value is not so much about the first RTT, as
that is limited by IW no doubt (true for both sides of the coin whether
you want to put a cap on buffers or whether you want to send faster the
IW is effectively the window until a settings frame arrives),  but about
building a protocol people will robustly deploy without bottlenecks.

Agreed.
 

 This is an issue that we're all very focused on right now, but at the
end of the day the defaults are going to rule a great many
implementations and those defaults shouldn't be focused on the memory
saving configuration if this is going to have broad http/2
applicability. 10 days ago I asked another v3 server author who I was
doing a little interop testing with what they used for their window and
he said "oh, just the default." The default will be important.

I'd think that, once people have a general understanding of the issues, they'll be able to do something other than just 'maintain the default window.' Right now we're all swimming in a sea of inexperience, though...
My earlier suggestion (to have the client signal the server when it was blocked by flow control) was meant to help implementations deal with this gracefully and without having access to the kernel-level parameters...

For a robust, high-quality implementation, I'd expect that it will have estimates of the amount of buffer it has available on the egress connections and factor that into the flow-control window when it can.

If we're willing to ratchet up the complexity one more level, we can have arbitrary groupings of streams with a shared flow-control window. Each grouping would correspond to a common choke-point. This provides an absolute guarantee on avoidance of HOL blocking th
...
Re: [spdy-dev] Thinking about flow control Jim Roskind 6/1/12 2:50 PM
On Fri, May 18, 2012 at 10:30 AM, Mike Belshe <mbe...@chromium.org> wrote:
Is there data that accompanies this claim?

+1

I had a nice chat with Ryan, and we began to really wonder about all our hypothetical scenarios where things run afoul.  Where is the real data to guide this discussion and design?

Do we have data that shows when/how often we encounter head-of-line blocking, and how severe the degradation is?

A lot of data I've seen shows that the TCP has a congestion window at the end of SPDY sessions with a median of around 17 packets, and a mean of around 65 packets (packets are around 1.4KB.  Hence the median situation is about 23KB packets in flight, and average of as high as 100KB (because of the long tail).  

When folks start talking about MB of buffering ("infinite" buffering?) at the receiver, are we accidentally focusing on a very low probability scenarios?  Is that event only an issue with a giant upload, where latency (for that giant upload) is not critical (plus or minus an RTT)?  Is the event soooo low in probability, that we *could* do something very special, and not cry over that ultra rare RTT cost?

For most(?) use of SPDY, we're doing HTTP GET, and the upload congestion windows (definitively in SPDY, and effectively in TCP) have no impact.

For downloads (to a client), as noted by Roberto, there is often little to no need for flow control, as the client computers are willing to throw as much buffer resources at the problem as they need to in order to get the job done.

I'm thoroughly convinced we need some stream-based congestion control... but without numbers, and real data, we'll surely design a bad system that will serve the user poorly in "common" cases.

Anyone got data? (rather than conjectured scenarios).

Jim

 

I'm mostly siding with Langley's question - that TCP's flow control should work for the overall layer.  Its simple and should suffice just fine.  It sounds like you're trying to flow control between multiple systems now.  (e.g. client -> proxy -> backend server).  This is a mistake - in the end, this will be a mistake - its over-optimizing for the proxy at the expense of the endpoints, because the only way to do this is to add round trips of latency onto the user.

I'll again caution against thinking flow control is easy.  It sounds easy, but its complicated with really subtle implications.

Mike


On Thu, May 17, 2012 at 1:44 PM, Roberto Peon <fe...@google.com> wrote:
All--

We've been having a number of private conversations about flow control.
The flow control that has been deployed in SPDY/3 seems to work, but it has some definite flaws and suboptimalities.
Basically, it only allows for per-stream flow control.

Per-stream flow control is certainly necessary; without it we'd have head-of-line blocking or infinite-buffering requirements at proxies, which is untenable.
On its, own, however, if we are still worried about infinite buffering and wish to
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 6/1/12 3:03 PM
On Fri, 2012-06-01 at 14:50 -0700, Jim Roskind wrote:

>   Where is the real data to guide this discussion and design?
>

that's what started this. on 5/21 I posted that gmail attachments are 3x
slower for my first test scenario in v3. You might think that's not
important, but my product team might easily choose not to ship it based
on that.

There was also a link in there to some work chris strom had that showed
chrome having a tough time ramping up download speeds.

you can call it anecdote, or you can call it data. I call it a problem.

-P



Re: [spdy-dev] Thinking about flow control William Chan 6/1/12 4:15 PM
Frankly, Google is wrong for having such low windows that cause the 3x perf degration on uploads. In spdy/2, we don't have windows...does that cause HoL blocking? Is there any data that shows this? I believe it's known to happen, the interesting thing is how often it does.

But I think that data is about the reverse proxy case. I find the forward proxy case more motivating. A forward proxy that has a desktop client and a mobile client connecting to it, and has a SPDY session to an origin server will get crazy HoL blocking without flow control. It's very conceivable to have a mobile client with a way slower download rate than the desktop client's download rate. I'm surprised we need data to convince people that this HoL
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/1/12 7:26 PM
On Fri, Jun 1, 2012 at 1:35 PM, Roberto Peon <fe...@google.com> wrote:
On Fri, Jun 1, 2012 at 11:31 AM, Alek Storm <alek....@gmail.com> wrote:
On Fri, Jun 1, 2012 at 12:36 PM, Patrick McManus <mcm...@ducksong.com> wrote:
simultaneous stream and session windows provide fast by default too (and potentially more smoothly  in congested scenarios as you point out) if the stream windows are big enough.

I guess the question is, with the addition of session windows and negative stream deltas, are you willing to run stream windows (and set the default) at something that supports at least 20mbit/sec at 100ms rtt? I can't imagine defining a new protocol that didn't start at least there - so if the new semantics don't make you feel comfortable deploying that I think we need to look for a different framework entirely.

No, the users of the web framework I contribute to (Tornado) can't afford a 2MB commitment to every stream, since the design goal of Tornado is to solve the C10K problem. 10,000 concurrent requests at 2MB each adds to 20GB. In this (very real) scenario, a user would have to downsize stream windows to maybe 1/10th of BDP (200KB) in order to fit in memory. I did the math; there would be more silence on the data link than there would be data transmission.

If your proxy knows about the size of the egress buffers, that can be part of the window size...

I'm afraid I don't understand. Could you clarify? I didn't mention a proxy.

-=R
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 6/2/12 9:00 AM


But I think that data is about the reverse proxy case. I find the forward proxy case more motivating. A forward proxy that has a desktop client and a mobile client connecting to it, and has a SPDY session to an origin server will get crazy HoL blocking without flow control. It's very conceivable to have a mobile client with a way slower download rate than the desktop client's download rate. I'm surprised we need data to convince people that this HoL blocking would happen in a forward proxy that does SPDY to an origin server.

I am convinced HoL blocking will happen, and that flow control is needed.

I am not convinced that the combination of connection window and stream window - and in particular the interaction between the 2  - is the right solution, at least with the suggested rules for sending. 

Of the 2, I think connection flow control is the most useful - as a way to avoid TCP flow control, which would block control packets. If we know control packets can go trough - I think there are different options on how to handle buffer use by each stream, stream window is not the only one. 

It seems any flow control solution will rely on some feedback that receiver returns to the sender. It also seem the main action for the sender is to slow down sending on individual streams. I don't understand why the other action - doping some buffered data or streams - is so strongly rejected in this group.

It looks like we'll have some pretty complex code to deal with congestion - very similar with TCP routers. Can we learn more from what TCP is doing ? Any other system that is multiplexing streams and has flow control ( but unlike TCP doesn't drop packets, which see
...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 6/2/12 12:06 PM
" A forward proxy that has a desktop client and a mobile client connecting to it, and has a SPDY session to an origin server will get crazy HoL blocking without flow control. It's very conceivable to have a mobile client with a way slower download rate than the desktop client's download rate. I'm surprised we need data to convince people that this HoL blocking would happen in a forward proxy that does SPDY to an origin server. "

Can you clarify this? Is the forward proxy in this example using the same SPDY session to the origin server for both the mobile and the desktop client at the same time? If so, is this shared SPDY session across proxied clients a use case that SPDY must support?

It seems fundamental to me that SPDY multiplexing should only occur across connections managed by the same app. If there's another app then there should be another SPDY TCP connection.

Peter

On Fri, Jun 1, 2012 at 7:15 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Fri, Jun 1, 2012 at 3:03 PM, Patrick McManus <mcm...@ducksong.com> wrote:
On Fri, 2012-06-01 at 14:50 -0700, Jim Roskind wrote:

>   Where is the real data to guide this discussion and design?
>

that's what started this. on 5/21 I posted that gmail attachments are 3x
slower for my first test scenario in v3. You might think that's not
important, but my product team might easily choose not to ship it based
on that.

There was also a link in there to some work chris strom had that showed
chrome having a tough time ramping up download speeds.

you can call it anecdote, or you can call it data. I call it a problem.

Frankly, Google is wrong for having such low windows that cause the 3x perf degration on uploads. In spdy/2, we don't have windows...does that cause HoL blocking? Is there any data that shows this? I believe it's known to happen, the interesting thing is how often it does.

But I think that data is about the reverse proxy case. I find the forward proxy case more motivating. A forward proxy that has a desktop client and a mobile client connecting to it, and has a SPDY session to an origin server will get crazy HoL blocking without flow co
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/2/12 2:44 PM
On Sat, Jun 2, 2012 at 2:06 PM, Peter Lepeska <bizzb...@gmail.com> wrote:
" A forward proxy that has a desktop client and a mobile client connecting to it, and has a SPDY session to an origin server will get crazy HoL blocking without flow control. It's very conceivable to have a mobile client with a way slower download rate than the desktop client's download rate. I'm surprised we need data to convince people that this HoL blocking would happen in a forward proxy that does SPDY to an origin server. "

Can you clarify this? Is the forward proxy in this example using the same SPDY session to the origin server for both the mobile and the desktop client at the same time? If so, is this shared SPDY session across proxied clients a use case that SPDY must support?

Yes, and absolutely yes. Proxies have the most to gain from connection multiplexing; making them faster makes the Internet faster for everyone.

It seems fundamental to me that SPDY multiplexing should only occur across connections managed by the same app. If there's another app then there should be another SPDY TCP connection.

That's true only for clients, since different processes cannot access each others' TCP connections (although even this could be accomplished if SPDY were added to the kernel's TCP/IP stack). Other than that, there are no rules about which connections may be shared - that's left up to implementors.

Alek

Peter

On Fri, Jun 1, 2012 at 7:15 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Fri, Jun 1, 2012 at 3:03 PM, Patrick McManus <mcm...@ducksong.com> wrote:
On Fri, 2012-06-01 at 14:50 -0700, Jim Roskind wrote:

>   Where is the real data to guide this discussion and design?
>

that's what started this. on 5/21 I posted that gmail attachments are 3x
slower for my first test scenario in v3. You might think that's not
important, but my product team might easily choose not to ship it based
on that.

There was also a link in there to some work chris strom had that showed
chrome having a tough time ramping up download speeds.

you can call it anecdote, or you can call it data. I call it a problem.

Frankly, Google is wrong for having such low windows that cause the 3x perf degration on uploads. In spdy/2, we don't have windows...does that cause HoL blocking? Is there any data that shows this? I believe it's known to happen, the interesting thing is how often it does.

But I think that data is about the reverse proxy case. I find the forward proxy case more motivating. A forward p
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 6/3/12 2:01 AM
On 31 May 2012 18:34, Costin Manolache <cos...@gmail.com> wrote:
> I am ok with the idea of per-connection flow control - as a way to avoid the
> TCP flow control, so control frames or higher-priority streams can go
> trough.

I think it is a misconception to believe that windows can avoid
TCP-flow control.   TCP flow control will depend greatly on what other
things the network and intermediaries are doing.  No matter what we do
with windows, TCP flow control can trigger on a connection.

The point of windows really is to declare how many buffers the
receiver is prepared to commit to read (if the TCP connection is
flowing) and store data.  This is to prevent HOL blocking caused when
TCP flow control is giving back pressure because the receiver is not
reading because just some stream consumer are not consuming and have
thus consumed all available buffers.     Windows stop the sender from
transmitting more data than the receiver is prepared to buffer, so
that if a stream that is not at it's window wants to send something,
then it can be sent.

Data sent that is within a window can still be delayed by TCP flow
control, but what we do know is that the receiver will still be
attempting to read it, so any flow control is not end to end.


On 31 May 2012 15:37, Patrick McManus <mcm...@ducksong.com> wrote:
> a per-connection spdy window as a backstop allows the per stream windows
> to be sized more aggressively without creating blocking problems for
> control or downstream traffic.

If this is the case, then I think per-connection windows are a good thing.
If we think they should be sized to avoid all tcp flow control, then
they are a bad thing (and wont work anyway).

Put anotherway, we could consider that per connection windows are an
attempt to limit the total buffer commitment of the receiver....
however that makes me more cautious about them.   If a client has a
choice between opening a stream on an existing connection and sharing
a perconnection window  Vs opening a new connection and getting it's
own connection window, then a fixed per connection window an incentive
to open new connections.

However,  if the per-connection window grows with the number of
streams (but giving a total that is less than number of streams * max
stream window), then perhaps it can work both as encouraging larger
per stream windows and still not encourage new connections.

So I'm currently in favour of a system that has dynamic windows for
both streams and connections - with the exact algorithms used to size
these windows to not be fully specified.  We can then let
experimenta...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 6/3/12 12:38 PM
"Proxies have the most to gain from connection multiplexing; making them faster makes the Internet faster for everyone. "

This doesn't make sense to me as running multiple users' traffic over the same connection will quickly bump up against the throughput limit of a single connection (~64 KB / RTT). Sharing a SPDY session across users may provide a benefit for the first couple users pooled together but as the number of users increases performance will be better if spread out across multiple SPDY sessions / TCP connections to the origin server.

Peter
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/3/12 1:23 PM
On Sun, Jun 3, 2012 at 2:38 PM, Peter Lepeska <bizzb...@gmail.com> wrote:
"Proxies have the most to gain from connection multiplexing; making them faster makes the Internet faster for everyone. "

This doesn't make sense to me as running multiple users' traffic over the same connection will quickly bump up against the throughput limit of a single connection (~64 KB / RTT). Sharing a SPDY session across users may provide a benefit for the first couple users pooled together but as the number of users increases performance will be better if spread out across multiple SPDY sessions / TCP connections to the origin server.

Throughput is a property of the data link, so opening multiple TCP connections won't get you any more of it - all else being equal (and it isn't), you can send all the data you want through a single connection, up to the throughput limit. However, there is currently (in spdy/3) an incentive to open multiple connections: each one gets its own TCP window, which is a measurement of the receiving endpoint's capacity to buffer what you're sending. I suspect you may have actually been talking about this in the first place.

As a solution, I like Greg's suggestion of dynamically-sized connection windows that, unlike spdy/3, don't depend on fixed-size stream windows. He seems to be in favor of dynamically sizing both connection and stream windows, which in combination with my earlier suggestion of allowing the receiver to send estimates of each stream's expected data sink rate, should satisfy conditions 1.1-1.4, more than satisfy 2.1, and allow implementations to handle 2.2 and 2.3 themselves.

Alek

Peter



On Sat, Jun 2, 2012 at 5:44 PM, Alek Storm <alek....@gmail.com> wrote:
On Sat, Jun 2, 2012 at 2:06 PM, Peter Lepeska <bizzb...@gmail.com> wrote:
" A forward proxy that has a desktop client and a mobile client connecting to it, and has a SPDY session to an origin server will get crazy HoL blocking without flow control. It's very conceivable to have a mobile client with a way slower download rate than the desktop client's download rate. I'm surprised we need data to convince people that this HoL blocking would happen in a forward proxy that does SPDY to an origin server. "

Can you clarify this? Is the forward proxy in this example using the same SPDY session to the origin server for both the mobile and the desktop client at the same time? If so, is this shared SPDY session across proxied clients a use case that SPDY must support?

Yes, and absolutely yes. Proxies have the most to gain from connection multiplexing; making them faster makes the Internet faster for everyone.

It seems fundamental to me that SPDY multiplexing should only occur across connections managed by the same app. If there's another app then there should be another SPDY TCP connection.

That's true only for clients, since different processes cannot access each others' TCP connections (although even this could be accomplished if SPDY were added to the kernel's TCP/IP stack). Other than that, there are no rules about which connections may be shared - that's left up to implementors.

Alek

Peter

On Fri, Jun 1, 2012 at 7:15 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Fri, Jun 1, 2012 at 3:03 PM, Patrick McManus <mcm...@ducksong.com> wrote:
On Fri, 2012-06-01 at 14:50 -0700, Jim Roskind wrote:

>   Where is the real data to guide this discussion and design?
>

that's what started this. on 5/21 I posted that gmail attachments are 3x
slower for my first test scenario in v3. You might think that's not
important, but my product team might easily choose not to ship it based
on that.

There was also a link in there to some work chris strom had that showed
chrome having a tough time ramping up download speeds.

you can call it anecdote, or you can call it data. I call it a problem.

Frankly, Google is wrong for having such low windows that cause the 3x perf degration on uploads. I
...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 6/3/12 1:53 PM
" Throughput is a property of the data link, so opening multiple TCP connections won't get you any more of it - all else being equal (and it isn't), you can send all the data you want through a single connection, up to the throughput limit. "

Let's say an enterprise located in Los Angeles has a 100 Mbps connection to the Internet. All enterprise traffic goes through this proxy. If two enterprise users download data from the same origin server located in NYC and share the same SPDY session over a single TCP connection between the proxy and origin server then their max throughput will be 64 KB divided by 80 ms (round trip time across the US) or 6.4 Mbps. If those same two users data were sent over two SPDY sessions from proxy to origin server, the max throughput would be 2 * 6.4 Mbps. 

There are conditions under which multiplexing users onto the same SPDY session would be beneficial but they seem pretty narrow to me. I think you'd get most of that benefit by pooling and re-using TCP connections so you could mitigate slow start. But in general if more than one user simultaneously wants to download data from an origin server, you're better off giving them each their own SPDY session.

Peter
...
Re: [spdy-dev] Thinking about flow control Daniel Stenberg 6/3/12 2:04 PM
On Sun, 3 Jun 2012, Peter Lepeska wrote:

> Let's say an enterprise located in Los Angeles has a 100 Mbps connection to
> the Internet. All enterprise traffic goes through this proxy. If two
> enterprise users download data from the same origin server located in NYC
> and share the same SPDY session over a single TCP connection between the
> proxy and origin server then their max throughput will be 64 KB divided by
> 80 ms (round trip time across the US) or 6.4 Mbps. If those same two users
> data were sent over two SPDY sessions from proxy to origin server, the max
> throughput would be 2 * 6.4 Mbps.

Are you talking about TCP stacks without the window scale option here?

--

  / daniel.haxx.se
Re: [spdy-dev] Thinking about flow control Simone Bordet 6/3/12 2:05 PM
Hi,

On Sun, Jun 3, 2012 at 10:53 PM, Peter Lepeska <bizzb...@gmail.com> wrote:
> " Throughput is a property of the data link, so opening multiple TCP
> connections won't get you any more of it - all else being equal (and it
> isn't), you can send all the data you want through a single connection, up
> to the throughput limit. "
>
> Let's say an enterprise located in Los Angeles has a 100 Mbps connection to
> the Internet. All enterprise traffic goes through this proxy. If two
> enterprise users download data from the same origin server located in NYC
> and share the same SPDY session over a single TCP connection between the
> proxy and origin server then their max throughput will be 64 KB divided by
> 80 ms (round trip time across the US) or 6.4 Mbps.

Assuming the 64K figure you mention is the SPDYv3 per-stream window,
then you have that *per-stream*, no ?

Simon
--
http://cometd.org
http://intalio.com
http://bordet.blogspot.com
----
Finally, no matter ho...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 6/3/12 2:16 PM
Yes. Though this ( http://en.wikipedia.org/wiki/TCP_window_scale_option ) says all modern operating systems have window scale option on by default, I see the 64 KB limit in my own network trace debugging all the time. I'll have to figure out why that is.

I agree if window scale option is working properly then I can see why proxies might want to multiplexing users onto a single SPDY session.

Peter


On Sun, Jun 3, 2012 at 5:04 PM, Daniel Stenberg <dan...@haxx.se> wrote:
On Sun, 3 Jun 2012, Peter Lepeska wrote:

Let's say an enterprise located in Los Angeles has a 100 Mbps connection to the Internet. All enterprise traffic goes through this proxy. If two enterprise users download data from the same origin server located in NYC and share the same SPDY session over a single TCP connection between the proxy and origin server then their max throughput will be 64 KB divided by 80 ms (round trip time across the US) or 6.4 Mbps. If those same two users data were sent over two SPDY sessions from proxy to origin server, the max throughput would be 2 * 6.4 Mbps.
...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 6/3/12 2:22 PM
Yes you're right.

My point goes away if windows scaling option is working as it should be by default for most modern operating systems. 

It still feels like we should be careful not to stretch SPDY too much for the proxy use case.

Thanks,

Peter
...
Re: [spdy-dev] Thinking about flow control Ilya Grigorik 6/3/12 2:40 PM
On Sun, Jun 3, 2012 at 2:16 PM, Peter Lepeska <bizzb...@gmail.com> wrote:
Yes. Though this ( http://en.wikipedia.org/wiki/TCP_window_scale_option ) says all modern operating systems have window scale option on by default, I see the 64 KB limit in my own network trace debugging all the time. I'll have to figure out why that is.

FWIW, I recently upgraded to Lion (OSX), and was surprised to find window scaling disabled by default - counter to what Wikipedia indicates.

igrigorik { ~ } > sysctl net.inet.tcp.rfc1323
net.inet.tcp.rfc1323: 0

ig 

Re: [spdy-dev] Thinking about flow control Greg Wilkins 6/3/12 3:36 PM
On 3 June 2012 22:23, Alek Storm <alek....@gmail.com> wrote:
>
> As a solution, I like Greg's suggestion of dynamically-sized connection
> windows that, unlike spdy/3, don't depend on fixed-size stream windows. He
> seems to be in favor of dynamically sizing both connection and stream
> windows, which in combination with my earlier suggestion of allowing the
> receiver to send estimates of each stream's expected data sink rate, should
> satisfy conditions 1.1-1.4, more than satisfy 2.1, and allow implementations
> to handle 2.2 and 2.3 themselves.



Just for clarity, this is what I'm proposing (based roughly on
Robertos proposal):


Both per stream and a per connection window are imposed on the sender,
which can have outstanding a maximum of:
min(stream_flow_control_window, per_connection_flow_control_window)
bytes at any point in time.

If the sender is limited by a window, then the sender indicates this
to the receiver (either with a flag on the last data frame or with a
new message), so that the receiver can consider adjusting the window
size.

Window sizes can be dynamic and are under the control of the receiver,
which can set the initial window sizes and grow/shrink the windows
accordingly.  The algorithm(s) for setting the window sizes will not
be defined by the specification, other than to say that if a receiver
set a window size, it MUST continue to read frames with any idle
capacity and attempt to deliver them to stream consumers up until it's
internal buffers of undelivered data have reached the window sizes
with data queued for streams. Furthermore, the algorithm SHOULD NOT
set initial windows such that a stream on a newly accepted connection
has any advantage over new stream on an established connection. Note
that a simple implementation could have a fixed 64KB stream windows
and a fixed infinite(max int) connection window - which would
implement v3 flow control.

Senders SHOULD be aware of TCP/IP flow control and if they are detect
TCP back pressure (write 0 bytes or a blocked write), then they should
refrain from queuing frames and give back pressure to all sending
streams.  Once TCP is flowing again, senders SHOULD select the next
frames to send based on all streams now ready to send (and possibly
their priorities and recent share of the per connection window).


Rating this on my criteria:

1.1 Uses full all available bandwidth
Depends on receivers algorithm - but can be approximated for most
traffic. However I believe that any algorithm limited by 1.4 can
always be defeated by pathological  streams.

1.2 No infinite postponement of a stream
Achieve...
Re: [spdy-dev] Thinking about flow control Costin Manolache 6/3/12 10:39 PM


On Sun, Jun 3, 2012 at 2:01 AM, Greg Wilkins <gr...@intalio.com> wrote:
On 31 May 2012 18:34, Costin Manolache <cos...@gmail.com> wrote:
> I am ok with the idea of per-connection flow control - as a way to avoid the
> TCP flow control, so control frames or higher-priority streams can go
> trough.

I think it is a misconception to believe that windows can avoid
TCP-flow control.   TCP flow control will depend greatly on what other
things the network and intermediaries are doing.  No matter what we do
with windows, TCP flow control can trigger on a connection.

You are right, you can't prevent TCP flow control - the slowest link will somehow impose a flow control. What I meant is avoid having the receiver cause it.


 

The point of windows really is to declare how many buffers the
receiver is prepared to commit to read (if the TCP connection is
flowing) and store data.  This is to prevent HOL blocking caused when
TCP flow control is giving back pressure because the receiver is not
reading because just some stream consumer are not consuming and have

Yes. The goal is to decide when to send and which frame, based on information from receiver. The 'windows' are really indications of how many more bytes can be  buffered by receiver without interrupting the reads and causing flow control, and indirectly how fast each stream is. 

How about turning this around: instead of 'stream window', the receiver will send back a 'buffer status' frame, containing the size of its remaining connection window and how much of each stream is buffered. 

This will not be mandatory - a simple SPDY implementation can just ignore them and keep sending at max speed, and let TCP flow control do its work, accepting head-of-line blocking. And various implementations can experiment with different algorithms and gather more data.

A proxy would still be able to keep memory use under control - based on available resources it can give more RAM to some connections, up to a limit. 

What I'm suggesting is very similar with what was proposed for connection+stream flow control, except the rules for how much to send on each stream. Implementations would have the full range of choices, from ignoring the flow info to doing very fancy things. Instead of having the receiver tell how much to send for each stream/connection - it would tell how much is currently buffered for each stream and how much more total buffers it has at that moment.

In the end, it's the sender who makes the ultimate choice on what frame to send ( or to stop sending ). Having the receiver attempt to control this is a bit backwards IMO. 

Having sender tell receiver it has more data doesn't make sense - if a congestion happens the receiver won't increase buffers, and increasing buffers too much is not the right solution - slowing down sending is. 

Each endpoint is both a sender and a receiver - you can't say that either proxies or servers or clients are 'smarter'.

By not imposing rules in the spec - except about how to pass the required info about flow - we may learn more on what appears to be a complicated problem.


Costin

 
thus consumed all available buffers.     Windows stop the sender from
transmitting more data than the receiver is prepared to buffer, so
that if a stream that is not at it's window wants to send something,
then it can be sent.

Data sent that is within a window can still be delayed by TCP flow
control, but what we do know is that the receiver will still be
attempting to read it, so any flow control is not end to end.


On 31 May 2012 15:37, Patrick McManus <mcm...@ducksong.com> wrote:
> a per-connection spdy window as a backstop allows the per stream windows
> to be sized more aggressively without creating blocking problems for
> control or downstream traffic.

If this is the case, then I think per-connection windows are a good thing.
If we think they should be sized to avoid all tcp flow control, then
they are a bad thing (and wont work anyway).

Put anotherway, we could consider that per connection windows are an
attempt to limit the total buffer commitment of the receiver....
however that makes me more cautious about them.   If a client has a
choice between opening a stream on an existing connection and sharing
a perconnection window  Vs opening a new connection and getting it's
own connection window, then a fixed per connection window an incentive
to open new connections.

However,  if the per-connection w
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/4/12 12:13 AM
On Sun, Jun 3, 2012 at 5:36 PM, Greg Wilkins <gr...@intalio.com> wrote:
On 3 June 2012 22:23, Alek Storm <alek....@gmail.com> wrote:
>
> As a solution, I like Greg's suggestion of dynamically-sized connection
> windows that, unlike spdy/3, don't depend on fixed-size stream windows. He
> seems to be in favor of dynamically sizing both connection and stream
> windows, which in combination with my earlier suggestion of allowing the
> receiver to send estimates of each stream's expected data sink rate, should
> satisfy conditions 1.1-1.4, more than satisfy 2.1, and allow implementations
> to handle 2.2 and 2.3 themselves.

I realize now that I left out a crucial caveat: I'm in favor of dynamically-sized per-connection windows, but against per-stream windows, since HoL blocking can be prevented by the sender respecting each stream's expected data sink rate.

If the sender is limited by a window, then the sender indicates this
to the receiver (either with a flag on the last data frame or with a
new message), so that the receiver can consider adjusting the window
size.

Won't the receiver always have this information, since they know both the window size of the stream and how much data has been sent on it so far? Why would they need to be notified by the sender? Even if they did, it's probably safe to assume that the client has already sized the window as large as its stream consumption rate will allow, since that's in its best interest. Knowing that the sender wants to transmit more data won't do any good - the client shouldn't be artificially limiting it in the first place.

Window sizes can be dynamic and are under the control of the receiver,
which can set the initial window sizes and grow/shrink the windows
accordingly.  The algorithm(s) for setting the window sizes will not
be defined by the specification, other than to say that if a receiver
set a window size, it MUST continue to read frames with any idle
capacity and attempt to deliver them to stream consumers up until it's
internal buffers of undelivered data have reached the window sizes
with data queued for streams. Furthermore, the algorithm SHOULD NOT
set initial windows such that a stream on a newly accepted connection
has any advantage over new stream on an established connection. Note
that a simple implementation could have a fixed 64KB stream windows
and a fixed infinite(max int) connection window - which would
implement v3 flow cont
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 6/4/12 4:22 AM
On 4 June 2012 09:13, Alek Storm <alek....@gmail.com> wrote:
> On Sun, Jun 3, 2012 at 5:36 PM, Greg Wilkins <gr...@intalio.com> wrote:
>> If the sender is limited by a window, then the sender indicates this
>> to the receiver (either with a flag on the last data frame or with a
>> new message), so that the receiver can consider adjusting the window
>> size.
>
> Won't the receiver always have this information,

No because on a connection with latency there will be data and window
updates in flight.  The receiver will not know if the window updates
are received by the sender before or after it hits a window limit. A
delay in further data could just be TCP delay or it could be a SPDY
window limit.

> Even if they did, it's
> probably safe to assume that the client has already sized the window as
> large as its stream consumption rate will allow, since that's in its best
> interest.

It is hard to know a stream consumption rate, specially if the stream
is consuming all the data being sent by the producer.  If all data is
being consumed, then receiving an indication that the SPDY windows
limits were hit tells the receiver that the producer could produce
more data.   Paradoxically it is when the receivers buffers are mostly
empty that you might want to increase the window size - because this
would indicate a fast consumer.  The window size is an indication of
how much data the client is prepared to buffer to avoid HOL if the
consumption suddenly stops and does not mean it actually has to be
buffering data when the window is increased.

Furthermore, the lack of indications that window limits are being hit
can be used to shrink windows.


> We already have dynamically-sized stream windows in v3, since WINDOW_UPDATE
> can specify any positive delta it wants at any time - the "fixed" 64kB
> number is just the default window size when a stream is first opened.
> Therefore, I think your proposal falls victim to the same problem of
> under-utilized bandwidth as latency increases, since resuming data
> transmission after hitting the stream window takes 1.5 RTTs. Then again, I
> might have missed something - is this problem actually solved?

Well my proposal certainly encompasses algorithms that will fall
victim to the same issue.   But it also allows algorithms that will
make a better approximation of avoiding it.

As Patrick has described, the ability to have both connection and
stream windows allows an algorithm to more aggressively size
individual stream windows to cater for the circumstance where there
are a few  very busy streams.  The per connection window is the safe
gua...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/4/12 10:53 AM


On Thu, May 31, 2012 at 9:33 AM, Roberto Peon <fe...@google.com> wrote:


On May 31, 2012 8:44 AM, "Mike Belshe" <mbelshe...@chromium.org> wrote:
>
>
>
> On Wed, May 30, 2012 at 4:16 PM, Alek Storm <alek.storm...@gmail.com> wrote:
>>
>> On Wed, May 30, 2012 at 5:04 PM, Mike Belshe <mbelshe...@chromium.org> wrote:
>>>
>>> I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.
>>>
>>> I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.
>>
>>
>> So a stream can be killed halfway through transmitting a large amount of data? How will the sender know when it is safe to retransmit without the stream getting killed again? And they'll have to retransmit the entire block from the beginning - everything that was sent in the killed stream is lost. That sounds remarkably inefficient.
>
>
> This isn't a normal case, of course, and I don't know why it would happen.  The server is out of memory or resources, so it starts killing.  (just like it does today!)
>
>>
>>> Justification:
>>> a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.
>>
>>
>> Absolutely not; see Patrick's examples (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/-Hnjp94xjG4J) near the beginning of this thread. A lack of per-stream flow control would become even more of a problem as web applications become more media-rich. I believe clients would begin to compensate by opening multiple TCP connections - not for a greater share of the server's bandwidth, but for stream-specific flow control.
>
>
> Bah.  Show me the data. The client can naturally throttle by not making requests.  If we wanted that world, we'd stick with HTTP and multiple connections.  The client wants it as fast as it can get it.  Flow control is not the way to handle prioritization, and once you've hit flow control, it takes a round trip to unwind it (e.g. slow).
>
> I have yet to see any use of client-side flow control which is faster than without flow control.

Proxies are both clients and servers.

>
>
>  
>>
>>
>>> d) If your backend server is down causing backlogs in your proxy, you can write code to deal with that (e.g. failover) or nuke the stream.  Why expose it out to the whole protocol?
>>
>>
>> That doesn't help forward proxies, which don't have control over upstream servers (see Ryan's excellent explanation at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/FGYat2VU22IJ). And I'm sure clients would not be pleased with repeatedly having their upload streams killed and restarting the upload from scratch because the proxy has no way to notify them of the size of its input buffers. With multiple downstream clients doing this at once, the proxy could become overwhelmed and unintentionally DoS'd.
>
>
> No.  If you have a wimpy proxy, limit concurrent requests to 6 just like browsers do today.  This means that you've got one TCP socket with 6 requests instead of 6 TCP sockets like you had with HTTP.  So it's strictly better than what we had before - if your proxy can't handle that then it can't handle HTTP either :-)  Now, you're right, if you want to support 100 concurrent streams, you need to make sure your proxy can handle that (I argue this is trivial for most existing deployments)...  Let's make no mistake - SPDY will require more resources if you want to send more streams through it faster.

This isn't true. A common pattern is long polling cometd connections. Assuming WS support in SPDY arrives, this will become even more common.

Even ignoring cometd, different streams have different target hosts and each has a different connection with different loss and flow characteristics. This changes the cost.

> That's not an accident.  But if your server can't handle it, there are already throttles.
>
> Anyway, I'm not completely against flow control.  I'm against complex, unproven flow control schemes.  The current proposal argues for a simple mechanism; intentionally reducing per-stream max throughput in exchange for reduced buffering. 

My opinion:
The current scheme was a mistake. We messed up. We should make a small rev to the protocol, call that spdy/4, and retire spdy/3 before it gets any more usage.

Trading away max thruput is just not acceptable. It defeats one of the central goals (decrease latency)  of the protocol.

I disagree with this assessment.  

The real mistake here was just an implementation one:  setting the per stream flow control to 12KB is clearly going to cut your max throughput.  Don't do that!

The default limit (64K) allows smaller proxies to be shielded from large initial bursts they couldn't handle.  Well implemented servers, in the existing protocol, are able to increase the window size to reasonably large levels, and then SYN_RESET poorly behaving clients at any time.  This works *great*, and achieves line-speed just fine.

The complexity of a per connection window is really tiny. Instead of updating one int, you update two ints on send().

Flow control always seems easy...

Upon receipt of a flow control window upda

...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/4/12 10:56 AM




No, the users of the web framework I contribute to (Tornado) can't afford a 2MB commitment to every stream, since the design goal of Tornado is to solve the C10K problem. 10,000 concurrent requests at 2MB each adds to 20GB. In this (very real) scenario, a user would have to downsize stream windows to maybe 1/10th of BDP (200KB) in order to fit in memory. I did the math; there would be more silence on the data link than there would be data transmission.

If your proxy knows about the size of the egress buffers, that can be part of the window size...


I'd like to see a reasonable proposal for how to set the connection throttles.  Without seeing the individual packets (which you don't get when you're on top of the transport), how would a non-kernel ha
...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/4/12 11:00 AM


On Fri, Jun 1, 2012 at 3:03 PM, Patrick McManus <mcm...@ducksong.com> wrote:
On Fri, 2012-06-01 at 14:50 -0700, Jim Roskind wrote:

>   Where is the real data to guide this discussion and design?
>

that's what started this. on 5/21 I posted that gmail attachments are 3x
slower for my first test scenario in v3. You might think that's not
important, but my product team might easily choose not to ship it based
on that.

I believe this is an implementation bug on the Google Servers.  If you want to set your window sizes to 12KB (or heck, why not 4KB, guys!)  - it's going to be slow!  



 

There was also a link in there to some work chris strom had that showed
chrome having a tough time ramping up download speeds.


I'm assuming chrome was accidentally throttling the servers by not increasing the window size.  This is also a bug.  Chrome/FF should do so and make this problem vaporize.

mike

 
...
Re: [spdy-dev] Thinking about flow control Peter Lepeska 6/4/12 11:54 AM
I wonder if it's possible for SPDY launch a second TCP connection just in this case where the sink for one of the streams is not absorbing data fast enough. So if a web server or an app is not absorbing data fast enough then pull that stream out of the multiplexed SPDY session and put it into its own new TCP connection. Ideally this would be done without dropping any of the data that has already been transferred successfully. This would do away with per stream flow control altogether.

Peter
...
Re: [spdy-dev] Thinking about flow control William Chan 6/4/12 11:57 AM
That's a slippery slope. We want people to use as few connections as possible....
Re: [spdy-dev] Thinking about flow control William Chan 6/4/12 6:05 PM
I agree that that was a critical mistake.
 

The default limit (64K) allows smaller proxies to be shielded from large initial bursts they couldn't handle.  Well implemented servers, in the existing protocol, are able to increase the window size to reasonably large levels, and then SYN_RESET poorly behaving clients at any time.  This works *great*, and achieves line-speed just fine.

I disagree on your use of RST_STREAM. What do you mean by "poorly behaving client"? If we have a forward proxy that speaks SPDY to origin servers, does a mobile client count as a "poorly behaving client"? Always RST_STREAM'ing a slow client like a mobile client is effectively DoS'ing all mobile clients. That's unacceptable.
 

The complexity of a per connection window is really tiny. Instead of updating one int, you update two ints on send().

Flow control always seems easy...

I think thinking about flow control is hard (hence this long thread) and respecting flow control is easy. An optimized server flow control implementation is difficult.
 

Upon receipt of a flow control window update for stream 0, you update the per connection window. Receiver side, you send the update for the connection window whenever is appropriate, at worst per stream window update.


Originally, the goal here was to limit the exposure of the server to infinite buffering requirements if one stream was too aggressive.  The simple answer is to kill that stream.  If you don't want to kill the stream, you can throttle it.  But now, we're unhappy because the throttling is not dynamic enough to cover the network needs and concurrent stream needs.  There are a lot of subtleties to this which have been debated at the transport layer for eons, and it very much overlaps with what is already being done at those layers.  Now the app needs to dynamically compute BDP too?  Without kernel mods, I'm not sure this is even realistic.  The app doesn't have access to the packet layer at all, and certainly sees fewer packets to measure.  Even if we had this per-connection limit, how would the server decide what value to use?  I don't think the app layer should try this when it is hiding atop a real transport (like TCP)

It's better to just kill streams.

As I explained above, I dislike killing streams as being the only knob in response to load. I think that's a large hammer. Before doing that, we should not send WINDOW_UPDATEs even after data has been received, or send smaller WINDOW_UPDATE deltas, in order to shrink the per-stream buffer sizes. Send a SETTINGS
...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/4/12 6:49 PM


In this case, I was making a false concession - that somehow the client is overloading the server in some bad way - if that really is the view of the proxy, it could kill the stream.
 
If we have a forward proxy that speaks SPDY to origin servers, does a mobile client count as a "poorly behaving client"? Always RST_STREAM'ing a slow client like a mobile client is effectively DoS'ing all mobile clients. That's unacceptable.

Of course, but this isn't a realistic scenario- why would the server be RST_STREAM'ing all the clients?  Is the server just massively under-provisioned?  If so, it could set the window size to 12KB or something like that, and rate-limit the clients.  But this would be a strict tradeoff between reduced buffering on the proxy vs latency on the client.
 

The complexity of a per connection window is really tiny. Instead of updating one int, you update two ints on send().

Flow control always seems easy...

I think thinking about flow control is hard (hence this long thread) and respecting flow control is easy. An optimized server flow control implementation is difficult.

:-)
 
 

Upon receipt of a flow control window update for stream 0, you update the per connection window. Receiver side, you send the update for the connection window whenever is appropriate, at worst per stream window update.


Originally, the goal here was to limit the exposure of the server to infinite buffering requirements if one stream was too aggressive.  The simple answer is to kill that stream.  If you don't want to kill the stream, you can throttle it.  But now, we're unhappy because the throttling is not dynamic enough to cover the network needs and concurrent stream needs.  There are a lot of subtleties to this which have been debated at the transport layer for eons, and it very much overlaps with what is already being done at those layers.  Now the app needs to dynamically compute BDP too?  Without kernel mods, I'm not sure this is even realistic.  The app doesn't have access to the packet layer at all, and certainly sees fewer packets to measure.  Even if we had this per-connection limit, how would the server decide what value to use?  I don't think the app layer should try this when it is hiding atop a real transport (like TCP)

It's better to just kill streams.

As I explained above, I dislike killing streams as being the only knob in response to load. I think that's a large hammer. Before doing that, we should not send WINDOW_UPDATEs even after data has been received, or send smaller WINDOW_UPDATE deltas, in order to shrink the per-stream buffer sizes. Send a SETTINGS frame to shrink the per-stream window sizes. This should be done *before* getting too much memory pressure. RST_STREAM should be used when the stream seems hung, so we want to reclaim buffers, or when under extreme memory pressure (but the
...
Re: [spdy-dev] Thinking about flow control Roberto Peon 6/4/12 7:18 PM
<snip>

My opinion:
The current scheme was a mistake. We messed up. We should make a small rev to the protocol, call that spdy/4, and retire spdy/3 before it gets any more usage.

Trading away max thruput is just not acceptable. It defeats one of the central goals (decrease latency)  of the protocol.

I disagree with this assessment.  

The real mistake here was just an implementation one:  setting the per stream flow control to 12KB is clearly going to cut your max throughput.  Don't do that!

I agree that that was a critical mistake.

Definitely agree that it was a mistake.
 
 

The default limit (64K) allows smaller proxies to be shielded from large initial bursts they couldn't handle.  Well implemented servers, in the existing protocol, are able to increase the window size to reasonably large levels, and then SYN_RESET poorly behaving clients at any time.  This works *great*, and achieves line-speed just fine.

I disagree on your use of RST_STREAM. What do you mean by "poorly behaving client"? If we have a forward proxy that speaks SPDY to origin servers, does a mobile client count as a "poorly behaving client"? Always RST_STREAM'ing a slow client like a mobile client is effectively DoS'ing all mobile clients. That's unacceptable.
 

The complexity of a per connection window is really tiny. Instead of updating one int, you update two ints on send().

Flow control always seems easy...

I think thinking about flow control is hard (hence this long thread) and respecting flow control is easy. An optimized server flow control implementation is difficult.

Flow control is hard. The hard part is (as noted above) figuring out when to assert it.
 
 

Upon receipt of a flow control window update for stream 0, you update the per connection window. Receiver side, you send the update for the connection window whenever is appropriate, at worst per stream window update.


Originally, the goal here was to limit the exposure of the server to infinite buffering requirements if one stream was too aggressive.  The simple answer is to kill that stream.  If you don't want to kill the stream, you can throttle it.  But now, we're unhappy because the throttling is not dynamic enough to cover the network needs and concurrent stream needs.  There are a lot of subtleties to this which have been debated at the transport layer for eons, and it very much overlaps with what is already being done at those layers.  Now the app needs to dynamically compute BDP too?  Without kernel mods, I'm not sure this is even realistic.  The app doesn't have access to the packet layer at all, and certainly sees fewer packets to measure.  Even if we had this per-connection limit, how would the server decide what value to use?  I don't think the app layer should try this when it is hiding atop a real transport (like TCP)

I suggest how earlier. If the socket is writable, and you aren't writing to it because of flow control, the receiver has underestimated BDP for the connection. 
 

It's better to just kill streams.

As I explained above, I dislike killing streams as being the only knob in response to load. I think that's a large hammer. Before doing that, we should not send WINDOW_UPDATEs even after data has been received, or send smaller WINDOW_UPDATE deltas, in order to shrink the per-stream buffer sizes. Send a SETTINGS frame to shrink the per-stream window sizes. This should be done *before* getting too much memory pressure. RST_STREAM should be used when the stream seems hung, so we want to reclaim buffers, or when under extreme memory pressure (but the flow control knobs should be used first to prevent reaching this situation).

Shrinking per-window sizes for all streams require O(num_streams) frames based on the way the protocol works today. Anything that avoids that requires a change that is roughly equivalent in terms of protocol frames as doing a per-session window (e.g. you'd have to store another int, and do a computation as you attempt to send each stream to figure out if you can send or not). 
This doesn't reduce the complexity.

 

That said, I think I'm beginning to come around to your general viewpoint that a per-session flow control window is unnecessary. In the normal case, a server should always have a high enough flow control window so as to send at line rate. When approaching memory pressure situations, a low SPDY per-session window would prevent fully utilizing line rate, but is not very different from simply not reading from the TCP socket, mod the control frames still being processed if using SPDY per-session windows. Processing control frames is probably important, because untimely responses to PING frames can result in peers thinking the SPDY session is dead. But I'm starting to think the application-level flexibility wins do not justify the complexity of per-session windows, and if we really are under memory pressure, then resort to SETTINGS (low per-stream windows) + RST_STREAMs. If you really need to tune the per-session windows, then tune it at the TCP level (using something like net.core.rmem_max, or setsockopt(), but then you lose auto-tuning).

Which complexity?

There is complexity of the code. On the sender side, that is, as described before, updating an int and doing a min(). The receiver side has to update an int and decide when to open up the window.
I'd suggest that almost all of the complexity here is deciding when to open up the window.
This complexity doesn't go away-- it exists whether you use TCP as a mechanism, or if you don't.
If you do attempt to use TCP as the mechanism, you are losing the ability to allow TCP to figure out the receive window, which is especially interesting for server efficiency when goodput < BDP.

For argument's sake, lets throw that out and ignore it--Lets assume we're using TCP's rwin as the flow control mechanism here, and talk about the complexity of the implementation for one which uses just TCP for flow control.

The first obvious question is: Are we willing to use MSG_PEEK?

If we're not using MSG_PEEK (which allows us to 'read' from the buffer without draining it), what heuristics are we going to use for PING frames?
If we ever decide to assert flow-control on the connection, we're potentially delaying the response of any control frame infinitely. Despite the fact that the socket is live, the client will believe it dead and it will (effectively) close all streams, and make a new connection, just to suffer the same fate on a new connection.
Basically, if you don't do MSG_PEEK, life sucks, connections die, liveness checks fail, you find dogs and cats living together.

If we are using MSG_PEEK, we are able to process frames that would otherwise be blocked in the TCP socket due to TCP's in-order delivery guarantees. Using MSG_PEEK, however, requires that we do twice as many syscalls (at minimum), and do twice as many copies (again best case scenario) since there is no way to drain the socket without reading from it for most socket implementations. Worst case, we have to do N reads, doing N^2 copying work, since MSG_PEEK requires you read all of the data to get to the tail of the data every time.
We'll also need to keep a userspace buffer *at least as large* as the socket buffer, so that, we can actually read to the end of t
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/4/12 7:32 PM
On Mon, Jun 4, 2012 at 8:49 PM, Mike Belshe <mbe...@chromium.org> wrote:
On Mon, Jun 4, 2012 at 6:05 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Mon, Jun 4, 2012 at 10:53 AM, Mike Belshe <mbe...@chromium.org> wrote:
The default limit (64K) allows smaller proxies to be shielded from large initial bursts they couldn't handle.  Well implemented servers, in the existing protocol, are able to increase the window size to reasonably large levels, and then SYN_RESET poorly behaving clients at any time.  This works *great*, and achieves line-speed just fine.

I disagree on your use of RST_STREAM. What do you mean by "poorly behaving client"?

In this case, I was making a false concession - that somehow the client is overloading the server in some bad way - if that really is the view of the proxy, it could kill the stream.
 
If we have a forward proxy that speaks SPDY to origin servers, does a mobile client count as a "poorly behaving client"? Always RST_STREAM'ing a slow client like a mobile client is effectively DoS'ing all mobile clients. That's unacceptable.

Of course, but this isn't a realistic scenario- why would the server be RST_STREAM'ing all the clients?  Is the server just massively under-provisioned?  If so, it could set the window size to 12KB or something like that, and rate-limit the clients.  But this would be a strict tradeoff between reduced buffering on the proxy vs latency on the client.

Imagine you're a proxy that has both mobile and desktop clients downstream, and you're multiplexing all their requests to ESPN.com. Everyone's downloading a different video, but the mobile clients must receive their streams at a much slower rate than the desktop clients. With only per-connection flow control, the proxy would keep buffering the mobile clients' streams until it hit the session window, at which point transmission of *all* the clients' streams would stop. Your solution would be to RST_STREAM the mobile clients' streams, even though neither they nor ESPN.com have done anything wrong. Is it the mobile clients' fault for being on a low-bandwidth pipe? You've effectively made it impossible for mobile and desktop clients to coexist on even a proxy rich in resources.

I prefer my own solution over per-stream flow control, but anything's better than crippling proxies.

...
Re: [spdy-dev] Thinking about flow control William Chan 6/4/12 7:50 PM
On Mon, Jun 4, 2012 at 7:18 PM, Roberto Peon <fe...@google.com> wrote:
<snip>

My opinion:
The current scheme was a mistake. We messed up. We should make a small rev to the protocol, call that spdy/4, and retire spdy/3 before it gets any more usage.

Trading away max thruput is just not acceptable. It defeats one of the central goals (decrease latency)  of the protocol.

I disagree with this assessment.  

The real mistake here was just an implementation one:  setting the per stream flow control to 12KB is clearly going to cut your max throughput.  Don't do that!

I agree that that was a critical mistake.

Definitely agree that it was a mistake.
 
 

The default limit (64K) allows smaller proxies to be shielded from large initial bursts they couldn't handle.  Well implemented servers, in the existing protocol, are able to increase the window size to reasonably large levels, and then SYN_RESET poorly behaving clients at any time.  This works *great*, and achieves line-speed just fine.

I disagree on your use of RST_STREAM. What do you mean by "poorly behaving client"? If we have a forward proxy that speaks SPDY to origin servers, does a mobile client count as a "poorly behaving client"? Always RST_STREAM'ing a slow client like a mobile client is effectively DoS'ing all mobile clients. That's unacceptable.
 

The complexity of a per connection window is really tiny. Instead of updating one int, you update two ints on send().

Flow control always seems easy...

I think thinking about flow control is hard (hence this long thread) and respecting flow control is easy. An optimized server flow control implementation is difficult.

Flow control is hard. The hard part is (as noted above) figuring out when to assert it.

Agreed.
 
 
 

Upon receipt of a flow control window update for stream 0, you update the per connection window. Receiver side, you send the update for the connection window whenever is appropriate, at worst per stream window update.


Originally, the goal here was to limit the exposure of the server to infinite buffering requirements if one stream was too aggressive.  The simple answer is to kill that stream.  If you don't want to kill the stream, you can throttle it.  But now, we're unhappy because the throttling is not dynamic enough to cover the network needs and concurrent stream needs.  There are a lot of subtleties to this which have been debated at the transport layer for eons, and it very much overlaps with what is already being done at those layers.  Now the app needs to dynamically compute BDP too?  Without kernel mods, I'm not sure this is even realistic.  The app doesn't have access to the packet layer at all, and certainly sees fewer packets to measure.  Even if we had this per-connection limit, how would the server decide what value to use?  I don't think the app layer should try this when it is hiding atop a real transport (like TCP)

I suggest how earlier. If the socket is writable, and you aren't writing to it because of flow control, the receiver has underestimated BDP for the connection. 
 

It's better to just kill streams.

As I explained above, I dislike killing streams as being the only knob in response to load. I think that's a large hammer. Before doing that, we should not send WINDOW_UPDATEs even after data has been received, or send smaller WINDOW_UPDATE deltas, in order to shrink the per-stream buffer sizes. Send a SETTINGS frame to shrink the per-stream window sizes. This should be done *before* getting too much memory pressure. RST_STREAM should be used when the stream seems hung, so we want to reclaim buffers, or when under extreme memory pressure (but the flow control knobs should be used first to prevent reaching this situation).

Shrinking per-window sizes for all streams require O(num_streams) frames based on the way the protocol works today. Anything that avoids that requires a change that is roughly equivalent in terms of protocol frames as doing a per-session window (e.g. you'd have to store another int, and do a computation as you attempt to send each stream to figure out if you can send or not). 
This doesn't reduce the complexity.

I'm not sure I understand the first part of what you're saying, but I agree that the complexity of flow control isn't reduced.


 

That said, I think I'm beginning to come around to your general viewpoint that a per-session flow control window is unnecessary. In the normal case, a server should always have a high enough flow control window so as to send at line rate. When approaching memory pressure situations, a low SPDY per-session window would prevent fully utilizing line rate, but is not very different from simply not reading from the TCP socket, mod the control frames still being processed if using SPDY per-session windows. Processing control frames is probably important, because untimely responses to PING frames can result in peers thinking the SPDY session is dead. But I'm starting to think the application-level flexibility wins do not justify the complexity of per-session windows, and if we really are under memory pressure, then resort to SETTINGS (low per-stream windows) + RST_STREAMs. If you really need to tune the per-session windows, then tune it at the TCP level (using something like net.core.rmem_max, or setsockopt(), but then you lose auto-tuning).

Which complexity?

There is complexity of the code. On the sender side, that is, as described before, updating an int and doing a min(). The receiver side has to update an int and decide when to open up the window.
I'd suggest that almost all of the complexity here is deciding when to open up the window.
This complexity doesn't go away-- it exists whether you use TCP as a mechanism, or if you don't.
If you do attempt to use TCP as the mechanism, you are losing the ability to allow TCP to figure out the receive window, which is especially interesting for server efficiency when goodput < BDP.

I think you mean that if you setsockopt(), you lose auto-tuning. That is correct. I suggested net.core.rmem_max, which provides a cap which can be used during times of memory pressure, but then re-raised to the default when memory pressure goes away. The obvious downside is this is a system-wide knob, but I believe that if you are writing a performant proxy server, you are monopolizing all system resources anyway, so this doesn't matter.
 

For argument's sake, lets throw that out and ignore it--Lets assume we're using TCP's rwin as the flow control mechanism here, and talk about the complexity of the implementation for one which uses just TCP for flow control.

The first obvious question is: Are we willing to use MSG_PEEK?

If we're not using MSG_PEEK (which allows us to 'read' from the buffer without draining it), what heuristics are we going to use for PING frames?
If we ever decide to assert flow-control on the connection, we're potentially delaying the response of any control frame infinitely. Despite the fact that the socket is live, the client will believe it dead and it will (effectively) close all streams, and make a new connection, just to suffer the same fate on a new connection.
Basically, if you don't do MSG_PEEK, life sucks, connections die, liveness checks fail, you find dogs and cats living together.

I do not follow. I think that if the receiver stops calling read(), then you are correct. I think the receiver should not stop calling read(). TCP windows can be lowered below BDP without impeding receipt of PING frames, unless there is more buffer bloat.
 

If we are using MSG_PEEK, we are able to process frames that would otherwise be blocked in the TCP socket due to TCP's in-order delivery guarantees. Using MSG_PEEK, however, requires that we do twice as many syscalls (at minimum), and do twice as many copies (again best case scenario) since there is no way to drain the socket without reading from it for most socket implementations. Worst case, we have to do N reads, doing N^2 copying work, since MSG_PEEK requires you read all of the data to get to the tail of the data every time.
We'll also need to keep a userspace buffer *at least as large* as the socket buffer, so that, we can actually read to the end of the buffer. I'm not aware of a socket implementation that allows you to do the equivalent of seek withing the socket buffer with a PEEK.



What I'm getting at (or trying to get at) is that the implementation complexity and resource requirements do not diminish (and probably get worse) if you use TCP for the flow control.
There is no free lunch here. It is easier from an implementation standpoint, if we care about the problem at all, to do it in userspace and trust that the OS will size its recv buffers for the roughly amount
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/4/12 8:03 PM
On Mon, Jun 4, 2012 at 6:22 AM, Greg Wilkins <gr...@intalio.com> wrote:
On 4 June 2012 09:13, Alek Storm <alek....@gmail.com> wrote:
> On Sun, Jun 3, 2012 at 5:36 PM, Greg Wilkins <gr...@intalio.com> wrote:
>> If the sender is limited by a window, then the sender indicates this
>> to the receiver (either with a flag on the last data frame or with a
>> new message), so that the receiver can consider adjusting the window
>> size.
>
> Won't the receiver always have this information,

No because on a connection with latency there will be data and window
updates in flight.  The receiver will not know if the window updates
are received by the sender before or after it hits a window limit. A
delay in further data could just be TCP delay or it could be a SPDY
window limit.

Could you give a specific example, using your new frame/flag?

> Even if they did, it's
> probably safe to assume that the client has already sized the window as
> large as its stream consumption rate will allow, since that's in its best
> interest.

It is hard to know a stream consumption rate, specially if the stream
is consuming all the data being sent by the producer.  If all data is
being consumed, then receiving an indication that the SPDY windows
limits were hit tells the receiver that the producer could produce
more data.   Paradoxically it is when the receivers buffers are mostly
empty that you might want to increase the window size - because this
would indicate a fast consumer.  The window size is an indication of
how much data the client is prepared to buffer to avoid HOL if the
consumption suddenly stops and does not mean it actually has to be
buffering data when the window is increased.

Furthermore, the lack of indications that window limits are being hit
can be used to shrink windows.

How would the receiver not know the rate at which its own buffers are being drained? If they're usually empty because data is being consumed quickly, then obviously the window size can be increased - it doesn't need any information from the sender to determine that.

> We already have dynamically-sized stream windows in v3, since WINDOW_UPDATE
> can specify any positive delta it wants at any time - the "fixed" 64kB
> number is just the default window size when a stream is first opened.
> Therefore, I think your proposal falls victim to the same problem of
> under-utilized bandwidth as latency increases, since resuming data
> transmission after hitting the stream window takes 1.5 RTTs. Then again, I
> might have missed something - is this problem actually solved?

Well my proposal certainly encompasses algorithms that will fall
victim to the same issue.   But it also allows algorithms that will
make a better approximation of avoiding it.

As Patrick has described, the ability to have both connection and
stream windows allows an algorithm to more aggressively size
individual stream windows to cater for the circumstance where there
are a few  very busy streams.  The per connection window is the safe
guard that if all streams become busy then the receiver does not have
to honour the large memory commitments for each and every stream.

That's great for streams that can be consumed faster than they're produced, but I fail to see how slow streams with smaller windows will benefit from this. The smaller the window, the more round trips - the bandwidth utilization problem from v3 remains.

...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/5/12 12:16 AM


On Mon, Jun 4, 2012 at 7:18 PM, Roberto Peon <fe...@google.com> wrote:
<snip>

My opinion:
The current scheme was a mistake. We messed up. We should make a small rev to the protocol, call that spdy/4, and retire spdy/3 before it gets any more usage.

Trading away max thruput is just not acceptable. It defeats one of the central goals (decrease latency)  of the protocol.

I disagree with this assessment.  

The real mistake here was just an implementation one:  setting the per stream flow control to 12KB is clearly going to cut your max throughput.  Don't do that!

I agree that that was a critical mistake.

Definitely agree that it was a mistake.
 
 

The default limit (64K) allows smaller proxies to be shielded from large initial bursts they couldn't handle.  Well implemented servers, in the existing protocol, are able to increase the window size to reasonably large levels, and then SYN_RESET poorly behaving clients at any time.  This works *great*, and achieves line-speed just fine.

I disagree on your use of RST_STREAM. What do you mean by "poorly behaving client"? If we have a forward proxy that speaks SPDY to origin servers, does a mobile client count as a "poorly behaving client"? Always RST_STREAM'ing a slow client like a mobile client is effectively DoS'ing all mobile clients. That's unacceptable.
 

The complexity of a per connection window is really tiny. Instead of updating one int, you update two ints on send().

Flow control always seems easy...

I think thinking about flow control is hard (hence this long thread) and respecting flow control is easy. An optimized server flow control implementation is difficult.

Flow control is hard. The hard part is (as noted above) figuring out when to assert it.
 
 

Upon receipt of a flow control window update for stream 0, you update the per connection window. Receiver side, you send the update for the connection window whenever is appropriate, at worst per stream window update.


Originally, the goal here was to limit the exposure of the server to infinite buffering requirements if one stream was too aggressive.  The simple answer is to kill that stream.  If you don't want to kill the stream, you can throttle it.  But now, we're unhappy because the throttling is not dynamic enough to cover the network needs and concurrent stream needs.  There are a lot of subtleties to this which have been debated at the transport layer for eons, and it very much overlaps with what is already being done at those layers.  Now the app needs to dynamically compute BDP too?  Without kernel mods, I'm not sure this is even realistic.  The app doesn't have access to the packet layer at all, and certainly sees fewer packets to measure.  Even if we had this per-connection limit, how would the server decide what value to use?  I don't think the app layer should try this when it is hiding atop a real transport (like TCP)

I suggest how earlier. If the socket is writable, and you aren't writing to it because of flow control, the receiver has underestimated BDP for the connection. 

Ok, but I'm still not clear how you're going to use this.  

Either you wanted the per-stream limit or you didn't.  So now you're saying that if you're at the per-stream limit, but the socket is still writable, you'll write anyway?  If you do that, aren't you just overriding the per-stream limit, making it moot?
 
 

It's better to just kill streams.

As I explained above, I dislike killing streams as being the only knob in response to load. I think that's a large hammer. Before doing that, we should not send WINDOW_UPDATEs even after data has been received, or send smaller WINDOW_UPDATE deltas, in order to shrink the per-stream buffer sizes. Send a SETTINGS frame to shrink the per-stream window sizes. This should be done *before* getting too much memory pressure. RST_STREAM should be used when the stream seems hung, so we want to reclaim buffers, or when under extreme memory pressure (but the flow control knobs should be used first to prevent reaching this situation).

Shrinking per-window sizes for all streams require O(num_streams) frames based on the way the protocol works today. Anything that avoids that requires a change that is roughly equivalent in terms of protocol frames as doing a per-session window (e.g. you'd have to store another int, and do a computation as you attempt to send each stream to figure out if you can send or not). 
This doesn't reduce the complexity.

 

That said, I think I'm beginning to come around to your general viewpoint that a per-session flow control window is unnecessary. In the normal case, a server should always have a high enough flow control window so as to send at line rate. When approaching memory pressure situations, a low SPDY per-session window would prevent fully utilizing line rate, but is not very different from simply not reading from the TCP socket, mod the control frames still being processed if using SPDY per-session windows. Processing control frames is probably important, because untimely responses to PING frames can result in peers thinking the SPDY session is dead. But I'm starting to think the application-level flexibility wins do not justify the complexity of per-session windows, and if we really are under memory pressure, then resort to SETTINGS (low per-stream windows) + RST_STREAMs. If you really need to tune the per-session windows, then tune it at the TCP level (using something like net.core.rmem_max, or setsockopt(), but then you lose auto-tuning).

Which complexity?

I'll cite two examples of complexity.

1) Nobody has stated how to practically implement what you have proposed.
It's easy to say "we'll have a session-level flow control".  But calculating what value should be used for that is very very hard.  TCP takes great efforts to calculate this, and TCP will have far more data than we will at the app layer.  So.... if this is easy, perhaps there is a proposal for how you will calculate what this throttle should even be?  The above stated "if the socket write would fail" is not a solution - that means you hit TCP's throttle already.

2) The fact that google was able to put up a 12KB window before realizing how it would affect performance.
I'm sorry to pour salt on this wound - but this is an important one.  Flow control is so subtle that even the guys writing this protocol were able to screw up performance, and that was with the *easier* flow control policy.  Every additional parameter is one more potential mess up. 
 

There is complexity of the code. On the sender side, that is, as described before, updating an int and doing a min(). The receiver side has to update an int and decide when to open up the window.
I'd suggest that almost all of the complexity here is deciding when to open up the window.
This complexity doesn't go away-- it exists whether you use TCP as a mechanism, or if you don't.
If you do attempt to use TCP as the mechanism, you are losing the ability to allow TCP to figure out the receive window, which is especially interesting for server efficiency when goodput < BDP.

For argument's sake, lets throw that out and ignore it--Lets assume we're using TCP's rwin as the flow control mechanism here, and talk about the complexity of the implementation for one which uses just TCP for flow control.

The first obvious question is: Are we willing to use MSG_PEEK?

If we're not using MSG_PEEK (which allows us to 'read' from the buffer without draining it), what heuristics are we going to use for PING frames?
If we ever decide to assert flow-control on the connection, we're potentially delaying the response of any control frame infinitely. Despite the fact that the socket is live, the client will believe it dead and it will (effectively) close all streams, and make a new connection, just to suffer the same fate on a new connection.
Basically, if you don't do MSG_PEEK, life sucks, connections die, liveness checks fail, you find dogs and cats living together.

If we are using MSG_PEEK, we are able to process frames that would otherwise be blocked in the TCP socket due to TCP's in-order delivery guarantees.

You're misstating what MSG_PEEK does here.  It doesn't allow you to peek around ordering.  I think you're thinking of out-of-band TCP data (which you could read via PEEK).  I've never tried to use OOB data, for fear that it may not be available on some platforms.  I suppose its a possibility to look at this for ping frames.  But its a bit off topic from flow control itself.


I'm going to take a stab at summarizing.

a) Greg posed a nice set of tradeoffs early on which articulated some of the choices we have.

b) Roberto and several others have proposed that we have a session level flow control to enable data flow at line rate on any given stream.   I do not believe any detailed algorithms have been brought forth which could accomplish this.  I'm guessing the final algorithm would look something like TCP's and have similar warm-up properties.

c) Alek proposed a flow control which would stop data packets but not block control packets from flowing.  This seems interesting, but the bulk of our discussion so far has been about achieving line-rate speeds.

d) Mike proposed that the existing protocol is good enough, but needs tuning.  Chrome should increase the window size it advertises to the server so that downloaded streams are effectively unblocked.  The need for reduced memory buffers is really a proxy issue, where a smaller throttle on uploads can still be employed if necessary.  If proxies get into big trouble, they can always RST_STREAM.


Mike





 
Using MSG_PEEK, however, requires that we do twice as many syscalls (at minimum), and do twice as many copies (again best case scenario) since there is no way to
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/5/12 12:36 AM
On Tue, Jun 5, 2012 at 2:16 AM, Mike Belshe <mbe...@chromium.org> wrote:
c) Alek proposed a flow control which would stop data packets but not block control packets from flowing.  This seems interesting, but the bulk of our discussion so far has been about achieving line-rate speeds.

I think there's been a miscommunication - unlike the per-stream flow control proposals, mine would *never* stop data packets from flowing (except due to TCP flow control). Thus, it is the only proposal which achieves both maximum bandwidth utilization and avoids HoL blocking. This is actually my second one - I give a short description here: https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/MhZfs1MBz6MJ. Thanks for mentioning it, though - it hasn't really been discussed.

Alek

d) Mike proposed that the existing protocol is good enough, but needs tuning.  Chrome should increase the window size it advertises to the server so that downloaded streams are effectively unblocked.  The need for reduced memory buffers is really a proxy issue, where a smaller throttle on uploads can still be employed if necessary.  If proxies get into big trouble, they can always RST_STREAM.


Mike





 
Using MSG_PEEK, however, requires that we do twice as many syscalls (at minimum), and do twice as many copies (again best case scenario) since there is no way to drain the socket without reading from it for most socket implementations. Worst case, we have to do N reads, doing N^2 copying work, since MSG_PEEK requires you read all of the data to get to the tail of the data every time.
We'll also need to keep a userspace buffer *at least as large* as the socket buffer, so that, we can actually read to the end of the buffer. I'm not aware of a socket implementation that allows you to do the equivalent of seek withing the socket buffer with a PEEK.



What I'm getting at (or trying to get at) is that the implementation complexity and resource requirements do not diminish (and probably get worse) if you use TCP for the flow control.
There is no free lunch here. It is easier from an implementation standpoint, if we care about the problem at all, to do it in userspace and trust that the OS will size its recv buffers for the roughly amount of data it is holding, which as far as I know is true on most modern OSs.





That being said... I'm happy to ignore it for now and come to an agreement about that later-- I think we're at the point where we need to document the various situations which require the various flow controls to be asserted, and use those as talking points. 

-=R 


...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 6/5/12 3:12 AM
On 5 June 2012 05:03, Alek Storm <alek....@gmail.com> wrote:
> On Mon, Jun 4, 2012 at 6:22 AM, Greg Wilkins <gr...@intalio.com> wrote:
>>
>> On 4 June 2012 09:13, Alek Storm <alek....@gmail.com> wrote:
>> > On Sun, Jun 3, 2012 at 5:36 PM, Greg Wilkins <gr...@intalio.com> wrote:
>> >> If the sender is limited by a window, then the sender indicates this
>> >> to the receiver (either with a flag on the last data frame or with a
>> >> new message), so that the receiver can consider adjusting the window
>> >> size.
>> >
>> > Won't the receiver always have this information,
>>
>> No because on a connection with latency there will be data and window
>> updates in flight.  The receiver will not know if the window updates
>> are received by the sender before or after it hits a window limit. A
>> delay in further data could just be TCP delay or it could be a SPDY
>> window limit.
>
> Could you give a specific example, using your new frame/flag?


Consider the following sequence of events on a SPDY receiver with a 64KB window:

  32KB of data received  (chunk A)
  All data consumed by application
  Window update sent with +32KB to the window (update A)
  32KB of data received   (chunk B)
  All data consumed by application
  Window update sent with +32KB to the window  (update B)
  32KB of data received  (chunk C)
  All data consumed by application
  Window update sent with +32KB to the window  (update C)
  32KB of data received  (chunk D)
  etc.


The corresponding sequence on the sender might be :

  Send 32KB of data (chunk A)
  Send 32KB of data (chunk B)
  blocked by flow control window
  receive update A
  Send 32KB of data (chunk C)
  blocked by flow control window
  receives update B
  Send 32KB of data (chunk D)
  blocked by flow control window
  receives update C
  etc...

which indicates a sender constrained by the SPDY window,  OR it could be

  Send 32KB of data (chunk A)
  receive update A
  blocked on data producer
  Send 32KB of data (chunk B)
  receives update B
  blocked on data producer
  Send 32KB of data (chunk C)
  receives update C
  blocked on data producer
  etc...

which is a sender constrained by a slow producer OR it could be

  Send 32KB of data (chunk A)
  receive update A
  blocked by TCP flow control
  Send 32KB of data (chunk B)
  receives update B
  blocked by TCP flow control
  Send 32KB of data (chunk C)
  receives update C
  blocked by TCP flow control
  etc...

which is a sender constrained by a slow TCP connection.


The receiver cannot tell the difference between these 3 different
scenarios.  Specifically the receiver does not know if update A
arrived at the server before or after chunk B was sent, thus it does
not know if chunk C was window constrained or not.  If  the data
frames could carry a flag indicating that the sender was blocked by
the SPDY window, then the receiver might see:

  32KB of data received  (chunk A)
  All data consumed by application
  Window update sent with +32KB to the window (update A)
  32KB of data received   (chunk B) WINDOW BLOCKED
  All data consumed by application
  Window update sent with +32KB to the window  (update B)
  32KB of data received  (chunk C) WINDOW BLOCKED
  All data consumed by application
  Window update sent with +32KB to the window  (update C)
  32KB of data received  (chunk D) WINDOW BLOCKED
  etc.

which would tell it that the sender  would benefit from having the
window enlarged.     If the flag is not set, then that tells the
receiver that something other than the window is the constraint on the
data rate and there is no need to increase the window.




>> As Patrick has described, the ability to have both connection and
>> stream windows allows an algorithm to more aggressively size
>> individual stream windows....
>
> That's great for streams that can be consumed faster than they're produced,
> b...
Re: [spdy-dev] Thinking about flow control Patrick McManus 6/5/12 6:05 AM
On Tue, 2012-06-05 at 00:16 -0700, Mike Belshe wrote:


> b) Roberto and several others have proposed that we have a session
> level flow control to enable data flow at line rate on any given
> stream.   I do not believe any detailed algorithms have been brought
> forth which could accomplish this.  I'm guessing the final algorithm
> would look something like TCP's and have similar warm-up properties.
>

I favor the simplest possible interpretation of this. Add a
session-window in addition to the stream-window. Senders can send the
min of the 2. Receivers should not fuss with trying to dynamically
determine the right size according to the network - size it big enough
to support high BDPs (no matter what the connection may actually be) and
if resource constraints mean you can't actually operate like that full
time then reduce the windows as necessary while you go buy more ram. The
ability to use negative deltas are key here in order to allow fairly
quick closing of a window that is well oversized for its actual bdp
(because there is not attempt at sizing them accurately).

as an example - run 400KB session windows, with 250KB stream windows. If
you really are low on resources, run with smaller versions at the cost
of throttling bandwidth. That's a straight forward tradeoff that
hopefully addresses the buffering problem of stream-buffer *
max-streams. If the problem is 1-or-a-subset of streams that are backing
up then use a negative delta to quickly shrink that window to something
small (as at 250KB it probably has a lot of unused credits for many
BDPs) to throttle sending. Exactly how to manage this window when
intentionally constricting sending rate is tricky, but is left up to
implementations just as it is in v3 - but in the default case its not an
issue as dat...
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 6/5/12 7:23 AM


FWIW, I landed a change yesterday (http://codereview.chromium.org/10479014/) which increases Chrome's receive window size to 10MB / stream, which should hopefully be effectively unlimited.

Cheers,

Ryan
 


Mike





 
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 6/5/12 8:56 AM
Than why is the receiver controlling the flow control ? 

The sender knows the difference, if it would also know the receiver buffer status
for each stream it could make better decisions. 


Costin

 
Specifically the receiver does not know if update A
arrived at the server before or after chunk B was sent, thus it does
not know if chunk C was window constrained or not.  If  the data
frames could carry a flag indicating that the sender was blocked by
the SPDY window, then the receiver might see:

 32KB of data received  (chunk A)
 All data consumed by application
 Window update sent with +32KB to the window (update A)
 32KB of data received   (chunk B) WINDOW BLOCKED
 All data consumed by application
 Window update sent with +32KB to the window  (update B)
 32KB of data received  (chunk C) WINDOW BLOCKED
 All data consumed by application
 Window update sent with +32KB to the window  (update C)
 32KB of data received  (chunk D) WINDOW BLOCKED
 etc.

which would tell it that the sender  would benefit from having the
window enlarged.     If the flag is not set, then that tells the
receiver that something other than the window is the constraint on the
data rate and there is no need to increase the window.




>> As Patrick has described, the ability to have both connection and
>> stream windows allows an algorithm to more aggressively size
>
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/5/12 12:00 PM
Thanks, it's clear to me now. I still can't imagine an algorithm that would take into account the sender's data production rate, since I would think they depend only on the receiver's consumption rate. However, my imagination may be lacking in this respect, and I suppose a flag on DATA frames wouldn't be much of a complexity burden.

>> As Patrick has described, the ability to have both connection and
>> stream windows allows an algorithm t
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/5/12 12:43 PM
On Tue, Jun 5, 2012 at 8:05 AM, Patrick McManus <mcm...@ducksong.com> wrote:
On Tue, 2012-06-05 at 00:16 -0700, Mike Belshe wrote:
> b) Roberto and several others have proposed that we have a session
> level flow control to enable data flow at line rate on any given
> stream.   I do not believe any detailed algorithms have been brought
> forth which could accomplish this.  I'm guessing the final algorithm
> would look something like TCP's and have similar warm-up properties.
>

I favor the simplest possible interpretation of this. Add a
session-window in addition to the stream-window. Senders can send the
min of the 2. Receivers should not fuss with trying to dynamically
determine the right size according to the network - size it big enough
to support high BDPs (no matter what the connection may actually be) and
if resource constraints mean you can't actually operate like that full
time then reduce the windows as necessary while you go buy more ram. The
ability to use negative deltas are key here in order to allow fairly
quick closing of a window that is well oversized for its actual bdp
(because there is not attempt at sizing them accurately).

as an example - run 400KB session windows, with 250KB stream windows. If
you really are low on resources, run with smaller versions at the cost
of throttling bandwidth. That's a straight forward tradeoff that
hopefully addresses the buffering problem of stream-buffer *
max-streams. If the problem is 1-or-a-subset of streams that are backing
up then use a negative delta to quickly shrink that window to something
small (as at 250KB it probably has a lot of unused credits for many
BDPs) to throttle sending. Exactly how to manage this window when
intentionally constricting sending rate is tricky, but is left up to
implementations just as it is in v3 - but in the default case its not an
issue as data just flows unconstricted.

I'm inclined to agree with Mike on this one - calculating BDPs is hard at the app level (does this scheme require it?), although this is an improvement over txon/txoff. I'm still quite concerned that data will not flow at line rate for streams which consume data more slowly than it is produced. It's easy to imagine scenarios in which performance is destroyed on high-bandwidth connections which have the misfortune of being high-latency.

A
...
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 6/5/12 12:47 PM


It seems to me that if data is being produce more quickly than it is consumed, then one of these must be true:

a) the link will not be saturated
b) the receiver will need to buffer unlimited data.

Since we explicitly want to avoid infinite buffering, doesn't that mean the the link must not be saturated?  Is there another alternative?

Cheers,

Ryan
 
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 6/5/12 1:16 PM
On 5 June 2012 21:47, Ryan Hamilton <r...@google.com> wrote:
> It seems to me that if data is being produce more quickly than it is
> consumed, then one of these must be true:
>
> a) the link will not be saturated
> b) the receiver will need to buffer unlimited data.
>
> Since we explicitly want to avoid infinite buffering, doesn't that mean the
> the link must not be saturated?  Is there another alternative?

Remember we are multiplexed, so a single link can have multiple
producers and consumers.
The intent of this conversation is to come up with a mechanism that
will allow a slow producer give back pressure to its corresponding
producer so that it does not fill up all the buffers available.

This is not really about avoiding saturating the link... ideally we
want to saturate the link because that is maximum speed.   In essence
it is about making sure that the receiver always has sufficient
buffers available to unsaturate the link by reading data EVEN IF all
the ...
Re: [spdy-dev] Thinking about flow control Patrick McManus 6/5/12 1:23 PM
On Tue, 2012-06-05 at 22:16 +0200, Greg Wilkins wrote:
> On 5 June 2012 21:47, Ryan Hamilton <r...@google.com> wrote:
> > It seems to me that if data is being produce more quickly than it is
> > consumed, then one of these must be true:
> >
> > a) the link will not be saturated
> > b) the receiver will need to buffer unlimited data.
> >
> > Since we explicitly want to avoid infinite buffering, doesn't that mean the
> > the link must not be saturated?  Is there another alternative?
>
> Remember we are multiplexed, so a single link can have multiple
> producers and consumers.
> The intent of this conversation is to come up with a mechanism that
> will allow a slow producer give back pressure to its corresponding
> producer so that it does not fill up all the buffers available.
>

back pressure would be sent to the fast side of the proxy via a
combination of a negative window update followed by throttled window
updates (presumably at the rate they are received from...
Re: [spdy-dev] Thinking about flow control Ryan Hamilton 6/5/12 2:35 PM
updates (presumably at the rate they are received from the slow side) to
keep things flowing smoothly at appox the slower line rate.

Perhaps I misunderstood what you said here:

I'm still quite concerned that data will not flow at line rate for streams which consume data more slowly than it is produced
 
It seemed to me that if we have a stream which is consuming data more slowly than it is produced, that that can NOT flow at line r
...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 6/6/12 2:31 AM


On 5 June 2012 23:35, Ryan Hamilton <r...@google.com> wrote:
> It seemed to me that if we have a stream which is consuming data more slowly
> than it is produced, that that can NOT flow at line rate.  But you seem to
> be suggesting that such a stream SHOULD flow at line rate.  Can you help me
> understand what I'm confused about?

A stream that is consuming data slowly will not flow at line rate.  It will be throttled by the window mechanism so that the receivers buffers do not fill and cause HOL blocking.
But the issue is that if the windows are sized incorrectly, then this may prevent a stream from being able to flow at line rate IF it has a fast consumer and producer.

Here are some criteria that I posted earlier that describe  what I think the flow control is trying to achieve:


1.1 Uses full all available bandwidth
The whole point of SPDY is to make the web faster, so if there is a willing stream producer, a willing stream consumer and available capacity in the pipe between SPDY implementations, then we should allow that capacity to be used up to and possibly even slightly beyond TCP/IP flow control.

1.2 No infinite postponement of a stream
The behaviour of one stream should not be able to infinitely postpone the delivery of data on another stream. We can control the behaviour of compliant SPDY senders and receivers, but we cannot control the behaviour of stream consumers and producers (the application).  Thus we have to consider that stream producers and consumers may act maliciously (either by design, by error or by force majeure (eg DNS resolution suddenly blocks)).   This does not mean that we have to avoid congesting the TCP pipe, just so long as we know the other end (the SPDY receiver) will eventually uncongest the pipe even if a stream consumer is not reading data - ie that the SPDY receiver has sufficient buffers.

1.3 Little incentive to use multiple connections
One of the problems with HTTP that has driven the development of SPDY is to remove the incentive for clients to use multiple connections.  Any per connection limit (such as TCP/IP slow start windows) are incentives to have multiple connections.  For example if we allocate a default initial per connection window, then a client that opens 2 connections will get twice times that limit and better initial performance.  Worse still, because of TCP/IP slow start, once you open 2 connections, you'll probably open 6 or 8 to get multiple slow start window allocations as well.

1.4 No infinite buffering
When an endpoint accepts a connection and/or a stream, it must be able to know the maximum memory that it has to commit to provide in order to satisfy the specification.  If accepting a connection/stream can result in unlimited memory commitments then we are open to denial of service attacks and unpredictable application performance.

The secondary factors that we should consider are many, but I think they should include:

2.1 Complexity
Avoiding complexity is a motherhood statement.  Yes we want to be as simple as possible, but not to the point were we significantly compromise the primary factors.  At the end of they day, there is likely to be perhaps a few hundred or a few thousand SPDY implementations that will provide infrastructure for millions of developers - better we suck up some complexity rather than fail a primary objective.

2.2 Fairness
Another motherhood statement. Yes we want to be fair between streams, but fair is really subjective and difficult to quantify.  Is takin...
Re: [spdy-dev] Thinking about flow control Greg Wilkins 6/6/12 3:04 AM
On 5 June 2012 09:16, Mike Belshe <mbe...@chromium.org> wrote:
>
> d) Mike proposed that the existing protocol is good enough, but needs tuning.  Chrome should increase the window size it advertises to the server so that downloaded streams are effectively unblocked.  The need for reduced memory buffers is really a proxy issue, where a smaller throttle on uploads can still be employed if necessary.  If proxies get into big trouble, they can always RST_STREAM.

I think the browser having a 10MB window per stream will work well for
down loads.   10MB is << infinity in terms of RAM for most client
machines, but is >> BDPs for most networks (eg  ADSL2+: 20 Mbs * 75 ms
RTT = 0.19MBs ).  So 10MB is probably overkill and 1MB might be a
better fit.

For aggregating proxies and servers that have many more streams to
deal with, 10MB per stream may as well be infinite buffering.  Even
0.2MBs is going to be tough (== 20GB for 100k streams).  But for
servers, only a minority of streams will upload and many of those will
be small. Also the HTTP headers tell the server what is coming so
buffer commitments can be estimated a little in advance.

For aggregating proxies it is tougher as they are dealing with
download traffic to many clients. So they can either buy more RAM,
live closer to readl BDPs (and thus throttle some) or be like the
airlines and  rely on statistical overbooking  of their resources. If
they get into trouble, RST is their way out.  Not nice but the 100k
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/6/12 6:35 PM
It seemed to me that if we have a stream which is consuming data more slowly than it is produced, that that can NOT flow at line rate.  But you seem to be suggesting that such a stream SHOULD flow at line rate.  Can you help me understand what I'm confused about?

It was actually me that said that ;). Perhaps "line rate" was the wrong term to use - "maximum bandwidth efficiency" would be better. This means that data will be sent at an average rate roughly equal to the rate it's consumed (if a 100MB file can be consumed at 1MB/sec, then 100MB will arrive over a period of 100 seconds). In the case of slow streams, the receiver will constantly cycle through the following states:

1) Data being sent, receiver's buffer filling
2) Data transmission stopped, receiver's buffer draining
3) Receiver's buffer empty, window update in flight
4) Window update received, data resumption in flight (but not yet arrived)

States 3 and 4 will be extremely painful on a high-latency con
...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/6/12 10:25 PM


On Tue, Jun 5, 2012 at 6:05 AM, Patrick McManus <mcm...@ducksong.com> wrote:
On Tue, 2012-06-05 at 00:16 -0700, Mike Belshe wrote:


> b) Roberto and several others have proposed that we have a session
> level flow control to enable data flow at line rate on any given
> stream.   I do not believe any detailed algorithms have been brought
> forth which could accomplish this.  I'm guessing the final algorithm
> would look something like TCP's and have similar warm-up properties.
>

I favor the simplest possible interpretation of this. Add a
session-window in addition to the stream-window. Senders can send the
min of the 2. Receivers should not fuss with trying to dynamically
determine the right size according to the network - size it big enough
to support high BDPs (no matter what the connection may actually be) and
if resource constraints mean you can't actually operate like that full
time then reduce the windows as necessary while you go buy more ram. The
ability to use negative deltas are key here in order to allow fairly
quick closing of a window that is well oversized for its actual bdp
(because there is not attempt at sizing them accurately).

as an example - run 400KB session windows, with 250KB stream windows. If

How do you decide 400KB/250KB?  Is it baked in as a constant?  It is certainly different than 12 or 64KB, but its ultimately the same thing - its a random throttle.  By being bigger, it will less often impact performance (and also leave proxies at more buffer exposure), but its just another random constant.

By having two of them, it does allow you to have bimodal behavior for 1 active stream vs multiple active streams (which is quite cool).  But neither one is going to go at line rate here for high BDP.

In your example, you can now have two stuck streams deadlock the entire session, right?  The simpler algorithm can't deadlock new streams.

Mike

 
you really are low on resources, run with smaller versions at the cost
of throttling bandwidth. That's a straight forward tradeoff that
hopefully addresses the buffering problem of stream-buffer *
max-streams. If the problem is 1-or-a-subset of streams that are backing
up then use a negative delta to quickly shrink that window to something
small (as at 250KB it probably has a lot of unused credits for many
BDPs) to throttle sending. Exactly how to manage this window when
intentionally constricting sen
...
Re: [spdy-dev] Thinking about flow control Patrick McManus 6/7/12 7:53 AM
hi Mike,

On Wed, 2012-06-06 at 22:25 -0700, Mike Belshe wrote:

> On Tue, Jun 5, 2012 at 6:05 AM, Patrick McManus <mcm...@ducksong.com>
> wrote:

>         I favor the simplest possible interpretation of this. Add a
>         session-window in addition to the stream-window.
[..]
>        
>         as an example - run 400KB session windows, with 250KB stream
>         windows. If
>
>
> How do you decide 400KB/250KB?  Is it baked in as a constant?

So these criticisms are fair, but I think somewhat mitigated by the
nature of what they are measuring. They are measuring a resource
constrained implementation's memory budget which is something that is
reasonable to configure. They are not measuring BDP of a particular
connection, though you should obviously compare your local configuration
to the BDP's you expect to be able to handle to see if your resources
are sufficient. If you aren't resource constrained, then make them
~infinte! (as firefox spdy/3 did)

>  It is certainly different than 12 or 64KB, but its ultimately the
> same thing - its a random throttle.  

neither 12KB or 250KB are random, though they are throttles. 250KB
reflects a (theoretical) choice to place an upper bound of uploads of
20mbit/s at 100ms rtt in order to have a memory bound guarantee.. (I'm
not saying that's the right criteria btw, just what the example was
derived from). 12KB reflected the resources the google proxy was willing
to commit under v3's stream-window-only scheme.

AFAICT 64KB was random :)

You can make the legitimate criticism that 250KB is too small for 15mbit
at 400ms (satellite?) - so if you're not constrained by resources then
don't set it anywhere near this low! But if you are constrained by
resources then its essential to ask yourself what you want to be able to
serve and if you have the resources to do it. At least this answers the
question of what you'll be able to deal with. The addition of the
session window lets you size the stream windows more aggressively and
that's 90% of its value.

Firefox, being a client and largely unrestricted by resources,
implemented v3 with a 256 MegaBYTE stream window (i.e. no limit) because
resource management is not our chief concern right now - I'd rather get
the data as fast as possible for all network types and stall the whole
session if need be via tcp rwin. But it is understandable that a server
or proxy would have a different priority - but if the server shares the
same pov the 2 window scheme still allows them to just run with
~infinite windows and let the data flow uninhibited.

> In your example, you can now have two stuck streams deadlock the
> entire session, right?  The simpler algorithm can't deadlock new
> streams.

There is a penalty to be paid for creating the max-buffer guarantee, but
I don't envision a deadlock. Let's consider a 500/250 configuration for
easy maths.

Stream 1 sends 250KB concurrently to stream 3 sending 250KB and the
server doesn't have anywhere to put any of the data right away (e.g.
backend database is slow connecting) so it doesn't generate window
updates. Both streams have more to send but are flow controlled. Stream
5 gets started and would like to send 100KB but cannot because the
session window is also flow controlled. Stream 5 could be serviced
quickly (e.g. goes to a local database instead of a distributed back
end) so its in every one's interest to let it proceed.

First of all, the server has achieved its goal of limiting its exposure
to 500KB and that's important. If it really only has 500KB worth of
buffering then _stopped_ is exactly where we want to be until that data
finds a home. I wouldn't call that a deadlock.

but let's assume the receiver comes up with 250KB more buffers and it
wants to let stream 5 (or any new stream) proceed while keeping streams
1 and 2 paused.

It can do that a couple ways.. One would be to update the base session
window to 750KB (of which 500KB is still used). That frees up stream 5.
The bad thing here is that once stream 1 and stream 3 do clear up the
session is left with 750KB of new burst exposure, so the receiver needs
an algorithm to shrink the session window from 750 back to 500.. which
is annoying but hardly unsolvable.

An alternative, and my preferred way to go about it, would be to borrow
the necessary window from an existing stream. Let's take it from stream
1 - First, send Stream 1 a negative window adjustment (v3 doesn't
support this - it would be an addition) that has the semantics of
reducing the base stream window size by 250KB. So that means stream 1
has now used 250KB of a 0byte window (double special super flow
controlled! :)). Now send stream 1 a normal window update of 250KB,
which brings its state to 0 used from a 0 byte window. The net result is
that stream 1 is still flow controlled by its stream window (0 of 0
used), stream 3 is still flow controlled by its stream window (250KB of
250KB used), but stream 5 can proceed because it is 0 of 250KB used and
the session window is 250KB of 500KB used. As the buffers for stream 1
are eventually moved to the backend window updates can be sent to that
stream allowing it to send again.

no deadlock. There is a potential rtt pause here as the receiver has to
deal with the problem of restarting thin...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/7/12 9:44 AM


Fair enough, my use of the word random was unfair and derogatory :-)

I guess what I meant is that they're just constants.

To defend the 64KB as not being 'random' either - it was intended to be larger than most stream bodies, and we picked it looking at the histograms of SPDY stream lengths and picking something sufficiently rare.  I then padded up to a power of 2 because I'm a computer geek and that's what geeks do with all constants.

 

You can make the legitimate criticism that 250KB is too small for 15mbit
at 400ms (satellite?) - so if you're not constrained by resources then
don't set it anywhere near this low! But if you are constrained by
resources then its essential to ask yourself what you want to be able to
serve and if you have the resources to do it. At least this answers the
question of what you'll be able to deal with. The addition of the
session window lets you size the stream windows more aggressively and
that's 90% of its value.

Firefox, being a client and largely unrestricted by resources,
implemented v3 with a 256 MegaBYTE stream window (i.e. no limit) because
resource management is not our chief concern right now - I'd rather get
the data as fast as possible for all network types and stall the whole
session if need be via tcp rwin. But it is understandable that a server
or proxy would have a different priority - but if the server shares the
same pov the 2 window scheme still allows them to just run with
~infinite windows and let the data flow uninhibited.

 I understand.  That's basically the way we felt about flow control in general.  
You lost me a little on the negative window adjustment, but I get the concept.  In the end there is no magic, you can either:
    - toss some data to open the flow control
    - increase the amount of buffering desired
I assume you're proposing the latter.  The server got stuck at 500KB of exposure; waited some period, and realized the only way out of the blockage was to either purge or increase, and you're proposing increase. 

To avoid the session-level stall, the implementation needs to be substantially more complicated than the simple algorithm which it was described as in earlier messages.  Before we said this was "just consider your window to be the min of throttle 1 or throttle 2".  But, in order to avoid stalls, the receiver now has to monitor whether it's at session throttle, and if so, has to go do something or the whole thing deadlocks. 

To be fair - my simpler proposal doesn't have unbounded buffering.  If you keep throwing new streams at a server, you keep getting buffer space per stream.  I don't think this happens in practice (where a single client just keeps opening ever-increasing streams to be mean), but I suppose it could happen in some sort of a retry from client case when the server is sick...  The proposal you have put forth does provide better limits for servers to truly limit their exposure.  In my proposal, the server would be free to start nuking streams to reclaim space.


no deadlock. There is a potential rtt pause here as the receiver has to
deal with the problem of restarting things after the session window is
exhausted and the streams are stuck. But I think that's the right place
to put the inevitable penalty. Its certainly less painful that RSTing
things (and likely ending back up in the same place).

I think you're being squishy here :-)  On one hand, you claim victory for having a fixed server exposure of 500KB.  But, if you let that be static, then you can have total session stallouts.  So, in addition to having that clamp, implementors will need to be able to increase the exposure on-the-fly.  This means that the 500KB wasn't *really* the exposure to begin with.  But, it does allow servers to dynamically adjust in a conscious and controlled way.

I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.


...
Re: [spdy-dev] Thinking about flow control Costin Manolache 6/7/12 3:08 PM
On Thu, Jun 7, 2012 at 9:44 AM, Mike Belshe <mbe...@chromium.org> wrote:

I think you're being squishy here :-)  On one hand, you claim victory for having a fixed server exposure of 500KB.  But, if you let that be static, then you can have total session stallouts.  So, in addition to having that clamp, implementors will need to be able to increase the exposure on-the-fly.  This means that the 500KB wasn't *really* the exposure to begin with.  But, it does allow servers to dynamically adjust in a conscious and controlled way.

In my experience when a service/server is slow, a lot of streams will stall. Flow control and 'bound' memory are mostly needed when this case happens, so I think in practice when 'stallouts' start to happen there will be no extra memory. 

 


I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I'll be in vacation - but I want to repeat my proposal to deal with 'stalled' streams by dropping some frames.

This is not (just) some crazy idea, it has been used for few years in android. And IMHO it is simpler to implement 
on both sides than the proposed 'increase the buffer somehow'.

It requires the sender to keep the frames it sends until it receives the window update (i.e. confirmation that they went trough).
A negative window would indicate that some frames have been dropped, and it needs to resend them.

Besides android, TCP is using 'dropped' frames/retransmit for flow control.

I think this proposal will address both 'bound memory' and simple enough handling of stalled streams. 


Costin

 


 

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
stream windows could be sized ~infinitely (so you wouldn't even need to
consider what BDP might be) and then reduced (with negative updates) to
some throttling value only when they started causing buffering on the
receiver. Bu
...
Re: [spdy-dev] Thinking about flow control William Chan 6/7/12 3:32 PM
On Thu, Jun 7, 2012 at 3:08 PM, Costin Manolache <cos...@gmail.com> wrote:
On Thu, Jun 7, 2012 at 9:44 AM, Mike Belshe <mbe...@chromium.org> wrote:

I think you're being squishy here :-)  On one hand, you claim victory for having a fixed server exposure of 500KB.  But, if you let that be static, then you can have total session stallouts.  So, in addition to having that clamp, implementors will need to be able to increase the exposure on-the-fly.  This means that the 500KB wasn't *really* the exposure to begin with.  But, it does allow servers to dynamically adjust in a conscious and controlled way.

In my experience when a service/server is slow, a lot of streams will stall. Flow control and 'bound' memory are mostly needed when this case happens, so I think in practice when 'stallouts' start to happen there will be no extra memory. 

 


I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I'll be in vacation - but I want to repeat my proposal to deal with 'stalled' streams by dropping some frames.

This is not (just) some crazy idea, it has been used for few years in android. And IMHO it is simpler to implement 
on both sides than the proposed 'increase the buffer somehow'.

Where is it used in Android? Do you have statistics you can share?
 

It requires the sender to keep the frames it sends until it receives the window update (i.e. confirmation that they went trough).
A negative window would indicate that some frames have been dropped, and it needs to resend them.

Besides android, TCP is using 'dropped' frames/retransmit for flow control.

I think this proposal will address both 'bound memory' and simple enough handling of stalled streams. 


Costin

 


 

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
stream windows could be sized ~infinitely (so you wouldn't even need to
consider what BDP might be) and then reduced (with negative updates) to
some throttli
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 6/7/12 3:43 PM


On Thu, Jun 7, 2012 at 3:32 PM, William Chan (陈智昌) <will...@chromium.org> wrote:
On Thu, Jun 7, 2012 at 3:08 PM, Costin Manolache <cos...@gmail.com> wrote:
On Thu, Jun 7, 2012 at 9:44 AM, Mike Belshe <mbe...@chromium.org> wrote:

I think you're being squishy here :-)  On one hand, you claim victory for having a fixed server exposure of 500KB.  But, if you let that be static, then you can have total session stallouts.  So, in addition to having that clamp, implementors will need to be able to increase the exposure on-the-fly.  This means that the 500KB wasn't *really* the exposure to begin with.  But, it does allow servers to dynamically adjust in a conscious and controlled way.

In my experience when a service/server is slow, a lot of streams will stall. Flow control and 'bound' memory are mostly needed when this case happens, so I think in practice when 'stallouts' start to happen there will be no extra memory. 

 


I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I'll be in vacation - but I want to repeat my proposal to deal with 'stalled' streams by dropping some frames.

This is not (just) some crazy idea, it has been used for few years in android. And IMHO it is simpler to implement 
on both sides than the proposed 'increase the buffer somehow'.

Where is it used in Android? Do you have statistics you can share?

It is used in a slightly different way - messages are saved on disk, and it's not tied to a specific TCP connection ( TCP connection can go away at any time, things are a bit more brutal). This is part of the c2dm / talk. I don't think we have any public stats, but 
the protocol is similar - multiplexed streams, single TCP connection, etc. 

The retransmit is not actually intended for 'flow control' - but to deal with unreliable connections. My point is that re-transmitting 
frames is not as complex as it seems, and there are protocols where frames are routinely dropped ( but streams still flow, even
when the TCP connection itself is dropped ).

Costin

 
 

It requires the sender to keep the frames it sends until it receives the window update (i.e. confirmation that they went trough).
A negative window would indicate that some frames have been dropped, and it needs to resend them.

Besides android, TCP is using 'dropped' frames/retransmit for flow control.

I think this proposal will address both 'bound memory' and simple enough handling of stalled streams. 


Costin

 


 

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
st
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/7/12 3:48 PM
On Thu, Jun 7, 2012 at 5:08 PM, Costin Manolache <cos...@gmail.com> wrote:
On Thu, Jun 7, 2012 at 9:44 AM, Mike Belshe <mbe...@chromium.org> wrote:
I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I'll be in vacation - but I want to repeat my proposal to deal with 'stalled' streams by dropping some frames.

This is not (just) some crazy idea, it has been used for few years in android. And IMHO it is simpler to implement 
on both sides than the proposed 'increase the buffer somehow'.

It requires the sender to keep the frames it sends until it receives the window update (i.e. confirmation that they went trough).
A negative window would indicate that some frames have been dropped, and it needs to resend them.

This suffers from the same flaw as txon/txoff: it requires one endpoint to buffer at least BDP. Non-blocking servers that handle large numbers of concurrent requests cannot support this, so I am opposed to it.

Besides android, TCP is using 'dropped' frames/retransmit for flow control.

I think this proposal will address both 'bound memory' and simple enough handling of stalled streams. 


Costin

 


 

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
stream windows could be sized ~infinitely (so you wouldn't even need to
consider what BDP might be) and then reduced (with negative updates) to
some throttling value only when they started causing buffering on the
receiver. But I respect Roberto's operati
...
Re: [spdy-dev] Thinking about flow control Costin Manolache 6/7/12 5:15 PM


On Thu, Jun 7, 2012 at 3:48 PM, Alek Storm <alek....@gmail.com> wrote:
On Thu, Jun 7, 2012 at 5:08 PM, Costin Manolache <cos...@gmail.com> wrote:
On Thu, Jun 7, 2012 at 9:44 AM, Mike Belshe <mbe...@chromium.org> wrote:
I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I'll be in vacation - but I want to repeat my proposal to deal with 'stalled' streams by dropping some frames.

This is not (just) some crazy idea, it has been used for few years in android. And IMHO it is simpler to implement 
on both sides than the proposed 'increase the buffer somehow'.

It requires the sender to keep the frames it sends until it receives the window update (i.e. confirmation that they went trough).
A negative window would indicate that some frames have been dropped, and it needs to resend them.

This suffers from the same flaw as txon/txoff: it requires one endpoint to buffer at least BDP. Non-blocking servers that handle large numbers of concurrent requests cannot support this, so I am opposed to it.

Actually it require sender to buffer up to window size ( or how much they decide to send ), which may be larger than BDP. But they also have to buffer if the current flow control kicks in until they slow down the producer. 

Most senders already use some large buffers. It is also true there will be some duplication - there is also the TCP level buffering.
But it still seems better than RST-ing the whole stream as Mike suggests, or by magically increasing the buffer size on the receiver size when the outage happens. 


Costin

 

Besides android, TCP is using 'dropped' frames/retransmit for flow control.

I think this proposal will address both 'bound memory' and simple enough handling of stalled streams. 


Costin

 


 

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
stream windows could be sized ~infinitely (so you wouldn't even need to
consider what BDP might be) and then reduced (with
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/7/12 6:32 PM
On Thu, Jun 7, 2012 at 7:15 PM, Costin Manolache <cos...@gmail.com> wrote:
On Thu, Jun 7, 2012 at 3:48 PM, Alek Storm <alek....@gmail.com> wrote:
On Thu, Jun 7, 2012 at 5:08 PM, Costin Manolache <cos...@gmail.com> wrote:
On Thu, Jun 7, 2012 at 9:44 AM, Mike Belshe <mbe...@chromium.org> wrote:
I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I'll be in vacation - but I want to repeat my proposal to deal with 'stalled' streams by dropping some frames.

This is not (just) some crazy idea, it has been used for few years in android. And IMHO it is simpler to implement 
on both sides than the proposed 'increase the buffer somehow'.

It requires the sender to keep the frames it sends until it receives the window update (i.e. confirmation that they went trough).
A negative window would indicate that some frames have been dropped, and it needs to resend them.

This suffers from the same flaw as txon/txoff: it requires one endpoint to buffer at least BDP. Non-blocking servers that handle large numbers of concurrent requests cannot support this, so I am opposed to it.

Actually it require sender to buffer up to window size ( or how much they decide to send ), which may be larger than BDP.

Your scheme requires the server to buffer an amount of data equal to whatever the client sets the window size to, as I will now demonstrate. Consider a client that sets the window size to 10MB. As the server sends data, it cannot drain its outgoing buffers until it receives confirmation from the client that the data has been consumed - no matter how slowly it sends data. The client is free to wait until all 10MB has been sent before sending a window update - meaning the server needs a 10MB buffer.

But they also have to buffer if the current flow control kicks in until they slow down the producer.

That depends entirely on what kind of data is being sent. When the server becomes flow-controlled, if the data is being generated on the fly, it can pause that generation process. If it's being read from disk, it can simply stop reading. If the server is actually a reverse proxy, it can flow control the backend server. None of these scenarios requires much buffering on the server's part.

Alek

Most senders already use some large buffers. It is also true there will be some duplication - there is also the TCP level buffering.
But it still seems better than RST-ing the whole stream as Mike suggests, or by magically increasing the buffer size on the receiver size when the outage happens. 


Costin

 

Besides android, TCP is using 'dropped' frames/retransmit for flow control.

I think this proposal will address both 'bound memory' and simple enough handling of stalled streams. 


Costin

 


 

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/7/12 7:29 PM
On Thu, Jun 7, 2012 at 11:44 AM, Mike Belshe <mbe...@chromium.org> wrote:
I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I agree, which is why I think you should take another look at my proposal. Like yours, it does away with both session and stream windows, and adds only a simple mechanism to communicate the receiver's estimated consumption rate for each stream. With that information, the sender can schedule sending data frames for each stream so that HoL blocking is avoided. They can choose any algorithm to do this, and if a badly-behaved sender ignores this and sends too much data on a particular stream, the receiver can perform your favorite action: nuke it ;).

That's it. No window updates, no wanton stream killing, no latency penalty, no buffering requirements.

Advantages:
- Speed. Data is *always* being sent. Round trip delays are not periodically incurred, unlike per-stream window solutions.
- Simplicity. Nearly as simple as eliminating flow control altogether, but without the HoL blocking.

Disadvantages:
- None. Heck, I *challenge* anyone to come up with a disadvantage to this proposal. Please.

Alek

Note: This is entirely unrelated to my first proposal, which specified a round-robin scheme. This is much simpler and more flexible.

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true

stream windows could be sized ~infinitely (so you wouldn't even need to
consider what BDP might be) and then reduced (with negative updates) to
some throttling value only when they started causing buffering on the
receiver. But I respect Roberto's operational experience with a big
gateway and he hasn't been willing to
...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/7/12 11:35 PM


On Thu, Jun 7, 2012 at 7:29 PM, Alek Storm <alek....@gmail.com> wrote:
On Thu, Jun 7, 2012 at 11:44 AM, Mike Belshe <mbe...@chromium.org> wrote:
I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I agree, which is why I think you should take another look at my proposal.

I am searching for it; I do recall reading it, but I can't find it now - this thread is too massive.  Can you repost or point me at it?

thanks
mike


 
Like yours, it does away with both session and stream windows, and adds only a simple mechanism to communicate the receiver's estimated consumption rate for each stream. With that information, the sender can schedule sending data frames for each stream so that HoL blocking is avoided. They can choose any algorithm to do this, and if a badly-behaved sender ignores this and sends too much data on a particular stream, the receiver can perform your favorite action: nuke it ;).

That's it. No window updates, no wanton stream killing, no latency penalty, no buffering requirements.

Advantages:
- Speed. Data is *always* being sent. Round trip delays are not periodically incurred, unlike per-stream window solutions.
- Simplicity. Nearly as simple as eliminating flow control altogether, but without the HoL blocking.

Disadvantages:
- None. Heck, I *challenge* anyone to come up with a disadvantage to this proposal. Please.

Alek

Note: This is entirely unrelated to my first proposal, which specified a round-robin scheme. This is much simpler and more flexible.

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
stream windows could be sized ~infinitely (so you wouldn't even need to
consider what BDP might be) and then reduced (with negative updates) to
some throttling value only when they started causing buffering on the
receiver. But I respect Ro
...
Re: [spdy-dev] Thinking about flow control Alek Storm 6/7/12 11:48 PM
On Fri, Jun 8, 2012 at 1:35 AM, Mike Belshe <mbe...@chromium.org> wrote:
On Thu, Jun 7, 2012 at 7:29 PM, Alek Storm <alek....@gmail.com> wrote:
On Thu, Jun 7, 2012 at 11:44 AM, Mike Belshe <mbe...@chromium.org> wrote:
I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I agree, which is why I think you should take another look at my proposal.

I am searching for it; I do recall reading it, but I can't find it now - this thread is too massive.  Can you repost or point me at it?

I think we may have broken a few records :). The original post is at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/MhZfs1MBz6MJ, but I think the explanation in the email above is a better summary. No stream or session windows, just occasional updates sent from the receiver to the sender when consumption rates change. I've purposely left how this is serialized undefined for now, but I can elaborate if you'd like.

Alek

thanks
mike


 
Like yours, it does away with both session and stream windows, and adds only a simple mechanism to communicate the receiver's estimated consumption rate for each stream. With that information, the sender can schedule sending data frames for each stream so that HoL blocking is avoided. They can choose any algorithm to do this, and if a badly-behaved sender ignores this and sends too much data on a particular stream, the receiver can perform your favorite action: nuke it ;).

That's it. No window updates, no wanton stream killing, no latency penalty, no buffering requirements.

Advantages:
- Speed. Data is *always* being sent. Round trip delays are not periodically incurred, unlike per-stream window solutions.
- Simplicity. Nearly as simple as eliminating flow control altogether, but without the HoL blocking.

Disadvantages:
- None. Heck, I *challenge* anyone to come up with a disadvantage to this proposal. Please.

Alek

Note: This is entirely unrelated to my first proposal, which specified a round-robin scheme. This is much simpler and more flexible.

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
stream windows could be sized ~infinitely (so you wouldn't even need to
consider what BDP might be) and then reduced
...
Re: [spdy-dev] Thinking about flow control Mike Belshe 6/8/12 12:25 AM


On Thu, Jun 7, 2012 at 11:48 PM, Alek Storm <alek....@gmail.com> wrote:
On Fri, Jun 8, 2012 at 1:35 AM, Mike Belshe <mbe...@chromium.org> wrote:
On Thu, Jun 7, 2012 at 7:29 PM, Alek Storm <alek....@gmail.com> wrote:
On Thu, Jun 7, 2012 at 11:44 AM, Mike Belshe <mbe...@chromium.org> wrote:
I stand by my earlier claim that flow control is complicated.  Endpoints which fail to think about how to deal with at-throttle stalls will just be broken and stall.

Even Chrome forgot to expand its window size to infinity (like you did with FF!)....  This stuff is really subtle.

I agree, which is why I think you should take another look at my proposal.

I am searching for it; I do recall reading it, but I can't find it now - this thread is too massive.  Can you repost or point me at it?

I think we may have broken a few records :). The original post is at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/MhZfs1MBz6MJ, but I think the explanation in the email above is a better summary. No stream or session windows, just occasional updates sent from the receiver to the sender when consumption rates change. I've purposely left how this is serialized undefined for now, but I can elaborate if you'd like.

Oh.  I thought that was too vague to comment on so far.  Maybe you can provide more details (dare I ask for a separate thread? :-)

Mike


 

Alek

thanks
mike


 
Like yours, it does away with both session and stream windows, and adds only a simple mechanism to communicate the receiver's estimated consumption rate for each stream. With that information, the sender can schedule sending data frames for each stream so that HoL blocking is avoided. They can choose any algorithm to do this, and if a badly-behaved sender ignores this and sends too much data on a particular stream, the receiver can perform your favorite action: nuke it ;).

That's it. No window updates, no wanton stream killing, no latency penalty, no buffering requirements.

Advantages:
- Speed. Data is *always* being sent. Round trip delays are not periodically incurred, unlike per-stream window solutions.
- Simplicity. Nearly as simple as eliminating flow control altogether, but without the HoL blocking.

Disadvantages:
- None. Heck, I *challenge* anyone to come up with a disadvantage to this proposal. Please.

Alek

Note: This is entirely unrelated to my first proposal, which specified a round-robin scheme. This is much simpler and more flexible.

This might be considered burying the lede, but I personally think we
don't strictly need the session window if all receivers will simply sign
up to the reality that they need to be able to buffer a BDP worth of
data from every stream the same way it is in HTTP/1.

Its really a worst-case scenario.  TCP sockets don't even give receivers a lot of play here; if you muck with it manually, you increase latency.  So you had better let TCP use the sizes it wants.

For our streams, its quite unlikely that every stream is going to max-out BDP; we have lots of short streams.  
 
If that were true
stream windows could be sized ~infin
...
Re: [spdy-dev] Thinking about flow control Antonio Vicente 6/9/12 11:11 AM


On Wed, May 30, 2012 at 8:07 PM, Roberto Peon <fe...@google.com> wrote:
It is annoying, but we're doing multiplexing through proxies, and if we're serious about providing a reliable service through them (and I AM), then we need flow control.
I believe that proxies, both forward (mobile) and reverse (loadbalancers) will become more common as time progresses. Ensuring that they will work reliably seems important for the future of the protocol. Dropping the connection randomly, especially when we have little idea of the nature of the transaction, seems a poor choice. As Alek implies, it is an uncomfortable situation when you have to retry, and is definitely not work conserving.

As for what am proposing:

Keep the per-stream window, because we need it to avoid HOL blocking.
Add a per-tcp-connection window.
A sender can send a maximum of:
    min(stream_flow_control_window, per_connection_flow_control_window) bytes at any point in time.

I think I understood the interaction of per connection and per stream windows when we talked offline.
I thought what we were going for was:
  max_send = max(stream_flow_control_window, per_connection_flow_control_window)

This limit has 2 desirable properties that other schemes are missing:
  1. all streams can make progress independently because of stream_flow_control_window
  2. large uploads can get a performance boost by constraining themselves against per_connection_flow_control_window instead of stream_flow_control_window

We could keep stream_flow_control_window small, and make per_connection_flow_control_window reasonably large; but as mentioned elsewhere in the thread this is bait for clients creating multiple SPDY connections to one host.

Would a convention where we start with some somewhat small per-stream default that allows small posts to do their thing without round trips, and encouraging receivers to grow the window substantially once they have seen a syn_stream/syn_reply, possibly taking content-length into account, make people happy?  I personally don't have a problem allocating 1MB or more to a few streams as long as:
- I have the memory available.
- I can decide to grow windows at stream creation time or somewhat down the line as resource usage changes.
- Unused large allocations eventually timeout if not used to allow resource recovery when clients misbehave.  Larger allocations would come with shorter timeouts.

I hate the complexity of having endpoints track timeouts in addition to per-stream windows, so a likely implementation would just reset streams with large windows after some time if the sender hasn't made enough progress.

-antonio

Whenever the sender finds that it is restricted from sending by flow control (and only by flow control), then it should tell the other side so that the window can (possibly) grow.

-=R



On Wed, May 30, 2012 at 4:16 PM, Alek Storm <alek....@gmail.com> wrote:
On Wed, May 30, 2012 at 5:04 PM, Mike Belshe <mbe...@chromium.org> wrote:
I believe that we have a tradeoff of full-pipe performance vs buffering which the current SPDY spec makes.

I think Roberto is proposing something, but I'm not sure what it is.  I am very much against more complexity, because I believe the entire problem is 100% contrived and unreal - simply not worth the complexity.  The protocol can already deal with an over-buffer situation even without *any* flow control - just kill the stream.  (See below for justification).  I'd rather remove all flow control from SPDY than add more complexity.

So a stream can be killed halfway through transmitting a large amount of data? How will the sender know when it is safe to retransmit without the stream getting killed again? And they'll have to retransmit the entire block from the beginning - everything that was sent in the killed stream is lost. That sounds remarkably inefficient.

Justification:
a) The client isn't going to throttle the downlink - it wants data as fast as it can get it.

Absolutely not; see Patrick's examples (https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/-Hnjp94xjG4J) near the beginning of this thread. A lack of per-stream flow control would become even more of a problem as web applications become more media-rich. I believe clients would begin to compensate by opening multiple TCP connections - not for a greater share of the server's bandwidth, but for stream-specific flow control.

d) If your backend server is down causing backlogs in your proxy, you can write code to deal with that (e.g. failover) or nuke the stream.  Why expose it out to the whole protocol?

That doesn't help forward proxies, which don't have control over upstream servers (see Ryan's excellent explanation at https://groups.google.com/d/msg/spdy-dev/JB_aQPNI7rw/FGYat2VU22IJ). And I'm sure clients would not be pleased with repeatedly having their upload streams killed and restarting the upload from scratch because the proxy has no way to notify them of the size of its input buffers. With multiple downstream clients doing this at once, the proxy could become overwhelmed and unintentionally DoS'd.

Alek

Mike




On Wed, May 30, 2012 at 1:10 PM, Costin Manolache <cos...@gmail.com> wrote:
On Wed, May 30, 2012 at 12:13 PM, Roberto Peon <fe...@google.com> wrote:


On Wed, May 30, 2012 at 11:49 AM, Costin Manolache <cos...@gmail.com> wrote:


On Wed, May 30, 2012 at 10:43 AM, Roberto Peon <fe...@google.com> wrote:


On Wed, May 30, 2012 at 9:22 AM, Costin Manolache <cos...@gmail.com> wrote:


On Wed, May 30, 2012 at 3:47 AM, Simone Bordet <sbo...@intalio.com> wrote:
Hi,

On Wed, May 30, 2012 at 6:12 AM, Costin Manolache <cos...@gmail.com> wrote:
> One relatively easy solution - used on older versions of android - is to
> have the client hold to the data it sent, and the proxy or server to
> indicate how much was consumed, with negative numbers indicating that client
> needs to resend some data.
>
> For example you want to upload a 1M file, you start sending frames up to the
> window size ( say 128k ), but you don't delete/GC the frames you sent until
> you get the next window update from server. The window update will have an
> extra field indicating how much was consumed.

You don't want to send window updates until you're sure data has being
consumed by the application.

Why ? Window updates indicate there is space for more bytes in the buffers, not that the bytes have been consumed.

For any decent implementation, so long as the bytes in the buffers aren't blocking any other stream, this is good enough, and certainly no worse that TCP.
For a proxy, 'consumed by the application' translates to 'moved ingress bytes to egress bytes'.
 

 
Otherwise you're duplicating what the TCP ACK is saying, and it is of
no interest to the sender.

The problem is duplicating only part of TCP flow control. ACK is a part of flow control, just like the window update. TCP relies on packet drops and ACKs to determine what to send and how fast.

Even in HTTP the sender has to be able to deal with drops and re-transmits. The status code is a form of ACK, and plenty of problems have been caused by not dealing properly with drops and retries in http.

Bufferbloat is mentioned quite a bit - maybe we should look at ECN ( congestion notification ), which is the alternative to ACK and dropping packets.  

SPDY duplicates stuff from lower layers - multiplexing, a part of flow control.  It's likely to duplicate some of the problems and make other worse by not duplicating enough :-)

rexmits are a necessary part of TCP because of packet loss. We have a reliable transport that already does rexmit for us. We shouldn't need to reimplement that-- it is a fair bit of additional complexity and I believe that we don't need it to solve our problems.

"Packet loss" also means "dropped because of full buffers".
We also have a transport that does flow control - yet we are duplicating that ( in part - without the part that deals with congestion). 

Agreed. We're duplicating it because we'd be required to do infinite buffering at proxies without it. That problem is not being solved by the transport, unfortunately :/

My point is that the proposals I've seen are not _duplicating_ - just pick a subset. 

And I don't agree it 'requires infinite buffering' - it requires the same amount of buffering that HTTP would require, all other knobs being equal. 

 
 



 

In particular, the scheme I proposed earlier should address all of the issues we've brought up so far. Roughly, it is:

Assume:
   we have per-stream window sizes.
   we have per-connection window sizes.
  A sender can send up to (min(per-stream, per-connection)) bytes.

 
"a stream is blocked"  means that the sender for that stream:
  * can write to the socket (i.e. the socket is writable and there is space in the TCP egress buffers)
  * has no higher priority stream that is currently sending (and thus blocking this stream because of prioritization)
  * there are bytes to be sent on this stream.

The algorithm is then (pseudocode):

OnWritable(socket, stream_id):
  if (bytes_to send && socket_writable && clear_to_send_this_priority):
    max_window = min(connection_flow_control_window),
                              flow_control_window[stream_id]))
    bytes_sent = send(socket, bytes_to_send, min(bytes_to_send.len(), max_window))
    if (StillWritable(socket) && bytes_to_send.len() > max_window):
      SendBlockedFrame(socket, stream_id, bytes_to_send.len() - max_window)
      last_time_blocked[stream_id] = Now()

OnWindowUpdate(stream_id, window_update_frame):
  flow_control_window[stream_id] += window_update_frame.stream_update_size;
  connection_flow_control_window += window_update_frame.overall_update_size;
  
  // If we were blocked
  if (bytes_to_send.len() > 0 && last_time_blocked[stream_id] > 0):
    time_blocked = Now() - last_time_blocked[stream_id]
    SendUnblockedFrame(socket, stream_id, bytes_to_send.len(), time_blocked)
    max_window = min(connection_flow_control_window),
                              flow_control_window[stream_id]))   
    if max_window >= bytes_to_send.len():
      last_time_blocked[stream_id] = 0
    else:
      last_time_blocked[stream_id] = Now()
 
In natural language:
if a sender is ever blocked, then it should send a frame to the receiver indicating the stream ID which is blocked, with then amount of bytes it would wish to send, but couldn't because of flow-control.
When a sender receives a window update frame, it should indicate how many bytes are blocked and for how long

The receiver, upon receipt of such a frame, could increase the various window sizes as indicated by the frames which tell the receiver the number (and possible duration) of the blocked bytes (hopefully up to a maximum as estimated by the BDP).

Not sure I understand - you can't increase any window if the per-connection buffers are full. 

The sender has sent initial window of all the streams, up to filling the per connection window. There is no more space in the proxy ( maybe for control frames which are not subject to frame control). 

If the proxy has no more space, then noone should be sending more bytes and things are working properly.

They are not working properly - you may have higher priority streams that can't go trough, and 'bad' streams preventing good streams. Very similar with the buffer bloat, and for similar reasons. 

In contrast plain HTTP would work just fine in this situation - the bad streams will hit TCP flow control, the new streams will keep working. 

 
If the proxy has space in its buffers, it indicates such by increasing the per-connection window size.
If the proxy is blockage for a particular stream, it doesn't update the window size for that stream, but otherwise the per-stream window size should be the per-connection window size.
...
More topics »