1 /*
2 * ngtcp2
3 *
4 * Copyright (c) 2018 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_cc.h"
26
27 #include <assert.h>
28
29 #if defined(_MSC_VER)
30 # include <intrin.h>
31 #endif
32
33 #include "ngtcp2_log.h"
34 #include "ngtcp2_macro.h"
35 #include "ngtcp2_mem.h"
36 #include "ngtcp2_rcvry.h"
37
ngtcp2_cc_compute_initcwnd(size_t max_udp_payload_size)38 uint64_t ngtcp2_cc_compute_initcwnd(size_t max_udp_payload_size) {
39 uint64_t n = 2 * max_udp_payload_size;
40 n = ngtcp2_max(n, 14720);
41 return ngtcp2_min(10 * max_udp_payload_size, n);
42 }
43
ngtcp2_cc_pkt_init(ngtcp2_cc_pkt * pkt,int64_t pkt_num,size_t pktlen,ngtcp2_pktns_id pktns_id,ngtcp2_tstamp sent_ts,uint64_t lost,uint64_t tx_in_flight,int is_app_limited)44 ngtcp2_cc_pkt *ngtcp2_cc_pkt_init(ngtcp2_cc_pkt *pkt, int64_t pkt_num,
45 size_t pktlen, ngtcp2_pktns_id pktns_id,
46 ngtcp2_tstamp sent_ts, uint64_t lost,
47 uint64_t tx_in_flight, int is_app_limited) {
48 pkt->pkt_num = pkt_num;
49 pkt->pktlen = pktlen;
50 pkt->pktns_id = pktns_id;
51 pkt->sent_ts = sent_ts;
52 pkt->lost = lost;
53 pkt->tx_in_flight = tx_in_flight;
54 pkt->is_app_limited = is_app_limited;
55
56 return pkt;
57 }
58
reno_cc_reset(ngtcp2_reno_cc * cc)59 static void reno_cc_reset(ngtcp2_reno_cc *cc) {
60 cc->max_delivery_rate_sec = 0;
61 cc->target_cwnd = 0;
62 cc->pending_add = 0;
63 }
64
ngtcp2_reno_cc_init(ngtcp2_reno_cc * cc,ngtcp2_log * log)65 void ngtcp2_reno_cc_init(ngtcp2_reno_cc *cc, ngtcp2_log *log) {
66 cc->ccb.log = log;
67 reno_cc_reset(cc);
68 }
69
ngtcp2_reno_cc_free(ngtcp2_reno_cc * cc)70 void ngtcp2_reno_cc_free(ngtcp2_reno_cc *cc) { (void)cc; }
71
ngtcp2_cc_reno_cc_init(ngtcp2_cc * cc,ngtcp2_log * log,const ngtcp2_mem * mem)72 int ngtcp2_cc_reno_cc_init(ngtcp2_cc *cc, ngtcp2_log *log,
73 const ngtcp2_mem *mem) {
74 ngtcp2_reno_cc *reno_cc;
75
76 reno_cc = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_reno_cc));
77 if (reno_cc == NULL) {
78 return NGTCP2_ERR_NOMEM;
79 }
80
81 ngtcp2_reno_cc_init(reno_cc, log);
82
83 cc->ccb = &reno_cc->ccb;
84 cc->on_pkt_acked = ngtcp2_cc_reno_cc_on_pkt_acked;
85 cc->congestion_event = ngtcp2_cc_reno_cc_congestion_event;
86 cc->on_persistent_congestion = ngtcp2_cc_reno_cc_on_persistent_congestion;
87 cc->on_ack_recv = ngtcp2_cc_reno_cc_on_ack_recv;
88 cc->reset = ngtcp2_cc_reno_cc_reset;
89
90 return 0;
91 }
92
ngtcp2_cc_reno_cc_free(ngtcp2_cc * cc,const ngtcp2_mem * mem)93 void ngtcp2_cc_reno_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem) {
94 ngtcp2_reno_cc *reno_cc = ngtcp2_struct_of(cc->ccb, ngtcp2_reno_cc, ccb);
95
96 ngtcp2_reno_cc_free(reno_cc);
97 ngtcp2_mem_free(mem, reno_cc);
98 }
99
in_congestion_recovery(const ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_time)100 static int in_congestion_recovery(const ngtcp2_conn_stat *cstat,
101 ngtcp2_tstamp sent_time) {
102 return cstat->congestion_recovery_start_ts != UINT64_MAX &&
103 sent_time <= cstat->congestion_recovery_start_ts;
104 }
105
ngtcp2_cc_reno_cc_on_pkt_acked(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)106 void ngtcp2_cc_reno_cc_on_pkt_acked(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
107 const ngtcp2_cc_pkt *pkt,
108 ngtcp2_tstamp ts) {
109 ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
110 uint64_t m;
111 (void)ts;
112
113 if (in_congestion_recovery(cstat, pkt->sent_ts)) {
114 return;
115 }
116
117 if (cc->target_cwnd && cc->target_cwnd < cstat->cwnd) {
118 return;
119 }
120
121 if (cstat->cwnd < cstat->ssthresh) {
122 cstat->cwnd += pkt->pktlen;
123 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
124 "pkn=%" PRId64 " acked, slow start cwnd=%" PRIu64,
125 pkt->pkt_num, cstat->cwnd);
126 return;
127 }
128
129 m = cstat->max_udp_payload_size * pkt->pktlen + cc->pending_add;
130 cc->pending_add = m % cstat->cwnd;
131
132 cstat->cwnd += m / cstat->cwnd;
133 }
134
ngtcp2_cc_reno_cc_congestion_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_ts,ngtcp2_tstamp ts)135 void ngtcp2_cc_reno_cc_congestion_event(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
136 ngtcp2_tstamp sent_ts,
137 ngtcp2_tstamp ts) {
138 ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
139 uint64_t min_cwnd;
140
141 if (in_congestion_recovery(cstat, sent_ts)) {
142 return;
143 }
144
145 cstat->congestion_recovery_start_ts = ts;
146 cstat->cwnd >>= NGTCP2_LOSS_REDUCTION_FACTOR_BITS;
147 min_cwnd = 2 * cstat->max_udp_payload_size;
148 cstat->cwnd = ngtcp2_max(cstat->cwnd, min_cwnd);
149 cstat->ssthresh = cstat->cwnd;
150
151 cc->pending_add = 0;
152
153 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
154 "reduce cwnd because of packet loss cwnd=%" PRIu64,
155 cstat->cwnd);
156 }
157
ngtcp2_cc_reno_cc_on_persistent_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)158 void ngtcp2_cc_reno_cc_on_persistent_congestion(ngtcp2_cc *ccx,
159 ngtcp2_conn_stat *cstat,
160 ngtcp2_tstamp ts) {
161 (void)ccx;
162 (void)ts;
163
164 cstat->cwnd = 2 * cstat->max_udp_payload_size;
165 cstat->congestion_recovery_start_ts = UINT64_MAX;
166 }
167
ngtcp2_cc_reno_cc_on_ack_recv(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)168 void ngtcp2_cc_reno_cc_on_ack_recv(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
169 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) {
170 ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
171 uint64_t target_cwnd, initcwnd;
172 (void)ack;
173 (void)ts;
174
175 /* TODO Use sliding window for min rtt measurement */
176 /* TODO Use sliding window */
177 cc->max_delivery_rate_sec =
178 ngtcp2_max(cc->max_delivery_rate_sec, cstat->delivery_rate_sec);
179
180 if (cstat->min_rtt != UINT64_MAX && cc->max_delivery_rate_sec) {
181 target_cwnd = cc->max_delivery_rate_sec * cstat->min_rtt / NGTCP2_SECONDS;
182 initcwnd = ngtcp2_cc_compute_initcwnd(cstat->max_udp_payload_size);
183 cc->target_cwnd = ngtcp2_max(initcwnd, target_cwnd) * 289 / 100;
184
185 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
186 "target_cwnd=%" PRIu64 " max_delivery_rate_sec=%" PRIu64
187 " min_rtt=%" PRIu64,
188 cc->target_cwnd, cc->max_delivery_rate_sec, cstat->min_rtt);
189 }
190 }
191
ngtcp2_cc_reno_cc_reset(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)192 void ngtcp2_cc_reno_cc_reset(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
193 ngtcp2_tstamp ts) {
194 ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
195 (void)cstat;
196 (void)ts;
197
198 reno_cc_reset(cc);
199 }
200
cubic_cc_reset(ngtcp2_cubic_cc * cc)201 static void cubic_cc_reset(ngtcp2_cubic_cc *cc) {
202 cc->max_delivery_rate_sec = 0;
203 cc->target_cwnd = 0;
204 cc->w_last_max = 0;
205 cc->w_tcp = 0;
206 cc->origin_point = 0;
207 cc->epoch_start = UINT64_MAX;
208 cc->k = 0;
209
210 cc->prior.cwnd = 0;
211 cc->prior.ssthresh = 0;
212 cc->prior.w_last_max = 0;
213 cc->prior.w_tcp = 0;
214 cc->prior.origin_point = 0;
215 cc->prior.epoch_start = UINT64_MAX;
216 cc->prior.k = 0;
217
218 cc->rtt_sample_count = 0;
219 cc->current_round_min_rtt = UINT64_MAX;
220 cc->last_round_min_rtt = UINT64_MAX;
221 cc->window_end = -1;
222 }
223
ngtcp2_cubic_cc_init(ngtcp2_cubic_cc * cc,ngtcp2_log * log)224 void ngtcp2_cubic_cc_init(ngtcp2_cubic_cc *cc, ngtcp2_log *log) {
225 cc->ccb.log = log;
226 cubic_cc_reset(cc);
227 }
228
ngtcp2_cubic_cc_free(ngtcp2_cubic_cc * cc)229 void ngtcp2_cubic_cc_free(ngtcp2_cubic_cc *cc) { (void)cc; }
230
ngtcp2_cc_cubic_cc_init(ngtcp2_cc * cc,ngtcp2_log * log,const ngtcp2_mem * mem)231 int ngtcp2_cc_cubic_cc_init(ngtcp2_cc *cc, ngtcp2_log *log,
232 const ngtcp2_mem *mem) {
233 ngtcp2_cubic_cc *cubic_cc;
234
235 cubic_cc = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_cubic_cc));
236 if (cubic_cc == NULL) {
237 return NGTCP2_ERR_NOMEM;
238 }
239
240 ngtcp2_cubic_cc_init(cubic_cc, log);
241
242 cc->ccb = &cubic_cc->ccb;
243 cc->on_pkt_acked = ngtcp2_cc_cubic_cc_on_pkt_acked;
244 cc->congestion_event = ngtcp2_cc_cubic_cc_congestion_event;
245 cc->on_spurious_congestion = ngtcp2_cc_cubic_cc_on_spurious_congestion;
246 cc->on_persistent_congestion = ngtcp2_cc_cubic_cc_on_persistent_congestion;
247 cc->on_ack_recv = ngtcp2_cc_cubic_cc_on_ack_recv;
248 cc->on_pkt_sent = ngtcp2_cc_cubic_cc_on_pkt_sent;
249 cc->new_rtt_sample = ngtcp2_cc_cubic_cc_new_rtt_sample;
250 cc->reset = ngtcp2_cc_cubic_cc_reset;
251 cc->event = ngtcp2_cc_cubic_cc_event;
252
253 return 0;
254 }
255
ngtcp2_cc_cubic_cc_free(ngtcp2_cc * cc,const ngtcp2_mem * mem)256 void ngtcp2_cc_cubic_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem) {
257 ngtcp2_cubic_cc *cubic_cc = ngtcp2_struct_of(cc->ccb, ngtcp2_cubic_cc, ccb);
258
259 ngtcp2_cubic_cc_free(cubic_cc);
260 ngtcp2_mem_free(mem, cubic_cc);
261 }
262
ngtcp2_cbrt(uint64_t n)263 static uint64_t ngtcp2_cbrt(uint64_t n) {
264 int d;
265 uint64_t a;
266
267 if (n == 0) {
268 return 0;
269 }
270
271 #if defined(_MSC_VER)
272 # if defined(_M_X64)
273 d = (int)__lzcnt64(n);
274 # elif defined(_M_ARM64)
275 {
276 unsigned long index;
277 d = sizeof(uint64_t) * CHAR_BIT;
278 if (_BitScanReverse64(&index, n)) {
279 d = d - 1 - index;
280 }
281 }
282 # else
283 if ((n >> 32) != 0) {
284 d = __lzcnt((unsigned int)(n >> 32));
285 } else {
286 d = 32 + __lzcnt((unsigned int)n);
287 }
288 # endif
289 #else
290 d = __builtin_clzll(n);
291 #endif
292 a = 1ULL << ((64 - d) / 3 + 1);
293
294 for (; a * a * a > n;) {
295 a = (2 * a + n / a / a) / 3;
296 }
297 return a;
298 }
299
300 /* HyStart++ constants */
301 #define NGTCP2_HS_MIN_SSTHRESH 16
302 #define NGTCP2_HS_N_RTT_SAMPLE 8
303 #define NGTCP2_HS_MIN_ETA (4 * NGTCP2_MILLISECONDS)
304 #define NGTCP2_HS_MAX_ETA (16 * NGTCP2_MILLISECONDS)
305
ngtcp2_cc_cubic_cc_on_pkt_acked(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)306 void ngtcp2_cc_cubic_cc_on_pkt_acked(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
307 const ngtcp2_cc_pkt *pkt,
308 ngtcp2_tstamp ts) {
309 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
310 ngtcp2_duration t, min_rtt, eta;
311 uint64_t target;
312 uint64_t tx, kx, time_delta, delta;
313 uint64_t add, tcp_add;
314 uint64_t m;
315
316 if (pkt->pktns_id == NGTCP2_PKTNS_ID_APPLICATION && cc->window_end != -1 &&
317 cc->window_end <= pkt->pkt_num) {
318 cc->window_end = -1;
319 }
320
321 if (in_congestion_recovery(cstat, pkt->sent_ts)) {
322 return;
323 }
324
325 if (cc->target_cwnd && cc->target_cwnd < cstat->cwnd) {
326 return;
327 }
328
329 if (cstat->cwnd < cstat->ssthresh) {
330 /* slow-start */
331 cstat->cwnd += pkt->pktlen;
332
333 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
334 "pkn=%" PRId64 " acked, slow start cwnd=%" PRIu64,
335 pkt->pkt_num, cstat->cwnd);
336
337 if (cc->last_round_min_rtt != UINT64_MAX &&
338 cc->current_round_min_rtt != UINT64_MAX &&
339 cstat->cwnd >= NGTCP2_HS_MIN_SSTHRESH * cstat->max_udp_payload_size &&
340 cc->rtt_sample_count >= NGTCP2_HS_N_RTT_SAMPLE) {
341 eta = cc->last_round_min_rtt / 8;
342
343 if (eta < NGTCP2_HS_MIN_ETA) {
344 eta = NGTCP2_HS_MIN_ETA;
345 } else if (eta > NGTCP2_HS_MAX_ETA) {
346 eta = NGTCP2_HS_MAX_ETA;
347 }
348
349 if (cc->current_round_min_rtt >= cc->last_round_min_rtt + eta) {
350 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
351 "HyStart++ exit slow start");
352
353 cc->w_last_max = cstat->cwnd;
354 cstat->ssthresh = cstat->cwnd;
355 }
356 }
357
358 return;
359 }
360
361 /* congestion avoidance */
362
363 if (cc->epoch_start == UINT64_MAX) {
364 cc->epoch_start = ts;
365 if (cstat->cwnd < cc->w_last_max) {
366 cc->k = ngtcp2_cbrt((cc->w_last_max - cstat->cwnd) * 10 / 4 /
367 cstat->max_udp_payload_size);
368 cc->origin_point = cc->w_last_max;
369 } else {
370 cc->k = 0;
371 cc->origin_point = cstat->cwnd;
372 }
373
374 cc->w_tcp = cstat->cwnd;
375
376 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
377 "cubic-ca epoch_start=%" PRIu64 " k=%" PRIu64
378 " origin_point=%" PRIu64,
379 cc->epoch_start, cc->k, cc->origin_point);
380
381 cc->pending_add = 0;
382 cc->pending_w_add = 0;
383 }
384
385 min_rtt = cstat->min_rtt == UINT64_MAX ? cstat->initial_rtt : cstat->min_rtt;
386
387 t = ts + min_rtt - cc->epoch_start;
388
389 tx = (t << 4) / NGTCP2_SECONDS;
390 kx = (cc->k << 4);
391
392 if (tx > kx) {
393 time_delta = tx - kx;
394 } else {
395 time_delta = kx - tx;
396 }
397
398 delta = cstat->max_udp_payload_size *
399 ((((time_delta * time_delta) >> 4) * time_delta) >> 8) * 4 / 10;
400
401 if (tx > kx) {
402 target = cc->origin_point + delta;
403 } else {
404 target = cc->origin_point - delta;
405 }
406
407 if (target > cstat->cwnd) {
408 m = cc->pending_add + cstat->max_udp_payload_size * (target - cstat->cwnd);
409 add = m / cstat->cwnd;
410 cc->pending_add = m % cstat->cwnd;
411 } else {
412 m = cc->pending_add + cstat->max_udp_payload_size;
413 add = m / (100 * cstat->cwnd);
414 cc->pending_add = m % (100 * cstat->cwnd);
415 }
416
417 m = cc->pending_w_add + cstat->max_udp_payload_size * pkt->pktlen;
418
419 cc->w_tcp += m / cstat->cwnd;
420 cc->pending_w_add = m % cstat->cwnd;
421
422 if (cc->w_tcp > cstat->cwnd) {
423 tcp_add =
424 cstat->max_udp_payload_size * (cc->w_tcp - cstat->cwnd) / cstat->cwnd;
425 if (tcp_add > add) {
426 add = tcp_add;
427 }
428 }
429
430 cstat->cwnd += add;
431
432 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
433 "pkn=%" PRId64 " acked, cubic-ca cwnd=%" PRIu64 " t=%" PRIu64
434 " k=%" PRIi64 " time_delta=%" PRIu64 " delta=%" PRIu64
435 " target=%" PRIu64 " w_tcp=%" PRIu64,
436 pkt->pkt_num, cstat->cwnd, t, cc->k, time_delta >> 4, delta,
437 target, cc->w_tcp);
438 }
439
ngtcp2_cc_cubic_cc_congestion_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_ts,ngtcp2_tstamp ts)440 void ngtcp2_cc_cubic_cc_congestion_event(ngtcp2_cc *ccx,
441 ngtcp2_conn_stat *cstat,
442 ngtcp2_tstamp sent_ts,
443 ngtcp2_tstamp ts) {
444 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
445 uint64_t min_cwnd;
446
447 if (in_congestion_recovery(cstat, sent_ts)) {
448 return;
449 }
450
451 if (cc->prior.cwnd < cstat->cwnd) {
452 cc->prior.cwnd = cstat->cwnd;
453 cc->prior.ssthresh = cstat->ssthresh;
454 cc->prior.w_last_max = cc->w_last_max;
455 cc->prior.w_tcp = cc->w_tcp;
456 cc->prior.origin_point = cc->origin_point;
457 cc->prior.epoch_start = cc->epoch_start;
458 cc->prior.k = cc->k;
459 }
460
461 cstat->congestion_recovery_start_ts = ts;
462
463 cc->epoch_start = UINT64_MAX;
464 if (cstat->cwnd < cc->w_last_max) {
465 cc->w_last_max = cstat->cwnd * 17 / 10 / 2;
466 } else {
467 cc->w_last_max = cstat->cwnd;
468 }
469
470 min_cwnd = 2 * cstat->max_udp_payload_size;
471 cstat->ssthresh = cstat->cwnd * 7 / 10;
472 cstat->ssthresh = ngtcp2_max(cstat->ssthresh, min_cwnd);
473 cstat->cwnd = cstat->ssthresh;
474
475 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
476 "reduce cwnd because of packet loss cwnd=%" PRIu64,
477 cstat->cwnd);
478 }
479
ngtcp2_cc_cubic_cc_on_spurious_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)480 void ngtcp2_cc_cubic_cc_on_spurious_congestion(ngtcp2_cc *ccx,
481 ngtcp2_conn_stat *cstat,
482 ngtcp2_tstamp ts) {
483 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
484 (void)ts;
485
486 if (cstat->cwnd >= cc->prior.cwnd) {
487 return;
488 }
489
490 cstat->congestion_recovery_start_ts = UINT64_MAX;
491
492 cstat->cwnd = cc->prior.cwnd;
493 cstat->ssthresh = cc->prior.ssthresh;
494 cc->w_last_max = cc->prior.w_last_max;
495 cc->w_tcp = cc->prior.w_tcp;
496 cc->origin_point = cc->prior.origin_point;
497 cc->epoch_start = cc->prior.epoch_start;
498 cc->k = cc->prior.k;
499
500 cc->prior.cwnd = 0;
501 cc->prior.ssthresh = 0;
502 cc->prior.w_last_max = 0;
503 cc->prior.w_tcp = 0;
504 cc->prior.origin_point = 0;
505 cc->prior.epoch_start = UINT64_MAX;
506 cc->prior.k = 0;
507
508 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
509 "spurious congestion is detected and congestion state is "
510 "restored cwnd=%" PRIu64,
511 cstat->cwnd);
512 }
513
ngtcp2_cc_cubic_cc_on_persistent_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)514 void ngtcp2_cc_cubic_cc_on_persistent_congestion(ngtcp2_cc *ccx,
515 ngtcp2_conn_stat *cstat,
516 ngtcp2_tstamp ts) {
517 (void)ccx;
518 (void)ts;
519
520 cstat->cwnd = 2 * cstat->max_udp_payload_size;
521 cstat->congestion_recovery_start_ts = UINT64_MAX;
522 }
523
ngtcp2_cc_cubic_cc_on_ack_recv(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)524 void ngtcp2_cc_cubic_cc_on_ack_recv(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
525 const ngtcp2_cc_ack *ack,
526 ngtcp2_tstamp ts) {
527 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
528 uint64_t target_cwnd, initcwnd;
529 (void)ack;
530 (void)ts;
531
532 /* TODO Use sliding window for min rtt measurement */
533 /* TODO Use sliding window */
534 cc->max_delivery_rate_sec =
535 ngtcp2_max(cc->max_delivery_rate_sec, cstat->delivery_rate_sec);
536
537 if (cstat->min_rtt != UINT64_MAX && cc->max_delivery_rate_sec) {
538 target_cwnd = cc->max_delivery_rate_sec * cstat->min_rtt / NGTCP2_SECONDS;
539 initcwnd = ngtcp2_cc_compute_initcwnd(cstat->max_udp_payload_size);
540 cc->target_cwnd = ngtcp2_max(initcwnd, target_cwnd) * 289 / 100;
541
542 ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
543 "target_cwnd=%" PRIu64 " max_delivery_rate_sec=%" PRIu64
544 " min_rtt=%" PRIu64,
545 cc->target_cwnd, cc->max_delivery_rate_sec, cstat->min_rtt);
546 }
547 }
548
ngtcp2_cc_cubic_cc_on_pkt_sent(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt)549 void ngtcp2_cc_cubic_cc_on_pkt_sent(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
550 const ngtcp2_cc_pkt *pkt) {
551 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
552 (void)cstat;
553
554 if (pkt->pktns_id != NGTCP2_PKTNS_ID_APPLICATION || cc->window_end != -1) {
555 return;
556 }
557
558 cc->window_end = pkt->pkt_num;
559 cc->last_round_min_rtt = cc->current_round_min_rtt;
560 cc->current_round_min_rtt = UINT64_MAX;
561 cc->rtt_sample_count = 0;
562 }
563
ngtcp2_cc_cubic_cc_new_rtt_sample(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)564 void ngtcp2_cc_cubic_cc_new_rtt_sample(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
565 ngtcp2_tstamp ts) {
566 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
567 (void)ts;
568
569 if (cc->window_end == -1) {
570 return;
571 }
572
573 cc->current_round_min_rtt =
574 ngtcp2_min(cc->current_round_min_rtt, cstat->latest_rtt);
575 ++cc->rtt_sample_count;
576 }
577
ngtcp2_cc_cubic_cc_reset(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)578 void ngtcp2_cc_cubic_cc_reset(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
579 ngtcp2_tstamp ts) {
580 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
581 (void)cstat;
582 (void)ts;
583
584 cubic_cc_reset(cc);
585 }
586
ngtcp2_cc_cubic_cc_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_cc_event_type event,ngtcp2_tstamp ts)587 void ngtcp2_cc_cubic_cc_event(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
588 ngtcp2_cc_event_type event, ngtcp2_tstamp ts) {
589 ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
590 ngtcp2_tstamp last_ts;
591
592 if (event != NGTCP2_CC_EVENT_TYPE_TX_START || cc->epoch_start == UINT64_MAX) {
593 return;
594 }
595
596 last_ts = cstat->last_tx_pkt_ts[NGTCP2_PKTNS_ID_APPLICATION];
597 if (last_ts == UINT64_MAX || last_ts <= cc->epoch_start) {
598 return;
599 }
600
601 assert(ts >= last_ts);
602
603 cc->epoch_start += ts - last_ts;
604 }
605