Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 1 | /* |
| 2 | * TCP Veno congestion control |
| 3 | * |
| 4 | * This is based on the congestion detection/avoidance scheme described in |
| 5 | * C. P. Fu, S. C. Liew. |
| 6 | * "TCP Veno: TCP Enhancement for Transmission over Wireless Access Networks." |
| 7 | * IEEE Journal on Selected Areas in Communication, |
| 8 | * Feb. 2003. |
Justin P. Mattock | 631dd1a | 2010-10-18 11:03:14 +0200 | [diff] [blame] | 9 | * See http://www.ie.cuhk.edu.hk/fileadmin/staff_upload/soung/Journal/J3.pdf |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 10 | */ |
| 11 | |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 12 | #include <linux/mm.h> |
| 13 | #include <linux/module.h> |
| 14 | #include <linux/skbuff.h> |
| 15 | #include <linux/inet_diag.h> |
| 16 | |
| 17 | #include <net/tcp.h> |
| 18 | |
| 19 | /* Default values of the Veno variables, in fixed-point representation |
| 20 | * with V_PARAM_SHIFT bits to the right of the binary point. |
| 21 | */ |
| 22 | #define V_PARAM_SHIFT 1 |
| 23 | static const int beta = 3 << V_PARAM_SHIFT; |
| 24 | |
| 25 | /* Veno variables */ |
| 26 | struct veno { |
| 27 | u8 doing_veno_now; /* if true, do veno for this rtt */ |
| 28 | u16 cntrtt; /* # of rtts measured within last rtt */ |
| 29 | u32 minrtt; /* min of rtts measured within last rtt (in usec) */ |
| 30 | u32 basertt; /* the min of all Veno rtt measurements seen (in usec) */ |
| 31 | u32 inc; /* decide whether to increase cwnd */ |
| 32 | u32 diff; /* calculate the diff rate */ |
| 33 | }; |
| 34 | |
| 35 | /* There are several situations when we must "re-start" Veno: |
| 36 | * |
| 37 | * o when a connection is established |
| 38 | * o after an RTO |
| 39 | * o after fast recovery |
| 40 | * o when we send a packet and there is no outstanding |
| 41 | * unacknowledged data (restarting an idle connection) |
| 42 | * |
| 43 | */ |
| 44 | static inline void veno_enable(struct sock *sk) |
| 45 | { |
| 46 | struct veno *veno = inet_csk_ca(sk); |
| 47 | |
| 48 | /* turn on Veno */ |
| 49 | veno->doing_veno_now = 1; |
| 50 | |
| 51 | veno->minrtt = 0x7fffffff; |
| 52 | } |
| 53 | |
| 54 | static inline void veno_disable(struct sock *sk) |
| 55 | { |
| 56 | struct veno *veno = inet_csk_ca(sk); |
| 57 | |
| 58 | /* turn off Veno */ |
| 59 | veno->doing_veno_now = 0; |
| 60 | } |
| 61 | |
| 62 | static void tcp_veno_init(struct sock *sk) |
| 63 | { |
| 64 | struct veno *veno = inet_csk_ca(sk); |
| 65 | |
| 66 | veno->basertt = 0x7fffffff; |
| 67 | veno->inc = 1; |
| 68 | veno_enable(sk); |
| 69 | } |
| 70 | |
| 71 | /* Do rtt sampling needed for Veno. */ |
Stephen Hemminger | 30cfd0b | 2007-07-25 23:49:34 -0700 | [diff] [blame] | 72 | static void tcp_veno_pkts_acked(struct sock *sk, u32 cnt, s32 rtt_us) |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 73 | { |
| 74 | struct veno *veno = inet_csk_ca(sk); |
Stephen Hemminger | 164891a | 2007-04-23 22:26:16 -0700 | [diff] [blame] | 75 | u32 vrtt; |
| 76 | |
Stephen Hemminger | 30cfd0b | 2007-07-25 23:49:34 -0700 | [diff] [blame] | 77 | if (rtt_us < 0) |
Ilpo Järvinen | b9ce204 | 2007-06-15 15:08:43 -0700 | [diff] [blame] | 78 | return; |
| 79 | |
Stephen Hemminger | 164891a | 2007-04-23 22:26:16 -0700 | [diff] [blame] | 80 | /* Never allow zero rtt or baseRTT */ |
Stephen Hemminger | 30cfd0b | 2007-07-25 23:49:34 -0700 | [diff] [blame] | 81 | vrtt = rtt_us + 1; |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 82 | |
| 83 | /* Filter to find propagation delay: */ |
| 84 | if (vrtt < veno->basertt) |
| 85 | veno->basertt = vrtt; |
| 86 | |
| 87 | /* Find the min rtt during the last rtt to find |
| 88 | * the current prop. delay + queuing delay: |
| 89 | */ |
| 90 | veno->minrtt = min(veno->minrtt, vrtt); |
| 91 | veno->cntrtt++; |
| 92 | } |
| 93 | |
| 94 | static void tcp_veno_state(struct sock *sk, u8 ca_state) |
| 95 | { |
| 96 | if (ca_state == TCP_CA_Open) |
| 97 | veno_enable(sk); |
| 98 | else |
| 99 | veno_disable(sk); |
| 100 | } |
| 101 | |
| 102 | /* |
| 103 | * If the connection is idle and we are restarting, |
| 104 | * then we don't want to do any Veno calculations |
| 105 | * until we get fresh rtt samples. So when we |
| 106 | * restart, we reset our Veno state to a clean |
| 107 | * state. After we get acks for this flight of |
| 108 | * packets, _then_ we can make Veno calculations |
| 109 | * again. |
| 110 | */ |
| 111 | static void tcp_veno_cwnd_event(struct sock *sk, enum tcp_ca_event event) |
| 112 | { |
| 113 | if (event == CA_EVENT_CWND_RESTART || event == CA_EVENT_TX_START) |
| 114 | tcp_veno_init(sk); |
| 115 | } |
| 116 | |
Eric Dumazet | 2490155 | 2014-05-02 21:18:05 -0700 | [diff] [blame] | 117 | static void tcp_veno_cong_avoid(struct sock *sk, u32 ack, u32 acked) |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 118 | { |
| 119 | struct tcp_sock *tp = tcp_sk(sk); |
| 120 | struct veno *veno = inet_csk_ca(sk); |
| 121 | |
Harvey Harrison | ab59859 | 2008-05-01 02:47:38 -0700 | [diff] [blame] | 122 | if (!veno->doing_veno_now) { |
Eric Dumazet | 2490155 | 2014-05-02 21:18:05 -0700 | [diff] [blame] | 123 | tcp_reno_cong_avoid(sk, ack, acked); |
Harvey Harrison | ab59859 | 2008-05-01 02:47:38 -0700 | [diff] [blame] | 124 | return; |
| 125 | } |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 126 | |
| 127 | /* limited by applications */ |
Eric Dumazet | 2490155 | 2014-05-02 21:18:05 -0700 | [diff] [blame] | 128 | if (!tcp_is_cwnd_limited(sk)) |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 129 | return; |
| 130 | |
| 131 | /* We do the Veno calculations only if we got enough rtt samples */ |
| 132 | if (veno->cntrtt <= 2) { |
| 133 | /* We don't have enough rtt samples to do the Veno |
| 134 | * calculation, so we'll behave like Reno. |
| 135 | */ |
Eric Dumazet | 2490155 | 2014-05-02 21:18:05 -0700 | [diff] [blame] | 136 | tcp_reno_cong_avoid(sk, ack, acked); |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 137 | } else { |
Lachlan Andrew | 1591311 | 2008-04-30 01:04:03 -0700 | [diff] [blame] | 138 | u64 target_cwnd; |
| 139 | u32 rtt; |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 140 | |
| 141 | /* We have enough rtt samples, so, using the Veno |
| 142 | * algorithm, we determine the state of the network. |
| 143 | */ |
| 144 | |
| 145 | rtt = veno->minrtt; |
| 146 | |
Christoph Paasch | 45a0769 | 2014-07-29 12:07:27 +0200 | [diff] [blame] | 147 | target_cwnd = (u64)tp->snd_cwnd * veno->basertt; |
Lachlan Andrew | 1591311 | 2008-04-30 01:04:03 -0700 | [diff] [blame] | 148 | target_cwnd <<= V_PARAM_SHIFT; |
| 149 | do_div(target_cwnd, rtt); |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 150 | |
| 151 | veno->diff = (tp->snd_cwnd << V_PARAM_SHIFT) - target_cwnd; |
| 152 | |
| 153 | if (tp->snd_cwnd <= tp->snd_ssthresh) { |
| 154 | /* Slow start. */ |
Yuchung Cheng | 9f9843a7 | 2013-10-31 11:07:31 -0700 | [diff] [blame] | 155 | tcp_slow_start(tp, acked); |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 156 | } else { |
| 157 | /* Congestion avoidance. */ |
| 158 | if (veno->diff < beta) { |
| 159 | /* In the "non-congestive state", increase cwnd |
| 160 | * every rtt. |
| 161 | */ |
Neal Cardwell | e73ebb08 | 2015-01-28 20:01:35 -0500 | [diff] [blame] | 162 | tcp_cong_avoid_ai(tp, tp->snd_cwnd, 1); |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 163 | } else { |
| 164 | /* In the "congestive state", increase cwnd |
| 165 | * every other rtt. |
| 166 | */ |
| 167 | if (tp->snd_cwnd_cnt >= tp->snd_cwnd) { |
Joe Perches | 9d4fb27 | 2009-11-23 10:41:23 -0800 | [diff] [blame] | 168 | if (veno->inc && |
| 169 | tp->snd_cwnd < tp->snd_cwnd_clamp) { |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 170 | tp->snd_cwnd++; |
| 171 | veno->inc = 0; |
| 172 | } else |
| 173 | veno->inc = 1; |
| 174 | tp->snd_cwnd_cnt = 0; |
| 175 | } else |
| 176 | tp->snd_cwnd_cnt++; |
| 177 | } |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 178 | } |
| 179 | if (tp->snd_cwnd < 2) |
| 180 | tp->snd_cwnd = 2; |
| 181 | else if (tp->snd_cwnd > tp->snd_cwnd_clamp) |
| 182 | tp->snd_cwnd = tp->snd_cwnd_clamp; |
| 183 | } |
| 184 | /* Wipe the slate clean for the next rtt. */ |
| 185 | /* veno->cntrtt = 0; */ |
| 186 | veno->minrtt = 0x7fffffff; |
| 187 | } |
| 188 | |
| 189 | /* Veno MD phase */ |
| 190 | static u32 tcp_veno_ssthresh(struct sock *sk) |
| 191 | { |
| 192 | const struct tcp_sock *tp = tcp_sk(sk); |
| 193 | struct veno *veno = inet_csk_ca(sk); |
| 194 | |
| 195 | if (veno->diff < beta) |
| 196 | /* in "non-congestive state", cut cwnd by 1/5 */ |
| 197 | return max(tp->snd_cwnd * 4 / 5, 2U); |
| 198 | else |
| 199 | /* in "congestive state", cut cwnd by 1/2 */ |
| 200 | return max(tp->snd_cwnd >> 1U, 2U); |
| 201 | } |
| 202 | |
Stephen Hemminger | a252beb | 2011-03-10 00:40:17 -0800 | [diff] [blame] | 203 | static struct tcp_congestion_ops tcp_veno __read_mostly = { |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 204 | .init = tcp_veno_init, |
| 205 | .ssthresh = tcp_veno_ssthresh, |
| 206 | .cong_avoid = tcp_veno_cong_avoid, |
Stephen Hemminger | 164891a | 2007-04-23 22:26:16 -0700 | [diff] [blame] | 207 | .pkts_acked = tcp_veno_pkts_acked, |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 208 | .set_state = tcp_veno_state, |
| 209 | .cwnd_event = tcp_veno_cwnd_event, |
| 210 | |
| 211 | .owner = THIS_MODULE, |
| 212 | .name = "veno", |
| 213 | }; |
| 214 | |
| 215 | static int __init tcp_veno_register(void) |
| 216 | { |
Alexey Dobriyan | 74975d4 | 2006-08-25 17:10:33 -0700 | [diff] [blame] | 217 | BUILD_BUG_ON(sizeof(struct veno) > ICSK_CA_PRIV_SIZE); |
Bin Zhou | 76f1017 | 2006-06-05 17:28:30 -0700 | [diff] [blame] | 218 | tcp_register_congestion_control(&tcp_veno); |
| 219 | return 0; |
| 220 | } |
| 221 | |
| 222 | static void __exit tcp_veno_unregister(void) |
| 223 | { |
| 224 | tcp_unregister_congestion_control(&tcp_veno); |
| 225 | } |
| 226 | |
| 227 | module_init(tcp_veno_register); |
| 228 | module_exit(tcp_veno_unregister); |
| 229 | |
| 230 | MODULE_AUTHOR("Bin Zhou, Cheng Peng Fu"); |
| 231 | MODULE_LICENSE("GPL"); |
| 232 | MODULE_DESCRIPTION("TCP Veno"); |