Subject: [ledbat] random input

From: Mirja Kühlewind <[email-masked]>
Date: Wed, 16 Feb 2011 17:15:54 +0100

Hi,

I would like to remove the part about the random input from the draft. It 
might be helpful for LEDBAT if there actually is some variation in delay on 
link as this could cause the bottleneck queue to empty from time to time. If 
this would happen, all LEDBAT connections will be able to measure the real 
base delay. But adding some random delay factor when calculation the cwnd at 
the sender doesn't help to empty the queue at all. Is it okay to remove the 
random input part or does anybody have different results?

Actually, regarding the intra-protocol fairness issue. I wouldn't care too 
much about multiple LEDBAT's which will not share the capacity equally, as 
this was not one of the design goals (as already stated in the previous 
mail). But the other problem is that a LEDBAT that will never measure the 
true base delay, will add its own TARGET on top of the wrong base delay. In 
the worst case when the old LEDBAT connection is decreasing as fast as the 
new one is increasing,  the new LEDBAT will actually add double the TARGET. 
Maybe this is a case for having a higher GAIN value for the decrease...? But 
what's the right value here?

Mirja

---

From: Rolf Winter <[email-masked]>
Date: Thu, 17 Feb 2011 13:54:31 +0000

Hi,

<chair's hat off>

I think that it might be OK to remove random factor, especially as the delay measurement should add sufficient randomness. The draft currently recommend a random value of 0 anyway. Regarding the point about not being able to measure the real base delay, I guess the hope is that other (TCP/UDP) traffic will force all LEDBAT flows once in a while to back off completely, allowing all flows at some point to measure the true base delay.

Again, BitTorrent input would be helpful on this point.

Best,

Rolf

NEC Europe Limited | Registered Office: NEC House, 1 Victoria Road, London W3 6BL | Registered in England 2832014 

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Mirja Kühlewind
> Sent: Mittwoch, 16. Februar 2011 17:16
> To: [email-masked]
> Subject: [ledbat] random input
> 
> Hi,
> 
> _______________________________________________
> ledbat mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ledbat

---

From: "Woundy, Richard" <[email-masked]>
Date: Thu, 17 Feb 2011 19:07:50 +0000

> Again, BitTorrent input would be helpful on this point.

Agreed. But I should point out that this topic has been raised frequently in past face to face meetings.

Even if we remove the explicit random factor, can we at least summarize that at least some random fluctuation in base delay measurement is assumed?

Below are relevant minutes from the last three LEDBAT meetings.

>From http://www.ietf.org/proceedings/76/minutes/ledbat.txt:

Late comer's (non)-advantage
-----

Lars: implementation depends on side effects on user's operating system, and looks like only might work by serendipity. It seems to be just a hack that might not work all the time.

Slav: if your machine is so good, then you can introduce noise / random fluctuations in inter-packet transmission time.

Stewart: As world moves to flash disk, high-performance CPUs, timers are more and more precise. Cannot depend on the end system introducing random noise.

Murari: problem is non-existent on many systems.

Rich: Assumption about a backoff time is random. Need to clearly state expectation that things back off with a random component. The random component is an implementation detail. (ACTION)

Lars: Better to have something explicit in the document.

Slav: Need to flush queue to figure out RTT on second stream to really know.

Lars: That is too heavy weight (Slav clearly agrees)

Bob Briscoe: Late-comer's advantage: please add it to the draft as described on the list.  Disadvantage: late-comer does not know base delay. Advantage: if it does know base delay, other flows will not necessarily get out of the way of the new flow. Draft says randomness fixes this, but that means randomness needs to be ensured (ACTION)

Fairness
-----

Bob: Need to write down assumptions. Random walks with a lot of flows competing with each other; do not see how ones will a small amount of bandwidth will ever get large or vice versa. Need to state why randomness helps and importance of true randomness in the algorithm.  
(ACTION)

Andrew: randomness protocol adds needs an estimator to know what randomness is available so it knows how much randomness to add.

Bob: May be we see randomness in networks because today's protocols have randomness built in. If on a ledbat-only network, no randomness.  
E.g., data center

Slav: experience is randomness still there.

Stuart: every network does NOT have randomness. Slav: every network I have TRIED has randomness, but not necessarily true for all networks.  
Stuart: MacOS 8.6 (?) had this problem; throughput cut in half. No randomness, so everyone had the same collisions repeating.

Bob: just need to note this in spec.

>From http://www.ietf.org/proceedings/77/minutes/ledbat.txt:

Fairness
Lars: Measurements in Trilogy project is not enough, minutes may be needed to determine baseline delay measurement. Explicit randomization should help. 

Rolf Winter NEC:  An issue is one minute slots for base delay, with history of ten minutes. A long delay in a one minute slot will not be aged out until ten minutes. 

