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

From: marcelo bagnulo braun <[email-masked]>
Date: Tue, 3 Sep 2019 11:05:17 +0200

Hi Neal,

Thanks for the comments and sorry for the delay in replying, I was away.

Reading RFC6817, the goals of LEDBAT are:

" LEDBAT congestion control seeks to achieve the following goals:

    1.  to utilize end-to-end available bandwidth and to maintain low
        queueing delay when no other traffic is present,

    2.  to add limited queuing delay to that induced by concurrent flows,
        and

    3.  to yield quickly to standard TCP flows that share the same
        bottleneck link."

So, as i read this, when other traffic is present, the goal of LEDBAT is 
expressed in the additional queueing delay added by the LEDBAT flow and 
NOT in terms of the absolute queueing delay in the bottleneck. (I think 
this differs form other efforts targetting of limiting the absolute 
queueing delay.

 From this perspective, simply slowing down the flow, would allow 
LEDBAT++ to measure the base delay in its absence and comply with the 
goal of limited additional delay.

Also, note that LEDBAT reacts to losses, and this serves as a safety net 
in case the delay estimation are mistaken.

In the case of rLEDBAt, we plan so simply use LEDBAT++, so we will refer 
to the other document (de facto incorporating the periodic slowdowns).

Makes sense?
Regards, marcelo

El 24/07/19 a las 02:36, Neal Cardwell escribió:
> Thanks for today's presentations on LEDBAT++ and rLEDBAT. These are
> nice work, and I agree they are important improvements on LEDBAT, and
> worth pursuing as working group efforts, with a goal of standardizing
> these algorithms in some form.
>
> I had two related questions on slowdowns:
>
> (1) Regarding LEDBAT++ and slowdowns:
> https://tools.ietf.org/html/draft-balasubramanian-iccrg-ledbatplusplus-00#section-4.4
> To try to avoid latency drift in the base delay, the LEDBAT++ design
> describes periodic slowdowns that cut cwnd to 2 packets. As far as I'm
> aware, the only way the flows would be able to refresh an accurate
> notion of the base delay would be if there is at least one slowdown
> during the base delay filter window in which the bottleneck queue is
> essentially empty. But if a LEDBAT++ flow has a fair share of the BDP
> that is less than the depth of the queue, then having that flow remove
> all of its packets from the path, by itself, will not fully drain the
> bottleneck queue (the packets from the remaining flows that are not in
> slowdown will be enough to fill the pipe and create a non-zero queue,
> obscuring the base delay).
>
> So AFAICT uncoordinated slow-downs won't drain the queue; then the
> only approach I can think of to achieve this would be for the flows to
> coordinate in some fashion to all do a slowdown during overlapping
> time intervals (as in BBR's PROBE_RTT mechanism). But AFAICT in the
> design described in the draft, if there are many flows then I did not
> see a mechanism described in the draft that would achieve this.
>
> The IETF 100 LEDBAT++ slides show a multi-flow example, on page 14:
>    https://datatracker.ietf.org/meeting/100/materials/slides-100-iccrg-ledbat-low-priority-tcp-congestion-control-in-windows-01
> But that example has just two flows. And two flows is an easy case for
> this kind of scheme: if there are two flows that are sharing a link
> equally, then when one of them stops sending then this will almost
> always drain the queue quite well.
>
> Do you have test results you can share with more flows, showing how
> the slowdown mechanism works for cases with more flows? Or is there a
> way to add more text in the draft to explain how the slowdown design
> in LEDBAT++ handles this issue already?
>
> (2) The rLEDBAT draft:
> https://tools.ietf.org/html/draft-bagnulo-iccrg-rledbat-00
> mentions: "rLEDBAT estimates the Base RTT (i.e. the RTT when there is
> no queuing delay) as the minimum observed RTT in the last n minutes."
> However it doesn't seem to mention a slowdown mechanism to try to
> refresh the estimate of the base RTT. Does it have such a mechanism?
> AFAICT rLEDBAT, like LEDBAT++, would need a mechanism to do a
> coordinated cut in cwnds, like BBR's PROBE_RTT mechanism, if multiple
> rLEDBAT flows are to all maintain a good estimate of the base RTT of
> the path. Any thoughts on that question?
>
> Apologies if I'm missing something on either of these issues. :-)
>
> And thank you both for presenting these respective algorithms. I think
> both algorithms are important advances, and standardizing something
> like each of them would be valuable for the community.
>
> thanks,
> neal
>

---

From: Neal Cardwell <[email-masked]>
Date: Tue, 3 Sep 2019 11:04:41 -0400

> goal of limited additional delay.

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.

(2) With minor tweaks to coordinate slowdowns, the LEDBAT++/rLEDBAT
algorithms could be tweaked to avoid this problem in common multi-flow
scenarios.

best,
neal

---

From: marcelo bagnulo braun <[email-masked]>
Date: Tue, 3 Sep 2019 17:57:12 +0200

below...

> interference with the network performance of competing flows") or the

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.

this is also true for LEDBAT, i guess.

> algorithms could be tweaked to avoid this problem in common multi-flow

I guess the obvious way to synchronize this would be to generate a 
packet loss so that all the flows would slow down and it would be 
possible to measure the base delay. But i guess you have something more 
subtle in mind?

Regards, marcelo

---

From: marcelo bagnulo braun <[email-masked]>
Date: Wed, 4 Sep 2019 12:15:38 +0200

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ó:
> 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?

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.

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++.

I am not sure this is true for all combinations of parameter values, i 
need to look into this.

Regards, marcelo

> possible to measure the base delay. But i guess you have something 
> more subtle in mind?
>
> Regards, marcelo
>
>
>
>> best,
>> neal
>>
>

---

From: Neal Cardwell <[email-masked]>
Date: Fri, 6 Sep 2019 11:02:34 -0400

> El 03/09/19 a las 17:04, Neal Cardwell escribió:
...
> possible to measure the base delay. But i guess you have something more

Yes, rather than synchronizing using losses, I had something in mind along
the lines I proposed earlier in this thread; something like
BBR's PROBE_RTT mechanism:

   ... the
   only approach I can think of to achieve this would be for the flows to
   coordinate in some fashion to all do a slowdown during overlapping
   time intervals (as in BBR's PROBE_RTT mechanism).

The details of BBR's PROBE_RTT mechanism are described in:
  https://tools.ietf.org/html/draft-cardwell-iccrg-bbr-congestion-control-00#section-4.3.5

best,
neal

---

From: Neal Cardwell <[email-masked]>
Date: Fri, 6 Sep 2019 11:25:28 -0400

> 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.

> 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.

> So, I am not convinced that it is not enough with the slow down proposed

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

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

---

From: Matt Mathis <[email-masked]>
Date: Fri, 6 Sep 2019 17:06:28 -0700

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=
[email-masked]> wrote:

> _______________________________________________
> iccrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/iccrg
>

---

From: marcelo bagnulo braun <[email-masked]>
Date: Mon, 9 Sep 2019 10:35:38 +0200

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?
Thanks, marcelo

---

From: marcelo bagnulo braun <[email-masked]>
Date: Mon, 9 Sep 2019 10:57:15 +0200

Forgot the reference:
[1] Rethinking the Low Extra Delay Background Transport (LEDBAT) Protocol
Carofiglio, Giovanna; Muscariello, Luca; Rossi, Dario; Testa, Claudio; 
Valenti, Silvio
ISSN: 1389-1286 , 1872-7069; DOI: 10.1016/j.comnet.2013.02.020
Computer networks. , 2013, Vol.57(8), p.1838-1852

El 09/09/19 a las 10:35, marcelo bagnulo braun escribió:
> Hi Neal,
>
> Thanks for the explanation. I can see now that uncoordinated slow 
> downs is not enough to provide a bounded 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?
> Thanks, marcelo
>
>

---

From: marcelo bagnulo braun <[email-masked]>
Date: Mon, 9 Sep 2019 12:01:34 +0200

below...

>    https://tools.ietf.org/html/draft-cardwell-iccrg-bbr-congestion-control-00#section-4.3.5

Thanks for the pointer. So, if i understand this correctly, essentially 
the proposed mechanism is that the flow slows down 10 seconds after the 
last update in the estimation of the base delay.

Is this it or am i missing something?

I understand that the expectation is that if there are several flows, 
the slow down of one them will cause the update of the base delay of 
several flows. These flows are now synchronized, so when they all slow 
down at the same time, they will cause even more flows to update their 
base delay estimation, and eventually all of them will be synchronized 
in their slow downs and then properly assess the base delay.

If this is so, I guess one question is how to know for sure that when 
they are in the uncoordinated state, the slow down of one of them will 
cause the update of the base delay of other flows, no?

Thanks, marcelo

> .

---

From: "Bless, Roland (TM)" <[email-masked]>
Date: Mon, 9 Sep 2019 15:36:01 +0200

Hi Marcelo,

Just some quick remarks. My colleague Mario Hock did some LEDBAT
research, too (yet unpublished), that eventually evolved into TCP LoLa
[*].
There are often dependencies between performance (e.g., keeping
utilization high and overall delay bounded) and fairness goals
and their respective mechanisms.
However, the results for using LEDBAT with AIMD are somewhat sensitive
to the \beta reduction factor and also show delay jitter.

In contrast to LEDBAT and Vegas, TCP LoLa tries to bound the
overall queuing delay (not the per-flow queueing delay).
TCP LoLa has a special "Fair Flow Balancing" mechanism that
uses Queueing Delay measurements for synchronization: if the flows
measure a queueing delay above Q_target, they will multiplicatively
decrease their CWnd after some fixed waiting period (this allows all
LoLa flows to quite reliably detect the exceedance of Q_target).
This "Tailored Decrease" reduction action uses a CWnd value that will
likely result in a light underutilization and thus allows all flows to
measure the current RTT_min.

[*]  Mario Hock, Felix Neumeister, Martina Zitterbart, Roland Bless: TCP
LoLa: Congestion Control for Low Latencies and High Throughput,
IEEE LCN 2017, http://ieeexplore.ieee.org/document/8109356/

---

From: Neal Cardwell <[email-masked]>
Date: Mon, 9 Sep 2019 10:10:15 -0400

> provide fairness and keep the queueing delay added by the ledbat flows

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

---

From: Neal Cardwell <[email-masked]>
Date: Mon, 9 Sep 2019 10:30:58 -0400

[+bbr-dev since this iccrg list thread is getting into a discussion of the
detailed dynamics of PROBE_RTT]

> Is this it or am i missing something?

Yes, that's it, exactly.

> in their slow downs and then properly assess the base delay.

Yes, that's the basic flavor of the dynamics.

> cause the update of the base delay of other flows, no?

In the common case BBR PROBE_RTT works in a way that can be broken down
into two parts:

(1) How does the algorithm coordinate the phase of multiple bulk flows to
enter PROBE_RTT at overlapping time periods? This coordination works
because if there are multiple bulk flows sharing a bottleneck, they will
usually tend to see the same pattern of increases and decreases in RTT, due
to the variation of queuing delay over time (they will all tend to see the
same time series, merely shifted up or down by their two-way propagation
delay). So the flows will tend to be able to agree on the point in time
during the last 10-second window that had the lowest RTT. Then the flows
use that point in time as a coordination marker, and all schedule their
next PROBE_RTT relative to that point in time. Over time, usually 2-3
min_rtt windows of 10 seconds each, that allows coordinated decreases of
cwnd.

(2) How does a coordinated decrease of cwnd in PROBE_RTT expose the
approximate two-way propagation delay? If the multiple flows coordinate a
cut in cwnd, and that cut reduces the cwnds low enough and long enough that
the sum of the rates of the flows is less than the bottleneck bandwidth,
then the bottleneck queue can drain and the RTT samples can approximate
the  two-way propagation delay for each flow. It is easiest to visualize
the simplest case, where all flows have the same two-way propagation delay,
and then the ensemble of flows merely needs to pull the cwnds down far
enough to make the sum of cwnds less than the BDP of the path, and then
hold that condition for long enough for all flows to measure an
approximation of the queue-free RTT. With LEDBAT++ having a cwnd=2 (as in
https://tools.ietf.org/id/draft-balasubramanian-iccrg-ledbatplusplus-00.html )
or BBRv1 having a cwnd=4, the sum of the cwnds will tend to be less than
the BDP of the path in many common cases (up to tens or hundreds of flows
at typical low BDPs, or thousands of flows in high-speed WANs).

thanks,
neal

---

From: Luca Muscariello <[email-masked]>
Date: Mon, 9 Sep 2019 17:08:25 +0200

[1] assumes perfect knowledge of the RTT_min. So one way to measure it is
still required.
AIMD alone is not enough of course.

---

From: marcelo bagnulo braun <[email-masked]>
Date: Mon, 9 Sep 2019 17:34:03 +0200

Hi Luca,
thanks for replying.

I am not sure i understand your answer though. I mean the whole problem 
of LEDBAT latecomer advantage is that the late comer misestimates the 
base delay (i.e. RTT_min?) and then it adds the target delay on top of 
the wrongly estiamted base delay.
So, i dont understand what do you mean that the mechanism assumes 
knownledge of the base delay. Clearly, i am missing something here, 
could you educate me?

Thanks, marcelo

El 09/09/19 a las 17:08, Luca Muscariello escribió:
> [1] assumes perfect knowledge of the RTT_min. So one way to measure it 
> is still required.
> On Mon, Sep 9, 2019 at 10:35 AM marcelo bagnulo braun 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Hi Neal,
>
>     downs
>     [email-masked] <mailto:[email-masked]>

---

From: "Bless, Roland (TM)" <[email-masked]>
Date: Tue, 10 Sep 2019 09:34:42 +0200

Hi Marcelo,

> the wrongly estiamted base delay.

Yes.

> knownledge of the base delay. Clearly, i am missing something here,

As Luca wrote, their proposed algorithm requires a _perfect knowledge_
of RTT_min, i.e., transmission and propagation delay
without any queueing delay.

Note that, even if one would have perfect knowledge of queueing delay,
the latecomer advantage would turn into a latecomer disadvantage,
because the latecomer would back-off. Fairness remains still
an issue then...

Regards
 Roland

---

From: Luca Muscariello <[email-masked]>
Date: Tue, 10 Sep 2019 10:22:13 +0200

I think, Roland is right about fairness.
More generally AIAD is unfair, which turns out to be a stability issue.
This is also known for Vegas.

So even if RTT_min is known AIAD is a bad design choice.
Still it remains to infer RTT_min.

There is a reference that I report below that can be useful to fix LEDBAT
for what concerns
intra/inter protocol fairness seen from a stability perspective.

A. Tang, X. Wei, S. H. Low and M. Chiang,
"Equilibrium of Heterogeneous Congestion Control: Optimality and
Stability,"
in *IEEE/ACM Transactions on Networking*, vol. 18, no. 3, pp. 844-857, June
2010.
doi: 10.1109/TNET.2009.2034963

---

From: Michael Welzl <[email-masked]>
Date: Tue, 10 Sep 2019 11:45:56 +0200

> On 10 Sep 2019, at 10:22, Luca Muscariello <[email-masked]> wrote:
> 

That said, I hope people are aware that AIMD isn't really much better in that respect. This gets quite clear when simply looking at some trajectories with unequal RTTs.
Easy and intuitive to do with this tool: http://heim.ifi.uio.no/~michawe/research/tools/cavt/index.html

Cheers,
Michael

> There is a reference that I report below that can be useful to fix LEDBAT for what concerns 
> "Equilibrium of Heterogeneous Congestion Control: Optimality and Stability," 
> in IEEE/ACM Transactions on Networking, vol. 18, no. 3, pp. 844-857, June 2010.
> On Tue, Sep 10, 2019 at 9:36 AM Bless, Roland (TM) <[email-masked]> wrote:
> Hi Marcelo,
>

---

From: Luca Muscariello <[email-masked]>
Date: Tue, 10 Sep 2019 15:02:49 +0200

I think those are two different kind of unfairness effects. One can lead to
starvation, the other to biased fair shares in favor of small RTTs.

On Tue 10 Sep 2019 at 11:46, Michael Welzl <[email-masked]> wrote:

> That said, I hope people are aware that AIMD isn't really much better in
> that respect. This gets quite clear when simply looking at some
> trajectories with unequal RTTs.
> Easy and intuitive to do with this tool:
> http://heim.ifi.uio.no/~michawe/research/tools/cavt/index.html
>
> Cheers,
> Michael
>
>