Skip to contentSkip to conversation

TCP CUBIC Hystart fixes

PATCH In review Stephen Hemminger 4 participants 15 messages Mar 14, 2011 – Mar 22, 2011

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover TCP CUBIC Hystart fixes

This is the merge of my patches and recent update Sangtae. It addresses the problems reported by Lucas Nussbaum that Hystart causes poor startup performance over links with lots of buffering.

#1 lore raw

PATCH 1/7 tcp: fix RTT for quick packets in congestion control

In the congestion control interface, the callback for each ACK includes an estimated round trip time in microseconds.
Some algorithms need high resolution (Vegas style) but most only need jiffie resolution. If RTT is not accurate (like a retransmission) -1 is used as a flag value.

When doing coarse resolution if RTT is less than a a jiffie then 0 should be returned rather than no estimate. Otherwise algorithms that expect good ack's to trigger slow start (like CUBIC Hystart) will be confused.

net/ipv4/tcp_input.c +1 -1
@@ -3350,7 +3350,7 @@ static int tcp_clean_rtx_queue(struct so
 						 net_invalid_timestamp()))
 					rtt_us = ktime_us_delta(ktime_get_real(),
 								last_ackt);
-				else if (ca_seq_rtt > 0)
+				else if (ca_seq_rtt >= 0)
 					rtt_us = jiffies_to_usecs(ca_seq_rtt);
 			}
 
#2 lore raw

PATCH 2/7 tcp_cubic: fix comparison of jiffies

In reply to Stephen Hemminger

Jiffies wraps around therefore the correct way to compare is to use cast to signed value.

Note: cubic is not using full jiffies value on 64 bit arch because using full unsigned long makes struct bictcp grow too large for the available ca_priv area.

Includes correction from Sangtae Ha to improve ack train detection.

