1 /* 2 * TCP NV: TCP with Congestion Avoidance 3 * 4 * TCP-NV is a successor of TCP-Vegas that has been developed to 5 * deal with the issues that occur in modern networks. 6 * Like TCP-Vegas, TCP-NV supports true congestion avoidance, 7 * the ability to detect congestion before packet losses occur. 8 * When congestion (queue buildup) starts to occur, TCP-NV 9 * predicts what the cwnd size should be for the current 10 * throughput and it reduces the cwnd proportionally to 11 * the difference between the current cwnd and the predicted cwnd. 12 * 13 * NV is only recommeneded for traffic within a data center, and when 14 * all the flows are NV (at least those within the data center). This 15 * is due to the inherent unfairness between flows using losses to 16 * detect congestion (congestion control) and those that use queue 17 * buildup to detect congestion (congestion avoidance). 18 * 19 * Note: High NIC coalescence values may lower the performance of NV 20 * due to the increased noise in RTT values. In particular, we have 21 * seen issues with rx-frames values greater than 8. 22 * 23 * TODO: 24 * 1) Add mechanism to deal with reverse congestion. 25 */ 26 27 #include <linux/mm.h> 28 #include <linux/module.h> 29 #include <linux/math64.h> 30 #include <net/tcp.h> 31 #include <linux/inet_diag.h> 32 33 /* TCP NV parameters 34 * 35 * nv_pad Max number of queued packets allowed in network 36 * nv_pad_buffer Do not grow cwnd if this closed to nv_pad 37 * nv_reset_period How often (in) seconds)to reset min_rtt 38 * nv_min_cwnd Don't decrease cwnd below this if there are no losses 39 * nv_cong_dec_mult Decrease cwnd by X% (30%) of congestion when detected 40 * nv_ssthresh_factor On congestion set ssthresh to this * <desired cwnd> / 8 41 * nv_rtt_factor RTT averaging factor 42 * nv_loss_dec_factor Decrease cwnd by this (50%) when losses occur 43 * nv_dec_eval_min_calls Wait this many RTT measurements before dec cwnd 44 * nv_inc_eval_min_calls Wait this many RTT measurements before inc cwnd 45 * nv_ssthresh_eval_min_calls Wait this many RTT measurements before stopping 46 * slow-start due to congestion 47 * nv_stop_rtt_cnt Only grow cwnd for this many RTTs after non-congestion 48 * nv_rtt_min_cnt Wait these many RTTs before making congesion decision 49 * nv_cwnd_growth_rate_neg 50 * nv_cwnd_growth_rate_pos 51 * How quickly to double growth rate (not rate) of cwnd when not 52 * congested. One value (nv_cwnd_growth_rate_neg) for when 53 * rate < 1 pkt/RTT (after losses). The other (nv_cwnd_growth_rate_pos) 54 * otherwise. 55 */ 56 57 static int nv_pad __read_mostly = 10; 58 static int nv_pad_buffer __read_mostly = 2; 59 static int nv_reset_period __read_mostly = 5; /* in seconds */ 60 static int nv_min_cwnd __read_mostly = 2; 61 static int nv_cong_dec_mult __read_mostly = 30 * 128 / 100; /* = 30% */ 62 static int nv_ssthresh_factor __read_mostly = 8; /* = 1 */ 63 static int nv_rtt_factor __read_mostly = 128; /* = 1/2*old + 1/2*new */ 64 static int nv_loss_dec_factor __read_mostly = 512; /* => 50% */ 65 static int nv_cwnd_growth_rate_neg __read_mostly = 8; 66 static int nv_cwnd_growth_rate_pos __read_mostly; /* 0 => fixed like Reno */ 67 static int nv_dec_eval_min_calls __read_mostly = 60; 68 static int nv_inc_eval_min_calls __read_mostly = 20; 69 static int nv_ssthresh_eval_min_calls __read_mostly = 30; 70 static int nv_stop_rtt_cnt __read_mostly = 10; 71 static int nv_rtt_min_cnt __read_mostly = 2; 72 73 module_param(nv_pad, int, 0644); 74 MODULE_PARM_DESC(nv_pad, "max queued packets allowed in network"); 75 module_param(nv_reset_period, int, 0644); 76 MODULE_PARM_DESC(nv_reset_period, "nv_min_rtt reset period (secs)"); 77 module_param(nv_min_cwnd, int, 0644); 78 MODULE_PARM_DESC(nv_min_cwnd, "NV will not decrease cwnd below this value" 79 " without losses"); 80 81 /* TCP NV Parameters */ 82 struct tcpnv { 83 unsigned long nv_min_rtt_reset_jiffies; /* when to switch to 84 * nv_min_rtt_new */ 85 s8 cwnd_growth_factor; /* Current cwnd growth factor, 86 * < 0 => less than 1 packet/RTT */ 87 u8 available8; 88 u16 available16; 89 u32 loss_cwnd; /* cwnd at last loss */ 90 u8 nv_allow_cwnd_growth:1, /* whether cwnd can grow */ 91 nv_reset:1, /* whether to reset values */ 92 nv_catchup:1; /* whether we are growing because 93 * of temporary cwnd decrease */ 94 u8 nv_eval_call_cnt; /* call count since last eval */ 95 u8 nv_min_cwnd; /* nv won't make a ca decision if cwnd is 96 * smaller than this. It may grow to handle 97 * TSO, LRO and interrupt coalescence because 98 * with these a small cwnd cannot saturate 99 * the link. Note that this is different from 100 * the file local nv_min_cwnd */ 101 u8 nv_rtt_cnt; /* RTTs without making ca decision */; 102 u32 nv_last_rtt; /* last rtt */ 103 u32 nv_min_rtt; /* active min rtt. Used to determine slope */ 104 u32 nv_min_rtt_new; /* min rtt for future use */ 105 u32 nv_rtt_max_rate; /* max rate seen during current RTT */ 106 u32 nv_rtt_start_seq; /* current RTT ends when packet arrives 107 * acking beyond nv_rtt_start_seq */ 108 u32 nv_last_snd_una; /* Previous value of tp->snd_una. It is 109 * used to determine bytes acked since last 110 * call to bictcp_acked */ 111 u32 nv_no_cong_cnt; /* Consecutive no congestion decisions */ 112 }; 113 114 #define NV_INIT_RTT U32_MAX 115 #define NV_MIN_CWND 4 116 #define NV_MIN_CWND_GROW 2 117 #define NV_TSO_CWND_BOUND 80 118 119 static inline void tcpnv_reset(struct tcpnv *ca, struct sock *sk) 120 { 121 struct tcp_sock *tp = tcp_sk(sk); 122 123 ca->nv_reset = 0; 124 ca->loss_cwnd = 0; 125 ca->nv_no_cong_cnt = 0; 126 ca->nv_rtt_cnt = 0; 127 ca->nv_last_rtt = 0; 128 ca->nv_rtt_max_rate = 0; 129 ca->nv_rtt_start_seq = tp->snd_una; 130 ca->nv_eval_call_cnt = 0; 131 ca->nv_last_snd_una = tp->snd_una; 132 } 133 134 static void tcpnv_init(struct sock *sk) 135 { 136 struct tcpnv *ca = inet_csk_ca(sk); 137 138 tcpnv_reset(ca, sk); 139 140 ca->nv_allow_cwnd_growth = 1; 141 ca->nv_min_rtt_reset_jiffies = jiffies + 2 * HZ; 142 ca->nv_min_rtt = NV_INIT_RTT; 143 ca->nv_min_rtt_new = NV_INIT_RTT; 144 ca->nv_min_cwnd = NV_MIN_CWND; 145 ca->nv_catchup = 0; 146 ca->cwnd_growth_factor = 0; 147 } 148 149 static void tcpnv_cong_avoid(struct sock *sk, u32 ack, u32 acked) 150 { 151 struct tcp_sock *tp = tcp_sk(sk); 152 struct tcpnv *ca = inet_csk_ca(sk); 153 u32 cnt; 154 155 if (!tcp_is_cwnd_limited(sk)) 156 return; 157 158 /* Only grow cwnd if NV has not detected congestion */ 159 if (!ca->nv_allow_cwnd_growth) 160 return; 161 162 if (tcp_in_slow_start(tp)) { 163 acked = tcp_slow_start(tp, acked); 164 if (!acked) 165 return; 166 } 167 168 if (ca->cwnd_growth_factor < 0) { 169 cnt = tp->snd_cwnd << -ca->cwnd_growth_factor; 170 tcp_cong_avoid_ai(tp, cnt, acked); 171 } else { 172 cnt = max(4U, tp->snd_cwnd >> ca->cwnd_growth_factor); 173 tcp_cong_avoid_ai(tp, cnt, acked); 174 } 175 } 176 177 static u32 tcpnv_recalc_ssthresh(struct sock *sk) 178 { 179 const struct tcp_sock *tp = tcp_sk(sk); 180 struct tcpnv *ca = inet_csk_ca(sk); 181 182 ca->loss_cwnd = tp->snd_cwnd; 183 return max((tp->snd_cwnd * nv_loss_dec_factor) >> 10, 2U); 184 } 185 186 static u32 tcpnv_undo_cwnd(struct sock *sk) 187 { 188 struct tcpnv *ca = inet_csk_ca(sk); 189 190 return max(tcp_sk(sk)->snd_cwnd, ca->loss_cwnd); 191 } 192 193 static void tcpnv_state(struct sock *sk, u8 new_state) 194 { 195 struct tcpnv *ca = inet_csk_ca(sk); 196 197 if (new_state == TCP_CA_Open && ca->nv_reset) { 198 tcpnv_reset(ca, sk); 199 } else if (new_state == TCP_CA_Loss || new_state == TCP_CA_CWR || 200 new_state == TCP_CA_Recovery) { 201 ca->nv_reset = 1; 202 ca->nv_allow_cwnd_growth = 0; 203 if (new_state == TCP_CA_Loss) { 204 /* Reset cwnd growth factor to Reno value */ 205 if (ca->cwnd_growth_factor > 0) 206 ca->cwnd_growth_factor = 0; 207 /* Decrease growth rate if allowed */ 208 if (nv_cwnd_growth_rate_neg > 0 && 209 ca->cwnd_growth_factor > -8) 210 ca->cwnd_growth_factor--; 211 } 212 } 213 } 214 215 /* Do congestion avoidance calculations for TCP-NV 216 */ 217 static void tcpnv_acked(struct sock *sk, const struct ack_sample *sample) 218 { 219 const struct inet_connection_sock *icsk = inet_csk(sk); 220 struct tcp_sock *tp = tcp_sk(sk); 221 struct tcpnv *ca = inet_csk_ca(sk); 222 unsigned long now = jiffies; 223 s64 rate64 = 0; 224 u32 rate, max_win, cwnd_by_slope; 225 u32 avg_rtt; 226 u32 bytes_acked = 0; 227 228 /* Some calls are for duplicates without timetamps */ 229 if (sample->rtt_us < 0) 230 return; 231 232 /* If not in TCP_CA_Open or TCP_CA_Disorder states, skip. */ 233 if (icsk->icsk_ca_state != TCP_CA_Open && 234 icsk->icsk_ca_state != TCP_CA_Disorder) 235 return; 236 237 /* Stop cwnd growth if we were in catch up mode */ 238 if (ca->nv_catchup && tp->snd_cwnd >= nv_min_cwnd) { 239 ca->nv_catchup = 0; 240 ca->nv_allow_cwnd_growth = 0; 241 } 242 243 bytes_acked = tp->snd_una - ca->nv_last_snd_una; 244 ca->nv_last_snd_una = tp->snd_una; 245 246 if (sample->in_flight == 0) 247 return; 248 249 /* Calculate moving average of RTT */ 250 if (nv_rtt_factor > 0) { 251 if (ca->nv_last_rtt > 0) { 252 avg_rtt = (((u64)sample->rtt_us) * nv_rtt_factor + 253 ((u64)ca->nv_last_rtt) 254 * (256 - nv_rtt_factor)) >> 8; 255 } else { 256 avg_rtt = sample->rtt_us; 257 ca->nv_min_rtt = avg_rtt << 1; 258 } 259 ca->nv_last_rtt = avg_rtt; 260 } else { 261 avg_rtt = sample->rtt_us; 262 } 263 264 /* rate in 100's bits per second */ 265 rate64 = ((u64)sample->in_flight) * 8000000; 266 rate = (u32)div64_u64(rate64, (u64)(avg_rtt * 100)); 267 268 /* Remember the maximum rate seen during this RTT 269 * Note: It may be more than one RTT. This function should be 270 * called at least nv_dec_eval_min_calls times. 271 */ 272 if (ca->nv_rtt_max_rate < rate) 273 ca->nv_rtt_max_rate = rate; 274 275 /* We have valid information, increment counter */ 276 if (ca->nv_eval_call_cnt < 255) 277 ca->nv_eval_call_cnt++; 278 279 /* update min rtt if necessary */ 280 if (avg_rtt < ca->nv_min_rtt) 281 ca->nv_min_rtt = avg_rtt; 282 283 /* update future min_rtt if necessary */ 284 if (avg_rtt < ca->nv_min_rtt_new) 285 ca->nv_min_rtt_new = avg_rtt; 286 287 /* nv_min_rtt is updated with the minimum (possibley averaged) rtt 288 * seen in the last sysctl_tcp_nv_reset_period seconds (i.e. a 289 * warm reset). This new nv_min_rtt will be continued to be updated 290 * and be used for another sysctl_tcp_nv_reset_period seconds, 291 * when it will be updated again. 292 * In practice we introduce some randomness, so the actual period used 293 * is chosen randomly from the range: 294 * [sysctl_tcp_nv_reset_period*3/4, sysctl_tcp_nv_reset_period*5/4) 295 */ 296 if (time_after_eq(now, ca->nv_min_rtt_reset_jiffies)) { 297 unsigned char rand; 298 299 ca->nv_min_rtt = ca->nv_min_rtt_new; 300 ca->nv_min_rtt_new = NV_INIT_RTT; 301 get_random_bytes(&rand, 1); 302 ca->nv_min_rtt_reset_jiffies = 303 now + ((nv_reset_period * (384 + rand) * HZ) >> 9); 304 /* Every so often we decrease ca->nv_min_cwnd in case previous 305 * value is no longer accurate. 306 */ 307 ca->nv_min_cwnd = max(ca->nv_min_cwnd / 2, NV_MIN_CWND); 308 } 309 310 /* Once per RTT check if we need to do congestion avoidance */ 311 if (before(ca->nv_rtt_start_seq, tp->snd_una)) { 312 ca->nv_rtt_start_seq = tp->snd_nxt; 313 if (ca->nv_rtt_cnt < 0xff) 314 /* Increase counter for RTTs without CA decision */ 315 ca->nv_rtt_cnt++; 316 317 /* If this function is only called once within an RTT 318 * the cwnd is probably too small (in some cases due to 319 * tso, lro or interrupt coalescence), so we increase 320 * ca->nv_min_cwnd. 321 */ 322 if (ca->nv_eval_call_cnt == 1 && 323 bytes_acked >= (ca->nv_min_cwnd - 1) * tp->mss_cache && 324 ca->nv_min_cwnd < (NV_TSO_CWND_BOUND + 1)) { 325 ca->nv_min_cwnd = min(ca->nv_min_cwnd 326 + NV_MIN_CWND_GROW, 327 NV_TSO_CWND_BOUND + 1); 328 ca->nv_rtt_start_seq = tp->snd_nxt + 329 ca->nv_min_cwnd * tp->mss_cache; 330 ca->nv_eval_call_cnt = 0; 331 ca->nv_allow_cwnd_growth = 1; 332 return; 333 } 334 335 /* Find the ideal cwnd for current rate from slope 336 * slope = 80000.0 * mss / nv_min_rtt 337 * cwnd_by_slope = nv_rtt_max_rate / slope 338 */ 339 cwnd_by_slope = (u32) 340 div64_u64(((u64)ca->nv_rtt_max_rate) * ca->nv_min_rtt, 341 (u64)(80000 * tp->mss_cache)); 342 max_win = cwnd_by_slope + nv_pad; 343 344 /* If cwnd > max_win, decrease cwnd 345 * if cwnd < max_win, grow cwnd 346 * else leave the same 347 */ 348 if (tp->snd_cwnd > max_win) { 349 /* there is congestion, check that it is ok 350 * to make a CA decision 351 * 1. We should have at least nv_dec_eval_min_calls 352 * data points before making a CA decision 353 * 2. We only make a congesion decision after 354 * nv_rtt_min_cnt RTTs 355 */ 356 if (ca->nv_rtt_cnt < nv_rtt_min_cnt) { 357 return; 358 } else if (tp->snd_ssthresh == TCP_INFINITE_SSTHRESH) { 359 if (ca->nv_eval_call_cnt < 360 nv_ssthresh_eval_min_calls) 361 return; 362 /* otherwise we will decrease cwnd */ 363 } else if (ca->nv_eval_call_cnt < 364 nv_dec_eval_min_calls) { 365 if (ca->nv_allow_cwnd_growth && 366 ca->nv_rtt_cnt > nv_stop_rtt_cnt) 367 ca->nv_allow_cwnd_growth = 0; 368 return; 369 } 370 371 /* We have enough data to determine we are congested */ 372 ca->nv_allow_cwnd_growth = 0; 373 tp->snd_ssthresh = 374 (nv_ssthresh_factor * max_win) >> 3; 375 if (tp->snd_cwnd - max_win > 2) { 376 /* gap > 2, we do exponential cwnd decrease */ 377 int dec; 378 379 dec = max(2U, ((tp->snd_cwnd - max_win) * 380 nv_cong_dec_mult) >> 7); 381 tp->snd_cwnd -= dec; 382 } else if (nv_cong_dec_mult > 0) { 383 tp->snd_cwnd = max_win; 384 } 385 if (ca->cwnd_growth_factor > 0) 386 ca->cwnd_growth_factor = 0; 387 ca->nv_no_cong_cnt = 0; 388 } else if (tp->snd_cwnd <= max_win - nv_pad_buffer) { 389 /* There is no congestion, grow cwnd if allowed*/ 390 if (ca->nv_eval_call_cnt < nv_inc_eval_min_calls) 391 return; 392 393 ca->nv_allow_cwnd_growth = 1; 394 ca->nv_no_cong_cnt++; 395 if (ca->cwnd_growth_factor < 0 && 396 nv_cwnd_growth_rate_neg > 0 && 397 ca->nv_no_cong_cnt > nv_cwnd_growth_rate_neg) { 398 ca->cwnd_growth_factor++; 399 ca->nv_no_cong_cnt = 0; 400 } else if (ca->cwnd_growth_factor >= 0 && 401 nv_cwnd_growth_rate_pos > 0 && 402 ca->nv_no_cong_cnt > 403 nv_cwnd_growth_rate_pos) { 404 ca->cwnd_growth_factor++; 405 ca->nv_no_cong_cnt = 0; 406 } 407 } else { 408 /* cwnd is in-between, so do nothing */ 409 return; 410 } 411 412 /* update state */ 413 ca->nv_eval_call_cnt = 0; 414 ca->nv_rtt_cnt = 0; 415 ca->nv_rtt_max_rate = 0; 416 417 /* Don't want to make cwnd < nv_min_cwnd 418 * (it wasn't before, if it is now is because nv 419 * decreased it). 420 */ 421 if (tp->snd_cwnd < nv_min_cwnd) 422 tp->snd_cwnd = nv_min_cwnd; 423 } 424 } 425 426 /* Extract info for Tcp socket info provided via netlink */ 427 size_t tcpnv_get_info(struct sock *sk, u32 ext, int *attr, 428 union tcp_cc_info *info) 429 { 430 const struct tcpnv *ca = inet_csk_ca(sk); 431 432 if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) { 433 info->vegas.tcpv_enabled = 1; 434 info->vegas.tcpv_rttcnt = ca->nv_rtt_cnt; 435 info->vegas.tcpv_rtt = ca->nv_last_rtt; 436 info->vegas.tcpv_minrtt = ca->nv_min_rtt; 437 438 *attr = INET_DIAG_VEGASINFO; 439 return sizeof(struct tcpvegas_info); 440 } 441 return 0; 442 } 443 EXPORT_SYMBOL_GPL(tcpnv_get_info); 444 445 static struct tcp_congestion_ops tcpnv __read_mostly = { 446 .init = tcpnv_init, 447 .ssthresh = tcpnv_recalc_ssthresh, 448 .cong_avoid = tcpnv_cong_avoid, 449 .set_state = tcpnv_state, 450 .undo_cwnd = tcpnv_undo_cwnd, 451 .pkts_acked = tcpnv_acked, 452 .get_info = tcpnv_get_info, 453 454 .owner = THIS_MODULE, 455 .name = "nv", 456 }; 457 458 static int __init tcpnv_register(void) 459 { 460 BUILD_BUG_ON(sizeof(struct tcpnv) > ICSK_CA_PRIV_SIZE); 461 462 return tcp_register_congestion_control(&tcpnv); 463 } 464 465 static void __exit tcpnv_unregister(void) 466 { 467 tcp_unregister_congestion_control(&tcpnv); 468 } 469 470 module_init(tcpnv_register); 471 module_exit(tcpnv_unregister); 472 473 MODULE_AUTHOR("Lawrence Brakmo"); 474 MODULE_LICENSE("GPL"); 475 MODULE_DESCRIPTION("TCP NV"); 476 MODULE_VERSION("1.0"); 477