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