1 /*
2 * ngtcp2
3 *
4 * Copyright (c) 2021 ngtcp2 contributors
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25 #include "ngtcp2_bbr2.h"
26
27 #include <assert.h>
28
29 #include "ngtcp2_log.h"
30 #include "ngtcp2_macro.h"
31 #include "ngtcp2_mem.h"
32 #include "ngtcp2_rcvry.h"
33 #include "ngtcp2_rst.h"
34
35 #define NGTCP2_BBR_MAX_BW_FILTERLEN 2
36
37 #define NGTCP2_BBR_EXTRA_ACKED_FILTERLEN 10
38
39 #define NGTCP2_BBR_STARTUP_PACING_GAIN ((double)2.77)
40
41 #define NGTCP2_BBR_STARTUP_CWND_GAIN 2
42
43 #define NGTCP2_BBR_PROBE_RTT_CWND_GAIN ((double)0.5)
44
45 #define NGTCP2_BBR_BETA_NUMER 7
46 #define NGTCP2_BBR_BETA_DENOM 10
47
48 #define NGTCP2_BBR_LOSS_THRESH_NUMER 2
49 #define NGTCP2_BBR_LOSS_THRESH_DENOM 100
50
51 #define NGTCP2_BBR_HEADROOM_NUMER 15
52 #define NGTCP2_BBR_HEADROOM_DENOM 100
53
54 #define NGTCP2_BBR_PROBE_RTT_INTERVAL (5 * NGTCP2_SECONDS)
55 #define NGTCP2_BBR_MIN_RTT_FILTERLEN (10 * NGTCP2_SECONDS)
56
57 #define NGTCP2_BBR_PROBE_RTT_DURATION (200 * NGTCP2_MILLISECONDS)
58
59 #define NGTCP2_BBR_PACING_MARGIN_PERCENT 1
60
61 static void bbr_on_init(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
62 ngtcp2_tstamp initial_ts);
63
64 static void bbr_on_transmit(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
65 ngtcp2_tstamp ts);
66
67 static void bbr_reset_congestion_signals(ngtcp2_bbr2_cc *bbr);
68
69 static void bbr_reset_lower_bounds(ngtcp2_bbr2_cc *bbr);
70
71 static void bbr_init_round_counting(ngtcp2_bbr2_cc *bbr);
72
73 static void bbr_init_full_pipe(ngtcp2_bbr2_cc *bbr);
74
75 static void bbr_init_pacing_rate(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat);
76
77 static void bbr_set_pacing_rate_with_gain(ngtcp2_bbr2_cc *bbr,
78 ngtcp2_conn_stat *cstat,
79 double pacing_gain);
80
81 static void bbr_set_pacing_rate(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat);
82
83 static void bbr_enter_startup(ngtcp2_bbr2_cc *bbr);
84
85 static void bbr_check_startup_done(ngtcp2_bbr2_cc *bbr,
86 const ngtcp2_cc_ack *ack);
87
88 static void bbr_update_on_ack(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
89 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts);
90
91 static void bbr_update_model_and_state(ngtcp2_bbr2_cc *cc,
92 ngtcp2_conn_stat *cstat,
93 const ngtcp2_cc_ack *ack,
94 ngtcp2_tstamp ts);
95
96 static void bbr_update_control_parameters(ngtcp2_bbr2_cc *cc,
97 ngtcp2_conn_stat *cstat,
98 const ngtcp2_cc_ack *ack);
99
100 static void bbr_update_on_loss(ngtcp2_bbr2_cc *cc, ngtcp2_conn_stat *cstat,
101 const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts);
102
103 static void bbr_update_latest_delivery_signals(ngtcp2_bbr2_cc *bbr,
104 ngtcp2_conn_stat *cstat);
105
106 static void bbr_advance_latest_delivery_signals(ngtcp2_bbr2_cc *bbr,
107 ngtcp2_conn_stat *cstat);
108
109 static void bbr_update_congestion_signals(ngtcp2_bbr2_cc *bbr,
110 ngtcp2_conn_stat *cstat,
111 const ngtcp2_cc_ack *ack);
112
113 static void bbr_adapt_lower_bounds_from_congestion(ngtcp2_bbr2_cc *bbr,
114 ngtcp2_conn_stat *cstat);
115
116 static void bbr_init_lower_bounds(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat);
117
118 static void bbr_loss_lower_bounds(ngtcp2_bbr2_cc *bbr);
119
120 static void bbr_bound_bw_for_model(ngtcp2_bbr2_cc *bbr);
121
122 static void bbr_update_max_bw(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
123 const ngtcp2_cc_ack *ack);
124
125 static void bbr_update_round(ngtcp2_bbr2_cc *bbr, const ngtcp2_cc_ack *ack);
126
127 static void bbr_start_round(ngtcp2_bbr2_cc *bbr);
128
129 static int bbr_is_in_probe_bw_state(ngtcp2_bbr2_cc *bbr);
130
131 static void bbr_update_ack_aggregation(ngtcp2_bbr2_cc *bbr,
132 ngtcp2_conn_stat *cstat,
133 const ngtcp2_cc_ack *ack,
134 ngtcp2_tstamp ts);
135
136 static void bbr_enter_drain(ngtcp2_bbr2_cc *bbr);
137
138 static void bbr_check_drain(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
139 ngtcp2_tstamp ts);
140
141 static void bbr_enter_probe_bw(ngtcp2_bbr2_cc *bbr, ngtcp2_tstamp ts);
142
143 static void bbr_start_probe_bw_down(ngtcp2_bbr2_cc *bbr, ngtcp2_tstamp ts);
144
145 static void bbr_start_probe_bw_cruise(ngtcp2_bbr2_cc *bbr);
146
147 static void bbr_start_probe_bw_refill(ngtcp2_bbr2_cc *bbr);
148
149 static void bbr_start_probe_bw_up(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
150 ngtcp2_tstamp ts);
151
152 static void bbr_update_probe_bw_cycle_phase(ngtcp2_bbr2_cc *bbr,
153 ngtcp2_conn_stat *cstat,
154 const ngtcp2_cc_ack *ack,
155 ngtcp2_tstamp ts);
156
157 static int bbr_check_time_to_cruise(ngtcp2_bbr2_cc *bbr,
158 ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts);
159
160 static int bbr_has_elapsed_in_phase(ngtcp2_bbr2_cc *bbr,
161 ngtcp2_duration interval, ngtcp2_tstamp ts);
162
163 static uint64_t bbr_inflight_with_headroom(ngtcp2_bbr2_cc *bbr,
164 ngtcp2_conn_stat *cstat);
165
166 static void bbr_raise_inflight_hi_slope(ngtcp2_bbr2_cc *bbr,
167 ngtcp2_conn_stat *cstat);
168
169 static void bbr_probe_inflight_hi_upward(ngtcp2_bbr2_cc *bbr,
170 ngtcp2_conn_stat *cstat,
171 const ngtcp2_cc_ack *ack);
172
173 static void bbr_adapt_upper_bounds(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
174 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts);
175
176 static int bbr_check_time_to_probe_bw(ngtcp2_bbr2_cc *bbr,
177 ngtcp2_conn_stat *cstat,
178 ngtcp2_tstamp ts);
179
180 static void bbr_pick_probe_wait(ngtcp2_bbr2_cc *bbr);
181
182 static int bbr_is_reno_coexistence_probe_time(ngtcp2_bbr2_cc *bbr,
183 ngtcp2_conn_stat *cstat);
184
185 static uint64_t bbr_target_inflight(ngtcp2_bbr2_cc *bbr,
186 ngtcp2_conn_stat *cstat);
187
188 static int bbr_check_inflight_too_high(ngtcp2_bbr2_cc *bbr,
189 ngtcp2_conn_stat *cstat,
190 ngtcp2_tstamp ts);
191
192 static int is_inflight_too_high(const ngtcp2_rs *rs);
193
194 static void bbr_handle_inflight_too_high(ngtcp2_bbr2_cc *bbr,
195 ngtcp2_conn_stat *cstat,
196 const ngtcp2_rs *rs, ngtcp2_tstamp ts);
197
198 static void bbr_handle_lost_packet(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
199 const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts);
200
201 static uint64_t bbr_inflight_hi_from_lost_packet(ngtcp2_bbr2_cc *bbr,
202 const ngtcp2_rs *rs,
203 const ngtcp2_cc_pkt *pkt);
204
205 static void bbr_update_min_rtt(ngtcp2_bbr2_cc *bbr, const ngtcp2_cc_ack *ack,
206 ngtcp2_tstamp ts);
207
208 static void bbr_check_probe_rtt(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
209 ngtcp2_tstamp ts);
210
211 static void bbr_enter_probe_rtt(ngtcp2_bbr2_cc *bbr);
212
213 static void bbr_handle_probe_rtt(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
214 ngtcp2_tstamp ts);
215
216 static void bbr_check_probe_rtt_done(ngtcp2_bbr2_cc *bbr,
217 ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts);
218
219 static void bbr_mark_connection_app_limited(ngtcp2_bbr2_cc *bbr,
220 ngtcp2_conn_stat *cstat);
221
222 static void bbr_exit_probe_rtt(ngtcp2_bbr2_cc *bbr, ngtcp2_tstamp ts);
223
224 static void bbr_handle_restart_from_idle(ngtcp2_bbr2_cc *bbr,
225 ngtcp2_conn_stat *cstat,
226 ngtcp2_tstamp ts);
227
228 static uint64_t bbr_bdp_multiple(ngtcp2_bbr2_cc *bbr, uint64_t bw, double gain);
229
230 static uint64_t bbr_quantization_budget(ngtcp2_bbr2_cc *bbr,
231 ngtcp2_conn_stat *cstat,
232 uint64_t inflight);
233
234 static uint64_t bbr_inflight(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
235 uint64_t bw, double gain);
236
237 static void bbr_update_max_inflight(ngtcp2_bbr2_cc *bbr,
238 ngtcp2_conn_stat *cstat);
239
240 static void bbr_update_offload_budget(ngtcp2_bbr2_cc *bbr,
241 ngtcp2_conn_stat *cstat);
242
243 static uint64_t min_pipe_cwnd(size_t max_udp_payload_size);
244
245 static void bbr_advance_max_bw_filter(ngtcp2_bbr2_cc *bbr);
246
247 static void bbr_modulate_cwnd_for_recovery(ngtcp2_bbr2_cc *bbr,
248 ngtcp2_conn_stat *cstat,
249 const ngtcp2_cc_ack *ack);
250
251 static void bbr_save_cwnd(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat);
252
253 static void bbr_restore_cwnd(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat);
254
255 static uint64_t bbr_probe_rtt_cwnd(ngtcp2_bbr2_cc *bbr,
256 ngtcp2_conn_stat *cstat);
257
258 static void bbr_bound_cwnd_for_probe_rtt(ngtcp2_bbr2_cc *bbr,
259 ngtcp2_conn_stat *cstat);
260
261 static void bbr_set_cwnd(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
262 const ngtcp2_cc_ack *ack);
263
264 static void bbr_bound_cwnd_for_model(ngtcp2_bbr2_cc *bbr,
265 ngtcp2_conn_stat *cstat);
266
267 static void bbr_set_send_quantum(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat);
268
269 static int in_congestion_recovery(const ngtcp2_conn_stat *cstat,
270 ngtcp2_tstamp sent_time);
271
272 static void bbr_handle_recovery(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
273 const ngtcp2_cc_ack *ack);
274
bbr_on_init(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp initial_ts)275 static void bbr_on_init(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
276 ngtcp2_tstamp initial_ts) {
277 ngtcp2_window_filter_init(&bbr->max_bw_filter, NGTCP2_BBR_MAX_BW_FILTERLEN);
278 ngtcp2_window_filter_init(&bbr->extra_acked_filter,
279 NGTCP2_BBR_EXTRA_ACKED_FILTERLEN);
280
281 bbr->min_rtt = UINT64_MAX;
282 bbr->min_rtt_stamp = initial_ts;
283 /* remark: Use UINT64_MAX instead of 0 for consistency. */
284 bbr->probe_rtt_done_stamp = UINT64_MAX;
285 bbr->probe_rtt_round_done = 0;
286 bbr->prior_cwnd = 0;
287 bbr->idle_restart = 0;
288 bbr->extra_acked_interval_start = initial_ts;
289 bbr->extra_acked_delivered = 0;
290
291 bbr_reset_congestion_signals(bbr);
292 bbr_reset_lower_bounds(bbr);
293 bbr_init_round_counting(bbr);
294 bbr_init_full_pipe(bbr);
295 bbr_init_pacing_rate(bbr, cstat);
296 bbr_enter_startup(bbr);
297
298 cstat->send_quantum = cstat->max_udp_payload_size * 10;
299
300 /* Missing in documentation */
301 bbr->loss_round_start = 0;
302 bbr->loss_round_delivered = UINT64_MAX;
303
304 bbr->rounds_since_bw_probe = 0;
305
306 bbr->max_bw = 0;
307 bbr->bw = 0;
308
309 bbr->cycle_count = 0;
310
311 bbr->extra_acked = 0;
312
313 bbr->bytes_lost_in_round = 0;
314 bbr->loss_events_in_round = 0;
315
316 bbr->offload_budget = 0;
317
318 bbr->probe_up_cnt = UINT64_MAX;
319 bbr->cycle_stamp = UINT64_MAX;
320 bbr->ack_phase = 0;
321 bbr->bw_probe_wait = 0;
322 bbr->bw_probe_samples = 0;
323 bbr->bw_probe_up_rounds = 0;
324 bbr->bw_probe_up_acks = 0;
325
326 bbr->inflight_hi = UINT64_MAX;
327 bbr->bw_hi = UINT64_MAX;
328
329 bbr->probe_rtt_expired = 0;
330 bbr->probe_rtt_min_delay = UINT64_MAX;
331 bbr->probe_rtt_min_stamp = initial_ts;
332
333 bbr->in_loss_recovery = 0;
334 bbr->packet_conservation = 0;
335
336 bbr->max_inflight = 0;
337
338 bbr->congestion_recovery_start_ts = UINT64_MAX;
339 bbr->congestion_recovery_next_round_delivered = 0;
340
341 bbr->prior_inflight_lo = 0;
342 bbr->prior_inflight_hi = 0;
343 bbr->prior_bw_lo = 0;
344 }
345
bbr_reset_congestion_signals(ngtcp2_bbr2_cc * bbr)346 static void bbr_reset_congestion_signals(ngtcp2_bbr2_cc *bbr) {
347 bbr->loss_in_round = 0;
348 bbr->bw_latest = 0;
349 bbr->inflight_latest = 0;
350 }
351
bbr_reset_lower_bounds(ngtcp2_bbr2_cc * bbr)352 static void bbr_reset_lower_bounds(ngtcp2_bbr2_cc *bbr) {
353 bbr->bw_lo = UINT64_MAX;
354 bbr->inflight_lo = UINT64_MAX;
355 }
356
bbr_init_round_counting(ngtcp2_bbr2_cc * bbr)357 static void bbr_init_round_counting(ngtcp2_bbr2_cc *bbr) {
358 bbr->next_round_delivered = 0;
359 bbr->round_start = 0;
360 bbr->round_count = 0;
361 }
362
bbr_init_full_pipe(ngtcp2_bbr2_cc * bbr)363 static void bbr_init_full_pipe(ngtcp2_bbr2_cc *bbr) {
364 bbr->filled_pipe = 0;
365 bbr->full_bw = 0;
366 bbr->full_bw_count = 0;
367 }
368
bbr_check_startup_full_bandwidth(ngtcp2_bbr2_cc * bbr)369 static void bbr_check_startup_full_bandwidth(ngtcp2_bbr2_cc *bbr) {
370 if (bbr->filled_pipe || !bbr->round_start || bbr->rst->rs.is_app_limited) {
371 return;
372 }
373
374 if (bbr->max_bw * 100 >= bbr->full_bw * 125) {
375 bbr->full_bw = bbr->max_bw;
376 bbr->full_bw_count = 0;
377 }
378
379 ++bbr->full_bw_count;
380
381 if (bbr->full_bw_count >= 3) {
382 bbr->filled_pipe = 1;
383
384 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV,
385 "bbr2 filled pipe, full_bw=%" PRIu64, bbr->full_bw);
386 }
387 }
388
bbr_check_startup_high_loss(ngtcp2_bbr2_cc * bbr,const ngtcp2_cc_ack * ack)389 static void bbr_check_startup_high_loss(ngtcp2_bbr2_cc *bbr,
390 const ngtcp2_cc_ack *ack) {
391 if (bbr->filled_pipe || !bbr->round_start || bbr->rst->rs.is_app_limited) {
392 return;
393 }
394
395 if (bbr->loss_events_in_round <= 3) {
396 return;
397 }
398
399 /* loss_thresh = 2% */
400 if (bbr->bytes_lost_in_round * 100 <= ack->prior_bytes_in_flight * 2) {
401 return;
402 }
403
404 bbr->filled_pipe = 1;
405 }
406
bbr_init_pacing_rate(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)407 static void bbr_init_pacing_rate(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat) {
408 double nominal_bandwidth = (double)bbr->initial_cwnd;
409
410 cstat->pacing_rate = NGTCP2_BBR_STARTUP_PACING_GAIN * nominal_bandwidth /
411 (double)NGTCP2_MILLISECONDS;
412 }
413
bbr_set_pacing_rate_with_gain(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,double pacing_gain)414 static void bbr_set_pacing_rate_with_gain(ngtcp2_bbr2_cc *bbr,
415 ngtcp2_conn_stat *cstat,
416 double pacing_gain) {
417 double rate = pacing_gain * (double)bbr->bw *
418 (100 - NGTCP2_BBR_PACING_MARGIN_PERCENT) / 100 / NGTCP2_SECONDS;
419
420 if (bbr->filled_pipe || rate > cstat->pacing_rate) {
421 cstat->pacing_rate = rate;
422 }
423 }
424
bbr_set_pacing_rate(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)425 static void bbr_set_pacing_rate(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat) {
426 bbr_set_pacing_rate_with_gain(bbr, cstat, bbr->pacing_gain);
427 }
428
bbr_enter_startup(ngtcp2_bbr2_cc * bbr)429 static void bbr_enter_startup(ngtcp2_bbr2_cc *bbr) {
430 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV, "bbr2 enter Startup");
431
432 bbr->state = NGTCP2_BBR2_STATE_STARTUP;
433 bbr->pacing_gain = NGTCP2_BBR_STARTUP_PACING_GAIN;
434 bbr->cwnd_gain = NGTCP2_BBR_STARTUP_CWND_GAIN;
435 }
436
bbr_check_startup_done(ngtcp2_bbr2_cc * bbr,const ngtcp2_cc_ack * ack)437 static void bbr_check_startup_done(ngtcp2_bbr2_cc *bbr,
438 const ngtcp2_cc_ack *ack) {
439 bbr_check_startup_full_bandwidth(bbr);
440 bbr_check_startup_high_loss(bbr, ack);
441
442 if (bbr->state == NGTCP2_BBR2_STATE_STARTUP && bbr->filled_pipe) {
443 bbr_enter_drain(bbr);
444 }
445 }
446
bbr_on_transmit(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)447 static void bbr_on_transmit(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
448 ngtcp2_tstamp ts) {
449 bbr_handle_restart_from_idle(bbr, cstat, ts);
450 }
451
bbr_update_on_ack(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)452 static void bbr_update_on_ack(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
453 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) {
454 bbr_update_model_and_state(bbr, cstat, ack, ts);
455 bbr_update_control_parameters(bbr, cstat, ack);
456 }
457
bbr_update_model_and_state(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)458 static void bbr_update_model_and_state(ngtcp2_bbr2_cc *bbr,
459 ngtcp2_conn_stat *cstat,
460 const ngtcp2_cc_ack *ack,
461 ngtcp2_tstamp ts) {
462 bbr_update_latest_delivery_signals(bbr, cstat);
463 bbr_update_congestion_signals(bbr, cstat, ack);
464 bbr_update_ack_aggregation(bbr, cstat, ack, ts);
465 bbr_check_startup_done(bbr, ack);
466 bbr_check_drain(bbr, cstat, ts);
467 bbr_update_probe_bw_cycle_phase(bbr, cstat, ack, ts);
468 bbr_update_min_rtt(bbr, ack, ts);
469 bbr_check_probe_rtt(bbr, cstat, ts);
470 bbr_advance_latest_delivery_signals(bbr, cstat);
471 bbr_bound_bw_for_model(bbr);
472 }
473
bbr_update_control_parameters(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack)474 static void bbr_update_control_parameters(ngtcp2_bbr2_cc *bbr,
475 ngtcp2_conn_stat *cstat,
476 const ngtcp2_cc_ack *ack) {
477 bbr_set_pacing_rate(bbr, cstat);
478 bbr_set_send_quantum(bbr, cstat);
479 bbr_set_cwnd(bbr, cstat, ack);
480 }
481
bbr_update_on_loss(ngtcp2_bbr2_cc * cc,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)482 static void bbr_update_on_loss(ngtcp2_bbr2_cc *cc, ngtcp2_conn_stat *cstat,
483 const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts) {
484 bbr_handle_lost_packet(cc, cstat, pkt, ts);
485 }
486
bbr_update_latest_delivery_signals(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)487 static void bbr_update_latest_delivery_signals(ngtcp2_bbr2_cc *bbr,
488 ngtcp2_conn_stat *cstat) {
489 bbr->loss_round_start = 0;
490 bbr->bw_latest = ngtcp2_max(bbr->bw_latest, cstat->delivery_rate_sec);
491 bbr->inflight_latest =
492 ngtcp2_max(bbr->inflight_latest, bbr->rst->rs.delivered);
493
494 if (bbr->rst->rs.prior_delivered >= bbr->loss_round_delivered) {
495 bbr->loss_round_delivered = bbr->rst->delivered;
496 bbr->loss_round_start = 1;
497 }
498 }
499
bbr_advance_latest_delivery_signals(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)500 static void bbr_advance_latest_delivery_signals(ngtcp2_bbr2_cc *bbr,
501 ngtcp2_conn_stat *cstat) {
502 if (bbr->loss_round_start) {
503 bbr->bw_latest = cstat->delivery_rate_sec;
504 bbr->inflight_latest = bbr->rst->rs.delivered;
505 }
506 }
507
bbr_update_congestion_signals(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack)508 static void bbr_update_congestion_signals(ngtcp2_bbr2_cc *bbr,
509 ngtcp2_conn_stat *cstat,
510 const ngtcp2_cc_ack *ack) {
511 bbr_update_max_bw(bbr, cstat, ack);
512
513 if (ack->bytes_lost) {
514 bbr->bytes_lost_in_round += ack->bytes_lost;
515 ++bbr->loss_events_in_round;
516
517 if (!bbr->loss_in_round) {
518 bbr->loss_in_round = 1;
519 bbr->loss_round_delivered = bbr->rst->delivered;
520 }
521 }
522
523 if (!bbr->loss_round_start) {
524 return;
525 }
526
527 bbr_adapt_lower_bounds_from_congestion(bbr, cstat);
528
529 bbr->loss_in_round = 0;
530 }
531
bbr_adapt_lower_bounds_from_congestion(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)532 static void bbr_adapt_lower_bounds_from_congestion(ngtcp2_bbr2_cc *bbr,
533 ngtcp2_conn_stat *cstat) {
534 if (!bbr->filled_pipe || bbr_is_in_probe_bw_state(bbr)) {
535 return;
536 }
537
538 if (bbr->loss_in_round) {
539 bbr_init_lower_bounds(bbr, cstat);
540 bbr_loss_lower_bounds(bbr);
541 }
542 }
543
bbr_init_lower_bounds(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)544 static void bbr_init_lower_bounds(ngtcp2_bbr2_cc *bbr,
545 ngtcp2_conn_stat *cstat) {
546 if (bbr->bw_lo == UINT64_MAX) {
547 bbr->bw_lo = bbr->max_bw;
548 }
549
550 if (bbr->inflight_lo == UINT64_MAX) {
551 bbr->inflight_lo = cstat->cwnd;
552 }
553 }
554
bbr_loss_lower_bounds(ngtcp2_bbr2_cc * bbr)555 static void bbr_loss_lower_bounds(ngtcp2_bbr2_cc *bbr) {
556 bbr->bw_lo = ngtcp2_max(bbr->bw_latest, bbr->bw_lo * NGTCP2_BBR_BETA_NUMER /
557 NGTCP2_BBR_BETA_DENOM);
558 bbr->inflight_lo = ngtcp2_max(bbr->inflight_latest,
559 bbr->inflight_lo * NGTCP2_BBR_BETA_NUMER /
560 NGTCP2_BBR_BETA_DENOM);
561 }
562
bbr_bound_bw_for_model(ngtcp2_bbr2_cc * bbr)563 static void bbr_bound_bw_for_model(ngtcp2_bbr2_cc *bbr) {
564 bbr->bw = ngtcp2_min(bbr->max_bw, bbr->bw_lo);
565 bbr->bw = ngtcp2_min(bbr->bw, bbr->bw_hi);
566 }
567
bbr_update_max_bw(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack)568 static void bbr_update_max_bw(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
569 const ngtcp2_cc_ack *ack) {
570 bbr_update_round(bbr, ack);
571 bbr_handle_recovery(bbr, cstat, ack);
572
573 if (cstat->delivery_rate_sec >= bbr->max_bw || !bbr->rst->rs.is_app_limited) {
574 ngtcp2_window_filter_update(&bbr->max_bw_filter, cstat->delivery_rate_sec,
575 bbr->cycle_count);
576
577 bbr->max_bw = ngtcp2_window_filter_get_best(&bbr->max_bw_filter);
578 }
579 }
580
bbr_update_round(ngtcp2_bbr2_cc * bbr,const ngtcp2_cc_ack * ack)581 static void bbr_update_round(ngtcp2_bbr2_cc *bbr, const ngtcp2_cc_ack *ack) {
582 if (ack->pkt_delivered >= bbr->next_round_delivered) {
583 bbr_start_round(bbr);
584
585 ++bbr->round_count;
586 ++bbr->rounds_since_bw_probe;
587 bbr->round_start = 1;
588
589 bbr->bytes_lost_in_round = 0;
590 bbr->loss_events_in_round = 0;
591
592 bbr->rst->is_cwnd_limited = 0;
593
594 return;
595 }
596
597 bbr->round_start = 0;
598 }
599
bbr_start_round(ngtcp2_bbr2_cc * bbr)600 static void bbr_start_round(ngtcp2_bbr2_cc *bbr) {
601 bbr->next_round_delivered = bbr->rst->delivered;
602 }
603
bbr_is_in_probe_bw_state(ngtcp2_bbr2_cc * bbr)604 static int bbr_is_in_probe_bw_state(ngtcp2_bbr2_cc *bbr) {
605 switch (bbr->state) {
606 case NGTCP2_BBR2_STATE_PROBE_BW_DOWN:
607 case NGTCP2_BBR2_STATE_PROBE_BW_CRUISE:
608 case NGTCP2_BBR2_STATE_PROBE_BW_REFILL:
609 case NGTCP2_BBR2_STATE_PROBE_BW_UP:
610 return 1;
611 default:
612 return 0;
613 }
614 }
615
bbr_update_ack_aggregation(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)616 static void bbr_update_ack_aggregation(ngtcp2_bbr2_cc *bbr,
617 ngtcp2_conn_stat *cstat,
618 const ngtcp2_cc_ack *ack,
619 ngtcp2_tstamp ts) {
620 ngtcp2_duration interval = ts - bbr->extra_acked_interval_start;
621 uint64_t expected_delivered = bbr->bw * interval / NGTCP2_SECONDS;
622 uint64_t extra;
623
624 if (bbr->extra_acked_delivered <= expected_delivered) {
625 bbr->extra_acked_delivered = 0;
626 bbr->extra_acked_interval_start = ts;
627 expected_delivered = 0;
628 }
629
630 bbr->extra_acked_delivered += ack->bytes_delivered;
631 extra = bbr->extra_acked_delivered - expected_delivered;
632 extra = ngtcp2_min(extra, cstat->cwnd);
633
634 ngtcp2_window_filter_update(&bbr->extra_acked_filter, extra,
635 bbr->round_count);
636
637 bbr->extra_acked = ngtcp2_window_filter_get_best(&bbr->extra_acked_filter);
638 }
639
bbr_enter_drain(ngtcp2_bbr2_cc * bbr)640 static void bbr_enter_drain(ngtcp2_bbr2_cc *bbr) {
641 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV, "bbr2 enter Drain");
642
643 bbr->state = NGTCP2_BBR2_STATE_DRAIN;
644 bbr->pacing_gain = 1. / NGTCP2_BBR_STARTUP_CWND_GAIN;
645 bbr->cwnd_gain = NGTCP2_BBR_STARTUP_CWND_GAIN;
646 }
647
bbr_check_drain(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)648 static void bbr_check_drain(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
649 ngtcp2_tstamp ts) {
650 if (bbr->state == NGTCP2_BBR2_STATE_DRAIN &&
651 cstat->bytes_in_flight <= bbr_inflight(bbr, cstat, bbr->bw, 1.0)) {
652 bbr_enter_probe_bw(bbr, ts);
653 }
654 }
655
bbr_enter_probe_bw(ngtcp2_bbr2_cc * bbr,ngtcp2_tstamp ts)656 static void bbr_enter_probe_bw(ngtcp2_bbr2_cc *bbr, ngtcp2_tstamp ts) {
657 bbr_start_probe_bw_down(bbr, ts);
658 }
659
bbr_start_probe_bw_down(ngtcp2_bbr2_cc * bbr,ngtcp2_tstamp ts)660 static void bbr_start_probe_bw_down(ngtcp2_bbr2_cc *bbr, ngtcp2_tstamp ts) {
661 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV,
662 "bbr2 start ProbeBW_DOWN");
663
664 bbr_reset_congestion_signals(bbr);
665
666 bbr->probe_up_cnt = UINT64_MAX;
667
668 bbr_pick_probe_wait(bbr);
669
670 bbr->cycle_stamp = ts;
671 bbr->ack_phase = NGTCP2_BBR2_ACK_PHASE_ACKS_PROBE_STOPPING;
672
673 bbr_start_round(bbr);
674
675 bbr->state = NGTCP2_BBR2_STATE_PROBE_BW_DOWN;
676 bbr->pacing_gain = 0.9;
677 bbr->cwnd_gain = 2;
678 }
679
bbr_start_probe_bw_cruise(ngtcp2_bbr2_cc * bbr)680 static void bbr_start_probe_bw_cruise(ngtcp2_bbr2_cc *bbr) {
681 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV,
682 "bbr2 start ProbeBW_CRUISE");
683
684 bbr->state = NGTCP2_BBR2_STATE_PROBE_BW_CRUISE;
685 bbr->pacing_gain = 1.0;
686 bbr->cwnd_gain = 2;
687 }
688
bbr_start_probe_bw_refill(ngtcp2_bbr2_cc * bbr)689 static void bbr_start_probe_bw_refill(ngtcp2_bbr2_cc *bbr) {
690 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV,
691 "bbr2 start ProbeBW_REFILL");
692
693 bbr_reset_lower_bounds(bbr);
694
695 bbr->bw_probe_up_rounds = 0;
696 bbr->bw_probe_up_acks = 0;
697 bbr->ack_phase = NGTCP2_BBR2_ACK_PHASE_ACKS_REFILLING;
698
699 bbr_start_round(bbr);
700
701 bbr->state = NGTCP2_BBR2_STATE_PROBE_BW_REFILL;
702 bbr->pacing_gain = 1.0;
703 bbr->cwnd_gain = 2;
704 }
705
bbr_start_probe_bw_up(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)706 static void bbr_start_probe_bw_up(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
707 ngtcp2_tstamp ts) {
708 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV, "bbr2 start ProbeBW_UP");
709
710 bbr->ack_phase = NGTCP2_BBR2_ACK_PHASE_ACKS_PROBE_STARTING;
711
712 bbr_start_round(bbr);
713
714 bbr->cycle_stamp = ts;
715 bbr->state = NGTCP2_BBR2_STATE_PROBE_BW_UP;
716 bbr->pacing_gain = 1.25;
717 bbr->cwnd_gain = 2;
718
719 bbr_raise_inflight_hi_slope(bbr, cstat);
720 }
721
bbr_update_probe_bw_cycle_phase(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)722 static void bbr_update_probe_bw_cycle_phase(ngtcp2_bbr2_cc *bbr,
723 ngtcp2_conn_stat *cstat,
724 const ngtcp2_cc_ack *ack,
725 ngtcp2_tstamp ts) {
726 if (!bbr->filled_pipe) {
727 return;
728 }
729
730 bbr_adapt_upper_bounds(bbr, cstat, ack, ts);
731
732 if (!bbr_is_in_probe_bw_state(bbr)) {
733 return;
734 }
735
736 switch (bbr->state) {
737 case NGTCP2_BBR2_STATE_PROBE_BW_DOWN:
738 if (bbr_check_time_to_probe_bw(bbr, cstat, ts)) {
739 return;
740 }
741
742 if (bbr_check_time_to_cruise(bbr, cstat, ts)) {
743 bbr_start_probe_bw_cruise(bbr);
744 }
745
746 break;
747 case NGTCP2_BBR2_STATE_PROBE_BW_CRUISE:
748 if (bbr_check_time_to_probe_bw(bbr, cstat, ts)) {
749 return;
750 }
751
752 break;
753 case NGTCP2_BBR2_STATE_PROBE_BW_REFILL:
754 if (bbr->round_start) {
755 bbr->bw_probe_samples = 1;
756 bbr_start_probe_bw_up(bbr, cstat, ts);
757 }
758
759 break;
760 case NGTCP2_BBR2_STATE_PROBE_BW_UP:
761 if (bbr_has_elapsed_in_phase(bbr, bbr->min_rtt, ts) &&
762 cstat->bytes_in_flight > bbr_inflight(bbr, cstat, bbr->max_bw, 1.25)) {
763 bbr_start_probe_bw_down(bbr, ts);
764 }
765
766 break;
767 default:
768 break;
769 }
770 }
771
bbr_check_time_to_cruise(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)772 static int bbr_check_time_to_cruise(ngtcp2_bbr2_cc *bbr,
773 ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts) {
774 (void)ts;
775
776 if (cstat->bytes_in_flight > bbr_inflight_with_headroom(bbr, cstat)) {
777 return 0;
778 }
779
780 if (cstat->bytes_in_flight <= bbr_inflight(bbr, cstat, bbr->max_bw, 1.0)) {
781 return 1;
782 }
783
784 return 0;
785 }
786
bbr_has_elapsed_in_phase(ngtcp2_bbr2_cc * bbr,ngtcp2_duration interval,ngtcp2_tstamp ts)787 static int bbr_has_elapsed_in_phase(ngtcp2_bbr2_cc *bbr,
788 ngtcp2_duration interval,
789 ngtcp2_tstamp ts) {
790 return ts > bbr->cycle_stamp + interval;
791 }
792
bbr_inflight_with_headroom(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)793 static uint64_t bbr_inflight_with_headroom(ngtcp2_bbr2_cc *bbr,
794 ngtcp2_conn_stat *cstat) {
795 uint64_t headroom;
796 uint64_t mpcwnd;
797 if (bbr->inflight_hi == UINT64_MAX) {
798 return UINT64_MAX;
799 }
800
801 headroom = ngtcp2_max(cstat->max_udp_payload_size,
802 bbr->inflight_hi * NGTCP2_BBR_HEADROOM_NUMER /
803 NGTCP2_BBR_HEADROOM_DENOM);
804 mpcwnd = min_pipe_cwnd(cstat->max_udp_payload_size);
805
806 if (bbr->inflight_hi > headroom) {
807 return ngtcp2_max(bbr->inflight_hi - headroom, mpcwnd);
808 }
809
810 return mpcwnd;
811 }
812
bbr_raise_inflight_hi_slope(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)813 static void bbr_raise_inflight_hi_slope(ngtcp2_bbr2_cc *bbr,
814 ngtcp2_conn_stat *cstat) {
815 uint64_t growth_this_round = cstat->max_udp_payload_size
816 << bbr->bw_probe_up_rounds;
817
818 bbr->bw_probe_up_rounds = ngtcp2_min(bbr->bw_probe_up_rounds + 1, 30);
819 bbr->probe_up_cnt = ngtcp2_max(cstat->cwnd / growth_this_round, 1) *
820 cstat->max_udp_payload_size;
821 }
822
bbr_probe_inflight_hi_upward(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack)823 static void bbr_probe_inflight_hi_upward(ngtcp2_bbr2_cc *bbr,
824 ngtcp2_conn_stat *cstat,
825 const ngtcp2_cc_ack *ack) {
826 uint64_t delta;
827
828 if (!bbr->rst->is_cwnd_limited || cstat->cwnd < bbr->inflight_hi) {
829 return;
830 }
831
832 bbr->bw_probe_up_acks += ack->bytes_delivered;
833
834 if (bbr->bw_probe_up_acks >= bbr->probe_up_cnt) {
835 delta = bbr->bw_probe_up_acks / bbr->probe_up_cnt;
836 bbr->bw_probe_up_acks -= delta * bbr->probe_up_cnt;
837 bbr->inflight_hi += delta * cstat->max_udp_payload_size;
838 }
839
840 if (bbr->round_start) {
841 bbr_raise_inflight_hi_slope(bbr, cstat);
842 }
843 }
844
bbr_adapt_upper_bounds(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)845 static void bbr_adapt_upper_bounds(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
846 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) {
847 if (bbr->ack_phase == NGTCP2_BBR2_ACK_PHASE_ACKS_PROBE_STARTING &&
848 bbr->round_start) {
849 bbr->ack_phase = NGTCP2_BBR2_ACK_PHASE_ACKS_PROBE_FEEDBACK;
850 }
851
852 if (bbr->ack_phase == NGTCP2_BBR2_ACK_PHASE_ACKS_PROBE_STOPPING &&
853 bbr->round_start) {
854 if (bbr_is_in_probe_bw_state(bbr) && !bbr->rst->rs.is_app_limited) {
855 bbr_advance_max_bw_filter(bbr);
856 }
857 }
858
859 if (!bbr_check_inflight_too_high(bbr, cstat, ts)) {
860 /* bbr->bw_hi never be updated */
861 if (bbr->inflight_hi == UINT64_MAX /* || bbr->bw_hi == UINT64_MAX */) {
862 return;
863 }
864
865 if (bbr->rst->rs.tx_in_flight > bbr->inflight_hi) {
866 bbr->inflight_hi = bbr->rst->rs.tx_in_flight;
867 }
868
869 if (cstat->delivery_rate_sec > bbr->bw_hi) {
870 bbr->bw_hi = cstat->delivery_rate_sec;
871 }
872
873 if (bbr->state == NGTCP2_BBR2_STATE_PROBE_BW_UP) {
874 bbr_probe_inflight_hi_upward(bbr, cstat, ack);
875 }
876 }
877 }
878
bbr_check_time_to_probe_bw(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)879 static int bbr_check_time_to_probe_bw(ngtcp2_bbr2_cc *bbr,
880 ngtcp2_conn_stat *cstat,
881 ngtcp2_tstamp ts) {
882 if (bbr_has_elapsed_in_phase(bbr, bbr->bw_probe_wait, ts) ||
883 bbr_is_reno_coexistence_probe_time(bbr, cstat)) {
884 bbr_start_probe_bw_refill(bbr);
885
886 return 1;
887 }
888
889 return 0;
890 }
891
bbr_pick_probe_wait(ngtcp2_bbr2_cc * bbr)892 static void bbr_pick_probe_wait(ngtcp2_bbr2_cc *bbr) {
893 uint8_t rand;
894
895 bbr->rand(&rand, 1, &bbr->rand_ctx);
896
897 bbr->rounds_since_bw_probe = (uint64_t)(rand * 2 / 256);
898
899 bbr->rand(&rand, 1, &bbr->rand_ctx);
900
901 bbr->bw_probe_wait = 2 * NGTCP2_SECONDS +
902 (ngtcp2_tstamp)((double)rand / 255. * NGTCP2_SECONDS);
903 }
904
bbr_is_reno_coexistence_probe_time(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)905 static int bbr_is_reno_coexistence_probe_time(ngtcp2_bbr2_cc *bbr,
906 ngtcp2_conn_stat *cstat) {
907 uint64_t reno_rounds =
908 bbr_target_inflight(bbr, cstat) / cstat->max_udp_payload_size;
909
910 return bbr->rounds_since_bw_probe >= ngtcp2_min(reno_rounds, 63);
911 }
912
bbr_target_inflight(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)913 static uint64_t bbr_target_inflight(ngtcp2_bbr2_cc *bbr,
914 ngtcp2_conn_stat *cstat) {
915 uint64_t bdp = bbr_inflight(bbr, cstat, bbr->bw, 1.0);
916
917 return ngtcp2_min(bdp, cstat->cwnd);
918 }
919
bbr_check_inflight_too_high(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)920 static int bbr_check_inflight_too_high(ngtcp2_bbr2_cc *bbr,
921 ngtcp2_conn_stat *cstat,
922 ngtcp2_tstamp ts) {
923 if (is_inflight_too_high(&bbr->rst->rs)) {
924 if (bbr->bw_probe_samples) {
925 bbr_handle_inflight_too_high(bbr, cstat, &bbr->rst->rs, ts);
926 }
927
928 return 1;
929 }
930
931 return 0;
932 }
933
is_inflight_too_high(const ngtcp2_rs * rs)934 static int is_inflight_too_high(const ngtcp2_rs *rs) {
935 return rs->lost * NGTCP2_BBR_LOSS_THRESH_DENOM >
936 rs->tx_in_flight * NGTCP2_BBR_LOSS_THRESH_NUMER;
937 }
938
bbr_handle_inflight_too_high(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_rs * rs,ngtcp2_tstamp ts)939 static void bbr_handle_inflight_too_high(ngtcp2_bbr2_cc *bbr,
940 ngtcp2_conn_stat *cstat,
941 const ngtcp2_rs *rs,
942 ngtcp2_tstamp ts) {
943 bbr->bw_probe_samples = 0;
944
945 if (!rs->is_app_limited) {
946 bbr->prior_inflight_hi = bbr->inflight_hi;
947
948 bbr->inflight_hi = ngtcp2_max(
949 rs->tx_in_flight, bbr_target_inflight(bbr, cstat) *
950 NGTCP2_BBR_BETA_NUMER / NGTCP2_BBR_BETA_DENOM);
951 }
952
953 if (bbr->state == NGTCP2_BBR2_STATE_PROBE_BW_UP) {
954 bbr_start_probe_bw_down(bbr, ts);
955 }
956 }
957
bbr_handle_lost_packet(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)958 static void bbr_handle_lost_packet(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
959 const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts) {
960 ngtcp2_rs rs = {0};
961
962 if (!bbr->bw_probe_samples) {
963 return;
964 }
965
966 rs.tx_in_flight = pkt->tx_in_flight;
967 rs.lost = bbr->rst->lost - pkt->lost;
968 rs.is_app_limited = pkt->is_app_limited;
969
970 if (is_inflight_too_high(&rs)) {
971 rs.tx_in_flight = bbr_inflight_hi_from_lost_packet(bbr, &rs, pkt);
972
973 bbr_handle_inflight_too_high(bbr, cstat, &rs, ts);
974 }
975 }
976
bbr_inflight_hi_from_lost_packet(ngtcp2_bbr2_cc * bbr,const ngtcp2_rs * rs,const ngtcp2_cc_pkt * pkt)977 static uint64_t bbr_inflight_hi_from_lost_packet(ngtcp2_bbr2_cc *bbr,
978 const ngtcp2_rs *rs,
979 const ngtcp2_cc_pkt *pkt) {
980 uint64_t inflight_prev, lost_prefix;
981 (void)bbr;
982
983 assert(rs->tx_in_flight >= pkt->pktlen);
984
985 inflight_prev = rs->tx_in_flight - pkt->pktlen;
986
987 assert(rs->lost >= pkt->pktlen);
988
989 /* bbr->rst->lost is not incremented for pkt yet */
990
991 if (inflight_prev * NGTCP2_BBR_LOSS_THRESH_NUMER <
992 rs->lost * NGTCP2_BBR_LOSS_THRESH_DENOM) {
993 return inflight_prev;
994 }
995
996 lost_prefix = (inflight_prev * NGTCP2_BBR_LOSS_THRESH_NUMER -
997 rs->lost * NGTCP2_BBR_LOSS_THRESH_DENOM) /
998 (NGTCP2_BBR_LOSS_THRESH_DENOM - NGTCP2_BBR_LOSS_THRESH_NUMER);
999
1000 return inflight_prev + lost_prefix;
1001 }
1002
bbr_update_min_rtt(ngtcp2_bbr2_cc * bbr,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)1003 static void bbr_update_min_rtt(ngtcp2_bbr2_cc *bbr, const ngtcp2_cc_ack *ack,
1004 ngtcp2_tstamp ts) {
1005 int min_rtt_expired;
1006
1007 bbr->probe_rtt_expired =
1008 ts > bbr->probe_rtt_min_stamp + NGTCP2_BBR_PROBE_RTT_INTERVAL;
1009
1010 if (ack->rtt != UINT64_MAX &&
1011 (ack->rtt < bbr->probe_rtt_min_delay || bbr->probe_rtt_expired)) {
1012 bbr->probe_rtt_min_delay = ack->rtt;
1013 bbr->probe_rtt_min_stamp = ts;
1014 }
1015
1016 min_rtt_expired = ts > bbr->min_rtt_stamp + NGTCP2_BBR_MIN_RTT_FILTERLEN;
1017
1018 if (bbr->probe_rtt_min_delay < bbr->min_rtt || min_rtt_expired) {
1019 bbr->min_rtt = bbr->probe_rtt_min_delay;
1020 bbr->min_rtt_stamp = bbr->probe_rtt_min_stamp;
1021
1022 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV,
1023 "bbr2 update min_rtt=%" PRIu64, bbr->min_rtt);
1024 }
1025 }
1026
bbr_check_probe_rtt(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1027 static void bbr_check_probe_rtt(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
1028 ngtcp2_tstamp ts) {
1029 if (bbr->state != NGTCP2_BBR2_STATE_PROBE_RTT && bbr->probe_rtt_expired &&
1030 !bbr->idle_restart) {
1031 bbr_enter_probe_rtt(bbr);
1032 bbr_save_cwnd(bbr, cstat);
1033
1034 bbr->probe_rtt_done_stamp = UINT64_MAX;
1035 bbr->ack_phase = NGTCP2_BBR2_ACK_PHASE_ACKS_PROBE_STOPPING;
1036
1037 bbr_start_round(bbr);
1038 }
1039
1040 if (bbr->state == NGTCP2_BBR2_STATE_PROBE_RTT) {
1041 bbr_handle_probe_rtt(bbr, cstat, ts);
1042 }
1043
1044 if (bbr->rst->rs.delivered) {
1045 bbr->idle_restart = 0;
1046 }
1047 }
1048
bbr_enter_probe_rtt(ngtcp2_bbr2_cc * bbr)1049 static void bbr_enter_probe_rtt(ngtcp2_bbr2_cc *bbr) {
1050 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV, "bbr2 enter ProbeRTT");
1051
1052 bbr->state = NGTCP2_BBR2_STATE_PROBE_RTT;
1053 bbr->pacing_gain = 1;
1054 bbr->cwnd_gain = NGTCP2_BBR_PROBE_RTT_CWND_GAIN;
1055 }
1056
bbr_handle_probe_rtt(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1057 static void bbr_handle_probe_rtt(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
1058 ngtcp2_tstamp ts) {
1059 bbr_mark_connection_app_limited(bbr, cstat);
1060
1061 if (bbr->probe_rtt_done_stamp == UINT64_MAX &&
1062 cstat->bytes_in_flight <= bbr_probe_rtt_cwnd(bbr, cstat)) {
1063 bbr->probe_rtt_done_stamp = ts + NGTCP2_BBR_PROBE_RTT_DURATION;
1064 bbr->probe_rtt_round_done = 0;
1065
1066 bbr_start_round(bbr);
1067
1068 return;
1069 }
1070
1071 if (bbr->probe_rtt_done_stamp != UINT64_MAX) {
1072 if (bbr->round_start) {
1073 bbr->probe_rtt_round_done = 1;
1074 }
1075
1076 if (bbr->probe_rtt_round_done) {
1077 bbr_check_probe_rtt_done(bbr, cstat, ts);
1078 }
1079 }
1080 }
1081
bbr_check_probe_rtt_done(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1082 static void bbr_check_probe_rtt_done(ngtcp2_bbr2_cc *bbr,
1083 ngtcp2_conn_stat *cstat,
1084 ngtcp2_tstamp ts) {
1085 if (bbr->probe_rtt_done_stamp != UINT64_MAX &&
1086 ts > bbr->probe_rtt_done_stamp) {
1087 bbr->probe_rtt_min_stamp = ts;
1088 bbr_restore_cwnd(bbr, cstat);
1089 bbr_exit_probe_rtt(bbr, ts);
1090 }
1091 }
1092
bbr_mark_connection_app_limited(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1093 static void bbr_mark_connection_app_limited(ngtcp2_bbr2_cc *bbr,
1094 ngtcp2_conn_stat *cstat) {
1095 uint64_t app_limited = bbr->rst->delivered + cstat->bytes_in_flight;
1096
1097 if (app_limited) {
1098 bbr->rst->app_limited = app_limited;
1099 } else {
1100 bbr->rst->app_limited = cstat->max_udp_payload_size;
1101 }
1102 }
1103
bbr_exit_probe_rtt(ngtcp2_bbr2_cc * bbr,ngtcp2_tstamp ts)1104 static void bbr_exit_probe_rtt(ngtcp2_bbr2_cc *bbr, ngtcp2_tstamp ts) {
1105 bbr_reset_lower_bounds(bbr);
1106
1107 if (bbr->filled_pipe) {
1108 bbr_start_probe_bw_down(bbr, ts);
1109 bbr_start_probe_bw_cruise(bbr);
1110 } else {
1111 bbr_enter_startup(bbr);
1112 }
1113 }
1114
bbr_handle_restart_from_idle(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1115 static void bbr_handle_restart_from_idle(ngtcp2_bbr2_cc *bbr,
1116 ngtcp2_conn_stat *cstat,
1117 ngtcp2_tstamp ts) {
1118 if (cstat->bytes_in_flight == 0 && bbr->rst->app_limited) {
1119 ngtcp2_log_info(bbr->ccb.log, NGTCP2_LOG_EVENT_RCV,
1120 "bbr2 restart from idle");
1121
1122 bbr->idle_restart = 1;
1123 bbr->extra_acked_interval_start = ts;
1124
1125 if (bbr_is_in_probe_bw_state(bbr)) {
1126 bbr_set_pacing_rate_with_gain(bbr, cstat, 1);
1127 } else if (bbr->state == NGTCP2_BBR2_STATE_PROBE_RTT) {
1128 bbr_check_probe_rtt_done(bbr, cstat, ts);
1129 }
1130 }
1131 }
1132
bbr_bdp_multiple(ngtcp2_bbr2_cc * bbr,uint64_t bw,double gain)1133 static uint64_t bbr_bdp_multiple(ngtcp2_bbr2_cc *bbr, uint64_t bw,
1134 double gain) {
1135 uint64_t bdp;
1136
1137 if (bbr->min_rtt == UINT64_MAX) {
1138 return bbr->initial_cwnd;
1139 }
1140
1141 bdp = bw * bbr->min_rtt / NGTCP2_SECONDS;
1142
1143 return (uint64_t)(gain * (double)bdp);
1144 }
1145
min_pipe_cwnd(size_t max_udp_payload_size)1146 static uint64_t min_pipe_cwnd(size_t max_udp_payload_size) {
1147 return max_udp_payload_size * 4;
1148 }
1149
bbr_quantization_budget(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,uint64_t inflight)1150 static uint64_t bbr_quantization_budget(ngtcp2_bbr2_cc *bbr,
1151 ngtcp2_conn_stat *cstat,
1152 uint64_t inflight) {
1153 bbr_update_offload_budget(bbr, cstat);
1154
1155 inflight = ngtcp2_max(inflight, bbr->offload_budget);
1156 inflight = ngtcp2_max(inflight, min_pipe_cwnd(cstat->max_udp_payload_size));
1157
1158 if (bbr->state == NGTCP2_BBR2_STATE_PROBE_BW_UP) {
1159 inflight += 2 * cstat->max_udp_payload_size;
1160 }
1161
1162 return inflight;
1163 }
1164
bbr_inflight(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,uint64_t bw,double gain)1165 static uint64_t bbr_inflight(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
1166 uint64_t bw, double gain) {
1167 uint64_t inflight = bbr_bdp_multiple(bbr, bw, gain);
1168
1169 return bbr_quantization_budget(bbr, cstat, inflight);
1170 }
1171
bbr_update_max_inflight(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1172 static void bbr_update_max_inflight(ngtcp2_bbr2_cc *bbr,
1173 ngtcp2_conn_stat *cstat) {
1174 uint64_t inflight;
1175
1176 /* Not documented */
1177 /* bbr_update_aggregation_budget(bbr); */
1178
1179 inflight = bbr_bdp_multiple(bbr, bbr->bw, bbr->cwnd_gain) + bbr->extra_acked;
1180 bbr->max_inflight = bbr_quantization_budget(bbr, cstat, inflight);
1181 }
1182
bbr_update_offload_budget(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1183 static void bbr_update_offload_budget(ngtcp2_bbr2_cc *bbr,
1184 ngtcp2_conn_stat *cstat) {
1185 bbr->offload_budget = 3 * cstat->send_quantum;
1186 }
1187
bbr_advance_max_bw_filter(ngtcp2_bbr2_cc * bbr)1188 static void bbr_advance_max_bw_filter(ngtcp2_bbr2_cc *bbr) {
1189 ++bbr->cycle_count;
1190 }
1191
bbr_modulate_cwnd_for_recovery(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack)1192 static void bbr_modulate_cwnd_for_recovery(ngtcp2_bbr2_cc *bbr,
1193 ngtcp2_conn_stat *cstat,
1194 const ngtcp2_cc_ack *ack) {
1195 if (ack->bytes_lost > 0) {
1196 if (cstat->cwnd > ack->bytes_lost) {
1197 cstat->cwnd -= ack->bytes_lost;
1198 cstat->cwnd = ngtcp2_max(cstat->cwnd, 2 * cstat->max_udp_payload_size);
1199 } else {
1200 cstat->cwnd = cstat->max_udp_payload_size;
1201 }
1202 }
1203
1204 if (bbr->packet_conservation) {
1205 cstat->cwnd =
1206 ngtcp2_max(cstat->cwnd, cstat->bytes_in_flight + ack->bytes_delivered);
1207 }
1208 }
1209
bbr_save_cwnd(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1210 static void bbr_save_cwnd(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat) {
1211 if (!bbr->in_loss_recovery && bbr->state != NGTCP2_BBR2_STATE_PROBE_RTT) {
1212 bbr->prior_cwnd = cstat->cwnd;
1213 return;
1214 }
1215
1216 bbr->prior_cwnd = ngtcp2_max(bbr->prior_cwnd, cstat->cwnd);
1217 }
1218
bbr_restore_cwnd(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1219 static void bbr_restore_cwnd(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat) {
1220 cstat->cwnd = ngtcp2_max(cstat->cwnd, bbr->prior_cwnd);
1221 }
1222
bbr_probe_rtt_cwnd(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1223 static uint64_t bbr_probe_rtt_cwnd(ngtcp2_bbr2_cc *bbr,
1224 ngtcp2_conn_stat *cstat) {
1225 uint64_t probe_rtt_cwnd =
1226 bbr_bdp_multiple(bbr, bbr->bw, NGTCP2_BBR_PROBE_RTT_CWND_GAIN);
1227 uint64_t mpcwnd = min_pipe_cwnd(cstat->max_udp_payload_size);
1228
1229 return ngtcp2_max(probe_rtt_cwnd, mpcwnd);
1230 }
1231
bbr_bound_cwnd_for_probe_rtt(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1232 static void bbr_bound_cwnd_for_probe_rtt(ngtcp2_bbr2_cc *bbr,
1233 ngtcp2_conn_stat *cstat) {
1234 uint64_t probe_rtt_cwnd;
1235
1236 if (bbr->state == NGTCP2_BBR2_STATE_PROBE_RTT) {
1237 probe_rtt_cwnd = bbr_probe_rtt_cwnd(bbr, cstat);
1238
1239 cstat->cwnd = ngtcp2_min(cstat->cwnd, probe_rtt_cwnd);
1240 }
1241 }
1242
bbr_set_cwnd(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack)1243 static void bbr_set_cwnd(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
1244 const ngtcp2_cc_ack *ack) {
1245 uint64_t mpcwnd;
1246
1247 bbr_update_max_inflight(bbr, cstat);
1248 bbr_modulate_cwnd_for_recovery(bbr, cstat, ack);
1249
1250 if (!bbr->packet_conservation) {
1251 if (bbr->filled_pipe) {
1252 cstat->cwnd += ack->bytes_delivered;
1253 cstat->cwnd = ngtcp2_min(cstat->cwnd, bbr->max_inflight);
1254 } else if (cstat->cwnd < bbr->max_inflight ||
1255 bbr->rst->delivered < bbr->initial_cwnd) {
1256 cstat->cwnd += ack->bytes_delivered;
1257 }
1258
1259 mpcwnd = min_pipe_cwnd(cstat->max_udp_payload_size);
1260 cstat->cwnd = ngtcp2_max(cstat->cwnd, mpcwnd);
1261 }
1262
1263 bbr_bound_cwnd_for_probe_rtt(bbr, cstat);
1264 bbr_bound_cwnd_for_model(bbr, cstat);
1265 }
1266
bbr_bound_cwnd_for_model(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1267 static void bbr_bound_cwnd_for_model(ngtcp2_bbr2_cc *bbr,
1268 ngtcp2_conn_stat *cstat) {
1269 uint64_t cap = UINT64_MAX;
1270 uint64_t mpcwnd = min_pipe_cwnd(cstat->max_udp_payload_size);
1271
1272 if (bbr_is_in_probe_bw_state(bbr) &&
1273 bbr->state != NGTCP2_BBR2_STATE_PROBE_BW_CRUISE) {
1274 cap = bbr->inflight_hi;
1275 } else if (bbr->state == NGTCP2_BBR2_STATE_PROBE_RTT ||
1276 bbr->state == NGTCP2_BBR2_STATE_PROBE_BW_CRUISE) {
1277 cap = bbr_inflight_with_headroom(bbr, cstat);
1278 }
1279
1280 cap = ngtcp2_min(cap, bbr->inflight_lo);
1281 cap = ngtcp2_max(cap, mpcwnd);
1282
1283 cstat->cwnd = ngtcp2_min(cstat->cwnd, cap);
1284 }
1285
bbr_set_send_quantum(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat)1286 static void bbr_set_send_quantum(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat) {
1287 size_t send_quantum =
1288 (size_t)(cstat->pacing_rate * (double)(bbr->min_rtt == UINT64_MAX
1289 ? NGTCP2_MILLISECONDS
1290 : bbr->min_rtt));
1291 (void)bbr;
1292
1293 cstat->send_quantum = ngtcp2_min(send_quantum, 64 * 1024);
1294 cstat->send_quantum =
1295 ngtcp2_max(cstat->send_quantum, cstat->max_udp_payload_size * 10);
1296 }
1297
in_congestion_recovery(const ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_time)1298 static int in_congestion_recovery(const ngtcp2_conn_stat *cstat,
1299 ngtcp2_tstamp sent_time) {
1300 return cstat->congestion_recovery_start_ts != UINT64_MAX &&
1301 sent_time <= cstat->congestion_recovery_start_ts;
1302 }
1303
bbr_handle_recovery(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack)1304 static void bbr_handle_recovery(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
1305 const ngtcp2_cc_ack *ack) {
1306 if (bbr->in_loss_recovery) {
1307 if (ack->pkt_delivered >= bbr->congestion_recovery_next_round_delivered) {
1308 bbr->packet_conservation = 0;
1309 }
1310
1311 if (!in_congestion_recovery(cstat, ack->largest_acked_sent_ts)) {
1312 bbr->in_loss_recovery = 0;
1313 bbr->packet_conservation = 0;
1314 bbr_restore_cwnd(bbr, cstat);
1315 }
1316
1317 return;
1318 }
1319
1320 if (bbr->congestion_recovery_start_ts != UINT64_MAX) {
1321 bbr->in_loss_recovery = 1;
1322 bbr_save_cwnd(bbr, cstat);
1323 cstat->cwnd = cstat->bytes_in_flight +
1324 ngtcp2_max(ack->bytes_delivered, cstat->max_udp_payload_size);
1325
1326 cstat->congestion_recovery_start_ts = bbr->congestion_recovery_start_ts;
1327 bbr->congestion_recovery_start_ts = UINT64_MAX;
1328 bbr->packet_conservation = 1;
1329 bbr->congestion_recovery_next_round_delivered = bbr->rst->delivered;
1330 bbr->prior_inflight_lo = bbr->inflight_lo;
1331 bbr->prior_bw_lo = bbr->bw_lo;
1332 }
1333 }
1334
bbr2_cc_init(ngtcp2_bbr2_cc * bbr,ngtcp2_conn_stat * cstat,ngtcp2_rst * rst,ngtcp2_tstamp initial_ts,ngtcp2_rand rand,const ngtcp2_rand_ctx * rand_ctx,ngtcp2_log * log)1335 static void bbr2_cc_init(ngtcp2_bbr2_cc *bbr, ngtcp2_conn_stat *cstat,
1336 ngtcp2_rst *rst, ngtcp2_tstamp initial_ts,
1337 ngtcp2_rand rand, const ngtcp2_rand_ctx *rand_ctx,
1338 ngtcp2_log *log) {
1339 bbr->ccb.log = log;
1340 bbr->rst = rst;
1341 bbr->rand = rand;
1342 bbr->rand_ctx = *rand_ctx;
1343 bbr->initial_cwnd = cstat->cwnd;
1344
1345 bbr_on_init(bbr, cstat, initial_ts);
1346 }
1347
bbr2_cc_free(ngtcp2_bbr2_cc * bbr)1348 static void bbr2_cc_free(ngtcp2_bbr2_cc *bbr) { (void)bbr; }
1349
bbr2_cc_on_pkt_acked(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)1350 static void bbr2_cc_on_pkt_acked(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1351 const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts) {
1352 (void)ccx;
1353 (void)cstat;
1354 (void)pkt;
1355 (void)ts;
1356 }
1357
bbr2_cc_on_pkt_lost(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)1358 static void bbr2_cc_on_pkt_lost(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1359 const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts) {
1360 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(ccx->ccb, ngtcp2_bbr2_cc, ccb);
1361
1362 bbr_update_on_loss(bbr, cstat, pkt, ts);
1363 }
1364
bbr2_cc_congestion_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_ts,ngtcp2_tstamp ts)1365 static void bbr2_cc_congestion_event(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1366 ngtcp2_tstamp sent_ts, ngtcp2_tstamp ts) {
1367 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(ccx->ccb, ngtcp2_bbr2_cc, ccb);
1368
1369 if (!bbr->filled_pipe || bbr->in_loss_recovery ||
1370 bbr->congestion_recovery_start_ts != UINT64_MAX ||
1371 in_congestion_recovery(cstat, sent_ts)) {
1372 return;
1373 }
1374
1375 bbr->congestion_recovery_start_ts = ts;
1376 }
1377
bbr2_cc_on_spurious_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1378 static void bbr2_cc_on_spurious_congestion(ngtcp2_cc *ccx,
1379 ngtcp2_conn_stat *cstat,
1380 ngtcp2_tstamp ts) {
1381 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(ccx->ccb, ngtcp2_bbr2_cc, ccb);
1382 (void)ts;
1383
1384 bbr->congestion_recovery_start_ts = UINT64_MAX;
1385 cstat->congestion_recovery_start_ts = UINT64_MAX;
1386
1387 if (bbr->in_loss_recovery) {
1388 bbr->in_loss_recovery = 0;
1389 bbr->packet_conservation = 0;
1390 bbr_restore_cwnd(bbr, cstat);
1391 bbr->full_bw_count = 0;
1392 bbr->loss_in_round = 0;
1393 bbr->inflight_lo = ngtcp2_max(bbr->inflight_lo, bbr->prior_inflight_lo);
1394 bbr->inflight_hi = ngtcp2_max(bbr->inflight_hi, bbr->prior_inflight_hi);
1395 bbr->bw_lo = ngtcp2_max(bbr->bw_lo, bbr->prior_bw_lo);
1396 }
1397 }
1398
bbr2_cc_on_persistent_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1399 static void bbr2_cc_on_persistent_congestion(ngtcp2_cc *ccx,
1400 ngtcp2_conn_stat *cstat,
1401 ngtcp2_tstamp ts) {
1402 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(ccx->ccb, ngtcp2_bbr2_cc, ccb);
1403 (void)ts;
1404
1405 cstat->congestion_recovery_start_ts = UINT64_MAX;
1406 bbr->congestion_recovery_start_ts = UINT64_MAX;
1407 bbr->in_loss_recovery = 0;
1408 bbr->packet_conservation = 0;
1409
1410 bbr_save_cwnd(bbr, cstat);
1411 cstat->cwnd = cstat->bytes_in_flight + cstat->max_udp_payload_size;
1412 cstat->cwnd =
1413 ngtcp2_max(cstat->cwnd, min_pipe_cwnd(cstat->max_udp_payload_size));
1414 }
1415
bbr2_cc_on_ack_recv(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)1416 static void bbr2_cc_on_ack_recv(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1417 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) {
1418 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(ccx->ccb, ngtcp2_bbr2_cc, ccb);
1419
1420 bbr_update_on_ack(bbr, cstat, ack, ts);
1421 }
1422
bbr2_cc_on_pkt_sent(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt)1423 static void bbr2_cc_on_pkt_sent(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1424 const ngtcp2_cc_pkt *pkt) {
1425 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(ccx->ccb, ngtcp2_bbr2_cc, ccb);
1426
1427 bbr_on_transmit(bbr, cstat, pkt->sent_ts);
1428 }
1429
bbr2_cc_new_rtt_sample(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1430 static void bbr2_cc_new_rtt_sample(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1431 ngtcp2_tstamp ts) {
1432 (void)ccx;
1433 (void)cstat;
1434 (void)ts;
1435 }
1436
bbr2_cc_reset(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1437 static void bbr2_cc_reset(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1438 ngtcp2_tstamp ts) {
1439 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(ccx->ccb, ngtcp2_bbr2_cc, ccb);
1440
1441 bbr_on_init(bbr, cstat, ts);
1442 }
1443
bbr2_cc_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_cc_event_type event,ngtcp2_tstamp ts)1444 static void bbr2_cc_event(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
1445 ngtcp2_cc_event_type event, ngtcp2_tstamp ts) {
1446 (void)ccx;
1447 (void)cstat;
1448 (void)event;
1449 (void)ts;
1450 }
1451
ngtcp2_cc_bbr2_cc_init(ngtcp2_cc * cc,ngtcp2_log * log,ngtcp2_conn_stat * cstat,ngtcp2_rst * rst,ngtcp2_tstamp initial_ts,ngtcp2_rand rand,const ngtcp2_rand_ctx * rand_ctx,const ngtcp2_mem * mem)1452 int ngtcp2_cc_bbr2_cc_init(ngtcp2_cc *cc, ngtcp2_log *log,
1453 ngtcp2_conn_stat *cstat, ngtcp2_rst *rst,
1454 ngtcp2_tstamp initial_ts, ngtcp2_rand rand,
1455 const ngtcp2_rand_ctx *rand_ctx,
1456 const ngtcp2_mem *mem) {
1457 ngtcp2_bbr2_cc *bbr;
1458
1459 bbr = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_bbr2_cc));
1460 if (bbr == NULL) {
1461 return NGTCP2_ERR_NOMEM;
1462 }
1463
1464 bbr2_cc_init(bbr, cstat, rst, initial_ts, rand, rand_ctx, log);
1465
1466 cc->ccb = &bbr->ccb;
1467 cc->on_pkt_acked = bbr2_cc_on_pkt_acked;
1468 cc->on_pkt_lost = bbr2_cc_on_pkt_lost;
1469 cc->congestion_event = bbr2_cc_congestion_event;
1470 cc->on_spurious_congestion = bbr2_cc_on_spurious_congestion;
1471 cc->on_persistent_congestion = bbr2_cc_on_persistent_congestion;
1472 cc->on_ack_recv = bbr2_cc_on_ack_recv;
1473 cc->on_pkt_sent = bbr2_cc_on_pkt_sent;
1474 cc->new_rtt_sample = bbr2_cc_new_rtt_sample;
1475 cc->reset = bbr2_cc_reset;
1476 cc->event = bbr2_cc_event;
1477
1478 return 0;
1479 }
1480
ngtcp2_cc_bbr2_cc_free(ngtcp2_cc * cc,const ngtcp2_mem * mem)1481 void ngtcp2_cc_bbr2_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem) {
1482 ngtcp2_bbr2_cc *bbr = ngtcp2_struct_of(cc->ccb, ngtcp2_bbr2_cc, ccb);
1483
1484 bbr2_cc_free(bbr);
1485 ngtcp2_mem_free(mem, bbr);
1486 }
1487