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

[Neal Cardwell <[e-mail]>]

On Wed, Sep 4, 2019 at 6:15 AM marcelo bagnulo braun <[e-mail]> wrote:
>
> Apologies for replying to my own email, but i would like to take
> something back, see below...
>
> El 03/09/19 a las 17:57, marcelo bagnulo braun escribió:
> > I guess what I'm trying to get at is that:
> >>
> >> (1) AFAICT the LEDBAT++ and rLEDBAT algorithms so far do not seem to
> >> provide a bound on "the additional queueing delay added by the LEDBAT
> >> flow", in the case where there are several  LEDBAT++/rLEDBAT flows and
> >> the fair share of in-flight data is less than the queue depth.
> >> Instead, the group dynamics would be such that the queue would
> >> gradually but steadily ratchet up until the buffer is full. This does
> >> not seem to meet the goals expressed in RFC6817 ("limiting the
> >> consequent increase in queueing delay on that path...avoiding
> >> interference with the network performance of competing flows") or the
> >> LEDBAT++/rLEDBAT drafts.
> >
> >
> > right, the additional queueing delay added by a single flow is
> > bounded, but if you keep on adding LEDBAT flows one after the other,
> > the total added queuing delay is not bounded indeed.
>
> Let me take this back.
>
> So, let's consider how would this situation you describe would happen.
>
> The scenario that I have been able to identify where this would happen
> would be for example the following.
>
> We have two LEDBAT++ flows (let's assume there is no other traffic for now).
>
> They have managed to accurately measure the base delay and thus they are
> fairly sharing the bottleneck link and inducing half of the target delay
> each.
>
> After n minutes, there is one of the flows (f1) that forgets the oldest
> minute of history, the one that contained the accurate measurement of
> the base delay.
>
> This implies that it will now record as base delay the minimum delay
> observed in the AIMD process, which is the one caused by both flows
> having half of the maximum window (I am assuming both flows are
> synchronized).
>
> The first consequence of this is that flow f1 will take a larger share
> of the bottleneck capacity.
>
> In any case, when the queuing delay measured by f1 is larger than the
> target, f1 will reduce its window to half. Depending on the relationship
> between the target delay and the real base delay, it is possible that
> when f1 reduces it window in half, the resulting delay is still larger
> than its current minimum, resulting in the increase of the queueing
> delay that you mentioned. Since this happens every n minutes,this can
> cause the queueing delay to grow unbounded.
>
> Is this the type of scenario you had in mind?

Yes, that is the type of scenario I had in mind.

Basically, if the fair share of inflight data is less than the standing queue,
then having a single flow cut its inflight will not drain the queue, and thus
no single flow can reveal the true two-way propagation delay by itself.

So an algorithm that relies on a windowed min_rtt estimate and individual
flows cutting by themselves will gradually ratchet up the level of queuing,
causing the queuing delay to grow without bounds.

> 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