net/ipv4/tcp_cubic.c +4 -2
@@ -342,9 +342,11 @@ static void hystart_update(struct sock *
 		u32 curr_jiffies = jiffies;
 
 		/* first detection parameter - ack-train detection */
-		if (curr_jiffies - ca->last_jiffies <= msecs_to_jiffies(2)) {
+		if ((s32)(curr_jiffies - ca->last_jiffies) <=
+		    msecs_to_jiffies(2)) {
 			ca->last_jiffies = curr_jiffies;
-			if (curr_jiffies - ca->round_start >= ca->delay_min>>4)
+			if ((s32) (curr_jiffies - ca->round_start) >
+			    ca->delay_min >> 4)
 				ca->found |= HYSTART_ACK_TRAIN;
 		}
 
#3 lore raw

PATCH 3/7 tcp_cubic: make ack train delta value a parameter

In reply to Stephen Hemminger

Make the spacing between ACK's that indicates a train a tuneable value like other hystart values.

net/ipv4/tcp_cubic.c +4 -1
@@ -52,6 +52,7 @@ static int tcp_friendliness __read_mostl
 static int hystart __read_mostly = 1;
 static int hystart_detect __read_mostly = HYSTART_ACK_TRAIN | HYSTART_DELAY;
 static int hystart_low_window __read_mostly = 16;
+static int hystart_ack_delta __read_mostly = 2;
 
 static u32 cube_rtt_scale __read_mostly;
 static u32 beta_scale __read_mostly;
@@ -75,6 +76,8 @@ MODULE_PARM_DESC(hystart_detect, "hyrbri
 		 " 1: packet-train 2: delay 3: both packet-train and delay");
 module_param(hystart_low_window, int, 0644);
 MODULE_PARM_DESC(hystart_low_window, "lower bound cwnd for hybrid slow start");
+module_param(hystart_ack_delta, int, 0644);
+MODULE_PARM_DESC(hystart_ack_delta, "spacing between ack's indicating train (msecs)");
 
 /* BIC TCP Parameters */
 struct bictcp {
@@ -343,7 +346,7 @@ static void hystart_update(struct sock *
 
 		/* first detection parameter - ack-train detection */
 		if ((s32)(curr_jiffies - ca->last_jiffies) <=
-		    msecs_to_jiffies(2)) {
+		    msecs_to_jiffies(hystart_ack_delta)) {
 			ca->last_jiffies = curr_jiffies;
 			if ((s32) (curr_jiffies - ca->round_start) >
 			    ca->delay_min >> 4)
#4 lore raw

PATCH 4/7 tcp_cubic: fix clock dependency

In reply to Stephen Hemminger

The hystart code was written with assumption that HZ=1000. Replace the use of jiffies with bictcp_clock as a millisecond real time clock.

net/ipv4/tcp_cubic.c +19 -12
@@ -88,7 +88,7 @@ struct bictcp {
 	u32	last_time;	/* time when updated last_cwnd */
 	u32	bic_origin_point;/* origin point of bic function */
 	u32	bic_K;		/* time to origin point from the beginning of the current epoch */
-	u32	delay_min;	/* min delay */
+	u32	delay_min;	/* min delay (msec << 3) */
 	u32	epoch_start;	/* beginning of an epoch */
 	u32	ack_cnt;	/* number of acks */
 	u32	tcp_cwnd;	/* estimated tcp cwnd */
@@ -98,7 +98,7 @@ struct bictcp {
 	u8	found;		/* the exit point is found? */
 	u32	round_start;	/* beginning of each round */
 	u32	end_seq;	/* end_seq of the round */
-	u32	last_jiffies;	/* last time when the ACK spacing is close */
+	u32	last_ack;	/* last time when the ACK spacing is close */
 	u32	curr_rtt;	/* the minimum rtt of current round */
 };
 
@@ -119,12 +119,21 @@ static inline void bictcp_reset(struct b
 	ca->found = 0;
 }
 
+static inline u32 bictcp_clock(void)
+{
+#if HZ < 1000
+	return ktime_to_ms(ktime_get_real());
+#else
+	return jiffies_to_msecs(jiffies);
+#endif
+}
+
 static inline void bictcp_hystart_reset(struct sock *sk)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
 	struct bictcp *ca = inet_csk_ca(sk);
 
-	ca->round_start = ca->last_jiffies = jiffies;
+	ca->round_start = ca->last_ack = bictcp_clock();
 	ca->end_seq = tp->snd_nxt;
 	ca->curr_rtt = 0;
 	ca->sample_cnt = 0;
@@ -239,8 +248,8 @@ static inline void bictcp_update(struct
 	 */
 
 	/* change the unit from HZ to bictcp_HZ */
-	t = ((tcp_time_stamp + (ca->delay_min>>3) - ca->epoch_start)
-	     << BICTCP_HZ) / HZ;
+	t = ((tcp_time_stamp + msecs_to_jiffies(ca->delay_min>>3)
+	      - ca->epoch_start) << BICTCP_HZ) / HZ;
 
 	if (t < ca->bic_K)		/* t - K */
 		offs = ca->bic_K - t;
@@ -342,14 +351,12 @@ static void hystart_update(struct sock *
 	struct bictcp *ca = inet_csk_ca(sk);
 
 	if (!(ca->found & hystart_detect)) {
-		u32 curr_jiffies = jiffies;
+		u32 now = bictcp_clock();
 
 		/* first detection parameter - ack-train detection */
-		if ((s32)(curr_jiffies - ca->last_jiffies) <=
-		    msecs_to_jiffies(hystart_ack_delta)) {
-			ca->last_jiffies = curr_jiffies;
-			if ((s32) (curr_jiffies - ca->round_start) >
-			    ca->delay_min >> 4)
+		if ((s32)(now - ca->last_ack) <= hystart_ack_delta) {
+			ca->last_ack = now;
+			if ((s32)(now - ca->round_start) > ca->delay_min >> 4)
 				ca->found |= HYSTART_ACK_TRAIN;
 		}
 
@@ -396,7 +403,7 @@ static void bictcp_acked(struct sock *sk
 	if ((s32)(tcp_time_stamp - ca->epoch_start) < HZ)
 		return;
 
-	delay = usecs_to_jiffies(rtt_us) << 3;
+	delay = (rtt_us << 3) / USEC_PER_MSEC;
 	if (delay == 0)
 		delay = 1;
 
#8 lore raw

PATCH 5/7 tcp_cubic: enable high resolution ack time if needed

In reply to Stephen Hemminger

This is a refined version of an earlier patch by Lucas Nussbaum. Cubic needs RTT values in milliseconds. If HZ < 1000 then the values will be too coarse.

net/ipv4/tcp_cubic.c +4 -0
@@ -459,6 +459,10 @@ static int __init cubictcp_register(void
 	/* divide by bic_scale and by constant Srtt (100ms) */
 	do_div(cube_factor, bic_scale * 10);
 
+	/* hystart needs ms clock resolution */
+	if (hystart && HZ < 1000)
+		cubictcp.flags |= TCP_CONG_RTT_STAMP;
+
 	return tcp_register_congestion_control(&cubictcp);
 }
 
#9 lore raw

PATCH 6/7 tcp_cubic: make the delay threshold of HyStart less sensitive

In reply to Stephen Hemminger

From: Sangtae Ha <[email protected]>

Make HyStart less sensitive to abrupt delay variations due to buffer bloat.

---
 net/ipv4/tcp_cubic.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
net/ipv4/tcp_cubic.c +1 -1
@@ -39,7 +39,7 @@
 
 /* Number of delay samples for detecting the increase of delay */
 #define HYSTART_MIN_SAMPLES	8
-#define HYSTART_DELAY_MIN	(2U<<3)
+#define HYSTART_DELAY_MIN	(4U<<3)
 #define HYSTART_DELAY_MAX	(16U<<3)
 #define HYSTART_DELAY_THRESH(x)	clamp(x, HYSTART_DELAY_MIN, HYSTART_DELAY_MAX)
 
#10 lore raw

PATCH 7/7 tcp_cubic: fix low utilization of CUBIC with HyStart

In reply to Stephen Hemminger

From: Sangtae Ha <[email protected]>

HyStart sets the initial exit point of slow start.
Suppose that HyStart exits at 0.5BDP in a BDP network and no history exists. If the BDP of a network is large, CUBIC's initial cwnd growth may be too conservative to utilize the link.
CUBIC increases the cwnd 20% per RTT in this case.

---
 net/ipv4/tcp_cubic.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)
net/ipv4/tcp_cubic.c +7 -0
@@ -270,6 +270,13 @@ static inline void bictcp_update(struct
 		ca->cnt = 100 * cwnd;              /* very small increment*/
 	}
 
+	/*
+	 * The initial growth of cubic function may be too conservative
+	 * when the available bandwidth is still unknown.
+	 */
+	if (ca->loss_cwnd == 0 && ca->cnt > 20)
+		ca->cnt = 20;	/* increase cwnd 5% per RTT */
+
 	/* TCP Friendly */
 	if (tcp_friendliness) {
 		u32 scale = beta_scale;
#5 lore raw

Re: [PATCH 4/7] tcp_cubic: fix clock dependency

In reply to Stephen Hemminger
Quoted 29 lines · Stephen Hemminger

pièce jointe document texte brut (tcp-cubic-minrtt.patch) The hystart code was written with assumption that HZ=1000. Replace the use of jiffies with bictcp_clock as a millisecond real time clock.

net/ipv4/tcp_cubic.c +2 -2
@@ -88,7 +88,7 @@ struct bictcp {
 	u32	last_time;	/* time when updated last_cwnd */
 	u32	bic_origin_point;/* origin point of bic function */
 	u32	bic_K;		/* time to origin point from the beginning of the current epoch */
-	u32	delay_min;	/* min delay */
+	u32	delay_min;	/* min delay (msec << 3) */
 	u32	epoch_start;	/* beginning of an epoch */
 	u32	ack_cnt;	/* number of acks */
 	u32	tcp_cwnd;	/* estimated tcp cwnd */
@@ -98,7 +98,7 @@ struct bictcp {
 	u8	found;		/* the exit point is found? */
 	u32	round_start;	/* beginning of each round */
 	u32	end_seq;	/* end_seq of the round */
-	u32	last_jiffies;	/* last time when the ACK spacing is close */
+	u32	last_ack;	/* last time when the ACK spacing is close */
 	u32	curr_rtt;	/* the minimum rtt of current round */
 };
 

net/ipv4/tcp_cubic.c static inline void bictcp_reset(struct b · line 125

Quoted 7 lines
net/ipv4/tcp_cubic.c +4 -0
@@ -119,12 +119,21 @@ static inline void bictcp_reset(struct b
 	ca->found = 0;
 }
 
+static inline u32 bictcp_clock(void)
+{
+#if HZ < 1000
+	return ktime_to_ms(ktime_get_real());

Small point : This can be changed if date/time is changed

Maybe use monotonic time (aka ktime_get_ts()) ?

#6 lore raw

Re: [PATCH 4/7] tcp_cubic: fix clock dependency

Quoted 33 lines · On Mon, 14 Mar 2011 19:51:19 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 32 lines · Stephen Hemminger

pièce jointe document texte brut (tcp-cubic-minrtt.patch) The hystart code was written with assumption that HZ=1000. Replace the use of jiffies with bictcp_clock as a millisecond real time clock.

net/ipv4/tcp_cubic.c +2 -2
@@ -88,7 +88,7 @@ struct bictcp {
 	u32	last_time;	/* time when updated last_cwnd */
 	u32	bic_origin_point;/* origin point of bic function */
 	u32	bic_K;		/* time to origin point from the beginning of the current epoch */
-	u32	delay_min;	/* min delay */
+	u32	delay_min;	/* min delay (msec << 3) */
 	u32	epoch_start;	/* beginning of an epoch */
 	u32	ack_cnt;	/* number of acks */
 	u32	tcp_cwnd;	/* estimated tcp cwnd */
@@ -98,7 +98,7 @@ struct bictcp {
 	u8	found;		/* the exit point is found? */
 	u32	round_start;	/* beginning of each round */
 	u32	end_seq;	/* end_seq of the round */
-	u32	last_jiffies;	/* last time when the ACK spacing is close */
+	u32	last_ack;	/* last time when the ACK spacing is close */
 	u32	curr_rtt;	/* the minimum rtt of current round */
 };
 
@@ -119,12 +119,21 @@ static inline void bictcp_reset(struct b
 	ca->found = 0;
 }
 
Quoted 8 lines

net/ipv4/tcp_cubic.c static inline void bictcp_reset(struct b · line 125

Quoted 4 lines
net/ipv4/tcp_cubic.c +4 -0
+static inline u32 bictcp_clock(void)
+{
+#if HZ < 1000
+	return ktime_to_ms(ktime_get_real());

Small point : This can be changed if date/time is changed

Maybe use monotonic time (aka ktime_get_ts()) ?

I choose get_real() because that is what skb timestamp is using; both should probably use monotonic clock.

#7 lore raw

Re: [PATCH 4/7] tcp_cubic: fix clock dependency

Quoted 4 lines · Stephen Hemminger

I choose get_real() because that is what skb timestamp is using; both should probably use monotonic clock.

This point was raised elsewhere, problem is tcpdump/libpcap probably wants "real" time, not monotonic clock...

maintainer
#11 lore raw
In reply to Stephen Hemminger

From: Stephen Hemminger <[email protected]>
Date: Mon, 14 Mar 2011 10:52:11 -0700

Quoted 3 lines

This is the merge of my patches and recent update Sangtae. It addresses the problems reported by Lucas Nussbaum that Hystart causes poor startup performance over links with lots of buffering.

Ok, I've applied all of this to net-2.6 and did test builds with HZ={100,250,1000} on both sparc64 and x86.

I'll let it cook for a day or two before pushing it out to Linus.

Tested-by on the v1 series
#12 lore raw
In reply to Stephen Hemminger
Quoted 3 lines · Stephen Hemminger

This is the merge of my patches and recent update Sangtae. It addresses the problems reported by Lucas Nussbaum that Hystart causes poor startup performance over links with lots of buffering.

Hi,

I've tested the patches, and they work fine.

Here are some results (gigabit link, RTT=11ms).

Without the patches, hystart disabled:
Segments (cwnd, ssthresh)
2500 ++-----------+-------------+------------+-------------+-----------++
+ + + + snd_cwnd ****** +
| snd_ssthresh ###### |
2000 ++ ************************************************* ++

        |       **                                                         |
        |       *                                                          |
        |       *                                                          |
   1500 ++      *                                                         ++
        |       *                                                          |
        |       *                                                          |
   1000 ++      *                                                         ++
        |      **                                                          |
        |      *                                                           |
        |      *                                                           |
    500 ++     *                                                          ++
        |     **                                                           |
        +    **      +             +            +             +            +

0 ++-***####################################################--------++
0 0.5 1 1.5 2 2.5
time (seconds)

Without the patches, hystart enabled:
Segments (cwnd, ssthresh)
300 ++------------+------------+-------------+------------+------------++
+ + + + snd_cwnd ****** +
| ***snd_ssthresh ###### |
250 ++ *********************** ++

       |     ******************###################################         |
       |     *                                                             |
   200 ++    *                                                            ++
       |     *                                                             |
   150 ++    *                                                            ++
       |     *                                                             |
       |     *                                                             |
   100 ++   **                                                            ++
       |    *#                                                             |
       |    *#                                                             |
    50 ++   *#                                                            ++
       |   **#                                                             |
       +  ** #       +            +             +            +             +

0 ++-*###-------+------------+-------------+------------+------------++
0 0.5 1 1.5 2 2.5
time (seconds)

Note how slow start ends very early (~ 230 segments), resulting in poor performance.

With the patches, hystart enabled, run 1:
Segments (cwnd, ssthresh)
2500 ++-----+-------+------+-------+------+-------+------+-------+-----++
+ + + + + + + snd_cwnd ****** +
| snd_ssthresh ###### |

   2000 ++   *********************************************************    ++
        |    *                                                             |
        |    *                                                             |
        |    *                                                             |
   1500 ++   *                                                            ++
        |    *                                                             |
        |   **                                                             |
   1000 ++  *                                                             ++
        |   *                                                              |
        |   *                                                              |
        |   *                                                              |
    500 ++  *                                                             ++
        |  **                                                              |
        +  *   +       +      +       +      +       +      +       +      +
      0 ++**##########################################################----++
        0     0.5      1     1.5      2     2.5      3     3.5      4     4.5
                                  time (seconds)

There's no perceived delay increase, but also no losses. The NIC sends data at line rate without congestion. we don't exit slow start, but that's fine:

With the patch, hystart enabled, run 2: (that's the most frequent situation)
Segments (cwnd, ssthresh)
2500 ++-----+-------+------+-------+------+-------+------+-------+-----++
+ + + + + + + snd_cwnd ****** +
| snd_ssthresh ###### |

   2000 ++    ********************************************************    ++
        |     *#                                                           |
        |     *#                                                           |
        |     *#                                                           |
   1500 ++    *#                                                          ++
        |     *#                                                           |
        |     *#                                                           |
   1000 ++   **#                                                          ++
        |    * #                                                           |
        |    * #                                                           |
        |    * #                                                           |

500 ++ ** # ++
| * # |
+ ** # + + + + + + + +
0 ++**####-------+------+-------+------+-------+------+-------+-----++
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5
time (seconds)

Hystart detects a delay increase, so we exit slow start, but at a reasonable point. Hystart works fine in that case. (no impact on performance).

With the patch, hystart enabled, run 3:
Segments (cwnd, ssthresh)
2500 ++-----+-------+------+-------+------+-------+------+-------+-----++
+ + + + + + + snd_cwnd ****** +
| snd_ssthresh ###### |
2000 ++ ******************************************************* ++

        |      *                                                           |
        |     **                                                           |
        |     *                                                            |
   1500 ++   **#######################################################    ++
        |    *#                                                            |
        |    *#                                                            |
   1000 ++   *#                                                           ++
        |    *#                                                            |
        |   **#                                                            |
        |   * #                                                            |
    500 ++  * #                                                           ++
        |   * #                                                            |
        +  ** #+       +      +       +      +       +      +       +      +
      0 ++**###+-------+------+-------+------+-------+------+-------+-----++
        0     0.5      1     1.5      2     2.5      3     3.5      4     4.5
                                  time (seconds)

Hystart causes slow start to end a bit too early, but late enough not to affect performance significantly. Hystart behaves fine in that case too.

Signature · 3 lines
| Lucas Nussbaum             MCF Université Nancy 2 |
| [email protected]         LORIA / AlGorille |
| http://www.loria.fr/~lnussbau/  +33 3 54 95 86 19 |
#13 lore raw
In reply to Stephen Hemminger
Quoted 3 lines · Stephen Hemminger

This is the merge of my patches and recent update Sangtae. It addresses the problems reported by Lucas Nussbaum that Hystart causes poor startup performance over links with lots of buffering.

What do you plan to do regarding stable kernels? We should probably either push that patch serie, or disable hystart if HZ < 1000.

Signature · 3 lines
| Lucas Nussbaum             MCF Université Nancy 2 |
| [email protected]         LORIA / AlGorille |
| http://www.loria.fr/~lnussbau/  +33 3 54 95 86 19 |
maintainer
#14 lore raw

From: Lucas Nussbaum <[email protected]>
Date: Tue, 22 Mar 2011 12:35:42 +0100

Quoted 7 lines · Stephen Hemminger
Quoted 3 lines

This is the merge of my patches and recent update Sangtae. It addresses the problems reported by Lucas Nussbaum that Hystart causes poor startup performance over links with lots of buffering.

What do you plan to do regarding stable kernels? We should probably either push that patch serie, or disable hystart if HZ < 1000.

I think once the patch series gets some soaking time in Linus's tree we can send it over to -stable.