Re: [iccrg] Fairness mechanism of BBRv2

[Neal Cardwell <[e-mail]>]

On Thu, Mar 28, 2019 at 7:11 PM Mario Hock <[e-mail]> wrote:
>
> Neil, thanks for the quick answer.

Hi, Mario,

Thanks for the excellent points.

> Yes, I would be very interested in the algebraic analysis and simulation
> 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.)

> Am 28.03.19 um 18:18 schrieb Neal Cardwell:
> > 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.
>
> 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?

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.

> > (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.
>
> [1] has shown that MIMD does not lead to fairness. What is different in
> your case?

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.

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

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

> [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
>
>
> > 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 <[e-mail]> wrote:
> >>
> >> 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
> >>
> >> _______________________________________________
> >> iccrg mailing list
> >> [e-mail]
> >> https://www.irtf.org/mailman/listinfo/iccrg