Stanislav: Clarification, inserts small random (zero mean) values to delay which changes amount of capacity that is distributed to other flows. Paramter should be related to the target. 

>From http://www.ietf.org/proceedings/79/minutes/ledbat.txt:

SC - we don't need to agonise too much about fairness - apps that are using this have already made a decision to play nice

RoW - not sure I agree - competing apps in the same space may have motivations to try to deliver better performance by increasing the base delay very slightly. this should be discussed in the draft.

Random reshuffling for fairness slide

RoW - have results that demonstrate latecomer advantage

SC - Stas Shalunov (SS) asserted that OS scheduler would give enough randomness, I asked how much randomness was needed, didn't get a response. Don't hold up the document for this, if we don't have a firm answer then leave text vague 'some amount of randomness is believed to help'

LE - people implementing this should experiment with this. does adding more entropy improve behaviour they observe? this might be an improvement but we really don't know and we need someone to tell us.

MS - don't know if BitTorrent do this in their implementation today

SC - quite certain they don't as SS asserted that entropy of OS scheduling would deal with this. But it won't if we're talking about MacOSX.

MS - if you have few connections then the synch problem seems real, but we don't have data.

-- Rich

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Rolf Winter
Sent: Thursday, February 17, 2011 8:55 AM
To: Mirja Kühlewind; [email-masked]
Subject: Re: [ledbat] random input

Hi,

<chair's hat off>

Best,

Rolf

---

From: Mirja Kuehlewind <[email-masked]>
Date: Fri, 18 Feb 2011 13:19:16 +0100

Those minutes show exactly the point. As Stas said "random fluctuations in 
inter-packet transmission time" is needed. But the random factor in the draft 
doesn't bring any randomness for the inter-packet transmission times!

On Thursday 17 February 2011 20:07:50 Woundy, Richard wrote:
> Even if we remove the explicit random factor, can we at least summarize
> that at least some random fluctuation in base delay measurement is assumed?
>
> Lars: implementation depends on side effects on user's operating system,
> and looks like only might work by serendipity. It seems to be just a hack
> that might not work all the time.
>
> Slav: if your machine is so good, then you can introduce noise / random
> fluctuations in inter-packet transmission time.
>
> Stewart: As world moves to flash disk, high-performance CPUs, timers are
> more and more precise. Cannot depend on the end system introducing random
> noise.
>
> Rich: Assumption about a backoff time is random. Need to clearly state
> expectation that things back off with a random component. The random
> component is an implementation detail. (ACTION)
>
> Bob Briscoe: Late-comer's advantage: please add it to the draft as
> described on the list.  Disadvantage: late-comer does not know base delay.
> Advantage: if it does know base delay, other flows will not necessarily get
> out of the way of the new flow. Draft says randomness fixes this, but that
> means randomness needs to be ensured (ACTION)
>
> Fairness
> -----
>
> Bob: Need to write down assumptions. Random walks with a lot of flows
> competing with each other; do not see how ones will a small amount of
> bandwidth will ever get large or vice versa. Need to state why randomness
> helps and importance of true randomness in the algorithm. (ACTION)
>
> Andrew: randomness protocol adds needs an estimator to know what randomness
> is available so it knows how much randomness to add.
>
> Bob: May be we see randomness in networks because today's protocols have
> randomness built in. If on a ledbat-only network, no randomness. E.g., data
> center
>
> Stuart: every network does NOT have randomness. Slav: every network I have
> TRIED has randomness, but not necessarily true for all networks. Stuart:
> MacOS 8.6 (?) had this problem; throughput cut in half. No randomness, so
> everyone had the same collisions repeating.
>
> Lars: Measurements in Trilogy project is not enough, minutes may be needed
> to determine baseline delay measurement. Explicit randomization should
> help.
>
> Rolf Winter NEC:  An issue is one minute slots for base delay, with history
> of ten minutes. A long delay in a one minute slot will not be aged out
> until ten minutes.
>
> Stanislav: Clarification, inserts small random (zero mean) values to delay
> which changes amount of capacity that is distributed to other flows.
> Paramter should be related to the target.
>
> SC - we don't need to agonise too much about fairness - apps that are using
> this have already made a decision to play nice
>
> RoW - not sure I agree - competing apps in the same space may have
> motivations to try to deliver better performance by increasing the base
> delay very slightly. this should be discussed in the draft.
>
> SC - Stas Shalunov (SS) asserted that OS scheduler would give enough
> randomness, I asked how much randomness was needed, didn't get a response.
> Don't hold up the document for this, if we don't have a firm answer then
> leave text vague 'some amount of randomness is believed to help'
>
> LE - people implementing this should experiment with this. does adding more
> entropy improve behaviour they observe? this might be an improvement but we
> really don't know and we need someone to tell us.
>
> SC - quite certain they don't as SS asserted that entropy of OS scheduling
> would deal with this. But it won't if we're talking about MacOSX.
>
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Rolf Winter Sent: Thursday, February 17, 2011 8:55 AM
> I think that it might be OK to remove random factor, especially as the
> delay measurement should add sufficient randomness. The draft currently
> recommend a random value of 0 anyway. Regarding the point about not being
> able to measure the real base delay, I guess the hope is that other
> (TCP/UDP) traffic will force all LEDBAT flows once in a while to back off
> completely, allowing all flows at some point to measure the true base
> delay.
>

