1 /*- 2 * Copyright (c) 2008-2010 Lawrence Stewart <lstewart@freebsd.org> 3 * Copyright (c) 2010 The FreeBSD Foundation 4 * All rights reserved. 5 * 6 * This software was developed by Lawrence Stewart while studying at the Centre 7 * for Advanced Internet Architectures, Swinburne University, made possible in 8 * part by a grant from the Cisco University Research Program Fund at Community 9 * Foundation Silicon Valley. 10 * 11 * Portions of this software were developed at the Centre for Advanced 12 * Internet Architectures, Swinburne University of Technology, Melbourne, 13 * Australia by David Hayes under sponsorship from the FreeBSD Foundation. 14 * 15 * Redistribution and use in source and binary forms, with or without 16 * modification, are permitted provided that the following conditions 17 * are met: 18 * 1. Redistributions of source code must retain the above copyright 19 * notice, this list of conditions and the following disclaimer. 20 * 2. Redistributions in binary form must reproduce the above copyright 21 * notice, this list of conditions and the following disclaimer in the 22 * documentation and/or other materials provided with the distribution. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 /* 38 * An implementation of the CUBIC congestion control algorithm for FreeBSD, 39 * based on the Internet Draft "draft-rhee-tcpm-cubic-02" by Rhee, Xu and Ha. 40 * Originally released as part of the NewTCP research project at Swinburne 41 * University's Centre for Advanced Internet Architectures, Melbourne, 42 * Australia, which was made possible in part by a grant from the Cisco 43 * University Research Program Fund at Community Foundation Silicon Valley. More 44 * details are available at: 45 * http://caia.swin.edu.au/urp/newtcp/ 46 */ 47 48 #include <sys/cdefs.h> 49 __FBSDID("$FreeBSD$"); 50 51 #include <sys/param.h> 52 #include <sys/kernel.h> 53 #include <sys/malloc.h> 54 #include <sys/module.h> 55 #include <sys/socket.h> 56 #include <sys/socketvar.h> 57 #include <sys/sysctl.h> 58 #include <sys/systm.h> 59 60 #include <net/vnet.h> 61 62 #include <netinet/cc.h> 63 #include <netinet/tcp_seq.h> 64 #include <netinet/tcp_timer.h> 65 #include <netinet/tcp_var.h> 66 67 #include <netinet/cc/cc_cubic.h> 68 #include <netinet/cc/cc_module.h> 69 70 static void cubic_ack_received(struct cc_var *ccv, uint16_t type); 71 static void cubic_cb_destroy(struct cc_var *ccv); 72 static int cubic_cb_init(struct cc_var *ccv); 73 static void cubic_cong_signal(struct cc_var *ccv, uint32_t type); 74 static void cubic_conn_init(struct cc_var *ccv); 75 static int cubic_mod_init(void); 76 static void cubic_post_recovery(struct cc_var *ccv); 77 static void cubic_record_rtt(struct cc_var *ccv); 78 static void cubic_ssthresh_update(struct cc_var *ccv); 79 80 struct cubic { 81 /* Cubic K in fixed point form with CUBIC_SHIFT worth of precision. */ 82 int64_t K; 83 /* Sum of RTT samples across an epoch in ticks. */ 84 int64_t sum_rtt_ticks; 85 /* cwnd at the most recent congestion event. */ 86 unsigned long max_cwnd; 87 /* cwnd at the previous congestion event. */ 88 unsigned long prev_max_cwnd; 89 /* Number of congestion events. */ 90 uint32_t num_cong_events; 91 /* Minimum observed rtt in ticks. */ 92 int min_rtt_ticks; 93 /* Mean observed rtt between congestion epochs. */ 94 int mean_rtt_ticks; 95 /* ACKs since last congestion event. */ 96 int epoch_ack_count; 97 /* Time of last congestion event in ticks. */ 98 int t_last_cong; 99 }; 100 101 MALLOC_DECLARE(M_CUBIC); 102 MALLOC_DEFINE(M_CUBIC, "cubic data", 103 "Per connection data required for the CUBIC congestion control algorithm"); 104 105 struct cc_algo cubic_cc_algo = { 106 .name = "cubic", 107 .ack_received = cubic_ack_received, 108 .cb_destroy = cubic_cb_destroy, 109 .cb_init = cubic_cb_init, 110 .cong_signal = cubic_cong_signal, 111 .conn_init = cubic_conn_init, 112 .mod_init = cubic_mod_init, 113 .post_recovery = cubic_post_recovery, 114 }; 115 116 static void 117 cubic_ack_received(struct cc_var *ccv, uint16_t type) 118 { 119 struct cubic *cubic_data; 120 unsigned long w_tf, w_cubic_next; 121 int ticks_since_cong; 122 123 cubic_data = ccv->cc_data; 124 cubic_record_rtt(ccv); 125 126 /* 127 * Regular ACK and we're not in cong/fast recovery and we're cwnd 128 * limited and we're either not doing ABC or are slow starting or are 129 * doing ABC and we've sent a cwnd's worth of bytes. 130 */ 131 if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) && 132 (ccv->flags & CCF_CWND_LIMITED) && (!V_tcp_do_rfc3465 || 133 CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh) || 134 (V_tcp_do_rfc3465 && ccv->flags & CCF_ABC_SENTAWND))) { 135 /* Use the logic in NewReno ack_received() for slow start. */ 136 if (CCV(ccv, snd_cwnd) <= CCV(ccv, snd_ssthresh) || 137 cubic_data->min_rtt_ticks == TCPTV_SRTTBASE) 138 newreno_cc_algo.ack_received(ccv, type); 139 else { 140 ticks_since_cong = ticks - cubic_data->t_last_cong; 141 142 /* 143 * The mean RTT is used to best reflect the equations in 144 * the I-D. Using min_rtt in the tf_cwnd calculation 145 * causes w_tf to grow much faster than it should if the 146 * RTT is dominated by network buffering rather than 147 * propogation delay. 148 */ 149 w_tf = tf_cwnd(ticks_since_cong, 150 cubic_data->mean_rtt_ticks, cubic_data->max_cwnd, 151 CCV(ccv, t_maxseg)); 152 153 w_cubic_next = cubic_cwnd(ticks_since_cong + 154 cubic_data->mean_rtt_ticks, cubic_data->max_cwnd, 155 CCV(ccv, t_maxseg), cubic_data->K); 156 157 ccv->flags &= ~CCF_ABC_SENTAWND; 158 159 if (w_cubic_next < w_tf) 160 /* 161 * TCP-friendly region, follow tf 162 * cwnd growth. 163 */ 164 CCV(ccv, snd_cwnd) = w_tf; 165 166 else if (CCV(ccv, snd_cwnd) < w_cubic_next) { 167 /* 168 * Concave or convex region, follow CUBIC 169 * cwnd growth. 170 */ 171 if (V_tcp_do_rfc3465) 172 CCV(ccv, snd_cwnd) = w_cubic_next; 173 else 174 CCV(ccv, snd_cwnd) += ((w_cubic_next - 175 CCV(ccv, snd_cwnd)) * 176 CCV(ccv, t_maxseg)) / 177 CCV(ccv, snd_cwnd); 178 } 179 180 /* 181 * If we're not in slow start and we're probing for a 182 * new cwnd limit at the start of a connection 183 * (happens when hostcache has a relevant entry), 184 * keep updating our current estimate of the 185 * max_cwnd. 186 */ 187 if (cubic_data->num_cong_events == 0 && 188 cubic_data->max_cwnd < CCV(ccv, snd_cwnd)) 189 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 190 } 191 } 192 } 193 194 static void 195 cubic_cb_destroy(struct cc_var *ccv) 196 { 197 198 if (ccv->cc_data != NULL) 199 free(ccv->cc_data, M_CUBIC); 200 } 201 202 static int 203 cubic_cb_init(struct cc_var *ccv) 204 { 205 struct cubic *cubic_data; 206 207 cubic_data = malloc(sizeof(struct cubic), M_CUBIC, M_NOWAIT|M_ZERO); 208 209 if (cubic_data == NULL) 210 return (ENOMEM); 211 212 /* Init some key variables with sensible defaults. */ 213 cubic_data->t_last_cong = ticks; 214 cubic_data->min_rtt_ticks = TCPTV_SRTTBASE; 215 cubic_data->mean_rtt_ticks = 1; 216 217 ccv->cc_data = cubic_data; 218 219 return (0); 220 } 221 222 /* 223 * Perform any necessary tasks before we enter congestion recovery. 224 */ 225 static void 226 cubic_cong_signal(struct cc_var *ccv, uint32_t type) 227 { 228 struct cubic *cubic_data; 229 230 cubic_data = ccv->cc_data; 231 232 switch (type) { 233 case CC_NDUPACK: 234 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) { 235 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 236 cubic_ssthresh_update(ccv); 237 cubic_data->num_cong_events++; 238 cubic_data->prev_max_cwnd = cubic_data->max_cwnd; 239 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 240 } 241 ENTER_RECOVERY(CCV(ccv, t_flags)); 242 } 243 break; 244 245 case CC_ECN: 246 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) { 247 cubic_ssthresh_update(ccv); 248 cubic_data->num_cong_events++; 249 cubic_data->prev_max_cwnd = cubic_data->max_cwnd; 250 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 251 cubic_data->t_last_cong = ticks; 252 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh); 253 ENTER_CONGRECOVERY(CCV(ccv, t_flags)); 254 } 255 break; 256 257 case CC_RTO: 258 /* 259 * Grab the current time and record it so we know when the 260 * most recent congestion event was. Only record it when the 261 * timeout has fired more than once, as there is a reasonable 262 * chance the first one is a false alarm and may not indicate 263 * congestion. 264 */ 265 if (CCV(ccv, t_rxtshift) >= 2) 266 cubic_data->num_cong_events++; 267 cubic_data->t_last_cong = ticks; 268 break; 269 } 270 } 271 272 static void 273 cubic_conn_init(struct cc_var *ccv) 274 { 275 struct cubic *cubic_data; 276 277 cubic_data = ccv->cc_data; 278 279 /* 280 * Ensure we have a sane initial value for max_cwnd recorded. Without 281 * this here bad things happen when entries from the TCP hostcache 282 * get used. 283 */ 284 cubic_data->max_cwnd = CCV(ccv, snd_cwnd); 285 } 286 287 static int 288 cubic_mod_init(void) 289 { 290 291 cubic_cc_algo.after_idle = newreno_cc_algo.after_idle; 292 293 return (0); 294 } 295 296 /* 297 * Perform any necessary tasks before we exit congestion recovery. 298 */ 299 static void 300 cubic_post_recovery(struct cc_var *ccv) 301 { 302 struct cubic *cubic_data; 303 304 cubic_data = ccv->cc_data; 305 306 /* Fast convergence heuristic. */ 307 if (cubic_data->max_cwnd < cubic_data->prev_max_cwnd) 308 cubic_data->max_cwnd = (cubic_data->max_cwnd * CUBIC_FC_FACTOR) 309 >> CUBIC_SHIFT; 310 311 if (IN_FASTRECOVERY(CCV(ccv, t_flags))) { 312 /* 313 * If inflight data is less than ssthresh, set cwnd 314 * conservatively to avoid a burst of data, as suggested in 315 * the NewReno RFC. Otherwise, use the CUBIC method. 316 * 317 * XXXLAS: Find a way to do this without needing curack 318 */ 319 if (SEQ_GT(ccv->curack + CCV(ccv, snd_ssthresh), 320 CCV(ccv, snd_max))) 321 CCV(ccv, snd_cwnd) = CCV(ccv, snd_max) - ccv->curack + 322 CCV(ccv, t_maxseg); 323 else 324 /* Update cwnd based on beta and adjusted max_cwnd. */ 325 CCV(ccv, snd_cwnd) = max(1, ((CUBIC_BETA * 326 cubic_data->max_cwnd) >> CUBIC_SHIFT)); 327 } 328 cubic_data->t_last_cong = ticks; 329 330 /* Calculate the average RTT between congestion epochs. */ 331 if (cubic_data->epoch_ack_count > 0 && 332 cubic_data->sum_rtt_ticks >= cubic_data->epoch_ack_count) { 333 cubic_data->mean_rtt_ticks = (int)(cubic_data->sum_rtt_ticks / 334 cubic_data->epoch_ack_count); 335 } 336 337 cubic_data->epoch_ack_count = 0; 338 cubic_data->sum_rtt_ticks = 0; 339 cubic_data->K = cubic_k(cubic_data->max_cwnd / CCV(ccv, t_maxseg)); 340 } 341 342 /* 343 * Record the min RTT and sum samples for the epoch average RTT calculation. 344 */ 345 static void 346 cubic_record_rtt(struct cc_var *ccv) 347 { 348 struct cubic *cubic_data; 349 int t_srtt_ticks; 350 351 /* Ignore srtt until a min number of samples have been taken. */ 352 if (CCV(ccv, t_rttupdated) >= CUBIC_MIN_RTT_SAMPLES) { 353 cubic_data = ccv->cc_data; 354 t_srtt_ticks = CCV(ccv, t_srtt) / TCP_RTT_SCALE; 355 356 /* 357 * Record the current SRTT as our minrtt if it's the smallest 358 * we've seen or minrtt is currently equal to its initialised 359 * value. 360 * 361 * XXXLAS: Should there be some hysteresis for minrtt? 362 */ 363 if ((t_srtt_ticks < cubic_data->min_rtt_ticks || 364 cubic_data->min_rtt_ticks == TCPTV_SRTTBASE)) { 365 cubic_data->min_rtt_ticks = max(1, t_srtt_ticks); 366 367 /* 368 * If the connection is within its first congestion 369 * epoch, ensure we prime mean_rtt_ticks with a 370 * reasonable value until the epoch average RTT is 371 * calculated in cubic_post_recovery(). 372 */ 373 if (cubic_data->min_rtt_ticks > 374 cubic_data->mean_rtt_ticks) 375 cubic_data->mean_rtt_ticks = 376 cubic_data->min_rtt_ticks; 377 } 378 379 /* Sum samples for epoch average RTT calculation. */ 380 cubic_data->sum_rtt_ticks += t_srtt_ticks; 381 cubic_data->epoch_ack_count++; 382 } 383 } 384 385 /* 386 * Update the ssthresh in the event of congestion. 387 */ 388 static void 389 cubic_ssthresh_update(struct cc_var *ccv) 390 { 391 struct cubic *cubic_data; 392 393 cubic_data = ccv->cc_data; 394 395 /* 396 * On the first congestion event, set ssthresh to cwnd * 0.5, on 397 * subsequent congestion events, set it to cwnd * beta. 398 */ 399 if (cubic_data->num_cong_events == 0) 400 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd) >> 1; 401 else 402 CCV(ccv, snd_ssthresh) = (CCV(ccv, snd_cwnd) * CUBIC_BETA) 403 >> CUBIC_SHIFT; 404 } 405 406 407 DECLARE_CC_MODULE(cubic, &cubic_cc_algo); 408