TCP CUBIC Hystart fixes
Subsystems (3)
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.
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); }
PATCH 2/7 tcp_cubic: fix comparison of jiffies
In reply to Stephen HemmingerJiffies 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 ; }
PATCH 3/7 tcp_cubic: make ack train delta value a parameter
In reply to Stephen HemmingerMake 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_mostlstatic 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 )
PATCH 4/7 tcp_cubic: fix clock dependency
In reply to Stephen HemmingerThe 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 *skif ((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 ;
PATCH 5/7 tcp_cubic: enable high resolution ack time if needed
In reply to Stephen HemmingerThis 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); }
PATCH 6/7 tcp_cubic: make the delay threshold of HyStart less sensitive
In reply to Stephen HemmingerFrom: 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)
PATCH 7/7 tcp_cubic: fix low utilization of CUBIC with HyStart
In reply to Stephen HemmingerFrom: 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;
Re: [PATCH 4/7] tcp_cubic: fix clock dependency
In reply to Stephen HemmingerQuoted 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_clockas a millisecond real time clock.Signed-off-by Stephen Hemminger <[email protected]>Reported-by Lucas Nussbaum <[email protected]>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()) ?
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_clockas a millisecond real time clock.Signed-off-by Stephen Hemminger <[email protected]>Reported-by Lucas Nussbaum <[email protected]>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.
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...
David Miller
maintainerFrom: 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.
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 |
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 |
David Miller
maintainerFrom: 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.