sys/netinet/cc/cc_dctcp.c

   1 /*-
   2  * Copyright (c) 2007-2008
   3  *      Swinburne University of Technology, Melbourne, Australia
   4  * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
   5  * Copyright (c) 2014 Midori Kato <katoon@sfc.wide.ad.jp>
   6  * Copyright (c) 2014 The FreeBSD Foundation
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28  * SUCH DAMAGE.
  29  */
  30
  31 /*
  32  * An implementation of the DCTCP algorithm for FreeBSD, based on
  33  * "Data Center TCP (DCTCP)" by M. Alizadeh, A. Greenberg, D. A. Maltz,
  34  * J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan.,
  35  * in ACM Conference on SIGCOMM 2010, New York, USA,
  36  * Originally released as the contribution of Microsoft Research project.
  37  */
  38
  39 #include <sys/cdefs.h>
  40 __FBSDID("$FreeBSD$");
  41
  42 #include <sys/param.h>
  43 #include <sys/kernel.h>
  44 #include <sys/malloc.h>
  45 #include <sys/module.h>
  46 #include <sys/socket.h>
  47 #include <sys/socketvar.h>
  48 #include <sys/sysctl.h>
  49 #include <sys/systm.h>
  50
  51 #include <net/vnet.h>
  52
  53 #include <netinet/tcp.h>
  54 #include <netinet/tcp_seq.h>
  55 #include <netinet/tcp_var.h>
  56 #include <netinet/cc/cc.h>
  57 #include <netinet/cc/cc_module.h>
  58
  59 #define CAST_PTR_INT(X) (*((int*)(X)))
  60
  61 #define MAX_ALPHA_VALUE 1024
  62 static VNET_DEFINE(uint32_t, dctcp_alpha) = 0;
  63 #define V_dctcp_alpha       VNET(dctcp_alpha)
  64 static VNET_DEFINE(uint32_t, dctcp_shift_g) = 4;
  65 #define V_dctcp_shift_g     VNET(dctcp_shift_g)
  66 static VNET_DEFINE(uint32_t, dctcp_slowstart) = 0;
  67 #define V_dctcp_slowstart   VNET(dctcp_slowstart)
  68
  69 struct dctcp {
  70         int     bytes_ecn;      /* # of marked bytes during a RTT */
  71         int     bytes_total;    /* # of acked bytes during a RTT */
  72         int     alpha;          /* the fraction of marked bytes */
  73         int     ce_prev;        /* CE state of the last segment */
  74         int     save_sndnxt;    /* end sequence number of the current window */
  75         int     ece_curr;       /* ECE flag in this segment */
  76         int     ece_prev;       /* ECE flag in the last segment */
  77         uint32_t    num_cong_events; /* # of congestion events */
  78 };
  79
  80 static MALLOC_DEFINE(M_dctcp, "dctcp data",
  81     "Per connection data required for the dctcp algorithm");
  82
  83 static void     dctcp_ack_received(struct cc_var *ccv, uint16_t type);
  84 static void     dctcp_after_idle(struct cc_var *ccv);
  85 static void     dctcp_cb_destroy(struct cc_var *ccv);
  86 static int      dctcp_cb_init(struct cc_var *ccv);
  87 static void     dctcp_cong_signal(struct cc_var *ccv, uint32_t type);
  88 static void     dctcp_conn_init(struct cc_var *ccv);
  89 static void     dctcp_post_recovery(struct cc_var *ccv);
  90 static void     dctcp_ecnpkt_handler(struct cc_var *ccv);
  91 static void     dctcp_update_alpha(struct cc_var *ccv);
  92
  93 struct cc_algo dctcp_cc_algo = {
  94         .name = "dctcp",
  95         .ack_received = dctcp_ack_received,
  96         .cb_destroy = dctcp_cb_destroy,
  97         .cb_init = dctcp_cb_init,
  98         .cong_signal = dctcp_cong_signal,
  99         .conn_init = dctcp_conn_init,
 100         .post_recovery = dctcp_post_recovery,
 101         .ecnpkt_handler = dctcp_ecnpkt_handler,
 102         .after_idle = dctcp_after_idle,
 103 };
 104
 105 static void
 106 dctcp_ack_received(struct cc_var *ccv, uint16_t type)
 107 {
 108         struct dctcp *dctcp_data;
 109         int bytes_acked = 0;
 110
 111         dctcp_data = ccv->cc_data;
 112
 113         if (CCV(ccv, t_flags) & TF_ECN_PERMIT) {
 114                 /*
 115                  * DCTCP doesn't treat receipt of ECN marked packet as a
 116                  * congestion event. Thus, DCTCP always executes the ACK
 117                  * processing out of congestion recovery.
 118                  */
 119                 if (IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 120                         EXIT_CONGRECOVERY(CCV(ccv, t_flags));
 121                         newreno_cc_algo.ack_received(ccv, type);
 122                         ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 123                 } else
 124                         newreno_cc_algo.ack_received(ccv, type);
 125
 126                 if (type == CC_DUPACK)
 127                         bytes_acked = CCV(ccv, t_maxseg);
 128
 129                 if (type == CC_ACK)
 130                         bytes_acked = ccv->bytes_this_ack;
 131
 132                 /* Update total bytes. */
 133                 dctcp_data->bytes_total += bytes_acked;
 134
 135                 /* Update total marked bytes. */
 136                 if (dctcp_data->ece_curr) {
 137                         if (!dctcp_data->ece_prev
 138                             && bytes_acked > CCV(ccv, t_maxseg)) {
 139                                 dctcp_data->bytes_ecn +=
 140                                     (bytes_acked - CCV(ccv, t_maxseg));
 141                         } else
 142                                 dctcp_data->bytes_ecn += bytes_acked;
 143                         dctcp_data->ece_prev = 1;
 144                 } else {
 145                         if (dctcp_data->ece_prev
 146                             && bytes_acked > CCV(ccv, t_maxseg))
 147                                 dctcp_data->bytes_ecn += CCV(ccv, t_maxseg);
 148                         dctcp_data->ece_prev = 0;
 149                 }
 150                 dctcp_data->ece_curr = 0;
 151
 152                 /*
 153                  * Update the fraction of marked bytes at the end of
 154                  * current window size.
 155                  */
 156                 if ((IN_FASTRECOVERY(CCV(ccv, t_flags)) &&
 157                     SEQ_GEQ(ccv->curack, CCV(ccv, snd_recover))) ||
 158                     (!IN_FASTRECOVERY(CCV(ccv, t_flags)) &&
 159                     SEQ_GT(ccv->curack, dctcp_data->save_sndnxt)))
 160                         dctcp_update_alpha(ccv);
 161         } else
 162                 newreno_cc_algo.ack_received(ccv, type);
 163 }
 164
 165 static void
 166 dctcp_after_idle(struct cc_var *ccv)
 167 {
 168         struct dctcp *dctcp_data;
 169
 170         dctcp_data = ccv->cc_data;
 171
 172         /* Initialize internal parameters after idle time */
 173         dctcp_data->bytes_ecn = 0;
 174         dctcp_data->bytes_total = 0;
 175         dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
 176         dctcp_data->alpha = V_dctcp_alpha;
 177         dctcp_data->ece_curr = 0;
 178         dctcp_data->ece_prev = 0;
 179         dctcp_data->num_cong_events = 0;
 180
 181         dctcp_cc_algo.after_idle = newreno_cc_algo.after_idle;
 182 }
 183
 184 static void
 185 dctcp_cb_destroy(struct cc_var *ccv)
 186 {
 187         if (ccv->cc_data != NULL)
 188                 free(ccv->cc_data, M_dctcp);
 189 }
 190
 191 static int
 192 dctcp_cb_init(struct cc_var *ccv)
 193 {
 194         struct dctcp *dctcp_data;
 195
 196         dctcp_data = malloc(sizeof(struct dctcp), M_dctcp, M_NOWAIT|M_ZERO);
 197
 198         if (dctcp_data == NULL)
 199                 return (ENOMEM);
 200
 201         /* Initialize some key variables with sensible defaults. */
 202         dctcp_data->bytes_ecn = 0;
 203         dctcp_data->bytes_total = 0;
 204         /*
 205          * When alpha is set to 0 in the beginning, DCTCP sender transfers as
 206          * much data as possible until the value converges which may expand the
 207          * queueing delay at the switch. When alpha is set to 1, queueing delay
 208          * is kept small.
 209          * Throughput-sensitive applications should have alpha = 0
 210          * Latency-sensitive applications should have alpha = 1
 211          *
 212          * Note: DCTCP draft suggests initial alpha to be 1 but we've decided to
 213          * keep it 0 as default.
 214          */
 215         dctcp_data->alpha = V_dctcp_alpha;
 216         dctcp_data->save_sndnxt = 0;
 217         dctcp_data->ce_prev = 0;
 218         dctcp_data->ece_curr = 0;
 219         dctcp_data->ece_prev = 0;
 220         dctcp_data->num_cong_events = 0;
 221
 222         ccv->cc_data = dctcp_data;
 223         return (0);
 224 }
 225
 226 /*
 227  * Perform any necessary tasks before we enter congestion recovery.
 228  */
 229 static void
 230 dctcp_cong_signal(struct cc_var *ccv, uint32_t type)
 231 {
 232         struct dctcp *dctcp_data;
 233         u_int win, mss;
 234
 235         dctcp_data = ccv->cc_data;
 236         win = CCV(ccv, snd_cwnd);
 237         mss = CCV(ccv, t_maxseg);
 238
 239         switch (type) {
 240         case CC_NDUPACK:
 241                 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
 242                         if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 243                                 CCV(ccv, snd_ssthresh) = mss *
 244                                     max(win / 2 / mss, 2);
 245                                 dctcp_data->num_cong_events++;
 246                         } else {
 247                                 /* cwnd has already updated as congestion
 248                                  * recovery. Reverse cwnd value using
 249                                  * snd_cwnd_prev and recalculate snd_ssthresh
 250                                  */
 251                                 win = CCV(ccv, snd_cwnd_prev);
 252                                 CCV(ccv, snd_ssthresh) =
 253                                     max(win / 2 / mss, 2) * mss;
 254                         }
 255                         ENTER_RECOVERY(CCV(ccv, t_flags));
 256                 }
 257                 break;
 258         case CC_ECN:
 259                 /*
 260                  * Save current snd_cwnd when the host encounters both
 261                  * congestion recovery and fast recovery.
 262                  */
 263                 CCV(ccv, snd_cwnd_prev) = win;
 264                 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 265                         if (V_dctcp_slowstart &&
 266                             dctcp_data->num_cong_events++ == 0) {
 267                                 CCV(ccv, snd_ssthresh) =
 268                                     mss * max(win / 2 / mss, 2);
 269                                 dctcp_data->alpha = MAX_ALPHA_VALUE;
 270                                 dctcp_data->bytes_ecn = 0;
 271                                 dctcp_data->bytes_total = 0;
 272                                 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
 273                         } else
 274                                 CCV(ccv, snd_ssthresh) = max((win - ((win *
 275                                     dctcp_data->alpha) >> 11)) / mss, 2) * mss;
 276                         CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
 277                         ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 278                 }
 279                 dctcp_data->ece_curr = 1;
 280                 break;
 281         case CC_RTO:
 282                 if (CCV(ccv, t_flags) & TF_ECN_PERMIT) {
 283                         CCV(ccv, t_flags) |= TF_ECN_SND_CWR;
 284                         dctcp_update_alpha(ccv);
 285                         dctcp_data->save_sndnxt += CCV(ccv, t_maxseg);
 286                         dctcp_data->num_cong_events++;
 287                 }
 288                 break;
 289         }
 290 }
 291
 292 static void
 293 dctcp_conn_init(struct cc_var *ccv)
 294 {
 295         struct dctcp *dctcp_data;
 296
 297         dctcp_data = ccv->cc_data;
 298
 299         if (CCV(ccv, t_flags) & TF_ECN_PERMIT)
 300                 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
 301 }
 302
 303 /*
 304  * Perform any necessary tasks before we exit congestion recovery.
 305  */
 306 static void
 307 dctcp_post_recovery(struct cc_var *ccv)
 308 {
 309         dctcp_cc_algo.post_recovery = newreno_cc_algo.post_recovery;
 310
 311         if (CCV(ccv, t_flags) & TF_ECN_PERMIT)
 312                 dctcp_update_alpha(ccv);
 313 }
 314
 315 /*
 316  * Execute an additional ECN processing using ECN field in IP header and the CWR
 317  * bit in TCP header.
 318  *
 319  * delay_ack == 0 - Delayed ACK disabled
 320  * delay_ack == 1 - Delayed ACK enabled
 321  */
 322
 323 static void
 324 dctcp_ecnpkt_handler(struct cc_var *ccv)
 325 {
 326         struct dctcp *dctcp_data;
 327         uint32_t ccflag;
 328         int delay_ack;
 329
 330         dctcp_data = ccv->cc_data;
 331         ccflag = ccv->flags;
 332         delay_ack = 1;
 333
 334         /*
 335          * DCTCP responses an ACK immediately when the CE state
 336          * in between this segment and the last segment is not same.
 337          */
 338         if (ccflag & CCF_IPHDR_CE) {
 339                 if (!dctcp_data->ce_prev && (ccflag & CCF_DELACK))
 340                         delay_ack = 0;
 341                 dctcp_data->ce_prev = 1;
 342                 CCV(ccv, t_flags) |= TF_ECN_SND_ECE;
 343         } else {
 344                 if (dctcp_data->ce_prev && (ccflag & CCF_DELACK))
 345                         delay_ack = 0;
 346                 dctcp_data->ce_prev = 0;
 347                 CCV(ccv, t_flags) &= ~TF_ECN_SND_ECE;
 348         }
 349
 350         /* DCTCP sets delayed ack when this segment sets the CWR flag. */
 351         if ((ccflag & CCF_DELACK) && (ccflag & CCF_TCPHDR_CWR))
 352                 delay_ack = 1;
 353
 354         if (delay_ack == 0)
 355                 ccv->flags |= CCF_ACKNOW;
 356         else
 357                 ccv->flags &= ~CCF_ACKNOW;
 358 }
 359
 360 /*
 361  * Update the fraction of marked bytes represented as 'alpha'.
 362  * Also initialize several internal parameters at the end of this function.
 363  */
 364 static void
 365 dctcp_update_alpha(struct cc_var *ccv)
 366 {
 367         struct dctcp *dctcp_data;
 368         int alpha_prev;
 369
 370         dctcp_data = ccv->cc_data;
 371         alpha_prev = dctcp_data->alpha;
 372         dctcp_data->bytes_total = max(dctcp_data->bytes_total, 1);
 373
 374         /*
 375          * Update alpha: alpha = (1 - g) * alpha + g * F.
 376          * Here:
 377          * g is weight factor
 378          *      recommaded to be set to 1/16
 379          *      small g = slow convergence between competitive DCTCP flows
 380          *      large g = impacts low utilization of bandwidth at switches
 381          * F is fraction of marked segments in last RTT
 382          *      updated every RTT
 383          * Alpha must be round to 0 - MAX_ALPHA_VALUE.
 384          */
 385         dctcp_data->alpha = min(alpha_prev - (alpha_prev >> V_dctcp_shift_g) +
 386             (dctcp_data->bytes_ecn << (10 - V_dctcp_shift_g)) /
 387             dctcp_data->bytes_total, MAX_ALPHA_VALUE);
 388
 389         /* Initialize internal parameters for next alpha calculation */
 390         dctcp_data->bytes_ecn = 0;
 391         dctcp_data->bytes_total = 0;
 392         dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
 393 }
 394
 395 static int
 396 dctcp_alpha_handler(SYSCTL_HANDLER_ARGS)
 397 {
 398         uint32_t new;
 399         int error;
 400
 401         new = V_dctcp_alpha;
 402         error = sysctl_handle_int(oidp, &new, 0, req);
 403         if (error == 0 && req->newptr != NULL) {
 404                 if (CAST_PTR_INT(req->newptr) > 1)
 405                         error = EINVAL;
 406                 else {
 407                         if (new > MAX_ALPHA_VALUE)
 408                                 V_dctcp_alpha = MAX_ALPHA_VALUE;
 409                         else
 410                                 V_dctcp_alpha = new;
 411                 }
 412         }
 413
 414         return (error);
 415 }
 416
 417 static int
 418 dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS)
 419 {
 420         uint32_t new;
 421         int error;
 422
 423         new = V_dctcp_shift_g;
 424         error = sysctl_handle_int(oidp, &new, 0, req);
 425         if (error == 0 && req->newptr != NULL) {
 426                 if (CAST_PTR_INT(req->newptr) > 1)
 427                         error = EINVAL;
 428                 else
 429                         V_dctcp_shift_g = new;
 430         }
 431
 432         return (error);
 433 }
 434
 435 static int
 436 dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS)
 437 {
 438         uint32_t new;
 439         int error;
 440
 441         new = V_dctcp_slowstart;
 442         error = sysctl_handle_int(oidp, &new, 0, req);
 443         if (error == 0 && req->newptr != NULL) {
 444                 if (CAST_PTR_INT(req->newptr) > 1)
 445                         error = EINVAL;
 446                 else
 447                         V_dctcp_slowstart = new;
 448         }
 449
 450         return (error);
 451 }
 452
 453 SYSCTL_DECL(_net_inet_tcp_cc_dctcp);
 454 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp, CTLFLAG_RW, NULL,
 455     "dctcp congestion control related settings");
 456
 457 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha,
 458     CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_alpha), 0,
 459     &dctcp_alpha_handler,
 460     "IU", "dctcp alpha parameter");
 461
 462 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g,
 463     CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_shift_g), 4,
 464     &dctcp_shift_g_handler,
 465     "IU", "dctcp shift parameter");
 466
 467 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart,
 468     CTLFLAG_VNET|CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(dctcp_slowstart), 0,
 469     &dctcp_slowstart_handler,
 470     "IU", "half CWND reduction after the first slow start");
 471
 472 DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo);