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