Subject: Re: [iccrg] [tcpm] Cwnd growth after fast convergence in CUBIC

From: Vidhi Goel <[email-masked]>
Date: Thu, 05 Nov 2020 20:45:18 -0800

+Lars and ICCRG

Hi Wesley,

I had noticed the same problem as you described when I implemented Cubic. This is my take on computing the K factor that avoids the situation of target cwnd <= cwnd.

W_max = cwnd = 100
Cwnd = cwnd * beta = 70 

W_max = W_max * 0.85 = 85

I simplified the formula to calculate K as below:

K = cbrt(W_max*(1-beta)/C)
=> K = cbrt(W_max - W_max * beta) / C)

// As I already computed cwnd = Wmax * beta, I replace it by cwnd (without the convergence factor)
=> K = cbrt(W_max - cwnd / C)

This ensures that the target cwnd is never below 70. 

IMO, we should not be applying beta to W_max after convergence factor has been applied in the K formula. Perhaps, it was an oversight in K’s formula.

Thanks,
Vidhi

> On Nov 5, 2020, at 11:32 AM, Rosenblum, Wesley <wesleyr=[email-masked]> wrote:
> 
> In RFC8312, section 4.6, the fast convergence heuristic specifies to further reduce W_max when a decrease in available bandwidth is detected. After W_max has been further reduced, W_cubic(0) will be less than cwnd, since W_max is now less than the previous cwnd. When entering congestion avoidance, this can cause the target congestion window to be less than the current congestion window. For example, say cwnd = 100, beta_cubic = .7 and a congestion event occurs:
> 
> W_max = cwnd = 100;
> W_max = W_max*(1.0+beta_cubic)/2.0 = 85   // further reduce W_max for fast convergence
> 
> cwnd = cwnd * beta_cubic = 70	          // window reduction
> W_cubic(0) = W_max * beta_cubic = 59.5
> 
> If we were to enter congestion avoidance at this point, with a small enough RTT, the target candidate congestion window as calculated by W_cubic(t+RTT) may be less than the current congestion window (~59.5 < 70). 
> 
> My question is: How should the cwnd be adjusted in congestion avoidance when it is below the target candidate congestion window? If we were to follow section 4.3 and increment cwnd by (W_cubic(t+RTT) - cwnd)/cwnd, this would result in a negative increment, which doesn’t make sense to me. The Linux CUBIC implementation adds a “very small increment” in such a case: see https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cubic.c#L293-L297. Does anyone know why Linux adds that increment? My inclination is to just leave the cwnd as is and not make any adjustment when target cwnd <= cwnd, but I’m wondering if there is any other guidance for this case.
> 
> Thanks,
> Wesley
> 
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Lars Eggert <[email-masked]>
Date: Fri, 6 Nov 2020 10:28:16 +0200

Hi,

> IMO, we should not be applying beta to W_max after convergence factor has been applied in the K formula. Perhaps, it was an oversight in K’s formula.

the other authors of the CUBIC RFC are experts on the algorithm, I mostly just helped get it through the IETF process.

That said, the intent was to document what the Linux code was doing at the time. Is there a difference between the RFC and what Linux has been doing or is doing now? If yes, it might be time to revise the RFC.

(I think Martin Thomson also found some nits recently.)

Thanks,
Lars

---

From: Neal Cardwell <[email-masked]>
Date: Fri, 6 Nov 2020 09:10:15 -0500

On Fri, Nov 6, 2020 at 3:28 AM Lars Eggert <[email-masked]> wrote:
> That said, the intent was to document what the Linux code was doing
> at the time. Is there a difference between the RFC and what Linux
> has been doing or is doing now? If yes, it might be time to revise
> the RFC.

Yes, it seems that this is a case where the RFC differs from the Linux
TCP CUBIC code.

The RFC says:
      K = cubic_root(W_max*(1-beta_cubic)/C) (Eq. 2)

which is equivalent to:
      K = cubic_root((W_max - W_max*beta_cubic)/C).  [B]

The Linux code does something different: it computes K once per epoch
immediately after the fast recovery or ECN cwnd reduction phase
completes, using:

      K = cubic_root((W_max - cwnd)/C).  [C]

See the computation of bic_K here:
  https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cubic.c#L254

For the non-fast-convergence case, the result of [B] and [C] are
equivalent, but for the fast convergence case they are not. So it
looks like in the case of fast convergence the RFC formula produces a
result that is incorrect, and does not match the Linux TCP CUBIC
behavior.

AFAICT,  changing Eq 2 to the following might fix the RFC and make it
match the Linux TCP CUBIC behavior:

      K = cubic_root(W_max - W_last_max*beta_cubic)/C) (Eq. 2)

best,
neal

---

From: L X <[email-masked]>
Date: Sat, 7 Nov 2020 10:30:46 -0600

Yes, the RFC is different from the Linux Cubic in case of fast convergence.

I would suggest changing Equation (2) of RFC 8312 to
K = cubic_root((W_max* - cwnd)/C) (Eq. 2)

where cwnd is the cwnd at the beginning of a congestion avoidance
stage. That is, W_cubic(0)=the cwnd at the beginning of a congestion
avoidance stage

By the way, sometime the fast recovery stage also changes cwnd based
on the number of packets in flight. As a result the cwnd at the
beginning of a congestion avoidance stage may be different from
W_last_max*beta_cubic.

Therefore, I would prefer to using the following Equation (2) in RFC 8312

K = cubic_root((W_max* - cwnd)/C) (Eq. 2)

instead of

Thank you all

Lisong

On Fri, Nov 6, 2020 at 8:11 AM Neal Cardwell <ncardwell=
[email-masked]> wrote:

> iccrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/iccrg
>