15 messages, 4 authors, 2011-03-22 · open the first message on its own page
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:03
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.
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:03
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. Signed-off-by: Stephen Hemminger <redacted>
--- a/net/ipv4/tcp_cubic.c 2011-03-11 09:00:06.856664687 -0800
+++ b/net/ipv4/tcp_cubic.c 2011-03-11 09:02:11.685796371 -0800@@ -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; }
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:03
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. Signed-off-by: Stephen Hemminger <redacted>
--- a/net/ipv4/tcp_input.c 2011-03-14 08:31:35.442834792 -0700
+++ b/net/ipv4/tcp_input.c 2011-03-14 08:31:40.078917049 -0700@@ -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); }
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:03
The hystart code was written with assumption that HZ=1000. Replace the use of jiffies with bictcp_clock as a millisecond real time clock. Signed-off-by: Stephen Hemminger <redacted> Reported-by: Lucas Nussbaum <redacted>
--- a/net/ipv4/tcp_cubic.c 2011-03-14 08:19:18.000000000 -0700
+++ b/net/ipv4/tcp_cubic.c 2011-03-14 08:22:42.486690594 -0700@@ -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;
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:03
Make the spacing between ACK's that indicates a train a tuneable value like other hystart values. Signed-off-by: Stephen Hemminger <redacted>
--- a/net/ipv4/tcp_cubic.c 2011-03-14 08:19:15.697936023 -0700
+++ b/net/ipv4/tcp_cubic.c 2011-03-14 08:19:18.361944814 -0700@@ -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)
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:04
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. Signed-off-by: Stephen Hemminger <redacted> Reported-by: Lucas Nussbaum <redacted>
--- a/net/ipv4/tcp_cubic.c 2011-03-14 08:22:42.486690594 -0700
+++ b/net/ipv4/tcp_cubic.c 2011-03-14 08:27:24.435852847 -0700@@ -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); }
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:04
From: Sangtae Ha <redacted> 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. Signed-off-by: Sangtae Ha <redacted> Acked-by: Stephen Hemminger <redacted> --- net/ipv4/tcp_cubic.c | 9 +++++++++ 1 files changed, 9 insertions(+), 0 deletions(-)
--- a/net/ipv4/tcp_cubic.c 2011-03-14 08:32:46.347993869 -0700
+++ b/net/ipv4/tcp_cubic.c 2011-03-14 10:57:00.846549449 -0700@@ -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;
From: Stephen Hemminger <hidden>
Date: 2011-03-14 18:02:04
From: Sangtae Ha <redacted> Make HyStart less sensitive to abrupt delay variations due to buffer bloat. Signed-off-by: Sangtae Ha <redacted> Acked-by: Stephen Hemminger <redacted> Reported-by: Lucas Nussbaum <redacted> --- net/ipv4/tcp_cubic.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
--- a/net/ipv4/tcp_cubic.c 2011-03-14 08:27:24.435852847 -0700
+++ b/net/ipv4/tcp_cubic.c 2011-03-14 08:27:29.043872578 -0700@@ -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)
From: Eric Dumazet <hidden>
Date: 2011-03-14 18:52:31
Le lundi 14 mars 2011 à 10:52 -0700, Stephen Hemminger a écrit :
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. Signed-off-by: Stephen Hemminger <redacted> Reported-by: Lucas Nussbaum <redacted>--- a/net/ipv4/tcp_cubic.c 2011-03-14 08:19:18.000000000 -0700 +++ b/net/ipv4/tcp_cubic.c 2011-03-14 08:22:42.486690594 -0700@@ -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());
Small point : This can be changed if date/time is changed Maybe use monotonic time (aka ktime_get_ts()) ?
From: Stephen Hemminger <hidden>
Date: 2011-03-14 21:21:27
On Mon, 14 Mar 2011 19:51:19 +0100 Eric Dumazet [off-list ref] wrote:
Le lundi 14 mars 2011 à 10:52 -0700, Stephen Hemminger a écrit :quoted
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. Signed-off-by: Stephen Hemminger <redacted> Reported-by: Lucas Nussbaum <redacted>--- a/net/ipv4/tcp_cubic.c 2011-03-14 08:19:18.000000000 -0700 +++ b/net/ipv4/tcp_cubic.c 2011-03-14 08:22:42.486690594 -0700@@ -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());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. --
From: Eric Dumazet <hidden>
Date: 2011-03-14 21:37:12
Le lundi 14 mars 2011 à 14:21 -0700, Stephen Hemminger a écrit :
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...
From: David Miller <davem@davemloft.net>
Date: 2011-03-14 22:57:27
From: Stephen Hemminger <redacted> Date: Mon, 14 Mar 2011 10:52:11 -0700
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.
From: Lucas Nussbaum <hidden>
Date: 2011-03-22 11:35:44
On 14/03/11 at 10:52 -0700, Stephen Hemminger wrote:
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.
Tested-By: Lucas Nussbaum <redacted>
--
| Lucas Nussbaum MCF Université Nancy 2 |
| lucas.nussbaum@loria.fr LORIA / AlGorille |
| http://www.loria.fr/~lnussbau/ +33 3 54 95 86 19 |
From: Lucas Nussbaum <hidden>
Date: 2011-03-22 11:35:44
On 14/03/11 at 10:52 -0700, Stephen Hemminger wrote:
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. -- | Lucas Nussbaum MCF Université Nancy 2 | | lucas.nussbaum@loria.fr LORIA / AlGorille | | http://www.loria.fr/~lnussbau/ +33 3 54 95 86 19 |
From: David Miller <davem@davemloft.net>
Date: 2011-03-22 12:04:28
From: Lucas Nussbaum <redacted> Date: Tue, 22 Mar 2011 12:35:42 +0100
On 14/03/11 at 10:52 -0700, Stephen Hemminger wrote:quoted
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.