Subject: Re: [tcpm] Concluding WGLC for draft-ietf-tcpm-rfc8312bis-03

From: Lars Eggert <[email-masked]>
Date: Thu, 2 Sep 2021 13:54:51 +0300

Hi Markku,

On 2021-8-31, at 14:10, Lars Eggert <[email-masked]> wrote:
> We've created a bunch of GitHub issues based on the issues you identified, and will work on resolutions there. Do you have a GitHub ID we can use to tag you?

could you share your GitHub ID so we can tag you when there are questions, or could you check the issues directly? We'd like your input on some of the proposed resolutions.

Thanks,
Lars

---

From: Markku Kojo <[email-masked]>
Date: Thu, 2 Sep 2021 14:37:30 +0300 (EEST)

Hi Lars,

On Tue, 31 Aug 2021, Lars Eggert wrote:

> Hi Markku,
>
> On 2021-8-30, at 19:33, Markku Kojo <kojo=[email-masked]> wrote:
>> My sincere apologies as this comes very late in the process but I was not able to follow IETF mailing list at the time of WGLC nor during the recent weeks, and I couldn't attend IETF 111.
>
> it's always a bit disappointing to get a long review just when you
> thought you were done, but it will lead to a better document in the end
> - so thank you for your review!

I know. I was not intended to do a review but Yoshi's recent question and 
some discussions on the list that I catched up just recently aroused my 
interest. I was quite suprised myself on how many issues I found. Hope it 
is helpful.

One additionl thing that I didn't mention but what I found as I was 
trying to read the doc as if I didn't know anything about CUBIC: the 
algorithm specification is a bit scattered around the doc together with 
the discussion of the features. So, it is likely to require a reader to 
jump back and forth in the dc to get a full picture. It might be useful 
to gather the actual algorithm actions to be taken on occurance of 
differents events (congestion detected, enter congestion avoidance, a new 
ACK arrives, etc.) into a single place to have a compact and accurate 
description of when each of the algorithm actions exactly are taken and 
in which form. Most congestion control RFCs do it like this. To avoid any 
significant restructuring of the doc this might work best by adding a new 
section for it. Then the current Sec 4 may remain as a more detailed 
description and discussion/justification for various actions like it 
currently does. This is just my opinion on how to make the doc more easy 
to follow.

> We've created a bunch of GitHub issues based on the issues you
> identified, and will work on resolutions there. Do you have a GitHub ID
> we can use to tag you?

Done and sent to you.

While direct discussions via GitHub are sure useful, many of the issues 
may deserve discussion over the list as well, I believe.

Thanks,

/Markku

>> 1. ECN
>>
>> a) The draft modifies RFC 3168 when ECE arrives and would result
> ...
> https://github.com/NTAP/rfc8312bis/issues/83
>
>> b) RFC 8311 (sec 4.1) allows modifying the TCP-sender response to
> ...
> https://github.com/NTAP/rfc8312bis/issues/84
>
>> c) ABE (RFC 8511) is currently the only experimental RFC to modify
> ...
> https://github.com/NTAP/rfc8312bis/issues/85
>
>> 2. Slow-Start Overshoot w/ loss-based congestion conrol
> ...
> https://github.com/NTAP/rfc8312bis/issues/86
>
>> 3. RACK (and QUIC)
> ...
> https://github.com/NTAP/rfc8312bis/issues/87
>
>> 4. Fairness to AIMD congestion control
> ...
> https://github.com/NTAP/rfc8312bis/issues/88
>
>> 5. Contribution to buffer bloat and slower convergence due to
>>   larger decrease factor
> ...
> https://github.com/NTAP/rfc8312bis/issues/89
>
>> 6. Citing Experimental RFCs as if being a part of CUBIC
> ...
> https://github.com/NTAP/rfc8312bis/issues/90
>
>> 7. Discussion
> ...
> https://github.com/NTAP/rfc8312bis/issues/91
>
>> Sec 5.1
> ...
> https://github.com/NTAP/rfc8312bis/issues/92
>
>> Sec 5.3
> ...
> https://github.com/NTAP/rfc8312bis/issues/93
>
>> Sec 5.4
> ...
> https://github.com/NTAP/rfc8312bis/issues/94
>
>> Sec 5.5
> ...
> https://github.com/NTAP/rfc8312bis/issues/95
>
>> Sec 5.6
> ...
> https://github.com/NTAP/rfc8312bis/issues/96
>
>> Sec 5.8
> ...
> https://github.com/NTAP/rfc8312bis/issues/97
>
>> Sec 5.9
> ...
> https://github.com/NTAP/rfc8312bis/issues/98
>
>> 8. The draft says in the intro that CUBIC is to be regarded as *current standard* for TCP
> ...
> https://github.com/NTAP/rfc8312bis/issues/99
>
>> Misc comments:
>>
>> _epoch_start_: needs more accurate and consistent definition when the exactly the epoch
>
> ...
> https://github.com/NTAP/rfc8312bis/issues/100
>
>> In many occassions:
>> "(upon receiving) an ACK" -> "(upon receiving) a new ACK"
>
> https://github.com/NTAP/rfc8312bis/issues/101
>
>> On page 13:
> https://github.com/NTAP/rfc8312bis/issues/102
>
> Thanks,
> Lars
>
>

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sun, 5 Sep 2021 03:47:02 -0700

