### 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/

- [tcpm] Concluding WGLC for draft-ietf-tcpm-rfc831… Yoshifumi Nishida
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Yoshifumi Nishida
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Lars Eggert
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Vidhi Goel
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Vidhi Goel
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Lisong Xu
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Sangtae Ha
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Markku Kojo
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Lars Eggert
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Lars Eggert
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Markku Kojo
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Yoshifumi Nishida
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Lars Eggert
- [tcpm] alpha_cubic (was: Concluding WGLC for draf… Bob Briscoe
- Re: [tcpm] alpha_cubic (was: Concluding WGLC for … Yoshifumi Nishida
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Markku Kojo
- Re: [tcpm] alpha_cubic (was: Concluding WGLC for … Yoshifumi Nishida
- Re: [tcpm] alpha_cubic (was: Concluding WGLC for … Jonathan Morton
- Re: [tcpm] alpha_cubic Bob Briscoe
- Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rf… Bob Briscoe
- Re: [tcpm] alpha_cubic Yoshifumi Nishida
- Re: [tcpm] alpha_cubic Bob Briscoe
- Re: [tcpm] alpha_cubic Neal Cardwell
- Re: [tcpm] alpha_cubic Bob Briscoe
- Re: [tcpm] alpha_cubic Bob Briscoe
- Re: [tcpm] alpha_cubic Markku Kojo
- Re: [tcpm] alpha_cubic Yoshifumi Nishida