Subject: [iccrg] Fairness mechanism of BBRv2

From: Mario Hock <[email-masked]>
Date: Thu, 28 Mar 2019 17:29:48 +0100

Neal,

as just discussed during the ICCRG session (jabber question), can you 
give some details about the "convergence to fairness" mechanism of BBRv2 
(intra-protocol)?

Did I get you right that either MD (multiplicative decrease) or MI 
(multiplicative increase) leads to fairness, depending on buffer size?

Also, did you mean increase/decrease of CWnd or of rate?

Best, Mario

---

From: Neal Cardwell <[email-masked]>
Date: Thu, 28 Mar 2019 18:18:49 +0100

Hi Mario,

Yes, that's right. The basic idea is:

(a) In a bottleneck that is providing loss or ECN signals, the BBRv2
flows will be doing a MD (multiplicative decrease) in the volume of
in-flight data (cwnd). As with the MD in Reno or CUBIC, this leaves an
amount of unused headroom (in the buffer and/or bottleneck link) that
is larger for high-rate flows, and smaller for low-rate flows. So the
convergence dynamics are somewhat analogous to CUBIC, which also uses
an MD and then super-linear increase process.

(b) In a bottleneck that has a deep buffer and is not providing loss
or ECN signals, the BBRv2 flows will be converging toward approximate
fairness using the same MI/MD  rate-based scheme used in BBRv1. The
basic reason that the flows pull toward fairness is that in each round
of probing, the MI probing from small flows produces a larger
proportional increase in their bandwidth estimate than does the MI
probing from large flows. Here the dynamics are a bit analogous to a
market with a fixed-rate set of sales transactions; if all the players
are trying to increase their market share (sales rate) by stocking
shelves with an MI relative to their sales in the last interval, the
small start-up producers will find it much easier to grow
multiplicatively for a while, while the bigger players will end up
noticing their market share is shrinking multiplicatively due to
losing customers to the smaller players.

I believe the (a) part is fairly closely analogous to the essence of
the well-studied CUBIC dynamics. For the (b) part, we have an
algebraic analysis and simulation scripts/graphs, if there is
interest. I might be able to post those after the IETF if there is
interest.

best,
neal

On Thu, Mar 28, 2019 at 5:30 PM Mario Hock <[email-masked]> wrote:
> _______________________________________________
> iccrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/iccrg

---

From: Mario Hock <[email-masked]>
Date: Thu, 28 Mar 2019 19:11:17 +0100

Neil, thanks for the quick answer.

Yes, I would be very interested in the algebraic analysis and simulation 
scripts/graphs. (Some further questions inline.)

> an MD and then super-linear increase process.

In CUBIC we have, let's call it, a generalized form of AIMD (additive 
increase, multiplicative decrease). In CUBIC the increase is not 
additive but still does not depend on the current CWnd size.

It's the combination of "equal" (non CWnd dependant) increase and 
multiplicative (CWnd dependant) decrease that converges to fairness. 
What's increase of BBRv2 here?

> losing customers to the smaller players.

[1] has shown that MIMD does not lead to fairness. What is different in 
your case?

Actually, going over my own formulas from [2], I might got a clue:

rate_new = 1.25 * rate_old * (OUT / IN)

(IN = input rate at bottleneck, OUT = output rate of bottleneck)

So, the idea is: When a large flow is probing, IN is larger than when a 
small flow is probing. Thus rate_new / rate_old is smaller for a large 
flow than for a small flow. As long as they probe at distinct time.

Does this coincide with your findings?

[1] D.-M. Chiu und R. Jain, „Analysis of the increase and decrease 
algorithms for congestion avoidance in computer networks“, Computer 
Networks and ISDN Systems, Bd. 17, Nr. 1, S. 1–14, Juni 1989.

[1]M. Hock, R. Bless, und M. Zitterbart, „Experimental Evaluation of BBR 
Congestion Control“, in 2017 IEEE 25th International Conference on 
Network Protocols (ICNP), 2017.

Best, Mario

---

From: Neal Cardwell <[email-masked]>
Date: Fri, 29 Mar 2019 00:05:44 +0100

> Neil, thanks for the quick answer.

Hi, Mario,

Thanks for the excellent points.

> scripts/graphs. (Some further questions inline.)

OK, sure, I will try to put that together and send it out. (Though I
think we are on the same page about that part, based on your remarks
further down in your e-mail.)

> What's increase of BBRv2 here?

We tried to describe the flavor of the increase behavior on slide 25
of today's slide deck:
  https://datatracker.ietf.org/meeting/104/materials/slides-104-iccrg-an-update-on-bbr-00

In the current design, the basic idea is that in any given round trip
time of probing beyond inflight_hi, the cwnd is set to:
  inflight_hi + inflight_probe
where inflight_probe starts at 0, and then grows exponentially per
round: 1, 2, 4, 8... packets.

That increase constraint does have the nice property you mention where
the cwnd increase at any instant does not depend on the current cwnd
size.

> [1] has shown that MIMD does not lead to fairness. What is different in

AIMD is the headline scheme in [1], but FWIW [1] says that a MIMD-like
scheme can work as long as there is an additive component as well.
Specifically, on page 9 it says:

"Proposition 1. In order to satisfy the requirements of distributed
convergence to efficiency and fairness without truncation, the linear
decrease policy should be multiplicative, and the linear increase
policy should always have an additive component, and optionally it may
have a multiplicative component with the coefficient no less than
one."

So basically, according to [1] you need MD, and AI, but you can also
have an optional MI component as well.

> Does this coincide with your findings?

Yes, exactly, that "rate_new / rate_old is smaller for a large flow
than for a small flow, as long as they probe at distinct time" dynamic
is what I was trying to describe in the (b) case.

best,
neal