HI Markku,

Thanks for the detailed review. These are indeed very good points. Thank
you so much!
I personally would like to discuss 4. on the ML as it may be rather a big
and fundamental points than the others.
I believe the equations for AIMD TCP calculation came from "A Comparison of
Equation-Based
and AIMD Congestion Control" and It seems to me your point is that draft
doesn't use the equations properly.
However, I'm not very sure how it's not correctly used yet.
Could you elaborate this a bit more?

Thanks,
--
Yoshi

On Mon, Aug 30, 2021 at 9:33 AM Markku Kojo <[email-masked]> wrote:

> Hi Yoshi, all,
>
> On Wed, 18 Aug 2021, Yoshifumi Nishida wrote:
>
> > Hi,The chairs think 8312bis draft is in good shape and it's ready for
> submission.
> > We know we had some discussions on how to handle ABC draft in the draft
> during the
> > last WG meeting and there are on-going related discussions on the ML.
> > However, we still think we can proceed with the draft as the
> relevance between the
> > draft and the current discussions is not very high.
> >
> > If anyone has different thoughts on this, please let us know.
> > Otherwise, we will prepare a writeup soon and submit it to IESG.
>
> My sincere apologies as this comes very late in the process but I was not
> able to follow IETF mailing list at the time of WGLC nor during
> the recent weeks, and I couldn't attend IETF 111.
>
> I took a look at the draft and some statements of it seemed to be in
> conflict with other Standards Track RFCs. I believe the tcpm
> wg should look more closer to these to avoid publishing conflicting
> guidance in different Standards Track RFCs. In addition, there are some
> issues I am concerned about.
>
> 1. ECN
>
>     in cwnd < 2 MSS by setting a lower bound of 2 MSS for cwnd (only
>     ssthresh is supposed to have a lower bound of 2 MSS).
>     This is in conflict with RFC 3168, RFC 5033, and RFC 2914 which
>     require "full backoff", that is, a sender must continue decreasing
>     sending rate as long as congestion persists. This is a fundamental
>     property for any congestion control mechanism. For ECN, RFC 3168
>     (sec 6.1.2) requires that cwnd is halved until the minimum cwnd
>     of one MSS is received, and then the sender continues reducing
>     sending rate by using a timer with exponential backoff, if more
>     ECE-echo packets keep on arriving.
>
>     This implementation bug has been long with Linux and is present
>     in other stacks as well and should get corrected ASAP with
>     appropriate advise in all published RFCs, instead of replicating
>     the bug in the RFC series.
>
>     ECE for experimental purposes only. Has there been any discussion
>     with tsvwg in that modifying the TCP-response to ECE in CUBIC is
>     conflict with RFC 8311 as CUBIC is currently intended to become
>     a Standards Track RFC?
>
>     the TCP-sender response to ECE. ABE allows modifying multiplicative
>     decrease factor only for AIMD TCP and only when ECE arrives in
>     congestion avoidance, that is, not when the sender is in slow-start.
>
>     Applying a decrease factor of 0.7 (or higher) when a congestion
>     singnal arrives and ends the initial slow start would be
>     inconsiderate because it extends the convergence time from
>     the slow-start overshoot. ABE has found that using a larger decrease
>     factor yields performance improvement when applied in congestion
>     avoidance, but not otherwise. Do we have data that would support
>     different findings with CUBIC?
>
>     The larger decrease factor of 0.7 seems unadviseable also if
>     used in the initial slow start with loss based congestion
>     control (w/ Not-ECT traffic); packets start getting dropped
>     when a TCP sender has increased cwnd in slow start such that
>     the available network bandwidth and buffering capacity at the
>     bottleneck is filled, but the TCP sender continues sending
>     more packets for one RTT doubling cwnd and hence also the number
>     of packets inflight before the congestion signal reaches the sender.
>     Now, even if the sender uses the standard decrease factor of 0.5,
>     the cwnd gets reduced only to a value that equals to the cwnd just
>     before (or around) the congestion point. That is, the network is
>     still full when the sender enters fast recovery but we do not
>     expect more drops during fast recovery in a deterministic model.
>     Only in congestion avoidance after the recovery, the sender
>     increases cwnd again and gets a packet drop that takes the
>     sender to a normal sawtooth cycle in an ideal case. So, the
>     convergence time from slow-start is expexted to be fast though
>     in reality loss recovery does not always work ideally with
>     such many drops in a window of data.
>
>     However, if the sender applies decrease factor of 0.7, it
>     continues in fast recovery with a 40% higher cwnd than what is
>     the available network capacity. This is very likely to result in
>     significant number of packet losses during fast recovery, and
>     very likely to result in loss of retransmissions. So, it is no
>     wonder that so many people have been very concerned about the
>     slow-start overshoot and the problems it creates.
>     It is very obvious that applying decrease factor of 0.7 in
>     the initial slow start is likely to extend the convergence
>     time from the slow-start overshoot significantly. Or, do we
>     have data that shows that such concern is unnecessary?
>     Also, a number of new loss-recovery mechanisms have been
>     introduced maybe mainly because of this?
>     I would hesitate recommending decrease factor of 0.7 when
>     a congestion event occurs during the initial slow start.
>
>
> 3. RACK (and QUIC)
>
>     The draft states that RACK (and QUIC loss detection) can be used
>     with CUBIC to detect losses. However, it seems to have gone
>     unnoticed that RACK may also detect loss of a retransmission in
>     which case the congestion control response is required to be taken
>     twice, i.e., ssthresh and cwnd must be lowered again (MUST in
>     RFC 5681 Sec. 4.3). Once RACK got published all new congestion
>     controls and updates to existing RFCs must include this essential
>     congestion control response, if the congestion control mechanism
>     intends to use RACK for loss detection.
>
>     This draft does not have any such requirement nor does it specify
>     how this is done?
>
>     The equation on page 12 to derive increase factor α      that
>                                                        cubic
>
>     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. 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.
>
>
>     This draft uses a larger cwnd decrease factor, resulting in larger
>     average cwnd and buffer occupation. This means that it is
>     likely to contribute significantly to buffer bloat, particularly
>     when considering also the use of concave increase function in the
>     beginning of the congestion avoidance that keeps the cwnd close
>     to maximum most of the time as carefully explained in the draft.
>     This means that CUBIC keeps also buffer bloated router queues
>     very efficiently full at all times.
>
>     Currently the draft does mention the slower convergence speed
>     as the only side effect for the larger decrease factor and does
>     not discuss the contribution to buffer bloat. It would be
>     important to assess this together with measurement data to
>     back up any observations.
>
>     Do we have data in different environments, including buffer-bloated
>     environments that show how much effect CUBIC has compared to
>     AIMD TCP?
>     And, how does larger decrease function impact convergence speed,
>     particularly in buffer-bloated environments.
>     Many people have complained that window-based (TCP) congestion
>     control drives buffer bloat. Of course, also the current standard
>     AIMD TCP tends to fill in the buffer-bloated queues but it
>     unlikely does it as effectively as CUBIC? This would be good to
>     understand better.
>
>     The draft says that CUBIC MAY implement DSACK [RFC3708], limited slow
>     start [RFC 3742], [RFC7661] and hybrid slow start [cites a paper].
>     Aren't the first three down references? Not sure if it is appropriate
>     for a Stds Track document to cite experimental work or a paper like
>     this even though it's a MAY.
>
>
> 7. Discussion
>
> I regret to say that the discussion in Sec 5. brings up surprisingly
> little data to back up the claims that are made. Given the long
> deployment experience that is emphasised in the draft, there, however, is
> little evidence (measurement data) summarised and cited to back up the
> claims. "There is a long deployment experience" does not provide
> any evidence as such. There should be a lot of studies with measurement
> data accumulated over the years that would support the assertions in the
> doc. Or, is there?
>
> Sec 5.1
>
> In this subsection, one should show the impact of CUBIC when
> competing with AIMD TCP. The numbers in tables are derived from
> analytical models that give average window size with fixed random
> loss probabilities and unlimited bandwidth. That is not the same as when
> flows are combeting in the same congested bottleneck that builds a queue.
> Loss probabilities for different flows are likely to be different
> especially at lower levels of statistical multiplexing.
>
> The first para of sec 5.1 does not sound like true. Simply looking at the
> original CUBIC paper [HRX08] reveals that CUBIC dominates AIMD TCP (SACK
> TCP) in the regions where SACK TCP alone is able to fully utilize the
> available bandwidth (Figure 10 c up until 200 Mbps, and to some extent in
> Fig 10 a with 40 ms delay). And ín all cases where SACK TCP alone is not
> able to utilize all available b/w, CUBIC steals multiple times more b/w
> from SACK TCP than what SACK TCP is not able to utilize. Figures 5 and 6
> tell the same story. Has something changed and/or is there possibly data
> that provides alternative evidence.
>
> In addition, the recommended value for constant C and the two alternative
> values presented in the draft are the same as in the original paper. It
> would be interesting to see if there has been any experimentation with
> different values and what might be the outcome?
>
> Sec 5.3
>
> Any experimental data to summarize and cite?
>
> Sec 5.4
>
> The text correctly states that CUBIC fills queues faster than AIMD TCP
> and increases the risk of standing queues. Then it proposes queue sizing
> and AQM as a solution, which is odd. Applying AQM to keep the queues
> shorter of course decreases the RTT (delay) seen but it does not help
> with standing queues (they remain standing but are just shorter).
>
> Sec 5.5
>
> Setting lower bound of 2 MSS for cwnd with ECN may result in symptoms of
> congestion collapse with certain specific conditions, e.g., if the actual
> (physical) queue size is very large and there is a mix of ECN-capable
> (ECT) and not ECN-capable flows. When the number of ECN capable flows
> increase the start starving the not ECN-capable flows as ECT flows stop
> responding to congestion and start increasing the queue such that AQM has
> to drop almost all not ECT packets.
>
> Sec 5.6
>
> Competing CUBIC flows will converge but it happens very slowly and
> requires a large amount of data to send, i.e., short flows are more
> unlikely to live long enough to converge. This seems to be case at least
> according to the results in original paper [HRX08, Fig 4 b].
> Summary and citing some performance data would be very useful and much
> more convincing.
>
> Sec 5.8
>
> The MUST NOT requirement would be much better placed with other
> specifications in Sec 4 and would benefit from more accurate description.
>
> Sec 5.9
>
> The statement made here is not convincing and is likely to be incorrect.
> E.g., CUBIC with larger decrease factor would most likely release
> capacity notably slower than AIMD TCP if there is sudden congestion.
>
>
> 8. The draft says in the intro that CUBIC is to be regarded as *current
> standard* for TCP congestion control. It sounds a bit like it would
> obsolete RFC 5681 which is not the intent. RFC 5681 still has its
> specific role as the document that gives the baseline and generic
> guidelines for TCP (and other) congestion control.
> Instead, I think this document should articulate very carefully its role
> among the congestion control algorithms. How, I am not sure. Maybe
> simply as an alternative for RFC5681 congestion avoidance and
> multiplicative decrease.
>
> Please note also that when specifying these algorithms this document is
> in direct conflict with a MUST in RFC5681 which says: "however, a TCP
> MUST NOT be more aggressive than the following algorithms allow (that is,
> MUST NOT send data when the value of cwnd computed by the following
> algorithms would not allow the data to be sent)."
> Therefore, the draft should make this differentation very clear maybe
> already in the abstract and justify the deviations much better than it
> currently does (accompanied with evidence = data). This is very important
> i order to make a convincing case why it is ok for this doc to deviate
> from the current Standards Track TCP normative statements.
>
> Misc comments:
>
> _epoch_start_: needs more accurate and consistent definition when the
> exactly the epoch starts. Is it when congestion event occurs or when
> TSP sender enters congestion avoidance first time after an congestion
> event. If it is  different in different scenarios that would be good to
> present systematically.
>
> In many occassions:
>
>    " the sender MAY employ a Fast
>      Recovery algorithm to gradually adjust the congestion window to its
>      new reduced _ssthresh_ value."
>
> I assume this is aiming at saying that something similar to PRR MAY be
> used to reduce cwnd. This, however, is somewhat vaguely said and using
> fasr recovery is misleading. We need to remember also that it might not
> be trivial to have it right. So, dunno whether it would be useful to drop
> this.
>
> Best regards,
>
> /Markku

