sys/netinet/cc/cc_chd.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2009-2010
   5  *      Swinburne University of Technology, Melbourne, Australia
   6  * Copyright (c) 2010-2011 The FreeBSD Foundation
   7  * All rights reserved.
   8  *
   9  * This software was developed at the Centre for Advanced Internet
  10  * Architectures, Swinburne University of Technology, by David Hayes and
  11  * Lawrence Stewart, made possible in part by a grant from the Cisco University
  12  * Research Program Fund at Community Foundation Silicon Valley.
  13  *
  14  * Portions of this software were developed at the Centre for Advanced Internet
  15  * Architectures, Swinburne University of Technology, Melbourne, Australia by
  16  * David Hayes under sponsorship from the FreeBSD Foundation.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions
  20  * are met:
  21  * 1. Redistributions of source code must retain the above copyright
  22  *    notice, this list of conditions and the following disclaimer.
  23  * 2. Redistributions in binary form must reproduce the above copyright
  24  *    notice, this list of conditions and the following disclaimer in the
  25  *    documentation and/or other materials provided with the distribution.
  26  *
  27  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37  * SUCH DAMAGE.
  38  */
  39
  40 /*
  41  * An implementation of the CAIA-Hamilton delay based congestion control
  42  * algorithm, based on "Improved coexistence and loss tolerance for delay based
  43  * TCP congestion control" by D. A. Hayes and G. Armitage., in 35th Annual IEEE
  44  * Conference on Local Computer Networks (LCN 2010), Denver, Colorado, USA,
  45  * 11-14 October 2010.
  46  *
  47  * Originally released as part of the NewTCP research project at Swinburne
  48  * University of Technology's Centre for Advanced Internet Architectures,
  49  * Melbourne, Australia, which was made possible in part by a grant from the
  50  * Cisco University Research Program Fund at Community Foundation Silicon
  51  * Valley. More details are available at:
  52  *   http://caia.swin.edu.au/urp/newtcp/
  53  */
  54
  55 #include <sys/cdefs.h>
  56 __FBSDID("$FreeBSD$");
  57
  58 #include <sys/param.h>
  59 #include <sys/kernel.h>
  60 #include <sys/khelp.h>
  61 #include <sys/limits.h>
  62 #include <sys/malloc.h>
  63 #include <sys/module.h>
  64 #include <sys/queue.h>
  65 #include <sys/socket.h>
  66 #include <sys/socketvar.h>
  67 #include <sys/sysctl.h>
  68 #include <sys/systm.h>
  69
  70 #include <net/vnet.h>
  71
  72 #include <netinet/tcp.h>
  73 #include <netinet/tcp_seq.h>
  74 #include <netinet/tcp_timer.h>
  75 #include <netinet/tcp_var.h>
  76 #include <netinet/cc/cc.h>
  77 #include <netinet/cc/cc_module.h>
  78
  79 #include <netinet/khelp/h_ertt.h>
  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 VNET_DEFINE_STATIC(uint32_t, chd_qmin) = 5;
 119 VNET_DEFINE_STATIC(uint32_t, chd_pmax) = 50;
 120 VNET_DEFINE_STATIC(uint32_t, chd_loss_fair) = 1;
 121 VNET_DEFINE_STATIC(uint32_t, chd_use_max) = 1;
 122 VNET_DEFINE_STATIC(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         free(ccv->cc_data, M_CHD);
 309 }
 310
 311 static int
 312 chd_cb_init(struct cc_var *ccv)
 313 {
 314         struct chd *chd_data;
 315
 316         chd_data = malloc(sizeof(struct chd), M_CHD, M_NOWAIT);
 317         if (chd_data == NULL)
 318                 return (ENOMEM);
 319
 320         chd_data->shadow_w = 0;
 321         ccv->cc_data = chd_data;
 322
 323         return (0);
 324 }
 325
 326 static void
 327 chd_cong_signal(struct cc_var *ccv, uint32_t signal_type)
 328 {
 329         struct ertt *e_t;
 330         struct chd *chd_data;
 331         int qdly;
 332
 333         e_t = khelp_get_osd(CCV(ccv, osd), ertt_id);
 334         chd_data = ccv->cc_data;
 335         qdly = imax(e_t->rtt, chd_data->maxrtt_in_rtt) - e_t->minrtt;
 336
 337         switch(signal_type) {
 338         case CC_CHD_DELAY:
 339                 chd_window_decrease(ccv); /* Set new ssthresh. */
 340                 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
 341                 CCV(ccv, snd_recover) = CCV(ccv, snd_max);
 342                 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 343                 break;
 344
 345         case CC_NDUPACK: /* Packet loss. */
 346                 /*
 347                  * Only react to loss as a congestion signal if qdly >
 348                  * V_chd_qthresh.  If qdly is less than qthresh, presume that
 349                  * this is a non congestion related loss. If qdly is greater
 350                  * than qthresh, assume that we are competing with loss based
 351                  * tcp flows and restore window from any unnecessary backoffs,
 352                  * before the decrease.
 353                  */
 354                 if (!IN_RECOVERY(CCV(ccv, t_flags)) && qdly > V_chd_qthresh) {
 355                         if (chd_data->loss_compete) {
 356                                 CCV(ccv, snd_cwnd) = max(CCV(ccv, snd_cwnd),
 357                                     chd_data->shadow_w);
 358                         }
 359                         chd_window_decrease(ccv);
 360                 } else {
 361                          /*
 362                           * This loss isn't congestion related, or already
 363                           * recovering from congestion.
 364                           */
 365                         CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
 366                         CCV(ccv, snd_recover) = CCV(ccv, snd_max);
 367                 }
 368
 369                 if (chd_data->shadow_w > 0) {
 370                         chd_data->shadow_w = max(chd_data->shadow_w /
 371                             CCV(ccv, t_maxseg) / 2, 2) * CCV(ccv, t_maxseg);
 372                 }
 373                 ENTER_FASTRECOVERY(CCV(ccv, t_flags));
 374                 break;
 375
 376         default:
 377                 newreno_cc_algo.cong_signal(ccv, signal_type);
 378         }
 379 }
 380
 381 static void
 382 chd_conn_init(struct cc_var *ccv)
 383 {
 384         struct chd *chd_data;
 385
 386         chd_data = ccv->cc_data;
 387         chd_data->prev_backoff_qdly = 0;
 388         chd_data->maxrtt_in_rtt = 0;
 389         chd_data->loss_compete = 0;
 390         /*
 391          * Initialise the shadow_cwnd to be equal to snd_cwnd in case we are
 392          * competing with loss based flows from the start.
 393          */
 394         chd_data->shadow_w = CCV(ccv, snd_cwnd);
 395 }
 396
 397 static int
 398 chd_mod_init(void)
 399 {
 400
 401         ertt_id = khelp_get_id("ertt");
 402         if (ertt_id <= 0) {
 403                 printf("%s: h_ertt module not found\n", __func__);
 404                 return (ENOENT);
 405         }
 406
 407         chd_cc_algo.after_idle = newreno_cc_algo.after_idle;
 408         chd_cc_algo.post_recovery = newreno_cc_algo.post_recovery;
 409
 410         return (0);
 411 }
 412
 413 static int
 414 chd_loss_fair_handler(SYSCTL_HANDLER_ARGS)
 415 {
 416         int error;
 417         uint32_t new;
 418
 419         new = V_chd_loss_fair;
 420         error = sysctl_handle_int(oidp, &new, 0, req);
 421         if (error == 0 && req->newptr != NULL) {
 422                 if (new > 1)
 423                         error = EINVAL;
 424                 else
 425                         V_chd_loss_fair = new;
 426         }
 427
 428         return (error);
 429 }
 430
 431 static int
 432 chd_pmax_handler(SYSCTL_HANDLER_ARGS)
 433 {
 434         int error;
 435         uint32_t new;
 436
 437         new = V_chd_pmax;
 438         error = sysctl_handle_int(oidp, &new, 0, req);
 439         if (error == 0 && req->newptr != NULL) {
 440                 if (new == 0 || new > 100)
 441                         error = EINVAL;
 442                 else
 443                         V_chd_pmax = new;
 444         }
 445
 446         return (error);
 447 }
 448
 449 static int
 450 chd_qthresh_handler(SYSCTL_HANDLER_ARGS)
 451 {
 452         int error;
 453         uint32_t new;
 454
 455         new = V_chd_qthresh;
 456         error = sysctl_handle_int(oidp, &new, 0, req);
 457         if (error == 0 && req->newptr != NULL) {
 458                 if (new <= V_chd_qmin)
 459                         error = EINVAL;
 460                 else
 461                         V_chd_qthresh = new;
 462         }
 463
 464         return (error);
 465 }
 466
 467 SYSCTL_DECL(_net_inet_tcp_cc_chd);
 468 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, chd, CTLFLAG_RW, NULL,
 469     "CAIA Hamilton delay-based congestion control related settings");
 470
 471 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, loss_fair,
 472     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
 473     &VNET_NAME(chd_loss_fair), 1, &chd_loss_fair_handler,
 474     "IU", "Flag to enable shadow window functionality.");
 475
 476 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, pmax,
 477     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
 478     &VNET_NAME(chd_pmax), 5, &chd_pmax_handler,
 479     "IU", "Per RTT maximum backoff probability as a percentage");
 480
 481 SYSCTL_PROC(_net_inet_tcp_cc_chd, OID_AUTO, queue_threshold,
 482     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW,
 483     &VNET_NAME(chd_qthresh), 20, &chd_qthresh_handler,
 484     "IU", "Queueing congestion threshold in ticks");
 485
 486 SYSCTL_UINT(_net_inet_tcp_cc_chd, OID_AUTO, queue_min,
 487     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_qmin), 5,
 488     "Minimum queueing delay threshold in ticks");
 489
 490 SYSCTL_UINT(_net_inet_tcp_cc_chd,  OID_AUTO, use_max,
 491     CTLFLAG_VNET | CTLFLAG_RW, &VNET_NAME(chd_use_max), 1,
 492     "Use the maximum RTT seen within the measurement period (RTT) "
 493     "as the basic delay measurement for the algorithm.");
 494
 495 DECLARE_CC_MODULE(chd, &chd_cc_algo);
 496 MODULE_DEPEND(chd, ertt, 1, 1, 1);