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

[Praveen Balasubramanian <[e-mail]>]

Thanks for the feedback Neal, Matt and Marcelo.



LEDBAT++ does not make any guarantees that it will measure the base delay accurately. The base delay referred to here and in original LEDBAT is as measured by the flow. The original LEDBAT claims that random stalls will create an opportunity to observe the base delay. With LEDBAT++ the flows themselves add explicit effort to create such stalls. It will also be hard to maintain the property of 90% throughput perf target of standard TCP (in absence of contention) if there are too many slowdown periods. Maybe the slowdown entry could be triggered by a new minRTT measurement as well as throttled by the 90% heuristic of LEDBAT++.



In practice we don’t see the ratcheting effect to be pronounced. Initial measurements on large number of flows show that the queuing delay goes past 100 msec only when there are more than 500 LEDBAT++ flows contending. We need to dig into this more to understand why. But PROBE_RTT like mechanism is something certainly worth experimenting with in the future. And if the results look good we’d be happy to incorporate it into LEDBAT++.

From: Matt Mathis <[e-mail]>
Sent: Friday, September 6, 2019 5:06 PM
To: marcelo bagnulo braun <[e-mail]>; Praveen Balasubramanian <[e-mail]>
Cc: iccrg IRTF list <[e-mail]>; Neal Cardwell <ncardwell=[e-mail]>; Yuchung Cheng <[e-mail]>
Subject: Re: [iccrg] LEDBAT++, rLEDBAT, and slowdowns

Adding to Neal's points: a robust distributed algorithm for each flow to compute is own minRTT is a known hard problem, going back a long long way.  I believe that it is the essence of the proof in "Flow Control Power is Nondecentralizable" [1] because no flow can tell if its observed min RTT includes other flows' standing queue.   BBR minimizes this problem by explicitly trying to globally synchronize minRTT measurements, which is demonstrably good enough for known cases.  If you can do better, please share and we can consider porting your algorithm to BBR, if you can't do better, please consider adopting the exact algorithm in BBR, so we can all synchronize the minRTT measurements.

BTW To the extent that the proof in [1] applies to BBR, it implies that the min RTT algorithm in BBR is also subject to pathological behavior under some unknown conditions.  Yes I do fret about this from time to time, but no I haven't found an example.  "Global synchronization" is hard, so the most likely failure modes look like strong regional synchronizations in different phases, and flows that traverse multiple regions.  This clearly might fail optimality, but I can't imagine how to cause divergent or latchup behaviors.  Under authentic workloads this is not a worry at all.

[1] JEFFREY M. JAFFE, 1981, Flow Control Power is Nondecentralizable, IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-29, NO. 9,

Thanks,
--MM--
The best way to predict the future is to create it.  - Alan Kay

We must not tolerate intolerance;
       however our response must be carefully measured:
            too strong would be hypocritical and risks spiraling out of control;
            too weak risks being mistaken for tacit approval.


On Fri, Sep 6, 2019 at 8:26 AM Neal Cardwell <ncardwell=[e-mail]<mailto:[e-mail]>> wrote:
On Wed, Sep 4, 2019 at 6:15 AM marcelo bagnulo braun <[e-mail]<mailto:[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

_______________________________________________
iccrg mailing list
[e-mail]<mailto:[e-mail]>
https://www.irtf.org/mailman/listinfo/iccrg<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Ficcrg&data=02%7C01%7Cpravb%40microsoft.com%7Ce67fcb1b6a6147f6287a08d7332742ff%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637034116037542604&sdata=y%2F4tAkhd6sLU58spKZf1RyDFn4NEN32ilLVqm0k8DEk%3D&reserved=0>