145095Ssos/*- 255333Ssos * Copyright (c) 2009-2010 345095Ssos * Swinburne University of Technology, Melbourne, Australia 445095Ssos * Copyright (c) 2010 Lawrence Stewart <lstewart@freebsd.org> 545095Ssos * Copyright (c) 2010-2011 The FreeBSD Foundation 645095Ssos * All rights reserved. 745095Ssos * 845095Ssos * This software was developed at the Centre for Advanced Internet 945095Ssos * Architectures, Swinburne University of Technology, by David Hayes and 1045095Ssos * Lawrence Stewart, made possible in part by a grant from the Cisco University 1145095Ssos * Research Program Fund at Community Foundation Silicon Valley. 1245095Ssos * 1345095Ssos * Portions of this software were developed at the Centre for Advanced Internet 1445095Ssos * Architectures, Swinburne University of Technology, Melbourne, Australia by 1545095Ssos * David Hayes under sponsorship from the FreeBSD Foundation. 1645095Ssos * 1745095Ssos * Redistribution and use in source and binary forms, with or without 1845095Ssos * modification, are permitted provided that the following conditions 1945095Ssos * are met: 2045095Ssos * 1. Redistributions of source code must retain the above copyright 2145095Ssos * notice, this list of conditions and the following disclaimer. 2245095Ssos * 2. Redistributions in binary form must reproduce the above copyright 2345095Ssos * notice, this list of conditions and the following disclaimer in the 2445095Ssos * documentation and/or other materials provided with the distribution. 2545095Ssos * 2645095Ssos * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 2745095Ssos * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2850477Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2945095Ssos * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 3045095Ssos * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 3145150Ssos * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 3251520Ssos * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3345095Ssos * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3445095Ssos * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3545095Ssos * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3645095Ssos * SUCH DAMAGE. 3745798Ssos */ 3854270Ssos 3954270Ssos/* 4051520Ssos * An implementation of the Vegas congestion control algorithm for FreeBSD, 4145095Ssos * based on L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion 4247272Ssos * avoidance on a global internet", IEEE J. Sel. Areas Commun., vol. 13, no. 8, 4345095Ssos * pp. 1465-1480, Oct. 1995. The original Vegas duplicate ack policy has not 4447272Ssos * been implemented, since clock ticks are not as coarse as they were (i.e. 4551520Ssos * 500ms) when Vegas was designed. Also, packets are timed once per RTT as in 4651520Ssos * the original paper. 4751520Ssos * 4845095Ssos * Originally released as part of the NewTCP research project at Swinburne 4954270Ssos * University of Technology's Centre for Advanced Internet Architectures, 5045095Ssos * Melbourne, Australia, which was made possible in part by a grant from the 5152067Ssos * Cisco University Research Program Fund at Community Foundation Silicon 5255333Ssos * Valley. More details are available at: 5352067Ssos * http://caia.swin.edu.au/urp/newtcp/ 5452067Ssos */ 5552067Ssos 5645720Speter#include <sys/cdefs.h> 5745720Speter__FBSDID("$FreeBSD: releng/11.0/sys/netinet/cc/cc_vegas.c 294931 2016-01-27 17:59:39Z glebius $"); 5851520Ssos 5945720Speter#include <sys/param.h> 6045720Speter#include <sys/kernel.h> 6145150Ssos#include <sys/khelp.h> 6245150Ssos#include <sys/malloc.h> 6345095Ssos#include <sys/module.h> 6445095Ssos#include <sys/queue.h> 6545095Ssos#include <sys/socket.h> 6645095Ssos#include <sys/socketvar.h> 6756558Ssos#include <sys/sysctl.h> 6855333Ssos#include <sys/systm.h> 6945095Ssos 7045095Ssos#include <net/vnet.h> 7145095Ssos 7245095Ssos#include <netinet/tcp.h> 7352067Ssos#include <netinet/tcp_timer.h> 7452067Ssos#include <netinet/tcp_var.h> 7552067Ssos#include <netinet/cc/cc.h> 7652067Ssos#include <netinet/cc/cc_module.h> 7752067Ssos 7856558Ssos#include <netinet/khelp/h_ertt.h> 7952067Ssos 8052067Ssos#define CAST_PTR_INT(X) (*((int*)(X))) 8152067Ssos 8252067Ssos/* 8356558Ssos * Private signal type for rate based congestion signal. 8456558Ssos * See <netinet/cc.h> for appropriate bit-range to use for private signals. 8545095Ssos */ 8656558Ssos#define CC_VEGAS_RATE 0x01000000 8756558Ssos 8856558Ssosstatic void vegas_ack_received(struct cc_var *ccv, uint16_t ack_type); 8956558Ssosstatic void vegas_cb_destroy(struct cc_var *ccv); 9056558Ssosstatic int vegas_cb_init(struct cc_var *ccv); 9156558Ssosstatic void vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type); 9256558Ssosstatic void vegas_conn_init(struct cc_var *ccv); 9356558Ssosstatic int vegas_mod_init(void); 9456558Ssos 9545095Ssosstruct vegas { 9645095Ssos int slow_start_toggle; 9755333Ssos}; 9845095Ssos 9945095Ssosstatic int32_t ertt_id; 10056138Ssos 10156138Ssosstatic VNET_DEFINE(uint32_t, vegas_alpha) = 1; 10256138Ssosstatic VNET_DEFINE(uint32_t, vegas_beta) = 3; 10345095Ssos#define V_vegas_alpha VNET(vegas_alpha) 10451520Ssos#define V_vegas_beta VNET(vegas_beta) 10545095Ssos 10645095Ssosstatic MALLOC_DEFINE(M_VEGAS, "vegas data", 10753029Ssos "Per connection data required for the Vegas congestion control algorithm"); 10851520Ssos 10956558Ssosstruct cc_algo vegas_cc_algo = { 11056558Ssos .name = "vegas", 11156558Ssos .ack_received = vegas_ack_received, 11256558Ssos .cb_destroy = vegas_cb_destroy, 11353681Ssos .cb_init = vegas_cb_init, 11453681Ssos .cong_signal = vegas_cong_signal, 11553681Ssos .conn_init = vegas_conn_init, 11653681Ssos .mod_init = vegas_mod_init 11753681Ssos}; 11853681Ssos 11956558Ssos/* 12053681Ssos * The vegas window adjustment is done once every RTT, as indicated by the 12153681Ssos * ERTT_NEW_MEASUREMENT flag. This flag is reset once the new measurment data 12245095Ssos * has been used. 12345095Ssos */ 12445095Ssosstatic void 12545095Ssosvegas_ack_received(struct cc_var *ccv, uint16_t ack_type) 12645095Ssos{ 12745095Ssos struct ertt *e_t; 12845095Ssos struct vegas *vegas_data; 12945095Ssos long actual_tx_rate, expected_tx_rate, ndiff; 13045798Ssos 13151520Ssos e_t = khelp_get_osd(CCV(ccv, osd), ertt_id); 13251520Ssos vegas_data = ccv->cc_data; 13351520Ssos 13451520Ssos if (e_t->flags & ERTT_NEW_MEASUREMENT) { /* Once per RTT. */ 13551520Ssos if (e_t->minrtt && e_t->markedpkt_rtt) { 13651520Ssos expected_tx_rate = e_t->marked_snd_cwnd / e_t->minrtt; 13751520Ssos actual_tx_rate = e_t->bytes_tx_in_marked_rtt / 13851520Ssos e_t->markedpkt_rtt; 13951520Ssos ndiff = (expected_tx_rate - actual_tx_rate) * 14051520Ssos e_t->minrtt / CCV(ccv, t_maxseg); 14151520Ssos 14251520Ssos if (ndiff < V_vegas_alpha) { 14351520Ssos if (CCV(ccv, snd_cwnd) <= 14445095Ssos CCV(ccv, snd_ssthresh)) { 14545095Ssos vegas_data->slow_start_toggle = 14653029Ssos vegas_data->slow_start_toggle ? 14751520Ssos 0 : 1; 14856558Ssos } else { 14956558Ssos vegas_data->slow_start_toggle = 0; 15056558Ssos CCV(ccv, snd_cwnd) = 15156558Ssos min(CCV(ccv, snd_cwnd) + 15256558Ssos CCV(ccv, t_maxseg), 15353681Ssos TCP_MAXWIN << CCV(ccv, snd_scale)); 15453681Ssos } 15553681Ssos } else if (ndiff > V_vegas_beta) { 15653681Ssos /* Rate-based congestion. */ 15753681Ssos vegas_cong_signal(ccv, CC_VEGAS_RATE); 15853681Ssos vegas_data->slow_start_toggle = 0; 15953681Ssos } 16053681Ssos } 16153681Ssos e_t->flags &= ~ERTT_NEW_MEASUREMENT; 16253681Ssos } 16353681Ssos 16453681Ssos if (vegas_data->slow_start_toggle) 16553681Ssos newreno_cc_algo.ack_received(ccv, ack_type); 16653681Ssos} 16753681Ssos 16853681Ssosstatic void 16953681Ssosvegas_cb_destroy(struct cc_var *ccv) 17053681Ssos{ 17153681Ssos 17253681Ssos if (ccv->cc_data != NULL) 17353681Ssos free(ccv->cc_data, M_VEGAS); 17453681Ssos} 17553681Ssos 17653681Ssosstatic int 17753681Ssosvegas_cb_init(struct cc_var *ccv) 17856558Ssos{ 17953681Ssos struct vegas *vegas_data; 18045095Ssos 18151520Ssos vegas_data = malloc(sizeof(struct vegas), M_VEGAS, M_NOWAIT); 18253681Ssos 18345095Ssos if (vegas_data == NULL) 18445095Ssos return (ENOMEM); 18545095Ssos 18654544Ssos vegas_data->slow_start_toggle = 1; 18754544Ssos ccv->cc_data = vegas_data; 18854544Ssos 18954544Ssos return (0); 19054544Ssos} 19154544Ssos 19254544Ssos/* 19354544Ssos * If congestion has been triggered triggered by the Vegas measured rates, it is 19454544Ssos * handled here, otherwise it falls back to newreno's congestion handling. 19554544Ssos */ 19654544Ssosstatic void 19754544Ssosvegas_cong_signal(struct cc_var *ccv, uint32_t signal_type) 19854544Ssos{ 19954544Ssos struct vegas *vegas_data; 20056558Ssos int presignalrecov; 20156558Ssos 20256558Ssos vegas_data = ccv->cc_data; 20354544Ssos 20456558Ssos if (IN_RECOVERY(CCV(ccv, t_flags))) 20554544Ssos presignalrecov = 1; 20654544Ssos else 20754544Ssos presignalrecov = 0; 20845095Ssos 20945095Ssos switch(signal_type) { 21052067Ssos case CC_VEGAS_RATE: 21153029Ssos if (!IN_RECOVERY(CCV(ccv, t_flags))) { 21253029Ssos CCV(ccv, snd_cwnd) = max(2 * CCV(ccv, t_maxseg), 21356558Ssos CCV(ccv, snd_cwnd) - CCV(ccv, t_maxseg)); 21456558Ssos if (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) 21553029Ssos /* Exit slow start. */ 21652067Ssos CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd); 21753681Ssos } 21852067Ssos break; 21952067Ssos 22051520Ssos default: 22153029Ssos newreno_cc_algo.cong_signal(ccv, signal_type); 22251520Ssos } 22356558Ssos 22456558Ssos if (IN_RECOVERY(CCV(ccv, t_flags)) && !presignalrecov) 22556558Ssos vegas_data->slow_start_toggle = 22653681Ssos (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) ? 1 : 0; 22753681Ssos} 22853681Ssos 22953681Ssosstatic void 23053681Ssosvegas_conn_init(struct cc_var *ccv) 23153681Ssos{ 23253681Ssos struct vegas *vegas_data; 23356558Ssos 23453681Ssos vegas_data = ccv->cc_data; 23553681Ssos vegas_data->slow_start_toggle = 1; 23651520Ssos} 23753681Ssos 23852067Ssosstatic int 23953029Ssosvegas_mod_init(void) 24052067Ssos{ 24156558Ssos 24256558Ssos ertt_id = khelp_get_id("ertt"); 24356558Ssos if (ertt_id <= 0) { 24453681Ssos printf("%s: h_ertt module not found\n", __func__); 24553681Ssos return (ENOENT); 24653681Ssos } 24753681Ssos 24856558Ssos vegas_cc_algo.after_idle = newreno_cc_algo.after_idle; 24953681Ssos vegas_cc_algo.post_recovery = newreno_cc_algo.post_recovery; 25053681Ssos 25152067Ssos return (0); 25253681Ssos} 25352067Ssos 25452067Ssosstatic int 25555333Ssosvegas_alpha_handler(SYSCTL_HANDLER_ARGS) 25654969Ssos{ 25756138Ssos int error; 25856138Ssos uint32_t new; 25956138Ssos 26056138Ssos new = V_vegas_alpha; 26156138Ssos error = sysctl_handle_int(oidp, &new, 0, req); 26256138Ssos if (error == 0 && req->newptr != NULL) { 26356558Ssos if (CAST_PTR_INT(req->newptr) < 1 || 26456558Ssos CAST_PTR_INT(req->newptr) > V_vegas_beta) 26556138Ssos error = EINVAL; 26656138Ssos else 26756558Ssos V_vegas_alpha = new; 26856138Ssos } 26956138Ssos 27056138Ssos return (error); 27156138Ssos} 27256138Ssos 27356138Ssosstatic int 27456138Ssosvegas_beta_handler(SYSCTL_HANDLER_ARGS) 27556558Ssos{ 27656558Ssos int error; 27756558Ssos uint32_t new; 27856138Ssos 27956138Ssos new = V_vegas_beta; 28056558Ssos error = sysctl_handle_int(oidp, &new, 0, req); 28156138Ssos if (error == 0 && req->newptr != NULL) { 28256138Ssos if (CAST_PTR_INT(req->newptr) < 1 || 28356138Ssos CAST_PTR_INT(req->newptr) < V_vegas_alpha) 28456138Ssos error = EINVAL; 28556138Ssos else 28656138Ssos V_vegas_beta = new; 28756138Ssos } 28854270Ssos 28956138Ssos return (error); 29054270Ssos} 29156558Ssos 29256558SsosSYSCTL_DECL(_net_inet_tcp_cc_vegas); 29356558SsosSYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, vegas, CTLFLAG_RW, NULL, 29454270Ssos "Vegas related settings"); 29554969Ssos 29656558SsosSYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, alpha, 29754270Ssos CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 29853681Ssos &VNET_NAME(vegas_alpha), 1, &vegas_alpha_handler, "IU", 29954270Ssos "vegas alpha, specified as number of \"buffers\" (0 < alpha < beta)"); 30054270Ssos 30156138SsosSYSCTL_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, beta, 30255333Ssos CTLFLAG_VNET | CTLTYPE_UINT | CTLFLAG_RW, 30355333Ssos &VNET_NAME(vegas_beta), 3, &vegas_beta_handler, "IU", 30455333Ssos "vegas beta, specified as number of \"buffers\" (0 < alpha < beta)"); 30555333Ssos 30653681SsosDECLARE_CC_MODULE(vegas, &vegas_cc_algo); 30753681SsosMODULE_DEPEND(vegas, ertt, 1, 1, 1); 30853681Ssos