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
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
|
/*-
* SPDX-License-Identifier: BSD-2-Clause
*
* 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_
#include <sys/limits.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.7 << CUBIC_SHIFT. */
#define CUBIC_BETA 179
/* ~0.3 << CUBIC_SHIFT. */
#define ONE_SUB_CUBIC_BETA 77
/* 3 * ONE_SUB_CUBIC_BETA. */
#define THREE_X_PT3 231
/* (2 << CUBIC_SHIFT) - ONE_SUB_CUBIC_BETA. */
#define TWO_SUB_PT3 435
/* ~0.4 << CUBIC_SHIFT. */
#define CUBIC_C_FACTOR 102
/* CUBIC fast convergence factor: (1+beta_cubic)/2. */
#define CUBIC_FC_FACTOR 217
/* Don't trust s_rtt until this many rtt samples have been taken. */
#define CUBIC_MIN_RTT_SAMPLES 8
/*
* (2^21)^3 is long max. Dividing (2^63) by Cubic_C_factor
* and taking cube-root yields 448845 as the effective useful limit
*/
#define CUBED_ROOT_MAX_ULONG 448845
/* Flags used in the cubic structure */
#define CUBICFLAG_CONG_EVENT 0x00000001 /* congestion experienced */
#define CUBICFLAG_IN_SLOWSTART 0x00000002 /* in slow start */
#define CUBICFLAG_IN_APPLIMIT 0x00000004 /* application limited */
#define CUBICFLAG_RTO_EVENT 0x00000008 /* RTO experienced */
#define CUBICFLAG_HYSTART_ENABLED 0x00000010 /* Hystart++ is enabled */
#define CUBICFLAG_HYSTART_IN_CSS 0x00000020 /* We are in Hystart++ CSS */
/* Kernel only bits */
#ifdef _KERNEL
struct cubic {
/* CUBIC K in fixed point form with CUBIC_SHIFT worth of precision. */
int64_t K;
/* Sum of RTT samples across an epoch in ticks. */
int64_t sum_rtt_ticks;
/* cwnd at the most recent congestion event. */
unsigned long max_cwnd;
/* cwnd at the previous congestion event. */
unsigned long prev_max_cwnd;
/* A copy of prev_max_cwnd. Used for CC_RTO_ERR */
unsigned long prev_max_cwnd_cp;
/* various flags */
uint32_t flags;
/* Minimum observed rtt in ticks. */
int min_rtt_ticks;
/* Mean observed rtt between congestion epochs. */
int mean_rtt_ticks;
/* ACKs since last congestion event. */
int epoch_ack_count;
/* Timestamp (in ticks) of arriving in congestion avoidance from last
* congestion event.
*/
int t_last_cong;
/* Timestamp (in ticks) of a previous congestion event. Used for
* CC_RTO_ERR.
*/
int t_last_cong_prev;
uint32_t css_baseline_minrtt;
uint32_t css_current_round_minrtt;
uint32_t css_lastround_minrtt;
uint32_t css_rttsample_count;
uint32_t css_entered_at_round;
uint32_t css_current_round;
uint32_t css_fas_at_css_entry;
uint32_t css_lowrtt_fas;
uint32_t css_last_fas;
};
#endif
/* Userland only bits. */
#ifndef _KERNEL
extern int hz;
/*
* Implementation based on the formulae found in the CUBIC Internet Draft
* "draft-ietf-tcpm-cubic-04".
*
*/
static __inline float
theoretical_cubic_k(double wmax_pkts)
{
double C;
C = 0.4;
return (pow((wmax_pkts * 0.3) / 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.7) + ((3 * 0.3) / (2 - 0.3) *
(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;
if (cwnd > CUBED_ROOT_MAX_ULONG)
return INT_MAX;
if (cwnd < -CUBED_ROOT_MAX_ULONG)
return 0;
/* (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) >> CUBIC_SHIFT_4) * smss + wmax;
/*
* for negative cwnd, limiting to zero as lower bound
*/
return (lmax(0,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.7. 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_PT3 * (unsigned long)ticks_since_cong *
(unsigned long)smss) << CUBIC_SHIFT) / (TWO_SUB_PT3 * rtt_ticks)))
>> CUBIC_SHIFT);
}
#endif /* _NETINET_CC_CUBIC_H_ */
|
