Mercurial > hg > nginx

comparison src/event/quic/ngx_event_quic_ack.c @ 8792:004172345bdc quic

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
8791:af33d1ef1c3c 8792: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 }