From nobody Tue Mar 22 09:48:35 2022 Return-Path: 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 3D7CB3A09B5 for ; Tue, 22 Mar 2022 09:48:32 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 2.991 X-Spam-Level: ** X-Spam-Status: No, score=2.991 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, GB_SUMOF=5, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cs.helsinki.fi 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 aHgW4CHIAAtE for ; Tue, 22 Mar 2022 09:48:27 -0700 (PDT) Received: from script.cs.helsinki.fi (script.cs.helsinki.fi [128.214.11.1]) (using TLSv1.2 with cipher AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 086D03A08F5 for ; Tue, 22 Mar 2022 09:47:34 -0700 (PDT) X-DKIM: Courier DKIM Filter v0.50+pk-2017-10-25 mail.cs.helsinki.fi Tue, 22 Mar 2022 18:47:06 +0200 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.helsinki.fi; h=date:from:to:cc:subject:in-reply-to:message-id:references :mime-version:content-type:content-id; s=dkim20130528; bh=ylg9yk nXE9gxe6z1K1HIluE60G8SI6RRNUAjcFTZ99U=; b=TAkq1GY8bnr6B3ZXUt1nnL 34EpVbf38tjgdzoMUDKT2CYVeuwocyup7OWcprplmBs0fnqscn1TN33IH6KVpvpG +cop+gp59n521SvSrzf1nTMHfS5/fkvDkzIkZr5Yp4LHirAkORmvoY3neIbu/Qm/ 6Pw7ZfiqkLkjlG7+HJx2E= Received: from hp8x-60 (88-113-49-197.elisa-laajakaista.fi [88.113.49.197]) (AUTH: PLAIN kojo, TLS: TLSv1/SSLv3,256bits,AES256-GCM-SHA384) by mail.cs.helsinki.fi with ESMTPSA; Tue, 22 Mar 2022 18:47:06 +0200 id 00000000005A1C65.000000006239FD8A.0000246B Date: Tue, 22 Mar 2022 18:47:04 +0200 (EET) From: Markku Kojo To: Bob Briscoe cc: Yoshifumi Nishida , Markku Kojo , "tcpm@ietf.org Extensions" In-Reply-To: <3fa617e4-82ac-a359-e087-a00ff7d4c633@bobbriscoe.net> Message-ID: References: <2a3f7032-6548-061f-c6b1-a39442699228@bobbriscoe.net> <3fa617e4-82ac-a359-e087-a00ff7d4c633@bobbriscoe.net> User-Agent: Alpine 2.21 (DEB 202 2017-01-01) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=_script-9346-1647967626-0001-2" Content-ID: Archived-At: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 22 Mar 2022 16:48:33 -0000 This is a MIME-formatted message. If you see this text it means that your E-mail software does not support MIME-formatted messages. --=_script-9346-1647967626-0001-2 Content-Type: text/plain; charset="iso-8859-7"; format=flowed Content-Transfer-Encoding: quoted-printable Content-ID: Hi Yoshi, Bob, all, below please find my understanding of and feedback on Bob's report (https://raw.githubusercontent.com/bbriscoe/cubic-reno/main/creno_tr.pdf)= .=20 This hopefully also clarifies what I meant when saying that the equation=20 [in the draft] assumes equal drop probability for the different values of=20 alpha and beta but the drop probability actually changes when these=20 values are changed from alpha=3D1, beta =3D 0.5. I have also thought this = a=20 bit more after reading Bob's report and include my understanding of why=20 the performance with C-Reno and Reno differ in case of AQM. In brief, the model for steady state behavior for the Reno-friendly=20 region in a tail-drop queue indeed is incorrect when the additive=20 increase factor alpha < 1 is applied for an alternate AIMD(a, b) TCP.=20 This is because the packet dynamics and behavior of TCP that injects more=20 packets only when cwnd has increased by at least one MSS. This differs=20 from the assumptions of the model and what Bob has used in his analysis=20 (see more below). Also the AQM case remains unvalidated, my reasoning=20 differs, or extends, somewhat the reasoning that Bob gave in his report. The math itself in the original paper [FHP00] which the CUBIC=20 TCP-friendly region is based on seems correct, likewise the math in Bob's=20 report as well as in Yoshi's explanation below: > Yoshifumi Nishida wrote: >=20 > Also, in one congestion epoch, (=E1=3D1.0,=A0 =E2 =3D0.5) increases 0.5 = W1 while > (=E1=3DX,=A0 =E2 =3D0.7) increases 0.3 W2 > Now, if=A0we define the congestion epoch as e RTTs, e =3D 0.5 W1 / 1.0=A0 = and=20 > also e =3D 0.3 W2 / X > This means, X should satisfy >=A0 0.5 W1 /1.0=A0 =3D 0.3 * 1.5/1.7 W1/ X > then we get X =3D 0.529. > This will mean if we launch (=E1=3D1.0,=A0 =E2 =3D0.5) and (=E1=3D0.529= ,=A0 =E2 =3D0.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. I'll try to explain the problems with the model separately for a tail-dro= p=20 and AQM queue. 1. Tail-drop queue (*) The problem with the use of the formula in the original paper as well as=20 in Bob's and Yoshi's analyses is, like it often easily happens, that the=20 theoretical model that has been derived in one context using certain=20 assumptions is reused in another context where the assumptions do not=20 hold, i.e, the model does not match the reality. In this case, the correct use of formula presumes that the drop=20 probability is the same (on the average) for a standard TCP =3D AIMD(1,1/= 2)=20 and AIMD(a,b). That is implicitly assumed also in Bob's report for=20 synchronized (tail drop) case as Bob's math is derived using the same=20 number of packets over a cycle (=3D in between drops, which is reciprocal=20 of drop rate). (Btw, involving RTT in the calculations is unnecessary as=20 all competing flows see the same queue on every RTT, so RTT is the same=20 for all flows sharing the same queue, assuming the base RTT for the flows=20 is the same). Also, Yoshi's calculations above effectively make the same=20 assumption that both flows reduce cwnd at the same time ("when the sum of=20 their windows becomes Wmax"). To understand the difference, we need to look at the packet dynamics of=20 flows competing in a tail drop queue, not just the math. The assumption=20 of equal drop probability holds for any two (or n) AIMD(1, 1/2) TCPs=20 competing on a shared bottleneck: when the bottleneck tail drop buffer=20 becomes full towards the end of a cycle (on RTT n), both TCPs increase=20 their cwnd by 1 for the RTT n+1 and inject two back-to-back pkts=20 resulting in a drop of 1 pkt each (the latter pkt of the two back-to-back=20 pkts =3D the excess pkt according to packet conservation rule becomes=20 dropped). When an AIMD(1, 1/2) TCP competes with an AIMD(a=3D0.53, b=3D0.= 7)=20 TCP (=3DCUBIC) and the tail drop buffer becomes full on RTT n, the=20 AIMD(1,1/2) TCP increases its cwnd by 1 on RTT n+1 and gets 1 pkt=20 dropped. However, AIMD(0.53,0.7) TCP increases its cwnd by 0.53 and=20 only injects an excess packet on RTT n+1 roughly every second cycle=20 because a TCP sender does not inject an additional packet until cwnd has=20 increased by at least by 1 MSS. Hence, in a synchronized case the AIMD(0.53, 0.7) TCP avoids a packet=20 drop and cwnd reduction roughly every second cycle and is able to extend=20 its cycle because the competing AIMD(1, 1/2) TCP reduced its cwnd on RTT=20 n+1 and the bottleneck buffer is not anymore full on RTT n+2 when=20 AIMD(0.53,0.7) TCP injects its additional packet (and would encounter a=20 pkt drop only if the queue is full).=20 Because the cycle is systematically extended in this way for AIMD(0,53,=20 0.7) (=3DCUBIC in Reno-friendly mode), it increases the average number of=20 pkts between drops and thereby decreases the drop probility of CUBIC to=20 be lower than that of the competing AIMD (1, 1/2) TCP. These packet=20 dynamics breaks the model. So, the basic problem is that the model used for the Reno-friendly=20 region obviously is not valid. The results in the original paper [FHP00]=20 do not support the validity of the model either and I am not aware that=20 the model would have been validated by anyone. A good, unresolved question is why the simulation results in the=20 original paper [FHP00] gave lower throughput for AIMD(1/5, 7/8)=20 (denoted as AIMD(1/5, 1/8) in the original paper) for the AQM case. Note that the paper did not give lower throughput for AIMD(1/5, 1/8) with=20 a tail drop bottleneck as the results in the paper were shown only for an=20 AQM bottleneck and the paper just said the results for tail drop are=20 similar which is a vague expression; it may also mean that he results=20 were reversed with similar difference in throughput? Anyway, the results=20 obviously did not validate the model. Bob's explanation for the reason why C-Reno's packet rate decreases is=20 correct but what would happen if the buffer was not deep enough and=20 drained out seems not all correct. The packet rate is the relative share=20 on a shared bottleneck link with fixed capacity. The cwnd of the C-Reno=20 flow is larger than that of Reno in the beginning of the cycle, becomes=20 equal in the middle, and stays increasingly behind for the rest of the=20 cycle. Therefore, C-Reno's *proportional* share decreases during the=20 cycle; the overall througput is the same all the time and bounded by the=20 link capacity. If the buffer was not deep enough and drained out, the relative packet=20 rate between the two flows still behaves the same even if there is no=20 queue and also when the link is underutilized for the beginning of the=20 cycle. When the link is underutilized, the pkt rate increases for both=20 flows until the link becomes fully utilized (note that RTT does not=20 change when the link is underutilized). The pkt rate of C-Reno=20 would increase slower though but it won't change its proportinal share,=20 i.e., C-Reno will not suffer more unlike Bob suggests. The overall averag= e=20 rate is lower in such a case because the link is underutilized for the=20 beginning of the cycle. AQM queue: Bob's explanation for AQM case seems pretty much being on the correct=20 track. In the AQM case the desynchronization of the flows is merely guaranteed=20 for low level of multiplexing. I agree with Bob that modelling AQM=20 case is hard and it also depends on the AQM in use. I also agree Bob's=20 analysis that towards the end of a cycle a probabilistic AQM is more=20 likely to hit Reno somewhat more often than C-Reno. On the other hand,=20 with desynchronized flows the AQM may hit any flow irrespective of its=20 phase. Therefore, the AQM is more likely to hit C-Reno towards the=20 beginning of its cycle somewhat more often than Reno because C-Reno's=20 pkt rate is then higher than that of Reno, and a hit in the beginning of=20 the cycle hurts the performance much more than in the end of=20 the cycle. A hit in the beginning of the cycle results in a cwnd value=20 that is significantly lower than in the beginning of the previous cycle=20 while a hit towards the end of cycle results in a cwnd value much closer=20 to that in the beginning of the previous cycle (the behavious the=20 resembles steady state regular cycle). This might explain, at least in=20 part, the lower throughput for C-Reno in AQM case. I think that an additional possible explanation for the discrepancy in=20 the original paper is that possibly something was wrong with the=20 simulation implementation, or maybe in the simulation parameters. Not all=20 parameters were exposed in the paper. The results also seem not to=20 involve any replications, so we cannot expect statistical validity from=20 the results, a part of the story may be explained just by random effects. In addition, the reasons for the discrepancy speculated in the original=20 paper seem likely to be correct: "One factor could be the assumption of regular, deterministic drops in the deterministic model; another factor could be the role played by retransmit timeouts for TCP in regimes with high packet drop rates." The first one above means the incorrect assumption that drop=20 probabilities are the same. Moreover, the role of RTOs is definitely one=20 potential reason with the high number of competing flows as the model=20 considers the regular steady-state only. So, in summary, the AQM case clearly remains unvalidated as well, or the=20 validation in the original paper actually shows that the model is not=20 correct. An additional problem with the incorrect model is that it tends to result=20 is overaggressive CUBIC behaviour regardless of whether the model yields=20 too low or too high throughput (cwnd) for CUBIC sender in the=20 Reno-frindly region: if the model yields too low throughput, the CUBIC=20 sender leaves the Reno-friendly region too early and becomes (much) more=20 aggressive actual Reno sender would; otherwise, if the model yields too=20 high throughput, the CUBIC sender is too aggressive throughout the=20 Reno-friendly region. (*) Note: The tail drop case in not always synchronized for competing Reno CC=20 flows either. Flows get more or less randomly desynchronized from time to=20 time because the total sum of the cwnds for the competing flows at the en= d=20 of the cycle does not necessarily match the buffering capacity of the pat= h. This, however, is not a big problem for the model because competing flows=20 alternate such that each flow encounters a longer cycle more or less=20 randomly. A flow having a longer cycle is then later pushed towards the=20 correct awg cwnd. In the long run the cycle lengths (=3D drop probability= )=20 averages to be the same, and very importantly, there is no systematic=20 bias. Thanks, /Markku Bob Briscoe wrote: > Markku, Yoshi, >=20 > As promised, I've tried to develop the maths to derive the additive inc= rease factor for the > Reno-Friendly mode of Cubic. I did it for two cases: > * synchronized (tail-drop) > * desynchronized (AQM) >=20 > I've written a short LaTeX report and uploaded here: > =A0=A0=A0 https://raw.githubusercontent.com/bbriscoe/cubic-reno/main/cr= eno_tr.pdf > If Markku and others review it, I'll update it with any corrections, an= d 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 anyt= hing in the summary. >=20 > Tail Drop case > * This turned out to be straightforward, and ended up with the same f= ormula as in RFC8312 (which > came from [FHP00] which assumed /non/-tail-drop!). > * I believe my derivation is straightforward and rigorous and it does= n'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 a= s Reno: > + I've explained why C-Reno would suffer more than Reno if the bu= ffer was not deep enough to > take the combined synchronized decreases without draining out c= ompletely. > + but I haven't proved this empirically by trying with a deeper b= uffer (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 form= ula in RFC8312, at least for > tail drop scenarios, which are (sadly) still likely to be prevalent. >=20 >=20 > 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 incorre= ct for the AQM case, which is > more deeply thought-through than my earlier emails: > + my critique seems similar to Markku's and it is possible it's t= he same, but there's not > enough explanation in Markku's emails to know for sure. > + @Markku, perhaps you can see if what I've written describes wha= t 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 beyon= d me, and the results in > [FHP00] are still=A0the opposite of what I'd expect. >=20 >=20 > Bob >=20 > On 17/09/2021 10:06, Yoshifumi Nishida wrote: > Hi Bob, >=20 > Thanks for the comments. > I at least think we both can agree that the draft uses [FHP00] as the b= asis of their AIMD or > NewReno model. > If you have any suggestions to update the texts to address your concern= s, please share. (but, > in this case, using github might be straightforward.) > =A0 > Unfortunately, I'm not sure about the empirical=A0evidence to support t= he formula.=A0 > 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=A0issues might not be too = obvious at least. > If you have any specific concerns in the formula, could you share?=A0 >=20 > Thanks, > -- > Yoshi=A0 >=20 >=20 > On Mon, Sep 13, 2021 at 4:17 PM Bob Briscoe wrote= : > Yoshi, > > On 11/09/2021 22:02, Yoshifumi Nishida wrote: > Hi Bob, >=20 > Thanks for the very detailed explanation.=A0 > I agree with some of your points. But, I have two comments on this. >=20 > The first point is about RTT variation.=A0 > I think you have a point there, but I personally think=A0the paper pres= umes 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 wi= ll be > mostly the same. >=20 >=20 > [BB] The paper gets the same answer as I got under assumption #3 (all s= awtooth 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 th= ink it is > too broad as a scope of this document. It looks a very deep resea= rch topic > to me. > I think the model is basically derived=A0from Equation-based Congestion = Control > paper in sigcomm 2000. If we want to update or renew it, we might need = another > RFC5348. >=20 >=20 > [BB] I didn't use Equation-based CC at all and, at least under one of m= y three > assumptions, I got the same result as the [FHP00] paper (with one furth= er assumptions > about how many drops there are at the top of different sawteeth). >=20 > I just wanted to check the outcome wouldn't be different if I used a mo= del 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 sam= e result as one > of my cases just using basic AIMD sawtooth geometry, at least in this o= ne case, the > varying RTT doesn't make any difference. >=20 > Nonetheless, I think you're right that deriving the correct formula wou= ld involve deeper > research. I don't think publication of the RFC should block on that res= earch. > > So, I think it would be better for this doc to use the model as i= t is and > leave its enhancements for future discussions. >=20 >=20 > [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 C= ubic that it uses > from that paper is correct, when it clearly doesn't produce the desired = result, even in > the paper that proposed it. >=20 >=20 > The second point is =E1 in the draft might be too big. >=20 >=20 > [BB] How so? The paper's own simulations (exploring a very limited spac= e) conclude that > =E1 from the model is more than 2x too small. > > During my WGLC review, I read [FHP00] once and I had similar thou= ghts. > But, after I re-read the paper several times, I start having a differen= t > interpretation.=A0 >=20 > First off, it is very clear that =E2=3D0.7 is more aggressive than =E2 = =3D0.5 when there's > no other traffic. > As cwnd growth is linear, if there's enough long time for the data tran= sfer, the > average cwnd for =E2 =3D0.5 will be (1.0=A0+ 0.5)/2 =3D 0.75 Wmax and i= t will be (1.0=A0+ > 0.7)/2 =3D 0.85 Wmax=A0for =E2=3D0.7. >=20 >=20 > [BB] Correct > > So, it is obvious that this model does not aim for the cases wher= e there's > no other traffic. >=20 >=20 > [BB] It is certainly obvious that comparing flow rates is not about sin= gle flows. >=20 > But, by the same token, does it mean anything to say a flow is 'more ag= gressive when > there's no other traffic'? > You can have different cwnd for the same throughput, if the avg queue d= elay is higher > and therefore RTT is higher.=A0 But I don't think that says anything ab= out aggression. If > anything, aggression is about shorter recovery time. >=20 > Yes, the analysis I used was for each flow on its own. When they are no= t on their own, > but competing in the same queue, (obviously) there cannot be two differ= ent 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 f= inal word by any > stretch of the imagination. However, if on their own they have differen= t recovery times, > then when together A will be pulling B away from its natural recovery t= ime and towards > A's recovery time, and vice versa. >=20 >=20 > I believe the choice of (=E1,=A0 =E2) in [FHP00] is designed to be more = or less fair > only when it competes with (=E1=3D1.0,=A0 =E2 =3D0.5) > Hence, I think we should not apply the loss rate for no-other-traffic s= ituation to > the formula, which can lead to =E13=A0=3D 0.20 > Instead, I am thinking we can think in this way.. >=20 > (=E1=3D1.0,=A0 =E2 =3D0.5) model oscillates between 0.5 W1 and 1.0 W1 i= n a congestion epoch. > (=E1=3DX,=A0 =E2 =3D0.7) model oscillates between 0.7 W2 and 1.0 W2 in = the same congestion > epoch. > =A0 where W1 is max window for (=E1=3D1.0,=A0 =E2 =3D0.5), W2 is max wi= ndow for (=E1=3DX,=A0 =E2 =3D0.7) > When these two models have the same loss ratio, it should satisfy (1.0=A0= + 0.5) W1 =3D > (1.0=A0+ 0.7) W2=A0 =A0 >=20 > Also, in one congestion epoch, (=E1=3D1.0,=A0 =E2 =3D0.5) increases 0.5 = W1 while (=E1=3DX,=A0 =E2 > =3D0.7) increases 0.3 W2 > Now, if=A0we define the congestion epoch as e RTTs, e =3D 0.5 W1 / 1.0=A0 = and also e =3D > 0.3 W2 / X > This means, X should satisfy > =A0 0.5 W1 /1.0=A0 =3D 0.3 * 1.5/1.7 W1/ X > then we get X =3D 0.529. >=20 >=20 > [BB] This is the same equation as in [FHP00], but with numbers not vari= ables. 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 techniqu= e to compare the > geometry of the sawteeth. >=20 > But is there empirical evidence to support this formula, given the simu= lations in the > paper itself don't support it? That's the question. >=20 > Also, I'd like to hear Markku's response to your original question to h= im. I was only > trying to second-guess what he was trying to say. >=20 >=20 > Bob >=20 >=20 >=20 > This will mean if we launch (=E1=3D1.0,=A0 =E2 =3D0.5) and (=E1=3D0.529= ,=A0 =E2 =3D0.7) at the same > time and reduce them when the sum of their windows becomes Wmax, the th= roughput of > them will mostly be the same. > -- > Yoshi > =A0 > On Tue, Sep 7, 2021 at 5:17 AM Bob Briscoe wrote: > Yoshi, > > You recently asked Markku for an explanation of his point #4. > > Coincidentally, a few weeks ago, I was checking the formula in RF= C8312 > 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 explainin= g 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 go= ing > 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 > > =A0=A0 The equation on page 12 to derive increase factor =E1_cubi= c > that > =A0=A0 intends to achieve the same average window as AIMD TCP see= ms > to > =A0=A0 have its origins in a preliminary paper that states that t= he > =A0=A0 authors do not have an explanation to the discrepancy betw= een > =A0=A0 their AIMD model and experimental results, which clearly > deviate. > =A0=A0 It seems to have gone unnoticed that the equation assumes > equal > =A0=A0 drop probability for the different values of the increase > factor > =A0=A0 and multiplicative decrease factor but the drop probabilit= y > =A0=A0 changes when these factors change. >=20 >=20 > [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. >=20 > 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. T= his > 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: >=20 > I've taken three possible alternative assumptions, with their resulting > additive increase factors for theoretical equality with Reno (I've give= n all > the derivations at the end of this email): > #1) All sawteeth have the same Rmin: =E1 ~=3D (1/=E22 - 1) / 3;=A0=A0=A0 = =A0=A0=A0 Example: =E2 > =3D 0.7; =E1 ~=3D 0.35 > #2) All sawteeth have the same Rmax: =E1 ~=3D 4(1-=E22) / 3;=A0=A0=A0 =A0= =A0=A0 =A0=A0=A0 Example: =E2 > =3D 0.7; =E1 ~=3D 0.68 > #3) All sawteeth have the same Ravg: =E1 ~=3D 3(1-=E2) / (1+=E2);=A0=A0= =A0=A0=A0=A0=A0 Example: =E2 > =3D 0.7; =E1 ~=3D 0.53=A0=A0=A0 <=3D=3D used in [FHP00] and therefore i= n RFC8312 >=20 >=20 > 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 magi= c AQM > was invented that minimized the standing queue. > I don't think any of the assumptions are good models of C-Reno's intera= ction > with CoDel. >=20 > 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 ass= umes > deterministic marking; i.e. that that each flow experiences just one dr= op or > mark at the top of each sawtooth. If that applies at all, it only appli= es to > AQMs, not to tail-drop buffers that tend to drop more than one packet a= t a > time. Nonetheless, for the purpose of rate comparison, all the flows wi= ll > share the same bottleneck. So if flow rates are equal under a certain A= QM, > they might be equal under tail-drop too (see {Note 1} at the very end). >=20 > I would still like to say 'none of the above' because Linux C-Reno has = been > widely used with =E1=3D1, =E2=3D0.7 for many years now without the sky = falling. So > it's questionable whether friendliness should be defined relative to Re= no. > Otherwise, from day 1, RFC8312bis will be stating the forlorn hope that > Linux C-Reno should regress to become less aggressive than its former s= elf, > just to be friendly to Reno, which apparently barely exists any more > (according to the Great TCP Congestion Control Census of 2019 [MSJ+19])= . >=20 > 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 =E1 fo= r > C-Reno defined in RFC8312. >=20 > (FAQ: Why does C-Reno add <1 segment per RTT to be friendly to Reno, wh= ich > adds 1 segment per RTT? > C-Reno in the RFC multiplicatively decreases cwnd to 0.7*cwnd on a loss > (multiplicative decrease factor =E2=3D0.7), whereas Reno uses =E2=3D0.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 (=E1) than 1 segment. Using =E1= <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 s= low > linear increase has made the queue large enough to come out of its > 'TCP-Friendly' mode.) >=20 > Whatever, rfc8312bis certainly shouldn't refer solely to [FHP00] withou= t > caveats. >=20 > 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 ar= e out > by about 2x. The paper used =E2=3D7/8. So, from the theory, for each of = the > above three assumptions, the additive increase factor would have had to = be: > =E11 =3D 0.10 > =E12 =3D 0.31 > =E13 =3D 0.20 > They used a RED AQM (which should be somewhere between assumption #2 & = #3). > But they had to configure C-Reno with =E1=3D0.4 to get close to equal f= low rates > with Reno > Using my 'finger in the air' modification to the formulae in {Note 1}, = =E13 =3D > sqrt(0.20) =3D 0.44, which would have been about right (perhaps only > coincidentally). >=20 > The question over what =E1 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 =E1. Assumption#= 2 is > probably the 'most correct', and also happens to give the highest value = of =E1 > for the 'TCP-Friendly' region (=E1=3D0.68 when =E2=3D0.7). > (By my unsubstantiated formula in {Note 1}, =E12 =3D sqrt(0.68) =3D 0.8= 2.) >=20 > If we look for an empirical value of =E1 that gives reasonably equal fl= ow > rates against Reno, I suspect we will get all sorts of different answer= s > 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 w= ant > to take this path, feel free, but if you're still on it in a year's tim= e, > don't say I didn't warn you. >=20 >=20 > Derivations of the above three formulae follow at the end. > > The equations for the drop > =A0=A0 probability / the # of packets in one congestion epoch > =A0=A0 are available in the original paper and one can easily ver= ify > =A0=A0 this. Therefore, the equations used in CUBIC are not corre= ct > =A0=A0 and seem to underestimate _W_est_ for AIMD TCP, resulting = in > =A0=A0 moving away from AIMD-Friendly region too early. This give= s > =A0=A0 CUBIC unjustified advantage over AIMD TCP particularly in > =A0=A0 environments with low level of statistical multiplexing. W= ith > =A0=A0 high level of multiplexing, drop probability goes higher a= nd > =A0=A0 differences in the drop probablilities tend to get small. = On > the > =A0=A0 other hand, with such high level of competition, the > theoretical > =A0=A0 equations may not be that valid anymore. > > /Markku >=20 >=20 > [BB] Derivations of the formulae for =E1 under the three different assu= mptions > follow. It's possible/likely that this is all already in a paper somewh= ere, > but I haven't been able to find one. > > 0) Preparatory material >=20 > 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 multiplicativ= e > decrease. >=20 > The overall approach is: > A) Find a formula in terms of the AI and MD factors (=E1 & =E2), for th= e > recovery time of C-Reno. > B) Equate this to the recovery time of Reno, which will produce a formu= la > for the additive increase factor, =E1. >=20 > 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 t= he > number of rounds per cycle, J. > 2) Then J is found by writing two formulae; > =A0 2a) one for the average sawtooth decrease > =A0 2b) and the other for the increase. > Then by assuming a steady state the two can be equated. > Here goes... >=20 > The following formula gives the recovery time, Tr, from one max window = to > the next, in C-Reno with: > * additive increase (AI) factor =E1 [segment / RTT] > * and packet-rate r [packet / s] > assuming that the minimum window of each sawtooth still fully utilizes = the > link. > =A0=A0=A0 Tr =3D =D3J-1j=3D0=A0 =A0 (Rmin + j=E1/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 th= at > the queue grows by =E1 fractional packets in each round, and the queue = delay > per packet is 1/r (seconds per packet is reciprocal of packets per seco= nd). > The sum of all the second terms forms an arithmetic progression, the su= m of > which is given by the well-known formula, as follows: > =A0=A0 =A0 =A0=A0=A0 =3D J.Rmin + J(J-1)=E1/2r > =A0=A0=A0 =A0=A0 ~=3D J.Rmin + J2=E1/2r.=A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 (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= =3D1/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. >=20 > 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: > =A0=A0=A0 (Rmax - Rmin) =3D J=E1/r,=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 = =A0=A0=A0 =A0=A0=A0 =A0=A0=A0=A0=A0=A0=A0=A0 (2a) > Or by the multiplicative relationship between the max and min RTTs, by = the > definition of =E2: Rmin =3D =E2.Rmax. > =A0=A0=A0 (Rmax - Rmin) =3D (Rmin / =E2) - Rmin > =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0 =3D Rmin(1-=E2)/=E2 =A0=A0 =A0=A0=A0=A0=A0 =A0=A0=A0 =A0=A0 (2b= ) > Equating (2a) and (2b): > =A0=A0=A0 J =3D r.Rmin(1-=E2) / (=E1=E2) =A0=A0 =A0=A0=A0 =A0=A0=A0 =A0= =A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0=A0=A0=A0=A0=A0=A0 (2) >=20 > Substituting for J from (2) in (1): > =A0=A0=A0 Tr =3D r.Rmin2 (1-=E2) / (=E2=E1) + r.Rmin2 (1-=E2)2/(2=E22=E1= ) > =A0=A0=A0 =A0=A0=A0=A0 =3D r.Rmin2 (1-=E2) / (=E2=E1) * (1 + (1-=E2)/2=E2 = ) > =A0=A0=A0 =A0=A0=A0=A0 =3D r.Rmin2 (1-=E2)(1+=E2) / (2=E22=E1) > =A0=A0=A0 =A0=A0=A0=A0 =3D r.Rmin2 (1-=E22) / (2=E22=E1)=A0=A0=A0=A0 =A0= =A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0= =A0 (3) > And, because Rmin =3D =E2.Rmax. > =A0=A0=A0 Tr =3D r.Rmax2 (1-=E22) / (2=E1)=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0 =A0 =A0 =A0 =A0 =A0=A0=A0=A0=A0=A0=A0=A0 =A0 = =A0 (4) >=20 > The well-known steady-state Reno formula from [FF99] is: > =A0=A0=A0 rReno ~=3D (1/Ravg) sqrt(3 / 2p)=A0=A0=A0 =A0=A0=A0 =A0=A0=A0 = =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 > =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 (5) > assuming deterministic marking (which is also assumed for the above mod= el of > C-Reno). >=20 > Assuming a Reno sawtooth is approximately linear, the average RTT of a = Reno > flow, > =A0=A0=A0 Ravg ~=3D (Rmax + Rmin)/2 > and > =A0=A0=A0 Rmin =3D Rmax/2 > Therefore > =A0=A0=A0 rReno ~=3D (1/Rmin) sqrt(2 / 3p)=A0=A0=A0 =A0=A0=A0 =A0=A0=A0 = =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 > =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 (6) > =A0=A0=A0 rReno ~=3D (1/Rmax) sqrt(8 / 3p)=A0=A0=A0 =A0=A0=A0 =A0=A0=A0 = =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 > =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 (7) >=20 > With the preparatory material done, next we take each of the three > assumptions, one at a time. > > #1) All sawteeth have the same Rmin=A0 >=20 > From Eqn (3): > =A0=A0=A0 Tr =3D r.Rmin2 (1-=E22) / (2=E22=E1) > Total packets sent over period Tr is r.Tr during which time assume 1 pa= cket > is lost (or marked) at the sawtooth peak {Note 1}. So loss probability: > =A0=A0=A0 p =3D 1 / r.Tr > Substituting for Tr and rearranging : > =A0=A0=A0 r2 =3D 2=E22=E1 / Rmin2 (1-=E22)p > =A0=A0=A0 r =3D (=E2/Rmin) sqrt(2=E1 / (1-=E22)p) > Equating the Reno packet rate, rReno, from eqn (6) to the C-Reno packet > rate, r, for all =E1 and =E2: > =A0=A0=A0 r =3D rReno > =A0=A0=A0=A0=A0=A0 =3D (1/Rmin) sqrt(2 / 3p). > Therefore, > =A0=A0=A0 (1/Rmin) sqrt(2 / 3p) ~=3D (=E2/Rmin) sqrt(2=E1 / (1-=E22)p) > Rearranging > =A0=A0=A0 2/3 ~=3D 2=E1=E22 / (1-=E22) > =A0=A0=A0 =E1 ~=3D (1-=E22)/3=E22 > =A0=A0=A0=A0=A0=A0 ~=3D (1/=E22 - 1) / 3=A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0= =A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0= =A0 =A0=A0=A0 =A0=A0=A0 > =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 (= 8) > > #2) All sawteeth have the same Rmax =3D Rmin / =E2 >=20 > From Eqn (4): > =A0=A0=A0 Tr =3D r.Rmax2 (1-=E22) / (2=E1) > As before, after substituting for Tr and rearranging: > =A0=A0=A0 p =3D 1 / r.Tr > =A0=A0=A0 r =3D (1/Rmax) sqrt(2=E1 / (1-=E22)p) > Equating to rReno from eqn (7) for all =E1 and =E2, > =A0=A0=A0=A0=A0 ~=3D (1/Rmax) sqrt(8 / 3p). > Rearranging > =A0=A0=A0 8/3 ~=3D 2=E1 / (1-=E22) > =A0=A0=A0 =E1 ~=3D 4(1-=E22) / 3 =A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0= =A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0= =A0 =A0=A0=A0 =A0=A0=A0 > =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 (9) > > #3) All sawteeth have the same Ravg >=20 > Ravg =3D (Rmax + =E2Rmax )/2 > =A0=A0=A0 =A0=A0=A0=A0 =3D Rmax (1+=E2)/2 > From Eqn (4): > =A0=A0=A0 Tr =3D r.Rmax2 (1-=E22) / (2=E1) > =A0=A0=A0=A0=A0=A0=A0=A0 =3D 2r.Ravg2 (1-=E2) / =E1(1+=E2) > As before, after substituting for Tr and rearranging: > =A0=A0=A0 p =3D 1 / r.Tr > =A0=A0=A0 r =3D (1/Ravg) sqrt(=E1 (1+=E2) / 2(1-=E2)p) > Equating to rReno from eqn (5) for all =E1 and =E2, > =A0=A0=A0=A0=A0 ~=3D (1/Ravg) sqrt(3 / 2p). > Rearranging > =A0=A0=A0 3/2 ~=3D =E1(1+=E2) / 2(1-=E2) > =A0=A0=A0 =E1 ~=3D 3(1-=E2) / (1+=E2)=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 = =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0= =A0=A0 =A0=A0=A0 =A0=A0=A0 > =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 =A0=A0=A0 (10) >=20 > This last formula is same as the equation used for C-Reno in RFC8312 an= d in > the RFC8312bis=A0draft. >=20 >=20 > {Note 1}: The assumption in [FHP00] of deterministic marking is suspect = for > the Internet (meaning that the spacing between drops or marks is even a= nd > 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 bet= ter > not to assume the actual average number dropped (or marked) is known, b= ut > instead assume the ratio of the average drops or marks between C-Reno a= nd > Reno will be roughly proportional to their AI factors. This would modif= y the > formula for C-Reno's drop probability to: > =A0=A0=A0 p =3D =E1Reno / =E1C-Reno.r.Tr > Substituting =E1Reno =3D 1: > =A0=A0=A0 p =3D 1 / =E1C-Reno.r.Tr > This would modify all the results to: >=20 > #1) All sawteeth have the same Rmin: =E1 ~=3D sqrt( (1/=E22 - 1) / 3 );= =A0=A0=A0 =A0=A0=A0 > Example: =E2 =3D 0.7; =E1 ~=3D 0.59 > #2) All sawteeth have the same Rmax: =E1 ~=3D sqrt( 4(1-=E22) / 3 );=A0= =A0=A0 =A0=A0=A0 =A0=A0=A0 > Example: =E2 =3D 0.7; =E1 ~=3D 0.82 > #3) All sawteeth have the same Ravg: =E1 ~=3D sqrt( 3(1-=E2) / (1+=E2) = );=A0=A0=A0=A0=A0=A0=A0 > Example: =E2 =3D 0.7; =E1 ~=3D 0.73 >=20 > However, these would then be wrong where there really is deterministic > marking. >=20 > References > =3D=3D=3D=3D=3D=3D=3D=3D=3D > [FHP00]=A0=A0=A0 Floyd, S., Handley, M., and J. Padhye, "A Comparison o= f > Equation-Based and AIMD Congestion Control", May 2000,=A0 > >=20 > [MSJ+19] Ayush Mishra, Xiangpeng Sun, Atishya Jain, Sameer Pande, Raj J= oshi, > and Ben Leong. The Great Internet TCP Congestion Control Census. Proc. = ACM > on Measurement and Analysis of Computing Systems, 3(3), December 2019 >=20 > [FF99] Sally Floyd and Kevin Fall, "Promoting the Use of End-to-End > Congestion Control in the Internet", IEEE/ACM ToN (1999) >=20 >=20 > Bob >=20 > --=20 > ________________________________________________________________ > Bob Briscoe http://bobbriscoe.net/ >=20 >=20 > --=20 > ________________________________________________________________ > Bob Briscoe http://bobbriscoe.net/ >=20 >=20 > --=20 > ________________________________________________________________ > Bob Briscoe http://bobbriscoe.net/ >=20 > --=_script-9346-1647967626-0001-2--