---

From: Lars Eggert <[email-masked]>
Date: Tue, 7 Sep 2021 09:29:30 +0300

Hi,

On 2021-9-2, at 14:37, Markku Kojo <[email-masked]> wrote:
> While direct discussions via GitHub are sure useful, many of the issues may deserve discussion over the list as well, I believe.

true, and we will bring those to the list that should be discussed here.

In the meantime, could you look at the issues/resolutions that we tagged you in, so we can start merging some changes?

Thanks,
Lars

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 7 Sep 2021 13:17:34 +0100

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:
>    The equation on page 12 to derive increase factor α_cubic that
>    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

[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>

[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 Briscoe                               http://bobbriscoe.net/

---

From: Yoshifumi Nishida <[email-masked]>
Date: Wed, 8 Sep 2021 02:04:05 -0700

Hi Bob,

Thank you so much! I will think it through.
--
Yoshi

On Tue, Sep 7, 2021 at 5:17 AM Bob Briscoe <[email-masked]> wrote:

> 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...
>
> 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:
>
> #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;
> #3) All sawteeth have the same Ravg: α ~= 3(1-β) / (1+β);        Example:
> β = 0.7; α ~= 0.53    <== used in [FHP00] and therefore in RFC8312
>
>
> 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).
>
> 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]).
>
> (FAQ: Why does C-Reno add <1 segment per RTT to be friendly to Reno, which
> adds 1 segment per RTT?
> 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.)
>
> 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
> 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.)
>
> 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.
>
>
> B) Equate this to the recovery time of Reno, which will produce a formula
> for the additive increase factor, α.
>
> increasingly large as the queue grows. This sum is stated in terms of the
> number of rounds per cycle, J.
> The following formula gives the recovery time, Tr, from one max window to
> the next, in C-Reno with:
> 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)
> 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.
>
>     (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)
>
>     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)
>
>     rReno ~= (1/Ravg) sqrt(3 / 2p)
>             (5)
> assuming deterministic marking (which is also assumed for the above model
> of C-Reno).
>
>     Ravg ~= (Rmax + Rmin)/2
>     Rmin = Rmax/2
>     rReno ~= (1/Rmin) sqrt(2 / 3p)
>             (6)
>     rReno ~= (1/Rmax) sqrt(8 / 3p)
>             (7)
>
> #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
>     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α)
>     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+β)
>     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)
>
> 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
> #1) All sawteeth have the same Rmin: α ~= sqrt( (1/β2 - 1) / 3 );
> #2) All sawteeth have the same Rmax: α ~= sqrt( 4(1-β2) / 3 );
> 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
>

