1 /*- 2 * Copyright (c) 2009-2010 3 * Swinburne University of Technology, Melbourne, Australia 4 * Copyright (c) 2010-2011 The FreeBSD Foundation 5 * All rights reserved. 6 * 7 * This software was developed at the Centre for Advanced Internet 8 * Architectures, Swinburne University of Technology, by David Hayes and 9 * Lawrence Stewart, made possible in part by a grant from the Cisco University 10 * Research Program Fund at Community Foundation Silicon Valley. 11 * 12 * Portions of this software were developed at the Centre for Advanced Internet 13 * Architectures, Swinburne University of Technology, Melbourne, Australia by 14 * David Hayes under sponsorship from the FreeBSD Foundation. 15 * 16 * Redistribution and use in source and binary forms, with or without 17 * modification, are permitted provided that the following conditions 18 * are met: 19 * 1. Redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer. 21 * 2. Redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 */ 37 38 /* 39 * An implementation of the CAIA-Hamilton delay based congestion control 40 * algorithm, based on "Improved coexistence and loss tolerance for delay based 41 * TCP congestion control" by D. A. Hayes and G. Armitage., in 35th Annual IEEE 42 * Conference on Local Computer Networks (LCN 2010), Denver, Colorado, USA, 43 * 11-14 October 2010. 44 * 45 * Originally released as part of the NewTCP research project at Swinburne 46 * University of Technology's Centre for Advanced Internet Architectures, 47 * Melbourne, Australia, which was made possible in part by a grant from the 48 * Cisco University Research Program Fund at Community Foundation Silicon 49 * Valley. More details are available at: 50 * http://caia.swin.edu.au/urp/newtcp/ 51 */ 52 53 #include <sys/cdefs.h> 54 __FBSDID("$FreeBSD$"); 55 56 #include <sys/param.h> 57 #include <sys/kernel.h> 58 #include <sys/khelp.h> 59 #include <sys/limits.h> 60 #include <sys/malloc.h> 61 #include <sys/module.h> 62 #include <sys/queue.h> 63 #include <sys/socket.h> 64 #include <sys/socketvar.h> 65 #include <sys/sysctl.h> 66 #include <sys/systm.h> 67 68 #include <net/vnet.h> 69 70 #include <netinet/tcp.h> 71 #include <netinet/tcp_seq.h> 72 #include <netinet/tcp_timer.h> 73 #include <netinet/tcp_var.h> 74 #include <netinet/cc/cc.h> 75 #include <netinet/cc/cc_module.h> 76 77 #include <netinet/khelp/h_ertt.h> 78 79 #define CAST_PTR_INT(X) (*((int*)(X))) 80 81 /* 82 * Private signal type for rate based congestion signal. 83 * See <netinet/cc.h> for appropriate bit-range to use for private signals. 84 */ 85 #define CC_CHD_DELAY 0x02000000 86 87 /* Largest possible number returned by random(). */ 88 #define RANDOM_MAX INT_MAX 89 90 static void chd_ack_received(struct cc_var *ccv, uint16_t ack_type); 91 static void chd_cb_destroy(struct cc_var *ccv); 92 static int chd_cb_init(struct cc_var *ccv); 93 static void chd_cong_signal(struct cc_var *ccv, uint32_t signal_type); 94 static void chd_conn_init(struct cc_var *ccv); 95 static int chd_mod_init(void); 96 97 struct chd { 98 /* 99 * Shadow window - keeps track of what the NewReno congestion window 100 * would have been if delay-based cwnd backoffs had not been made. This 101 * functionality aids coexistence with loss-based TCP flows which may be 102 * sharing links along the path. 103 */ 104 unsigned long shadow_w; 105 /* 106 * Loss-based TCP compatibility flag - When set, it turns on the shadow 107 * window functionality. 108 */ 109 int loss_compete; 110 /* The maximum round trip time seen within a measured rtt period. */ 111 int maxrtt_in_rtt; 112 /* The previous qdly that caused cwnd to backoff. */ 113 int prev_backoff_qdly; 114 }; 115 116 static int ertt_id; 117 118 static VNET_DEFINE(uint32_t, chd_qmin) = 5; 119 static VNET_DEFINE(uint32_t, chd_pmax) = 50; 120 static VNET_DEFINE(uint32_t, chd_loss_fair) = 1; 121 static VNET_DEFINE(uint32_t, chd_use_max) = 1; 122 static VNET_DEFINE(uint32_t, chd_qthresh) = 20; 123 #define V_chd_qthresh VNET(chd_qthresh) 124 #define V_chd_qmin VNET(chd_qmin) 125 #define V_chd_pmax VNET(chd_pmax) 126 #define V_chd_loss_fair VNET(chd_loss_fair) 127 #define V_chd_use_max VNET(chd_use_max) 128 129 static MALLOC_DEFINE(M_CHD, "chd data", 130 "Per connection data required for the CHD congestion control algorithm"); 131 132 struct cc_algo chd_cc_algo = { 133 .name = "chd", 134 .ack_received = chd_ack_received, 135 .cb_destroy = chd_cb_destroy, 136 .cb_init = chd_cb_init, 137 .cong_signal = chd_cong_signal, 138 .conn_init = chd_conn_init, 139 .mod_init = chd_mod_init 140 }; 141 142 static __inline void 143 chd_window_decrease(struct cc_var *ccv) 144 { 145 unsigned long win; 146 147 win = min(CCV(ccv, snd_wnd), CCV(ccv, snd_cwnd)) / CCV(ccv, t_maxseg); 148 win -= max((win / 2), 1); 149 CCV(ccv, snd_ssthresh) = max(win, 2) * CCV(ccv, t_maxseg); 150 } 151 152 /* 153 * Probabilistic backoff function. Returns 1 if we should backoff or 0 154 * otherwise. The calculation of p is similar to the calculation of p in cc_hd. 155 */ 156 static __inline int 157 should_backoff(int qdly, int maxqdly, struct chd *chd_data) 158 { 159 unsigned long p, rand; 160 161 rand = random(); 162 163 if (qdly < V_chd_qthresh) { 164 chd_data->loss_compete = 0; 165 p = (((RANDOM_MAX / 100) * V_chd_pmax) / 166 (V_chd_qthresh - V_chd_qmin)) * 167 (qdly - V_chd_qmin); 168 } else { 169 if (qdly > V_chd_qthresh) { 170 p = (((RANDOM_MAX / 100) * V_chd_pmax) / 171 (maxqdly - V_chd_qthresh)) * 172 (maxqdly - qdly); 173 if (V_chd_loss_fair && rand < p) 174 chd_data->loss_compete = 1; 175 } else { 176 p = (RANDOM_MAX / 100) * V_chd_pmax; 177 chd_data->loss_compete = 0; 178 } 179 } 180 181 return (rand < p); 182 } 183 184 static __inline void 185 chd_window_increase(struct cc_var *ccv, int new_measurement) 186 { 187 struct chd *chd_data; 188 int incr; 189 190 chd_data = ccv->cc_data; 191 incr = 0; 192 193 if (CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh)) { 194 /* Adapted from NewReno slow start. */ 195 if (V_tcp_do_rfc3465) { 196 /* In slow-start with ABC enabled. */ 197 if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max)) { 198 /* Not due to RTO. */ 199 incr = min(ccv->bytes_this_ack, 200 V_tcp_abc_l_var * CCV(ccv, t_maxseg)); 201 } else { 202 /* Due to RTO. */ 203 incr = min(ccv->bytes_this_ack, 204 CCV(ccv, t_maxseg)); 205 } 206 } else 207 incr = CCV(ccv, t_maxseg); 208 209 } else { /* Congestion avoidance. */ 210 if (V_tcp_do_rfc3465) { 211 if (ccv->flags & CCF_ABC_SENTAWND) { 212 ccv->flags &= ~CCF_ABC_SENTAWND; 213 incr = CCV(ccv, t_maxseg); 214 } 215 } else if (new_measurement) 216 incr = CCV(ccv, t_maxseg); 217 } 218 219 if (chd_data->shadow_w > 0) { 220 /* Track NewReno window. */ 221 chd_data->shadow_w = min(chd_data->shadow_w + incr, 222 TCP_MAXWIN << CCV(ccv, snd_scale)); 223 } 224 225 CCV(ccv,snd_cwnd) = min(CCV(ccv, snd_cwnd) + incr, 226 TCP_MAXWIN << CCV(ccv, snd_scale)); 227 } 228 229 /* 230 * All ACK signals are used for timing measurements to determine delay-based 231 * congestion. However, window increases are only performed when 232 * ack_type == CC_ACK. 233 */ 234 static void 235 chd_ack_received(struct cc_var *ccv, uint16_t ack_type) 236 { 237 struct chd *chd_data; 238 struct ertt *e_t; 239 int backoff, new_measurement, qdly, rtt; 240 241 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id); 242 chd_data = ccv->cc_data; 243 new_measurement = e_t->flags & ERTT_NEW_MEASUREMENT; 244 backoff = qdly = 0; 245 246 chd_data->maxrtt_in_rtt = imax(e_t->rtt, chd_data->maxrtt_in_rtt); 247 248 if (new_measurement) { 249 /* 250 * There is a new per RTT measurement, so check to see if there 251 * is delay based congestion. 252 */ 253 rtt = V_chd_use_max ? chd_data->maxrtt_in_rtt : e_t->rtt; 254 chd_data->maxrtt_in_rtt = 0; 255 256 if (rtt && e_t->minrtt && !IN_RECOVERY(CCV(ccv, t_flags))) { 257 qdly = rtt - e_t->minrtt; 258 if (qdly > V_chd_qmin) { 259 /* 260 * Probabilistic delay based congestion 261 * indication. 262 */ 263 backoff = should_backoff(qdly, 264 e_t->maxrtt - e_t->minrtt, chd_data); 265 } else 266 chd_data->loss_compete = 0; 267 } 268 /* Reset per RTT measurement flag to start a new measurement. */ 269 e_t->flags &= ~ERTT_NEW_MEASUREMENT; 270 } 271 272 if (backoff) { 273 /* 274 * Update shadow_w before delay based backoff. 275 */ 276 if (chd_data->loss_compete || 277 qdly > chd_data->prev_backoff_qdly) { 278 /* 279 * Delay is higher than when we backed off previously, 280 * so it is possible that this flow is competing with 281 * loss based flows. 282 */ 283 chd_data->shadow_w = max(CCV(ccv, snd_cwnd), 284 chd_data->shadow_w); 285 } else { 286 /* 287 * Reset shadow_w, as it is probable that this flow is 288 * not competing with loss based flows at the moment. 289 */ 290 chd_data->shadow_w = 0; 291 } 292 293 chd_data->prev_backoff_qdly = qdly; 294 /* 295 * Send delay-based congestion signal to the congestion signal 296 * handler. 297 */ 298 chd_cong_signal(ccv, CC_CHD_DELAY); 299 300 } else if (ack_type == CC_ACK) 301 chd_window_increase(ccv, new_measurement); 302 } 303 304 static void 305 chd_cb_destroy(struct cc_var *ccv) 306 { 307 308 if (ccv->cc_data != NULL) 309 free(ccv->cc_data, M_CHD); 310 } 311 312 static int 313 chd_cb_init(struct cc_var *ccv) 314 { 315 struct chd *chd_data; 316 317 chd_data = malloc(sizeof(struct chd), M_CHD, M_NOWAIT); 318 if (chd_data == NULL) 319 return (ENOMEM); 320 321 chd_data->shadow_w = 0; 322 ccv->cc_data = chd_data; 323 324 return (0); 325 } 326 327 static void 328 chd_cong_signal(struct cc_var *ccv, uint32_t signal_type) 329 { 330 struct ertt *e_t; 331 struct chd *chd_data; 332 int qdly; 333 u_int mss; 334 335 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id); 336 chd_data = ccv->cc_data; 337 qdly = imax(e_t->rtt, chd_data->maxrtt_in_rtt) - e_t->minrtt; 338 mss = CCV(ccv, t_maxseg); 339 340 switch(signal_type) { 341 case CC_CHD_DELAY: 342 chd_window_decrease(ccv); /* Set new ssthresh. */ 343 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); 344 CCV(ccv, snd_recover) = CCV(ccv, snd_max); 345 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 346 break; 347 348 case CC_NDUPACK: /* Packet loss. */ 349 /* 350 * Only react to loss as a congestion signal if qdly > 351 * V_chd_qthresh. If qdly is less than qthresh, presume that 352 * this is a non congestion related loss. If qdly is greater 353 * than qthresh, assume that we are competing with loss based 354 * tcp flows and restore window from any unnecessary backoffs, 355 * before the decrease. 356 */ 357 if (!IN_RECOVERY(CCV(ccv, t_flags)) && qdly > V_chd_qthresh) { 358 if (chd_data->loss_compete) { 359 CCV(ccv, snd_cwnd) = max(CCV(ccv, snd_cwnd), 360 chd_data->shadow_w); 361 } 362 chd_window_decrease(ccv); 363 } else { 364 /* 365 * This loss isn't congestion related, or already 366 * recovering from congestion. 367 */ 368 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd); 369 CCV(ccv, snd_recover) = CCV(ccv, snd_max); 370 } 371 372 if (chd_data->shadow_w > 0) { 373 chd_data->shadow_w = max(chd_data->shadow_w / 374 CCV(ccv, t_maxseg) / 2, 2) * CCV(ccv, t_maxseg); 375 } 376 ENTER_FASTRECOVERY(CCV(ccv, t_flags)); 377 break; 378 case CC_RTO: 379 CCV(ccv, snd_ssthresh) = 380 max((CCV(ccv, snd_max) - CCV(ccv, snd_una)) / 2 / mss, 2) 381 * mss; 382 CCV(ccv, snd_cwnd) = mss; 383 break; 384 385 default: 386 newreno_cc_algo.cong_signal(ccv, signal_type); 387 } 388 } 389 390 static void 391 chd_conn_init(struct cc_var *ccv) 392 { 393 struct chd *chd_data; 394 395 chd_data = ccv->cc_data; 396 chd_data->prev_backoff_qdly = 0; 397 chd_data->maxrtt_in_rtt = 0; 398 chd_data->loss_compete = 0; 399 /* 400 * Initialise the shadow_cwnd to be equal to snd_cwnd in case we are 401 * competing with loss based flows from the start. 402 */ 403 chd_data->shadow_w = CCV(ccv, snd_cwnd); 404 } 405 406 static int 407 chd_mod_init(void) 408 { 409 410 ertt_id = khelp_get_id("ertt"); 411 if (ertt_id <= 0) { 412 printf("%s: h_ertt module not found\n", __func__); 413 return (ENOENT); 414 } 415 416 chd_cc_algo.after_idle = newreno_cc_algo.after_idle; 417 chd_cc_algo.post_recovery = newreno_cc_algo.post_recovery; 418 419 return (0); 420 } 421 422 static int 423 chd_loss_fair_handler(SYSCTL_HANDLER_ARGS) 424 { 425 int error; 426 uint32_t new; 427 428 new = V_chd_loss_fair; 429 error = sysctl_handle_int(oidp, &new, 0, req); 430 if (error == 0 && req->newptr != NULL) { 431 if (CAST_PTR_INT(req->newptr) > 1) 432 error = EINVAL; 433 else 434 V_chd_loss_fair = new; 435 } 436 437 return (error); 438 } 439 440 static int 441 chd_pmax_handler(SYSCTL_HANDLER_ARGS) 442 { 443 int error; 444 uint32_t new; 445 446 new = V_chd_pmax; 447 error = sysctl_handle_int(oidp, &new, 0, req); 448 if (error == 0 && req->newptr != NULL) { 449 if (CAST_PTR_INT(req->newptr) == 0 || 450 CAST_PTR_INT(req->newptr) > 100) 451 error = EINVAL; 452 else 453 V_chd_pmax = new; 454 } 455 456 return (error); 457 } 458 459 static int 460 chd_qthresh_handler(SYSCTL_HANDLER_ARGS) 461 { 462 int error; 463 uint32_t new; 464 465 new = V_chd_qthresh; 466 error = sysctl_handle_int(oidp, &new, 0, req); 467 if (error == 0 && req->newptr != NULL) { 468 if (CAST_PTR_INT(req->newptr) <= V_chd_qmin) 469 error = EINVAL; 470 else 471 V_chd_qthresh = new; 472 } 473 474 return (error); 475 } 476 477 SYSCTL_DECL(_net_inet_tcp_cc_chd); 478 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, chd, CTLFLAG_RW, NULL, 479 "CAIA Hamilton delay-based congestion control related settings"); 480 481 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, loss_fair, 482 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 483 &VNET_NAME(chd_loss_fair), 1, &chd_loss_fair_handler, 484 "IU", "Flag to enable shadow window functionality."); 485 486 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, pmax, 487 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 488 &VNET_NAME(chd_pmax), 5, &chd_pmax_handler, 489 "IU", "Per RTT maximum backoff probability as a percentage"); 490 491 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, queue_threshold, 492 CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 493 &VNET_NAME(chd_qthresh), 20, &chd_qthresh_handler, 494 "IU", "Queueing congestion threshold in ticks"); 495 496 SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, queue_min, 497 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_qmin), 5, 498 "Minimum queueing delay threshold in ticks"); 499 500 SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, use_max, 501 CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_use_max), 1, 502 "Use the maximum RTT seen within the measurement period (RTT) " 503 "as the basic delay measurement for the algorithm."); 504 505 DECLARE_CC_MODULE(chd, &chd_cc_algo); 506 MODULE_DEPEND(chd, ertt, 1, 1, 1); 507