tcp: refactor F-RTO
Subsystems (4)
PATCH v2 1/3 tcp: refactor F-RTO
The patch series refactor the F-RTO feature (RFC4138/5682).
This is to simplify the loss recovery processing. Existing F-RTO was developed during the experimental stage (RFC4138) and has many experimental features. It takes a separate code path from the traditional timeout processing by overloading CA_Disorder instead of using CA_Loss state. This complicates CA_Disorder state handling because it's also used for handling dubious ACKs and undos. While the algorithm in the RFC does not change the congestion control, the implementation intercepts congestion control in various places (e.g., frto_cwnd in tcp_ack()).
The new code implements newer F-RTO RFC5682 using CA_Loss processing path. F-RTO becomes a small extension in the timeout processing and interfaces with congestion control and Eifel undo modules. It lets congestion control (module) determines how many to send independently. F-RTO only chooses what to send in order to detect spurious retranmission. If timeout is found spurious it invokes existing Eifel undo algorithms like DSACK or TCP timestamp based detection.
The first patch removes all F-RTO code except the sysctl_tcp_frto is left for the new implementation. Since CA_EVENT_FRTO is removed, TCP westwood now computes ssthresh on regular timeout CA_EVENT_LOSS event.
--- Documentation/networking/ip-sysctl.txt | 17 -- include/linux/tcp.h | 6 +- include/net/tcp.h | 4 - net/ipv4/sysctl_net_ipv4.c | 7 - net/ipv4/tcp_input.c | 375 +-------------------------------- net/ipv4/tcp_minisocks.c | 3 - net/ipv4/tcp_output.c | 11 +- net/ipv4/tcp_timer.c | 6 +- net/ipv4/tcp_westwood.c | 2 +- 9 files changed, 10 insertions(+), 421 deletions(-)
Documentation/networking/ip-sysctl.txt +0 -17
@@ -239,23 +239,6 @@ tcp_frto - INTEGER interacts badly with the packet counting of the SACK enabled TCP flow. -tcp_frto_response - INTEGER - When F-RTO has detected that a TCP retransmission timeout was - spurious (i.e, the timeout would have been avoided had TCP set a - longer retransmission timeout), TCP has several options what to do - next. Possible values are: - 0 Rate halving based; a smooth and conservative response, - results in halved cwnd and ssthresh after one RTT - 1 Very conservative response; not recommended because even - though being valid, it interacts poorly with the rest of - Linux TCP, halves cwnd and ssthresh immediately - 2 Aggressive response; undoes congestion control measures - that are now known to be unnecessary (ignoring the - possibility of a lost retransmission that would require - TCP to be more cautious), cwnd and ssthresh are restored - to the values prior timeout - Default: 0 (rate halving based) - tcp_keepalive_time - INTEGER How often TCP sends out keepalive messages when keepalive is enabled. Default: 2hours.
include/linux/tcp.h +2 -4
@@ -187,14 +187,12 @@ struct tcp_sock {u32 window_clamp;/* Maximal window to advertise */ u32 rcv_ssthresh;/* Current window clamp */ -u32 frto_highmark;/* snd_nxt when RTO occurred */ u16 advmss;/* Advertised MSS */ -u8 frto_counter;/* Number of new acks after RTO */ +u8 unused; u8 nonagle : 4,/* Disable Nagle algorithm? */ thin_lto : 1,/* Use linear timeouts for thin streams */ thin_dupack : 1,/* Fast retransmit on first dupack */ - repair : 1, - unused : 1; + repair : 1;u8 repair_queue; u8 do_early_retrans:1,/* Enable RFC5827 early-retransmit */ syn_data:1, /* SYN includes data */
include/net/tcp.h +0 -4
@@ -272,7 +272,6 @@ extern int sysctl_tcp_app_win;extern int sysctl_tcp_adv_win_scale;extern int sysctl_tcp_tw_reuse;extern int sysctl_tcp_frto; -extern int sysctl_tcp_frto_response;extern int sysctl_tcp_low_latency;extern int sysctl_tcp_dma_copybreak;extern int sysctl_tcp_nometrics_save;
@@ -424,8 +423,6 @@ extern struct sock * tcp_check_req(struct sock *sk,struct sk_buff *skb, bool fastopen);extern int tcp_child_process (struct sock *parent,struct sock *child,struct sk_buff *skb); -extern bool tcp_use_frto (struct sock *sk); -extern void tcp_enter_frto (struct sock *sk);extern void tcp_enter_loss (struct sock *sk,int how);extern void tcp_clear_retrans (struct tcp_sock *tp);extern void tcp_update_metrics (struct sock *sk);
@@ -756,7 +753,6 @@ enum tcp_ca_event {CA_EVENT_TX_START ,/* first transmit when no packets in flight */ CA_EVENT_CWND_RESTART ,/* congestion window restart */ CA_EVENT_COMPLETE_CWR ,/* end of congestion recovery */ -CA_EVENT_FRTO ,/* fast recovery timeout */ CA_EVENT_LOSS ,/* loss timeout */ CA_EVENT_FAST_ACK ,/* in sequence ack */ CA_EVENT_SLOW_ACK, /* other ack */
net/ipv4/sysctl_net_ipv4.c +0 -7
@@ -592,13 +592,6 @@ static struct ctl_table ipv4_table[] = { .proc_handler = proc_dointvec }, { - .procname = "tcp_frto_response", - .data = &sysctl_tcp_frto_response, - .maxlen = sizeof(int), - .mode = 0644, - .proc_handler = proc_dointvec - }, - { .procname = "tcp_low_latency", .data = &sysctl_tcp_low_latency, .maxlen = sizeof(int),
net/ipv4/tcp_input.c +4 -371
474 lines not on this page · raw message
net/ipv4/tcp_minisocks.c +0 -3
@@ -422,9 +422,6 @@ struct sock *tcp_create_openreq_child(struct sock *sk, struct request_sock *req, newtp->snd_cwnd =TCP_INIT_CWND ; newtp->snd_cwnd_cnt =0 ; - newtp->frto_counter =0 ; - newtp->frto_highmark =0 ; -if (newicsk->icsk_ca_ops != &tcp_init_congestion_ops && !try_module_get (newicsk->icsk_ca_ops->owner)) newicsk->icsk_ca_ops = &tcp_init_congestion_ops;
net/ipv4/tcp_output.c +2 -9
@@ -78,10 +78,6 @@ static void tcp_event_new_data_sent(struct sock *sk, const struct sk_buff *skb)tcp_advance_send_head (sk, skb); tp->snd_nxt =TCP_SKB_CB (skb)->end_seq; -/* Don't override Nagle indefinitely with F-RTO */ -if (tp->frto_counter ==2 ) - tp->frto_counter =3 ; - tp->packets_out +=tcp_skb_pcount (skb);if (!prior_packets || icsk->icsk_pending ==ICSK_TIME_EARLY_RETRANS || icsk->icsk_pending ==ICSK_TIME_LOSS_PROBE )
@@ -1470,11 +1466,8 @@ static inline bool tcp_nagle_test(const struct tcp_sock *tp, const struct sk_bufif (nonagle &TCP_NAGLE_PUSH )return true; -/* Don't use the nagle rule for urgent data (or for the final FIN). -* Nagle can be ignored during F-RTO too (see RFC4138). -*/ -if (tcp_urg_mode (tp) || (tp->frto_counter ==2 ) || - (TCP_SKB_CB (skb)->tcp_flags &TCPHDR_FIN )) +/* Don't use the nagle rule for urgent data (or for the final FIN). */ +if (tcp_urg_mode (tp) || (TCP_SKB_CB (skb)->tcp_flags &TCPHDR_FIN ))return true;if (!tcp_nagle_check (tp, skb, cur_mss, nonagle))
net/ipv4/tcp_timer.c +1 -5
@@ -416,11 +416,7 @@ void tcp_retransmit_timer(struct sock *sk)NET_INC_STATS_BH (sock_net (sk), mib_idx); } -if (tcp_use_frto (sk)) { -tcp_enter_frto (sk); - }else { -tcp_enter_loss (sk,0 ); - } +tcp_enter_loss (sk,0 );if (tcp_retransmit_skb (sk,tcp_write_queue_head (sk)) >0 ) {/* Retransmission failed because of local congestion,
net/ipv4/tcp_westwood.c +1 -1
@@ -236,7 +236,7 @@ static void tcp_westwood_event(struct sock *sk, enum tcp_ca_event event) tp->snd_cwnd = tp->snd_ssthresh =tcp_westwood_bw_rttmin (sk);break ; -case CA_EVENT_FRTO : +case CA_EVENT_LOSS : tp->snd_ssthresh =tcp_westwood_bw_rttmin (sk);/* Update RTT_min when next ack arrives */ w->reset_rtt_min =1 ;
Signature · 1 line
1.8.1.3
PATCH v2 2/3 tcp: refactor CA_Loss state processing
Consolidate all of TCP CA_Loss state processing in tcp_fastretrans_alert() into a new function called tcp_process_loss(). This is to prepare the new F-RTO implementation in the next patch.
--- net/ipv4/tcp_input.c | 42 ++++++++++++++++++++++++++---------------- 1 file changed, 26 insertions(+), 16 deletions(-)
net/ipv4/tcp_input.c +26 -16
@@ -2664,6 +2664,30 @@ static void tcp_enter_recovery(struct sock *sk, bool ece_ack)tcp_set_ca_state (sk, TCP_CA_Recovery); } +/* Process an ACK in CA_Loss state. Move to CA_Open if lost data are +* recovered or spurious. Otherwise retransmits more on partial ACKs. +*/ +static void tcp_process_loss (struct sock *sk,int flag) +{ +struct inet_connection_sock *icsk =inet_csk (sk); +struct tcp_sock *tp =tcp_sk (sk); + +if (!before (tp->snd_una, tp->high_seq)) { + icsk->icsk_retransmits =0 ; +tcp_try_undo_recovery (sk); +return ; + } + +if (flag &FLAG_DATA_ACKED ) + icsk->icsk_retransmits =0 ; +if (tcp_is_reno (tp) && flag &FLAG_SND_UNA_ADVANCED ) +tcp_reset_reno_sack (tp); +if (tcp_try_undo_loss (sk)) +return ; +tcp_moderate_cwnd (tp); +tcp_xmit_retransmit_queue (sk); +} +/* Process an event, which can update packets-in-flight not trivially. * Main goal of this function is to calculate new estimate for left_out, * taking into account both packets sitting in receiver's buffer and
@@ -2710,12 +2734,6 @@ static void tcp_fastretrans_alert(struct sock *sk, int pkts_acked, tp->retrans_stamp =0 ; }else if (!before (tp->snd_una, tp->high_seq)) {switch (icsk->icsk_ca_state) { -case TCP_CA_Loss: - icsk->icsk_retransmits =0 ; -if (tcp_try_undo_recovery (sk)) -return ; -break ; -case TCP_CA_CWR :/* CWR is to be held something *above* high_seq * is ACKed for CWR bit to reach receiver. */
@@ -2746,18 +2764,10 @@ static void tcp_fastretrans_alert(struct sock *sk, int pkts_acked, newly_acked_sacked = pkts_acked + tp->sacked_out - prior_sacked;break ;case TCP_CA_Loss: -if (flag &FLAG_DATA_ACKED ) - icsk->icsk_retransmits =0 ; -if (tcp_is_reno (tp) && flag &FLAG_SND_UNA_ADVANCED ) -tcp_reset_reno_sack (tp); -if (!tcp_try_undo_loss (sk)) { -tcp_moderate_cwnd (tp); -tcp_xmit_retransmit_queue (sk); -return ; - } +tcp_process_loss (sk, flag);if (icsk->icsk_ca_state != TCP_CA_Open)return ; -/* Loss is undone; fall through to processing in Open state. */ +/* Fall through to processing in Open state. */ default :if (tcp_is_reno (tp)) {if (flag &FLAG_SND_UNA_ADVANCED )
Signature · 1 line
1.8.1.3
Re: [PATCH v2 2/3 net-next] tcp: refactor CA_Loss state processing
Quoted 9 lines · Yuchung Cheng
Consolidate all of TCP
CA_Lossstate processing intcp_fastretrans_alert()into a new function calledtcp_process_loss(). This is to prepare the new F-RTO implementation in the next patch.Signed-off-by Yuchung Cheng <[email protected]>Acked-by Neal Cardwell <[email protected]>--- net/ipv4/tcp_input.c | 42 ++++++++++++++++++++++++++---------------- 1 file changed, 26 insertions(+), 16 deletions(-)
PATCH v2 3/3 tcp: implement RFC5682 F-RTO
In reply to Yuchung ChengThis patch implements F-RTO (foward RTO recovery):
When the first retransmission after timeout is acknowledged, F-RTO sends new data instead of old data. If the next ACK acknowledges some never-retransmitted data, then the timeout was spurious and the congestion state is reverted. Otherwise if the next ACK selectively acknowledges the new data, then the timeout was genuine and the loss recovery continues. This idea applies to recurring timeouts as well. While F-RTO sends different data during timeout recovery, it does not (and should not) change the congestion control.
The implementaion follows the three steps of SACK enhanced algorithm (section 3) in RFC5682. Step 1 is in tcp_enter_loss(). Step 2 and 3 are in tcp_process_loss(). The basic version is not supported because SACK enhanced version also works for non-SACK connections.
The new implementation is functionally in parity with the old F-RTO implementation except the one case where it increases undo events:
In addition to the RFC algorithm, a spurious timeout may be detected without sending data in step 2, as long as the SACK confirms not all the original data are dropped. When this happens, the sender will undo the cwnd and perhaps enter fast recovery instead. This additional check increases the F-RTO undo events by 5x compared to the prior implementation on Google Web servers, since the sender often does not have new data to send for HTTP.
Note F-RTO may detect spurious timeout before Eifel with timestamps does so.
---
ChangeLog in v2:
- Removed extra while spaces
- Allow F-RTO in sack reneging case to detect spurious retransmit(s)
- Re-tested after merging with the recent TCP tail loss probe patch
Documentation/networking/ip-sysctl.txt | 18 +++------ include/linux/tcp.h | 3 +- net/ipv4/tcp_input.c | 73 ++++++++++++++++++++++++++++------ 3 files changed, 68 insertions(+), 26 deletions(-)
Documentation/networking/ip-sysctl.txt +6 -12
@@ -225,19 +225,13 @@ tcp_fin_timeout - INTEGER Default: 60 seconds tcp_frto - INTEGER - Enables Forward RTO-Recovery (F-RTO) defined in RFC4138. + Enables Forward RTO-Recovery (F-RTO) defined in RFC5682. F-RTO is an enhanced recovery algorithm for TCP retransmission - timeouts. It is particularly beneficial in wireless environments - where packet loss is typically due to random radio interference - rather than intermediate router congestion. F-RTO is sender-side - only modification. Therefore it does not require any support from - the peer. - - If set to 1, basic version is enabled. 2 enables SACK enhanced - F-RTO if flow uses SACK. The basic version can be used also when - SACK is in use though scenario(s) with it exists where F-RTO - interacts badly with the packet counting of the SACK enabled TCP - flow. + timeouts. It is particularly beneficial in networks where the + RTT fluctuates (e.g., wireless). F-RTO is sender-side only + modification. It does not require any support from the peer. + + By default it's enabled with a non-zero value. 0 disables F-RTO. tcp_keepalive_time - INTEGER How often TCP sends out keepalive messages when keepalive is enabled.
include/linux/tcp.h +2 -1
@@ -192,7 +192,8 @@ struct tcp_sock { u8 nonagle : 4,/* Disable Nagle algorithm? */ thin_lto : 1,/* Use linear timeouts for thin streams */ thin_dupack : 1,/* Fast retransmit on first dupack */ - repair : 1; + repair : 1, + frto : 1;/* F-RTO (RFC5682) activated in CA_Loss */u8 repair_queue; u8 do_early_retrans:1,/* Enable RFC5827 early-retransmit */ syn_data:1, /* SYN includes data */
net/ipv4/tcp_input.c +60 -13
146 lines not on this page · raw message
Signature · 1 line
1.8.1.3
Re: [PATCH v2 3/3 net-next] tcp: implement RFC5682 F-RTO
Quoted 36 lines · Yuchung Cheng
This patch implements F-RTO (foward RTO recovery):
When the first retransmission after timeout is acknowledged, F-RTO sends new data instead of old data. If the next ACK acknowledges some never-retransmitted data, then the timeout was spurious and the congestion state is reverted. Otherwise if the next ACK selectively acknowledges the new data, then the timeout was genuine and the loss recovery continues. This idea applies to recurring timeouts as well. While F-RTO sends different data during timeout recovery, it does not (and should not) change the congestion control.
The implementaion follows the three steps of SACK enhanced algorithm (section 3) in RFC5682. Step 1 is in
tcp_enter_loss(). Step 2 and 3 are intcp_process_loss(). The basic version is not supported because SACK enhanced version also works for non-SACK connections.The new implementation is functionally in parity with the old F-RTO implementation except the one case where it increases undo events:
In addition to the RFC algorithm, a spurious timeout may be detected without sending data in step 2, as long as the SACK confirms not all the original data are dropped. When this happens, the sender will undo the cwnd and perhaps enter fast recovery instead. This additional check increases the F-RTO undo events by 5x compared to the prior implementation on Google Web servers, since the sender often does not have new data to send for HTTP.Note F-RTO may detect spurious timeout before Eifel with timestamps does so.
Signed-off-by Yuchung Cheng <[email protected]>---
ChangeLog in v2:
- Removed extra while spaces
- Allow F-RTO in sack reneging case to detect spurious retransmit(s)
- Re-tested after merging with the recent TCP tail loss probe patch
Quoted 4 lines
Documentation/networking/ip-sysctl.txt | 18 +++------ include/linux/tcp.h | 3 +- net/ipv4/tcp_input.c | 73 ++++++++++++++++++++++++++++------ 3 files changed, 68 insertions(+), 26 deletions(-)
Re: [PATCH v2 3/3 net-next] tcp: implement RFC5682 F-RTO
In reply to Yuchung ChengQuoted 36 lines · Yuchung Cheng
This patch implements F-RTO (foward RTO recovery):
When the first retransmission after timeout is acknowledged, F-RTO sends new data instead of old data. If the next ACK acknowledges some never-retransmitted data, then the timeout was spurious and the congestion state is reverted. Otherwise if the next ACK selectively acknowledges the new data, then the timeout was genuine and the loss recovery continues. This idea applies to recurring timeouts as well. While F-RTO sends different data during timeout recovery, it does not (and should not) change the congestion control.
The implementaion follows the three steps of SACK enhanced algorithm (section 3) in RFC5682. Step 1 is in
tcp_enter_loss(). Step 2 and 3 are intcp_process_loss(). The basic version is not supported because SACK enhanced version also works for non-SACK connections.The new implementation is functionally in parity with the old F-RTO implementation except the one case where it increases undo events:
In addition to the RFC algorithm, a spurious timeout may be detected without sending data in step 2, as long as the SACK confirms not all the original data are dropped. When this happens, the sender will undo the cwnd and perhaps enter fast recovery instead. This additional check increases the F-RTO undo events by 5x compared to the prior implementation on Google Web servers, since the sender often does not have new data to send for HTTP.Note F-RTO may detect spurious timeout before Eifel with timestamps does so.
Signed-off-by Yuchung Cheng <[email protected]>---
ChangeLog in v2:
- Removed extra while spaces
- Allow F-RTO in sack reneging case to detect spurious retransmit(s)
- Re-tested after merging with the recent TCP tail loss probe patch
Quoted 4 lines
Documentation/networking/ip-sysctl.txt | 18 +++------ include/linux/tcp.h | 3 +- net/ipv4/tcp_input.c | 73 ++++++++++++++++++++++++++++------ 3 files changed, 68 insertions(+), 26 deletions(-)
Quoted 21 lines · Yuchung Cheng
The patch series refactor the F-RTO feature (RFC4138/5682).
This is to simplify the loss recovery processing. Existing F-RTO was developed during the experimental stage (RFC4138) and has many experimental features. It takes a separate code path from the traditional timeout processing by overloading
CA_Disorderinstead of usingCA_Lossstate. This complicatesCA_Disorderstate handling because it's also used for handling dubious ACKs and undos. While the algorithm in the RFC does not change the congestion control, the implementation intercepts congestion control in various places (e.g.,frto_cwndintcp_ack()).The new code implements newer F-RTO RFC5682 using
CA_Lossprocessing path. F-RTO becomes a small extension in the timeout processing and interfaces with congestion control and Eifel undo modules. It lets congestion control (module) determines how many to send independently. F-RTO only chooses what to send in order to detect spurious retranmission. If timeout is found spurious it invokes existing Eifel undo algorithms like DSACK or TCP timestamp based detection.
Quoted 7 lines
The first patch removes all F-RTO code except the
sysctl_tcp_frtois left for the new implementation. SinceCA_EVENT_FRTOis removed, TCP westwood now computes ssthresh on regular timeoutCA_EVENT_LOSSevent.Signed-off-by Yuchung Cheng <[email protected]>Acked-by Neal Cardwell <[email protected]>---
David Miller
maintainerI've given Ilpo more than enough time to give some kind of even minimal feedback, and he has been silent instead.
So I'm going to apply this series to net-next, thanks a lot for doing this work!