---

From: Markku Kojo <[email-masked]>
Date: Wed, 8 Sep 2021 18:32:09 +0300 (EEST)

Hi,

On Tue, 7 Sep 2021, Lars Eggert wrote:

> In the meantime, could you look at the issues/resolutions that we
> tagged you in, so we can start merging some changes?

Sure, I will. Unfortunately I have been (and will be) fully booked for 
this week, but I try to address those ASAP.

Thanks,

/Markku

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sat, 11 Sep 2021 14:02:50 -0700

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.
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.
So, I think it would be better for this doc to use the model as it is and
leave its enhancements for future discussions.

The second point is α in the draft might be too big.
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.
So, it is obvious that this model does not aim for the cases where there's
no other traffic.

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.

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

---

From: Jonathan Morton <[email-masked]>
Date: Sun, 12 Sep 2021 21:25:19 +0300

> On 12 Sep, 2021, at 12:02 am, Yoshifumi Nishida <[email-masked]> wrote:
> 
> 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.
> 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. 
> So, I think it would be better for this doc to use the model as it is and leave its enhancements for future discussions.

I think the assumption of constant RTT will become increasingly valid as AQM is deployed, so this was a good and prescient simplification by the authors.  The alternative scenario of a relatively large drop-tail buffer can be checked empirically for reasonable behaviour, if required - but the existing wide deployment of CUBIC suggests that any serious trouble would already have been noticed.

