Skip to contentSkip to conversation

tcp_cubic: fix to achieve at least the same throughput as Reno

PATCH Superseded Mingrui Zhang 2 participants 8 messages Aug 15, 2024 – Aug 17, 2024

Subsystems (3)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover tcp_cubic: fix to achieve at least the same throughput as Reno

This series patches fixes some CUBIC bugs so that "CUBIC achieves at least the same throughput as Reno in small-BDP networks"
[RFC 9438: https://www.rfc-editor.org/rfc/rfc9438.html]

It consists of three bug fixes, all changing function bictcp_update() of tcp_cubic.c, which controls how fast CUBIC increases its congestion window size snd_cwnd.

(1) tcp_cubic: fix to run bictcp_update() at least once per RTT
(2) tcp_cubic: fix to match Reno additive increment
(3) tcp_cubic: fix to use emulated Reno cwnd one RTT in the future

Experiments:

Below are Mininet experiments to demonstrate the performance difference between the original CUBIC and patched CUBIC.

Network: link capacity = 100Mbps, RTT = 4ms

TCP flows: one RENO and one CUBIC. initial cwnd = 10 packets. The first data packet of each flow is lost

snd_cwnd of RENO and original CUBIC flows
https://github.com/zmrui/tcp_cubic_fix/blob/main/renocubic_fixb0.jpg

snd_cwnd of RENO and patched CUBIC (with bug fixes 1, 2, and 3) flows.
https://github.com/zmrui/tcp_cubic_fix/blob/main/renocubic_fixb1b2b3.jpg

The result of patched CUBIC with different combinations of bug fixes 1, 2, and 3 can be found at the following link, where you can also find more experiment results.

https://github.com/zmrui/tcp_cubic_fix

Thanks
Mingrui, and Lisong

Changes:
v2->v3:
Corrent the "Fixes:" footer content
https://lore.kernel.org/netdev/[email protected]/T/#t
v1->v2:
Separate patches
Add new cwnd_prior field to hold cwnd before a loss event
https://lore.kernel.org/netdev/[email protected]/T/#t

Mingrui Zhang (3):
tcp_cubic: fix to run bictcp_update() at least once per RTT
tcp_cubic: fix to match Reno additive increment
tcp_cubic: fix to use emulated Reno cwnd one RTT in the future

 net/ipv4/tcp_cubic.c | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)
Signature · 1 line
2.34.1
#1 lore raw

PATCH v3 1/3 tcp_cubic: fix to run bictcp_update() at least once per RTT

The original code bypasses bictcp_update() under certain conditions to reduce the CPU overhead. Intuitively, when last_cwnd==cwnd, bictcp_update() is executed 32 times per second. As a result, it is possible that bictcp_update() is not executed for several RTTs when RTT is short (specifically < 1/32 second = 31 ms and last_cwnd==cwnd which may happen in small-BDP networks), thus leading to low throughput in these RTTs.

The patched code executes bictcp_update() 32 times per second if RTT > 31 ms or every RTT if RTT < 31 ms, when last_cwnd==cwnd.

Fixes df3271f3361b ("[TCP] BIC: CUBIC window growth (2.0)")
Fixes ac35f562203a ("tcp: bic, cubic: use tcp_jiffies32 instead of tcp_time_stamp")

---
v2->v3: Corrent the "Fixes:" footer content
v1->v2: Separate patches

 net/ipv4/tcp_cubic.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
net/ipv4/tcp_cubic.c +5 -1
index 5dbed91c6178..11bad5317a8f 100644
@@ -218,8 +218,12 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
 
 	ca->ack_cnt += acked;	/* count the number of ACKed packets */
 
+	/* Update 32 times per second if RTT > 1/32 second,
+	 *        every RTT if RTT < 1/32 second
+	 *	  even when last_cwnd == cwnd
+	 */
 	if (ca->last_cwnd == cwnd &&
-	    (s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32)
+	    (s32)(tcp_jiffies32 - ca->last_time) <= min(HZ / 32, usecs_to_jiffies(ca->delay_min)))
 		return;
 
 	/* The CUBIC function can update ca->cnt at most once per jiffy.
Signature · 1 line
2.34.1
maintainer
#2 lore raw

Re: [PATCH net v3 1/3] tcp_cubic: fix to run bictcp_update() at least once per RTT

Quoted 32 lines · Mingrui Zhang

The original code bypasses bictcp_update() under certain conditions to reduce the CPU overhead. Intuitively, when last_cwnd==cwnd, bictcp_update() is executed 32 times per second. As a result, it is possible that bictcp_update() is not executed for several RTTs when RTT is short (specifically < 1/32 second = 31 ms and last_cwnd==cwnd which may happen in small-BDP networks), thus leading to low throughput in these RTTs.

The patched code executes bictcp_update() 32 times per second if RTT > 31 ms or every RTT if RTT < 31 ms, when last_cwnd==cwnd.

Fixes df3271f3361b ("[TCP] BIC: CUBIC window growth (2.0)")
Fixes ac35f562203a ("tcp: bic, cubic: use tcp_jiffies32 instead of tcp_time_stamp")

---
v2->v3: Corrent the "Fixes:" footer content
v1->v2: Separate patches

 net/ipv4/tcp_cubic.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
net/ipv4/tcp_cubic.c +1 -0
index 5dbed91c6178..11bad5317a8f 100644
@@ -218,8 +218,12 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
 
        ca->ack_cnt += acked;   /* count the number of ACKed packets */
 
