cc_vegas.c revision 274225
11541Srgrimes/*- 222521Sdyson * Copyright (c) 2009-2010 31541Srgrimes * Swinburne University of Technology, Melbourne, Australia 41541Srgrimes * Copyright (c) 2010 Lawrence Stewart <lstewart@freebsd.org> 51541Srgrimes * Copyright (c) 2010-2011 The FreeBSD Foundation 61541Srgrimes * All rights reserved. 71541Srgrimes * 81541Srgrimes * This software was developed at the Centre for Advanced Internet 91541Srgrimes * Architectures, Swinburne University of Technology, by David Hayes and 101541Srgrimes * Lawrence Stewart, made possible in part by a grant from the Cisco University 111541Srgrimes * Research Program Fund at Community Foundation Silicon Valley. 121541Srgrimes * 131541Srgrimes * Portions of this software were developed at the Centre for Advanced Internet 141541Srgrimes * Architectures, Swinburne University of Technology, Melbourne, Australia by 151541Srgrimes * David Hayes under sponsorship from the FreeBSD Foundation. 161541Srgrimes * 171541Srgrimes * Redistribution and use in source and binary forms, with or without 181541Srgrimes * modification, are permitted provided that the following conditions 191541Srgrimes * are met: 201541Srgrimes * 1. Redistributions of source code must retain the above copyright 211541Srgrimes * notice, this list of conditions and the following disclaimer. 221541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 231541Srgrimes * notice, this list of conditions and the following disclaimer in the 241541Srgrimes * documentation and/or other materials provided with the distribution. 251541Srgrimes * 261541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 271541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 281541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 291541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 301541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 311541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 321541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 331541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 341541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 351541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3622521Sdyson * SUCH DAMAGE. 3750477Speter */ 381541Srgrimes 391541Srgrimes/* 402175Spaul * An implementation of the Vegas congestion control algorithm for FreeBSD, 412175Spaul * based on L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion 422175Spaul * avoidance on a global internet", IEEE J. Sel. Areas Commun., vol. 13, no. 8, 4337291Sjmg * pp. 1465-1480, Oct. 1995. The original Vegas duplicate ack policy has not 4437272Sjmg * been implemented, since clock ticks are not as coarse as they were (i.e. 4537291Sjmg * 500ms) when Vegas was designed. Also, packets are timed once per RTT as in 4637272Sjmg * the original paper. 471541Srgrimes * 481541Srgrimes * Originally released as part of the NewTCP research project at Swinburne 491541Srgrimes * University of Technology's Centre for Advanced Internet Architectures, 501541Srgrimes * Melbourne, Australia, which was made possible in part by a grant from the 511541Srgrimes * Cisco University Research Program Fund at Community Foundation Silicon 529336Sdfr * Valley. More details are available at: 539336Sdfr * http://caia.swin.edu.au/urp/newtcp/ 549336Sdfr */ 559336Sdfr 569336Sdfr#include <sys/cdefs.h> 579336Sdfr__FBSDID("$FreeBSD: head/sys/netinet/cc/cc_vegas.c 274225 2014-11-07 09:39:05Z glebius $"); 581541Srgrimes 591541Srgrimes#include <sys/param.h> 601541Srgrimes#include <sys/kernel.h> 611541Srgrimes#include <sys/khelp.h> 621828Sdg#include <sys/malloc.h> 6336176Speter#include <sys/module.h> 641828Sdg#include <sys/queue.h> 651828Sdg#include <sys/socket.h> 661541Srgrimes#include <sys/socketvar.h> 671828Sdg#include <sys/sysctl.h> 6836176Speter#include <sys/systm.h> 6936176Speter 7036176Speter#include <net/if.h> 7136176Speter#include <net/vnet.h> 7236176Speter 7336176Speter#include <netinet/cc.h> 741541Srgrimes#include <netinet/tcp_seq.h> 751541Srgrimes#include <netinet/tcp_timer.h> 769336Sdfr#include <netinet/tcp_var.h> 771541Srgrimes 781541Srgrimes#include <netinet/cc/cc_module.h> 791541Srgrimes 8024378Sbde#include <netinet/khelp/h_ertt.h> 819336Sdfr 829336Sdfr#define CAST_PTR_INT(X) (*((int*)(X))) 839336Sdfr 849336Sdfr/* 859336Sdfr * Private signal type for rate based congestion signal. 8624378Sbde * See <netinet/cc.h> for appropriate bit-range to use for private signals. 8724378Sbde */ 8824378Sbde#define CC_VEGAS_RATE 0x01000000 899336Sdfr 909336Sdfrstatic void vegas_ack_received(struct cc_var *ccv, uint16_t ack_type); 919336Sdfrstatic void vegas_cb_destroy(struct cc_var *ccv); 929336Sdfrstatic int vegas_cb_init(struct cc_var *ccv); 931541Srgrimesstatic void vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type); 949336Sdfrstatic void vegas_conn_init(struct cc_var *ccv); 959336Sdfrstatic int vegas_mod_init(void); 969336Sdfr 979336Sdfrstruct vegas { 989336Sdfr int slow_start_toggle; 999336Sdfr}; 1001541Srgrimes 1011541Srgrimesstatic int32_t ertt_id; 1029336Sdfr 1039336Sdfrstatic VNET_DEFINE(uint32_t, vegas_alpha) = 1; 1049336Sdfrstatic VNET_DEFINE(uint32_t, vegas_beta) = 3; 1059336Sdfr#define V_vegas_alpha VNET(vegas_alpha) 1069336Sdfr#define V_vegas_beta VNET(vegas_beta) 1079336Sdfr 1089336Sdfrstatic MALLOC_DEFINE(M_VEGAS, "vegas data", 1099336Sdfr "Per connection data required for the Vegas congestion control algorithm"); 1109336Sdfr 1119336Sdfrstruct cc_algo vegas_cc_algo = { 1129336Sdfr .name = "vegas", 1139336Sdfr .ack_received = vegas_ack_received, 1149336Sdfr .cb_destroy = vegas_cb_destroy, 1159336Sdfr .cb_init = vegas_cb_init, 1169336Sdfr .cong_signal = vegas_cong_signal, 1179336Sdfr .conn_init = vegas_conn_init, 1189336Sdfr .mod_init = vegas_mod_init 1199336Sdfr}; 1209336Sdfr 1219336Sdfr/* 1229336Sdfr * The vegas window adjustment is done once every RTT, as indicated by the 1239336Sdfr * ERTT_NEW_MEASUREMENT flag. This flag is reset once the new measurment data 1249336Sdfr * has been used. 1259336Sdfr */ 1269336Sdfrstatic void 1279336Sdfrvegas_ack_received(struct cc_var *ccv, uint16_t ack_type) 1289336Sdfr{ 12922521Sdyson struct ertt *e_t; 13022521Sdyson struct vegas *vegas_data; 13122521Sdyson long actual_tx_rate, expected_tx_rate, ndiff; 13222521Sdyson 13322521Sdyson e_t = khelp_get_osd(CCV(ccv, osd), ertt_id); 13422521Sdyson vegas_data = ccv->cc_data; 13522521Sdyson 13622521Sdyson if (e_t->flags & ERTT_NEW_MEASUREMENT) { /* Once per RTT. */ 13722521Sdyson if (e_t->minrtt && e_t->markedpkt_rtt) { 13822521Sdyson expected_tx_rate = e_t->marked_snd_cwnd / e_t->minrtt; 13922521Sdyson actual_tx_rate = e_t->bytes_tx_in_marked_rtt / 14022521Sdyson e_t->markedpkt_rtt; 14122521Sdyson ndiff = (expected_tx_rate - actual_tx_rate) * 14222521Sdyson e_t->minrtt / CCV(ccv, t_maxseg); 14322521Sdyson 14422521Sdyson if (ndiff < V_vegas_alpha) { 14522521Sdyson if (CCV(ccv, snd_cwnd) <= 14622521Sdyson CCV(ccv, snd_ssthresh)) { 14722521Sdyson vegas_data->slow_start_toggle = 14822521Sdyson vegas_data->slow_start_toggle ? 14922521Sdyson 0 : 1; 15022521Sdyson } else { 15136176Speter vegas_data->slow_start_toggle = 0; 15236176Speter CCV(ccv, snd_cwnd) = 15336176Speter min(CCV(ccv, snd_cwnd) + 15436176Speter CCV(ccv, t_maxseg), 15522521Sdyson TCP_MAXWIN << CCV(ccv, snd_scale)); 15622521Sdyson } 15722521Sdyson } else if (ndiff > V_vegas_beta) { 15822521Sdyson /* Rate-based congestion. */ 15922521Sdyson vegas_cong_signal(ccv, CC_VEGAS_RATE); 16022521Sdyson vegas_data->slow_start_toggle = 0; 16122521Sdyson } 16222521Sdyson } 16322521Sdyson e_t->flags &= ~ERTT_NEW_MEASUREMENT; 16422521Sdyson } 16522521Sdyson 16622521Sdyson if (vegas_data->slow_start_toggle) 16722521Sdyson newreno_cc_algo.ack_received(ccv, ack_type); 16822521Sdyson} 16922521Sdyson 17022521Sdysonstatic void 17122521Sdysonvegas_cb_destroy(struct cc_var *ccv) 17222521Sdyson{ 17322521Sdyson 17422521Sdyson if (ccv->cc_data != NULL) 17522521Sdyson free(ccv->cc_data, M_VEGAS); 17622521Sdyson} 17722521Sdyson 17836176Speterstatic int 17936176Spetervegas_cb_init(struct cc_var *ccv) 18036176Speter{ 18136176Speter struct vegas *vegas_data; 18222521Sdyson 18336176Speter vegas_data = malloc(sizeof(struct vegas), M_VEGAS, M_NOWAIT); 18436176Speter 18536176Speter if (vegas_data == NULL) 18636176Speter return (ENOMEM); 18736176Speter 18836176Speter vegas_data->slow_start_toggle = 1; 18936176Speter ccv->cc_data = vegas_data; 19036176Speter 19136176Speter return (0); 19236176Speter} 19336176Speter 19436176Speter/* 19536176Speter * If congestion has been triggered triggered by the Vegas measured rates, it is 19636176Speter * handled here, otherwise it falls back to newreno's congestion handling. 19736176Speter */ 19822521Sdysonstatic void 1991541Srgrimesvegas_cong_signal(struct cc_var *ccv, uint32_t signal_type) 2001541Srgrimes{ 2011541Srgrimes struct vegas *vegas_data; 2021541Srgrimes int presignalrecov; 2031541Srgrimes 20422521Sdyson vegas_data = ccv->cc_data; 2051541Srgrimes 2061541Srgrimes if (IN_RECOVERY(CCV(ccv, t_flags))) 2071541Srgrimes presignalrecov = 1; 2081541Srgrimes else 2091541Srgrimes presignalrecov = 0; 2101541Srgrimes 21136541Speter switch(signal_type) { 2121541Srgrimes case CC_VEGAS_RATE: 2131541Srgrimes if (!IN_RECOVERY(CCV(ccv, t_flags))) { 2149336Sdfr CCV(ccv, snd_cwnd) = max(2 * CCV(ccv, t_maxseg), 2159336Sdfr CCV(ccv, snd_cwnd) - CCV(ccv, t_maxseg)); 2169336Sdfr if (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) 2179336Sdfr /* Exit slow start. */ 21836541Speter CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd); 2199336Sdfr } 2201541Srgrimes break; 2211541Srgrimes 2221541Srgrimes default: 2231541Srgrimes newreno_cc_algo.cong_signal(ccv, signal_type); 2241541Srgrimes } 2251541Srgrimes 2261541Srgrimes if (IN_RECOVERY(CCV(ccv, t_flags)) && !presignalrecov) 2279336Sdfr vegas_data->slow_start_toggle = 2289336Sdfr (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) ? 1 : 0; 2299336Sdfr} 2309336Sdfr 2311541Srgrimesstatic void 2321541Srgrimesvegas_conn_init(struct cc_var *ccv) 2331541Srgrimes{ 23422521Sdyson struct vegas *vegas_data; 23522521Sdyson 23622521Sdyson vegas_data = ccv->cc_data; 23722521Sdyson vegas_data->slow_start_toggle = 1; 2381541Srgrimes} 2391541Srgrimes 2401541Srgrimesstatic int 2411541Srgrimesvegas_mod_init(void) 2421541Srgrimes{ 2431541Srgrimes 2441541Srgrimes ertt_id = khelp_get_id("ertt"); 2451541Srgrimes if (ertt_id <= 0) { 2461541Srgrimes printf("%s: h_ertt module not found\n", __func__); 2471541Srgrimes return (ENOENT); 2481541Srgrimes } 2491541Srgrimes 2501541Srgrimes vegas_cc_algo.after_idle = newreno_cc_algo.after_idle; 2511541Srgrimes vegas_cc_algo.post_recovery = newreno_cc_algo.post_recovery; 2521541Srgrimes 2531541Srgrimes return (0); 2541541Srgrimes} 2551541Srgrimes 2561541Srgrimesstatic int 2571541Srgrimesvegas_alpha_handler(SYSCTL_HANDLER_ARGS) 2581541Srgrimes{ 2591541Srgrimes int error; 2601541Srgrimes uint32_t new; 2611541Srgrimes 2621541Srgrimes new = V_vegas_alpha; 2631541Srgrimes error = sysctl_handle_int(oidp, &new, 0, req); 2641541Srgrimes if (error == 0 && req->newptr != NULL) { 2651541Srgrimes if (CAST_PTR_INT(req->newptr) < 1 || 2661541Srgrimes CAST_PTR_INT(req->newptr) > V_vegas_beta) 2671541Srgrimes error = EINVAL; 2681541Srgrimes else 2691541Srgrimes V_vegas_alpha = new; 2701541Srgrimes } 2711541Srgrimes 2721541Srgrimes return (error); 2739336Sdfr} 2741541Srgrimes 27522521Sdysonstatic int 2761541Srgrimesvegas_beta_handler(SYSCTL_HANDLER_ARGS) 2771541Srgrimes{ 2781541Srgrimes int error; 2791541Srgrimes uint32_t new; 2801541Srgrimes 2811541Srgrimes new = V_vegas_beta; 2821541Srgrimes error = sysctl_handle_int(oidp, &new, 0, req); 2831541Srgrimes if (error == 0 && req->newptr != NULL) { 2841541Srgrimes if (CAST_PTR_INT(req->newptr) < 1 || 2851541Srgrimes CAST_PTR_INT(req->newptr) < V_vegas_alpha) 2861541Srgrimes error = EINVAL; 2871541Srgrimes else 2881541Srgrimes V_vegas_beta = new; 2893820Swollman } 2903820Swollman 2913820Swollman return (error); 29224330Sguido} 2933820Swollman 2943820SwollmanSYSCTL_DECL(_net_inet_tcp_cc_vegas); 2953820SwollmanSYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, vegas, CTLFLAG_RW, NULL, 2963820Swollman "Vegas related settings"); 29724330Sguido 2983820SwollmanSYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, alpha, 2993820Swollman CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 30022521Sdyson &VNET_NAME(vegas_alpha), 1, &vegas_alpha_handler, "IU", 3014067Swollman "vegas alpha, specified as number of \"buffers\" (0 < alpha < beta)"); 30230354Sphk 30330354SphkSYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, beta, 30430354Sphk CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 30530354Sphk &VNET_NAME(vegas_beta), 3, &vegas_beta_handler, "IU", 30630354Sphk "vegas beta, specified as number of \"buffers\" (0 < alpha < beta)"); 30730354Sphk 30830354SphkDECLARE_CC_MODULE(vegas, &vegas_cc_algo); 30930354SphkMODULE_DEPEND(vegas, ertt, 1, 1, 1); 31036329Speter