cc_vegas.c revision 218152
1218152Slstewart/*- 2218152Slstewart * Copyright (c) 2009-2010 3218152Slstewart * Swinburne University of Technology, Melbourne, Australia 4218152Slstewart * Copyright (c) 2010 Lawrence Stewart <lstewart@freebsd.org> 5218152Slstewart * Copyright (c) 2010-2011 The FreeBSD Foundation 6218152Slstewart * All rights reserved. 7218152Slstewart * 8218152Slstewart * This software was developed at the Centre for Advanced Internet 9218152Slstewart * Architectures, Swinburne University, by David Hayes and Lawrence Stewart, 10218152Slstewart * made possible in part by a grant from the Cisco University Research Program 11218152Slstewart * Fund at Community Foundation Silicon Valley. 12218152Slstewart * 13218152Slstewart * Portions of this software were developed at the Centre for Advanced Internet 14218152Slstewart * Architectures, Swinburne University of Technology, Melbourne, Australia by 15218152Slstewart * David Hayes under sponsorship from the FreeBSD Foundation. 16218152Slstewart * 17218152Slstewart * Redistribution and use in source and binary forms, with or without 18218152Slstewart * modification, are permitted provided that the following conditions 19218152Slstewart * are met: 20218152Slstewart * 1. Redistributions of source code must retain the above copyright 21218152Slstewart * notice, this list of conditions and the following disclaimer. 22218152Slstewart * 2. Redistributions in binary form must reproduce the above copyright 23218152Slstewart * notice, this list of conditions and the following disclaimer in the 24218152Slstewart * documentation and/or other materials provided with the distribution. 25218152Slstewart * 26218152Slstewart * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 27218152Slstewart * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28218152Slstewart * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29218152Slstewart * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 30218152Slstewart * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31218152Slstewart * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32218152Slstewart * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33218152Slstewart * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34218152Slstewart * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35218152Slstewart * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36218152Slstewart * SUCH DAMAGE. 37218152Slstewart */ 38218152Slstewart 39218152Slstewart/* 40218152Slstewart * An implementation of the Vegas congestion control algorithm for FreeBSD, 41218152Slstewart * based on L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion 42218152Slstewart * avoidance on a global internet", IEEE J. Sel. Areas Commun., vol. 13, no. 8, 43218152Slstewart * pp. 1465-1480, Oct. 1995. The original Vegas duplicate ack policy has not 44218152Slstewart * been implemented, since clock ticks are not as course as they were (i.e. 45218152Slstewart * 500ms) when Vegas was designed. Also, packets are timed once per RTT as in 46218152Slstewart * the original paper. 47218152Slstewart * 48218152Slstewart * Originally released as part of the NewTCP research project at Swinburne 49218152Slstewart * University's Centre for Advanced Internet Architectures, Melbourne, 50218152Slstewart * Australia, which was made possible in part by a grant from the Cisco 51218152Slstewart * University Research Program Fund at Community Foundation Silicon Valley. More 52218152Slstewart * details are available at: 53218152Slstewart * http://caia.swin.edu.au/urp/newtcp/ 54218152Slstewart */ 55218152Slstewart 56218152Slstewart#include <sys/cdefs.h> 57218152Slstewart__FBSDID("$FreeBSD: head/sys/netinet/cc/cc_vegas.c 218152 2011-02-01 06:17:00Z lstewart $"); 58218152Slstewart 59218152Slstewart#include <sys/param.h> 60218152Slstewart#include <sys/kernel.h> 61218152Slstewart#include <sys/khelp.h> 62218152Slstewart#include <sys/malloc.h> 63218152Slstewart#include <sys/module.h> 64218152Slstewart#include <sys/queue.h> 65218152Slstewart#include <sys/socket.h> 66218152Slstewart#include <sys/socketvar.h> 67218152Slstewart#include <sys/sysctl.h> 68218152Slstewart#include <sys/systm.h> 69218152Slstewart 70218152Slstewart#include <net/if.h> 71218152Slstewart#include <net/vnet.h> 72218152Slstewart 73218152Slstewart#include <netinet/cc.h> 74218152Slstewart#include <netinet/tcp_seq.h> 75218152Slstewart#include <netinet/tcp_timer.h> 76218152Slstewart#include <netinet/tcp_var.h> 77218152Slstewart 78218152Slstewart#include <netinet/cc/cc_module.h> 79218152Slstewart 80218152Slstewart#include <netinet/khelp/h_ertt.h> 81218152Slstewart 82218152Slstewart#define CAST_PTR_INT(X) (*((int*)(X))) 83218152Slstewart 84218152Slstewart/* 85218152Slstewart * Private signal type for rate based congestion signal. 86218152Slstewart * See <netinet/cc.h> for appropriate bit-range to use for private signals. 87218152Slstewart */ 88218152Slstewart#define CC_VEGAS_RATE 0x01000000 89218152Slstewart 90218152Slstewartstatic void vegas_ack_received(struct cc_var *ccv, uint16_t ack_type); 91218152Slstewartstatic void vegas_cb_destroy(struct cc_var *ccv); 92218152Slstewartstatic int vegas_cb_init(struct cc_var *ccv); 93218152Slstewartstatic void vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type); 94218152Slstewartstatic void vegas_conn_init(struct cc_var *ccv); 95218152Slstewartstatic int vegas_mod_init(void); 96218152Slstewart 97218152Slstewartstruct vegas { 98218152Slstewart int slow_start_toggle; 99218152Slstewart}; 100218152Slstewart 101218152Slstewartstatic int32_t ertt_id; 102218152Slstewart 103218152Slstewartstatic VNET_DEFINE(uint32_t, vegas_alpha) = 1; 104218152Slstewartstatic VNET_DEFINE(uint32_t, vegas_beta) = 3; 105218152Slstewart#define V_vegas_alpha VNET(vegas_alpha) 106218152Slstewart#define V_vegas_beta VNET(vegas_beta) 107218152Slstewart 108218152SlstewartMALLOC_DECLARE(M_VEGAS); 109218152SlstewartMALLOC_DEFINE(M_VEGAS, "vegas data", 110218152Slstewart "Per connection data required for the Vegas congestion control algorithm"); 111218152Slstewart 112218152Slstewartstruct cc_algo vegas_cc_algo = { 113218152Slstewart .name = "vegas", 114218152Slstewart .ack_received = vegas_ack_received, 115218152Slstewart .cb_destroy = vegas_cb_destroy, 116218152Slstewart .cb_init = vegas_cb_init, 117218152Slstewart .cong_signal = vegas_cong_signal, 118218152Slstewart .conn_init = vegas_conn_init, 119218152Slstewart .mod_init = vegas_mod_init 120218152Slstewart}; 121218152Slstewart 122218152Slstewart/* 123218152Slstewart * The vegas window adjustment is done once every RTT, as indicated by the 124218152Slstewart * ERTT_NEW_MEASUREMENT flag. This flag is reset once the new measurment data 125218152Slstewart * has been used. 126218152Slstewart */ 127218152Slstewartstatic void 128218152Slstewartvegas_ack_received(struct cc_var *ccv, uint16_t ack_type) 129218152Slstewart{ 130218152Slstewart struct ertt *e_t; 131218152Slstewart struct vegas *vegas_data; 132218152Slstewart long actual_tx_rate, expected_tx_rate, ndiff; 133218152Slstewart 134218152Slstewart e_t = khelp_get_osd(CCV(ccv, osd), ertt_id); 135218152Slstewart vegas_data = ccv->cc_data; 136218152Slstewart 137218152Slstewart if (e_t->flags & ERTT_NEW_MEASUREMENT) { /* Once per RTT. */ 138218152Slstewart if (e_t->minrtt && e_t->markedpkt_rtt) { 139218152Slstewart expected_tx_rate = e_t->marked_snd_cwnd / e_t->minrtt; 140218152Slstewart actual_tx_rate = e_t->bytes_tx_in_marked_rtt / 141218152Slstewart e_t->markedpkt_rtt; 142218152Slstewart ndiff = (expected_tx_rate - actual_tx_rate) * 143218152Slstewart e_t->minrtt / CCV(ccv, t_maxseg); 144218152Slstewart 145218152Slstewart if (ndiff < V_vegas_alpha) { 146218152Slstewart if (CCV(ccv, snd_cwnd) <= 147218152Slstewart CCV(ccv, snd_ssthresh)) { 148218152Slstewart vegas_data->slow_start_toggle = 149218152Slstewart vegas_data->slow_start_toggle ? 150218152Slstewart 0 : 1; 151218152Slstewart } else { 152218152Slstewart vegas_data->slow_start_toggle = 0; 153218152Slstewart CCV(ccv, snd_cwnd) = 154218152Slstewart min(CCV(ccv, snd_cwnd) + 155218152Slstewart CCV(ccv, t_maxseg), 156218152Slstewart TCP_MAXWIN << CCV(ccv, snd_scale)); 157218152Slstewart } 158218152Slstewart } else if (ndiff > V_vegas_beta) { 159218152Slstewart /* Rate-based congestion. */ 160218152Slstewart vegas_cong_signal(ccv, CC_VEGAS_RATE); 161218152Slstewart vegas_data->slow_start_toggle = 0; 162218152Slstewart } 163218152Slstewart } 164218152Slstewart e_t->flags &= ~ERTT_NEW_MEASUREMENT; 165218152Slstewart } 166218152Slstewart 167218152Slstewart if (vegas_data->slow_start_toggle) 168218152Slstewart newreno_cc_algo.ack_received(ccv, ack_type); 169218152Slstewart} 170218152Slstewart 171218152Slstewartstatic void 172218152Slstewartvegas_cb_destroy(struct cc_var *ccv) 173218152Slstewart{ 174218152Slstewart 175218152Slstewart if (ccv->cc_data != NULL) 176218152Slstewart free(ccv->cc_data, M_VEGAS); 177218152Slstewart} 178218152Slstewart 179218152Slstewartstatic int 180218152Slstewartvegas_cb_init(struct cc_var *ccv) 181218152Slstewart{ 182218152Slstewart struct vegas *vegas_data; 183218152Slstewart 184218152Slstewart vegas_data = malloc(sizeof(struct vegas), M_VEGAS, M_NOWAIT); 185218152Slstewart 186218152Slstewart if (vegas_data == NULL) 187218152Slstewart return (ENOMEM); 188218152Slstewart 189218152Slstewart vegas_data->slow_start_toggle = 1; 190218152Slstewart ccv->cc_data = vegas_data; 191218152Slstewart 192218152Slstewart return (0); 193218152Slstewart} 194218152Slstewart 195218152Slstewart/* 196218152Slstewart * If congestion has been triggered triggered by the Vegas measured rates, it is 197218152Slstewart * handled here, otherwise it falls back to newreno's congestion handling. 198218152Slstewart */ 199218152Slstewartstatic void 200218152Slstewartvegas_cong_signal(struct cc_var *ccv, uint32_t signal_type) 201218152Slstewart{ 202218152Slstewart struct vegas *vegas_data; 203218152Slstewart int presignalrecov; 204218152Slstewart 205218152Slstewart vegas_data = ccv->cc_data; 206218152Slstewart 207218152Slstewart if (IN_RECOVERY(CCV(ccv, t_flags))) 208218152Slstewart presignalrecov = 1; 209218152Slstewart else 210218152Slstewart presignalrecov = 0; 211218152Slstewart 212218152Slstewart switch(signal_type) { 213218152Slstewart case CC_VEGAS_RATE: 214218152Slstewart if (!IN_RECOVERY(CCV(ccv, t_flags))) { 215218152Slstewart CCV(ccv, snd_cwnd) = max(2 * CCV(ccv, t_maxseg), 216218152Slstewart CCV(ccv, snd_cwnd) - CCV(ccv, t_maxseg)); 217218152Slstewart if (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) 218218152Slstewart /* Exit slow start. */ 219218152Slstewart CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd); 220218152Slstewart } 221218152Slstewart break; 222218152Slstewart 223218152Slstewart default: 224218152Slstewart newreno_cc_algo.cong_signal(ccv, signal_type); 225218152Slstewart } 226218152Slstewart 227218152Slstewart if (IN_RECOVERY(CCV(ccv, t_flags)) && !presignalrecov) 228218152Slstewart vegas_data->slow_start_toggle = 229218152Slstewart (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) ? 1 : 0; 230218152Slstewart} 231218152Slstewart 232218152Slstewartstatic void 233218152Slstewartvegas_conn_init(struct cc_var *ccv) 234218152Slstewart{ 235218152Slstewart struct vegas *vegas_data; 236218152Slstewart 237218152Slstewart vegas_data = ccv->cc_data; 238218152Slstewart vegas_data->slow_start_toggle = 1; 239218152Slstewart} 240218152Slstewart 241218152Slstewartstatic int 242218152Slstewartvegas_mod_init(void) 243218152Slstewart{ 244218152Slstewart 245218152Slstewart ertt_id = khelp_get_id("ertt"); 246218152Slstewart if (ertt_id <= 0) { 247218152Slstewart printf("%s: h_ertt module not found\n", __func__); 248218152Slstewart return (ENOENT); 249218152Slstewart } 250218152Slstewart 251218152Slstewart vegas_cc_algo.after_idle = newreno_cc_algo.after_idle; 252218152Slstewart vegas_cc_algo.post_recovery = newreno_cc_algo.post_recovery; 253218152Slstewart 254218152Slstewart return (0); 255218152Slstewart} 256218152Slstewart 257218152Slstewartstatic int 258218152Slstewartvegas_alpha_handler(SYSCTL_HANDLER_ARGS) 259218152Slstewart{ 260218152Slstewart int error; 261218152Slstewart uint32_t new; 262218152Slstewart 263218152Slstewart new = V_vegas_alpha; 264218152Slstewart error = sysctl_handle_int(oidp, &new, 0, req); 265218152Slstewart if (error == 0 && req->newptr != NULL) { 266218152Slstewart if (CAST_PTR_INT(req->newptr) < 1 || 267218152Slstewart CAST_PTR_INT(req->newptr) > V_vegas_beta) 268218152Slstewart error = EINVAL; 269218152Slstewart else 270218152Slstewart V_vegas_alpha = new; 271218152Slstewart } 272218152Slstewart 273218152Slstewart return (error); 274218152Slstewart} 275218152Slstewart 276218152Slstewartstatic int 277218152Slstewartvegas_beta_handler(SYSCTL_HANDLER_ARGS) 278218152Slstewart{ 279218152Slstewart int error; 280218152Slstewart uint32_t new; 281218152Slstewart 282218152Slstewart new = V_vegas_beta; 283218152Slstewart error = sysctl_handle_int(oidp, &new, 0, req); 284218152Slstewart if (error == 0 && req->newptr != NULL) { 285218152Slstewart if (CAST_PTR_INT(req->newptr) < 1 || 286218152Slstewart CAST_PTR_INT(req->newptr) < V_vegas_alpha) 287218152Slstewart error = EINVAL; 288218152Slstewart else 289218152Slstewart V_vegas_beta = new; 290218152Slstewart } 291218152Slstewart 292218152Slstewart return (error); 293218152Slstewart} 294218152Slstewart 295218152SlstewartSYSCTL_DECL(_net_inet_tcp_cc_vegas); 296218152SlstewartSYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, vegas, CTLFLAG_RW, NULL, 297218152Slstewart "Vegas related settings"); 298218152Slstewart 299218152SlstewartSYSCTL_VNET_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, alpha, 300218152Slstewart CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(vegas_alpha), 1, &vegas_alpha_handler, 301218152Slstewart "IU", "vegas alpha, specified as number of \"buffers\" (0 < alpha < beta)"); 302218152Slstewart 303218152SlstewartSYSCTL_VNET_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, beta, 304218152Slstewart CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(vegas_beta), 3, &vegas_beta_handler, 305218152Slstewart "IU", "vegas beta, specified as number of \"buffers\" (0 < alpha < beta)"); 306218152Slstewart 307218152SlstewartDECLARE_CC_MODULE(vegas, &vegas_cc_algo); 308218152SlstewartMODULE_DEPEND(vegas, ertt, 1, 1, 1); 309