Lines Matching +full:avg +full:- +full:samples
1 // SPDX-License-Identifier: GPL-2.0-only
8 * "CUBIC: A New TCP-Friendly High-Speed TCP Variant"
41 /* Number of delay samples for detecting the increase of delay */
62 /* Note parameters that are used for precomputing scale factors are read-only */
77 " 1: packet-train 2: delay 3: both packet-train and delay");
97 u8 sample_cnt; /* number of samples to decide curr_rtt */
108 ca->found = 0; in bictcp_reset()
113 return tcp_sk(sk)->tcp_mstamp; in bictcp_clock_us()
121 ca->round_start = ca->last_ack = bictcp_clock_us(sk); in bictcp_hystart_reset()
122 ca->end_seq = tp->snd_nxt; in bictcp_hystart_reset()
123 ca->curr_rtt = ~0U; in bictcp_hystart_reset()
124 ca->sample_cnt = 0; in bictcp_hystart_reset()
137 tcp_sk(sk)->snd_ssthresh = initial_ssthresh; in cubictcp_init()
147 delta = now - tcp_sk(sk)->lsndtime; in cubictcp_cwnd_event()
152 if (ca->epoch_start && delta > 0) { in cubictcp_cwnd_event()
153 ca->epoch_start += delta; in cubictcp_cwnd_event()
154 if (after(ca->epoch_start, now)) in cubictcp_cwnd_event()
155 ca->epoch_start = now; in cubictcp_cwnd_event()
162 * Newton-Raphson iteration.
163 * Avg err ~= 0.195%
170 * Precomputed then refined by hand - Willy Tarreau in cubic_root()
173 * v = cbrt(x << 18) - 1 in cubic_root()
193 b = ((b * 84) >> 8) - 1; in cubic_root()
199 * Newton-Raphson iteration in cubic_root()
204 x = (2 * x + (u32)div64_u64(a, (u64)x * (u64)(x - 1))); in cubic_root()
217 ca->ack_cnt += acked; /* count the number of ACKed packets */ in bictcp_update()
219 if (ca->last_cwnd == cwnd && in bictcp_update()
220 (s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32) in bictcp_update()
223 /* The CUBIC function can update ca->cnt at most once per jiffy. in bictcp_update()
224 * On all cwnd reduction events, ca->epoch_start is set to 0, in bictcp_update()
225 * which will force a recalculation of ca->cnt. in bictcp_update()
227 if (ca->epoch_start && tcp_jiffies32 == ca->last_time) in bictcp_update()
230 ca->last_cwnd = cwnd; in bictcp_update()
231 ca->last_time = tcp_jiffies32; in bictcp_update()
233 if (ca->epoch_start == 0) { in bictcp_update()
234 ca->epoch_start = tcp_jiffies32; /* record beginning */ in bictcp_update()
235 ca->ack_cnt = acked; /* start counting */ in bictcp_update()
236 ca->tcp_cwnd = cwnd; /* syn with cubic */ in bictcp_update()
238 if (ca->last_max_cwnd <= cwnd) { in bictcp_update()
239 ca->bic_K = 0; in bictcp_update()
240 ca->bic_origin_point = cwnd; in bictcp_update()
243 * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ) in bictcp_update()
245 ca->bic_K = cubic_root(cube_factor in bictcp_update()
246 * (ca->last_max_cwnd - cwnd)); in bictcp_update()
247 ca->bic_origin_point = ca->last_max_cwnd; in bictcp_update()
251 /* cubic function - calc*/ in bictcp_update()
258 * time = (t - K) / 2^bictcp_HZ in bictcp_update()
265 t = (s32)(tcp_jiffies32 - ca->epoch_start); in bictcp_update()
266 t += usecs_to_jiffies(ca->delay_min); in bictcp_update()
271 if (t < ca->bic_K) /* t - K */ in bictcp_update()
272 offs = ca->bic_K - t; in bictcp_update()
274 offs = t - ca->bic_K; in bictcp_update()
276 /* c/rtt * (t-K)^3 */ in bictcp_update()
278 if (t < ca->bic_K) /* below origin*/ in bictcp_update()
279 bic_target = ca->bic_origin_point - delta; in bictcp_update()
281 bic_target = ca->bic_origin_point + delta; in bictcp_update()
283 /* cubic function - calc bictcp_cnt*/ in bictcp_update()
285 ca->cnt = cwnd / (bic_target - cwnd); in bictcp_update()
287 ca->cnt = 100 * cwnd; /* very small increment*/ in bictcp_update()
294 if (ca->last_max_cwnd == 0 && ca->cnt > 20) in bictcp_update()
295 ca->cnt = 20; /* increase cwnd 5% per RTT */ in bictcp_update()
303 while (ca->ack_cnt > delta) { /* update tcp cwnd */ in bictcp_update()
304 ca->ack_cnt -= delta; in bictcp_update()
305 ca->tcp_cwnd++; in bictcp_update()
308 if (ca->tcp_cwnd > cwnd) { /* if bic is slower than tcp */ in bictcp_update()
309 delta = ca->tcp_cwnd - cwnd; in bictcp_update()
311 if (ca->cnt > max_cnt) in bictcp_update()
312 ca->cnt = max_cnt; in bictcp_update()
319 ca->cnt = max(ca->cnt, 2U); in bictcp_update()
331 if (hystart && after(ack, ca->end_seq)) in cubictcp_cong_avoid()
337 bictcp_update(ca, tp->snd_cwnd, acked); in cubictcp_cong_avoid()
338 tcp_cong_avoid_ai(tp, ca->cnt, acked); in cubictcp_cong_avoid()
346 ca->epoch_start = 0; /* end of epoch */ in cubictcp_recalc_ssthresh()
349 if (tp->snd_cwnd < ca->last_max_cwnd && fast_convergence) in cubictcp_recalc_ssthresh()
350 ca->last_max_cwnd = (tp->snd_cwnd * (BICTCP_BETA_SCALE + beta)) in cubictcp_recalc_ssthresh()
353 ca->last_max_cwnd = tp->snd_cwnd; in cubictcp_recalc_ssthresh()
355 return max((tp->snd_cwnd * beta) / BICTCP_BETA_SCALE, 2U); in cubictcp_recalc_ssthresh()
368 * slow start we begin with small TSO packets and ca->delay_min would
379 rate = READ_ONCE(sk->sk_pacing_rate); in hystart_ack_delay()
395 /* first detection parameter - ack-train detection */ in hystart_update()
396 if ((s32)(now - ca->last_ack) <= hystart_ack_delta_us) { in hystart_update()
397 ca->last_ack = now; in hystart_update()
399 threshold = ca->delay_min + hystart_ack_delay(sk); in hystart_update()
402 * ca->delay_min/2. in hystart_update()
406 if (sk->sk_pacing_status == SK_PACING_NONE) in hystart_update()
409 if ((s32)(now - ca->round_start) > threshold) { in hystart_update()
410 ca->found = 1; in hystart_update()
412 now - ca->round_start, threshold, in hystart_update()
413 ca->delay_min, hystart_ack_delay(sk), tp->snd_cwnd); in hystart_update()
418 tp->snd_cwnd); in hystart_update()
419 tp->snd_ssthresh = tp->snd_cwnd; in hystart_update()
426 if (ca->curr_rtt > delay) in hystart_update()
427 ca->curr_rtt = delay; in hystart_update()
428 if (ca->sample_cnt < HYSTART_MIN_SAMPLES) { in hystart_update()
429 ca->sample_cnt++; in hystart_update()
431 if (ca->curr_rtt > ca->delay_min + in hystart_update()
432 HYSTART_DELAY_THRESH(ca->delay_min >> 3)) { in hystart_update()
433 ca->found = 1; in hystart_update()
438 tp->snd_cwnd); in hystart_update()
439 tp->snd_ssthresh = tp->snd_cwnd; in hystart_update()
452 if (sample->rtt_us < 0) in cubictcp_acked()
455 /* Discard delay samples right after fast recovery */ in cubictcp_acked()
456 if (ca->epoch_start && (s32)(tcp_jiffies32 - ca->epoch_start) < HZ) in cubictcp_acked()
459 delay = sample->rtt_us; in cubictcp_acked()
464 if (ca->delay_min == 0 || ca->delay_min > delay) in cubictcp_acked()
465 ca->delay_min = delay; in cubictcp_acked()
468 if (!ca->found && tcp_in_slow_start(tp) && hystart && in cubictcp_acked()
469 tp->snd_cwnd >= hystart_low_window) in cubictcp_acked()
489 /* Precompute a bunch of the scaling factors that are used per-packet in cubictcp_register()
494 / (BICTCP_BETA_SCALE - beta); in cubictcp_register()
498 /* calculate the "K" for (wmax-cwnd) = c/rtt * K^3 in cubictcp_register()
499 * so K = cubic_root( (wmax-cwnd)*rtt/c ) in cubictcp_register()
508 * HZ < 1,000,00 (corresponding to 10 nano-second) in cubictcp_register()