+       /* Update 32 times per second if RTT > 1/32 second,

net/ipv4/tcp_cubic.c static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)

Quoted 10 lines
net/ipv4/tcp_cubic.c +4 -2
+        *        every RTT if RTT < 1/32 second
+        *        even when last_cwnd == cwnd
+        */
        if (ca->last_cwnd == cwnd &&
-           (s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32)
+           (s32)(tcp_jiffies32 - ca->last_time) <= min(HZ / 32, usecs_to_jiffies(ca->delay_min)))
                return;
 
        /* The CUBIC function can update ca->cnt at most once per jiffy.
--

I'm getting a compiler error with our builds with clang:

net/ipv4/tcp_cubic.c:230:46: error: comparison of distinct pointer types
('typeof (1000 / 32) *' (aka 'int *') and
'typeof (usecs_to_jiffies(ca->delay_min)) *' (aka 'unsigned long *')) [-Werror,-Wcompare-distinct-pointer-types]

          (s32)(tcp_jiffies32 - ca->last_time) <= min(HZ / 32,

usecs_to_jiffies(ca->delay_min)))

Can you please try something like the following, which works for our build:

           (s32)(tcp_jiffies32 - ca->last_time) <=
           min_t(s32, HZ / 32, usecs_to_jiffies(ca->delay_min)))

thanks,
neal

#3 lore raw

Re: [PATCH net v3 1/3] tcp_cubic: fix to run bictcp_update() at least once per RTT

Quoted 52 lines · Neal Cardwell
Quoted 31 lines · Mingrui Zhang

The original code bypasses bictcp_update() under certain conditions to reduce the CPU overhead. Intuitively, when last_cwnd==cwnd, bictcp_update() is executed 32 times per second. As a result, it is possible that bictcp_update() is not executed for several RTTs when RTT is short (specifically < 1/32 second = 31 ms and last_cwnd==cwnd which may happen in small-BDP networks), thus leading to low throughput in these RTTs.

The patched code executes bictcp_update() 32 times per second if RTT > 31 ms or every RTT if RTT < 31 ms, when last_cwnd==cwnd.

Fixes df3271f3361b ("[TCP] BIC: CUBIC window growth (2.0)")
Fixes ac35f562203a ("tcp: bic, cubic: use tcp_jiffies32 instead of tcp_time_stamp")

---
v2->v3: Corrent the "Fixes:" footer content
v1->v2: Separate patches

 net/ipv4/tcp_cubic.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
net/ipv4/tcp_cubic.c +1 -0
index 5dbed91c6178..11bad5317a8f 100644
@@ -218,8 +218,12 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
 
        ca->ack_cnt += acked;   /* count the number of ACKed packets */
 
