Re: [iccrg] LEDBAT++, rLEDBAT, and slowdowns

[Neal Cardwell <[e-mail]>]

On Mon, Sep 9, 2019 at 4:35 AM marcelo bagnulo braun <[e-mail]>
wrote:

> Hi Neal,
>
> Thanks for the explanation. I can see now that uncoordinated slow downs
> is not enough to provide a bounded delay.
> I have an additional question related to this, that maybe you can
> provide some insight.
> Some papers, like [1], have proposed an AIMD variation of LEDBAT to
> achieve interledbat fairness. Since laedbat late comer advantage is
> essentially the problem of a late comer misestimating the base delay,
> and bloating the queueing delay, seems essentially the same problem. So
> the question is wouldnt AIMD solve the problem? I mean, wouldnt AIMD
> provide fairness and keep the queueing delay added by the ledbat flows
> bounded as well?
>

I'm pretty sure AIMD by itself would not solve the problem of unbounded
queuing delay for LEDBAT.

AIMD can increase fairness. But with enough flows the multiplicative
decrease aspect of AIMD, if it is uncoordinated, will fail to drain the
bottleneck queue, and thus will allow the queuing delays and base delay
estimates to keep ratcheting upward.

neal



> Thanks, marcelo
>
>
> El 06/09/19 a las 17:25, Neal Cardwell escribió:
> > However, if we apply the slowdown described in LEDBAT++
> >> (unsynchronized), then f1 would reduce its window and because f1 is the
> >> one expelling the other flows out, this would allow f1 to have a more
> >> accurate measure of the base delay, enabling the AIMD fairness to kick
> >> in and preventing the increase of the queueing delay.
> > As noted above, if the fair share of inflight data is less than the
> > standing queue, when f1 reduces its window it will not drain the queue
> > fully, so its base delay estimate will ratchet up to a value that
> > includes the queueing delay from all the other flows queued at
> > the bottleneck, even if all the others are LEDBAT++ flows.
> >
> >
> >> In summary, because errors in estimating the queuing delay causes one
> >> flow to grow more than the others, when this particular flow slows down,
> >> will allow a more accurate measure of the base delay, enabling AIMD
> >> fairness mechanisms to reconverge to a fair split.
> >>
> >> So, I am not convinced that it is not enough with the slow down proposed
> >> in LEDBAT++.
> > When you say a slow-down "will allow a more accurate measure of the
> > base delay," I think a key question is: more accurate than what, exactly?
> > An uncoordinated slow-down will allow a more accurate measure
> > of the base delay than the most recent RTT samples, but it will not
> > allow a measure that is more accurate than (or even matching)
> > the current base delay estimate.That's because uncoordinated
> > slow-downs can cause feedback loops, where flows measure
> > ever-increasing RTTs from the queues created by other flows
> > that are also unable to "anchor" their base delay estimates, so
> > are also allowing ever-increasing amounts of data in flight.
> >
> >> I am not sure this is true for all combinations of parameter values, i
> >> need to look into this.
> > Yes, I think further testing of LEDBAT++/rLEDBAT in multi-flow scenarios
> > would be worthwhile.
> >
> > A simple scenario that should illustrate this issue:
> >   o RTT of 100ms
> >   o bottleneck with 10*BDP of buffer space (allowing 1 sec of queuing)
> >   o 3 bulk LEDBAT++/rLEDBAT flows
> >
> > Per the dynamics discussed above, my theory is that in such a scenario
> > the queuing delay will grow until the buffer is oscillating near full and
> > there is ~1sec of queuing in the steady state. That is, rather than
> > "Low Extra Delay" there will be 1sec of extra delay. :-)
> >
> > best,
> > neal
> >
>
>