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