cc_vegas.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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 Lawrence Stewart <lstewart@freebsd.org>
    7  * Copyright (c) 2010-2011 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 David Hayes and
   12  * Lawrence Stewart, made possible in part by a grant from the Cisco University
   13  * Research Program Fund at Community Foundation Silicon Valley.
   14  *
   15  * Portions of this software were developed at the Centre for Advanced Internet
   16  * Architectures, Swinburne University of Technology, Melbourne, Australia by
   17  * 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  * An implementation of the Vegas congestion control algorithm for FreeBSD,
   43  * based on L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion
   44  * avoidance on a global internet", IEEE J. Sel. Areas Commun., vol. 13, no. 8,
   45  * pp. 1465-1480, Oct. 1995. The original Vegas duplicate ack policy has not
   46  * been implemented, since clock ticks are not as coarse as they were (i.e.
   47  * 500ms) when Vegas was designed. Also, packets are timed once per RTT as in
   48  * the original paper.
   49  *
   50  * Originally released as part of the NewTCP research project at Swinburne
   51  * University of Technology's Centre for Advanced Internet Architectures,
   52  * Melbourne, Australia, which was made possible in part by a grant from the
   53  * Cisco University Research Program Fund at Community Foundation Silicon
   54  * Valley. More details are available at:
   55  *   http://caia.swin.edu.au/urp/newtcp/
   56  */
   57 
   58 #include <sys/cdefs.h>
   59 __FBSDID("$FreeBSD$");
   60 
   61 #include <sys/param.h>
   62 #include <sys/kernel.h>
   63 #include <sys/khelp.h>
   64 #include <sys/malloc.h>
   65 #include <sys/module.h>
   66 #include <sys/queue.h>
   67 #include <sys/socket.h>
   68 #include <sys/socketvar.h>
   69 #include <sys/sysctl.h>
   70 #include <sys/systm.h>
   71 
   72 #include <net/vnet.h>
   73 
   74 #include <net/route.h>
   75 #include <net/route/nhop.h>
   76 
   77 #include <netinet/in_pcb.h>
   78 #include <netinet/tcp.h>
   79 #include <netinet/tcp_timer.h>
   80 #include <netinet/tcp_var.h>
   81 #include <netinet/cc/cc.h>
   82 #include <netinet/cc/cc_module.h>
   83 
   84 #include <netinet/khelp/h_ertt.h>
   85 
   86 /*
   87  * Private signal type for rate based congestion signal.
   88  * See <netinet/cc.h> for appropriate bit-range to use for private signals.
   89  */
   90 #define CC_VEGAS_RATE   0x01000000
   91 
   92 static void     vegas_ack_received(struct cc_var *ccv, uint16_t ack_type);
   93 static void     vegas_cb_destroy(struct cc_var *ccv);
   94 static int      vegas_cb_init(struct cc_var *ccv, void *ptr);
   95 static void     vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type);
   96 static void     vegas_conn_init(struct cc_var *ccv);
   97 static int      vegas_mod_init(void);
   98 static size_t   vegas_data_sz(void);
   99 
  100 struct vegas {
  101         int slow_start_toggle;
  102 };
  103 
  104 static int32_t ertt_id;
  105 
  106 VNET_DEFINE_STATIC(uint32_t, vegas_alpha) = 1;
  107 VNET_DEFINE_STATIC(uint32_t, vegas_beta) = 3;
  108 #define V_vegas_alpha   VNET(vegas_alpha)
  109 #define V_vegas_beta    VNET(vegas_beta)
  110 
  111 struct cc_algo vegas_cc_algo = {
  112         .name = "vegas",
  113         .ack_received = vegas_ack_received,
  114         .cb_destroy = vegas_cb_destroy,
  115         .cb_init = vegas_cb_init,
  116         .cong_signal = vegas_cong_signal,
  117         .conn_init = vegas_conn_init,
  118         .mod_init = vegas_mod_init,
  119         .cc_data_sz = vegas_data_sz,
  120         .after_idle = newreno_cc_after_idle,
  121         .post_recovery = newreno_cc_post_recovery,
  122 };
  123 
  124 /*
  125  * The vegas window adjustment is done once every RTT, as indicated by the
  126  * ERTT_NEW_MEASUREMENT flag. This flag is reset once the new measurement data
  127  * has been used.
  128  */
  129 static void
  130 vegas_ack_received(struct cc_var *ccv, uint16_t ack_type)
  131 {
  132         struct ertt *e_t;
  133         struct vegas *vegas_data;
  134         long actual_tx_rate, expected_tx_rate, ndiff;
  135 
  136         e_t = khelp_get_osd(&CCV(ccv, t_osd), ertt_id);
  137         vegas_data = ccv->cc_data;
  138 
  139         if (e_t->flags & ERTT_NEW_MEASUREMENT) { /* Once per RTT. */
  140                 if (e_t->minrtt && e_t->markedpkt_rtt) {
  141                         expected_tx_rate = e_t->marked_snd_cwnd / e_t->minrtt;
  142                         actual_tx_rate = e_t->bytes_tx_in_marked_rtt /
  143                             e_t->markedpkt_rtt;
  144                         ndiff = (expected_tx_rate - actual_tx_rate) *
  145                             e_t->minrtt / CCV(ccv, t_maxseg);
  146 
  147                         if (ndiff < V_vegas_alpha) {
  148                                 if (CCV(ccv, snd_cwnd) <=
  149                                     CCV(ccv, snd_ssthresh)) {
  150                                         vegas_data->slow_start_toggle =
  151                                             vegas_data->slow_start_toggle ?
  152                                             0 : 1;
  153                                 } else {
  154                                         vegas_data->slow_start_toggle = 0;
  155                                         CCV(ccv, snd_cwnd) =
  156                                             min(CCV(ccv, snd_cwnd) +
  157                                             CCV(ccv, t_maxseg),
  158                                             TCP_MAXWIN << CCV(ccv, snd_scale));
  159                                 }
  160                         } else if (ndiff > V_vegas_beta) {
  161                                 /* Rate-based congestion. */
  162                                 vegas_cong_signal(ccv, CC_VEGAS_RATE);
  163                                 vegas_data->slow_start_toggle = 0;
  164                         }
  165                 }
  166                 e_t->flags &= ~ERTT_NEW_MEASUREMENT;
  167         }
  168 
  169         if (vegas_data->slow_start_toggle)
  170                 newreno_cc_ack_received(ccv, ack_type);
  171 }
  172 
  173 static void
  174 vegas_cb_destroy(struct cc_var *ccv)
  175 {
  176         free(ccv->cc_data, M_CC_MEM);
  177 }
  178 
  179 static size_t
  180 vegas_data_sz(void)
  181 {
  182         return (sizeof(struct vegas));
  183 }
  184 
  185 static int
  186 vegas_cb_init(struct cc_var *ccv, void *ptr)
  187 {
  188         struct vegas *vegas_data;
  189 
  190         INP_WLOCK_ASSERT(tptoinpcb(ccv->ccvc.tcp));
  191         if (ptr == NULL) {
  192                 vegas_data = malloc(sizeof(struct vegas), M_CC_MEM, M_NOWAIT);
  193                 if (vegas_data == NULL)
  194                         return (ENOMEM);
  195         } else
  196                 vegas_data = ptr;
  197 
  198         vegas_data->slow_start_toggle = 1;
  199         ccv->cc_data = vegas_data;
  200 
  201         return (0);
  202 }
  203 
  204 /*
  205  * If congestion has been triggered triggered by the Vegas measured rates, it is
  206  * handled here, otherwise it falls back to newreno's congestion handling.
  207  */
  208 static void
  209 vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type)
  210 {
  211         struct vegas *vegas_data;
  212         int presignalrecov;
  213 
  214         vegas_data = ccv->cc_data;
  215 
  216         if (IN_RECOVERY(CCV(ccv, t_flags)))
  217                 presignalrecov = 1;
  218         else
  219                 presignalrecov = 0;
  220 
  221         switch(signal_type) {
  222         case CC_VEGAS_RATE:
  223                 if (!IN_RECOVERY(CCV(ccv, t_flags))) {
  224                         CCV(ccv, snd_cwnd) = max(2 * CCV(ccv, t_maxseg),
  225                             CCV(ccv, snd_cwnd) - CCV(ccv, t_maxseg));
  226                         if (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh))
  227                                 /* Exit slow start. */
  228                                 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd);
  229                 }
  230                 break;
  231 
  232         default:
  233                 newreno_cc_cong_signal(ccv, signal_type);
  234         }
  235 
  236         if (IN_RECOVERY(CCV(ccv, t_flags)) && !presignalrecov)
  237                 vegas_data->slow_start_toggle =
  238                     (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) ? 1 : 0;
  239 }
  240 
  241 static void
  242 vegas_conn_init(struct cc_var *ccv)
  243 {
  244         struct vegas *vegas_data;
  245 
  246         vegas_data = ccv->cc_data;
  247         vegas_data->slow_start_toggle = 1;
  248 }
  249 
  250 static int
  251 vegas_mod_init(void)
  252 {
  253         ertt_id = khelp_get_id("ertt");
  254         if (ertt_id <= 0) {
  255                 printf("%s: h_ertt module not found\n", __func__);
  256                 return (ENOENT);
  257         }
  258         return (0);
  259 }
  260 
  261 static int
  262 vegas_alpha_handler(SYSCTL_HANDLER_ARGS)
  263 {
  264         int error;
  265         uint32_t new;
  266 
  267         new = V_vegas_alpha;
  268         error = sysctl_handle_int(oidp, &new, 0, req);
  269         if (error == 0 && req->newptr != NULL) {
  270                 if (new == 0 || new > V_vegas_beta)
  271                         error = EINVAL;
  272                 else
  273                         V_vegas_alpha = new;
  274         }
  275 
  276         return (error);
  277 }
  278 
  279 static int
  280 vegas_beta_handler(SYSCTL_HANDLER_ARGS)
  281 {
  282         int error;
  283         uint32_t new;
  284 
  285         new = V_vegas_beta;
  286         error = sysctl_handle_int(oidp, &new, 0, req);
  287         if (error == 0 && req->newptr != NULL) {
  288                 if (new == 0 || new < V_vegas_alpha)
  289                          error = EINVAL;
  290                 else
  291                         V_vegas_beta = new;
  292         }
  293 
  294         return (error);
  295 }
  296 
  297 SYSCTL_DECL(_net_inet_tcp_cc_vegas);
  298 SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, vegas,
  299     CTLFLAG_RW | CTLFLAG_MPSAFE, NULL,
  300     "Vegas related settings");
  301 
  302 SYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, alpha,
  303     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
  304     &VNET_NAME(vegas_alpha), 1, &vegas_alpha_handler, "IU",
  305     "vegas alpha, specified as number of \"buffers\" (0 < alpha < beta)");
  306 
  307 SYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, beta,
  308     CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
  309     &VNET_NAME(vegas_beta), 3, &vegas_beta_handler, "IU",
  310     "vegas beta, specified as number of \"buffers\" (0 < alpha < beta)");
  311 
  312 DECLARE_CC_MODULE(vegas, &vegas_cc_algo);
  313 MODULE_VERSION(vegas, 2);
  314 MODULE_DEPEND(vegas, ertt, 1, 1, 1);
Cache object: e50143a7d30a0bd16fcd4194d5b76288
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/netinet/cc/cc_vegas.c

FreeBSD/Linux Kernel Cross Reference
sys/netinet/cc/cc_vegas.c
