details:
https://github.com/nginx/nginx/commit/f9a7e7cc11e71b2c62d4c5b9ac4feb7e92913c64
branches: master
commit: f9a7e7cc11e71b2c62d4c5b9ac4feb7e92913c64
user: Roman Arutyunyan <a...@nginx.com>
date: Thu, 7 Nov 2024 17:25:45 +0400
description:
QUIC: CUBIC congestion control.
---
src/event/quic/ngx_event_quic.c | 1 +
src/event/quic/ngx_event_quic_ack.c | 189 +++++++++++++++++++++++++++--
src/event/quic/ngx_event_quic_connection.h | 6 +
src/event/quic/ngx_event_quic_migration.c | 1 +
4 files changed, 185 insertions(+), 12 deletions(-)
diff --git a/src/event/quic/ngx_event_quic.c b/src/event/quic/ngx_event_quic.c
index 11497a6d7..49d30e82a 100644
--- a/src/event/quic/ngx_event_quic.c
+++ b/src/event/quic/ngx_event_quic.c
@@ -312,6 +312,7 @@ ngx_quic_new_connection(ngx_connection_t *c,
ngx_quic_conf_t *conf,
ngx_max(2 * NGX_QUIC_MIN_INITIAL_SIZE,
14720));
qc->congestion.ssthresh = (size_t) -1;
+ qc->congestion.mtu = NGX_QUIC_MIN_INITIAL_SIZE;
qc->congestion.recovery_start = ngx_current_msec - 1;
if (pkt->validated && pkt->retried) {
diff --git a/src/event/quic/ngx_event_quic_ack.c
b/src/event/quic/ngx_event_quic_ack.c
index d16545a1d..6b0eef35e 100644
--- a/src/event/quic/ngx_event_quic_ack.c
+++ b/src/event/quic/ngx_event_quic_ack.c
@@ -20,6 +20,10 @@
/* RFC 9002, 7.6.1. Duration: kPersistentCongestionThreshold */
#define NGX_QUIC_PERSISTENT_CONGESTION_THR 3
+/* CUBIC parameters x10 */
+#define NGX_QUIC_CUBIC_BETA 7
+#define MGX_QUIC_CUBIC_C 4
+
/* send time of ACK'ed packets */
typedef struct {
@@ -35,10 +39,12 @@ static void ngx_quic_rtt_sample(ngx_connection_t *c,
ngx_quic_ack_frame_t *ack,
static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c,
ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max,
ngx_quic_ack_stat_t *st);
+static size_t ngx_quic_congestion_cubic(ngx_connection_t *c);
static void ngx_quic_drop_ack_ranges(ngx_connection_t *c,
ngx_quic_send_ctx_t *ctx, uint64_t pn);
static ngx_int_t ngx_quic_detect_lost(ngx_connection_t *c,
ngx_quic_ack_stat_t *st);
+static ngx_msec_t ngx_quic_congestion_cubic_time(ngx_connection_t *c);
static ngx_msec_t ngx_quic_pcg_duration(ngx_connection_t *c);
static void ngx_quic_persistent_congestion(ngx_connection_t *c);
static ngx_msec_t ngx_quic_oldest_sent_packet(ngx_connection_t *c);
@@ -314,6 +320,7 @@ ngx_quic_handle_ack_frame_range(ngx_connection_t *c,
ngx_quic_send_ctx_t *ctx,
void
ngx_quic_congestion_ack(ngx_connection_t *c, ngx_quic_frame_t *f)
{
+ size_t w_cubic;
ngx_uint_t blocked;
ngx_msec_t now, timer;
ngx_quic_congestion_t *cg;
@@ -370,11 +377,46 @@ ngx_quic_congestion_ack(ngx_connection_t *c,
ngx_quic_frame_t *f)
now, cg->window, cg->ssthresh, cg->in_flight);
} else {
- cg->window += (uint64_t) qc->path->mtu * f->plen / cg->window;
- ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
- "quic congestion ack reno t:%M win:%uz if:%uz",
- now, cg->window, cg->in_flight);
+ /* RFC 9438, 4.2. Window Increase Function */
+
+ w_cubic = ngx_quic_congestion_cubic(c);
+
+ if (cg->window < cg->w_prior) {
+ cg->w_est += (uint64_t) cg->mtu * f->plen
+ * 3 * (10 - NGX_QUIC_CUBIC_BETA)
+ / (10 + NGX_QUIC_CUBIC_BETA) / cg->window;
+
+ } else {
+ cg->w_est += (uint64_t) cg->mtu * f->plen / cg->window;
+ }
+
+ if (w_cubic < cg->w_est) {
+ cg->window = cg->w_est;
+
+ ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
+ "quic congestion ack reno t:%M win:%uz c:%uz if:%uz",
+ now, cg->window, w_cubic, cg->in_flight);
+
+ } else if (w_cubic > cg->window) {
+
+ if (w_cubic >= cg->window * 3 / 2) {
+ cg->window += cg->mtu / 2;
+
+ } else {
+ cg->window += (uint64_t) cg->mtu * (w_cubic - cg->window)
+ / cg->window;
+ }
+
+ ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
+ "quic congestion ack cubic t:%M win:%uz c:%uz
if:%uz",
+ now, cg->window, w_cubic, cg->in_flight);
+
+ } else {
+ ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0,
+ "quic congestion ack skip t:%M win:%uz c:%uz
if:%uz",
+ now, cg->window, w_cubic, cg->in_flight);
+ }
}
done:
@@ -385,9 +427,62 @@ done:
}
+static size_t
+ngx_quic_congestion_cubic(ngx_connection_t *c)
+{
+ int64_t w, t, cc;
+ ngx_msec_t now;
+ ngx_quic_congestion_t *cg;
+ ngx_quic_connection_t *qc;
+
+ qc = ngx_quic_get_connection(c);
+ cg = &qc->congestion;
+
+ ngx_quic_congestion_idle(c, cg->idle);
+
+ now = ngx_current_msec;
+ t = (ngx_msec_int_t) (now - cg->k);
+
+ if (t > 1000000) {
+ w = NGX_MAX_SIZE_T_VALUE;
+ goto done;
+ }
+
+ if (t < -1000000) {
+ w = 0;
+ goto done;
+ }
+
+ /*
+ * RFC 9438, Figure 1
+ *
+ * w_cubic = C * (t_msec / 1000) ^ 3 * mtu + w_max
+ */
+
+ cc = 10000000000ll / (int64_t) cg->mtu / MGX_QUIC_CUBIC_C;
+ w = t * t * t / cc + (int64_t) cg->w_max;
+
+ if (w > NGX_MAX_SIZE_T_VALUE) {
+ w = NGX_MAX_SIZE_T_VALUE;
+ }
+
+ if (w < 0) {
+ w = 0;
+ }
+
+done:
+
+ ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
+ "quic cubic t:%L w:%L wm:%uz", t, w, cg->w_max);
+
+ return w;
+}
+
+
void
ngx_quic_congestion_idle(ngx_connection_t *c, ngx_uint_t idle)
{
+ ngx_msec_t now;
ngx_quic_congestion_t *cg;
ngx_quic_connection_t *qc;
@@ -397,6 +492,18 @@ ngx_quic_congestion_idle(ngx_connection_t *c, ngx_uint_t
idle)
ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0,
"quic congestion idle:%ui", idle);
+ if (cg->window >= cg->ssthresh) {
+ /* RFC 9438, 5.8. Behavior for Application-Limited Flows */
+
+ now = ngx_current_msec;
+
+ if (cg->idle) {
+ cg->k += now - cg->idle_start;
+ }
+
+ cg->idle_start = now;
+ }
+
cg->idle = idle;
}
@@ -580,8 +687,9 @@ ngx_quic_persistent_congestion(ngx_connection_t *c)
qc = ngx_quic_get_connection(c);
cg = &qc->congestion;
+ cg->mtu = qc->path->mtu;
cg->recovery_start = ngx_quic_oldest_sent_packet(c) - 1;
- cg->window = qc->path->mtu * 2;
+ cg->window = cg->mtu * 2;
ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0,
"quic congestion persistent t:%M win:%uz",
@@ -763,14 +871,19 @@ ngx_quic_congestion_lost(ngx_connection_t *c,
ngx_quic_frame_t *f)
goto done;
}
- cg->recovery_start = now;
- cg->window /= 2;
-
- if (cg->window < qc->path->mtu * 2) {
- cg->window = qc->path->mtu * 2;
- }
+ /* RFC 9438, 4.6. Multiplicative Decrease */
- cg->ssthresh = cg->window;
+ cg->mtu = qc->path->mtu;
+ cg->recovery_start = now;
+ cg->w_prior = cg->window;
+ /* RFC 9438, 4.7. Fast Convergence */
+ cg->w_max = (cg->window < cg->w_max)
+ ? cg->window * (10 + NGX_QUIC_CUBIC_BETA) / 20 : cg->window;
+ cg->ssthresh = cg->in_flight * NGX_QUIC_CUBIC_BETA / 10;
+ cg->window = ngx_max(cg->ssthresh, cg->mtu * 2);
+ cg->w_est = cg->window;
+ cg->k = now + ngx_quic_congestion_cubic_time(c);
+ cg->idle_start = now;
ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0,
"quic congestion lost t:%M win:%uz if:%uz",
@@ -784,6 +897,58 @@ done:
}
+static ngx_msec_t
+ngx_quic_congestion_cubic_time(ngx_connection_t *c)
+{
+ int64_t v, x, d, cc;
+ ngx_uint_t n;
+ ngx_quic_congestion_t *cg;
+ ngx_quic_connection_t *qc;
+
+ qc = ngx_quic_get_connection(c);
+ cg = &qc->congestion;
+
+ /*
+ * RFC 9438, Figure 2
+ *
+ * k_msec = ((w_max - cwnd_epoch) / C / mtu) ^ 1/3 * 1000
+ */
+
+ if (cg->w_max <= cg->window) {
+ return 0;
+ }
+
+ cc = 10000000000ll / (int64_t) cg->mtu / MGX_QUIC_CUBIC_C;
+ v = (int64_t) (cg->w_max - cg->window) * cc;
+
+ /*
+ * Newton-Raphson method for x ^ 3 = v:
+ *
+ * x_next = (2 * x_prev + v / x_prev ^ 2) / 3
+ */
+
+ x = 5000;
+
+ for (n = 1; n <= 10; n++) {
+ d = (v / x / x - x) / 3;
+ x += d;
+
+ if (ngx_abs(d) <= 100) {
+ break;
+ }
+ }
+
+ if (x > NGX_MAX_SIZE_T_VALUE) {
+ return NGX_MAX_SIZE_T_VALUE;
+ }
+
+ ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0,
+ "quic cubic time:%L n:%ui", x, n);
+
+ return x;
+}
+
+
void
ngx_quic_set_lost_timer(ngx_connection_t *c)
{
diff --git a/src/event/quic/ngx_event_quic_connection.h
b/src/event/quic/ngx_event_quic_connection.h
index acc09c142..716d62308 100644
--- a/src/event/quic/ngx_event_quic_connection.h
+++ b/src/event/quic/ngx_event_quic_connection.h
@@ -168,7 +168,13 @@ typedef struct {
size_t in_flight;
size_t window;
size_t ssthresh;
+ size_t w_max;
+ size_t w_est;
+ size_t w_prior;
+ size_t mtu;
ngx_msec_t recovery_start;
+ ngx_msec_t idle_start;
+ ngx_msec_t k;
ngx_uint_t idle; /* unsigned idle:1; */
} ngx_quic_congestion_t;
diff --git a/src/event/quic/ngx_event_quic_migration.c
b/src/event/quic/ngx_event_quic_migration.c
index 1d914ffd8..6befc3427 100644
--- a/src/event/quic/ngx_event_quic_migration.c
+++ b/src/event/quic/ngx_event_quic_migration.c
@@ -186,6 +186,7 @@ valid:
ngx_max(2 * NGX_QUIC_MIN_INITIAL_SIZE,
14720));
qc->congestion.ssthresh = (size_t) -1;
+ qc->congestion.mtu = NGX_QUIC_MIN_INITIAL_SIZE;
qc->congestion.recovery_start = ngx_current_msec - 1;
ngx_quic_init_rtt(qc);
_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
https://mailman.nginx.org/mailman/listinfo/nginx-devel
