sys/netinet/cc/cc_newreno.c

   1 /*-
   2  * Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994, 1995
   3  *      The Regents of the University of California.
   4  * Copyright (c) 2007-2008,2010
   5  *      Swinburne University of Technology, Melbourne, Australia.
   6  * Copyright (c) 2009-2010 Lawrence Stewart <lstewart@freebsd.org>
   7  * Copyright (c) 2010 The FreeBSD Foundation
   8  * All rights reserved.
   9  *
  10  * This software was developed at the Centre for Advanced Internet
  11  * Architectures, Swinburne University of Technology, by Lawrence Stewart, James
  12  * Healy and David Hayes, made possible in part by a grant from the Cisco
  13  * University Research Program Fund at Community Foundation Silicon Valley.
  14  *
  15  * Portions of this software were developed at the Centre for Advanced
  16  * Internet Architectures, Swinburne University of Technology, Melbourne,
  17  * Australia by David Hayes under sponsorship from the FreeBSD Foundation.
  18  *
  19  * Redistribution and use in source and binary forms, with or without
  20  * modification, are permitted provided that the following conditions
  21  * are met:
  22  * 1. Redistributions of source code must retain the above copyright
  23  *    notice, this list of conditions and the following disclaimer.
  24  * 2. Redistributions in binary form must reproduce the above copyright
  25  *    notice, this list of conditions and the following disclaimer in the
  26  *    documentation and/or other materials provided with the distribution.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  29  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  30  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  31  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  32  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  33  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  34  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  36  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  37  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  38  * SUCH DAMAGE.
  39  */
  40
  41 /*
  42  * This software was first released in 2007 by James Healy and Lawrence Stewart
  43  * whilst working on the NewTCP research project at Swinburne University of
  44  * Technology's Centre for Advanced Internet Architectures, Melbourne,
  45  * Australia, which was made possible in part by a grant from the Cisco
  46  * University Research Program Fund at Community Foundation Silicon Valley.
  47  * More details are available at:
  48  *   http://caia.swin.edu.au/urp/newtcp/
  49  */
  50
  51 #include <sys/cdefs.h>
  52 __FBSDID("$FreeBSD$");
  53
  54 #include <sys/param.h>
  55 #include <sys/kernel.h>
  56 #include <sys/malloc.h>
  57 #include <sys/module.h>
  58 #include <sys/socket.h>
  59 #include <sys/socketvar.h>
  60 #include <sys/sysctl.h>
  61 #include <sys/systm.h>
  62
  63 #include <net/vnet.h>
  64
  65 #include <netinet/tcp.h>
  66 #include <netinet/tcp_seq.h>
  67 #include <netinet/tcp_var.h>
  68 #include <netinet/cc/cc.h>
  69 #include <netinet/cc/cc_module.h>
  70
  71 static void     newreno_ack_received(struct cc_var *ccv, uint16_t type);
  72 static void     newreno_after_idle(struct cc_var *ccv);
  73 static void     newreno_cong_signal(struct cc_var *ccv, uint32_t type);
  74 static void     newreno_post_recovery(struct cc_var *ccv);
  75
  76 struct cc_algo newreno_cc_algo = {
  77         .name = "newreno",
  78         .ack_received = newreno_ack_received,
  79         .after_idle = newreno_after_idle,
  80         .cong_signal = newreno_cong_signal,
  81         .post_recovery = newreno_post_recovery,
  82 };
  83
  84 static void
  85 newreno_ack_received(struct cc_var *ccv, uint16_t type)
  86 {
  87         if (type == CC_ACK && !IN_RECOVERY(CCV(ccv, t_flags)) &&
  88             (ccv->flags & CCF_CWND_LIMITED)) {
  89                 u_int cw = CCV(ccv, snd_cwnd);
  90                 u_int incr = CCV(ccv, t_maxseg);
  91
  92                 /*
  93                  * Regular in-order ACK, open the congestion window.
  94                  * Method depends on which congestion control state we're
  95                  * in (slow start or cong avoid) and if ABC (RFC 3465) is
  96                  * enabled.
  97                  *
  98                  * slow start: cwnd <= ssthresh
  99                  * cong avoid: cwnd > ssthresh
 100                  *
 101                  * slow start and ABC (RFC 3465):
 102                  *   Grow cwnd exponentially by the amount of data
 103                  *   ACKed capping the max increment per ACK to
 104                  *   (abc_l_var * maxseg) bytes.
 105                  *
 106                  * slow start without ABC (RFC 5681):
 107                  *   Grow cwnd exponentially by maxseg per ACK.
 108                  *
 109                  * cong avoid and ABC (RFC 3465):
 110                  *   Grow cwnd linearly by maxseg per RTT for each
 111                  *   cwnd worth of ACKed data.
 112                  *
 113                  * cong avoid without ABC (RFC 5681):
 114                  *   Grow cwnd linearly by approximately maxseg per RTT using
 115                  *   maxseg^2 / cwnd per ACK as the increment.
 116                  *   If cwnd > maxseg^2, fix the cwnd increment at 1 byte to
 117                  *   avoid capping cwnd.
 118                  */
 119                 if (cw > CCV(ccv, snd_ssthresh)) {
 120                         if (V_tcp_do_rfc3465) {
 121                                 if (ccv->flags & CCF_ABC_SENTAWND)
 122                                         ccv->flags &= ~CCF_ABC_SENTAWND;
 123                                 else
 124                                         incr = 0;
 125                         } else
 126                                 incr = max((incr * incr / cw), 1);
 127                 } else if (V_tcp_do_rfc3465) {
 128                         /*
 129                          * In slow-start with ABC enabled and no RTO in sight?
 130                          * (Must not use abc_l_var > 1 if slow starting after
 131                          * an RTO. On RTO, snd_nxt = snd_una, so the
 132                          * snd_nxt == snd_max check is sufficient to
 133                          * handle this).
 134                          *
 135                          * XXXLAS: Find a way to signal SS after RTO that
 136                          * doesn't rely on tcpcb vars.
 137                          */
 138                         if (CCV(ccv, snd_nxt) == CCV(ccv, snd_max))
 139                                 incr = min(ccv->bytes_this_ack,
 140                                     ccv->nsegs * V_tcp_abc_l_var *
 141                                     CCV(ccv, t_maxseg));
 142                         else
 143                                 incr = min(ccv->bytes_this_ack, CCV(ccv, t_maxseg));
 144                 }
 145                 /* ABC is on by default, so incr equals 0 frequently. */
 146                 if (incr > 0)
 147                         CCV(ccv, snd_cwnd) = min(cw + incr,
 148                             TCP_MAXWIN << CCV(ccv, snd_scale));
 149         }
 150 }
 151
 152 static void
 153 newreno_after_idle(struct cc_var *ccv)
 154 {
 155         int rw;
 156
 157         /*
 158          * If we've been idle for more than one retransmit timeout the old
 159          * congestion window is no longer current and we have to reduce it to
 160          * the restart window before we can transmit again.
 161          *
 162          * The restart window is the initial window or the last CWND, whichever
 163          * is smaller.
 164          *
 165          * This is done to prevent us from flooding the path with a full CWND at
 166          * wirespeed, overloading router and switch buffers along the way.
 167          *
 168          * See RFC5681 Section 4.1. "Restarting Idle Connections".
 169          */
 170         if (V_tcp_do_rfc3390)
 171                 rw = min(4 * CCV(ccv, t_maxseg),
 172                     max(2 * CCV(ccv, t_maxseg), 4380));
 173         else
 174                 rw = CCV(ccv, t_maxseg) * 2;
 175
 176         CCV(ccv, snd_cwnd) = min(rw, CCV(ccv, snd_cwnd));
 177 }
 178
 179 /*
 180  * Perform any necessary tasks before we enter congestion recovery.
 181  */
 182 static void
 183 newreno_cong_signal(struct cc_var *ccv, uint32_t type)
 184 {
 185         uint32_t cwin, ssthresh_on_loss;
 186         u_int mss;
 187
 188         cwin = CCV(ccv, snd_cwnd);
 189         mss = CCV(ccv, t_maxseg);
 190         ssthresh_on_loss =
 191             max((CCV(ccv, snd_max) - CCV(ccv, snd_una)) / 2 / mss, 2)
 192                 * mss;
 193
 194         /* Catch algos which mistakenly leak private signal types. */
 195         KASSERT((type & CC_SIGPRIVMASK) == 0,
 196             ("%s: congestion signal type 0x%08x is private\n", __func__, type));
 197
 198         cwin = max(cwin / 2 / mss, 2) * mss;
 199
 200         switch (type) {
 201         case CC_NDUPACK:
 202                 if (!IN_FASTRECOVERY(CCV(ccv, t_flags))) {
 203                         if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 204                                 CCV(ccv, snd_ssthresh) = ssthresh_on_loss;
 205                                 CCV(ccv, snd_cwnd) = cwin;
 206                         }
 207                         ENTER_RECOVERY(CCV(ccv, t_flags));
 208                 }
 209                 break;
 210         case CC_ECN:
 211                 if (!IN_CONGRECOVERY(CCV(ccv, t_flags))) {
 212                         CCV(ccv, snd_ssthresh) = ssthresh_on_loss;
 213                         CCV(ccv, snd_cwnd) = cwin;
 214                         ENTER_CONGRECOVERY(CCV(ccv, t_flags));
 215                 }
 216                 break;
 217         case CC_RTO:
 218                 CCV(ccv, snd_ssthresh) = ssthresh_on_loss;
 219                 CCV(ccv, snd_cwnd) = mss;
 220                 break;
 221         }
 222 }
 223
 224 /*
 225  * Perform any necessary tasks before we exit congestion recovery.
 226  */
 227 static void
 228 newreno_post_recovery(struct cc_var *ccv)
 229 {
 230         int pipe;
 231         pipe = 0;
 232
 233         if (IN_FASTRECOVERY(CCV(ccv, t_flags))) {
 234                 /*
 235                  * Fast recovery will conclude after returning from this
 236                  * function. Window inflation should have left us with
 237                  * approximately snd_ssthresh outstanding data. But in case we
 238                  * would be inclined to send a burst, better to do it via the
 239                  * slow start mechanism.
 240                  *
 241                  * XXXLAS: Find a way to do this without needing curack
 242                  */
 243                 if (V_tcp_do_rfc6675_pipe)
 244                         pipe = tcp_compute_pipe(ccv->ccvc.tcp);
 245                 else
 246                         pipe = CCV(ccv, snd_max) - ccv->curack;
 247
 248                 if (pipe < CCV(ccv, snd_ssthresh))
 249                         CCV(ccv, snd_cwnd) = pipe + CCV(ccv, t_maxseg);
 250                 else
 251                         CCV(ccv, snd_cwnd) = CCV(ccv, snd_ssthresh);
 252         }
 253 }
 254
 255
 256 DECLARE_CC_MODULE(newreno, &newreno_cc_algo);