> 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. 
> So, it is obvious that this model does not aim for the cases where there's no other traffic.
> 
> 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

That was definitely the impression I got, too, and in fact it puzzles me why anyone would assume otherwise.

Another point to note is that this entire calculation is only valid in the "compatibility" regime of CUBIC, where it is explicitly attempting to perform similarly to NewReno.  If a test scenario drives CUBIC into its "native" regime where the polynomial curve rises above the linear growth function, then it will outperform NewReno by design.  The assumption then is that NewReno is insufficiently utilising available capacity, so there is less concern over causing harm to it and more advantage to using that leftover capacity.

 - Jonathan Morton

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 14 Sep 2021 00:17:03 +0100

Yoshi,

On 11/09/2021 22:02, Yoshifumi Nishida wrote:
> 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.

[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.
> 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.

> 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

> 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)
> situation to the formula, which can lead to α_3  = 0.20
> (α=1.0,  β =0.5) model oscillates between 0.5 W1 and 1.0 W1 in a 
> 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
>
> Now, if we define the congestion epoch as e RTTs, e = 0.5 W1 / 1.0  
> and also e = 0.3 W2 / X

[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 <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Yoshi,
>
>     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.
>
>     [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):
>     #3) All sawteeth have the same Ravg: α ~= 3(1-β) / (1+β);       
>     Example: β = 0.7; α ~= 0.53    <== used in [FHP00] and therefore
>     in RFC8312
>
>
>     #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.
>     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
>     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).
>     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.
>
>
>     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 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.
>     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.
>     The following formula gives the recovery time, T_r , from one max
>     window to the next, in C-Reno with:
>     assuming that the minimum window of each sawtooth still fully
>     utilizes the link.
>     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
>     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.
>     Or by the multiplicative relationship between the max and min
>     RTTs, by the definition of β: R_min = β.R_max .
>              = r.R_min ^2 (1-β^2 ) / (2β^2 α) (3)
>     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,
>     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
>            ~= (1/β^2 - 1) / 3 (8)
>         α ~= 4(1-β^2 ) / 3                                            
>     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:
>     #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
>     =========
>     <https://www.icir.org/tfrc/aimd.pdf
>     <https://www.icir.org/tfrc/aimd.pdf>>
>
>     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/>
>

