Re: [tcpm] alpha_cubic (Issue 1)

[Bob Briscoe <[e-mail]>]

Markku,

See [BB] inline..
Sry - I marked your email from March'22 below as ToDo, then  it got lost 
in my ToDo list.

On 22/03/2022 16:47, Markku Kojo wrote:
> 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). 
> This hopefully also clarifies what I meant when saying that the 
> equation [in the draft] assumes equal drop probability for the 
> different values of alpha and beta but the drop probability actually 
> changes when these values are changed from alpha=1, beta = 0.5. I have 
> also thought this a bit more after reading Bob's report and include my 
> understanding of why the performance with C-Reno and Reno differ in 
> case of AQM.
>
> In brief, the model for steady state behavior for the Reno-friendly 
> region in a tail-drop queue indeed is incorrect when the additive 
> increase factor alpha < 1 is applied for an alternate AIMD(a, b) TCP. 
> This is because the packet dynamics and behavior of TCP that injects 
> more packets only when cwnd has increased by at least one MSS. This 
> differs from the assumptions of the model and what Bob has used in his 
> analysis (see more below). Also the AQM case remains unvalidated, my 
> reasoning differs, or extends, somewhat the reasoning that Bob gave in 
> his report.
>
> The math itself in the original paper [FHP00] which the CUBIC 
> TCP-friendly region is based on seems correct, likewise the math in 
> Bob's report as well as in Yoshi's explanation below:
>
>>  Yoshifumi Nishida <[e-mail]> wrote:
>>
>> 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.
>
>> 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.
>
> I'll try to explain the problems with the model separately for a 
> tail-drop and AQM queue.
>
> 1. Tail-drop queue (*)
>
> The problem with the use of the formula in the original paper as well 
> as in Bob's and Yoshi's analyses is, like it often easily happens, 
> that the theoretical model that has been derived in one context using 
> certain assumptions is reused in another context where the assumptions 
> do not hold, i.e, the model does not match the reality.
>
> In this case, the correct use of formula presumes that the drop 
> probability is the same (on the average) for a standard TCP = 
> AIMD(1,1/2) and AIMD(a,b). That is implicitly assumed also in Bob's 
> report for synchronized (tail drop) case as Bob's math is derived 
> using the same number of packets over a cycle (= in between drops, 
> which is reciprocal of drop rate). 

