blob: d58d79a125aa7fe284083fa97a82085892ab4be7 [file] [log] [blame]
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +02001#include <haproxy/quic_cc.h>
Frédéric Lécaille8f991942023-03-24 15:14:45 +01002#include <haproxy/ticks.h>
3#include <haproxy/trace.h>
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +02004
Frederic Lecaille569a0252024-01-30 11:40:41 +01005/* IMPORTANT NOTE about the units defined by the RFC 9438
6 * (CUBIC for Fast and Long-Distance Networks):
7 *
8 * RFC 9438 4.1. Definitions:
9 * The unit of all window sizes in this document is segments of the SMSS, and
10 * the unit of all times is seconds. Implementations can use bytes to express
11 * window sizes, which would require factoring in the SMSS wherever necessary
12 * and replacing segments_acked (Figure 4) with the number of acknowledged
13 * bytes.
14 */
15
16/* So, this is the reason why here in this implementation each time a number
17 * of segments is used (typically a congestion window value), its value is
18 * multiplied by the MTU value.
19 */
20
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020021/* This source file is highly inspired from Linux kernel source file
22 * implementation for TCP Cubic. In fact, we have no choice if we do
23 * not want to use any floating point operations to be fast!
24 * (See net/ipv4/tcp_cubic.c)
25 */
26#define TRACE_SOURCE &trace_quic
27
Frederic Lecaille569a0252024-01-30 11:40:41 +010028/* Constants definitions:
29 * CUBIC_BETA_SCALED refers to the scaled value of RFC 9438 beta_cubic variable.
30 * CUBIC_C_SCALED refers to the scaled value of RFC 9438 C variable.
31 */
32
33/* The right shifting value to apply to scaled values to get its real value. */
34#define CUBIC_SCALE_FACTOR_SHIFT 10
35
36/* CUBIC multiplicative decrease factor as described in RFC 9438 section 4.6 */
37#define CUBIC_BETA_SCALED 717 /* beta_cubic = 0.7 (constant) */
38
39/* CUBIC C constant that determines the aggressiveness of CUBIC in competing
40 * with other congestion control algorithms in high-BDP networks.
41 */
42#define CUBIC_C_SCALED 410 /* RFC 9438 C = 0.4 segment/seconds^3
43 * or 410 mB/s^3 in this implementation.
44 */
45
46/* The scaled value of 1 */
47#define CUBIC_ONE_SCALED (1 << CUBIC_SCALE_FACTOR_SHIFT)
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020048
Frederic Lecaille569a0252024-01-30 11:40:41 +010049/* The left bit shifting to apply to convert milliseconds to seconds. */
50#define TIME_SCALE_FACTOR_SHIFT 10
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020051
Frederic Lecaille569a0252024-01-30 11:40:41 +010052/* The maximum time value which may be cubed and multiplied by CUBIC_C_SCALED */
53#define CUBIC_TIME_LIMIT 355535ULL /* ms */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020054
Frederic Lecaille569a0252024-01-30 11:40:41 +010055/* By connection CUBIC algorithm state. Note that the current congestion window
56 * value is not stored in this structure.
57 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020058struct cubic {
Frederic Lecaille569a0252024-01-30 11:40:41 +010059 /* QUIC_CC_ST_* state values. */
Frédéric Lécaille7d6270a2023-04-02 12:43:22 +020060 uint32_t state;
Frederic Lecaille569a0252024-01-30 11:40:41 +010061 /* Slow start threshold (in bytes) */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020062 uint32_t ssthresh;
Frederic Lecaille569a0252024-01-30 11:40:41 +010063 /* Remaining number of acknowledged bytes between two ACK for CUBIC congestion
64 * control window (in bytes).
65 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020066 uint32_t remaining_inc;
Frederic Lecaille569a0252024-01-30 11:40:41 +010067 /* Start time of at which the current avoidance stage started (in ms). */
68 uint32_t t_epoch;
69 /* The window to reach for each recovery period during a concave region (in bytes). */
70 uint32_t W_target;
71 /* The time period to reach W_target during a concave region (in ms). */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020072 uint32_t K;
Frederic Lecaille569a0252024-01-30 11:40:41 +010073 /* The last window maximum reached (in bytes). */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020074 uint32_t last_w_max;
Frederic Lecaille569a0252024-01-30 11:40:41 +010075 /* Estimated value of the Reno congestion window in the TCP-friendly region (in bytes). */
76 uint32_t W_est;
77 /* Remaining number of acknowledged bytes between two ACKs for estimated
78 * TCP-Reno congestion control window (in bytes).
79 */
80 uint32_t remaining_W_est_inc;
81 /* Start time of recovery period (used to avoid re-entering this state, if already
82 * in recovery period) (in ms).
83 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020084 uint32_t recovery_start_time;
85};
86
87static void quic_cc_cubic_reset(struct quic_cc *cc)
88{
89 struct cubic *c = quic_cc_priv(cc);
90
Frédéric Lécaillede2ba862023-04-02 10:49:35 +020091 TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécaille7d6270a2023-04-02 12:43:22 +020092 c->state = QUIC_CC_ST_SS;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020093 c->ssthresh = QUIC_CC_INFINITE_SSTHESH;
94 c->remaining_inc = 0;
Frederic Lecaille569a0252024-01-30 11:40:41 +010095 c->remaining_W_est_inc = 0;
96 c->t_epoch = 0;
97 c->W_target = 0;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +020098 c->K = 0;
99 c->last_w_max = 0;
Frederic Lecaille569a0252024-01-30 11:40:41 +0100100 c->W_est = 0;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200101 c->recovery_start_time = 0;
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200102 TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200103}
104
105static int quic_cc_cubic_init(struct quic_cc *cc)
106{
107 quic_cc_cubic_reset(cc);
108 return 1;
109}
110
111/* Cubic root.
112 * Highly inspired from Linux kernel sources.
113 * See net/ipv4/tcp_cubic.c
114 */
115static uint32_t cubic_root(uint64_t val)
116{
117 uint32_t x, b, shift;
118
119 static const uint8_t v[] = {
120 0, 54, 54, 54, 118, 118, 118, 118,
121 123, 129, 134, 138, 143, 147, 151, 156,
122 157, 161, 164, 168, 170, 173, 176, 179,
123 181, 185, 187, 190, 192, 194, 197, 199,
124 200, 202, 204, 206, 209, 211, 213, 215,
125 217, 219, 221, 222, 224, 225, 227, 229,
126 231, 232, 234, 236, 237, 239, 240, 242,
127 244, 245, 246, 248, 250, 251, 252, 254,
128 };
129
Frédéric Lécaille2c77a5e2022-08-03 12:49:30 +0200130 if (!val || (b = my_flsl(val)) < 7) {
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200131 /* val in [0..63] */
132 return ((uint32_t)v[(uint32_t)val] + 35) >> 6;
133 }
134
135 b = ((b * 84) >> 8) - 1;
136 shift = (val >> (b * 3));
137
138 x = ((uint32_t)(((uint32_t)v[shift] + 10) << b)) >> 6;
139
140 x = 2 * x + (uint32_t)(val / ((uint64_t)x * (uint64_t)(x - 1)));
141 x = ((x * 341) >> 10);
142
143 return x;
144}
145
Frederic Lecaille569a0252024-01-30 11:40:41 +0100146/*
147 * RFC 9438 3.1. Principle 1 for the CUBIC Increase Function
148 *
149 * For better network utilization and stability, CUBIC [HRX08] uses a cubic
150 * window increase function in terms of the elapsed time from the last
151 * congestion event. While most congestion control algorithms that provide
152 * alternatives to Reno increase the congestion window using convex functions,
153 * CUBIC uses both the concave and convex profiles of a cubic function for
154 * window growth.
155 *
156 * After a window reduction in response to a congestion event detected by
157 * duplicate acknowledgments (ACKs), Explicit Congestion Notification-Echo
158 * (ECN-Echo (ECE)) ACKs [RFC3168], RACK-TLP for TCP [RFC8985], or QUIC loss
159 * detection [RFC9002], CUBIC remembers the congestion window size at which it
160 * received the congestion event and performs a multiplicative decrease of the
161 * congestion window. When CUBIC enters into congestion avoidance, it starts to
162 * increase the congestion window using the concave profile of the cubic
163 * function. The cubic function is set to have its plateau at the remembered
164 * congestion window size, so that the concave window increase continues until
165 * then. After that, the cubic function turns into a convex profile and the
166 * convex window increase begins.
167 *
168 * W_cubic(time) (bytes)
169 * ^ convex region
170 * | <------------------------->
171 * | . +
172 * | . +
173 * | . +
174 * | . +
175 * | . + ^
176 * | . + | W_cubic_t
177 * | . + |
178 * | . + |
179 * W_target |-----------+--------------------------+------------------------+
180 * (W_max) | +. + . t
181 * | + . + .
182 * | + . + .
183 * | + . + .
184 * | + . + .
185 * | .+ .
186 * | + .
187 * | + .
188 * | + .
189 * | . .
190 * | . .
191 * | . .
192 * +-----------+--------------------------+-+------------------------> time (s)
193 * 0 t_epoch (t_epoch + K)
194 * <-------------------------->
195 * . concave region
196 * .
197 * congestion
198 * event
199 *
200 * RFC 9438 4.2. Window Increase Function:
201 *
202 * W_cubic(t) = C*(t-K)^3 + W_max (Figure 1)
203 * K = cubic_root((W_max - cwnd_epoch)/C) (Figure 2)
204 *
205 * +--------------------------------------------------------------------+
206 * | RFC 9438 definitions | Code variables |
207 * +--------------------------------------------------------------------+
208 * | C (segments/s^3) | CUBIC_C_SCALED (mB/s^3) |
209 * +--------------------------------------------------------------------+
210 * | W_max (segments) | c->last_w_max - path->cwnd (bytes) |
211 * +--------------------------------------------------------------------+
212 * | K (s) | c->K (ms) |
213 * +--------------------------------------------------------------------+
214 * | beta_cubic (constant) | CUBIC_BETA_SCALED (constant) |
215 * +--------------------------------------------------------------------+
216 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200217static inline void quic_cubic_update(struct quic_cc *cc, uint32_t acked)
218{
219 struct cubic *c = quic_cc_priv(cc);
220 struct quic_path *path = container_of(cc, struct quic_path, cc);
Frederic Lecaille569a0252024-01-30 11:40:41 +0100221 /* The elapsed time since the start of the congestion event. */
222 uint32_t elapsed_time;
223 /* Target value of the congestion window. */
224 uint32_t target;
225 /* The time at which the congestion window will be computed based
226 * on the cubic increase function.
227 */
228 uint64_t t;
229 /* The computed value of the congestion window at time t based on the cubic
230 * increase function.
231 */
232 uint64_t W_cubic_t;
233 uint32_t inc, inc_diff;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200234
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200235 TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc);
Frederic Lecaille569a0252024-01-30 11:40:41 +0100236 if (!c->t_epoch) {
237 c->t_epoch = now_ms;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200238 if (c->last_w_max <= path->cwnd) {
239 c->K = 0;
Frederic Lecaille569a0252024-01-30 11:40:41 +0100240 c->W_target = path->cwnd;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200241 }
242 else {
Frederic Lecaille569a0252024-01-30 11:40:41 +0100243 /* K value computing (in seconds):
244 * K = cubic_root((W_max - cwnd_epoch)/C) (Figure 2)
245 * Note that K is stored in 1024th of a second.
246 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200247 c->K = cubic_root((c->last_w_max - path->cwnd) *
Frederic Lecaille569a0252024-01-30 11:40:41 +0100248 (CUBIC_ONE_SCALED - CUBIC_BETA_SCALED) / CUBIC_C_SCALED / path->mtu) << TIME_SCALE_FACTOR_SHIFT;
249 c->W_target = c->last_w_max;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200250 }
251
Frederic Lecaille569a0252024-01-30 11:40:41 +0100252 c->W_est = path->cwnd;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200253 c->remaining_inc = 0;
Frederic Lecaille569a0252024-01-30 11:40:41 +0100254 c->remaining_W_est_inc = 0;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200255 }
256
Frederic Lecaille569a0252024-01-30 11:40:41 +0100257 elapsed_time = now_ms + path->loss.rtt_min - c->t_epoch;
258 if (elapsed_time < c->K) {
259 t = c->K - elapsed_time;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200260 }
261 else {
Frederic Lecaille569a0252024-01-30 11:40:41 +0100262 t = elapsed_time - c->K;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200263 }
264
Frederic Lecaille569a0252024-01-30 11:40:41 +0100265 if (t > CUBIC_TIME_LIMIT) {
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200266 /* TODO : should not happen if we handle the case
267 * of very late acks receipt. This must be handled as a congestion
268 * control event: a very late ack should trigger a congestion
269 * control algorithm reset.
270 */
271 quic_cc_cubic_reset(cc);
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200272 goto leave;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200273 }
274
Frederic Lecaille569a0252024-01-30 11:40:41 +0100275 /* Compute W_cubic_t at t time. */
276 W_cubic_t = path->mtu * ((CUBIC_C_SCALED * t * t * t) >> (CUBIC_SCALE_FACTOR_SHIFT + 3 * TIME_SCALE_FACTOR_SHIFT));
277 if (elapsed_time < c->K)
278 target = c->W_target - W_cubic_t;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200279 else
Frederic Lecaille569a0252024-01-30 11:40:41 +0100280 target = c->W_target + W_cubic_t;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200281
282 if (target > path->cwnd) {
Frederic Lecaille569a0252024-01-30 11:40:41 +0100283 /* Concave region */
284
285 /* RFC 9438 4.4. Concave Region
286 *
287 * When receiving a new ACK in congestion avoidance, if CUBIC is not in
288 * the Reno-friendly region and cwnd is less than Wmax, then CUBIC is
289 * in the concave region. In this region, cwnd MUST be incremented by
290 * (target - cwnd) / cwnd.
291 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200292 inc_diff = c->remaining_inc + path->mtu * (target - path->cwnd);
293 c->remaining_inc = inc_diff % path->cwnd;
294 inc = inc_diff / path->cwnd;
295 }
296 else {
Frederic Lecaille569a0252024-01-30 11:40:41 +0100297 /* Convex region: very small increment */
298
299 /* RFC 9438 4.5. Convex Region
300 *
301 * When receiving a new ACK in congestion avoidance, if CUBIC is not in
302 * the Reno-friendly region and cwnd is larger than or equal to Wmax,
303 * then CUBIC is in the convex region.The convex region indicates that
304 * the network conditions might have changed since the last congestion
305 * event, possibly implying more available bandwidth after some flow
306 * departures. Since the Internet is highly asynchronous, some amount
307 * of perturbation is always possible without causing a major change in
308 * available bandwidth.Unless the cwnd is overridden by the AIMD window
309 * increase, CUBIC will behave cautiously when operating in this region.
310 * The convex profile aims to increase the window very slowly at the
311 * beginning when cwnd is around Wmax and then gradually increases its
312 * rate of increase. This region is also called the "maximum probing
313 * phase", since CUBIC is searching for a new Wmax. In this region,
314 * cwnd MUST be incremented by (target - cwnd) / cwnd) for each received
315 * new ACK, where target is calculated as described in Section 4.2.
316 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200317 inc_diff = c->remaining_inc + path->mtu;
318 c->remaining_inc = inc_diff % (100 * path->cwnd);
319 inc = inc_diff / (100 * path->cwnd);
320 }
321
Frederic Lecaille569a0252024-01-30 11:40:41 +0100322 inc_diff = c->remaining_W_est_inc + path->mtu * acked;
323 c->W_est += inc_diff / path->cwnd;
324 c->remaining_W_est_inc = inc_diff % path->cwnd;
325
326 /* TCP friendliness :
327 * RFC 9438 4.3. Reno-Friendly Region
328 *
329 * Reno performs well in certain types of networks -- for example, under
330 * short RTTs and small bandwidths (or small BDPs). In these networks,
331 * CUBIC remains in the Reno-friendly region to achieve at least the same
332 * throughput as Reno.
333 *
334 * When receiving a new ACK in congestion avoidance (where cwnd could be
335 * greater than or less than Wmax), CUBIC checks whether Wcubic(t) is less
336 * than West. If so, CUBIC is in the Reno-friendly region and cwnd SHOULD
337 * be set to West at each reception of a new ACK.
338 *
339 * West is set equal to cwnd_epoch at the start of the congestion avoidance
340 * stage. After that, on every new ACK, West is updated using Figure 4.
341 * Note that this equation uses segments_acked and cwnd is measured in
342 * segments. An implementation that measures cwnd in bytes should adjust the
343 * equation accordingly using the number of acknowledged bytes and the SMSS.
344 * Also note that this equation works for connections with enabled or
345 * disabled delayed ACKs [RFC5681], as segments_acked will be different based
346 * on the segments actually acknowledged by a new ACK.
347 *
348 * Figure 4 : West = West + alpha_cubic * (segments_acked / cwnd)
349 *
350 * Once West has grown to reach the cwnd at the time of most recently
351 * setting ssthresh -- that is, West >= cwndprior -- the sender SHOULD set
352 * alpha_cubic to 1 to ensure that it can achieve the same congestion window
353 * increment rate as Reno, which uses AIMD(1, 0.5).
354 */
355 if (c->W_est > path->cwnd) {
356 uint32_t W_est_inc = path->mtu * (c->W_est - path->cwnd) / path->cwnd;
357 if (W_est_inc > inc)
358 inc = W_est_inc;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200359 }
360
361 path->cwnd += inc;
Frédéric Lécaillefad0e6c2023-04-06 10:19:17 +0200362 path->mcwnd = QUIC_MAX(path->cwnd, path->mcwnd);
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200363 leave:
364 TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200365}
366
367static void quic_cc_cubic_slow_start(struct quic_cc *cc)
368{
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200369 TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200370 quic_cc_cubic_reset(cc);
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200371 TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200372}
373
374static void quic_enter_recovery(struct quic_cc *cc)
375{
376 struct quic_path *path = container_of(cc, struct quic_path, cc);
377 struct cubic *c = quic_cc_priv(cc);
378 /* Current cwnd as number of packets */
379
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200380 TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc);
Frederic Lecaille569a0252024-01-30 11:40:41 +0100381 c->t_epoch = 0;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200382 c->recovery_start_time = now_ms;
Frederic Lecaille569a0252024-01-30 11:40:41 +0100383
384 /* RFC 9438 4.7. Fast Convergence
385 *
386 * To improve convergence speed, CUBIC uses a heuristic. When a new flow
387 * joins the network, existing flows need to give up some of their bandwidth
388 * to allow the new flow some room for growth if the existing flows have
389 * been using all the network bandwidth. To speed up this bandwidth release
390 * by existing flows, the following fast convergence mechanism SHOULD be
391 * implemented.With fast convergence, when a congestion event occurs, Wmax
392 * is updated as follows, before the window reduction described in Section
393 * 4.6.
394 *
395 * if cwnd < Wmax and fast convergence enabled, further reduce Wax:
396 * Wmax = cwnd * (1 + beta_cubic)
397 * otherwise, remember cwn before reduction:
398 * Wmax = cwnd
399 */
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200400 if (path->cwnd < c->last_w_max) {
Frederic Lecaille569a0252024-01-30 11:40:41 +0100401 /* (1 + beta_cubic) * path->cwnd / 2 */
402 c->last_w_max = (path->cwnd * (CUBIC_ONE_SCALED + CUBIC_BETA_SCALED) / 2) >> CUBIC_SCALE_FACTOR_SHIFT;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200403 }
404 else {
405 c->last_w_max = path->cwnd;
406 }
Frederic Lecaille569a0252024-01-30 11:40:41 +0100407
408 c->ssthresh = (CUBIC_BETA_SCALED * path->cwnd) >> CUBIC_SCALE_FACTOR_SHIFT;
Frédéric Lécaille595251f2023-04-13 10:46:42 +0200409 path->cwnd = QUIC_MAX(c->ssthresh, (uint32_t)path->min_cwnd);
Frédéric Lécaille7d6270a2023-04-02 12:43:22 +0200410 c->state = QUIC_CC_ST_RP;
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200411 TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc, NULL, cc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200412}
413
414/* Congestion slow-start callback. */
415static void quic_cc_cubic_ss_cb(struct quic_cc *cc, struct quic_cc_event *ev)
416{
417 struct quic_path *path = container_of(cc, struct quic_path, cc);
418 struct cubic *c = quic_cc_priv(cc);
419
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100420 TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc);
421 TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, ev);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200422 switch (ev->type) {
423 case QUIC_CC_EVT_ACK:
Frédéric Lécailledb548472023-04-02 10:07:48 +0200424 if (path->cwnd < QUIC_CC_INFINITE_SSTHESH - ev->ack.acked)
425 path->cwnd += ev->ack.acked;
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200426 /* Exit to congestion avoidance if slow start threshold is reached. */
427 if (path->cwnd >= c->ssthresh)
Frédéric Lécaille7d6270a2023-04-02 12:43:22 +0200428 c->state = QUIC_CC_ST_CA;
Frédéric Lécaillefad0e6c2023-04-06 10:19:17 +0200429 path->mcwnd = QUIC_MAX(path->cwnd, path->mcwnd);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200430 break;
431
432 case QUIC_CC_EVT_LOSS:
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200433 quic_enter_recovery(cc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200434 break;
435
436 case QUIC_CC_EVT_ECN_CE:
437 /* TODO */
438 break;
439 }
440
441 out:
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100442 TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, NULL, cc);
443 TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200444}
445
446/* Congestion avoidance callback. */
447static void quic_cc_cubic_ca_cb(struct quic_cc *cc, struct quic_cc_event *ev)
448{
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100449 TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc);
450 TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, ev);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200451 switch (ev->type) {
452 case QUIC_CC_EVT_ACK:
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200453 quic_cubic_update(cc, ev->ack.acked);
454 break;
455 case QUIC_CC_EVT_LOSS:
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200456 quic_enter_recovery(cc);
457 break;
458 case QUIC_CC_EVT_ECN_CE:
459 /* TODO */
460 break;
461 }
462
463 out:
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100464 TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, NULL, cc);
Frédéric Lécaille23b8eef2023-03-31 20:18:44 +0200465 TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200466}
467
Frédéric Lécailled7243312023-03-21 11:54:02 +0100468/* Recovery period callback */
469static void quic_cc_cubic_rp_cb(struct quic_cc *cc, struct quic_cc_event *ev)
470{
471 struct cubic *c = quic_cc_priv(cc);
472
473 TRACE_ENTER(QUIC_EV_CONN_CC, cc->qc, ev);
Frédéric Lécaillede2ba862023-04-02 10:49:35 +0200474 TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, ev, cc);
Frédéric Lécailled7243312023-03-21 11:54:02 +0100475
Frédéric Lécailled7243312023-03-21 11:54:02 +0100476 switch (ev->type) {
477 case QUIC_CC_EVT_ACK:
Frederic Lecaille569a0252024-01-30 11:40:41 +0100478 /* RFC 9002 7.3.2. Recovery
Frédéric Lécailled7243312023-03-21 11:54:02 +0100479 * A recovery period ends and the sender enters congestion avoidance when a
480 * packet sent during the recovery period is acknowledged.
481 */
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100482 if (tick_is_le(ev->ack.time_sent, c->recovery_start_time)) {
483 TRACE_PROTO("CC cubic (still in recov. period)", QUIC_EV_CONN_CC, cc->qc);
Frédéric Lécailled7243312023-03-21 11:54:02 +0100484 goto leave;
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100485 }
Frédéric Lécailled7243312023-03-21 11:54:02 +0100486
Frédéric Lécaille7d6270a2023-04-02 12:43:22 +0200487 c->state = QUIC_CC_ST_CA;
Frédéric Lécailled7243312023-03-21 11:54:02 +0100488 c->recovery_start_time = TICK_ETERNITY;
489 break;
490 case QUIC_CC_EVT_LOSS:
491 break;
492 case QUIC_CC_EVT_ECN_CE:
493 /* TODO */
494 break;
495 }
496
497 leave:
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100498 TRACE_PROTO("CC cubic", QUIC_EV_CONN_CC, cc->qc, NULL, cc);
Frédéric Lécailled7243312023-03-21 11:54:02 +0100499 TRACE_LEAVE(QUIC_EV_CONN_CC, cc->qc, NULL, cc);
500}
501
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200502static void (*quic_cc_cubic_state_cbs[])(struct quic_cc *cc,
503 struct quic_cc_event *ev) = {
504 [QUIC_CC_ST_SS] = quic_cc_cubic_ss_cb,
505 [QUIC_CC_ST_CA] = quic_cc_cubic_ca_cb,
Frédéric Lécailled7243312023-03-21 11:54:02 +0100506 [QUIC_CC_ST_RP] = quic_cc_cubic_rp_cb,
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200507};
508
509static void quic_cc_cubic_event(struct quic_cc *cc, struct quic_cc_event *ev)
510{
Frédéric Lécaille7d6270a2023-04-02 12:43:22 +0200511 struct cubic *c = quic_cc_priv(cc);
512
513 return quic_cc_cubic_state_cbs[c->state](cc, ev);
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200514}
515
516static void quic_cc_cubic_state_trace(struct buffer *buf, const struct quic_cc *cc)
517{
Frédéric Lécaille01314b82023-03-24 14:09:55 +0100518 struct quic_path *path;
519 struct cubic *c = quic_cc_priv(cc);
520
521 path = container_of(cc, struct quic_path, cc);
Frédéric Lécaillefad0e6c2023-04-06 10:19:17 +0200522 chunk_appendf(buf, " state=%s cwnd=%llu mcwnd=%llu ssthresh=%d rpst=%dms",
Frédéric Lécaille7d6270a2023-04-02 12:43:22 +0200523 quic_cc_state_str(c->state),
Frédéric Lécaille01314b82023-03-24 14:09:55 +0100524 (unsigned long long)path->cwnd,
Frédéric Lécaillefad0e6c2023-04-06 10:19:17 +0200525 (unsigned long long)path->mcwnd,
Frédéric Lécaille01314b82023-03-24 14:09:55 +0100526 (int)c->ssthresh,
527 !tick_isset(c->recovery_start_time) ? -1 :
528 TICKS_TO_MS(tick_remain(c->recovery_start_time, now_ms)));
Frédéric Lécaille1c9c2f62022-06-01 15:06:58 +0200529}
530
531struct quic_cc_algo quic_cc_algo_cubic = {
532 .type = QUIC_CC_ALGO_TP_CUBIC,
533 .init = quic_cc_cubic_init,
534 .event = quic_cc_cubic_event,
535 .slow_start = quic_cc_cubic_slow_start,
536 .state_trace = quic_cc_cubic_state_trace,
537};