---

From: Bob Briscoe <[email-masked]>
Date: Wed, 15 Sep 2021 14:02:56 +0100

Lars,

I went through all the issues you've created on github.
You will see I've been trying to help close off most of them in order to 
get this draft progressing.

I thought I should mention them all here, 'cos github doesn't seem to be 
notifying the tcpm list, like it does for QUIC issues and the quic list.

Bob

On 31/08/2021 12:10, Lars Eggert wrote:
> it's always a bit disappointing to get a long review just when you thought you were done, but it will lead to a better document in the end - so thank you for your review!
>
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Yoshifumi Nishida <[email-masked]>
Date: Fri, 17 Sep 2021 02:06:08 -0700

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 <[email-masked]> wrote:

> 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.
>
> clearly doesn't produce the desired result, even in the paper that proposed
> it.
>
>
> [BB] How so? The paper's own simulations (exploring a very limited space)
> conclude that α from the model is more than 2x too small.
>
> [BB] It is certainly obvious that comparing flow rates is not about single
> flows.
>
> 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.
>
> 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
> 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.
>
>
> 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.
>
> 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
>
>
>
>> 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
>> it doesn't vary. But it does, because the sawteeth vary the queue. But the
>> #1) All sawteeth have the same Rmin: α ~= (1/β2 - 1) / 3;
>> The following formula gives the recovery time, Tr, from one max window
>> the definition of β: Rmin = β.Rmax.
>> 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

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 23 Sep 2021 18:15:33 +0100

