Re: [tcpm] alpha_cubic

Bob Briscoe <ietf@bobbriscoe.net> Sat, 02 October 2021 16:09 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 D457F3A1042 for <tcpm@ietfa.amsl.com>; Sat, 2 Oct 2021 09:09:09 -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 YgIFftbvAdMr for <tcpm@ietfa.amsl.com>; Sat, 2 Oct 2021 09:09:02 -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 325CB3A1029 for <tcpm@ietf.org>; Sat, 2 Oct 2021 09:09:01 -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=2ODbPdDKF2ICjOzwkt4BxGiV3RUWl6cv/yZYSUQYYWE=; b=ORrUCL+rEnzNeFHQoh1dBjEBOK dm95MPCTJv4Ctx6uHe+Ych71GUByrcfQWiTGk037TOuL/ggs82n4GpBMqAeQ42Q7MCZy0HI0pFoUd dFK/5fzAX2D66/7zIdrm54Nl6fzoVBcceZfNB4CuCna3Oy/GdhrL3Cv0marrxiVdVraEBO4H0T4rZ LZlJWaBgM8S0N1EXxmqYG1FGdAGmDkNgXq6ifAsRWTAsMra/TPhaFb/0AdGuSDFJXHr8e6bZQqElh IX7i/mFHN2GZn+GtDZsZz3fcFu0KUeJVNfhF2t4f2ZZfOPaXw4pNb8/NhBI0N9DVtVE1TimgakFbw +WrO3ZXg==;
Received: from 67.153.238.178.in-addr.arpa ([178.238.153.67]:33786 helo=[192.168.1.11]) 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 1mWhZS-0045SE-9o; Sat, 02 Oct 2021 17:08:59 +0100
To: Yoshifumi Nishida <nsd.ietf@gmail.com>, Markku Kojo <kojo=40cs.helsinki.fi@dmarc.ietf.org>
Cc: "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: <3fa617e4-82ac-a359-e087-a00ff7d4c633@bobbriscoe.net>
Date: Sat, 2 Oct 2021 17:08:57 +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="------------B8A9E88B37E8D6AC352E3BA0"
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/TvXJgty7wLUA5CGvNoYPy7MlYyo>
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: Sat, 02 Oct 2021 16:09:10 -0000

Markku, Yoshi,

As promised, I've tried to develop the maths to derive the additive 
increase factor for the Reno-Friendly mode of Cubic. I did it for two cases:
* synchronized (tail-drop)
* desynchronized (AQM)

I've written a short LaTeX report and uploaded here:
https://raw.githubusercontent.com/bbriscoe/cubic-reno/main/creno_tr.pdf
If Markku and others review it, I'll update it with any corrections, and 
once ready, I can publish it on ArXiv, so that we have an archival 
reference.
Here's a brief summary, but pls read the report before criticizing 
anything in the summary.

*Tail Drop case**
*

  * This turned out to be straightforward, and ended up with the same
    formula as in RFC8312 (which came from [FHP00] which assumed
    /non/-tail-drop!).
  * I believe my derivation is straightforward and rigorous and it
    doesn't rely on loss probability, unlike [FHP00], which was Markku's
    main concern.
  * I've also included a possible explanation for the result with
    tail-drop in [FHP00] where the throughput of CUBIC in Reno-friendly
    mode was lower, not the same as Reno:
      o I've explained why C-Reno would suffer more than Reno if the
        buffer was not deep enough to take the combined synchronized
        decreases without draining out completely.
      o but I haven't proved this empirically by trying with a deeper
        buffer (and I don't intend to - someone else can do that if they
        want).

*Tail-drop summary:* I believe we now have some solid theory for the 
formula in RFC8312, at least for tail drop scenarios, which are (sadly) 
still likely to be prevalent.


*AQM case*

  * Too hard for me to produce even an approximate derivation of the AI
    factor.
  * I've included a discussion of why the formula in [FHP00] is
    incorrect for the AQM case, which is more deeply thought-through
    than my earlier emails:
      o my critique seems similar to Markku's and it is possible it's
        the same, but there's not enough explanation in Markku's emails
        to know for sure.
      o *@Markku*, perhaps you can see if what I've written describes
        what you meant?
  * However, in the AQM case, the simulations in the Floyd report give
    the opposite results to what I would expect.

*AQM summary:* A formula for the AI factor in the AQM case is still 
beyond me, and the results in [FHP00] are still the opposite of what I'd 
expect.


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/