[BB] That's incorrect I'm afraid (*#1*). I was careful not to assume the 
same drop probability. Quoting from the assumptions that I stated:

        All the flows are synchronized so that, when-
        ever one flow experiences loss the others do too.
        No assumption is made about how much loss
        occurs at each congestion event, except that
        all flows experience it and they only respond
        to the presence of loss, not its extent.

The two parts of loss probability are:
___no. of losses per event _
     number of packets between events.

Both top and bottom can be different for each flow under the above 
assumptions.
So there was no assumption of same loss probability here.

Nonetheless, below I relax the only assumption ("all flows experience 
it") that is occasionally not true (i.e. an approximation).

> (Btw, involving RTT in the calculations is unnecessary as all 
> competing flows see the same queue on every RTT, so RTT is the same 
> for all flows sharing the same queue, assuming the base RTT for the 
> flows is the same). Also, Yoshi's calculations above effectively make 
> the same assumption that both flows reduce cwnd at the same time 
> ("when the sum of their windows becomes Wmax").

[BB] This is also incorrect (*#2*). In the time of one cycle, a flow 
with a shorter RTT would increase more than a longer RTT flow of the 
same type. So the balance would be different.

>
> To understand the difference, we need to look at the packet dynamics 
> of flows competing in a tail drop queue, not just the math. The 
> assumption of equal drop probability holds for any two (or n) AIMD(1, 
> 1/2) TCPs competing on a shared bottleneck: when the bottleneck tail 
> drop buffer becomes full towards the end of a cycle (on RTT n), both 
> TCPs increase their cwnd by 1 for the RTT n+1 and inject two 
> back-to-back pkts resulting in a drop of 1 pkt each (the latter pkt of 
> the two back-to-back pkts = the excess pkt according to packet 
> conservation rule becomes dropped). When an AIMD(1, 1/2) TCP competes 
> with an AIMD(a=0.53, b=0.7) TCP (=CUBIC) and the tail drop buffer 
> becomes full on RTT n, the AIMD(1,1/2) TCP increases its cwnd by 1 on 
> RTT n+1 and gets 1 pkt dropped. However, AIMD(0.53,0.7) TCP increases 
> its cwnd by 0.53 and only injects an excess packet on RTT n+1 roughly 
> every second cycle because a TCP sender does not inject an additional 
> packet until cwnd has increased by at least by 1 MSS.
>
> Hence, in a synchronized case the AIMD(0.53, 0.7) TCP avoids a packet 
> drop and cwnd reduction roughly every second cycle and is able to 
> extend its cycle because the competing AIMD(1, 1/2) TCP reduced its 
> cwnd on RTT n+1 and the bottleneck buffer is not anymore full on RTT 
> n+2 when AIMD(0.53,0.7) TCP injects its additional packet (and would 
> encounter a pkt drop only if the queue is full). Because the cycle is 
> systematically extended in this way for AIMD(0,53, 0.7) (=CUBIC in 
> Reno-friendly mode), it increases the average number of pkts between 
> drops and thereby decreases the drop probility of CUBIC to be lower 
> than that of the competing AIMD (1, 1/2) TCP. These packet dynamics 
> breaks the model.

[BB] The likelihood of a flow experiencing a loss is not dependent on 
how much the flow /itself/ increases per round. Once the buffer is full, 
the probability that any one flow catches the next loss depends only on 
its packet arrival rate relative to the total packet arrival rate. The 
buffer doesn't know which flow is increasing the queue more than 
another. So all the above para is also incorrect (*#3*).

Nonetheless, you are right that a packet-level analysis is necessary.
Let's consider two flows: 1 Reno and 1 CUBIC in Reno-Friendly mode 
(CReno), and we're still assuming equal RTTs. The queue grows by (1 + 
0.53) seg/RTT between responses to losses. Once the buffer is full, one 
packet has to be dropped, but the queue continues to grow by 1.53 
segments during the next round trip (until the resulting response 
reaches the queue). So it is likely that another packet will have to be 
discarded within the same RTT as the first. The ACK clock is rarely 
completely smooth and even, so this should be thought of as a 
probabilistic process with mean 1.53, not a completely smooth growth 
with either 1 or 2 losses.

As I just said, the likelihood that one flow catches one of the losses 
depends on its packet rate relative to the other.
If the flows both have the same average window
     (which is the goal we are aiming for, as drawn in Fig 1 of the 
paper at 
https://raw.githubusercontent.com/bbriscoe/cubic-reno/main/creno_tr.pdf )
then, by triangle geometry, the ratio between the packet rates of the 
two flows when they both reach their max is
     r_r/r_c = (1 + b_c) / (1 + b_r)
                  = 1.7/1.5
                ~= 1.13.

Incidentally, you said the ratio of Reno to Cubic drops is 1 / 0.53 = 
1.9, which is also incorrect (*#4*) and greatly exaggerated compared to 
1.13.

So, when a loss occurs:
     p_r + p_c = 1             (1)
     p_r / p_c = 17/15     (2)
Therefore
     p_r = 17/32 ~= 53%
     p_c = 15/32 ~= 47%
So, if there are 2 losses for instance, the probabilities of each 
combination of the two losses within the round of the congestion event is:
     p_rr               = 53% * 53%                     = 28%
     p_rc or p_cr = 53%*47% + 47%*53% = 50%
     p_cc              = 47% * 47%                     = 22%

When the same flow is hit twice in the same round, it doesn't reduce any 
more than if it's hit once, but the other flow doesn't reduce at all (if 
there are no more than two losses in the round). So CReno is somewhat 
more likely than Reno to not get hit in some rounds. In such cases, only 
the Reno flow would reduce, then the queue would continue to grow by 
1.53 pkt/RTT, so the next cycle would be shorter and the CReno flow 
would be much more likely to be hit when it next filled the buffer --- 
and more likely to be hit twice.

It would be possible to calculate the average rate of each type of flow 
by calculating the probabilities of each chain of events 
programmatically. However, such precision is unnecessary. For the case 
of tail-drop buffers, it will be sufficient to say:
* either that the AI factor of CReno should be slightly lower than 0.53 
to make CReno and Reno flow rates more precisely equal;
* or that the average rate of CReno flows will be slightly higher in 
comparison with Reno flows, if 0.53 is used.
Here, `slightly''  means roughly within a 10% margin of error.

>
> So, the basic problem is that the model used for the Reno-friendly 
> region obviously is not valid. 

[BB] Why are you so keen to exaggerate? We've found that the model in 
the original paper is not exact, but it's a reasonable approximation. 
Why the need to make out that the sky is falling?

> The results in the original paper [FHP00] do not support the validity 
> of the model either and I am not aware that the model would have been 
> validated by anyone.
>
> A good, unresolved question is why the simulation results in the 
> original paper [FHP00] gave lower throughput for AIMD(1/5, 7/8) 
> (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 a tail drop bottleneck as the results in the paper were shown 
> only for an AQM bottleneck and the paper just said the results for 
> tail drop are similar which is a vague expression; it may also mean 
> that he results were reversed with similar difference in throughput? 
> Anyway, the results obviously did not validate the model.

[BB] Yes, the simulations in that paper are hard to explain. They used 
RED, which we no longer use, so they're not interesting anyway. I wrote 
a short alternative report that we can use instead. We don't need to 
hold up this draft because of a suspect 22-year old paper that we don't 
need to refer to any more. Let's move on please.

>
> Bob's explanation for the reason why C-Reno's packet rate decreases is 
> correct but what would happen if the buffer was not deep enough and 
> drained out seems not all correct. The packet rate is the relative 
> share on a shared bottleneck link with fixed capacity. The cwnd of the 
> C-Reno flow is larger than that of Reno in the beginning of the cycle, 
> becomes equal in the middle, and stays increasingly behind for the 
> rest of the cycle. Therefore, C-Reno's *proportional* share decreases 
> during the cycle; the overall througput is the same all the time and 
> bounded by the link capacity.
>
> If the buffer was not deep enough and drained out, the relative packet 
> rate between the two flows still behaves the same even if there is no 
> queue and also when the link is underutilized for the beginning of the 
> cycle. When the link is underutilized, the pkt rate increases for both 
> flows until the link becomes fully utilized (note that RTT does not 
> change when the link is underutilized). The pkt rate of C-Reno would 
> increase slower though but it won't change its proportinal share, 
> i.e., C-Reno will not suffer more unlike Bob suggests. The overall 
> average rate is lower in such a case because the link is underutilized 
> for the beginning of the cycle.

[BB] I don't quite know what you mean by "the relative packet rate 
between the two flows still behaves the same." The packet rates do not 
behave the same, but I think you mean that the ratio between them stays 
the same. I've now modelled this aspect as well (added to the paper), 
and I now agree that, although the Reno flow rate reduces by a greater 
absolute amount during the first part of the cycle, the ratio between 
the flow rates at each instant in the cycle does not change, so the 
ratio between the averages isn't altered if the buffer isn't deep enough 
to hold both sawteeth stacked on top of each other.

>
> AQM queue:
>
> Bob's explanation for AQM case seems pretty much being on the correct 
> track.
>
> In the AQM case the desynchronization of the flows is merely 
> guaranteed for low level of multiplexing. I agree with Bob that 
> modelling AQM case is hard and it also depends on the AQM in use. I 
> also agree Bob's analysis that towards the end of a cycle a 
> probabilistic AQM is more likely to hit Reno somewhat more often than 
> C-Reno. On the other hand, with desynchronized flows the AQM may hit 
> any flow irrespective of its phase. Therefore, the AQM is more likely 
> to hit C-Reno towards the beginning of its cycle somewhat more often 
> than Reno because C-Reno's pkt rate is then higher than that of Reno, 
> and a hit in the beginning of the cycle hurts the performance much 
> more than in the end of the cycle. A hit in the beginning of the cycle 
> results in a cwnd value that is significantly lower than in the 
> beginning of the previous cycle while a hit towards the end of cycle 
> results in a cwnd value much closer to that in the beginning of the 
> previous cycle (the behavious the resembles steady state regular 
> cycle). This might explain, at least in part, the lower throughput for 
> C-Reno in AQM case.

[BB]
[Aside: In other work, we have found that, with the smaller BDPs of the 
past, the AQM's response time was longer than the sawtooth cycles, so it 
could hit at any part of a sawtooth cycle. Whereas, with today's higher 
BDPs, the duration of Reno and CReno sawtooth cycles are longer, so AQMs 
tend to have time to reduce loss probability during the valley of a 
sawtooth, and only introduce loss (or ECN) when the sawteeth have caused 
the queue to slowly approach the operating point of the AQM. See Fig 3 
in this tech report: https://arxiv.org/pdf/2107.01003 ]

As I said during the tcpm meeting, we've run some experiments recently 
that happen to compare CUBIC-Reno with Reno. They happened to be on one 
of my slide for ICCRG the day before. They show that C-Reno and Reno 
have nearly identical sharing behaviour over a PIE AQM, for a large 
selection of different numbers of flows.

I've updated the report I wrote to try to resolve issue with the Floyd 
paper:
https://raw.githubusercontent.com/bbriscoe/cubic-reno/main/creno_tr.pdf
You'll see it now includes:
* a model of the shallow buffer case (Fig 2)
* discussion of the limitations of the synchronized loss assumption, 
using the text I've just written earlier in this email.
* plus these empirical results with a PIE AQM (Fig 4) from our ICCRG 
presentation.

>
> I think that an additional possible explanation for the discrepancy in 
> the original paper is that possibly something was wrong with the 
> simulation implementation, or maybe in the simulation parameters. Not 
> all parameters were exposed in the paper. The results also seem not to 
> involve any replications, so we cannot expect statistical validity 
> from 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 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 
> probabilities are the same. Moreover, the role of RTOs is definitely 
> one potential reason with the high number of competing flows as the 
> model considers the regular steady-state only.
>
> So, in summary, the AQM case clearly remains unvalidated as well, or 
> the validation in the original paper actually shows that the model is 
> not correct.
>
> An additional problem with the incorrect model is that it tends to 
> result is overaggressive CUBIC behaviour regardless of whether the 
> model yields too low or too high throughput (cwnd) for CUBIC sender in 
> the Reno-frindly region: if the model yields too low throughput, the 
> CUBIC sender leaves the Reno-friendly region too early and becomes 
> (much) more aggressive actual Reno sender would; otherwise, if the 
> model yields too high throughput, the CUBIC sender is too aggressive 
> throughout the Reno-friendly region.

[BB] Let's move on from that paper. We cannot know what was wrong 22 
year ago; the way forward is to run current experiments.

That's what we've done for the AQM case.
If someone does some experiments with a tail-drop buffer, I can add the 
results to that paper. Then submit it to ArXiV so that it is a 
sufficiently stable reference for the RFC Editor to use.


Bob

>
> (*) Note:
>
> The tail drop case in not always synchronized for competing Reno CC 
> flows either. Flows get more or less randomly desynchronized from time 
> to time because the total sum of the cwnds for the competing flows at 
> the end of the cycle does not necessarily match the buffering capacity 
> of the path.
> This, however, is not a big problem for the model because competing 
> flows alternate such that each flow encounters a longer cycle more or 
> less randomly. A flow having a longer cycle is then later pushed 
> towards the correct awg cwnd. In the long run the cycle lengths (= 
> drop probability) averages to be the same, and very importantly, there 
> is no systematic bias.
>
> Thanks,
>
> /Markku
>
> Bob Briscoe wrote:
>
>> 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:
>>      +  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.
>>      +  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:
>>      +  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.
>>      +  @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 <[e-mail]> 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 <[e-mail]> 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 Rmin: α ~= (1/β2 - 1) / 3; Example: β
>> = 0.7; α ~= 0.35
>> #2) All sawteeth have the same Rmax: α ~= 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, Tr, 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.
>>     Tr = ΣJ-1j=0    (Rmin + 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.Rmin + J(J-1)α/2r
>>        ~= J.Rmin + J2α/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:
>>     (Rmax - Rmin) = Jα/r,                                (2a)
>> Or by the multiplicative relationship between the max and min RTTs, 
>> by the
>> definition of β: Rmin = β.Rmax.
>>     (Rmax - Rmin) = (Rmin / β) - Rmin
>>                                = Rmin(1-β)/β (2b)
>> Equating (2a) and (2b):
>>     J = r.Rmin(1-β) / (αβ)                                  (2)
>>
>> Substituting for J from (2) in (1):
>>     Tr = r.Rmin2 (1-β) / (βα) + r.Rmin2 (1-β)2/(2β2α)
>>          = r.Rmin2 (1-β) / (βα) * (1 + (1-β)/2β )
>>          = r.Rmin2 (1-β)(1+β) / (2β2α)
>>          = r.Rmin2 (1-β2) / (2β2α)         (3)
>> And, because Rmin = β.Rmax.
>>     Tr = r.Rmax2 (1-β2) / (2α)              (4)
>>
>> The well-known steady-state Reno formula from [FF99] is:
>>     rReno ~= (1/Ravg) 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,
>>     Ravg ~= (Rmax + Rmin)/2
>> and
>>     Rmin = Rmax/2
>> Therefore
>>     rReno ~= (1/Rmin) sqrt(2 / 3p)
>>             (6)
>>     rReno ~= (1/Rmax) 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 Rmin
>>
>> From Eqn (3):
>>     Tr = r.Rmin2 (1-β2) / (2β2α)
>> Total packets sent over period Tr is r.Tr during which time assume 1 
>> packet
>> is lost (or marked) at the sawtooth peak {Note 1}. So loss probability:
>>     p = 1 / r.Tr
>> Substituting for Tr and rearranging :
>>     r2 = 2β2α / Rmin2 (1-β2)p
>>     r = (β/Rmin) sqrt(2α / (1-β2)p)
>> Equating the Reno packet rate, rReno, from eqn (6) to the C-Reno packet
>> rate, r, for all α and β:
>>     r = rReno
>>        = (1/Rmin) sqrt(2 / 3p).
>> Therefore,
>>     (1/Rmin) sqrt(2 / 3p) ~= (β/Rmin) 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 Rmax = Rmin / β
>>
>> From Eqn (4):
>>     Tr = r.Rmax2 (1-β2) / (2α)
>> As before, after substituting for Tr and rearranging:
>>     p = 1 / r.Tr
>>     r = (1/Rmax) sqrt(2α / (1-β2)p)
>> Equating to rReno from eqn (7) for all α and β,
>>       ~= (1/Rmax) sqrt(8 / 3p).
>> Rearranging
>>     8/3 ~= 2α / (1-β2)
>>     α ~= 4(1-β2) / 3
>>                         (9)
>>
>>   #3) All sawteeth have the same Ravg
>>
>> Ravg = (Rmax + βRmax )/2
>>          = Rmax (1+β)/2
>> From Eqn (4):
>>     Tr = r.Rmax2 (1-β2) / (2α)
>>          = 2r.Ravg2 (1-β) / α(1+β)
>> As before, after substituting for Tr and rearranging:
>>     p = 1 / r.Tr
>>     r = (1/Ravg) sqrt(α (1+β) / 2(1-β)p)
>> Equating to rReno from eqn (5) for all α and β,
>>       ~= (1/Ravg) 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.Tr
>> Substituting αReno = 1:
>>     p = 1 / αC-Reno.r.Tr
>> This would modify all the results to:
>>
>> #1) All sawteeth have the same Rmin: α ~= sqrt( (1/β2 - 1) / 3 );
>> Example: β = 0.7; α ~= 0.59
>> #2) All sawteeth have the same Rmax: α ~= 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>
>>
>> [MSJ+19] Ayush Mishra, Xiangpeng Sun, Atishya Jain, Sameer Pande, Raj 
>> Joshi,
>> and Ben Leong. The Great Internet TCP Congestion Control Census. 
>> 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 Briscoe http://bobbriscoe.net/
>>
>>
>> -- 
>> ________________________________________________________________
>> Bob Briscoe http://bobbriscoe.net/
>>
>>
>> -- 
>> ________________________________________________________________
>> Bob Briscoe http://bobbriscoe.net/
>>
>>

-- 
________________________________________________________________
Bob Briscoehttp://bobbriscoe.net/