-- 
-------------------------------------------------------------------
Dipl.-Ing. Mirja Kühlewind
Institute of Communication Networks and Computer Engineering (IKR)
University of Stuttgart, Germany
Pfaffenwaldring 47, D-70569 Stuttgart

tel: +49(0)711/685-67973
email: [email-masked]
web: www.ikr.uni-stuttgart.de
-------------------------------------------------------------------

---

From: "Woundy, Richard" <[email-masked]>
Date: Fri, 18 Feb 2011 16:08:26 +0000

Mirja,

The current text has:

    off_target = TARGET - queuing_delay + random_input()
    cwnd += GAIN * off_target / cwnd

and

   random_input()
     # random() is a PRNG between 0.0 and 1.0
     # NB: RANDOMNESS_AMOUNT is normally 0
     RANDOMNESS_AMOUNT * TARGET * ((random() - 0.5)*2)

Are you suggesting to delete "random_input()" entirely?

Or do you want to change the definition of random_input() to a set of comments that says 'some amount of randomness is believed to help' and 'there may be sufficient randomness in some environments'?

Or do you want to change the effect of GAIN on cwnd?

-- Rich

-----Original Message-----
From: Mirja Kuehlewind [mailto:[email-masked]] 
Sent: Friday, February 18, 2011 7:19 AM
To: Woundy, Richard
Cc: Rolf Winter; [email-masked]
Subject: Re: [ledbat] random input

tel: +49(0)711/685-67973

---

From: Mirja Kuehlewind <[email-masked]>
Date: Fri, 18 Feb 2011 17:20:09 +0100

I want to delete random_input() from the pseudo code and add/extend an section 
(probably in 5.3 Fairness between LEDBAT flows) to say  'some amount of 
randomness is believed to help' and 'there may be sufficient randomness in 
some environments'. 

I'm afraid that was not completely one of your three given options, but does 
this work for you?

If someone has some more experience on how much randomness can be found in 
real systems, I would be happy about additional information or even a piece 
of text as contribution for the draft!

On Friday 18 February 2011 17:08:26 Woundy, Richard wrote:
> Or do you want to change the definition of random_input() to a set of
> comments that says 'some amount of randomness is believed to help' and
> 'there may be sufficient randomness in some environments'?
>
> inter-packet transmission time" is needed. But the random factor in the
> draft doesn't bring any randomness for the inter-packet transmission times!
>
> > described on the list.  Disadvantage: late-comer does not know base
> > delay. Advantage: if it does know base delay, other flows will not
> > necessarily get out of the way of the new flow. Draft says randomness
> > fixes this, but that means randomness needs to be ensured (ACTION)
> >
> > Fairness
> > -----
> >
> > Andrew: randomness protocol adds needs an estimator to know what
> > randomness is available so it knows how much randomness to add.
> >
> > randomness built in. If on a ledbat-only network, no randomness. E.g.,
> > data center
> >
> > Stuart: every network does NOT have randomness. Slav: every network I
> > have TRIED has randomness, but not necessarily true for all networks.
> > Stuart: MacOS 8.6 (?) had this problem; throughput cut in half. No
> > randomness, so everyone had the same collisions repeating.
> >
> > Lars: Measurements in Trilogy project is not enough, minutes may be
> > needed to determine baseline delay measurement. Explicit randomization
> > should help.
> >
> > Rolf Winter NEC:  An issue is one minute slots for base delay, with
> > history of ten minutes. A long delay in a one minute slot will not be
> > aged out until ten minutes.
> >
> > Stanislav: Clarification, inserts small random (zero mean) values to
> > delay which changes amount of capacity that is distributed to other
> > flows. Paramter should be related to the target.
> >
> > SC - we don't need to agonise too much about fairness - apps that are
> > using this have already made a decision to play nice
> >
> > randomness, I asked how much randomness was needed, didn't get a
> > response. Don't hold up the document for this, if we don't have a firm
> > answer then leave text vague 'some amount of randomness is believed to
> > help'
> >
> > LE - people implementing this should experiment with this. does adding
> > more entropy improve behaviour they observe? this might be an improvement
> > but we really don't know and we need someone to tell us.
> >
> > SC - quite certain they don't as SS asserted that entropy of OS
> > scheduling would deal with this. But it won't if we're talking about
> > MacOSX.
> >
> > From: [email-masked] [mailto:[email-masked]] On Behalf
> > Of Rolf Winter Sent: Thursday, February 17, 2011 8:55 AM
> > NEC Europe Limited | Registered Office: NEC House, 1 Victoria Road,
> > London W3 6BL | Registered in England 2832014
> >

