1/*- 2 * Copyright (c) 2009-2010 3 * Swinburne University of Technology, Melbourne, Australia 4 * Copyright (c) 2010 Lawrence Stewart <lstewart@freebsd.org> 5 * Copyright (c) 2010-2011 The FreeBSD Foundation 6 * All rights reserved. 7 * 8 * This software was developed at the Centre for Advanced Internet 9 * Architectures, Swinburne University of Technology, by David Hayes and 10 * Lawrence Stewart, made possible in part by a grant from the Cisco University 11 * Research Program Fund at Community Foundation Silicon Valley. 12 * 13 * Portions of this software were developed at the Centre for Advanced Internet 14 * Architectures, Swinburne University of Technology, Melbourne, Australia by 15 * David Hayes under sponsorship from the FreeBSD Foundation. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39/* 40 * An implementation of the Vegas congestion control algorithm for FreeBSD, 41 * based on L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion 42 * avoidance on a global internet", IEEE J. Sel. Areas Commun., vol. 13, no. 8, 43 * pp. 1465-1480, Oct. 1995. The original Vegas duplicate ack policy has not 44 * been implemented, since clock ticks are not as coarse as they were (i.e. 45 * 500ms) when Vegas was designed. Also, packets are timed once per RTT as in 46 * the original paper. 47 * 48 * Originally released as part of the NewTCP research project at Swinburne 49 * University of Technology's Centre for Advanced Internet Architectures, 50 * Melbourne, Australia, which was made possible in part by a grant from the 51 * Cisco University Research Program Fund at Community Foundation Silicon 52 * Valley. More details are available at: 53 * http://caia.swin.edu.au/urp/newtcp/ 54 */ 55 56#include <sys/cdefs.h>
| 1/*- 2 * Copyright (c) 2009-2010 3 * Swinburne University of Technology, Melbourne, Australia 4 * Copyright (c) 2010 Lawrence Stewart <lstewart@freebsd.org> 5 * Copyright (c) 2010-2011 The FreeBSD Foundation 6 * All rights reserved. 7 * 8 * This software was developed at the Centre for Advanced Internet 9 * Architectures, Swinburne University of Technology, by David Hayes and 10 * Lawrence Stewart, made possible in part by a grant from the Cisco University 11 * Research Program Fund at Community Foundation Silicon Valley. 12 * 13 * Portions of this software were developed at the Centre for Advanced Internet 14 * Architectures, Swinburne University of Technology, Melbourne, Australia by 15 * David Hayes under sponsorship from the FreeBSD Foundation. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39/* 40 * An implementation of the Vegas congestion control algorithm for FreeBSD, 41 * based on L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion 42 * avoidance on a global internet", IEEE J. Sel. Areas Commun., vol. 13, no. 8, 43 * pp. 1465-1480, Oct. 1995. The original Vegas duplicate ack policy has not 44 * been implemented, since clock ticks are not as coarse as they were (i.e. 45 * 500ms) when Vegas was designed. Also, packets are timed once per RTT as in 46 * the original paper. 47 * 48 * Originally released as part of the NewTCP research project at Swinburne 49 * University of Technology's Centre for Advanced Internet Architectures, 50 * Melbourne, Australia, which was made possible in part by a grant from the 51 * Cisco University Research Program Fund at Community Foundation Silicon 52 * Valley. More details are available at: 53 * http://caia.swin.edu.au/urp/newtcp/ 54 */ 55 56#include <sys/cdefs.h>
|
110 "Per connection data required for the Vegas congestion control algorithm"); 111 112struct cc_algo vegas_cc_algo = { 113 .name = "vegas", 114 .ack_received = vegas_ack_received, 115 .cb_destroy = vegas_cb_destroy, 116 .cb_init = vegas_cb_init, 117 .cong_signal = vegas_cong_signal, 118 .conn_init = vegas_conn_init, 119 .mod_init = vegas_mod_init 120}; 121 122/* 123 * The vegas window adjustment is done once every RTT, as indicated by the 124 * ERTT_NEW_MEASUREMENT flag. This flag is reset once the new measurment data 125 * has been used. 126 */ 127static void 128vegas_ack_received(struct cc_var *ccv, uint16_t ack_type) 129{ 130 struct ertt *e_t; 131 struct vegas *vegas_data; 132 long actual_tx_rate, expected_tx_rate, ndiff; 133 134 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id); 135 vegas_data = ccv->cc_data; 136 137 if (e_t->flags & ERTT_NEW_MEASUREMENT) { /* Once per RTT. */ 138 if (e_t->minrtt && e_t->markedpkt_rtt) { 139 expected_tx_rate = e_t->marked_snd_cwnd / e_t->minrtt; 140 actual_tx_rate = e_t->bytes_tx_in_marked_rtt / 141 e_t->markedpkt_rtt; 142 ndiff = (expected_tx_rate - actual_tx_rate) * 143 e_t->minrtt / CCV(ccv, t_maxseg); 144 145 if (ndiff < V_vegas_alpha) { 146 if (CCV(ccv, snd_cwnd) <= 147 CCV(ccv, snd_ssthresh)) { 148 vegas_data->slow_start_toggle = 149 vegas_data->slow_start_toggle ? 150 0 : 1; 151 } else { 152 vegas_data->slow_start_toggle = 0; 153 CCV(ccv, snd_cwnd) = 154 min(CCV(ccv, snd_cwnd) + 155 CCV(ccv, t_maxseg), 156 TCP_MAXWIN << CCV(ccv, snd_scale)); 157 } 158 } else if (ndiff > V_vegas_beta) { 159 /* Rate-based congestion. */ 160 vegas_cong_signal(ccv, CC_VEGAS_RATE); 161 vegas_data->slow_start_toggle = 0; 162 } 163 } 164 e_t->flags &= ~ERTT_NEW_MEASUREMENT; 165 } 166 167 if (vegas_data->slow_start_toggle) 168 newreno_cc_algo.ack_received(ccv, ack_type); 169} 170 171static void 172vegas_cb_destroy(struct cc_var *ccv) 173{ 174 175 if (ccv->cc_data != NULL) 176 free(ccv->cc_data, M_VEGAS); 177} 178 179static int 180vegas_cb_init(struct cc_var *ccv) 181{ 182 struct vegas *vegas_data; 183 184 vegas_data = malloc(sizeof(struct vegas), M_VEGAS, M_NOWAIT); 185 186 if (vegas_data == NULL) 187 return (ENOMEM); 188 189 vegas_data->slow_start_toggle = 1; 190 ccv->cc_data = vegas_data; 191 192 return (0); 193} 194 195/* 196 * If congestion has been triggered triggered by the Vegas measured rates, it is 197 * handled here, otherwise it falls back to newreno's congestion handling. 198 */ 199static void 200vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type) 201{ 202 struct vegas *vegas_data; 203 int presignalrecov; 204 205 vegas_data = ccv->cc_data; 206 207 if (IN_RECOVERY(CCV(ccv, t_flags))) 208 presignalrecov = 1; 209 else 210 presignalrecov = 0; 211 212 switch(signal_type) { 213 case CC_VEGAS_RATE: 214 if (!IN_RECOVERY(CCV(ccv, t_flags))) { 215 CCV(ccv, snd_cwnd) = max(2 * CCV(ccv, t_maxseg), 216 CCV(ccv, snd_cwnd) - CCV(ccv, t_maxseg)); 217 if (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) 218 /* Exit slow start. */ 219 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd); 220 } 221 break; 222 223 default: 224 newreno_cc_algo.cong_signal(ccv, signal_type); 225 } 226 227 if (IN_RECOVERY(CCV(ccv, t_flags)) && !presignalrecov) 228 vegas_data->slow_start_toggle = 229 (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) ? 1 : 0; 230} 231 232static void 233vegas_conn_init(struct cc_var *ccv) 234{ 235 struct vegas *vegas_data; 236 237 vegas_data = ccv->cc_data; 238 vegas_data->slow_start_toggle = 1; 239} 240 241static int 242vegas_mod_init(void) 243{ 244 245 ertt_id = khelp_get_id("ertt"); 246 if (ertt_id <= 0) { 247 printf("%s: h_ertt module not found\n", __func__); 248 return (ENOENT); 249 } 250 251 vegas_cc_algo.after_idle = newreno_cc_algo.after_idle; 252 vegas_cc_algo.post_recovery = newreno_cc_algo.post_recovery; 253 254 return (0); 255} 256 257static int 258vegas_alpha_handler(SYSCTL_HANDLER_ARGS) 259{ 260 int error; 261 uint32_t new; 262 263 new = V_vegas_alpha; 264 error = sysctl_handle_int(oidp, &new, 0, req); 265 if (error == 0 && req->newptr != NULL) { 266 if (CAST_PTR_INT(req->newptr) < 1 || 267 CAST_PTR_INT(req->newptr) > V_vegas_beta) 268 error = EINVAL; 269 else 270 V_vegas_alpha = new; 271 } 272 273 return (error); 274} 275 276static int 277vegas_beta_handler(SYSCTL_HANDLER_ARGS) 278{ 279 int error; 280 uint32_t new; 281 282 new = V_vegas_beta; 283 error = sysctl_handle_int(oidp, &new, 0, req); 284 if (error == 0 && req->newptr != NULL) { 285 if (CAST_PTR_INT(req->newptr) < 1 || 286 CAST_PTR_INT(req->newptr) < V_vegas_alpha) 287 error = EINVAL; 288 else 289 V_vegas_beta = new; 290 } 291 292 return (error); 293} 294 295SYSCTL_DECL(_net_inet_tcp_cc_vegas); 296SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, vegas, CTLFLAG_RW, NULL, 297 "Vegas related settings"); 298 299SYSCTL_VNET_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, alpha, 300 CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(vegas_alpha), 1, &vegas_alpha_handler, 301 "IU", "vegas alpha, specified as number of \"buffers\" (0 < alpha < beta)"); 302 303SYSCTL_VNET_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, beta, 304 CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(vegas_beta), 3, &vegas_beta_handler, 305 "IU", "vegas beta, specified as number of \"buffers\" (0 < alpha < beta)"); 306 307DECLARE_CC_MODULE(vegas, &vegas_cc_algo); 308MODULE_DEPEND(vegas, ertt, 1, 1, 1);
| 109 "Per connection data required for the Vegas congestion control algorithm"); 110 111struct 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}; 120 121/* 122 * The vegas window adjustment is done once every RTT, as indicated by the 123 * ERTT_NEW_MEASUREMENT flag. This flag is reset once the new measurment data 124 * has been used. 125 */ 126static void 127vegas_ack_received(struct cc_var *ccv, uint16_t ack_type) 128{ 129 struct ertt *e_t; 130 struct vegas *vegas_data; 131 long actual_tx_rate, expected_tx_rate, ndiff; 132 133 e_t = khelp_get_osd(CCV(ccv, osd), ertt_id); 134 vegas_data = ccv->cc_data; 135 136 if (e_t->flags & ERTT_NEW_MEASUREMENT) { /* Once per RTT. */ 137 if (e_t->minrtt && e_t->markedpkt_rtt) { 138 expected_tx_rate = e_t->marked_snd_cwnd / e_t->minrtt; 139 actual_tx_rate = e_t->bytes_tx_in_marked_rtt / 140 e_t->markedpkt_rtt; 141 ndiff = (expected_tx_rate - actual_tx_rate) * 142 e_t->minrtt / CCV(ccv, t_maxseg); 143 144 if (ndiff < V_vegas_alpha) { 145 if (CCV(ccv, snd_cwnd) <= 146 CCV(ccv, snd_ssthresh)) { 147 vegas_data->slow_start_toggle = 148 vegas_data->slow_start_toggle ? 149 0 : 1; 150 } else { 151 vegas_data->slow_start_toggle = 0; 152 CCV(ccv, snd_cwnd) = 153 min(CCV(ccv, snd_cwnd) + 154 CCV(ccv, t_maxseg), 155 TCP_MAXWIN << CCV(ccv, snd_scale)); 156 } 157 } else if (ndiff > V_vegas_beta) { 158 /* Rate-based congestion. */ 159 vegas_cong_signal(ccv, CC_VEGAS_RATE); 160 vegas_data->slow_start_toggle = 0; 161 } 162 } 163 e_t->flags &= ~ERTT_NEW_MEASUREMENT; 164 } 165 166 if (vegas_data->slow_start_toggle) 167 newreno_cc_algo.ack_received(ccv, ack_type); 168} 169 170static void 171vegas_cb_destroy(struct cc_var *ccv) 172{ 173 174 if (ccv->cc_data != NULL) 175 free(ccv->cc_data, M_VEGAS); 176} 177 178static int 179vegas_cb_init(struct cc_var *ccv) 180{ 181 struct vegas *vegas_data; 182 183 vegas_data = malloc(sizeof(struct vegas), M_VEGAS, M_NOWAIT); 184 185 if (vegas_data == NULL) 186 return (ENOMEM); 187 188 vegas_data->slow_start_toggle = 1; 189 ccv->cc_data = vegas_data; 190 191 return (0); 192} 193 194/* 195 * If congestion has been triggered triggered by the Vegas measured rates, it is 196 * handled here, otherwise it falls back to newreno's congestion handling. 197 */ 198static void 199vegas_cong_signal(struct cc_var *ccv, uint32_t signal_type) 200{ 201 struct vegas *vegas_data; 202 int presignalrecov; 203 204 vegas_data = ccv->cc_data; 205 206 if (IN_RECOVERY(CCV(ccv, t_flags))) 207 presignalrecov = 1; 208 else 209 presignalrecov = 0; 210 211 switch(signal_type) { 212 case CC_VEGAS_RATE: 213 if (!IN_RECOVERY(CCV(ccv, t_flags))) { 214 CCV(ccv, snd_cwnd) = max(2 * CCV(ccv, t_maxseg), 215 CCV(ccv, snd_cwnd) - CCV(ccv, t_maxseg)); 216 if (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) 217 /* Exit slow start. */ 218 CCV(ccv, snd_ssthresh) = CCV(ccv, snd_cwnd); 219 } 220 break; 221 222 default: 223 newreno_cc_algo.cong_signal(ccv, signal_type); 224 } 225 226 if (IN_RECOVERY(CCV(ccv, t_flags)) && !presignalrecov) 227 vegas_data->slow_start_toggle = 228 (CCV(ccv, snd_cwnd) < CCV(ccv, snd_ssthresh)) ? 1 : 0; 229} 230 231static void 232vegas_conn_init(struct cc_var *ccv) 233{ 234 struct vegas *vegas_data; 235 236 vegas_data = ccv->cc_data; 237 vegas_data->slow_start_toggle = 1; 238} 239 240static int 241vegas_mod_init(void) 242{ 243 244 ertt_id = khelp_get_id("ertt"); 245 if (ertt_id <= 0) { 246 printf("%s: h_ertt module not found\n", __func__); 247 return (ENOENT); 248 } 249 250 vegas_cc_algo.after_idle = newreno_cc_algo.after_idle; 251 vegas_cc_algo.post_recovery = newreno_cc_algo.post_recovery; 252 253 return (0); 254} 255 256static int 257vegas_alpha_handler(SYSCTL_HANDLER_ARGS) 258{ 259 int error; 260 uint32_t new; 261 262 new = V_vegas_alpha; 263 error = sysctl_handle_int(oidp, &new, 0, req); 264 if (error == 0 && req->newptr != NULL) { 265 if (CAST_PTR_INT(req->newptr) < 1 || 266 CAST_PTR_INT(req->newptr) > V_vegas_beta) 267 error = EINVAL; 268 else 269 V_vegas_alpha = new; 270 } 271 272 return (error); 273} 274 275static int 276vegas_beta_handler(SYSCTL_HANDLER_ARGS) 277{ 278 int error; 279 uint32_t new; 280 281 new = V_vegas_beta; 282 error = sysctl_handle_int(oidp, &new, 0, req); 283 if (error == 0 && req->newptr != NULL) { 284 if (CAST_PTR_INT(req->newptr) < 1 || 285 CAST_PTR_INT(req->newptr) < V_vegas_alpha) 286 error = EINVAL; 287 else 288 V_vegas_beta = new; 289 } 290 291 return (error); 292} 293 294SYSCTL_DECL(_net_inet_tcp_cc_vegas); 295SYSCTL_NODE(_net_inet_tcp_cc, OID_AUTO, vegas, CTLFLAG_RW, NULL, 296 "Vegas related settings"); 297 298SYSCTL_VNET_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, alpha, 299 CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(vegas_alpha), 1, &vegas_alpha_handler, 300 "IU", "vegas alpha, specified as number of \"buffers\" (0 < alpha < beta)"); 301 302SYSCTL_VNET_PROC(_net_inet_tcp_cc_vegas, OID_AUTO, beta, 303 CTLTYPE_UINT|CTLFLAG_RW, &VNET_NAME(vegas_beta), 3, &vegas_beta_handler, 304 "IU", "vegas beta, specified as number of \"buffers\" (0 < alpha < beta)"); 305 306DECLARE_CC_MODULE(vegas, &vegas_cc_algo); 307MODULE_DEPEND(vegas, ertt, 1, 1, 1);
|