+       /* Update 32 times per second if RTT > 1/32 second,

net/ipv4/tcp_cubic.c static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)

Quoted 10 lines
net/ipv4/tcp_cubic.c +4 -2
+        *        every RTT if RTT < 1/32 second
+        *        even when last_cwnd == cwnd
+        */
        if (ca->last_cwnd == cwnd &&
-           (s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32)
+           (s32)(tcp_jiffies32 - ca->last_time) <= min(HZ / 32, usecs_to_jiffies(ca->delay_min)))
                return;
 
        /* The CUBIC function can update ca->cnt at most once per jiffy.
--

I'm getting a compiler error with our builds with clang:

net/ipv4/tcp_cubic.c:230:46: error: comparison of distinct pointer types
('typeof (1000 / 32) *' (aka 'int *') and
'typeof (usecs_to_jiffies(ca->delay_min)) *' (aka 'unsigned long *')) [-Werror,-Wcompare-distinct-pointer-types]

          (s32)(tcp_jiffies32 - ca->last_time) <= min(HZ / 32,

usecs_to_jiffies(ca->delay_min)))

Quoted 7 lines

Can you please try something like the following, which works for our build:

           (s32)(tcp_jiffies32 - ca->last_time) <=
           min_t(s32, HZ / 32, usecs_to_jiffies(ca->delay_min)))

thanks,
neal

Thank you, Neal,
We have tried your suggested changes, and they also work for our compile and experiment tests.
Thanks,
Mingrui

#4 lore raw

PATCH v3 2/3 tcp_cubic: fix to match Reno additive increment

In reply to Mingrui Zhang

The original code follows RFC 8312 (obsoleted CUBIC RFC).

The patched code follows RFC 9438 (new CUBIC RFC):
"Once _W_est_ has grown to reach the _cwnd_ at the time of most recently setting _ssthresh_ -- that is, _W_est_ >= _cwnd_prior_ -- the sender SHOULD set α__cubic_ to 1 to ensure that it can achieve the same congestion window increment rate as Reno, which uses AIMD (1,0.5)."

Add new field 'cwnd_prior' in bictcp to hold cwnd before a loss event

Fixes 89b3d9aaf467 ("[TCP] cubic: precompute constants")

---
v2->v3: Corrent the "Fixes:" footer content
v1->v2: Add new field 'cwnd_prior' in bictcp to hold cwnd before a loss event v1->v2: Separate patches

 net/ipv4/tcp_cubic.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
net/ipv4/tcp_cubic.c +6 -1
index 11bad5317a8f..7bc6db82de66 100644
@@ -102,6 +102,7 @@ struct bictcp {
 	u32	end_seq;	/* end_seq of the round */
 	u32	last_ack;	/* last time when the ACK spacing is close */
 	u32	curr_rtt;	/* the minimum rtt of current round */
+	u32	cwnd_prior;	/* cwnd before a loss event */
 };
 
 static inline void bictcp_reset(struct bictcp *ca)
@@ -305,7 +306,10 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
 	if (tcp_friendliness) {
 		u32 scale = beta_scale;
 
-		delta = (cwnd * scale) >> 3;
+		if (cwnd < ca->cwnd_prior)
+			delta = (cwnd * scale) >> 3;	/* CUBIC additive increment */
+		else
+			delta = cwnd;			/* Reno additive increment */
 		while (ca->ack_cnt > delta) {		/* update tcp cwnd */
 			ca->ack_cnt -= delta;
 			ca->tcp_cwnd++;
@@ -355,6 +359,7 @@ __bpf_kfunc static u32 cubictcp_recalc_ssthresh(struct sock *sk)
 			/ (2 * BICTCP_BETA_SCALE);
 	else
 		ca->last_max_cwnd = tcp_snd_cwnd(tp);
+	ca->cwnd_prior = tcp_snd_cwnd(tp);
 
 	return max((tcp_snd_cwnd(tp) * beta) / BICTCP_BETA_SCALE, 2U);
 }
Signature · 1 line
2.34.1
#5 lore raw

PATCH v3 3/3 tcp_cubic: fix to use emulated Reno cwnd one RTT in the future

In reply to Mingrui Zhang

The original code estimates RENO snd_cwnd using the estimated RENO snd_cwnd at the current time (i.e., tcp_cwnd).

The patched code estimates RENO snd_cwnd using the estimated RENO snd_cwnd after one RTT (i.e., tcp_cwnd_next_rtt), because ca->cnt is used to increase snd_cwnd for the next RTT.

Fixes 89b3d9aaf467 ("[TCP] cubic: precompute constants")

---
v2->v3: Corrent the "Fixes:" footer content
v1->v2: Separate patches

 net/ipv4/tcp_cubic.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
net/ipv4/tcp_cubic.c +5 -2
index 7bc6db82de66..a1467f99a233 100644
@@ -315,8 +315,11 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
 			ca->tcp_cwnd++;
 		}
 
