Subject: Re: [ledbat] fairness between competing delay flows in draft-shalunov-ledbat-congestion-00.txt

From: Murari Sridharan <[email-masked]>
Date: Mon, 1 Jun 2009 08:04:43 -0700

Bob i think you are raising some very valid points here, Stas would be great if you can respond to his mail, havent seen one yet. 

Bob, If i understand you correctly CTCP does somethign like this, there is a seperate window increase process and there is a delay threshold (as measured through gamma which is the packets backlogged) which is used simply as a thresold to decrease if exceeded.  Low priority TCP which is "a" ledbat type solution that we are looking at for some of our scenarios. Even though it doesnt have an explicit delay target it tries to detect change in slope and adjusts the receive window to throttle the sender. It does aim to maintain a lower delay and does so well in our experiments but there is no explicit delay target. I am trying out a simple variant where the receiver measures the backlog using a vegas style equation with rcvwnd instead of cwnd to see if we can keep a certain amount of packets backlogged thereby doing somethign liek what you describe below. Will keep the list posted on the findings. The main difference though is that low priority TCP does infact relyon RTT and not one-way delay so reverse path congestion could affect this. The advantage is it works as an alternative congestion control option on regular TCP and only one end needs to change, both of which are very compelling. 

Regarding getting a good delay measurement that is indeed what we observed with CTCP over production links. However in the case of CTCP we did a lot of testing on high-speed links and there was enough statistical multiplexing and we almost always got a good base delay measurement. In the case when the bottleneck is a home link and there are multiple ledbat flows within the home the first movers advantage that Doug mentions is indeed possible. In Stas' experiments I am not sure if he had multiple ledbat flows within the home from different computers and if he saw this problem or not. 

At this point it would be great if some folks in the DL can try out a NS version of the algorithm, its simple and straightforward to implement and we can then study different aspects being discussed below. Stas do you have some results you can share, would be great to see how some of the dynamics below work in practice. 

Thanks
________________________________________
From: [email-masked] [[email-masked]] On Behalf Of Bob Briscoe [[email-masked]]
Sent: Thursday, April 09, 2009 5:50 AM
To: Stanislav Shalunov
Cc: Douglas Leith; [email-masked]
Subject: Re: [ledbat] fairness between competing delay flows in draft-shalunov-ledbat-congestion-00.txt

Stas,

Point taken about base measurements, but this questions is about the
motivation for the core part of the control algo:
         cwnd += GAIN * off_target / cwnd. (using the draft's
terminology: off_target = TARGET - queuing_delay)
Q. Why should the controller's increase and decrease both depend on
the same formula?

I think this means the shares that competing flows get depend purely
on the minutiae of the dynamics of each competing flow. That means
shares depend on arbitrary stuff that sharing shouldn't depend on
(e.g. whether disk heads move, how many other interrupts are served,
who arrived first), and there's nothing explicit to control what the
shares do depend on. However, I assume I must have missed something,
as I'm sure you've thought of this.

As far as I can work out (haven't had time to work through the
non-linear case where the small standing queue might disappear
completely), shares don't explicitly depend on RTT or packet size or
delayed ack factor (which IMHO they shouldn't). While both the
acceleration and deceleration of each flow do depend on these factors
in equal measures (which IMHO they should too). So far so good, but...

...taking RTT as one example, altho the steady state shares won't
depend directly on RTT, they might depend on second order effects of
how differences in RTT interact with other random events. If correct,
that's not good. It's random.

Put another way, repeating the question in my earlier posting:
Q. Why should the controller aim to *increase* delay up to the target?

Instead the window *increase* could operate as a separate continuous
process (as in AIMD algos). And the threshold only indicates a
*decrease* is needed if exceeded. Then bottleneck sharing is
explicitly under control. It is the equilibrium when the two
decoupled increase & decrease processes balance. 'TARGET' then
becomes merely a lower threshold for the decrease process, not a
target for both processes.

Bob

At 07:29 03/04/2009, Stanislav Shalunov wrote:
>We have not observed the late-comer's advantage.
>
>As soon as the first flow has a hiccup (for example, because something
>needs to wait for a few disk head moves), there will be a gap in the
>first flow's traffic, enabling the second flow to measure accurately.
>
>During the session Murari mentioned that in their experience, flows
>were also always able to get a reasonable base delay measurement.
>
>Obviously, the more flows, the more uniform the traffic, the more
>likely it is that the late comers might be mistaken about the base.
>At tens of flows, this is clearly not a problem.  At tens of
>thousands, which is what most backbones see for bulk connections, I'd
>expect it to start showing.  The coordination problem at tens of
>thousands of connections is hard and almost certain to be emergent,
>but then extended congestion on backbone links is infrequent.  In the
>worst case, it'll all fall back to TCP.
>
>For a small number of flows, the situation most typically encountered
>on congested links, base estimation seems to be reliable.
>
>
>On Tue, Mar 31, 2009 at 5:23 PM, Douglas Leith <[email-masked]> wrote:
> > Can I ask what the expected/desired behaviour will be when two or more
> > ledbat flows share a link ?
> > For example, say a first flow starts, ramps us cwnd until it hits
> the target
> > queueing delay and then a second ledbat flow starts a while later.  Its not
> > clear to me from the ID how the first flow would alter its cwnd to make
> > space for the second ledbat flow (especially if the second flow
> does not use
> > slow start, or perhaps has an early exit from slow start).
> > Also, is there a danger that, similarly the vegas and related algorithms,
> > the later starting flow will have difficulty getting an accurate
> estimate of
> > the base RTT since earlier starting flows maintain a standing queue ?
> > Doug
> > www.hamilton.ie
>
>
>
>--
>Stanislav Shalunov
>BitTorrent Inc
>[email-masked]
>
>personal: http://shlang.com
>_______________________________________________
>ledbat mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/ledbat

________________________________________________________________
Bob Briscoe,               Networks Research Centre, BT Research

_______________________________________________
ledbat mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/ledbat

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 02 Jun 2009 08:08:13 +0100

Murari,

I think one thing in Stas's mind (reading between the lines of a 
conversation I had with him at the Dublin IETF) was that an AIMD 
process like we're describing leads delay to increase with no. of 
LEDBAT flows. Whereas the linear controller in his draft makes sure 
you get about the same delay however many flows.