Yoshi,

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

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

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

Bob

On 17/09/2021 10:06, Yoshifumi Nishida wrote:
> Hi Bob,
>
> Thanks for the comments.
> I at least think we both can agree that the draft uses [FHP00] as the 
> basis of their AIMD or NewReno model.
> If you have any suggestions to update the texts to address your 
> concerns, please share. (but, in this case, using github might be 
> straightforward.)
> Unfortunately, I'm not sure about the empirical evidence to support 
> the formula.
> But, given that cubic has been widely deployed for long time and we 
> don't see strong voices to point out problems for it, I am guessing 
> the issues might not be too obvious at least.
> On Mon, Sep 13, 2021 at 4:17 PM Bob Briscoe <[email-masked] 
>     [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 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.
>
>>
>>     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
>
>     [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
>>     (α=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)
>>     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
>     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.
>
>     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
>>         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.
>>
>>         [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:
>>
>>         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
>>         #3) All sawteeth have the same Ravg: α ~= 3(1-β) /
>>         (1+β);        Example: β = 0.7; α ~= 0.53 <== used in [FHP00]
>>         and therefore in RFC8312
>>
>>
>>         #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.
>>
>>         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.
>>
>>         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
>>         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:
>>         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).
>>         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
>>         [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 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, α.
>>
>>         become increasingly large as the queue grows. This sum is
>>         stated in terms of the number of rounds per cycle, J.
>>         The following formula gives the recovery time, T_r , from one
>>         max window to the next, in C-Reno with:
>>         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
>>         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.
>>                                        = R_min (1-β)/β             
>>            (2b)
>>             T_r = r.R_max ^2 (1-β^2 ) / (2α)                  (4)
>>
>>             r_Reno ~= (1/R_avg ) sqrt(3 / 2p)                 (5)
>>         Assuming a Reno sawtooth is approximately linear, the average
>>         RTT of a Reno flow,
>>             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.
>>
>>
>>         assume 1 packet is lost (or marked) at the sawtooth peak
>>         {Note 1}. So loss probability:
>>             p = 1 / r.T_r
>>         Equating the Reno packet rate, r_Reno , from eqn (6) to the
>>         C-Reno packet rate, r, for all α and β:
>>             r = r_Reno
>>         {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:
>>         #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
>>
>>         [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
>>         GreatInternetTCPCongestionControlCensus. Proc. ACM on
>>         Measurement and Analysis of Computing Systems, 3(3), December
>>         2019
>>

---

From: Neal Cardwell <[email-masked]>
Date: Thu, 23 Sep 2021 17:46:14 -0400

On Thu, Sep 23, 2021 at 1:16 PM Bob Briscoe <[email-masked]> wrote:

> perhaps didn't summarize well): the formula assumes deterministic marking
> (i.e. some but not all AQMs, and definitely not drop-tail). I believe a
> large majority of the bottleneck buffers on the Internet are still drop
> tail, despite the efforts of many to recommend AQM deployment. So it's not
> particularly applicable to the real Internet.
>
> It also assumes the sawteeth of flows with different RTTs all centre on an
> operating point around the middle of the sawteeth, which is perhaps true of
> RED, but not most other AQMs.
>
> in principle, but haven't developed the maths for it - it's hard. But pls
> don't wait for me. The Cubic RFC's good enough, and the precise value of
> the Reno-Friendly alpha parameter is fairly irrelevant given the most
> prevalent deployment (Linux) ignores the RFC and sets it much more
> aggressively to 1 instead of 0.53 anyway.
>

Hi Bob,

Can you please elaborate on the characterization of Linux TCP CUBIC as
using an alpha of 1 instead of 0.53?

My experience in reading the Linux TCP CUBIC code and testing it and
examining its packet-by-packet behavior in congestion avoidance is that it
uses the 0.53 value.

This is implemented in the code here:
  https://elixir.bootlin.com/linux/v5.14/source/net/ipv4/tcp_cubic.c#L297

Note that we have:
  beta_scale = 15
So the computation of:
  delta = (cwnd * scale) >> 3;
means:
  delta = (cwnd * 15) >> 3;
That means basically delta is:
    cwnd * 15/8

That means, for example, for a cwnd of 100, the number of packets that need
to be ACKed before increasing cwnd is:
  100 * 15/8 = 187.5

Since 187.5 is 1.875x the cwnd, the rate of cwnd increase is  1 packet /
1.875 rounds, or  .533 packets per 1 round .

So AFAICT this is implementing the correct 0.53 value you mention.

Where Linux TCP CUBIC Reno-emulation additive increase is not ideal is that
once cwnd reaches W_max, it does not return the additive increase to 1, in
order to match Reno for long-term cwnd growth. I have a patch series with
that and a few related fixes that I am trying to find time to polish up and
send upstream.

Apologies if I'm missing something or off in the weeds. :-)

best regards,
neal

>> 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.
>> model of varying RTT, 'cos I'd already recently done this maths for another
>> the same time and reduce them when the sum of their windows becomes Wmax,
>> the throughput of them will mostly be the same.
>> --
>> Yoshi
>>
>>> Example: β = 0.7; α ~= 0.53    <== used in [FHP00] and therefore in RFC8312
>>>
>>>
>>> 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).
>>>
>>> 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).
>>> 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,
>>> This last formula is same as the equation used for C-Reno in RFC8312
>>> and in the RFC8312bis draft.
>>>
>>>

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 28 Sep 2021 13:10:47 +0100

Neal, [re-sending with trimmed message body - too big for ML]

On 23/09/2021 22:46, Neal Cardwell wrote:
>
>
> On Thu, Sep 23, 2021 at 1:16 PM Bob Briscoe <[email-masked] 
>     To summarize the main concern I already wrote in my first email
>     (but perhaps didn't summarize well): the formula assumes
>     deterministic marking (i.e. some but not all AQMs, and definitely
>     not drop-tail). I believe a large majority of the bottleneck
>     buffers on the Internet are still drop tail, despite the efforts
>     of many to recommend AQM deployment. So it's not particularly
>     applicable to the real Internet.
>
>     It also assumes the sawteeth of flows with different RTTs all
>     centre on an operating point around the middle of the sawteeth,
>     which is perhaps true of RED, but not most other AQMs.
>
>     I will still try to develop a better formula - I've thought how to
>     do it in principle, but haven't developed the maths for it - it's
>     hard. But pls don't wait for me. The Cubic RFC's good enough, and
>     the precise value of the Reno-Friendly alpha parameter is fairly
>     irrelevant given the most prevalent deployment (Linux) ignores the
>     RFC and sets it much more aggressively to 1 instead of 0.53 anyway.
>
>
> Hi Bob,
>
> examining its packet-by-packet behavior in congestion avoidance is 
> that it uses the 0.53 value.
>
> <https://elixir.bootlin.com/linux/v5.14/source/net/ipv4/tcp_cubic.c#L297>
>
> Note that we have:
>   beta_scale = 15
> So the computation of:
> That means, for example, for a cwnd of 100, the number of packets that 
> need to be ACKed before increasing cwnd is:
>   100 * 15/8 = 187.5
>
> Since 187.5 is 1.875x the cwnd, the rate of cwnd increase is  1 packet 
> / 1.875 rounds, or  .533 packets per 1 round .
>

[BB] OMG. I've been labouring under this misapprehension for years. I 
just believed what someone told me about the Linux code because I 
trusted them, without ever checking it.

>
> Where Linux TCP CUBIC Reno-emulation additive increase is not ideal is 
> that once cwnd reaches W_max, it does not return the additive increase 
> to 1, in order to match Reno for long-term cwnd growth. I have a patch 
> series with that and a few related fixes that I am trying to find time 
> to polish up and send upstream.

[BB] Yes, that would be useful to fix.

> Apologies if I'm missing something or off in the weeds. :-)

[BB] No, mea culpa. I'm the one in the weeds.

So it matters even more whether 0.53 is really the correct value.

Thank you.

Bob

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