2 * TCP CUBIC: Binary Increase Congestion control for TCP v2.3
4 * http://netsrv.csc.ncsu.edu/twiki/bin/view/Main/BIC
5 * This is from the implementation of CUBIC TCP in
6 * Sangtae Ha, Injong Rhee and Lisong Xu,
7 * "CUBIC: A New TCP-Friendly High-Speed TCP Variant"
8 * in ACM SIGOPS Operating System Review, July 2008.
10 * http://netsrv.csc.ncsu.edu/export/cubic_a_new_tcp_2008.pdf
12 * CUBIC integrates a new slow start algorithm, called HyStart.
13 * The details of HyStart are presented in
14 * Sangtae Ha and Injong Rhee,
15 * "Taming the Elephants: New TCP Slow Start", NCSU TechReport 2008.
17 * http://netsrv.csc.ncsu.edu/export/hystart_techreport_2008.pdf
19 * All testing results are available from:
20 * http://netsrv.csc.ncsu.edu/wiki/index.php/TCP_Testing
22 * Unless CUBIC is enabled and congestion window is large
23 * this behaves the same as the original Reno.
27 #include <linux/module.h>
28 #include <linux/math64.h>
31 #define BICTCP_BETA_SCALE 1024 /* Scale factor beta calculation
32 * max_cwnd = snd_cwnd * beta
34 #define BICTCP_HZ 10 /* BIC HZ 2^10 = 1024 */
36 /* Two methods of hybrid slow start */
37 #define HYSTART_ACK_TRAIN 0x1
38 #define HYSTART_DELAY 0x2
40 /* Number of delay samples for detecting the increase of delay */
41 #define HYSTART_MIN_SAMPLES 8
42 #define HYSTART_DELAY_MIN (4U<<3)
43 #define HYSTART_DELAY_MAX (16U<<3)
44 #define HYSTART_DELAY_THRESH(x) clamp(x, HYSTART_DELAY_MIN, HYSTART_DELAY_MAX)
46 static int fast_convergence __read_mostly
= 1;
47 static int beta __read_mostly
= 717; /* = 717/1024 (BICTCP_BETA_SCALE) */
48 static int initial_ssthresh __read_mostly
;
49 static int bic_scale __read_mostly
= 41;
50 static int tcp_friendliness __read_mostly
= 1;
52 static int hystart __read_mostly
= 1;
53 static int hystart_detect __read_mostly
= HYSTART_ACK_TRAIN
| HYSTART_DELAY
;
54 static int hystart_low_window __read_mostly
= 16;
55 static int hystart_ack_delta __read_mostly
= 2;
57 static u32 cube_rtt_scale __read_mostly
;
58 static u32 beta_scale __read_mostly
;
59 static u64 cube_factor __read_mostly
;
61 /* Note parameters that are used for precomputing scale factors are read-only */
62 module_param(fast_convergence
, int, 0644);
63 MODULE_PARM_DESC(fast_convergence
, "turn on/off fast convergence");
64 module_param(beta
, int, 0644);
65 MODULE_PARM_DESC(beta
, "beta for multiplicative increase");
66 module_param(initial_ssthresh
, int, 0644);
67 MODULE_PARM_DESC(initial_ssthresh
, "initial value of slow start threshold");
68 module_param(bic_scale
, int, 0444);
69 MODULE_PARM_DESC(bic_scale
, "scale (scaled by 1024) value for bic function (bic_scale/1024)");
70 module_param(tcp_friendliness
, int, 0644);
71 MODULE_PARM_DESC(tcp_friendliness
, "turn on/off tcp friendliness");
72 module_param(hystart
, int, 0644);
73 MODULE_PARM_DESC(hystart
, "turn on/off hybrid slow start algorithm");
74 module_param(hystart_detect
, int, 0644);
75 MODULE_PARM_DESC(hystart_detect
, "hyrbrid slow start detection mechanisms"
76 " 1: packet-train 2: delay 3: both packet-train and delay");
77 module_param(hystart_low_window
, int, 0644);
78 MODULE_PARM_DESC(hystart_low_window
, "lower bound cwnd for hybrid slow start");
79 module_param(hystart_ack_delta
, int, 0644);
80 MODULE_PARM_DESC(hystart_ack_delta
, "spacing between ack's indicating train (msecs)");
82 /* BIC TCP Parameters */
84 u32 cnt
; /* increase cwnd by 1 after ACKs */
85 u32 last_max_cwnd
; /* last maximum snd_cwnd */
86 u32 loss_cwnd
; /* congestion window at last loss */
87 u32 last_cwnd
; /* the last snd_cwnd */
88 u32 last_time
; /* time when updated last_cwnd */
89 u32 bic_origin_point
;/* origin point of bic function */
90 u32 bic_K
; /* time to origin point
91 from the beginning of the current epoch */
92 u32 delay_min
; /* min delay (msec << 3) */
93 u32 epoch_start
; /* beginning of an epoch */
94 u32 ack_cnt
; /* number of acks */
95 u32 tcp_cwnd
; /* estimated tcp cwnd */
97 u8 sample_cnt
; /* number of samples to decide curr_rtt */
98 u8 found
; /* the exit point is found? */
99 u32 round_start
; /* beginning of each round */
100 u32 end_seq
; /* end_seq of the round */
101 u32 last_ack
; /* last time when the ACK spacing is close */
102 u32 curr_rtt
; /* the minimum rtt of current round */
105 static inline void bictcp_reset(struct bictcp
*ca
)
108 ca
->last_max_cwnd
= 0;
111 ca
->bic_origin_point
= 0;
120 static inline u32
bictcp_clock(void)
123 return ktime_to_ms(ktime_get_real());
125 return jiffies_to_msecs(jiffies
);
129 static inline void bictcp_hystart_reset(struct sock
*sk
)
131 struct tcp_sock
*tp
= tcp_sk(sk
);
132 struct bictcp
*ca
= inet_csk_ca(sk
);
134 ca
->round_start
= ca
->last_ack
= bictcp_clock();
135 ca
->end_seq
= tp
->snd_nxt
;
140 static void bictcp_init(struct sock
*sk
)
142 struct bictcp
*ca
= inet_csk_ca(sk
);
148 bictcp_hystart_reset(sk
);
150 if (!hystart
&& initial_ssthresh
)
151 tcp_sk(sk
)->snd_ssthresh
= initial_ssthresh
;
154 static void bictcp_cwnd_event(struct sock
*sk
, enum tcp_ca_event event
)
156 if (event
== CA_EVENT_TX_START
) {
157 s32 delta
= tcp_time_stamp
- tcp_sk(sk
)->lsndtime
;
158 struct bictcp
*ca
= inet_csk_ca(sk
);
160 /* We were application limited (idle) for a while.
161 * Shift epoch_start to keep cwnd growth to cubic curve.
163 if (ca
->epoch_start
&& delta
> 0)
164 ca
->epoch_start
+= delta
;
169 /* calculate the cubic root of x using a table lookup followed by one
170 * Newton-Raphson iteration.
173 static u32
cubic_root(u64 a
)
177 * cbrt(x) MSB values for x MSB values in [0..63].
178 * Precomputed then refined by hand - Willy Tarreau
181 * v = cbrt(x << 18) - 1
182 * cbrt(x) = (v[x] + 10) >> 6
184 static const u8 v
[] = {
185 /* 0x00 */ 0, 54, 54, 54, 118, 118, 118, 118,
186 /* 0x08 */ 123, 129, 134, 138, 143, 147, 151, 156,
187 /* 0x10 */ 157, 161, 164, 168, 170, 173, 176, 179,
188 /* 0x18 */ 181, 185, 187, 190, 192, 194, 197, 199,
189 /* 0x20 */ 200, 202, 204, 206, 209, 211, 213, 215,
190 /* 0x28 */ 217, 219, 221, 222, 224, 225, 227, 229,
191 /* 0x30 */ 231, 232, 234, 236, 237, 239, 240, 242,
192 /* 0x38 */ 244, 245, 246, 248, 250, 251, 252, 254,
198 return ((u32
)v
[(u32
)a
] + 35) >> 6;
201 b
= ((b
* 84) >> 8) - 1;
202 shift
= (a
>> (b
* 3));
204 x
= ((u32
)(((u32
)v
[shift
] + 10) << b
)) >> 6;
207 * Newton-Raphson iteration
209 * x = ( 2 * x + a / x ) / 3
212 x
= (2 * x
+ (u32
)div64_u64(a
, (u64
)x
* (u64
)(x
- 1)));
213 x
= ((x
* 341) >> 10);
218 * Compute congestion window to use.
220 static inline void bictcp_update(struct bictcp
*ca
, u32 cwnd
, u32 acked
)
222 u32 delta
, bic_target
, max_cnt
;
225 ca
->ack_cnt
+= acked
; /* count the number of ACKed packets */
227 if (ca
->last_cwnd
== cwnd
&&
228 (s32
)(tcp_time_stamp
- ca
->last_time
) <= HZ
/ 32)
231 /* The CUBIC function can update ca->cnt at most once per jiffy.
232 * On all cwnd reduction events, ca->epoch_start is set to 0,
233 * which will force a recalculation of ca->cnt.
235 if (ca
->epoch_start
&& tcp_time_stamp
== ca
->last_time
)
236 goto tcp_friendliness
;
238 ca
->last_cwnd
= cwnd
;
239 ca
->last_time
= tcp_time_stamp
;
241 if (ca
->epoch_start
== 0) {
242 ca
->epoch_start
= tcp_time_stamp
; /* record beginning */
243 ca
->ack_cnt
= acked
; /* start counting */
244 ca
->tcp_cwnd
= cwnd
; /* syn with cubic */
246 if (ca
->last_max_cwnd
<= cwnd
) {
248 ca
->bic_origin_point
= cwnd
;
250 /* Compute new K based on
251 * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ)
253 ca
->bic_K
= cubic_root(cube_factor
254 * (ca
->last_max_cwnd
- cwnd
));
255 ca
->bic_origin_point
= ca
->last_max_cwnd
;
259 /* cubic function - calc*/
260 /* calculate c * time^3 / rtt,
261 * while considering overflow in calculation of time^3
262 * (so time^3 is done by using 64 bit)
263 * and without the support of division of 64bit numbers
264 * (so all divisions are done by using 32 bit)
265 * also NOTE the unit of those veriables
266 * time = (t - K) / 2^bictcp_HZ
267 * c = bic_scale >> 10
268 * rtt = (srtt >> 3) / HZ
269 * !!! The following code does not have overflow problems,
270 * if the cwnd < 1 million packets !!!
273 t
= (s32
)(tcp_time_stamp
- ca
->epoch_start
);
274 t
+= msecs_to_jiffies(ca
->delay_min
>> 3);
275 /* change the unit from HZ to bictcp_HZ */
279 if (t
< ca
->bic_K
) /* t - K */
280 offs
= ca
->bic_K
- t
;
282 offs
= t
- ca
->bic_K
;
284 /* c/rtt * (t-K)^3 */
285 delta
= (cube_rtt_scale
* offs
* offs
* offs
) >> (10+3*BICTCP_HZ
);
286 if (t
< ca
->bic_K
) /* below origin*/
287 bic_target
= ca
->bic_origin_point
- delta
;
288 else /* above origin*/
289 bic_target
= ca
->bic_origin_point
+ delta
;
291 /* cubic function - calc bictcp_cnt*/
292 if (bic_target
> cwnd
) {
293 ca
->cnt
= cwnd
/ (bic_target
- cwnd
);
295 ca
->cnt
= 100 * cwnd
; /* very small increment*/
299 * The initial growth of cubic function may be too conservative
300 * when the available bandwidth is still unknown.
302 if (ca
->last_max_cwnd
== 0 && ca
->cnt
> 20)
303 ca
->cnt
= 20; /* increase cwnd 5% per RTT */
307 if (tcp_friendliness
) {
308 u32 scale
= beta_scale
;
310 delta
= (cwnd
* scale
) >> 3;
311 while (ca
->ack_cnt
> delta
) { /* update tcp cwnd */
312 ca
->ack_cnt
-= delta
;
316 if (ca
->tcp_cwnd
> cwnd
) { /* if bic is slower than tcp */
317 delta
= ca
->tcp_cwnd
- cwnd
;
318 max_cnt
= cwnd
/ delta
;
319 if (ca
->cnt
> max_cnt
)
324 /* The maximum rate of cwnd increase CUBIC allows is 1 packet per
325 * 2 packets ACKed, meaning cwnd grows at 1.5x per RTT.
327 ca
->cnt
= max(ca
->cnt
, 2U);
330 static void bictcp_cong_avoid(struct sock
*sk
, u32 ack
, u32 acked
)
332 struct tcp_sock
*tp
= tcp_sk(sk
);
333 struct bictcp
*ca
= inet_csk_ca(sk
);
335 if (!tcp_is_cwnd_limited(sk
))
338 if (tcp_in_slow_start(tp
)) {
339 if (hystart
&& after(ack
, ca
->end_seq
))
340 bictcp_hystart_reset(sk
);
341 acked
= tcp_slow_start(tp
, acked
);
345 bictcp_update(ca
, tp
->snd_cwnd
, acked
);
346 tcp_cong_avoid_ai(tp
, ca
->cnt
, acked
);
349 static u32
bictcp_recalc_ssthresh(struct sock
*sk
)
351 const struct tcp_sock
*tp
= tcp_sk(sk
);
352 struct bictcp
*ca
= inet_csk_ca(sk
);
354 ca
->epoch_start
= 0; /* end of epoch */
356 /* Wmax and fast convergence */
357 if (tp
->snd_cwnd
< ca
->last_max_cwnd
&& fast_convergence
)
358 ca
->last_max_cwnd
= (tp
->snd_cwnd
* (BICTCP_BETA_SCALE
+ beta
))
359 / (2 * BICTCP_BETA_SCALE
);
361 ca
->last_max_cwnd
= tp
->snd_cwnd
;
363 ca
->loss_cwnd
= tp
->snd_cwnd
;
365 return max((tp
->snd_cwnd
* beta
) / BICTCP_BETA_SCALE
, 2U);
368 static u32
bictcp_undo_cwnd(struct sock
*sk
)
370 struct bictcp
*ca
= inet_csk_ca(sk
);
372 return max(tcp_sk(sk
)->snd_cwnd
, ca
->loss_cwnd
);
375 static void bictcp_state(struct sock
*sk
, u8 new_state
)
377 if (new_state
== TCP_CA_Loss
) {
378 bictcp_reset(inet_csk_ca(sk
));
379 bictcp_hystart_reset(sk
);
383 static void hystart_update(struct sock
*sk
, u32 delay
)
385 struct tcp_sock
*tp
= tcp_sk(sk
);
386 struct bictcp
*ca
= inet_csk_ca(sk
);
388 if (ca
->found
& hystart_detect
)
391 if (hystart_detect
& HYSTART_ACK_TRAIN
) {
392 u32 now
= bictcp_clock();
394 /* first detection parameter - ack-train detection */
395 if ((s32
)(now
- ca
->last_ack
) <= hystart_ack_delta
) {
397 if ((s32
)(now
- ca
->round_start
) > ca
->delay_min
>> 4) {
398 ca
->found
|= HYSTART_ACK_TRAIN
;
399 NET_INC_STATS_BH(sock_net(sk
),
400 LINUX_MIB_TCPHYSTARTTRAINDETECT
);
401 NET_ADD_STATS_BH(sock_net(sk
),
402 LINUX_MIB_TCPHYSTARTTRAINCWND
,
404 tp
->snd_ssthresh
= tp
->snd_cwnd
;
409 if (hystart_detect
& HYSTART_DELAY
) {
410 /* obtain the minimum delay of more than sampling packets */
411 if (ca
->sample_cnt
< HYSTART_MIN_SAMPLES
) {
412 if (ca
->curr_rtt
== 0 || ca
->curr_rtt
> delay
)
413 ca
->curr_rtt
= delay
;
417 if (ca
->curr_rtt
> ca
->delay_min
+
418 HYSTART_DELAY_THRESH(ca
->delay_min
>> 3)) {
419 ca
->found
|= HYSTART_DELAY
;
420 NET_INC_STATS_BH(sock_net(sk
),
421 LINUX_MIB_TCPHYSTARTDELAYDETECT
);
422 NET_ADD_STATS_BH(sock_net(sk
),
423 LINUX_MIB_TCPHYSTARTDELAYCWND
,
425 tp
->snd_ssthresh
= tp
->snd_cwnd
;
431 /* Track delayed acknowledgment ratio using sliding window
432 * ratio = (15*ratio + sample) / 16
434 static void bictcp_acked(struct sock
*sk
, u32 cnt
, s32 rtt_us
)
436 const struct tcp_sock
*tp
= tcp_sk(sk
);
437 struct bictcp
*ca
= inet_csk_ca(sk
);
440 /* Some calls are for duplicates without timetamps */
444 /* Discard delay samples right after fast recovery */
445 if (ca
->epoch_start
&& (s32
)(tcp_time_stamp
- ca
->epoch_start
) < HZ
)
448 delay
= (rtt_us
<< 3) / USEC_PER_MSEC
;
452 /* first time call or link delay decreases */
453 if (ca
->delay_min
== 0 || ca
->delay_min
> delay
)
454 ca
->delay_min
= delay
;
456 /* hystart triggers when cwnd is larger than some threshold */
457 if (hystart
&& tcp_in_slow_start(tp
) &&
458 tp
->snd_cwnd
>= hystart_low_window
)
459 hystart_update(sk
, delay
);
462 static struct tcp_congestion_ops cubictcp __read_mostly
= {
464 .ssthresh
= bictcp_recalc_ssthresh
,
465 .cong_avoid
= bictcp_cong_avoid
,
466 .set_state
= bictcp_state
,
467 .undo_cwnd
= bictcp_undo_cwnd
,
468 .cwnd_event
= bictcp_cwnd_event
,
469 .pkts_acked
= bictcp_acked
,
470 .owner
= THIS_MODULE
,
474 static int __init
cubictcp_register(void)
476 BUILD_BUG_ON(sizeof(struct bictcp
) > ICSK_CA_PRIV_SIZE
);
478 /* Precompute a bunch of the scaling factors that are used per-packet
479 * based on SRTT of 100ms
482 beta_scale
= 8*(BICTCP_BETA_SCALE
+beta
) / 3
483 / (BICTCP_BETA_SCALE
- beta
);
485 cube_rtt_scale
= (bic_scale
* 10); /* 1024*c/rtt */
487 /* calculate the "K" for (wmax-cwnd) = c/rtt * K^3
488 * so K = cubic_root( (wmax-cwnd)*rtt/c )
489 * the unit of K is bictcp_HZ=2^10, not HZ
491 * c = bic_scale >> 10
494 * the following code has been designed and tested for
495 * cwnd < 1 million packets
497 * HZ < 1,000,00 (corresponding to 10 nano-second)
500 /* 1/c * 2^2*bictcp_HZ * srtt */
501 cube_factor
= 1ull << (10+3*BICTCP_HZ
); /* 2^40 */
503 /* divide by bic_scale and by constant Srtt (100ms) */
504 do_div(cube_factor
, bic_scale
* 10);
506 return tcp_register_congestion_control(&cubictcp
);
509 static void __exit
cubictcp_unregister(void)
511 tcp_unregister_congestion_control(&cubictcp
);
514 module_init(cubictcp_register
);
515 module_exit(cubictcp_unregister
);
517 MODULE_AUTHOR("Sangtae Ha, Stephen Hemminger");
518 MODULE_LICENSE("GPL");
519 MODULE_DESCRIPTION("CUBIC TCP");
520 MODULE_VERSION("2.3");