Mercurial > hg > nginx-quic
comparison src/event/ngx_event_quic.c @ 7987:3b107aadc9f6 quic
QUIC: added rtt estimation.
According to the quic-recovery 29, Section 5: Estimating the Round-Trip Time.
Currently, integer arithmetics is used, which loses sub-millisecond accuracy.
author | Vladimir Homutov <vl@nginx.com> |
---|---|
date | Thu, 16 Jul 2020 15:44:06 +0300 |
parents | e0f92f68e018 |
children | 0d1ad81dd65c |
comparison
equal
deleted
inserted
replaced
7986:001ec7fce567 | 7987:3b107aadc9f6 |
---|---|
96 ngx_event_t push; | 96 ngx_event_t push; |
97 ngx_event_t retransmit; | 97 ngx_event_t retransmit; |
98 ngx_event_t close; | 98 ngx_event_t close; |
99 ngx_queue_t free_frames; | 99 ngx_queue_t free_frames; |
100 ngx_msec_t last_cc; | 100 ngx_msec_t last_cc; |
101 | |
102 ngx_msec_t latest_rtt; | |
103 ngx_msec_t avg_rtt; | |
104 ngx_msec_t min_rtt; | |
105 ngx_msec_t rttvar; | |
101 | 106 |
102 #if (NGX_DEBUG) | 107 #if (NGX_DEBUG) |
103 ngx_uint_t nframes; | 108 ngx_uint_t nframes; |
104 #endif | 109 #endif |
105 | 110 |
187 static ngx_int_t ngx_quic_send_new_token(ngx_connection_t *c); | 192 static ngx_int_t ngx_quic_send_new_token(ngx_connection_t *c); |
188 | 193 |
189 static ngx_int_t ngx_quic_handle_ack_frame(ngx_connection_t *c, | 194 static ngx_int_t ngx_quic_handle_ack_frame(ngx_connection_t *c, |
190 ngx_quic_header_t *pkt, ngx_quic_ack_frame_t *f); | 195 ngx_quic_header_t *pkt, ngx_quic_ack_frame_t *f); |
191 static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c, | 196 static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c, |
192 ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max); | 197 ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max, |
198 ngx_msec_t *send_time); | |
199 static void ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, | |
200 enum ssl_encryption_level_t level, ngx_msec_t send_time); | |
193 static void ngx_quic_handle_stream_ack(ngx_connection_t *c, | 201 static void ngx_quic_handle_stream_ack(ngx_connection_t *c, |
194 ngx_quic_frame_t *f); | 202 ngx_quic_frame_t *f); |
195 | 203 |
196 static ngx_int_t ngx_quic_handle_ordered_frame(ngx_connection_t *c, | 204 static ngx_int_t ngx_quic_handle_ordered_frame(ngx_connection_t *c, |
197 ngx_quic_frames_stream_t *fs, ngx_quic_frame_t *frame, | 205 ngx_quic_frames_stream_t *fs, ngx_quic_frame_t *frame, |
663 ngx_queue_init(&qc->crypto[i].frames); | 671 ngx_queue_init(&qc->crypto[i].frames); |
664 } | 672 } |
665 | 673 |
666 ngx_queue_init(&qc->free_frames); | 674 ngx_queue_init(&qc->free_frames); |
667 | 675 |
676 qc->avg_rtt = NGX_QUIC_INITIAL_RTT; | |
677 qc->rttvar = NGX_QUIC_INITIAL_RTT / 2; | |
678 qc->min_rtt = NGX_TIMER_INFINITE; | |
679 | |
680 /* | |
681 * qc->latest_rtt = 0 | |
682 */ | |
683 | |
668 qc->retransmit.log = c->log; | 684 qc->retransmit.log = c->log; |
669 qc->retransmit.data = c; | 685 qc->retransmit.data = c; |
670 qc->retransmit.handler = ngx_quic_retransmit_handler; | 686 qc->retransmit.handler = ngx_quic_retransmit_handler; |
671 qc->retransmit.cancelable = 1; | 687 qc->retransmit.cancelable = 1; |
672 | 688 |
2208 ngx_quic_ack_frame_t *ack) | 2224 ngx_quic_ack_frame_t *ack) |
2209 { | 2225 { |
2210 ssize_t n; | 2226 ssize_t n; |
2211 u_char *pos, *end; | 2227 u_char *pos, *end; |
2212 uint64_t gap, range; | 2228 uint64_t gap, range; |
2229 ngx_msec_t send_time; | |
2213 ngx_uint_t i, min, max; | 2230 ngx_uint_t i, min, max; |
2214 ngx_quic_send_ctx_t *ctx; | 2231 ngx_quic_send_ctx_t *ctx; |
2215 | 2232 |
2216 ctx = ngx_quic_get_send_ctx(c->quic, pkt->level); | 2233 ctx = ngx_quic_get_send_ctx(c->quic, pkt->level); |
2217 | 2234 |
2232 } | 2249 } |
2233 | 2250 |
2234 min = ack->largest - ack->first_range; | 2251 min = ack->largest - ack->first_range; |
2235 max = ack->largest; | 2252 max = ack->largest; |
2236 | 2253 |
2237 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max) != NGX_OK) { | 2254 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time) |
2255 != NGX_OK) | |
2256 { | |
2238 return NGX_ERROR; | 2257 return NGX_ERROR; |
2239 } | 2258 } |
2240 | 2259 |
2241 /* 13.2.3. Receiver Tracking of ACK Frames */ | 2260 /* 13.2.3. Receiver Tracking of ACK Frames */ |
2242 if (ctx->largest_ack < max) { | 2261 if (ctx->largest_ack < max) { |
2243 ctx->largest_ack = max; | 2262 ctx->largest_ack = max; |
2244 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, | 2263 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, |
2245 "quic updated largest received ack: %ui", max); | 2264 "quic updated largest received ack: %ui", max); |
2265 | |
2266 /* | |
2267 * An endpoint generates an RTT sample on receiving an | |
2268 * ACK frame that meets the following two conditions: | |
2269 * | |
2270 * - the largest acknowledged packet number is newly acknowledged | |
2271 * - at least one of the newly acknowledged packets was ack-eliciting. | |
2272 */ | |
2273 | |
2274 if (send_time != NGX_TIMER_INFINITE) { | |
2275 ngx_quic_rtt_sample(c, ack, pkt->level, send_time); | |
2276 } | |
2246 } | 2277 } |
2247 | 2278 |
2248 pos = ack->ranges_start; | 2279 pos = ack->ranges_start; |
2249 end = ack->ranges_end; | 2280 end = ack->ranges_end; |
2250 | 2281 |
2272 return NGX_ERROR; | 2303 return NGX_ERROR; |
2273 } | 2304 } |
2274 | 2305 |
2275 min = max - range + 1; | 2306 min = max - range + 1; |
2276 | 2307 |
2277 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max) != NGX_OK) { | 2308 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time) |
2309 != NGX_OK) | |
2310 { | |
2278 return NGX_ERROR; | 2311 return NGX_ERROR; |
2279 } | 2312 } |
2280 } | 2313 } |
2281 | 2314 |
2282 return NGX_OK; | 2315 return NGX_OK; |
2283 } | 2316 } |
2284 | 2317 |
2285 | 2318 |
2286 static ngx_int_t | 2319 static ngx_int_t |
2287 ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx, | 2320 ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx, |
2288 uint64_t min, uint64_t max) | 2321 uint64_t min, uint64_t max, ngx_msec_t *send_time) |
2289 { | 2322 { |
2323 uint64_t found_num; | |
2290 ngx_uint_t found; | 2324 ngx_uint_t found; |
2291 ngx_queue_t *q; | 2325 ngx_queue_t *q; |
2292 ngx_quic_frame_t *f; | 2326 ngx_quic_frame_t *f; |
2293 ngx_quic_connection_t *qc; | 2327 ngx_quic_connection_t *qc; |
2294 | 2328 |
2295 qc = c->quic; | 2329 qc = c->quic; |
2296 | 2330 |
2331 *send_time = NGX_TIMER_INFINITE; | |
2297 found = 0; | 2332 found = 0; |
2298 | 2333 found_num = 0; |
2299 q = ngx_queue_head(&ctx->sent); | 2334 |
2335 q = ngx_queue_last(&ctx->sent); | |
2300 | 2336 |
2301 while (q != ngx_queue_sentinel(&ctx->sent)) { | 2337 while (q != ngx_queue_sentinel(&ctx->sent)) { |
2302 | 2338 |
2303 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | 2339 f = ngx_queue_data(q, ngx_quic_frame_t, queue); |
2340 q = ngx_queue_prev(q); | |
2304 | 2341 |
2305 if (f->pnum >= min && f->pnum <= max) { | 2342 if (f->pnum >= min && f->pnum <= max) { |
2306 ngx_quic_congestion_ack(c, f); | 2343 ngx_quic_congestion_ack(c, f); |
2307 | 2344 |
2308 ngx_quic_handle_stream_ack(c, f); | 2345 ngx_quic_handle_stream_ack(c, f); |
2309 | 2346 |
2310 q = ngx_queue_next(q); | 2347 if (f->pnum > found_num || !found) { |
2348 *send_time = f->last; | |
2349 found_num = f->pnum; | |
2350 } | |
2351 | |
2311 ngx_queue_remove(&f->queue); | 2352 ngx_queue_remove(&f->queue); |
2312 ngx_quic_free_frame(c, f); | 2353 ngx_quic_free_frame(c, f); |
2313 found = 1; | 2354 found = 1; |
2314 | |
2315 } else { | |
2316 q = ngx_queue_next(q); | |
2317 } | 2355 } |
2318 } | 2356 } |
2319 | 2357 |
2320 if (!found) { | 2358 if (!found) { |
2321 | 2359 |
2337 if (!qc->push.timer_set) { | 2375 if (!qc->push.timer_set) { |
2338 ngx_post_event(&qc->push, &ngx_posted_events); | 2376 ngx_post_event(&qc->push, &ngx_posted_events); |
2339 } | 2377 } |
2340 | 2378 |
2341 return NGX_OK; | 2379 return NGX_OK; |
2380 } | |
2381 | |
2382 | |
2383 static void | |
2384 ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, | |
2385 enum ssl_encryption_level_t level, ngx_msec_t send_time) | |
2386 { | |
2387 ngx_msec_t latest_rtt, ack_delay, adjusted_rtt, rttvar_sample; | |
2388 ngx_quic_connection_t *qc; | |
2389 | |
2390 qc = c->quic; | |
2391 | |
2392 latest_rtt = ngx_current_msec - send_time; | |
2393 qc->latest_rtt = latest_rtt; | |
2394 | |
2395 if (qc->min_rtt == NGX_TIMER_INFINITE) { | |
2396 qc->min_rtt = latest_rtt; | |
2397 qc->avg_rtt = latest_rtt; | |
2398 qc->rttvar = latest_rtt / 2; | |
2399 | |
2400 } else { | |
2401 qc->min_rtt = ngx_min(qc->min_rtt, latest_rtt); | |
2402 | |
2403 | |
2404 if (level == ssl_encryption_application) { | |
2405 ack_delay = ack->delay * (1 << qc->ctp.ack_delay_exponent) / 1000; | |
2406 ack_delay = ngx_min(ack_delay, qc->ctp.max_ack_delay); | |
2407 | |
2408 } else { | |
2409 ack_delay = 0; | |
2410 } | |
2411 | |
2412 adjusted_rtt = latest_rtt; | |
2413 | |
2414 if (qc->min_rtt + ack_delay < latest_rtt) { | |
2415 adjusted_rtt -= ack_delay; | |
2416 } | |
2417 | |
2418 qc->avg_rtt = 0.875 * qc->avg_rtt + 0.125 * adjusted_rtt; | |
2419 rttvar_sample = ngx_abs((ngx_msec_int_t) (qc->avg_rtt - adjusted_rtt)); | |
2420 qc->rttvar = 0.75 * qc->rttvar + 0.25 * rttvar_sample; | |
2421 } | |
2422 | |
2423 ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
2424 "quic rtt sample: latest %M, min %M, avg %M, var %M", | |
2425 latest_rtt, qc->min_rtt, qc->avg_rtt, qc->rttvar); | |
2342 } | 2426 } |
2343 | 2427 |
2344 | 2428 |
2345 static void | 2429 static void |
2346 ngx_quic_handle_stream_ack(ngx_connection_t *c, ngx_quic_frame_t *f) | 2430 ngx_quic_handle_stream_ack(ngx_connection_t *c, ngx_quic_frame_t *f) |