Mercurial > hg > nginx-quic
comparison src/event/quic/ngx_event_quic_ack.c @ 8493:004172345bdc quic
QUIC: persistent congestion calculation.
According to RFC 9002 (quic-recovery) 7.6.
author | Vladimir Homutov <vl@nginx.com> |
---|---|
date | Wed, 09 Jun 2021 15:11:43 +0300 |
parents | f52a2b77d406 |
children | 4715f3e669f1 |
comparison
equal
deleted
inserted
replaced
8492:af33d1ef1c3c | 8493:004172345bdc |
---|---|
16 #define NGX_QUIC_PKT_THR 3 /* packets */ | 16 #define NGX_QUIC_PKT_THR 3 /* packets */ |
17 /* quic-recovery, section 6.1.2, Time Threshold */ | 17 /* quic-recovery, section 6.1.2, Time Threshold */ |
18 #define NGX_QUIC_TIME_THR 1.125 | 18 #define NGX_QUIC_TIME_THR 1.125 |
19 #define NGX_QUIC_TIME_GRANULARITY 1 /* ms */ | 19 #define NGX_QUIC_TIME_GRANULARITY 1 /* ms */ |
20 | 20 |
21 /* quic-recovery, section 7.6.1 Persistent congestion duration */ | |
22 #define NGX_QUIC_PERSISTENT_CONGESTION_THR 3 | |
23 | |
21 #define ngx_quic_lost_threshold(qc) \ | 24 #define ngx_quic_lost_threshold(qc) \ |
22 ngx_max(NGX_QUIC_TIME_THR * ngx_max((qc)->latest_rtt, (qc)->avg_rtt), \ | 25 ngx_max(NGX_QUIC_TIME_THR * ngx_max((qc)->latest_rtt, (qc)->avg_rtt), \ |
23 NGX_QUIC_TIME_GRANULARITY) | 26 NGX_QUIC_TIME_GRANULARITY) |
27 | |
28 | |
29 /* send time of ACK'ed packets */ | |
30 typedef struct { | |
31 ngx_msec_t max_pn; | |
32 ngx_msec_t oldest; | |
33 ngx_msec_t newest; | |
34 } ngx_quic_ack_stat_t; | |
24 | 35 |
25 | 36 |
26 static void ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, | 37 static void ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, |
27 enum ssl_encryption_level_t level, ngx_msec_t send_time); | 38 enum ssl_encryption_level_t level, ngx_msec_t send_time); |
28 static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c, | 39 static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c, |
29 ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max, | 40 ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max, |
30 ngx_msec_t *send_time); | 41 ngx_quic_ack_stat_t *st); |
31 static void ngx_quic_drop_ack_ranges(ngx_connection_t *c, | 42 static void ngx_quic_drop_ack_ranges(ngx_connection_t *c, |
32 ngx_quic_send_ctx_t *ctx, uint64_t pn); | 43 ngx_quic_send_ctx_t *ctx, uint64_t pn); |
33 static ngx_int_t ngx_quic_detect_lost(ngx_connection_t *c); | 44 static ngx_int_t ngx_quic_detect_lost(ngx_connection_t *c, |
45 ngx_quic_ack_stat_t *st); | |
46 static ngx_msec_t ngx_quic_pcg_duration(ngx_connection_t *c); | |
47 static void ngx_quic_persistent_congestion(ngx_connection_t *c); | |
34 static void ngx_quic_congestion_lost(ngx_connection_t *c, | 48 static void ngx_quic_congestion_lost(ngx_connection_t *c, |
35 ngx_quic_frame_t *frame); | 49 ngx_quic_frame_t *frame); |
36 static void ngx_quic_lost_handler(ngx_event_t *ev); | 50 static void ngx_quic_lost_handler(ngx_event_t *ev); |
37 | 51 |
38 | 52 |
41 ngx_quic_frame_t *f) | 55 ngx_quic_frame_t *f) |
42 { | 56 { |
43 ssize_t n; | 57 ssize_t n; |
44 u_char *pos, *end; | 58 u_char *pos, *end; |
45 uint64_t min, max, gap, range; | 59 uint64_t min, max, gap, range; |
46 ngx_msec_t send_time; | |
47 ngx_uint_t i; | 60 ngx_uint_t i; |
61 ngx_quic_ack_stat_t send_time; | |
48 ngx_quic_send_ctx_t *ctx; | 62 ngx_quic_send_ctx_t *ctx; |
49 ngx_quic_ack_frame_t *ack; | 63 ngx_quic_ack_frame_t *ack; |
50 ngx_quic_connection_t *qc; | 64 ngx_quic_connection_t *qc; |
51 | 65 |
52 qc = ngx_quic_get_connection(c); | 66 qc = ngx_quic_get_connection(c); |
71 return NGX_ERROR; | 85 return NGX_ERROR; |
72 } | 86 } |
73 | 87 |
74 min = ack->largest - ack->first_range; | 88 min = ack->largest - ack->first_range; |
75 max = ack->largest; | 89 max = ack->largest; |
90 | |
91 send_time.oldest = NGX_TIMER_INFINITE; | |
92 send_time.newest = NGX_TIMER_INFINITE; | |
76 | 93 |
77 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time) | 94 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time) |
78 != NGX_OK) | 95 != NGX_OK) |
79 { | 96 { |
80 return NGX_ERROR; | 97 return NGX_ERROR; |
92 * | 109 * |
93 * - the largest acknowledged packet number is newly acknowledged | 110 * - the largest acknowledged packet number is newly acknowledged |
94 * - at least one of the newly acknowledged packets was ack-eliciting. | 111 * - at least one of the newly acknowledged packets was ack-eliciting. |
95 */ | 112 */ |
96 | 113 |
97 if (send_time != NGX_TIMER_INFINITE) { | 114 if (send_time.max_pn != NGX_TIMER_INFINITE) { |
98 ngx_quic_rtt_sample(c, ack, pkt->level, send_time); | 115 ngx_quic_rtt_sample(c, ack, pkt->level, send_time.max_pn); |
99 } | 116 } |
100 } | 117 } |
101 | 118 |
102 if (f->data) { | 119 if (f->data) { |
103 pos = f->data->buf->pos; | 120 pos = f->data->buf->pos; |
139 { | 156 { |
140 return NGX_ERROR; | 157 return NGX_ERROR; |
141 } | 158 } |
142 } | 159 } |
143 | 160 |
144 return ngx_quic_detect_lost(c); | 161 return ngx_quic_detect_lost(c, &send_time); |
145 } | 162 } |
146 | 163 |
147 | 164 |
148 static void | 165 static void |
149 ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, | 166 ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, |
159 | 176 |
160 if (qc->min_rtt == NGX_TIMER_INFINITE) { | 177 if (qc->min_rtt == NGX_TIMER_INFINITE) { |
161 qc->min_rtt = latest_rtt; | 178 qc->min_rtt = latest_rtt; |
162 qc->avg_rtt = latest_rtt; | 179 qc->avg_rtt = latest_rtt; |
163 qc->rttvar = latest_rtt / 2; | 180 qc->rttvar = latest_rtt / 2; |
181 qc->first_rtt = ngx_current_msec; | |
164 | 182 |
165 } else { | 183 } else { |
166 qc->min_rtt = ngx_min(qc->min_rtt, latest_rtt); | 184 qc->min_rtt = ngx_min(qc->min_rtt, latest_rtt); |
167 | 185 |
168 ack_delay = ack->delay * (1 << qc->ctp.ack_delay_exponent) / 1000; | 186 ack_delay = ack->delay * (1 << qc->ctp.ack_delay_exponent) / 1000; |
188 } | 206 } |
189 | 207 |
190 | 208 |
191 static ngx_int_t | 209 static ngx_int_t |
192 ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx, | 210 ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx, |
193 uint64_t min, uint64_t max, ngx_msec_t *send_time) | 211 uint64_t min, uint64_t max, ngx_quic_ack_stat_t *st) |
194 { | 212 { |
195 ngx_uint_t found; | 213 ngx_uint_t found; |
196 ngx_queue_t *q; | 214 ngx_queue_t *q; |
197 ngx_quic_frame_t *f; | 215 ngx_quic_frame_t *f; |
198 ngx_quic_connection_t *qc; | 216 ngx_quic_connection_t *qc; |
199 | 217 |
200 qc = ngx_quic_get_connection(c); | 218 qc = ngx_quic_get_connection(c); |
201 | 219 |
202 *send_time = NGX_TIMER_INFINITE; | 220 st->max_pn = NGX_TIMER_INFINITE; |
203 found = 0; | 221 found = 0; |
204 | 222 |
205 q = ngx_queue_last(&ctx->sent); | 223 q = ngx_queue_last(&ctx->sent); |
206 | 224 |
207 while (q != ngx_queue_sentinel(&ctx->sent)) { | 225 while (q != ngx_queue_sentinel(&ctx->sent)) { |
229 ngx_quic_handle_stream_ack(c, f); | 247 ngx_quic_handle_stream_ack(c, f); |
230 break; | 248 break; |
231 } | 249 } |
232 | 250 |
233 if (f->pnum == max) { | 251 if (f->pnum == max) { |
234 *send_time = f->last; | 252 st->max_pn = f->last; |
253 } | |
254 | |
255 /* save earliest and latest send times of frames ack'ed */ | |
256 if (st->oldest == NGX_TIMER_INFINITE || f->last < st->oldest) { | |
257 st->oldest = f->last; | |
258 } | |
259 | |
260 if (st->newest == NGX_TIMER_INFINITE || f->last > st->newest) { | |
261 st->newest = f->last; | |
235 } | 262 } |
236 | 263 |
237 ngx_queue_remove(&f->queue); | 264 ngx_queue_remove(&f->queue); |
238 ngx_quic_free_frame(c, f); | 265 ngx_quic_free_frame(c, f); |
239 found = 1; | 266 found = 1; |
375 } | 402 } |
376 } | 403 } |
377 | 404 |
378 | 405 |
379 static ngx_int_t | 406 static ngx_int_t |
380 ngx_quic_detect_lost(ngx_connection_t *c) | 407 ngx_quic_detect_lost(ngx_connection_t *c, ngx_quic_ack_stat_t *st) |
381 { | 408 { |
382 ngx_uint_t i; | 409 ngx_uint_t i, nlost; |
383 ngx_msec_t now, wait, thr; | 410 ngx_msec_t now, wait, thr, oldest, newest; |
384 ngx_queue_t *q; | 411 ngx_queue_t *q; |
385 ngx_quic_frame_t *start; | 412 ngx_quic_frame_t *start; |
386 ngx_quic_send_ctx_t *ctx; | 413 ngx_quic_send_ctx_t *ctx; |
387 ngx_quic_connection_t *qc; | 414 ngx_quic_connection_t *qc; |
388 | 415 |
389 qc = ngx_quic_get_connection(c); | 416 qc = ngx_quic_get_connection(c); |
390 now = ngx_current_msec; | 417 now = ngx_current_msec; |
391 thr = ngx_quic_lost_threshold(qc); | 418 thr = ngx_quic_lost_threshold(qc); |
419 | |
420 /* send time of lost packets across all send contexts */ | |
421 oldest = NGX_TIMER_INFINITE; | |
422 newest = NGX_TIMER_INFINITE; | |
423 | |
424 nlost = 0; | |
392 | 425 |
393 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { | 426 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { |
394 | 427 |
395 ctx = &qc->send_ctx[i]; | 428 ctx = &qc->send_ctx[i]; |
396 | 429 |
417 && ctx->largest_ack - start->pnum < NGX_QUIC_PKT_THR) | 450 && ctx->largest_ack - start->pnum < NGX_QUIC_PKT_THR) |
418 { | 451 { |
419 break; | 452 break; |
420 } | 453 } |
421 | 454 |
455 if (start->last > qc->first_rtt) { | |
456 | |
457 if (oldest == NGX_TIMER_INFINITE || start->last < oldest) { | |
458 oldest = start->last; | |
459 } | |
460 | |
461 if (newest == NGX_TIMER_INFINITE || start->last > newest) { | |
462 newest = start->last; | |
463 } | |
464 | |
465 nlost++; | |
466 } | |
467 | |
422 ngx_quic_resend_frames(c, ctx); | 468 ngx_quic_resend_frames(c, ctx); |
423 } | 469 } |
424 } | 470 } |
425 | 471 |
472 | |
473 /* Establishing Persistent Congestion (7.6.2) */ | |
474 | |
475 /* | |
476 * Once acknowledged, packets are no longer tracked. Thus no send time | |
477 * information is available for such packets. This limits persistent | |
478 * congestion algorithm to packets mentioned within ACK ranges of the | |
479 * latest ACK frame. | |
480 */ | |
481 | |
482 if (st && nlost >= 2 && (st->newest < oldest || st->oldest > newest)) { | |
483 | |
484 if (newest - oldest > ngx_quic_pcg_duration(c)) { | |
485 ngx_quic_persistent_congestion(c); | |
486 } | |
487 } | |
488 | |
426 ngx_quic_set_lost_timer(c); | 489 ngx_quic_set_lost_timer(c); |
427 | 490 |
428 return NGX_OK; | 491 return NGX_OK; |
492 } | |
493 | |
494 | |
495 static ngx_msec_t | |
496 ngx_quic_pcg_duration(ngx_connection_t *c) | |
497 { | |
498 ngx_msec_t duration; | |
499 ngx_quic_connection_t *qc; | |
500 | |
501 qc = ngx_quic_get_connection(c); | |
502 | |
503 duration = qc->avg_rtt; | |
504 duration += ngx_max(4 * qc->rttvar, NGX_QUIC_TIME_GRANULARITY); | |
505 duration += qc->ctp.max_ack_delay; | |
506 duration *= NGX_QUIC_PERSISTENT_CONGESTION_THR; | |
507 | |
508 return duration; | |
509 } | |
510 | |
511 | |
512 static void | |
513 ngx_quic_persistent_congestion(ngx_connection_t *c) | |
514 { | |
515 ngx_quic_congestion_t *cg; | |
516 ngx_quic_connection_t *qc; | |
517 | |
518 qc = ngx_quic_get_connection(c); | |
519 cg = &qc->congestion; | |
520 | |
521 cg->recovery_start = ngx_current_msec; | |
522 cg->window = qc->tp.max_udp_payload_size * 2; | |
523 | |
524 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
525 "quic persistent congestion win:%uz", cg->window); | |
429 } | 526 } |
430 | 527 |
431 | 528 |
432 void | 529 void |
433 ngx_quic_resend_frames(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx) | 530 ngx_quic_resend_frames(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx) |
685 | 782 |
686 ngx_log_debug0(NGX_LOG_DEBUG_EVENT, ev->log, 0, "quic lost timer"); | 783 ngx_log_debug0(NGX_LOG_DEBUG_EVENT, ev->log, 0, "quic lost timer"); |
687 | 784 |
688 c = ev->data; | 785 c = ev->data; |
689 | 786 |
690 if (ngx_quic_detect_lost(c) != NGX_OK) { | 787 if (ngx_quic_detect_lost(c, NULL) != NGX_OK) { |
691 ngx_quic_close_connection(c, NGX_ERROR); | 788 ngx_quic_close_connection(c, NGX_ERROR); |
692 } | 789 } |
693 | 790 |
694 ngx_quic_connstate_dbg(c); | 791 ngx_quic_connstate_dbg(c); |
695 } | 792 } |