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