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 DCTCP_SHIFT 10
  60 #define MAX_ALPHA_VALUE (1<<DCTCP_SHIFT)
  61 VNET_DEFINE_STATIC(uint32_t, dctcp_alpha) = MAX_ALPHA_VALUE;
  62 #define V_dctcp_alpha       VNET(dctcp_alpha)
  63 VNET_DEFINE_STATIC(uint32_t, dctcp_shift_g) = 4;
  64 #define V_dctcp_shift_g     VNET(dctcp_shift_g)
  65 VNET_DEFINE_STATIC(uint32_t, dctcp_slowstart) = 0;
  66 #define V_dctcp_slowstart   VNET(dctcp_slowstart)
  67
  68 struct dctcp {
  69         uint32_t bytes_ecn;       /* # of marked bytes during a RTT */
  70         uint32_t bytes_total;     /* # of acked bytes during a RTT */
  71         int      alpha;           /* the fraction of marked bytes */
  72         int      ce_prev;         /* CE state of the last segment */
  73         tcp_seq  save_sndnxt;     /* end sequence number of the current window */
  74         int      ece_curr;        /* ECE flag in this segment */
  75         int      ece_prev;        /* ECE flag in the last segment */
  76         uint32_t num_cong_events; /* # of congestion events */
  77 };
  78
  79 static MALLOC_DEFINE(M_dctcp, "dctcp data",
  80     "Per connection data required for the dctcp algorithm");
  81
  82 static void     dctcp_ack_received(struct cc_var *ccv, uint16_t type);
  83 static void     dctcp_after_idle(struct cc_var *ccv);
  84 static void     dctcp_cb_destroy(struct cc_var *ccv);
  85 static int      dctcp_cb_init(struct cc_var *ccv);
  86 static void     dctcp_cong_signal(struct cc_var *ccv, uint32_t type);
  87 static void     dctcp_conn_init(struct cc_var *ccv);
  88 static void     dctcp_post_recovery(struct cc_var *ccv);
  89 static void     dctcp_ecnpkt_handler(struct cc_var *ccv);
  90 static void     dctcp_update_alpha(struct cc_var *ccv);
  91
  92 struct cc_algo dctcp_cc_algo = {
  93         .name = "dctcp",
  94         .ack_received = dctcp_ack_received,
  95         .cb_destroy = dctcp_cb_destroy,
  96         .cb_init = dctcp_cb_init,
  97         .cong_signal = dctcp_cong_signal,
  98         .conn_init = dctcp_conn_init,
  99         .post_recovery = dctcp_post_recovery,
 100         .ecnpkt_handler = dctcp_ecnpkt_handler,
 101         .after_idle = dctcp_after_idle,
 102 };
 103
 104 static void
 105 dctcp_ack_received(struct cc_var *ccv, uint16_t type)
 106 {
 107         struct dctcp *dctcp_data;
 108         int bytes_acked = 0;
 109
 110         dctcp_data = ccv->cc_data;
 111
 112         if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) {
 113                 /*
 114                  * DCTCP doesn't treat receipt of ECN marked packet as a
 115                  * congestion event. Thus, DCTCP always executes the ACK
 116                  * processing out of congestion recovery.
 117                  */
 118                 if (IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 119                         EXIT_CONGRECOVERY(CCV(ccv, t_flags));
 120                         newreno_cc_algo.ack_received(ccv, type);
 121                         ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 122                 } else
 123                         newreno_cc_algo.ack_received(ccv, type);
 124
 125                 if (type == CC_DUPACK)
 126                         bytes_acked = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
 127
 128                 if (type == CC_ACK)
 129                         bytes_acked = ccv->bytes_this_ack;
 130
 131                 /* Update total bytes. */
 132                 dctcp_data->bytes_total += bytes_acked;
 133
 134                 /* Update total marked bytes. */
 135                 if (dctcp_data->ece_curr) {
 136                         //XXRMS: For fluid-model DCTCP, update
 137                         //cwnd here during for RTT fairness
 138                         if (!dctcp_data->ece_prev
 139                             && bytes_acked > CCV(ccv, t_maxseg)) {
 140                                 dctcp_data->bytes_ecn +=
 141                                     (bytes_acked - CCV(ccv, t_maxseg));
 142                         } else
 143                                 dctcp_data->bytes_ecn += bytes_acked;
 144                         dctcp_data->ece_prev = 1;
 145                 } else {
 146                         if (dctcp_data->ece_prev
 147                             && bytes_acked > CCV(ccv, t_maxseg))
 148                                 dctcp_data->bytes_ecn += CCV(ccv, t_maxseg);
 149                         dctcp_data->ece_prev = 0;
 150                 }
 151                 dctcp_data->ece_curr = 0;
 152
 153                 /*
 154                  * Update the fraction of marked bytes at the end of
 155                  * current window size.
 156                  */
 157                 if (!IN_FASTRECOVERY(CCV(ccv, t_flags)) &&
 158                     SEQ_GT(ccv->curack, dctcp_data->save_sndnxt))
 159                         dctcp_update_alpha(ccv);
 160         } else
 161                 newreno_cc_algo.ack_received(ccv, type);
 162 }
 163
 164 static void
 165 dctcp_after_idle(struct cc_var *ccv)
 166 {
 167         struct dctcp *dctcp_data;
 168
 169         if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) {
 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
 182         newreno_cc_algo.after_idle(ccv);
 183 }
 184
 185 static void
 186 dctcp_cb_destroy(struct cc_var *ccv)
 187 {
 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 cwin, mss;
 234
 235         if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT) {
 236                 dctcp_data = ccv->cc_data;
 237                 cwin = CCV(ccv, snd_cwnd);
 238                 mss = tcp_maxseg(ccv->ccvc.tcp);
 239
 240                 switch (type) {
 241                 case CC_NDUPACK:
 242                         if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
 243                                 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 244                                         CCV(ccv, snd_ssthresh) =
 245                                             max(cwin / 2, 2 * mss);
 246                                         dctcp_data->num_cong_events++;
 247                                 } else {
 248                                         /* cwnd has already updated as congestion
 249                                          * recovery. Reverse cwnd value using
 250                                          * snd_cwnd_prev and recalculate snd_ssthresh
 251                                          */
 252                                         cwin = CCV(ccv, snd_cwnd_prev);
 253                                         CCV(ccv, snd_ssthresh) =
 254                                             max(cwin / 2, 2 * mss);
 255                                 }
 256                                 ENTER_RECOVERY(CCV(ccv, t_flags));
 257                         }
 258                         break;
 259                 case CC_ECN:
 260                         /*
 261                          * Save current snd_cwnd when the host encounters both
 262                          * congestion recovery and fast recovery.
 263                          */
 264                         CCV(ccv, snd_cwnd_prev) = cwin;
 265                         if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 266                                 if (V_dctcp_slowstart &&
 267                                     dctcp_data->num_cong_events++ == 0) {
 268                                         CCV(ccv, snd_ssthresh) =
 269                                             max(cwin / 2, 2 * mss);
 270                                         dctcp_data->alpha = MAX_ALPHA_VALUE;
 271                                         dctcp_data->bytes_ecn = 0;
 272                                         dctcp_data->bytes_total = 0;
 273                                         dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
 274                                 } else
 275                                         CCV(ccv, snd_ssthresh) =
 276                                             max((cwin - (((uint64_t)cwin *
 277                                             dctcp_data->alpha) >> (DCTCP_SHIFT+1))),
 278                                             2 * mss);
 279                                 CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
 280                                 ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 281                         }
 282                         dctcp_data->ece_curr = 1;
 283                         break;
 284                 case CC_RTO:
 285                         CCV(ccv, snd_ssthresh) = max(min(CCV(ccv, snd_wnd),
 286                                                          CCV(ccv, snd_cwnd)) / 2 / mss,
 287                                                      2) * mss;
 288                         CCV(ccv, snd_cwnd) = mss;
 289                         dctcp_update_alpha(ccv);
 290                         dctcp_data->save_sndnxt += CCV(ccv, t_maxseg);
 291                         dctcp_data->num_cong_events++;
 292                         break;
 293                 }
 294         } else
 295                 newreno_cc_algo.cong_signal(ccv, type);
 296 }
 297
 298 static void
 299 dctcp_conn_init(struct cc_var *ccv)
 300 {
 301         struct dctcp *dctcp_data;
 302
 303         dctcp_data = ccv->cc_data;
 304
 305         if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT)
 306                 dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
 307 }
 308
 309 /*
 310  * Perform any necessary tasks before we exit congestion recovery.
 311  */
 312 static void
 313 dctcp_post_recovery(struct cc_var *ccv)
 314 {
 315         newreno_cc_algo.post_recovery(ccv);
 316
 317         if (CCV(ccv, t_flags2) & TF2_ECN_PERMIT)
 318                 dctcp_update_alpha(ccv);
 319 }
 320
 321 /*
 322  * Execute an additional ECN processing using ECN field in IP header
 323  * and the CWR bit in TCP header.
 324  */
 325 static void
 326 dctcp_ecnpkt_handler(struct cc_var *ccv)
 327 {
 328         struct dctcp *dctcp_data;
 329         uint32_t ccflag;
 330         int acknow;
 331
 332         dctcp_data = ccv->cc_data;
 333         ccflag = ccv->flags;
 334         acknow = 0;
 335
 336         /*
 337          * DCTCP responds with an ACK immediately when the CE state
 338          * in between this segment and the last segment has changed.
 339          */
 340         if (ccflag & CCF_IPHDR_CE) {
 341                 if (!dctcp_data->ce_prev) {
 342                         acknow = 1;
 343                         dctcp_data->ce_prev = 1;
 344                         CCV(ccv, t_flags2) |= TF2_ECN_SND_ECE;
 345                 }
 346         } else {
 347                 if (dctcp_data->ce_prev) {
 348                         acknow = 1;
 349                         dctcp_data->ce_prev = 0;
 350                         CCV(ccv, t_flags2) &= ~TF2_ECN_SND_ECE;
 351                 }
 352         }
 353
 354         if ((acknow) || (ccflag & CCF_TCPHDR_CWR)) {
 355                 ccv->flags |= CCF_ACKNOW;
 356         } else {
 357                 ccv->flags &= ~CCF_ACKNOW;
 358         }
 359 }
 360
 361 /*
 362  * Update the fraction of marked bytes represented as 'alpha'.
 363  * Also initialize several internal parameters at the end of this function.
 364  */
 365 static void
 366 dctcp_update_alpha(struct cc_var *ccv)
 367 {
 368         struct dctcp *dctcp_data;
 369         int alpha_prev;
 370
 371         dctcp_data = ccv->cc_data;
 372         alpha_prev = dctcp_data->alpha;
 373         dctcp_data->bytes_total = max(dctcp_data->bytes_total, 1);
 374
 375         /*
 376          * Update alpha: alpha = (1 - g) * alpha + g * M.
 377          * Here:
 378          * g is weight factor
 379          *      recommaded to be set to 1/16
 380          *      small g = slow convergence between competitive DCTCP flows
 381          *      large g = impacts low utilization of bandwidth at switches
 382          * M is fraction of marked segments in last RTT
 383          *      updated every RTT
 384          * Alpha must be round to 0 - MAX_ALPHA_VALUE.
 385          */
 386         dctcp_data->alpha = ulmin(alpha_prev - (alpha_prev >> V_dctcp_shift_g) +
 387             ((uint64_t)dctcp_data->bytes_ecn << (DCTCP_SHIFT - V_dctcp_shift_g)) /
 388             dctcp_data->bytes_total, MAX_ALPHA_VALUE);
 389
 390         /* Initialize internal parameters for next alpha calculation */
 391         dctcp_data->bytes_ecn = 0;
 392         dctcp_data->bytes_total = 0;
 393         dctcp_data->save_sndnxt = CCV(ccv, snd_nxt);
 394 }
 395
 396 static int
 397 dctcp_alpha_handler(SYSCTL_HANDLER_ARGS)
 398 {
 399         uint32_t new;
 400         int error;
 401
 402         new = V_dctcp_alpha;
 403         error = sysctl_handle_int(oidp, &new, 0, req);
 404         if (error == 0 && req->newptr != NULL) {
 405                 if (new > MAX_ALPHA_VALUE)
 406                         error = EINVAL;
 407                 else
 408                         V_dctcp_alpha = new;
 409         }
 410
 411         return (error);
 412 }
 413
 414 static int
 415 dctcp_shift_g_handler(SYSCTL_HANDLER_ARGS)
 416 {
 417         uint32_t new;
 418         int error;
 419
 420         new = V_dctcp_shift_g;
 421         error = sysctl_handle_int(oidp, &new, 0, req);
 422         if (error == 0 && req->newptr != NULL) {
 423                 if (new > DCTCP_SHIFT)
 424                         error = EINVAL;
 425                 else
 426                         V_dctcp_shift_g = new;
 427         }
 428
 429         return (error);
 430 }
 431
 432 static int
 433 dctcp_slowstart_handler(SYSCTL_HANDLER_ARGS)
 434 {
 435         uint32_t new;
 436         int error;
 437
 438         new = V_dctcp_slowstart;
 439         error = sysctl_handle_int(oidp, &new, 0, req);
 440         if (error == 0 && req->newptr != NULL) {
 441                 if (new > 1)
 442                         error = EINVAL;
 443                 else
 444                         V_dctcp_slowstart = new;
 445         }
 446
 447         return (error);
 448 }
 449
 450 SYSCTL_DECL(_net_inet_tcp_cc_dctcp);
 451 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, dctcp,
 452     CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
 453     "dctcp congestion control related settings");
 454
 455 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, alpha,
 456     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 457     &VNET_NAME(dctcp_alpha), 0, &dctcp_alpha_handler, "IU",
 458     "dctcp alpha parameter at start of session");
 459
 460 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, shift_g,
 461     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 462     &VNET_NAME(dctcp_shift_g), 4, &dctcp_shift_g_handler, "IU",
 463     "dctcp shift parameter");
 464
 465 SYSCTL_PROC(_net_inet_tcp_cc_dctcp, OID_AUTO, slowstart,
 466     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
 467     &VNET_NAME(dctcp_slowstart), 0, &dctcp_slowstart_handler, "IU",
 468     "half CWND reduction after the first slow start");
 469
 470 DECLARE_CC_MODULE(dctcp, &dctcp_cc_algo);
 471 MODULE_VERSION(dctcp, 1);