Re: [tcpm] alpha_cubic

Bob Briscoe <ietf@bobbriscoe.net> Thu, 23 September 2021 17:15 UTC

Return-Path: <ietf@bobbriscoe.net>
X-Original-To: tcpm@ietfa.amsl.com
Delivered-To: tcpm@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 83D303A13F8 for <tcpm@ietfa.amsl.com>; Thu, 23 Sep 2021 10:15:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.993
X-Spam-Level: **
X-Spam-Status: No, score=2.993 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, GB_SUMOF=5, HTML_MESSAGE=0.001, HTML_OBFUSCATE_10_20=0.093, NICE_REPLY_A=-0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=bobbriscoe.net
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 85rWlQ-dP9bX for <tcpm@ietfa.amsl.com>; Thu, 23 Sep 2021 10:15:40 -0700 (PDT)
Received: from mail-ssdrsserver2.hostinginterface.eu (mail-ssdrsserver2.hostinginterface.eu [185.185.85.90]) (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 150C93A1402 for <tcpm@ietf.org>; Thu, 23 Sep 2021 10:15:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=bobbriscoe.net; s=default; h=Content-Type:In-Reply-To:MIME-Version:Date: Message-ID:From:References:Cc:To:Subject:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=m5u6sBpkFwKuh0TKjmLW8JAtPDD2kH1lV95TmDvD3qg=; b=JCx3tePj264fg3Xii0qP2vO68f KTAbUSmuRLuE4IDr3kfFVQeFZnSsey0y20tfg8FaiKp1/Sl3HZfpMtbhFZQ44AcYJ9pGT45V6/sus uKtCfBQHREwP/N2m3uf+hqfpZFPI4M+epP7BdCpV9Ge4dFr9dVjmSR+M63LjIX7et7w3dC8Rw4fDZ 6C0Ce9+vqr+FQzqxJqcRojYSqesWMYbj/kV4GJKntLeH09bkAbn/xFUpJ4VktyCZyBwEWLQZ5rD5O Bp6RhF8+iPgcBKrJqf3bbfHro0c7AKPXRI19rkYpt+N3+/TXShntRuFbZ/jysooMEt4mshY1jV+Tv me9JnWWQ==;
Received: from 67.153.238.178.in-addr.arpa ([178.238.153.67]:60890 helo=[192.168.1.13]) by ssdrsserver2.hostinginterface.eu with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from <ietf@bobbriscoe.net>) id 1mTSJx-00BpUK-GT; Thu, 23 Sep 2021 18:15:34 +0100
To: Yoshifumi Nishida <nsd.ietf@gmail.com>
Cc: Markku Kojo <kojo=40cs.helsinki.fi@dmarc.ietf.org>, "tcpm@ietf.org Extensions" <tcpm@ietf.org>
References: <CAAK044SjMmBnO8xdn2ogWMZTcecXoET1dmZqd6Dt3WzOUi359A@mail.gmail.com> <alpine.DEB.2.21.2108300740560.5845@hp8x-60.cs.helsinki.fi> <ccfc4dc2-0570-1ba2-66a5-b5e199f11359@bobbriscoe.net> <CAAK044T-ZtZUuq4xBSuB1E9aqHOn96orXe=8ZMJHao_j4xpK3Q@mail.gmail.com> <2a3f7032-6548-061f-c6b1-a39442699228@bobbriscoe.net> <CAAK044Rcw2iryxQ7g-1nFGjnwxNkTX8NhnuGaOeDD=sQFH0sKw@mail.gmail.com>
From: Bob Briscoe <ietf@bobbriscoe.net>
Message-ID: <8b67d4a4-798d-474d-aa9c-edb500f53b27@bobbriscoe.net>
Date: Thu, 23 Sep 2021 18:15:33 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0
MIME-Version: 1.0
In-Reply-To: <CAAK044Rcw2iryxQ7g-1nFGjnwxNkTX8NhnuGaOeDD=sQFH0sKw@mail.gmail.com>
Content-Type: multipart/alternative; boundary="------------F5D0DC2D0849934C67F9D4FF"
Content-Language: en-GB
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname - ssdrsserver2.hostinginterface.eu
X-AntiAbuse: Original Domain - ietf.org
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - bobbriscoe.net
X-Get-Message-Sender-Via: ssdrsserver2.hostinginterface.eu: authenticated_id: in@bobbriscoe.net
X-Authenticated-Sender: ssdrsserver2.hostinginterface.eu: in@bobbriscoe.net
X-Source:
X-Source-Args:
X-Source-Dir:
Archived-At: <https://mailarchive.ietf.org/arch/msg/tcpm/9fp2qG9wuyctIg7nCnQfyOq0I2w>
Subject: Re: [tcpm] alpha_cubic
X-BeenThere: tcpm@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: TCP Maintenance and Minor Extensions Working Group <tcpm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tcpm>, <mailto:tcpm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tcpm/>
List-Post: <mailto:tcpm@ietf.org>
List-Help: <mailto:tcpm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tcpm>, <mailto:tcpm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 23 Sep 2021 17:15:46 -0000

Yoshi,

To summarize the main concern I already wrote in my first email (but 
perhaps didn't summarize well): the formula assumes deterministic 
marking (i.e. some but not all AQMs, and definitely not drop-tail). I 
believe a large majority of the bottleneck buffers on the Internet are 
still drop tail, despite the efforts of many to recommend AQM 
deployment. So it's not particularly applicable to the real Internet.

It also assumes the sawteeth of flows with different RTTs all centre on 
an operating point around the middle of the sawteeth, which is perhaps 
true of RED, but not most other AQMs.

I will still try to develop a better formula - I've thought how to do it 
in principle, but haven't developed the maths for it - it's hard. But 
pls don't wait for me. The Cubic RFC's good enough, and the precise 
value of the Reno-Friendly alpha parameter is fairly irrelevant given 
the most prevalent deployment (Linux) ignores the RFC and sets it much 
more aggressively to 1 instead of 0.53 anyway.


Bob

On 17/09/2021 10:06, Yoshifumi Nishida wrote:
> Hi Bob,
>
> Thanks for the comments.
> I at least think we both can agree that the draft uses [FHP00] as the 
> basis of their AIMD or NewReno model.
> If you have any suggestions to update the texts to address your 
> concerns, please share. (but, in this case, using github might be 
> straightforward.)
> Unfortunately, I'm not sure about the empirical evidence to support 
> the formula.
> But, given that cubic has been widely deployed for long time and we 
> don't see strong voices to point out problems for it, I am guessing 
> the issues might not be too obvious at least.
> If you have any specific concerns in the formula, could you share?
>
> Thanks,
> --
> Yoshi
>
>
> On Mon, Sep 13, 2021 at 4:17 PM Bob Briscoe <ietf@bobbriscoe.net 
> <mailto:ietf@bobbriscoe.net>> wrote:
>
>     Yoshi,
>
>     On 11/09/2021 22:02, Yoshifumi Nishida wrote:
>>     Hi Bob,
>>
>>     Thanks for the very detailed explanation.
>>     I agree with some of your points. But, I have two comments on this.
>>
>>     The first point is about RTT variation.
>>     I think you have a point there, but I personally think the paper
>>     presumes very shallow queue so that the model can be very simple.
>>     In this case, we don't have to think about min or max of RTT as
>>     they will be mostly the same.
>
>     [BB] The paper gets the same answer as I got under assumption #3
>     (all sawtooth vary around a set point half-way between max and min).
>     I didn't assume shallow queues, so it can't be assuming shallow
>     queues.
>
>>     I think we can probably argue the accuracy of the model, but I
>>     think it is too broad as a scope of this document. It looks a
>>     very deep research topic to me.
>>     I think the model is basically derived from Equation-based
>>     Congestion Control paper in sigcomm 2000. If we want to update or
>>     renew it, we might need another RFC5348.
>
>     [BB] I didn't use Equation-based CC at all and, at least under one
>     of my three assumptions, I got the same result as the [FHP00]
>     paper (with one further assumptions about how many drops there are
>     at the top of different sawteeth).
>
>     I just wanted to check the outcome wouldn't be different if I used
>     a model of varying RTT, 'cos I'd already recently done this maths
>     for another reason - to derive the recovery time after a loss.
>     This proved that, given [FHP00] got the same result as one of my
>     cases just using basic AIMD sawtooth geometry, at least in this
>     one case, the varying RTT doesn't make any difference.
>
>     Nonetheless, I think you're right that deriving the correct
>     formula would involve deeper research. I don't think publication
>     of the RFC should block on that research.
>
>>     So, I think it would be better for this doc to use the model as
>>     it is and leave its enhancements for future discussions.
>
>     [BB] That's up to the WG. But I would not refer to that paper, at
>     least not alone. And I don't think the draft should claim that the
>     formula for Reno-friendly Cubic that it uses from that paper is
>     correct, when it clearly doesn't produce the desired result, even
>     in the paper that proposed it.
>
>>
>>     The second point is α in the draft might be too big.
>
>     [BB] How so? The paper's own simulations (exploring a very limited
>     space) conclude that α from the model is more than 2x too small.
>
>>     During my WGLC review, I read [FHP00] once and I had similar
>>     thoughts.
>>     But, after I re-read the paper several times, I start having a
>>     different interpretation.
>>
>>     First off, it is very clear that β=0.7 is more aggressive than β
>>     =0.5 when there's no other traffic.
>>     As cwnd growth is linear, if there's enough long time for the
>>     data transfer, the average cwnd for β =0.5 will be (1.0 + 0.5)/2
>>     = 0.75 Wmax and it will be (1.0 + 0.7)/2 = 0.85 Wmax for β=0.7.
>
>     [BB] Correct
>
>>     So, it is obvious that this model does not aim for the cases
>>     where there's no other traffic.
>
>     [BB] It is certainly obvious that comparing flow rates is not
>     about single flows.
>
>     But, by the same token, does it mean anything to say a flow is
>     'more aggressive when there's no other traffic'?
>     You can have different cwnd for the same throughput, if the avg
>     queue delay is higher and therefore RTT is higher.  But I don't
>     think that says anything about aggression. If anything, aggression
>     is about shorter recovery time.
>
>     Yes, the analysis I used was for each flow on its own. When they
>     are not on their own, but competing in the same queue, (obviously)
>     there cannot be two different average queue delays. But you can
>     think of them as each progressing in parallel, each taking losses
>     and each contributing to the queue. I'm not saying my analysis is
>     the final word by any stretch of the imagination. However, if on
>     their own they have different recovery times, then when together A
>     will be pulling B away from its natural recovery time and towards
>     A's recovery time, and vice versa.
>
>>
>>     I believe the choice of (α,  β) in [FHP00] is designed to be more
>>     or less fair only when it competes with (α=1.0,  β =0.5)
>>     Hence, I think we should not apply the loss rate for
>>     no-other-traffic situation to the formula, which can lead to α_3
>>      = 0.20
>>     Instead, I am thinking we can think in this way..
>>
>>     (α=1.0,  β =0.5) model oscillates between 0.5 W1 and 1.0 W1 in a
>>     congestion epoch.
>>     (α=X,  β =0.7) model oscillates between 0.7 W2 and 1.0 W2 in the
>>     same congestion epoch.
>>       where W1 is max window for (α=1.0,  β =0.5), W2 is max window
>>     for (α=X,  β =0.7)
>>     When these two models have the same loss ratio, it should satisfy
>>     (1.0 + 0.5) W1 = (1.0 + 0.7) W2
>>
>>     Also, in one congestion epoch, (α=1.0,  β =0.5) increases 0.5 W1
>>     while (α=X,  β =0.7) increases 0.3 W2
>>     Now, if we define the congestion epoch as e RTTs, e = 0.5 W1 /
>>     1.0  and also e = 0.3 W2 / X
>>     This means, X should satisfy
>>       0.5 W1 /1.0  = 0.3 * 1.5/1.7 W1/ X
>>     then we get X = 0.529.
>
>     [BB] This is the same equation as in [FHP00], but with numbers not
>     variables. it's also the same as the formula in the current Cubic
>     RFC. And it gives the same answer you've got when you plug in the
>     numbers. Because you've used the same technique to compare the
>     geometry of the sawteeth.
>
>     But is there empirical evidence to support this formula, given the
>     simulations in the paper itself don't support it? That's the question.
>
>     Also, I'd like to hear Markku's response to your original question
>     to him. I was only trying to second-guess what he was trying to say.
>
>
>     Bob
>
>
>>
>>     This will mean if we launch (α=1.0,  β =0.5) and (α=0.529,  β
>>     =0.7) at the same time and reduce them when the sum of their
>>     windows becomes Wmax, the throughput of them will mostly be the same.
>>     --
>>     Yoshi
>>     On Tue, Sep 7, 2021 at 5:17 AM Bob Briscoe <ietf@bobbriscoe.net
>>     <mailto:ietf@bobbriscoe.net>> wrote:
>>
>>         Yoshi,
>>
>>         You recently asked Markku for an explanation of his point #4.
>>
>>         Coincidentally, a few weeks ago, I was checking the formula
>>         in RFC8312 for Cubic in TCP-Friendly mode (called "C-Reno" in
>>         this email for brevity), and I also checked back on that
>>         preliminary paper that Markku refers to. I think Markku has a
>>         different way of explaining the flaw in the equation, but
>>         below I'll try to explain what I think the problems are. See
>>         [BB] inline...
>>
>>         If you don't read HTML email, I'm afraid the maths is
>>         probably going to look like gobbledygook.
>>
>>         On 30/08/2021 17:33, Markku Kojo wrote:
>>>         Hi Yoshi, all,
>>>
>>>         On Wed, 18 Aug 2021, Yoshifumi Nishida wrote:
>>>
>>>         4. Fairness to AIMD congestion control
>>>
>>>            The equation on page 12 to derive increase factor α_cubic
>>>         that
>>>            intends to achieve the same average window as AIMD TCP
>>>         seems to
>>>            have its origins in a preliminary paper that states that the
>>>            authors do not have an explanation to the discrepancy
>>>         between
>>>            their AIMD model and experimental results, which clearly
>>>         deviate.
>>>            It seems to have gone unnoticed that the equation assumes
>>>         equal
>>>            drop probability for the different values of the increase
>>>         factor
>>>            and multiplicative decrease factor but the drop probability
>>>            changes when these factors change. 
>>
>>         [BB] The source of eqn (4) in RFC8312 is eqn (4) in [FHP00].
>>         This paper has been cited 250 times but it is not peer reviewed.
>>
>>         Equations (2) & (3) of [FHP00] that lead up to (4) use an RTT
>>         (R) as if it doesn't vary. But it does, because the sawteeth
>>         vary the queue. But the real problem is that the model
>>         (silently) assumes that R is an average RTT sitting part-way
>>         up the sawteeth, whatever the link rate or base RTT. This
>>         overlooks the fact that, if the tips of the sawteeth are
>>         always at the same queue depth (as in a tail-drop buffer) the
>>         average R will be higher if the sawteeth have smaller
>>         amplitude. This sounds picky, but the assumption on whether
>>         sawteeth vary about their bottom, top or middle greatly
>>         alters the outcome:
>>
>>         I've taken three possible alternative assumptions, with their
>>         resulting additive increase factors for theoretical equality
>>         with Reno (I've given all the derivations at the end of this
>>         email):
>>         #1) All sawteeth have the same R_min : α ~= (1/β^2 - 1) /
>>         3;        Example: β = 0.7; α ~= 0.35
>>         #2) All sawteeth have the same R_max : α ~= 4(1-β^2 ) / 3;   
>>                 Example: β = 0.7; α ~= 0.68
>>         #3) All sawteeth have the same Ravg: α ~= 3(1-β) /
>>         (1+β);        Example: β = 0.7; α ~= 0.53 <== used in [FHP00]
>>         and therefore in RFC8312
>>
>>
>>         Which assumption is most applicable?
>>         #2 models a tail-drop queue.
>>         #3 (or somewhere between #3 and #2) models a probabilistic
>>         AQM, such as PIE or RED.
>>         #1 is not applicable to the current Internet, but it would be
>>         if a magic AQM was invented that minimized the standing queue.
>>         I don't think any of the assumptions are good models of
>>         C-Reno's interaction with CoDel.
>>
>>         So which one should draft-ietf-tcpm-rfc8312bis recommend?
>>         You might think #2, given one suspects the vast majority of
>>         queues are still tail drop...
>>         However, it may be 'none of the above', 'cos the paper also
>>         says it assumes deterministic marking; i.e. that that each
>>         flow experiences just one drop or mark at the top of each
>>         sawtooth. If that applies at all, it only applies to AQMs,
>>         not to tail-drop buffers that tend to drop more than one
>>         packet at a time. Nonetheless, for the purpose of rate
>>         comparison, all the flows will share the same bottleneck. So
>>         if flow rates are equal under a certain AQM, they might be
>>         equal under tail-drop too (see {Note 1} at the very end).
>>
>>         I would still like to say 'none of the above' because Linux
>>         C-Reno has been widely used with α=1, β=0.7 for many years
>>         now without the sky falling. So it's questionable whether
>>         friendliness should be defined relative to Reno. Otherwise,
>>         from day 1, RFC8312bis will be stating the forlorn hope that
>>         Linux C-Reno should regress to become less aggressive than
>>         its former self, just to be friendly to Reno, which
>>         apparently barely exists any more (according to the Great TCP
>>         Congestion Control Census of 2019 [MSJ+19]).
>>
>>         Nonetheless, we need to bear in mind that BSD variants of
>>         Cubic (e.g. Apple's) are also widely used and I believe they
>>         comply with the α for C-Reno defined in RFC8312.
>>
>>         (FAQ: Why does C-Reno add <1 segment per RTT to be friendly
>>         to Reno, which adds 1 segment per RTT?
>>         C-Reno in the RFC multiplicatively decreases cwnd to 0.7*cwnd
>>         on a loss (multiplicative decrease factor β=0.7), whereas
>>         Reno uses β=0.5. So, because C-Reno reduces less, it's also
>>         meant to increase less per round so that the sawteeth don't
>>         reach the max window again more quickly than Reno would. That
>>         is, it's meant to use a smaller AI factor (α) than 1 segment.
>>         Using α<1 doesn't necessarily slow down Cubic's acceleration
>>         into unused capacity, because it can switch to a convex
>>         (hockey stick) Cubic curve once its slow linear increase has
>>         made the queue large enough to come out of its 'TCP-Friendly'
>>         mode.)
>>
>>         Whatever, rfc8312bis certainly shouldn't refer solely to
>>         [FHP00] without caveats.
>>
>>         Then we have the problem that none of the above formulae are
>>         verified against reality.
>>         Even in the [FHP00] paper, which uses assumption #3, the
>>         simulations are out by about 2x. The paper used β=7/8. So,
>>         from the theory, for each of the above three assumptions, the
>>         additive increase factor would have had to be:
>>         α_1 = 0.10
>>         α_2 = 0.31
>>         α_3 = 0.20
>>         They used a RED AQM (which should be somewhere between
>>         assumption #2 & #3).
>>         But they had to configure C-Reno with α=0.4 to get close to
>>         equal flow rates with Reno
>>         Using my 'finger in the air' modification to the formulae in
>>         {Note 1}, α_3 = sqrt(0.20) = 0.44, which would have been
>>         about right (perhaps only coincidentally).
>>
>>         The question over what α to put in the RFC could run and run.
>>         So here's a suggested path through this quagmire:
>>         These alternatives throw doubt on the wisdom of using
>>         assumption#3. So we could at least pick a new assumption for
>>         a theoretical α. Assumption#2 is probably the 'most correct',
>>         and also happens to give the highest value of α for the
>>         'TCP-Friendly' region (α=0.68 when β=0.7).
>>         (By my unsubstantiated formula in {Note 1}, α_2 = sqrt(0.68)
>>         = 0.82.)
>>
>>         If we look for an empirical value of α that gives reasonably
>>         equal flow rates against Reno, I suspect we will get all
>>         sorts of different answers depending on the conditions, e.g.
>>         AQM or not; high or low multiplexing; high or low RTT (shared
>>         by all flows); pacing, burstiness, etc,etc. If you want to
>>         take this path, feel free, but if you're still on it in a
>>         year's time, don't say I didn't warn you.
>>
>>
>>         Derivations of the above three formulae follow at the end.
>>
>>>         The equations for the drop
>>>            probability / the # of packets in one congestion epoch
>>>            are available in the original paper and one can easily
>>>         verify
>>>            this. Therefore, the equations used in CUBIC are not correct
>>>            and seem to underestimate _W_est_ for AIMD TCP, resulting in
>>>            moving away from AIMD-Friendly region too early. This gives
>>>            CUBIC unjustified advantage over AIMD TCP particularly in
>>>            environments with low level of statistical multiplexing.
>>>         With
>>>            high level of multiplexing, drop probability goes higher and
>>>            differences in the drop probablilities tend to get small.
>>>         On the
>>>            other hand, with such high level of competition, the
>>>         theoretical
>>>            equations may not be that valid anymore.
>>>
>>>         /Markku
>>
>>         [BB] Derivations of the formulae for α under the three
>>         different assumptions follow. It's possible/likely that this
>>         is all already in a paper somewhere, but I haven't been able
>>         to find one.
>>
>>
>>               0) Preparatory material
>>
>>         Terminology:
>>         The subscript for C-Reno is omitted given it would be on
>>         every term.
>>         The recovery time of an AIMD congestion control is the
>>         average time for additive increase to recover the window
>>         reduction after a multiplicative decrease.
>>
>>         The overall approach is:
>>         A) Find a formula in terms of the AI and MD factors (α & β),
>>         for the recovery time of C-Reno.
>>         B) Equate this to the recovery time of Reno, which will
>>         produce a formula for the additive increase factor, α.
>>
>>         The recovery time formula for C-Reno is derived by:
>>         1) summing up all the round trips in additive increase, which
>>         become increasingly large as the queue grows. This sum is
>>         stated in terms of the number of rounds per cycle, J.
>>         2) Then J is found by writing two formulae;
>>           2a) one for the average sawtooth decrease
>>           2b) and the other for the increase.
>>         Then by assuming a steady state the two can be equated.
>>         Here goes...
>>
>>         The following formula gives the recovery time, T_r , from one
>>         max window to the next, in C-Reno with:
>>         * additive increase (AI) factor α [segment / RTT]
>>         * and packet-rate r [packet / s]
>>         assuming that the minimum window of each sawtooth still fully
>>         utilizes the link.
>>             T_r = Σ^J-1 _j=0   (R_min + jα/r)
>>         where j is the index of each round, and J is the number of
>>         round trips of additive increase per sawtooth. The rationale
>>         for the second term is that the queue grows by α fractional
>>         packets in each round, and the queue delay per packet is 1/r
>>         (seconds per packet is reciprocal of packets per second). The
>>         sum of all the second terms forms an arithmetic progression,
>>         the sum of which is given by the well-known formula, as follows:
>>                  = J.R_min + J(J-1)α/2r
>>                ~= J.R_min + J^2 α/2r.                             (1)
>>         The approximation holds as long as J>>1. In some
>>         implementations (e.g. Linux), cwnd increases continuously, so
>>         strictly the limits should be j=1/2 to J-1/2 (the average
>>         half way through the first and last rounds), but details like
>>         this are insignificant compared to the approximation.
>>
>>         The difference in RTT due to the additional queue delay
>>         between the top and bottom of the sawtooth can be stated in
>>         two ways.
>>         Either as the sum of all the queue delays of each additive
>>         increase:
>>             (R_max - R_min ) = Jα/r,                                (2a)
>>         Or by the multiplicative relationship between the max and min
>>         RTTs, by the definition of β: R_min = β.R_max .
>>             (R_max - R_min ) = (R_min / β) - R_min
>>                                        = R_min (1-β)/β             
>>            (2b)
>>         Equating (2a) and (2b):
>>             J = r.R_min (1-β) / (αβ)                       (2)
>>
>>         Substituting for J from (2) in (1):
>>             T_r = r.R_min ^2 (1-β) / (βα) + r.R_min ^2 (1-β)^2 /(2β^2 α)
>>                  = r.R_min ^2 (1-β) / (βα) * (1 + (1-β)/2β )
>>                  = r.R_min ^2 (1-β)(1+β) / (2β^2 α)
>>                  = r.R_min ^2 (1-β^2 ) / (2β^2 α)         (3)
>>         And, because R_min = β.R_max .
>>             T_r = r.R_max ^2 (1-β^2 ) / (2α)                  (4)
>>
>>         The well-known steady-state Reno formula from [FF99] is:
>>             r_Reno ~= (1/R_avg ) sqrt(3 / 2p)                 (5)
>>         assuming deterministic marking (which is also assumed for the
>>         above model of C-Reno).
>>
>>         Assuming a Reno sawtooth is approximately linear, the average
>>         RTT of a Reno flow,
>>             R_avg ~= (R_max + R_min )/2
>>         and
>>             R_min = R_max /2
>>         Therefore
>>             r_Reno ~= (1/R_min ) sqrt(2 / 3p)                 (6)
>>             r_Reno ~= (1/R_max ) sqrt(8 / 3p)                 (7)
>>
>>         With the preparatory material done, next we take each of the
>>         three assumptions, one at a time.
>>
>>
>>               #1) All sawteeth have the same R_min
>>
>>         From Eqn (3):
>>             T_r = r.R_min ^2 (1-β^2 ) / (2β^2 α)
>>         Total packets sent over period T_r is r.T_r during which time
>>         assume 1 packet is lost (or marked) at the sawtooth peak
>>         {Note 1}. So loss probability:
>>             p = 1 / r.T_r
>>         Substituting for T_r and rearranging :
>>             r^2 = 2β^2 α / R_min ^2 (1-β^2 )p
>>             r = (β/R_min ) sqrt(2α / (1-β^2 )p)
>>         Equating the Reno packet rate, r_Reno , from eqn (6) to the
>>         C-Reno packet rate, r, for all α and β:
>>             r = r_Reno
>>                = (1/R_min ) sqrt(2 / 3p).
>>         Therefore,
>>             (1/R_min ) sqrt(2 / 3p) ~= (β/R_min ) sqrt(2α / (1-β^2 )p)
>>         Rearranging
>>             2/3 ~= 2αβ^2 / (1-β^2 )
>>             α ~= (1-β^2 )/3β^2
>>                ~= (1/β^2 - 1) / 3                     (8)
>>
>>
>>               #2) All sawteeth have the same R_max = R_min / β
>>
>>         From Eqn (4):
>>             T_r = r.R_max ^2 (1-β^2 ) / (2α)
>>         As before, after substituting for Tr and rearranging:
>>             p = 1 / r.T_r
>>             r = (1/R_max ) sqrt(2α / (1-β^2 )p)
>>         Equating to r_Reno from eqn (7) for all α and β,
>>               ~= (1/R_max ) sqrt(8 / 3p).
>>         Rearranging
>>             8/3 ~= 2α / (1-β^2 )
>>             α ~= 4(1-β^2 ) / 3                 (9)
>>
>>
>>               #3) All sawteeth have the same R_avg
>>
>>         R_avg = (R_max + βR_max )/2
>>                  = R_max (1+β)/2
>>         From Eqn (4):
>>             T_r = r.R_max ^2 (1-β^2 ) / (2α)
>>                  = 2r.R_avg ^2 (1-β) / α(1+β)
>>         As before, after substituting for Tr and rearranging:
>>             p = 1 / r.T_r
>>             r = (1/R_avg ) sqrt(α (1+β) / 2(1-β)p)
>>         Equating to r_Reno from eqn (5) for all α and β,
>>               ~= (1/R_avg ) sqrt(3 / 2p).
>>         Rearranging
>>             3/2 ~= α(1+β) / 2(1-β)
>>             α ~= 3(1-β) / (1+β) (10)
>>
>>         This last formula is same as the equation used for C-Reno in
>>         RFC8312 and in the RFC8312bis draft.
>>
>>
>>         {Note 1}: The assumption in [FHP00] of deterministic marking
>>         is suspect for the Internet (meaning that the spacing between
>>         drops or marks is even and there is always 1 packet dropped
>>         or marked at the top of each sawtooth). The actual average
>>         dropped (or marked) per sawtooth will depend on whether the
>>         buffer uses tail-drop or an AQM, and if so which AQM. It is
>>         perhaps better not to assume the actual average number
>>         dropped (or marked) is known, but instead assume the ratio of
>>         the average drops or marks between C-Reno and Reno will be
>>         roughly proportional to their AI factors. This would modify
>>         the formula for C-Reno's drop probability to:
>>             p = α_Reno / α_C-Reno .r.T_r
>>         Substituting α_Reno = 1:
>>             p = 1 / α_C-Reno .r.T_r
>>         This would modify all the results to:
>>
>>         #1) All sawteeth have the same R_min : α ~= sqrt( (1/β^2 - 1)
>>         / 3 ); Example: β = 0.7; α ~= 0.59
>>         #2) All sawteeth have the same R_max : α ~= sqrt( 4(1-β^2 ) /
>>         3 );            Example: β = 0.7; α ~= 0.82
>>         #3) All sawteeth have the same Ravg: α ~= sqrt( 3(1-β) /
>>         (1+β) );        Example: β = 0.7; α ~= 0.73
>>
>>         However, these would then be wrong where there really is
>>         deterministic marking.
>>
>>         References
>>         =========
>>         [FHP00]    Floyd, S., Handley, M., and J. Padhye, "A
>>         Comparison of Equation-Based and AIMD Congestion Control",
>>         May 2000, <https://www.icir.org/tfrc/aimd.pdf
>>         <https://www.icir.org/tfrc/aimd.pdf>>
>>
>>         [MSJ+19] AyushMishra,XiangpengSun,AtishyaJain,
>>         SameerPande,RajJoshi,andBenLeong.The
>>         GreatInternetTCPCongestionControlCensus. Proc. ACM on
>>         Measurement and Analysis of Computing Systems, 3(3), December
>>         2019
>>
>>         [FF99] Sally Floyd and Kevin Fall, "Promoting the Use of
>>         End-to-End Congestion Control in the Internet", IEEE/ACM ToN
>>         (1999)
>>
>>
>>         Bob
>>
>>         -- 
>>         ________________________________________________________________
>>         Bob Briscoehttp://bobbriscoe.net/  <http://bobbriscoe.net/>
>>
>
>     -- 
>     ________________________________________________________________
>     Bob Briscoehttp://bobbriscoe.net/  <http://bobbriscoe.net/>
>

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/