2 * TCP CUBIC: Binary Increase Congestion control for TCP v2.0
4 * This is from the implementation of CUBIC TCP in
5 * Injong Rhee, Lisong Xu.
6 * "CUBIC: A New TCP-Friendly High-Speed TCP Variant
9 * http://www.csc.ncsu.edu/faculty/rhee/export/bitcp/cubic-paper.pdf
11 * Unless CUBIC is enabled and congestion window is large
12 * this behaves the same as the original Reno.
15 #include <linux/config.h>
17 #include <linux/module.h>
19 #include <asm/div64.h>
21 #define BICTCP_BETA_SCALE 1024 /* Scale factor beta calculation
22 * max_cwnd = snd_cwnd * beta
26 * go to point (max+min)/N
28 #define BICTCP_HZ 10 /* BIC HZ 2^10 = 1024 */
30 static int fast_convergence
= 1;
31 static int max_increment
= 16;
32 static int beta
= 819; /* = 819/1024 (BICTCP_BETA_SCALE) */
33 static int initial_ssthresh
= 100;
34 static int bic_scale
= 41;
35 static int tcp_friendliness
= 1;
37 static u32 cube_rtt_scale
;
38 static u32 beta_scale
;
39 static u64 cube_factor
;
41 /* Note parameters that are used for precomputing scale factors are read-only */
42 module_param(fast_convergence
, int, 0644);
43 MODULE_PARM_DESC(fast_convergence
, "turn on/off fast convergence");
44 module_param(max_increment
, int, 0644);
45 MODULE_PARM_DESC(max_increment
, "Limit on increment allowed during binary search");
46 module_param(beta
, int, 0444);
47 MODULE_PARM_DESC(beta
, "beta for multiplicative increase");
48 module_param(initial_ssthresh
, int, 0644);
49 MODULE_PARM_DESC(initial_ssthresh
, "initial value of slow start threshold");
50 module_param(bic_scale
, int, 0444);
51 MODULE_PARM_DESC(bic_scale
, "scale (scaled by 1024) value for bic function (bic_scale/1024)");
52 module_param(tcp_friendliness
, int, 0644);
53 MODULE_PARM_DESC(tcp_friendliness
, "turn on/off tcp friendliness");
56 /* BIC TCP Parameters */
58 u32 cnt
; /* increase cwnd by 1 after ACKs */
59 u32 last_max_cwnd
; /* last maximum snd_cwnd */
60 u32 loss_cwnd
; /* congestion window at last loss */
61 u32 last_cwnd
; /* the last snd_cwnd */
62 u32 last_time
; /* time when updated last_cwnd */
63 u32 bic_origin_point
;/* origin point of bic function */
64 u32 bic_K
; /* time to origin point from the beginning of the current epoch */
65 u32 delay_min
; /* min delay */
66 u32 epoch_start
; /* beginning of an epoch */
67 u32 ack_cnt
; /* number of acks */
68 u32 tcp_cwnd
; /* estimated tcp cwnd */
69 #define ACK_RATIO_SHIFT 4
70 u32 delayed_ack
; /* estimate the ratio of Packets/ACKs << 4 */
73 static inline void bictcp_reset(struct bictcp
*ca
)
76 ca
->last_max_cwnd
= 0;
80 ca
->bic_origin_point
= 0;
84 ca
->delayed_ack
= 2 << ACK_RATIO_SHIFT
;
89 static void bictcp_init(struct sock
*sk
)
91 bictcp_reset(inet_csk_ca(sk
));
93 tcp_sk(sk
)->snd_ssthresh
= initial_ssthresh
;
96 /* 65536 times the cubic root */
97 static const u64 cubic_table
[8]
98 = {0, 65536, 82570, 94519, 104030, 112063, 119087, 125367};
101 * calculate the cubic root of x
102 * the basic idea is that x can be expressed as i*8^j
103 * so cubic_root(x) = cubic_root(i)*2^j
104 * in the following code, x is i, and y is 2^j
105 * because of integer calculation, there are errors in calculation
106 * so finally use binary search to find out the exact solution
108 static u32
cubic_root(u64 x
)
110 u64 y
, app
, target
, start
, end
, mid
, start_diff
, end_diff
;
117 /* first estimate lower and upper bound */
123 start
= (y
*cubic_table
[x
])>>16;
127 end
= (y
*cubic_table
[x
+1]+65535)>>16;
129 /* binary search for more accurate one */
130 while (start
< end
-1) {
131 mid
= (start
+end
) >> 1;
135 else if (app
> target
)
141 /* find the most accurate one from start and end */
142 app
= start
*start
*start
;
144 start_diff
= target
- app
;
146 start_diff
= app
- target
;
149 end_diff
= target
- app
;
151 end_diff
= app
- target
;
153 if (start_diff
< end_diff
)
160 * Compute congestion window to use.
162 static inline void bictcp_update(struct bictcp
*ca
, u32 cwnd
)
165 u32 delta
, t
, bic_target
, min_cnt
, max_cnt
;
167 ca
->ack_cnt
++; /* count the number of ACKs */
169 if (ca
->last_cwnd
== cwnd
&&
170 (s32
)(tcp_time_stamp
- ca
->last_time
) <= HZ
/ 32)
173 ca
->last_cwnd
= cwnd
;
174 ca
->last_time
= tcp_time_stamp
;
176 if (ca
->epoch_start
== 0) {
177 ca
->epoch_start
= tcp_time_stamp
; /* record the beginning of an epoch */
178 ca
->ack_cnt
= 1; /* start counting */
179 ca
->tcp_cwnd
= cwnd
; /* syn with cubic */
181 if (ca
->last_max_cwnd
<= cwnd
) {
183 ca
->bic_origin_point
= cwnd
;
185 /* Compute new K based on
186 * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ)
188 ca
->bic_K
= cubic_root(cube_factor
189 * (ca
->last_max_cwnd
- cwnd
));
190 ca
->bic_origin_point
= ca
->last_max_cwnd
;
194 /* cubic function - calc*/
195 /* calculate c * time^3 / rtt,
196 * while considering overflow in calculation of time^3
197 * (so time^3 is done by using 64 bit)
198 * and without the support of division of 64bit numbers
199 * (so all divisions are done by using 32 bit)
200 * also NOTE the unit of those veriables
201 * time = (t - K) / 2^bictcp_HZ
202 * c = bic_scale >> 10
203 * rtt = (srtt >> 3) / HZ
204 * !!! The following code does not have overflow problems,
205 * if the cwnd < 1 million packets !!!
208 /* change the unit from HZ to bictcp_HZ */
209 t
= ((tcp_time_stamp
+ ca
->delay_min
- ca
->epoch_start
)
212 if (t
< ca
->bic_K
) /* t - K */
213 offs
= ca
->bic_K
- t
;
215 offs
= t
- ca
->bic_K
;
217 /* c/rtt * (t-K)^3 */
218 delta
= (cube_rtt_scale
* offs
* offs
* offs
) >> (10+3*BICTCP_HZ
);
219 if (t
< ca
->bic_K
) /* below origin*/
220 bic_target
= ca
->bic_origin_point
- delta
;
221 else /* above origin*/
222 bic_target
= ca
->bic_origin_point
+ delta
;
224 /* cubic function - calc bictcp_cnt*/
225 if (bic_target
> cwnd
) {
226 ca
->cnt
= cwnd
/ (bic_target
- cwnd
);
228 ca
->cnt
= 100 * cwnd
; /* very small increment*/
231 if (ca
->delay_min
> 0) {
232 /* max increment = Smax * rtt / 0.1 */
233 min_cnt
= (cwnd
* HZ
* 8)/(10 * max_increment
* ca
->delay_min
);
234 if (ca
->cnt
< min_cnt
)
238 /* slow start and low utilization */
239 if (ca
->loss_cwnd
== 0) /* could be aggressive in slow start */
243 if (tcp_friendliness
) {
244 u32 scale
= beta_scale
;
245 delta
= (cwnd
* scale
) >> 3;
246 while (ca
->ack_cnt
> delta
) { /* update tcp cwnd */
247 ca
->ack_cnt
-= delta
;
251 if (ca
->tcp_cwnd
> cwnd
){ /* if bic is slower than tcp */
252 delta
= ca
->tcp_cwnd
- cwnd
;
253 max_cnt
= cwnd
/ delta
;
254 if (ca
->cnt
> max_cnt
)
259 ca
->cnt
= (ca
->cnt
<< ACK_RATIO_SHIFT
) / ca
->delayed_ack
;
260 if (ca
->cnt
== 0) /* cannot be zero */
265 /* Keep track of minimum rtt */
266 static inline void measure_delay(struct sock
*sk
)
268 const struct tcp_sock
*tp
= tcp_sk(sk
);
269 struct bictcp
*ca
= inet_csk_ca(sk
);
273 if (!(tp
->rx_opt
.saw_tstamp
&& tp
->rx_opt
.rcv_tsecr
) ||
274 /* Discard delay samples right after fast recovery */
275 (s32
)(tcp_time_stamp
- ca
->epoch_start
) < HZ
)
278 delay
= tcp_time_stamp
- tp
->rx_opt
.rcv_tsecr
;
282 /* first time call or link delay decreases */
283 if (ca
->delay_min
== 0 || ca
->delay_min
> delay
)
284 ca
->delay_min
= delay
;
287 static void bictcp_cong_avoid(struct sock
*sk
, u32 ack
,
288 u32 seq_rtt
, u32 in_flight
, int data_acked
)
290 struct tcp_sock
*tp
= tcp_sk(sk
);
291 struct bictcp
*ca
= inet_csk_ca(sk
);
296 if (!tcp_is_cwnd_limited(sk
, in_flight
))
299 if (tp
->snd_cwnd
<= tp
->snd_ssthresh
)
302 bictcp_update(ca
, tp
->snd_cwnd
);
304 /* In dangerous area, increase slowly.
305 * In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd
307 if (tp
->snd_cwnd_cnt
>= ca
->cnt
) {
308 if (tp
->snd_cwnd
< tp
->snd_cwnd_clamp
)
310 tp
->snd_cwnd_cnt
= 0;
317 static u32
bictcp_recalc_ssthresh(struct sock
*sk
)
319 const struct tcp_sock
*tp
= tcp_sk(sk
);
320 struct bictcp
*ca
= inet_csk_ca(sk
);
322 ca
->epoch_start
= 0; /* end of epoch */
324 /* Wmax and fast convergence */
325 if (tp
->snd_cwnd
< ca
->last_max_cwnd
&& fast_convergence
)
326 ca
->last_max_cwnd
= (tp
->snd_cwnd
* (BICTCP_BETA_SCALE
+ beta
))
327 / (2 * BICTCP_BETA_SCALE
);
329 ca
->last_max_cwnd
= tp
->snd_cwnd
;
331 ca
->loss_cwnd
= tp
->snd_cwnd
;
333 return max((tp
->snd_cwnd
* beta
) / BICTCP_BETA_SCALE
, 2U);
336 static u32
bictcp_undo_cwnd(struct sock
*sk
)
338 struct bictcp
*ca
= inet_csk_ca(sk
);
340 return max(tcp_sk(sk
)->snd_cwnd
, ca
->last_max_cwnd
);
343 static u32
bictcp_min_cwnd(struct sock
*sk
)
345 return tcp_sk(sk
)->snd_ssthresh
;
348 static void bictcp_state(struct sock
*sk
, u8 new_state
)
350 if (new_state
== TCP_CA_Loss
)
351 bictcp_reset(inet_csk_ca(sk
));
354 /* Track delayed acknowledgment ratio using sliding window
355 * ratio = (15*ratio + sample) / 16
357 static void bictcp_acked(struct sock
*sk
, u32 cnt
)
359 const struct inet_connection_sock
*icsk
= inet_csk(sk
);
361 if (cnt
> 0 && icsk
->icsk_ca_state
== TCP_CA_Open
) {
362 struct bictcp
*ca
= inet_csk_ca(sk
);
363 cnt
-= ca
->delayed_ack
>> ACK_RATIO_SHIFT
;
364 ca
->delayed_ack
+= cnt
;
369 static struct tcp_congestion_ops cubictcp
= {
371 .ssthresh
= bictcp_recalc_ssthresh
,
372 .cong_avoid
= bictcp_cong_avoid
,
373 .set_state
= bictcp_state
,
374 .undo_cwnd
= bictcp_undo_cwnd
,
375 .min_cwnd
= bictcp_min_cwnd
,
376 .pkts_acked
= bictcp_acked
,
377 .owner
= THIS_MODULE
,
381 static int __init
cubictcp_register(void)
383 BUG_ON(sizeof(struct bictcp
) > ICSK_CA_PRIV_SIZE
);
385 /* Precompute a bunch of the scaling factors that are used per-packet
386 * based on SRTT of 100ms
389 beta_scale
= 8*(BICTCP_BETA_SCALE
+beta
)/ 3 / (BICTCP_BETA_SCALE
- beta
);
391 cube_rtt_scale
= (bic_scale
<< 3) / 10; /* 1024*c/rtt */
393 /* calculate the "K" for (wmax-cwnd) = c/rtt * K^3
394 * so K = cubic_root( (wmax-cwnd)*rtt/c )
395 * the unit of K is bictcp_HZ=2^10, not HZ
397 * c = bic_scale >> 10
400 * the following code has been designed and tested for
401 * cwnd < 1 million packets
403 * HZ < 1,000,00 (corresponding to 10 nano-second)
406 /* 1/c * 2^2*bictcp_HZ * srtt */
407 cube_factor
= 1ull << (10+3*BICTCP_HZ
); /* 2^40 */
409 /* divide by bic_scale and by constant Srtt (100ms) */
410 do_div(cube_factor
, bic_scale
* 10);
412 return tcp_register_congestion_control(&cubictcp
);
415 static void __exit
cubictcp_unregister(void)
417 tcp_unregister_congestion_control(&cubictcp
);
420 module_init(cubictcp_register
);
421 module_exit(cubictcp_unregister
);
423 MODULE_AUTHOR("Sangtae Ha, Stephen Hemminger");
424 MODULE_LICENSE("GPL");
425 MODULE_DESCRIPTION("CUBIC TCP");
426 MODULE_VERSION("2.0");