Re: [iccrg] Fairness mechanism of BBRv2

Mario Hock <mario.hock@kit.edu> Thu, 28 March 2019 18:11 UTC

Return-Path: <mario.hock@kit.edu>
X-Original-To: iccrg@ietfa.amsl.com
Delivered-To: iccrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 174CD1202CC for <iccrg@ietfa.amsl.com>; Thu, 28 Mar 2019 11:11:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id J2wNafsyj33k for <iccrg@ietfa.amsl.com>; Thu, 28 Mar 2019 11:11:21 -0700 (PDT)
Received: from iramx2.ira.uni-karlsruhe.de (iramx2.ira.uni-karlsruhe.de [IPv6:2a00:1398:2::10:81]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 384A01202CB for <iccrg@irtf.org>; Thu, 28 Mar 2019 11:11:20 -0700 (PDT)
Received: from [2a00:1398:2:4006:d86e:69a0:2837:7cf0] by iramx2.ira.uni-karlsruhe.de with esmtpsa port 587 iface 2a00:1398:2::10:8 id 1h9ZUk-0006QG-O4; Thu, 28 Mar 2019 19:11:18 +0100
To: Neal Cardwell <ncardwell@google.com>
Cc: "iccrg@irtf.org" <iccrg@irtf.org>
References: <2992479c-d4bd-9647-384f-cad5f5b119bf@kit.edu> <CADVnQynMDGpa54XL3L12H56asS+Y5E3UFimmS2d9RoEKPeDpeA@mail.gmail.com>
From: Mario Hock <mario.hock@kit.edu>
Message-ID: <668e5315-314f-439f-b7b3-25264e853af5@kit.edu>
Date: Thu, 28 Mar 2019 19:11:17 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.5.1
MIME-Version: 1.0
In-Reply-To: <CADVnQynMDGpa54XL3L12H56asS+Y5E3UFimmS2d9RoEKPeDpeA@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-ATIS-AV: ClamAV (iramx2.ira.uni-karlsruhe.de)
X-ATIS-Timestamp: iramx2.ira.uni-karlsruhe.de esmtpsa 1553796678.857796576
Archived-At: <https://mailarchive.ietf.org/arch/msg/iccrg/dRkYFYqkThDYXYVCDyu-u3JI76g>
Subject: Re: [iccrg] Fairness mechanism of BBRv2
X-BeenThere: iccrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Discussions of Internet Congestion Control Research Group \(ICCRG\)" <iccrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/iccrg>, <mailto:iccrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/iccrg/>
List-Post: <mailto:iccrg@irtf.org>
List-Help: <mailto:iccrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/iccrg>, <mailto:iccrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 28 Mar 2019 18:11:24 -0000

Neil, thanks for the quick answer.

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

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?


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

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


> 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 <mario.hock@kit.edu> 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
>> iccrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/iccrg