diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-13 12:18:05 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-13 12:18:05 +0000 |
commit | b46aad6df449445a9fc4aa7b32bd40005438e3f7 (patch) | |
tree | 751aa858ca01f35de800164516b298887382919d /src/quic_cc_cubic.c | |
parent | Initial commit. (diff) | |
download | haproxy-upstream/2.9.5.tar.xz haproxy-upstream/2.9.5.zip |
Adding upstream version 2.9.5.upstream/2.9.5
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/quic_cc_cubic.c')
-rw-r--r-- | src/quic_cc_cubic.c | 542 |
1 files changed, 542 insertions, 0 deletions
diff --git a/src/quic_cc_cubic.c b/src/quic_cc_cubic.c new file mode 100644 index 0000000..76a62ac --- /dev/null +++ b/src/quic_cc_cubic.c @@ -0,0 +1,542 @@ +#include <haproxy/quic_cc.h> +#include <haproxy/quic_trace.h> +#include <haproxy/ticks.h> +#include <haproxy/trace.h> + +/* IMPORTANT NOTE about the units defined by the RFC 9438 + * (CUBIC for Fast and Long-Distance Networks): + * + * RFC 9438 4.1. Definitions: + * The unit of all window sizes in this document is segments of the SMSS, and + * the unit of all times is seconds. Implementations can use bytes to express + * window sizes, which would require factoring in the SMSS wherever necessary + * and replacing segments_acked (Figure 4) with the number of acknowledged + * bytes. + */ + +/* So, this is the reason why here in this implementation each time a number + * of segments is used (typically a congestion window value), its value is + * multiplied by the MTU value. + */ + +/* This source file is highly inspired from Linux kernel source file + * implementation for TCP Cubic. In fact, we have no choice if we do + * not want to use any floating point operations to be fast! + * (See net/ipv4/tcp_cubic.c) + */ + +/* Constants definitions: + * CUBIC_BETA_SCALED refers to the scaled value of RFC 9438 beta_cubic variable. + * CUBIC_C_SCALED refers to the scaled value of RFC 9438 C variable. + */ + +/* The right shifting value to apply to scaled values to get its real value. */ +#define CUBIC_SCALE_FACTOR_SHIFT 10 + +/* CUBIC multiplicative decrease factor as described in RFC 9438 section 4.6 */ +#define CUBIC_BETA_SCALED 717 /* beta_cubic = 0.7 (constant) */ + +/* CUBIC C constant that determines the aggressiveness of CUBIC in competing + * with other congestion control algorithms in high-BDP networks. + */ +#define CUBIC_C_SCALED 410 /* RFC 9438 C = 0.4 segment/seconds^3 + * or 410 mB/s^3 in this implementation. + */ + +/* The scaled value of 1 */ +#define CUBIC_ONE_SCALED (1 << CUBIC_SCALE_FACTOR_SHIFT) + +/* The maximum time value which may be cubed and multiplied by CUBIC_C_SCALED */ +#define CUBIC_TIME_LIMIT 355535ULL /* ms */ + +/* By connection CUBIC algorithm state. Note that the current congestion window + * value is not stored in this structure. + */ +struct cubic { + /* QUIC_CC_ST_* state values. */ + uint32_t state; + /* Slow start threshold (in bytes) */ + uint32_t ssthresh; + /* Remaining number of acknowledged bytes between two ACK for CUBIC congestion + * control window (in bytes). + */ + uint32_t remaining_inc; + /* Start time of at which the current avoidance stage started (in ms). */ + uint32_t t_epoch; + /* The window to reach for each recovery period during a concave region (in bytes). */ + uint32_t W_target; + /* The time period to reach W_target during a concave region (in ms). */ + uint32_t K; + /* The last window maximum reached (in bytes). */ + uint32_t last_w_max; + /* Estimated value of the Reno congestion window in the TCP-friendly region (in bytes). */ + uint32_t W_est; + /* Remaining number of acknowledged bytes between two ACKs for estimated + * TCP-Reno congestion control window (in bytes). + */ + uint32_t remaining_W_est_inc; + /* Start time of recovery period (used to avoid re-entering this state, if already + * in recovery period) (in ms). + */ + uint32_t recovery_start_time; +}; + +static void quic_cc_cubic_reset(struct quic_cc *cc) +{ + struct cubic *c = quic_cc_priv(cc); + + TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc); + c->state = QUIC_CC_ST_SS; + c->ssthresh = QUIC_CC_INFINITE_SSTHESH; + c->remaining_inc = 0; + c->remaining_W_est_inc = 0; + c->t_epoch = 0; + c->W_target = 0; + c->K = 0; + c->last_w_max = 0; + c->W_est = 0; + c->recovery_start_time = 0; + TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc); +} + +static int quic_cc_cubic_init(struct quic_cc *cc) +{ + quic_cc_cubic_reset(cc); + return 1; +} + +/* Cubic root. + * Highly inspired from Linux kernel sources. + * See net/ipv4/tcp_cubic.c + */ +static uint32_t cubic_root(uint64_t val) +{ + uint32_t x, b, shift; + + static const uint8_t v[] = { + 0, 54, 54, 54, 118, 118, 118, 118, + 123, 129, 134, 138, 143, 147, 151, 156, + 157, 161, 164, 168, 170, 173, 176, 179, + 181, 185, 187, 190, 192, 194, 197, 199, + 200, 202, 204, 206, 209, 211, 213, 215, + 217, 219, 221, 222, 224, 225, 227, 229, + 231, 232, 234, 236, 237, 239, 240, 242, + 244, 245, 246, 248, 250, 251, 252, 254, + }; + + if (!val || (b = my_flsl(val)) < 7) { + /* val in [0..63] */ + return ((uint32_t)v[(uint32_t)val] + 35) >> 6; + } + + b = ((b * 84) >> 8) - 1; + shift = (val >> (b * 3)); + + x = ((uint32_t)(((uint32_t)v[shift] + 10) << b)) >> 6; + + x = 2 * x + (uint32_t)(val / ((uint64_t)x * (uint64_t)(x - 1))); + x = ((x * 341) >> 10); + + return x; +} + +/* + * RFC 9438 3.1. Principle 1 for the CUBIC Increase Function + * + * For better network utilization and stability, CUBIC [HRX08] uses a cubic + * window increase function in terms of the elapsed time from the last + * congestion event. While most congestion control algorithms that provide + * alternatives to Reno increase the congestion window using convex functions, + * CUBIC uses both the concave and convex profiles of a cubic function for + * window growth. + * + * After a window reduction in response to a congestion event detected by + * duplicate acknowledgments (ACKs), Explicit Congestion Notification-Echo + * (ECN-Echo (ECE)) ACKs [RFC3168], RACK-TLP for TCP [RFC8985], or QUIC loss + * detection [RFC9002], CUBIC remembers the congestion window size at which it + * received the congestion event and performs a multiplicative decrease of the + * congestion window. When CUBIC enters into congestion avoidance, it starts to + * increase the congestion window using the concave profile of the cubic + * function. The cubic function is set to have its plateau at the remembered + * congestion window size, so that the concave window increase continues until + * then. After that, the cubic function turns into a convex profile and the + * convex window increase begins. + * + * W_cubic(time) (bytes) + * ^ convex region + * | <-------------------------> + * | . + + * | . + + * | . + + * | . + + * | . + ^ + * | . + | W_cubic_t + * | . + | + * | . + | + * W_target |-----------+--------------------------+------------------------+ + * (W_max) | +. + . t + * | + . + . + * | + . + . + * | + . + . + * | + . + . + * | .+ . + * | + . + * | + . + * | + . + * | . . + * | . . + * | . . + * +-----------+--------------------------+-+------------------------> time (s) + * 0 t_epoch (t_epoch + K) + * <--------------------------> + * . concave region + * . + * congestion + * event + * + * RFC 9438 4.2. Window Increase Function: + * + * W_cubic(t) = C*(t-K)^3 + W_max (Figure 1) + * K = cubic_root((W_max - cwnd_epoch)/C) (Figure 2) + * + * +--------------------------------------------------------------------+ + * | RFC 9438 definitions | Code variables | + * +--------------------------------------------------------------------+ + * | C (segments/s^3) | CUBIC_C_SCALED (mB/s^3) | + * +--------------------------------------------------------------------+ + * | W_max (segments) | c->last_w_max - path->cwnd (bytes) | + * +--------------------------------------------------------------------+ + * | K (s) | c->K (ms) | + * +--------------------------------------------------------------------+ + * | beta_cubic (constant) | CUBIC_BETA_SCALED (constant) | + * +--------------------------------------------------------------------+ + */ +static inline void quic_cubic_update(struct quic_cc *cc, uint32_t acked) +{ + struct cubic *c = quic_cc_priv(cc); + struct quic_cc_path *path = container_of(cc, struct quic_cc_path, cc); + /* The elapsed time since the start of the congestion event. */ + uint32_t elapsed_time; + /* Target value of the congestion window. */ + uint32_t target; + /* The time at which the congestion window will be computed based + * on the cubic increase function. + */ + uint64_t t; + /* The computed value of the congestion window at time t based on the cubic + * increase function. + */ + uint64_t W_cubic_t; + uint32_t inc, inc_diff; + + TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc); + if (!c->t_epoch) { + c->t_epoch = now_ms; + if (c->last_w_max <= path->cwnd) { + c->K = 0; + c->W_target = path->cwnd; + } + else { + /* K value computing (in seconds): + * K = cubic_root((W_max - cwnd_epoch)/C) (Figure 2) + * Note that K is stored in milliseconds. + */ + c->K = cubic_root(((c->last_w_max - path->cwnd) << CUBIC_SCALE_FACTOR_SHIFT) / (CUBIC_C_SCALED * path->mtu)); + /* Convert to miliseconds. */ + c->K *= 1000; + c->W_target = c->last_w_max; + } + + c->W_est = path->cwnd; + c->remaining_inc = 0; + c->remaining_W_est_inc = 0; + } + + elapsed_time = now_ms + path->loss.rtt_min - c->t_epoch; + if (elapsed_time < c->K) { + t = c->K - elapsed_time; + } + else { + t = elapsed_time - c->K; + } + + if (t > CUBIC_TIME_LIMIT) { + /* TODO : should not happen if we handle the case + * of very late acks receipt. This must be handled as a congestion + * control event: a very late ack should trigger a congestion + * control algorithm reset. + */ + quic_cc_cubic_reset(cc); + goto leave; + } + + /* Compute W_cubic_t at t time. */ + W_cubic_t = CUBIC_C_SCALED * path->mtu; + W_cubic_t = (W_cubic_t * t) / 1000; + W_cubic_t = (W_cubic_t * t) / 1000; + W_cubic_t = (W_cubic_t * t) / 1000; + W_cubic_t >>= CUBIC_SCALE_FACTOR_SHIFT; + if (elapsed_time < c->K) + target = c->W_target - W_cubic_t; + else + target = c->W_target + W_cubic_t; + + if (target > path->cwnd) { + /* Concave region */ + + /* RFC 9438 4.4. Concave Region + * + * When receiving a new ACK in congestion avoidance, if CUBIC is not in + * the Reno-friendly region and cwnd is less than Wmax, then CUBIC is + * in the concave region. In this region, cwnd MUST be incremented by + * (target - cwnd) / cwnd. + */ + inc_diff = c->remaining_inc + path->mtu * (target - path->cwnd); + c->remaining_inc = inc_diff % path->cwnd; + inc = inc_diff / path->cwnd; + } + else { + /* Convex region: very small increment */ + + /* RFC 9438 4.5. Convex Region + * + * When receiving a new ACK in congestion avoidance, if CUBIC is not in + * the Reno-friendly region and cwnd is larger than or equal to Wmax, + * then CUBIC is in the convex region.The convex region indicates that + * the network conditions might have changed since the last congestion + * event, possibly implying more available bandwidth after some flow + * departures. Since the Internet is highly asynchronous, some amount + * of perturbation is always possible without causing a major change in + * available bandwidth.Unless the cwnd is overridden by the AIMD window + * increase, CUBIC will behave cautiously when operating in this region. + * The convex profile aims to increase the window very slowly at the + * beginning when cwnd is around Wmax and then gradually increases its + * rate of increase. This region is also called the "maximum probing + * phase", since CUBIC is searching for a new Wmax. In this region, + * cwnd MUST be incremented by (target - cwnd) / cwnd) for each received + * new ACK, where target is calculated as described in Section 4.2. + */ + inc_diff = c->remaining_inc + path->mtu; + c->remaining_inc = inc_diff % (100 * path->cwnd); + inc = inc_diff / (100 * path->cwnd); + } + + inc_diff = c->remaining_W_est_inc + path->mtu * acked; + c->W_est += inc_diff / path->cwnd; + c->remaining_W_est_inc = inc_diff % path->cwnd; + + /* TCP friendliness : + * RFC 9438 4.3. Reno-Friendly Region + * + * Reno performs well in certain types of networks -- for example, under + * short RTTs and small bandwidths (or small BDPs). In these networks, + * CUBIC remains in the Reno-friendly region to achieve at least the same + * throughput as Reno. + * + * When receiving a new ACK in congestion avoidance (where cwnd could be + * greater than or less than Wmax), CUBIC checks whether Wcubic(t) is less + * than West. If so, CUBIC is in the Reno-friendly region and cwnd SHOULD + * be set to West at each reception of a new ACK. + * + * West is set equal to cwnd_epoch at the start of the congestion avoidance + * stage. After that, on every new ACK, West is updated using Figure 4. + * Note that this equation uses segments_acked and cwnd is measured in + * segments. An implementation that measures cwnd in bytes should adjust the + * equation accordingly using the number of acknowledged bytes and the SMSS. + * Also note that this equation works for connections with enabled or + * disabled delayed ACKs [RFC5681], as segments_acked will be different based + * on the segments actually acknowledged by a new ACK. + * + * Figure 4 : West = West + alpha_cubic * (segments_acked / cwnd) + * + * Once West has grown to reach the cwnd at the time of most recently + * setting ssthresh -- that is, West >= cwndprior -- the sender SHOULD set + * alpha_cubic to 1 to ensure that it can achieve the same congestion window + * increment rate as Reno, which uses AIMD(1, 0.5). + */ + if (c->W_est > path->cwnd) { + uint32_t W_est_inc = path->mtu * (c->W_est - path->cwnd) / path->cwnd; + if (W_est_inc > inc) + inc = W_est_inc; + } + + path->cwnd += inc; + path->cwnd = QUIC_MIN(path->max_cwnd, path->cwnd); + path->mcwnd = QUIC_MAX(path->cwnd, path->mcwnd); + leave: + TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc); +} + +static void quic_cc_cubic_slow_start(struct quic_cc *cc) +{ + TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc); + quic_cc_cubic_reset(cc); + TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc); +} + +static void quic_enter_recovery(struct quic_cc *cc) +{ + struct quic_cc_path *path = container_of(cc, struct quic_cc_path, cc); + struct cubic *c = quic_cc_priv(cc); + /* Current cwnd as number of packets */ + + TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc); + c->t_epoch = 0; + c->recovery_start_time = now_ms; + + /* RFC 9438 4.7. Fast Convergence + * + * To improve convergence speed, CUBIC uses a heuristic. When a new flow + * joins the network, existing flows need to give up some of their bandwidth + * to allow the new flow some room for growth if the existing flows have + * been using all the network bandwidth. To speed up this bandwidth release + * by existing flows, the following fast convergence mechanism SHOULD be + * implemented.With fast convergence, when a congestion event occurs, Wmax + * is updated as follows, before the window reduction described in Section + * 4.6. + * + * if cwnd < Wmax and fast convergence enabled, further reduce Wax: + * Wmax = cwnd * (1 + beta_cubic) + * otherwise, remember cwn before reduction: + * Wmax = cwnd + */ + if (path->cwnd < c->last_w_max) { + /* (1 + beta_cubic) * path->cwnd / 2 */ + c->last_w_max = (path->cwnd * (CUBIC_ONE_SCALED + CUBIC_BETA_SCALED) / 2) >> CUBIC_SCALE_FACTOR_SHIFT; + } + else { + c->last_w_max = path->cwnd; + } + + c->ssthresh = (CUBIC_BETA_SCALED * path->cwnd) >> CUBIC_SCALE_FACTOR_SHIFT; + path->cwnd = QUIC_MAX(c->ssthresh, (uint32_t)path->min_cwnd); + c->state = QUIC_CC_ST_RP; + TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc, NULL, cc); +} + +/* Congestion slow-start callback. */ +static void quic_cc_cubic_ss_cb(struct quic_cc *cc, struct quic_cc_event *ev) +{ + struct quic_cc_path *path = container_of(cc, struct quic_cc_path, cc); + struct cubic *c = quic_cc_priv(cc); + + TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc); + TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, ev); + switch (ev->type) { + case QUIC_CC_EVT_ACK: + if (path->cwnd < QUIC_CC_INFINITE_SSTHESH - ev->ack.acked) { + path->cwnd += ev->ack.acked; + path->cwnd = QUIC_MIN(path->max_cwnd, path->cwnd); + } + /* Exit to congestion avoidance if slow start threshold is reached. */ + if (path->cwnd >= c->ssthresh) + c->state = QUIC_CC_ST_CA; + path->mcwnd = QUIC_MAX(path->cwnd, path->mcwnd); + break; + + case QUIC_CC_EVT_LOSS: + quic_enter_recovery(cc); + break; + + case QUIC_CC_EVT_ECN_CE: + /* TODO */ + break; + } + + out: + TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, NULL, cc); + TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc); +} + +/* Congestion avoidance callback. */ +static void quic_cc_cubic_ca_cb(struct quic_cc *cc, struct quic_cc_event *ev) +{ + TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc); + TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, ev); + switch (ev->type) { + case QUIC_CC_EVT_ACK: + quic_cubic_update(cc, ev->ack.acked); + break; + case QUIC_CC_EVT_LOSS: + quic_enter_recovery(cc); + break; + case QUIC_CC_EVT_ECN_CE: + /* TODO */ + break; + } + + out: + TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, NULL, cc); + TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc); +} + +/* Recovery period callback */ +static void quic_cc_cubic_rp_cb(struct quic_cc *cc, struct quic_cc_event *ev) +{ + struct cubic *c = quic_cc_priv(cc); + + TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc, ev); + TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, ev, cc); + + switch (ev->type) { + case QUIC_CC_EVT_ACK: + /* RFC 9002 7.3.2. Recovery + * A recovery period ends and the sender enters congestion avoidance when a + * packet sent during the recovery period is acknowledged. + */ + if (tick_is_le(ev->ack.time_sent, c->recovery_start_time)) { + TRACE_PROTO("CC cubic (still in recov. period)", QUIC_EV_CONN_CC, cc->qc); + goto leave; + } + + c->state = QUIC_CC_ST_CA; + c->recovery_start_time = TICK_ETERNITY; + break; + case QUIC_CC_EVT_LOSS: + break; + case QUIC_CC_EVT_ECN_CE: + /* TODO */ + break; + } + + leave: + TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, NULL, cc); + TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc, NULL, cc); +} + +static void (*quic_cc_cubic_state_cbs[])(struct quic_cc *cc, + struct quic_cc_event *ev) = { + [QUIC_CC_ST_SS] = quic_cc_cubic_ss_cb, + [QUIC_CC_ST_CA] = quic_cc_cubic_ca_cb, + [QUIC_CC_ST_RP] = quic_cc_cubic_rp_cb, +}; + +static void quic_cc_cubic_event(struct quic_cc *cc, struct quic_cc_event *ev) +{ + struct cubic *c = quic_cc_priv(cc); + + return quic_cc_cubic_state_cbs[c->state](cc, ev); +} + +static void quic_cc_cubic_state_trace(struct buffer *buf, const struct quic_cc *cc) +{ + struct quic_cc_path *path; + struct cubic *c = quic_cc_priv(cc); + + path = container_of(cc, struct quic_cc_path, cc); + chunk_appendf(buf, " state=%s cwnd=%llu mcwnd=%llu ssthresh=%d rpst=%dms", + quic_cc_state_str(c->state), + (unsigned long long)path->cwnd, + (unsigned long long)path->mcwnd, + (int)c->ssthresh, + !tick_isset(c->recovery_start_time) ? -1 : + TICKS_TO_MS(tick_remain(c->recovery_start_time, now_ms))); +} + +struct quic_cc_algo quic_cc_algo_cubic = { + .type = QUIC_CC_ALGO_TP_CUBIC, + .init = quic_cc_cubic_init, + .event = quic_cc_cubic_event, + .slow_start = quic_cc_cubic_slow_start, + .state_trace = quic_cc_cubic_state_trace, +}; |