cc_cubic.h revision 216114
1216114Slstewart/*- 2216114Slstewart * Copyright (c) 2008-2010 Lawrence Stewart <lstewart@freebsd.org> 3216114Slstewart * Copyright (c) 2010 The FreeBSD Foundation 4216114Slstewart * All rights reserved. 5216114Slstewart * 6216114Slstewart * This software was developed by Lawrence Stewart while studying at the Centre 7216114Slstewart * for Advanced Internet Architectures, Swinburne University, made possible in 8216114Slstewart * part by a grant from the Cisco University Research Program Fund at Community 9216114Slstewart * Foundation Silicon Valley. 10216114Slstewart * 11216114Slstewart * Portions of this software were developed at the Centre for Advanced 12216114Slstewart * Internet Architectures, Swinburne University of Technology, Melbourne, 13216114Slstewart * Australia by David Hayes under sponsorship from the FreeBSD Foundation. 14216114Slstewart * 15216114Slstewart * Redistribution and use in source and binary forms, with or without 16216114Slstewart * modification, are permitted provided that the following conditions 17216114Slstewart * are met: 18216114Slstewart * 1. Redistributions of source code must retain the above copyright 19216114Slstewart * notice, this list of conditions and the following disclaimer. 20216114Slstewart * 2. Redistributions in binary form must reproduce the above copyright 21216114Slstewart * notice, this list of conditions and the following disclaimer in the 22216114Slstewart * documentation and/or other materials provided with the distribution. 23216114Slstewart * 24216114Slstewart * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 25216114Slstewart * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26216114Slstewart * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27216114Slstewart * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 28216114Slstewart * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29216114Slstewart * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30216114Slstewart * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31216114Slstewart * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32216114Slstewart * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33216114Slstewart * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34216114Slstewart * SUCH DAMAGE. 35216114Slstewart * 36216114Slstewart * $FreeBSD: head/sys/netinet/cc/cc_cubic.h 216114 2010-12-02 06:05:44Z lstewart $ 37216114Slstewart */ 38216114Slstewart 39216114Slstewart#ifndef _NETINET_CC_CUBIC_H_ 40216114Slstewart#define _NETINET_CC_CUBIC_H_ 41216114Slstewart 42216114Slstewart/* Number of bits of precision for fixed point math calcs. */ 43216114Slstewart#define CUBIC_SHIFT 8 44216114Slstewart 45216114Slstewart#define CUBIC_SHIFT_4 32 46216114Slstewart 47216114Slstewart/* 0.5 << CUBIC_SHIFT. */ 48216114Slstewart#define RENO_BETA 128 49216114Slstewart 50216114Slstewart/* ~0.8 << CUBIC_SHIFT. */ 51216114Slstewart#define CUBIC_BETA 204 52216114Slstewart 53216114Slstewart/* ~0.2 << CUBIC_SHIFT. */ 54216114Slstewart#define ONE_SUB_CUBIC_BETA 51 55216114Slstewart 56216114Slstewart/* 3 * ONE_SUB_CUBIC_BETA. */ 57216114Slstewart#define THREE_X_PT2 153 58216114Slstewart 59216114Slstewart/* (2 << CUBIC_SHIFT) - ONE_SUB_CUBIC_BETA. */ 60216114Slstewart#define TWO_SUB_PT2 461 61216114Slstewart 62216114Slstewart/* ~0.4 << CUBIC_SHIFT. */ 63216114Slstewart#define CUBIC_C_FACTOR 102 64216114Slstewart 65216114Slstewart/* CUBIC fast convergence factor: ~0.9 << CUBIC_SHIFT. */ 66216114Slstewart#define CUBIC_FC_FACTOR 230 67216114Slstewart 68216114Slstewart/* Don't trust s_rtt until this many rtt samples have been taken. */ 69216114Slstewart#define CUBIC_MIN_RTT_SAMPLES 8 70216114Slstewart 71216114Slstewart/* Userland only bits. */ 72216114Slstewart#ifndef _KERNEL 73216114Slstewart 74216114Slstewartextern int hz; 75216114Slstewart 76216114Slstewart/* 77216114Slstewart * Implementation based on the formulae found in the CUBIC Internet Draft 78216114Slstewart * "draft-rhee-tcpm-cubic-02". 79216114Slstewart * 80216114Slstewart * Note BETA used in cc_cubic is equal to (1-beta) in the I-D 81216114Slstewart */ 82216114Slstewart 83216114Slstewartstatic __inline float 84216114Slstewarttheoretical_cubic_k(double wmax_pkts) 85216114Slstewart{ 86216114Slstewart double C; 87216114Slstewart 88216114Slstewart C = 0.4; 89216114Slstewart 90216114Slstewart return (pow((wmax_pkts * 0.2) / C, (1.0 / 3.0)) * pow(2, CUBIC_SHIFT)); 91216114Slstewart} 92216114Slstewart 93216114Slstewartstatic __inline unsigned long 94216114Slstewarttheoretical_cubic_cwnd(int ticks_since_cong, unsigned long wmax, uint32_t smss) 95216114Slstewart{ 96216114Slstewart double C, wmax_pkts; 97216114Slstewart 98216114Slstewart C = 0.4; 99216114Slstewart wmax_pkts = wmax / (double)smss; 100216114Slstewart 101216114Slstewart return (smss * (wmax_pkts + 102216114Slstewart (C * pow(ticks_since_cong / (double)hz - 103216114Slstewart theoretical_cubic_k(wmax_pkts) / pow(2, CUBIC_SHIFT), 3.0)))); 104216114Slstewart} 105216114Slstewart 106216114Slstewartstatic __inline unsigned long 107216114Slstewarttheoretical_reno_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 108216114Slstewart uint32_t smss) 109216114Slstewart{ 110216114Slstewart 111216114Slstewart return ((wmax * 0.5) + ((ticks_since_cong / (float)rtt_ticks) * smss)); 112216114Slstewart} 113216114Slstewart 114216114Slstewartstatic __inline unsigned long 115216114Slstewarttheoretical_tf_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 116216114Slstewart uint32_t smss) 117216114Slstewart{ 118216114Slstewart 119216114Slstewart return ((wmax * 0.8) + ((3 * 0.2) / (2 - 0.2) * 120216114Slstewart (ticks_since_cong / (float)rtt_ticks) * smss)); 121216114Slstewart} 122216114Slstewart 123216114Slstewart#endif /* !_KERNEL */ 124216114Slstewart 125216114Slstewart/* 126216114Slstewart * Compute the CUBIC K value used in the cwnd calculation, using an 127216114Slstewart * implementation of eqn 2 in the I-D. The method used 128216114Slstewart * here is adapted from Apple Computer Technical Report #KT-32. 129216114Slstewart */ 130216114Slstewartstatic __inline int64_t 131216114Slstewartcubic_k(unsigned long wmax_pkts) 132216114Slstewart{ 133216114Slstewart int64_t s, K; 134216114Slstewart uint16_t p; 135216114Slstewart 136216114Slstewart K = s = 0; 137216114Slstewart p = 0; 138216114Slstewart 139216114Slstewart /* (wmax * beta)/C with CUBIC_SHIFT worth of precision. */ 140216114Slstewart s = ((wmax_pkts * ONE_SUB_CUBIC_BETA) << CUBIC_SHIFT) / CUBIC_C_FACTOR; 141216114Slstewart 142216114Slstewart /* Rebase s to be between 1 and 1/8 with a shift of CUBIC_SHIFT. */ 143216114Slstewart while (s >= 256) { 144216114Slstewart s >>= 3; 145216114Slstewart p++; 146216114Slstewart } 147216114Slstewart 148216114Slstewart /* 149216114Slstewart * Some magic constants taken from the Apple TR with appropriate 150216114Slstewart * shifts: 275 == 1.072302 << CUBIC_SHIFT, 98 == 0.3812513 << 151216114Slstewart * CUBIC_SHIFT, 120 == 0.46946116 << CUBIC_SHIFT. 152216114Slstewart */ 153216114Slstewart K = (((s * 275) >> CUBIC_SHIFT) + 98) - 154216114Slstewart (((s * s * 120) >> CUBIC_SHIFT) >> CUBIC_SHIFT); 155216114Slstewart 156216114Slstewart /* Multiply by 2^p to undo the rebasing of s from above. */ 157216114Slstewart return (K <<= p); 158216114Slstewart} 159216114Slstewart 160216114Slstewart/* 161216114Slstewart * Compute the new cwnd value using an implementation of eqn 1 from the I-D. 162216114Slstewart * Thanks to Kip Macy for help debugging this function. 163216114Slstewart * 164216114Slstewart * XXXLAS: Characterise bounds for overflow. 165216114Slstewart */ 166216114Slstewartstatic __inline unsigned long 167216114Slstewartcubic_cwnd(int ticks_since_cong, unsigned long wmax, uint32_t smss, int64_t K) 168216114Slstewart{ 169216114Slstewart int64_t cwnd; 170216114Slstewart 171216114Slstewart /* K is in fixed point form with CUBIC_SHIFT worth of precision. */ 172216114Slstewart 173216114Slstewart /* t - K, with CUBIC_SHIFT worth of precision. */ 174216114Slstewart cwnd = ((int64_t)(ticks_since_cong << CUBIC_SHIFT) - (K * hz)) / hz; 175216114Slstewart 176216114Slstewart /* (t - K)^3, with CUBIC_SHIFT^3 worth of precision. */ 177216114Slstewart cwnd *= (cwnd * cwnd); 178216114Slstewart 179216114Slstewart /* 180216114Slstewart * C(t - K)^3 + wmax 181216114Slstewart * The down shift by CUBIC_SHIFT_4 is because cwnd has 4 lots of 182216114Slstewart * CUBIC_SHIFT included in the value. 3 from the cubing of cwnd above, 183216114Slstewart * and an extra from multiplying through by CUBIC_C_FACTOR. 184216114Slstewart */ 185216114Slstewart cwnd = ((cwnd * CUBIC_C_FACTOR * smss) >> CUBIC_SHIFT_4) + wmax; 186216114Slstewart 187216114Slstewart return ((unsigned long)cwnd); 188216114Slstewart} 189216114Slstewart 190216114Slstewart/* 191216114Slstewart * Compute an approximation of the NewReno cwnd some number of ticks after a 192216114Slstewart * congestion event. RTT should be the average RTT estimate for the path 193216114Slstewart * measured over the previous congestion epoch and wmax is the value of cwnd at 194216114Slstewart * the last congestion event. The "TCP friendly" concept in the CUBIC I-D is 195216114Slstewart * rather tricky to understand and it turns out this function is not required. 196216114Slstewart * It is left here for reference. 197216114Slstewart */ 198216114Slstewartstatic __inline unsigned long 199216114Slstewartreno_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 200216114Slstewart uint32_t smss) 201216114Slstewart{ 202216114Slstewart 203216114Slstewart /* 204216114Slstewart * For NewReno, beta = 0.5, therefore: W_tcp(t) = wmax*0.5 + t/RTT 205216114Slstewart * W_tcp(t) deals with cwnd/wmax in pkts, so because our cwnd is in 206216114Slstewart * bytes, we have to multiply by smss. 207216114Slstewart */ 208216114Slstewart return (((wmax * RENO_BETA) + (((ticks_since_cong * smss) 209216114Slstewart << CUBIC_SHIFT) / rtt_ticks)) >> CUBIC_SHIFT); 210216114Slstewart} 211216114Slstewart 212216114Slstewart/* 213216114Slstewart * Compute an approximation of the "TCP friendly" cwnd some number of ticks 214216114Slstewart * after a congestion event that is designed to yield the same average cwnd as 215216114Slstewart * NewReno while using CUBIC's beta of 0.8. RTT should be the average RTT 216216114Slstewart * estimate for the path measured over the previous congestion epoch and wmax is 217216114Slstewart * the value of cwnd at the last congestion event. 218216114Slstewart */ 219216114Slstewartstatic __inline unsigned long 220216114Slstewarttf_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, 221216114Slstewart uint32_t smss) 222216114Slstewart{ 223216114Slstewart 224216114Slstewart /* Equation 4 of I-D. */ 225216114Slstewart return (((wmax * CUBIC_BETA) + (((THREE_X_PT2 * ticks_since_cong * 226216114Slstewart smss) << CUBIC_SHIFT) / TWO_SUB_PT2 / rtt_ticks)) >> CUBIC_SHIFT); 227216114Slstewart} 228216114Slstewart 229216114Slstewart#endif /* _NETINET_CC_CUBIC_H_ */ 230