-		if (ca->tcp_cwnd > cwnd) {	/* if bic is slower than tcp */
-			delta = ca->tcp_cwnd - cwnd;
+		/* Reno cwnd one RTT in the future */
+		u32 tcp_cwnd_next_rtt = ca->tcp_cwnd + (ca->ack_cnt + cwnd) / delta;
+
+		if (tcp_cwnd_next_rtt > cwnd) {  /* if bic is slower than Reno */
+			delta = tcp_cwnd_next_rtt - cwnd;
 			max_cnt = cwnd / delta;
 			if (ca->cnt > max_cnt)
 				ca->cnt = max_cnt;
Signature · 1 line
2.34.1
maintainer
#6 lore raw

Re: [PATCH net v3 3/3] tcp_cubic: fix to use emulated Reno cwnd one RTT in the future

Quoted 27 lines · Mingrui Zhang

The original code estimates RENO snd_cwnd using the estimated RENO snd_cwnd at the current time (i.e., tcp_cwnd).

The patched code estimates RENO snd_cwnd using the estimated RENO snd_cwnd after one RTT (i.e., tcp_cwnd_next_rtt), because ca->cnt is used to increase snd_cwnd for the next RTT.

Fixes 89b3d9aaf467 ("[TCP] cubic: precompute constants")

---
v2->v3: Corrent the "Fixes:" footer content
v1->v2: Separate patches

 net/ipv4/tcp_cubic.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
net/ipv4/tcp_cubic.c +0 -1
index 7bc6db82de66..a1467f99a233 100644
@@ -315,8 +315,11 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
                        ca->tcp_cwnd++;
                }
 
-               if (ca->tcp_cwnd > cwnd) {      /* if bic is slower than tcp */

net/ipv4/tcp_cubic.c static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)

Quoted 10 lines
net/ipv4/tcp_cubic.c +5 -2
-                       delta = ca->tcp_cwnd - cwnd;
+               /* Reno cwnd one RTT in the future */
+               u32 tcp_cwnd_next_rtt = ca->tcp_cwnd + (ca->ack_cnt + cwnd) / delta;
+
+               if (tcp_cwnd_next_rtt > cwnd) {  /* if bic is slower than Reno */
+                       delta = tcp_cwnd_next_rtt - cwnd;
                        max_cnt = cwnd / delta;
                        if (ca->cnt > max_cnt)
                                ca->cnt = max_cnt;
--

I'm getting a compilation error with clang:

net/ipv4/tcp_cubic.c:322:7: error: mixing declarations and code is incompatible with standards before C99 [-Werror,-Wdeclaration-after-statement]

    u32 tcp_cwnd_next_rtt = ca->tcp_cwnd + (ca->ack_cnt + cwnd) / delta;

Can you please try something like the following:

- u32 scale = beta_scale;
+ u32 scale = beta_scale, tcp_cwnd_next_rtt;
...
+ tcp_cwnd_next_rtt = ca->tcp_cwnd + (ca->ack_cnt + cwnd) / delta;

Thanks!
neal

#7 lore raw

Re: [PATCH net v3 3/3] tcp_cubic: fix to use emulated Reno cwnd one RTT in the future

Quoted 51 lines · Neal Cardwell
Quoted 26 lines · Mingrui Zhang

The original code estimates RENO snd_cwnd using the estimated RENO snd_cwnd at the current time (i.e., tcp_cwnd).

The patched code estimates RENO snd_cwnd using the estimated RENO snd_cwnd after one RTT (i.e., tcp_cwnd_next_rtt), because ca->cnt is used to increase snd_cwnd for the next RTT.

Fixes 89b3d9aaf467 ("[TCP] cubic: precompute constants")

---
v2->v3: Corrent the "Fixes:" footer content
v1->v2: Separate patches

 net/ipv4/tcp_cubic.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
net/ipv4/tcp_cubic.c +0 -1
index 7bc6db82de66..a1467f99a233 100644
@@ -315,8 +315,11 @@ static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
                        ca->tcp_cwnd++;
                }
 
-               if (ca->tcp_cwnd > cwnd) {      /* if bic is slower than tcp */

net/ipv4/tcp_cubic.c static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)

Quoted 10 lines
net/ipv4/tcp_cubic.c +5 -2
-                       delta = ca->tcp_cwnd - cwnd;
+               /* Reno cwnd one RTT in the future */
+               u32 tcp_cwnd_next_rtt = ca->tcp_cwnd + (ca->ack_cnt + cwnd) / delta;
+
+               if (tcp_cwnd_next_rtt > cwnd) {  /* if bic is slower than Reno */
+                       delta = tcp_cwnd_next_rtt - cwnd;
                        max_cnt = cwnd / delta;
                        if (ca->cnt > max_cnt)
                                ca->cnt = max_cnt;
--

I'm getting a compilation error with clang:

net/ipv4/tcp_cubic.c:322:7: error: mixing declarations and code is incompatible with standards before C99 [-Werror,-Wdeclaration-after-statement]

    u32 tcp_cwnd_next_rtt = ca->tcp_cwnd + (ca->ack_cnt + cwnd) / delta;

Can you please try something like the following:

(quoted diff) +2 -1
-               u32 scale = beta_scale;
+               u32 scale = beta_scale, tcp_cwnd_next_rtt;
...
+               tcp_cwnd_next_rtt = ca->tcp_cwnd + (ca->ack_cnt + cwnd) / delta;
Quoted 2 lines

Thanks!
neal

Thank you, Neal,
We have tried your suggested changes, and they also work for our compile and experiment tests. We did not find this issue because we have only tried to compile with the default Makefile with GCC. I agree with your changes, it is conform to the existing codes and compatible with that standards.

Thanks,
Mingrui