1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_cubic.c -- LSQUIC CUBIC implementation.
4 */
5
6#include <inttypes.h>
7#include <math.h>
8#include <stddef.h>
9#include <stdlib.h>
10#include <string.h>
11#include <sys/queue.h>
12#ifdef WIN32
13#include <vc_compat.h>
14#endif
15
16#include "lsquic_int_types.h"
17#include "lsquic_types.h"
18#include "lsquic_hash.h"
19#include "lsquic_util.h"
20#include "lsquic_cong_ctl.h"
21#include "lsquic_sfcw.h"
22#include "lsquic_conn_flow.h"
23#include "lsquic_varint.h"
24#include "lsquic_hq.h"
25#include "lsquic_stream.h"
26#include "lsquic_rtt.h"
27#include "lsquic_conn_public.h"
28#include "lsquic_packet_common.h"
29#include "lsquic_packet_out.h"
30#include "lsquic_cubic.h"
31
32#define LSQUIC_LOGGER_MODULE LSQLM_CUBIC
33#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(cubic->cu_conn)
34#include "lsquic_logger.h"
35
36#define FAST_CONVERGENCE        1
37#define BETA                    205     /* 205/1024 */
38#define C                       410     /* 410/1024 */
39#define TWO_MINUS_BETA_OVER_TWO 922     /* 922/1024 */
40#define ONE_MINUS_BETA          819     /* 819/1024 */
41#define ONE_OVER_C              2560    /* 2560/1024 */
42
43static void
44cubic_reset (struct lsquic_cubic *cubic)
45{
46    memset(cubic, 0, offsetof(struct lsquic_cubic, cu_conn));
47    cubic->cu_cwnd          = 32 * TCP_MSS;
48    cubic->cu_last_max_cwnd = 32 * TCP_MSS;
49    cubic->cu_tcp_cwnd      = 32 * TCP_MSS;
50}
51
52
53static void
54cubic_update (struct lsquic_cubic *cubic, lsquic_time_t now, unsigned n_bytes)
55{
56    double delta_t, t;
57    lsquic_time_t target;
58
59    if (0 == cubic->cu_epoch_start)
60    {
61        cubic->cu_epoch_start = now;
62        if (cubic->cu_cwnd < cubic->cu_last_max_cwnd)
63        {
64            cubic->cu_K = cbrt(cubic->cu_last_max_cwnd / TCP_MSS / 2);
65            cubic->cu_origin_point = cubic->cu_last_max_cwnd;
66        }
67        else
68        {
69            cubic->cu_K = 0;
70            cubic->cu_origin_point = cubic->cu_cwnd;
71        }
72        LSQ_DEBUG("cwnd: %lu; last_max_cwnd: %lu; K: %lf; origin_point: %lu",
73            cubic->cu_cwnd, cubic->cu_last_max_cwnd, cubic->cu_K, cubic->cu_origin_point);
74    }
75
76    delta_t = (double) (now + cubic->cu_min_delay - cubic->cu_epoch_start) / 1000000;
77    if (delta_t < cubic->cu_K)
78    {
79        t = cubic->cu_K - delta_t;
80        target = cubic->cu_origin_point - t * t * t * 0.4 * TCP_MSS;
81        LSQ_DEBUG("delta_t: %lf; t: %lf; target 1: %"PRIu64, delta_t, t, target);
82    }
83    else
84    {
85        t = delta_t - cubic->cu_K;
86        target = cubic->cu_origin_point + t * t * t * 0.4 * TCP_MSS;
87        LSQ_DEBUG("target 2: %"PRIu64, target);
88    }
89
90    if (cubic->cu_flags & CU_TCP_FRIENDLY)
91    {
92        cubic->cu_tcp_cwnd += n_bytes * TCP_MSS * ONE_MINUS_BETA / 1024
93                            / cubic->cu_tcp_cwnd;
94        LSQ_DEBUG("delta_t: %lf; last_max: %lu; cu_tcp_cwnd: %lu; target: "
95            "%"PRIu64"; over: %d; left: %d", delta_t, cubic->cu_last_max_cwnd,
96            cubic->cu_tcp_cwnd, target, cubic->cu_tcp_cwnd > target,
97            delta_t < cubic->cu_K);
98        if (cubic->cu_tcp_cwnd > target)
99            target = cubic->cu_tcp_cwnd;
100    }
101
102    if (target == 0)
103        target = TCP_MSS;
104
105    cubic->cu_cwnd = target;
106}
107
108
109void
110lsquic_cubic_set_flags (struct lsquic_cubic *cubic, enum cubic_flags flags)
111{
112    LSQ_DEBUG("%s(cubic, 0x%X)", __func__, flags);
113    cubic->cu_flags = flags;
114}
115
116
117static void
118lsquic_cubic_init (void *cong_ctl, const struct lsquic_conn_public *conn_pub,
119                                            enum quic_ft_bit UNUSED_retx_frames)
120{
121    struct lsquic_cubic *const cubic = cong_ctl;
122    cubic_reset(cubic);
123    cubic->cu_ssthresh = 10000 * TCP_MSS; /* Emulate "unbounded" slow start */
124    cubic->cu_conn  = conn_pub->lconn;
125    cubic->cu_rtt_stats = &conn_pub->rtt_stats;
126    cubic->cu_flags = DEFAULT_CUBIC_FLAGS;
127#ifndef NDEBUG
128    const char *s;
129    s = getenv("LSQUIC_CUBIC_SAMPLING_RATE");
130    if (s)
131        cubic->cu_sampling_rate = atoi(s);
132    else
133#endif
134        cubic->cu_sampling_rate = 100000;
135    LSQ_DEBUG("%s(cubic, $conn)", __func__);
136    LSQ_INFO("initialized");
137}
138
139
140static void
141lsquic_cubic_reinit (void *cong_ctl)
142{
143    struct lsquic_cubic *const cubic = cong_ctl;
144    cubic_reset(cubic);
145    cubic->cu_ssthresh = 10000 * TCP_MSS; /* Emulate "unbounded" slow start */
146    LSQ_DEBUG("re-initialized");
147}
148
149
150#define LOG_CWND(c) do {                                                    \
151    if (LSQ_LOG_ENABLED(LSQ_LOG_INFO)) {                                    \
152        lsquic_time_t now = lsquic_time_now();                              \
153        now -= now % (c)->cu_sampling_rate;                                 \
154        if (now > (c)->cu_last_logged) {                                    \
155            LSQ_INFO("CWND: %lu", (c)->cu_cwnd);                            \
156            (c)->cu_last_logged = now;                                      \
157        }                                                                   \
158    }                                                                       \
159} while (0)
160
161
162static void
163lsquic_cubic_was_quiet (void *cong_ctl, lsquic_time_t now, uint64_t in_flight)
164{
165    struct lsquic_cubic *const cubic = cong_ctl;
166    LSQ_DEBUG("%s(cubic, %"PRIu64")", __func__, now);
167    cubic->cu_epoch_start = 0;
168}
169
170
171static void
172lsquic_cubic_ack (void *cong_ctl, struct lsquic_packet_out *packet_out,
173                  unsigned n_bytes, lsquic_time_t now_time, int app_limited)
174{
175    struct lsquic_cubic *const cubic = cong_ctl;
176    lsquic_time_t rtt;
177
178    rtt = now_time - packet_out->po_sent;
179    LSQ_DEBUG("%s(cubic, %"PRIu64", %"PRIu64", %d, %u)", __func__, now_time, rtt,
180                                                        app_limited, n_bytes);
181    if (0 == cubic->cu_min_delay || rtt < cubic->cu_min_delay)
182    {
183        cubic->cu_min_delay = rtt;
184        LSQ_INFO("min_delay: %"PRIu64, rtt);
185    }
186
187    if (cubic->cu_cwnd <= cubic->cu_ssthresh)
188    {
189        cubic->cu_cwnd += TCP_MSS;
190        LSQ_DEBUG("ACK: slow threshold, cwnd: %lu", cubic->cu_cwnd);
191    }
192    else if (!app_limited)
193    {
194        cubic_update(cubic, now_time, n_bytes);
195        LSQ_DEBUG("ACK: cwnd: %lu", cubic->cu_cwnd);
196    }
197
198    LOG_CWND(cubic);
199}
200
201
202static void
203lsquic_cubic_loss (void *cong_ctl)
204{
205    struct lsquic_cubic *const cubic = cong_ctl;
206    LSQ_DEBUG("%s(cubic)", __func__);
207    cubic->cu_epoch_start = 0;
208    if (FAST_CONVERGENCE && cubic->cu_cwnd < cubic->cu_last_max_cwnd)
209        cubic->cu_last_max_cwnd = cubic->cu_cwnd * TWO_MINUS_BETA_OVER_TWO / 1024;
210    else
211        cubic->cu_last_max_cwnd = cubic->cu_cwnd;
212    cubic->cu_cwnd = cubic->cu_cwnd * ONE_MINUS_BETA / 1024;
213    cubic->cu_tcp_cwnd = cubic->cu_cwnd;
214    cubic->cu_ssthresh = cubic->cu_cwnd;
215    LSQ_INFO("loss detected, last_max_cwnd: %lu, cwnd: %lu",
216        cubic->cu_last_max_cwnd, cubic->cu_cwnd);
217    LOG_CWND(cubic);
218}
219
220
221static void
222lsquic_cubic_timeout (void *cong_ctl)
223{
224    struct lsquic_cubic *const cubic = cong_ctl;
225    unsigned long cwnd;
226
227    cwnd = cubic->cu_cwnd;
228    LSQ_DEBUG("%s(cubic)", __func__);
229    cubic_reset(cubic);
230    cubic->cu_ssthresh = cwnd / 2;
231    cubic->cu_tcp_cwnd = 2 * TCP_MSS;
232    cubic->cu_cwnd = 2 * TCP_MSS;
233    LSQ_INFO("timeout, cwnd: %lu", cubic->cu_cwnd);
234    LOG_CWND(cubic);
235}
236
237
238static void
239lsquic_cubic_cleanup (void *cong_ctl)
240{
241}
242
243
244static uint64_t
245lsquic_cubic_get_cwnd (void *cong_ctl)
246{
247    struct lsquic_cubic *const cubic = cong_ctl;
248    return cubic->cu_cwnd;
249}
250
251
252static int
253in_slow_start (void *cong_ctl)
254{
255    struct lsquic_cubic *const cubic = cong_ctl;
256    return cubic->cu_cwnd < cubic->cu_ssthresh;
257}
258
259
260static uint64_t
261lsquic_cubic_pacing_rate (void *cong_ctl, int in_recovery)
262{
263    struct lsquic_cubic *const cubic = cong_ctl;
264    uint64_t bandwidth, pacing_rate;
265    lsquic_time_t srtt;
266
267    srtt = lsquic_rtt_stats_get_srtt(cubic->cu_rtt_stats);
268    if (srtt == 0)
269        srtt = 50000;
270    bandwidth = cubic->cu_cwnd * 1000000 / srtt;
271    if (in_slow_start(cubic))
272        pacing_rate = bandwidth * 2;
273    else if (in_recovery)
274        pacing_rate = bandwidth;
275    else
276        pacing_rate = bandwidth + bandwidth / 4;
277
278    return pacing_rate;
279}
280
281
282
283const struct cong_ctl_if lsquic_cong_cubic_if =
284{
285    .cci_ack           = lsquic_cubic_ack,
286    .cci_cleanup       = lsquic_cubic_cleanup,
287    .cci_get_cwnd      = lsquic_cubic_get_cwnd,
288    .cci_init          = lsquic_cubic_init,
289    .cci_pacing_rate   = lsquic_cubic_pacing_rate,
290    .cci_loss          = lsquic_cubic_loss,
291    .cci_reinit        = lsquic_cubic_reinit,
292    .cci_timeout       = lsquic_cubic_timeout,
293    .cci_was_quiet     = lsquic_cubic_was_quiet,
294};
295