tel: +49(0)711/685-67973

---

From: "Woundy, Richard" <[email-masked]>
Date: Fri, 18 Feb 2011 18:50:28 +0000

this work for you?

Could you also add a comment somewhere within the algorithm in 3.4.2 that says something to this effect?

# See section 5.3 for a discussion of how randomness is assumed in the calculation above.

> If someone has some more experience on how much randomness can be found in real systems, I would be happy about additional information or even a piece of text as contribution for the draft!

Unfortunately I don't have personal knowledge. But the conversation below (from the IETF76 minutes) among Murari Sridharan (Microsoft), Stuart Cheshire (Apple) and Stanislav Shalunov (BitTorrent) seems instructive -- that is, many environments have some amount of 'randomness' due to operating system details (e.g. process/thread scheduling and/or less precise timers) and/or the use of hard disk drives (e.g. rotational delays at 'random' times).

Stuart points out that recent MacOS versions may not have these same random side-effects, and that has caused throughput issues in the past. Also, hard disk drives are being slowly replaced by solid state drives without rotational delays (or moving parts in general).

> > [Stuart]: As world moves to flash disk, high-performance CPUs, timers are
...
> > randomness, so everyone had the same collisions repeating.

I wonder if we'll get any more detailed guidance than that?

-- Rich

-----Original Message-----
From: Mirja Kuehlewind [mailto:[email-masked]] 
Sent: Friday, February 18, 2011 11:20 AM
To: Woundy, Richard
Cc: Rolf Winter; [email-masked]
Subject: Re: [ledbat] random input

tel: +49(0)711/685-67973

---

From: Rolf Winter <[email-masked]>
Date: Wed, 23 Feb 2011 15:50:31 +0000

Hi,

this sounds we have a workable way forward? Are there other comments on the issue of randomness?

Best,

Rolf

> From: Woundy, Richard [mailto:[email-masked]]
> Sent: Freitag, 18. Februar 2011 19:50
> To: Mirja Kuehlewind
> Subject: RE: [ledbat] random input
> 
> > If someone has some more experience on how much randomness can be
> found in real systems, I would be happy about additional information or
> even a piece of text as contribution for the draft!
> 
> Unfortunately I don't have personal knowledge. But the conversation
> below (from the IETF76 minutes) among Murari Sridharan (Microsoft),
> Stuart Cheshire (Apple) and Stanislav Shalunov (BitTorrent) seems
> instructive -- that is, many environments have some amount of
> 'randomness' due to operating system details (e.g. process/thread
> scheduling and/or less precise timers) and/or the use of hard disk
> drives (e.g. rotational delays at 'random' times).
> 
> Stuart points out that recent MacOS versions may not have these same
> random side-effects, and that has caused throughput issues in the past.
> Also, hard disk drives are being slowly replaced by solid state drives
> without rotational delays (or moving parts in general).
> 
> > > Agreed. But I should point out that this topic has been raised
> frequently
> > > in past face to face meetings.
> > >
> > > Slav: Need to flush queue to figure out RTT on second stream to
> really
> > > know.
> > >
> > > MS - if you have few connections then the synch problem seems real,
> but
> > > we don't have data.
> > >
> > > -- Rich
> > >
> Behalf
> > > > I would like to remove the part about the random input from the
> draft.
> > > > It
> > > > might be helpful for LEDBAT if there actually is some variation
> in
> > > > delay on
> > > > link as this could cause the bottleneck queue to empty from time
> to
> > > > time. If
> > > > this would happen, all LEDBAT connections will be able to measure
> the
> > > > real
> > > > base delay. But adding some random delay factor when calculation
> the
> > > > cwnd at
> > > > the sender doesn't help to empty the queue at all. Is it okay to
> remove
> > > > the
> > > > Actually, regarding the intra-protocol fairness issue. I wouldn't
> care
> > > > too
> > > > much about multiple LEDBAT's which will not share the capacity
> equally,
> > > > as
> > > > mail). But the other problem is that a LEDBAT that will never
> measure
> > > > the
> > > > the worst case when the old LEDBAT connection is decreasing as
> fast as
> > > > the
> > > > new one is increasing,  the new LEDBAT will actually add double
> the
> > > > TARGET.