However, that might be at the expense of some flows randomly getting 
much less than others. Stas's comments in the SF LEDBAT meeting could 
be construed as implying that in practice randomness seems to lead to 
all flows getting some decent share. However, I don't quite see how, 
as the algorithm seems to have no tendency to make this happen - it 
seems more likely Doug's first-mover advantage will dominate.

Stas?

Bob

At 16:04 01/06/2009, Murari Sridharan wrote:
>Bob i think you are raising some very valid points here, Stas would 
>be great if you can respond to his mail, havent seen one yet.
>
>Bob, If i understand you correctly CTCP does somethign like this, 
>there is a seperate window increase process and there is a delay 
>threshold (as measured through gamma which is the packets 
>backlogged) which is used simply as a thresold to decrease if 
>exceeded.  Low priority TCP which is "a" ledbat type solution that 
>we are looking at for some of our scenarios. Even though it doesnt 
>have an explicit delay target it tries to detect change in slope and 
>adjusts the receive window to throttle the sender. It does aim to 
>maintain a lower delay and does so well in our experiments but there 
>is no explicit delay target. I am trying out a simple variant where 
>the receiver measures the backlog using a vegas style equation with 
>rcvwnd instead of cwnd to see if we can keep a certain amount of 
>packets backlogged thereby doing somethign liek what you describe 
>below. Will keep the list posted on the findings. The main 
>difference though is that low priority TCP does infact relyon RTT 
>and not one-way delay so reverse path congestion could affect this. 
>The advantage is it works as an alternative congestion control 
>option on regular TCP and only one end needs to change, both of 
>which are very compelling.
>
>Regarding getting a good delay measurement that is indeed what we 
>observed with CTCP over production links. However in the case of 
>CTCP we did a lot of testing on high-speed links and there was 
>enough statistical multiplexing and we almost always got a good base 
>delay measurement. In the case when the bottleneck is a home link 
>and there are multiple ledbat flows within the home the first movers 
>advantage that Doug mentions is indeed possible. In Stas' 
>experiments I am not sure if he had multiple ledbat flows within the 
>home from different computers and if he saw this problem or not.
>
>At this point it would be great if some folks in the DL can try out 
>a NS version of the algorithm, its simple and straightforward to 
>implement and we can then study different aspects being discussed 
>below. Stas do you have some results you can share, would be great 
>to see how some of the dynamics below work in practice.
>
>Thanks

---

From: Murari Sridharan <[email-masked]>
Date: Tue, 16 Jun 2009 11:48:39 -0700

Stas, any updates on this? we are getting close and it would be best to address some of the key concerns so we can take a call on the mailing list on making this a WG item. 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Murari Sridharan
Sent: Monday, June 01, 2009 8:05 AM
To: Bob Briscoe; Stanislav Shalunov
Cc: Douglas Leith; [email-masked]
Subject: Re: [ledbat] fairness between competing delay flows in draft-shalunov-ledbat-congestion-00.txt

Bob, If i understand you correctly CTCP does somethign like this, there is a seperate window increase process and there is a delay threshold (as measured through gamma which is the packets backlogged) which is used simply as a thresold to decrease if exceeded.  Low priority TCP which is "a" ledbat type solution that we are looking at for some of our scenarios. Even though it doesnt have an explicit delay target it tries to detect change in slope and adjusts the receive window to throttle the sender. It does aim to maintain a lower delay and does so well in our experiments but there is no explicit delay target. I am trying out a simple variant where the receiver measures the backlog using a vegas style equation with rcvwnd instead of cwnd to see if we can keep a certain amount of packets backlogged thereby doing somethign liek what you describe below. Will keep the list posted on the findings. The main difference though is that low priority TCP does infact relyon RTT and not o
 ne-way delay so reverse path congestion could affect this. The advantage is it works as an alternative congestion control option on regular TCP and only one end needs to change, both of which are very compelling. 

Thanks

Stas,

Bob