lsquic_cubic.c revision 9c444524 
1/* Copyright (c) 2017 - 2019 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#ifdef WIN32
12#include <vc_compat.h>
13#endif
14
15#include "lsquic_int_types.h"
16#include "lsquic_types.h"
17#include "lsquic_cubic.h"
18#include "lsquic_util.h"
19
20#define LSQUIC_LOGGER_MODULE LSQLM_CUBIC
21#define LSQUIC_LOG_CONN_ID cubic->cu_cid
22#include "lsquic_logger.h"
23
24#define FAST_CONVERGENCE        1
25#define BETA                    205     /* 205/1024 */
26#define C                       410     /* 410/1024 */
27#define TWO_MINUS_BETA_OVER_TWO 922     /* 922/1024 */
28#define ONE_MINUS_BETA          819     /* 819/1024 */
29#define ONE_OVER_C              2560    /* 2560/1024 */
30
31static void
32cubic_reset (struct lsquic_cubic *cubic)
33{
34    memset(cubic, 0, offsetof(struct lsquic_cubic, cu_cid));
35    cubic->cu_cwnd          = 32 * TCP_MSS;
36    cubic->cu_last_max_cwnd = 32 * TCP_MSS;
37    cubic->cu_tcp_cwnd      = 32 * TCP_MSS;
38}
39
40
41static void
42cubic_update (struct lsquic_cubic *cubic, lsquic_time_t now, unsigned n_bytes)
43{
44    double delta_t, t;
45    lsquic_time_t target;
46
47    if (0 == cubic->cu_epoch_start)
48    {
49        cubic->cu_epoch_start = now;
50        if (cubic->cu_cwnd < cubic->cu_last_max_cwnd)
51        {
52            cubic->cu_K = cbrt(cubic->cu_last_max_cwnd / TCP_MSS / 2);
53            cubic->cu_origin_point = cubic->cu_last_max_cwnd;
54        }
55        else
56        {
57            cubic->cu_K = 0;
58            cubic->cu_origin_point = cubic->cu_cwnd;
59        }
60        LSQ_DEBUG("cwnd: %lu; last_max_cwnd: %lu; K: %lf; origin_point: %lu",
61            cubic->cu_cwnd, cubic->cu_last_max_cwnd, cubic->cu_K, cubic->cu_origin_point);
62    }
63
64    delta_t = (double) (now + cubic->cu_min_delay - cubic->cu_epoch_start) / 1000000;
65    if (delta_t < cubic->cu_K)
66    {
67        t = cubic->cu_K - delta_t;
68        target = cubic->cu_origin_point - t * t * t * 0.4 * TCP_MSS;
69        LSQ_DEBUG("delta_t: %lf; t: %lf; target 1: %"PRIu64, delta_t, t, target);
70    }
71    else
72    {
73        t = delta_t - cubic->cu_K;
74        target = cubic->cu_origin_point + t * t * t * 0.4 * TCP_MSS;
75        LSQ_DEBUG("target 2: %"PRIu64, target);
76    }
77
78    if (cubic->cu_flags & CU_TCP_FRIENDLY)
79    {
80        cubic->cu_tcp_cwnd += n_bytes * TCP_MSS * ONE_MINUS_BETA / 1024
81                            / cubic->cu_tcp_cwnd;
82        LSQ_DEBUG("delta_t: %lf; last_max: %lu; cu_tcp_cwnd: %lu; target: "
83            "%"PRIu64"; over: %d; left: %d", delta_t, cubic->cu_last_max_cwnd,
84            cubic->cu_tcp_cwnd, target, cubic->cu_tcp_cwnd > target,
85            delta_t < cubic->cu_K);
86        if (cubic->cu_tcp_cwnd > target)
87            target = cubic->cu_tcp_cwnd;
88    }
89
90    if (target == 0)
91        target = TCP_MSS;
92
93    cubic->cu_cwnd = target;
94}
95
96
97void
98lsquic_cubic_init_ext (struct lsquic_cubic *cubic, lsquic_cid_t cid,
99                                                        enum cubic_flags flags)
100{
101    cubic_reset(cubic);
102    cubic->cu_ssthresh = 10000 * TCP_MSS; /* Emulate "unbounded" slow start */
103    cubic->cu_cid   = cid;
104    cubic->cu_flags = flags;
105#ifndef NDEBUG
106    const char *s;
107    s = getenv("LSQUIC_CUBIC_SAMPLING_RATE");
108    if (s)
109        cubic->cu_sampling_rate = atoi(s);
110    else
111#endif
112        cubic->cu_sampling_rate = 100000;
113    LSQ_DEBUG("%s(cubic, %"PRIu64", 0x%X)", __func__, cid, flags);
114    LSQ_INFO("initialized");
115}
116
117
118#define LOG_CWND(c) do {                                                    \
119    if (LSQ_LOG_ENABLED(LSQ_LOG_INFO)) {                                    \
120        lsquic_time_t now = lsquic_time_now();                              \
121        now -= now % (c)->cu_sampling_rate;                                 \
122        if (now > (c)->cu_last_logged) {                                    \
123            LSQ_INFO("CWND: %lu", (c)->cu_cwnd);                            \
124            (c)->cu_last_logged = now;                                      \
125        }                                                                   \
126    }                                                                       \
127} while (0)
128
129
130void
131lsquic_cubic_was_quiet (struct lsquic_cubic *cubic, lsquic_time_t now)
132{
133    LSQ_DEBUG("%s(cubic, %"PRIu64")", __func__, now);
134    cubic->cu_epoch_start = 0;
135}
136
137
138void
139lsquic_cubic_ack (struct lsquic_cubic *cubic, lsquic_time_t now_time,
140                  lsquic_time_t rtt, int app_limited, unsigned n_bytes)
141{
142    LSQ_DEBUG("%s(cubic, %"PRIu64", %"PRIu64", %d, %u)", __func__, now_time, rtt,
143                                                        app_limited, n_bytes);
144    if (0 == cubic->cu_min_delay || rtt < cubic->cu_min_delay)
145    {
146        cubic->cu_min_delay = rtt;
147        LSQ_INFO("min_delay: %"PRIu64, rtt);
148    }
149
150    if (cubic->cu_cwnd <= cubic->cu_ssthresh)
151    {
152        cubic->cu_cwnd += TCP_MSS;
153        LSQ_DEBUG("ACK: slow threshold, cwnd: %lu", cubic->cu_cwnd);
154    }
155    else if (!app_limited)
156    {
157        cubic_update(cubic, now_time, n_bytes);
158        LSQ_DEBUG("ACK: cwnd: %lu", cubic->cu_cwnd);
159    }
160
161    LOG_CWND(cubic);
162}
163
164
165void
166lsquic_cubic_loss (struct lsquic_cubic *cubic)
167{
168    LSQ_DEBUG("%s(cubic)", __func__);
169    cubic->cu_epoch_start = 0;
170    if (FAST_CONVERGENCE && cubic->cu_cwnd < cubic->cu_last_max_cwnd)
171        cubic->cu_last_max_cwnd = cubic->cu_cwnd * TWO_MINUS_BETA_OVER_TWO / 1024;
172    else
173        cubic->cu_last_max_cwnd = cubic->cu_cwnd;
174    cubic->cu_cwnd = cubic->cu_cwnd * ONE_MINUS_BETA / 1024;
175    cubic->cu_tcp_cwnd = cubic->cu_cwnd;
176    cubic->cu_ssthresh = cubic->cu_cwnd;
177    LSQ_INFO("loss detected, last_max_cwnd: %lu, cwnd: %lu",
178        cubic->cu_last_max_cwnd, cubic->cu_cwnd);
179    LOG_CWND(cubic);
180}
181
182
183void
184lsquic_cubic_timeout (struct lsquic_cubic *cubic)
185{
186    unsigned long cwnd;
187
188    cwnd = cubic->cu_cwnd;
189    LSQ_DEBUG("%s(cubic)", __func__);
190    cubic_reset(cubic);
191    cubic->cu_ssthresh = cwnd / 2;
192    cubic->cu_tcp_cwnd = 2 * TCP_MSS;
193    cubic->cu_cwnd = 2 * TCP_MSS;
194    LSQ_INFO("timeout, cwnd: %lu", cubic->cu_cwnd);
195    LOG_CWND(cubic);
196}
197