cc_cubic.h revision 220560
1/*- 2 * Copyright (c) 2008-2010 Lawrence Stewart <lstewart@freebsd.org> 3 * Copyright (c) 2010 The FreeBSD Foundation 4 * All rights reserved. 5 * 6 * This software was developed by Lawrence Stewart while studying at the Centre 7 * for Advanced Internet Architectures, Swinburne University of Technology, made 8 * possible in part by a grant from the Cisco University Research Program Fund 9 * at Community Foundation Silicon Valley. 10 * 11 * Portions of this software were developed at the Centre for Advanced 12 * Internet Architectures, Swinburne University of Technology, Melbourne, 13 * Australia by David Hayes under sponsorship from the FreeBSD Foundation. 14 * 15 * Redistribution and use in source and binary forms, with or without 16 * modification, are permitted provided that the following conditions 17 * are met: 18 * 1. Redistributions of source code must retain the above copyright 19 * notice, this list of conditions and the following disclaimer. 20 * 2. Redistributions in binary form must reproduce the above copyright 21 * notice, this list of conditions and the following disclaimer in the 22 * documentation and/or other materials provided with the distribution. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * $FreeBSD: head/sys/netinet/cc/cc_cubic.h 220560 2011-04-12 08:13:18Z lstewart $ 37 */ 38 39#ifndef _NETINET_CC_CUBIC_H_ 40#define _NETINET_CC_CUBIC_H_ 41 42/* Number of bits of precision for fixed point math calcs. */ 43#define CUBIC_SHIFT 8 44 45#define CUBIC_SHIFT_4 32 46 47/* 0.5 << CUBIC_SHIFT. */ 48#define RENO_BETA 128 49 50/* ~0.8 << CUBIC_SHIFT. */ 51#define CUBIC_BETA 204 52 53/* ~0.2 << CUBIC_SHIFT. */ 54#define ONE_SUB_CUBIC_BETA 51 55 56/* 3 * ONE_SUB_CUBIC_BETA. */ 57#define THREE_X_PT2 153 58 59/* (2 << CUBIC_SHIFT) - ONE_SUB_CUBIC_BETA. */ 60#define TWO_SUB_PT2 461 61 62/* ~0.4 << CUBIC_SHIFT. */ 63#define CUBIC_C_FACTOR 102 64 65/* CUBIC fast convergence factor: ~0.9 << CUBIC_SHIFT. */ 66#define CUBIC_FC_FACTOR 230 67 68/* Don't trust s_rtt until this many rtt samples have been taken. */ 69#define CUBIC_MIN_RTT_SAMPLES 8 70 71/* Userland only bits. */ 72#ifndef _KERNEL 73 74extern int hz; 75 76/* 77 * Implementation based on the formulae found in the CUBIC Internet Draft 78 * "draft-rhee-tcpm-cubic-02". 79 * 80 * Note BETA used in cc_cubic is equal to (1-beta) in the I-D 81 */ 82 83static __inline float 84theoretical_cubic_k(double wmax_pkts) 85{ 86 double C; 87 88 C = 0.4; 89 90 return (pow((wmax_pkts * 0.2) / C, (1.0 / 3.0)) * pow(2, CUBIC_SHIFT)); 91} 92 93static __inline unsigned long 94theoretical_cubic_cwnd(int ticks_since_cong, unsigned long wmax, uint32_t smss) 95{ 96 double C, wmax_pkts; 97 98 C = 0.4; 99 wmax_pkts = wmax / (double)smss; 100 101 return (smss * (wmax_pkts + 102 (C * pow(ticks_since_cong / (double)hz - 103 theoretical_cubic_k(wmax_pkts) / pow(2, CUBIC_SHIFT), 3.0)))); 104} 105 106static __inline unsigned long 107theoretical_reno_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 108 uint32_t smss) 109{ 110 111 return ((wmax * 0.5) + ((ticks_since_cong / (float)rtt_ticks) * smss)); 112} 113 114static __inline unsigned long 115theoretical_tf_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 116 uint32_t smss) 117{ 118 119 return ((wmax * 0.8) + ((3 * 0.2) / (2 - 0.2) * 120 (ticks_since_cong / (float)rtt_ticks) * smss)); 121} 122 123#endif /* !_KERNEL */ 124 125/* 126 * Compute the CUBIC K value used in the cwnd calculation, using an 127 * implementation of eqn 2 in the I-D. The method used 128 * here is adapted from Apple Computer Technical Report #KT-32. 129 */ 130static __inline int64_t 131cubic_k(unsigned long wmax_pkts) 132{ 133 int64_t s, K; 134 uint16_t p; 135 136 K = s = 0; 137 p = 0; 138 139 /* (wmax * beta)/C with CUBIC_SHIFT worth of precision. */ 140 s = ((wmax_pkts * ONE_SUB_CUBIC_BETA) << CUBIC_SHIFT) / CUBIC_C_FACTOR; 141 142 /* Rebase s to be between 1 and 1/8 with a shift of CUBIC_SHIFT. */ 143 while (s >= 256) { 144 s >>= 3; 145 p++; 146 } 147 148 /* 149 * Some magic constants taken from the Apple TR with appropriate 150 * shifts: 275 == 1.072302 << CUBIC_SHIFT, 98 == 0.3812513 << 151 * CUBIC_SHIFT, 120 == 0.46946116 << CUBIC_SHIFT. 152 */ 153 K = (((s * 275) >> CUBIC_SHIFT) + 98) - 154 (((s * s * 120) >> CUBIC_SHIFT) >> CUBIC_SHIFT); 155 156 /* Multiply by 2^p to undo the rebasing of s from above. */ 157 return (K <<= p); 158} 159 160/* 161 * Compute the new cwnd value using an implementation of eqn 1 from the I-D. 162 * Thanks to Kip Macy for help debugging this function. 163 * 164 * XXXLAS: Characterise bounds for overflow. 165 */ 166static __inline unsigned long 167cubic_cwnd(int ticks_since_cong, unsigned long wmax, uint32_t smss, int64_t K) 168{ 169 int64_t cwnd; 170 171 /* K is in fixed point form with CUBIC_SHIFT worth of precision. */ 172 173 /* t - K, with CUBIC_SHIFT worth of precision. */ 174 cwnd = ((int64_t)(ticks_since_cong << CUBIC_SHIFT) - (K * hz)) / hz; 175 176 /* (t - K)^3, with CUBIC_SHIFT^3 worth of precision. */ 177 cwnd *= (cwnd * cwnd); 178 179 /* 180 * C(t - K)^3 + wmax 181 * The down shift by CUBIC_SHIFT_4 is because cwnd has 4 lots of 182 * CUBIC_SHIFT included in the value. 3 from the cubing of cwnd above, 183 * and an extra from multiplying through by CUBIC_C_FACTOR. 184 */ 185 cwnd = ((cwnd * CUBIC_C_FACTOR * smss) >> CUBIC_SHIFT_4) + wmax; 186 187 return ((unsigned long)cwnd); 188} 189 190/* 191 * Compute an approximation of the NewReno cwnd some number of ticks after a 192 * congestion event. RTT should be the average RTT estimate for the path 193 * measured over the previous congestion epoch and wmax is the value of cwnd at 194 * the last congestion event. The "TCP friendly" concept in the CUBIC I-D is 195 * rather tricky to understand and it turns out this function is not required. 196 * It is left here for reference. 197 */ 198static __inline unsigned long 199reno_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 200 uint32_t smss) 201{ 202 203 /* 204 * For NewReno, beta = 0.5, therefore: W_tcp(t) = wmax*0.5 + t/RTT 205 * W_tcp(t) deals with cwnd/wmax in pkts, so because our cwnd is in 206 * bytes, we have to multiply by smss. 207 */ 208 return (((wmax * RENO_BETA) + (((ticks_since_cong * smss) 209 << CUBIC_SHIFT) / rtt_ticks)) >> CUBIC_SHIFT); 210} 211 212/* 213 * Compute an approximation of the "TCP friendly" cwnd some number of ticks 214 * after a congestion event that is designed to yield the same average cwnd as 215 * NewReno while using CUBIC's beta of 0.8. RTT should be the average RTT 216 * estimate for the path measured over the previous congestion epoch and wmax is 217 * the value of cwnd at the last congestion event. 218 */ 219static __inline unsigned long 220tf_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 221 uint32_t smss) 222{ 223 224 /* Equation 4 of I-D. */ 225 return (((wmax * CUBIC_BETA) + (((THREE_X_PT2 * ticks_since_cong * 226 smss) << CUBIC_SHIFT) / TWO_SUB_PT2 / rtt_ticks)) >> CUBIC_SHIFT); 227} 228 229#endif /* _NETINET_CC_CUBIC_H_ */ 230