sys/netinet/cc/cc_chd.c

   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
 334         e_t = khelp_get_osd(CCV(ccv, osd), ertt_id);
 335         chd_data = ccv->cc_data;
 336         qdly = imax(e_t->rtt, chd_data->maxrtt_in_rtt) - e_t->minrtt;
 337
 338         switch(signal_type) {
 339         case CC_CHD_DELAY:
 340                 chd_window_decrease(ccv); /* Set new ssthresh. */
 341                 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
 342                 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
 343                 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 344                 break;
 345
 346         case CC_NDUPACK: /* Packet loss. */
 347                 /*
 348                  * Only react to loss as a congestion signal if qdly >
 349                  * V_chd_qthresh.  If qdly is less than qthresh, presume that
 350                  * this is a non congestion related loss. If qdly is greater
 351                  * than qthresh, assume that we are competing with loss based
 352                  * tcp flows and restore window from any unnecessary backoffs,
 353                  * before the decrease.
 354                  */
 355                 if (!IN_RECOVERY(CCV(ccv, t_flags)) && qdly > V_chd_qthresh) {
 356                         if (chd_data->loss_compete) {
 357                                 CCV(ccv, snd_cwnd) = max(CCV(ccv, snd_cwnd),
 358                                     chd_data->shadow_w);
 359                         }
 360                         chd_window_decrease(ccv);
 361                 } else {
 362                          /*
 363                           * This loss isn't congestion related, or already
 364                           * recovering from congestion.
 365                           */
 366                         CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
 367                         CCV(ccv, snd_recover) = CCV(ccv, snd_max);
 368                 }
 369
 370                 if (chd_data->shadow_w > 0) {
 371                         chd_data->shadow_w = max(chd_data->shadow_w /
 372                             CCV(ccv, t_maxseg) / 2, 2) * CCV(ccv, t_maxseg);
 373                 }
 374                 ENTER_FASTRECOVERY(CCV(ccv, t_flags));
 375                 break;
 376
 377         default:
 378                 newreno_cc_algo.cong_signal(ccv, signal_type);
 379         }
 380 }
 381
 382 static void
 383 chd_conn_init(struct cc_var *ccv)
 384 {
 385         struct chd *chd_data;
 386
 387         chd_data = ccv->cc_data;
 388         chd_data->prev_backoff_qdly = 0;
 389         chd_data->maxrtt_in_rtt = 0;
 390         chd_data->loss_compete = 0;
 391         /*
 392          * Initialise the shadow_cwnd to be equal to snd_cwnd in case we are
 393          * competing with loss based flows from the start.
 394          */
 395         chd_data->shadow_w = CCV(ccv, snd_cwnd);
 396 }
 397
 398 static int
 399 chd_mod_init(void)
 400 {
 401
 402         ertt_id = khelp_get_id("ertt");
 403         if (ertt_id <= 0) {
 404                 printf("%s: h_ertt module not found\n", __func__);
 405                 return (ENOENT);
 406         }
 407
 408         chd_cc_algo.after_idle = newreno_cc_algo.after_idle;
 409         chd_cc_algo.post_recovery = newreno_cc_algo.post_recovery;
 410
 411         return (0);
 412 }
 413
 414 static int
 415 chd_loss_fair_handler(SYSCTL_HANDLER_ARGS)
 416 {
 417         int error;
 418         uint32_t new;
 419
 420         new = V_chd_loss_fair;
 421         error = sysctl_handle_int(oidp, &new, 0, req);
 422         if (error == 0 && req->newptr != NULL) {
 423                 if (CAST_PTR_INT(req->newptr) > 1)
 424                         error = EINVAL;
 425                 else
 426                         V_chd_loss_fair = new;
 427         }
 428
 429         return (error);
 430 }
 431
 432 static int
 433 chd_pmax_handler(SYSCTL_HANDLER_ARGS)
 434 {
 435         int error;
 436         uint32_t new;
 437
 438         new = V_chd_pmax;
 439         error = sysctl_handle_int(oidp, &new, 0, req);
 440         if (error == 0 && req->newptr != NULL) {
 441                 if (CAST_PTR_INT(req->newptr) == 0 ||
 442                     CAST_PTR_INT(req->newptr) > 100)
 443                         error = EINVAL;
 444                 else
 445                         V_chd_pmax = new;
 446         }
 447
 448         return (error);
 449 }
 450
 451 static int
 452 chd_qthresh_handler(SYSCTL_HANDLER_ARGS)
 453 {
 454         int error;
 455         uint32_t new;
 456
 457         new = V_chd_qthresh;
 458         error = sysctl_handle_int(oidp, &new, 0, req);
 459         if (error == 0 && req->newptr != NULL) {
 460                 if (CAST_PTR_INT(req->newptr) <= V_chd_qmin)
 461                         error = EINVAL;
 462                 else
 463                         V_chd_qthresh = new;
 464         }
 465
 466         return (error);
 467 }
 468
 469 SYSCTL_DECL(_net_inet_tcp_cc_chd);
 470 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, chd, CTLFLAG_RW, NULL,
 471     "CAIA Hamilton delay-based congestion control related settings");
 472
 473 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, loss_fair,
 474     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
 475     &VNET_NAME(chd_loss_fair), 1, &chd_loss_fair_handler,
 476     "IU", "Flag to enable shadow window functionality.");
 477
 478 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, pmax,
 479     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
 480     &VNET_NAME(chd_pmax), 5, &chd_pmax_handler,
 481     "IU", "Per RTT maximum backoff probability as a percentage");
 482
 483 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, queue_threshold,
 484     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
 485     &VNET_NAME(chd_qthresh), 20, &chd_qthresh_handler,
 486     "IU", "Queueing congestion threshold in ticks");
 487
 488 SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, queue_min,
 489     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_qmin), 5,
 490     "Minimum queueing delay threshold in ticks");
 491
 492 SYSCTL_UINT(_net_inet_tcp_cc_chd,  OID_AUTO, use_max,
 493     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_use_max), 1,
 494     "Use the maximum RTT seen within the measurement period (RTT) "
 495     "as the basic delay measurement for the algorithm.");
 496
 497 DECLARE_CC_MODULE(chd, &chd_cc_algo);
 498 MODULE_DEPEND(chd, ertt, 1, 1, 1);