tcp_cubic.c revision 36ebcfff
1/*
2 * Copyright (c) 2018-2019 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include <vnet/tcp/tcp.h>
17#include <math.h>
18
19#define beta_cubic 	0.7
20#define cubic_c		0.4
21#define west_const 	(3 * (1 - beta_cubic) / (1 + beta_cubic))
22
23typedef struct cubic_cfg_
24{
25  u8 fast_convergence;
26} cubic_cfg_t;
27
28static cubic_cfg_t cubic_cfg = {
29  .fast_convergence = 1,
30};
31
32typedef struct cubic_data_
33{
34  /** time period (in seconds) needed to increase the current window
35   *  size to W_max if there are no further congestion events */
36  f64 K;
37
38  /** time (in sec) since the start of current congestion avoidance */
39  f64 t_start;
40
41  /** Inflection point of the cubic function (in snd_mss segments) */
42  u32 w_max;
43
44} __clib_packed cubic_data_t;
45
46STATIC_ASSERT (sizeof (cubic_data_t) <= TCP_CC_DATA_SZ, "cubic data len");
47
48static inline f64
49cubic_time (u32 thread_index)
50{
51  return transport_time_now (thread_index);
52}
53
54/**
55 * RFC 8312 Eq. 1
56 *
57 * CUBIC window increase function. Time and K need to be provided in seconds.
58 */
59static inline u64
60W_cubic (cubic_data_t * cd, f64 t)
61{
62  f64 diff = t - cd->K;
63
64  /* W_cubic(t) = C*(t-K)^3 + W_max */
65  return cubic_c * diff * diff * diff + cd->w_max;
66}
67
68/**
69 * RFC 8312 Eq. 2
70 */
71static inline f64
72K_cubic (cubic_data_t * cd, u32 wnd)
73{
74  /* K = cubic_root(W_max*(1-beta_cubic)/C)
75   * Because the current window may be less than W_max * beta_cubic because
76   * of fast convergence, we pass it as parameter */
77  return pow ((f64) (cd->w_max - wnd) / cubic_c, 1 / 3.0);
78}
79
80/**
81 * RFC 8312 Eq. 4
82 *
83 * Estimates the window size of AIMD(alpha_aimd, beta_aimd) for
84 * alpha_aimd=3*(1-beta_cubic)/(1+beta_cubic) and beta_aimd=beta_cubic.
85 * Time (t) and rtt should be provided in seconds
86 */
87static inline u32
88W_est (cubic_data_t * cd, f64 t, f64 rtt)
89{
90  /* W_est(t) = W_max*beta_cubic+[3*(1-beta_cubic)/(1+beta_cubic)]*(t/RTT) */
91  return cd->w_max * beta_cubic + west_const * (t / rtt);
92}
93
94static void
95cubic_congestion (tcp_connection_t * tc)
96{
97  cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
98  u32 w_max;
99
100  w_max = tc->cwnd / tc->snd_mss;
101  if (cubic_cfg.fast_convergence && w_max < cd->w_max)
102    w_max = w_max * ((1.0 + beta_cubic) / 2.0);
103
104  cd->w_max = w_max;
105  tc->ssthresh = clib_max (tc->cwnd * beta_cubic, 2 * tc->snd_mss);
106  tc->cwnd = tc->ssthresh;
107}
108
109static void
110cubic_loss (tcp_connection_t * tc)
111{
112  cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
113
114  tc->cwnd = tcp_loss_wnd (tc);
115  cd->t_start = cubic_time (tc->c_thread_index);
116  cd->K = 0;
117  cd->w_max = tc->cwnd / tc->snd_mss;
118}
119
120static void
121cubic_recovered (tcp_connection_t * tc)
122{
123  cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
124  cd->t_start = cubic_time (tc->c_thread_index);
125  tc->cwnd = tc->ssthresh;
126  cd->K = K_cubic (cd, tc->cwnd / tc->snd_mss);
127}
128
129static void
130cubic_cwnd_accumulate (tcp_connection_t * tc, u32 thresh, u32 bytes_acked)
131{
132  /* We just updated the threshold and don't know how large the previous
133   * one was. Still, optimistically increase cwnd by one segment and
134   * clear the accumulated bytes. */
135  if (tc->cwnd_acc_bytes > thresh)
136    {
137      tc->cwnd += tc->snd_mss;
138      tc->cwnd_acc_bytes = 0;
139    }
140
141  tcp_cwnd_accumulate (tc, thresh, tc->bytes_acked);
142}
143
144static void
145cubic_rcv_ack (tcp_connection_t * tc, tcp_rate_sample_t * rs)
146{
147  cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
148  u64 w_cubic, w_aimd;
149  f64 t, rtt_sec;
150  u32 thresh;
151
152  /* Constrained by tx fifo, can't grow further */
153  if (tc->cwnd >= tc->tx_fifo_size)
154    return;
155
156  if (tcp_in_slowstart (tc))
157    {
158      tc->cwnd += tc->bytes_acked;
159      return;
160    }
161
162  t = cubic_time (tc->c_thread_index) - cd->t_start;
163  rtt_sec = clib_min (tc->mrtt_us, (f64) tc->srtt * TCP_TICK);
164
165  w_cubic = W_cubic (cd, t + rtt_sec) * tc->snd_mss;
166  w_aimd = (u64) W_est (cd, t, rtt_sec) * tc->snd_mss;
167  if (w_cubic < w_aimd)
168    {
169      cubic_cwnd_accumulate (tc, tc->cwnd, tc->bytes_acked);
170    }
171  else
172    {
173      if (w_cubic > tc->cwnd)
174	{
175	  /* For NewReno and slow start, we increment cwnd based on the
176	   * number of bytes acked, not the number of acks received. In
177	   * particular, for NewReno we increment the cwnd by 1 snd_mss
178	   * only after we accumulate 1 cwnd of acked bytes (RFC 3465).
179	   *
180	   * For Cubic, as per RFC 8312 we should increment cwnd by
181	   * (w_cubic - cwnd)/cwnd for each ack. Instead of using that,
182	   * we compute the number of packets that need to be acked
183	   * before adding snd_mss to cwnd and compute the threshold
184	   */
185	  thresh = (tc->snd_mss * tc->cwnd) / (w_cubic - tc->cwnd);
186
187	  /* Make sure we don't increase cwnd more often than every segment */
188	  thresh = clib_max (thresh, tc->snd_mss);
189	}
190      else
191	{
192	  /* Practically we can't increment so just inflate threshold */
193	  thresh = 50 * tc->cwnd;
194	}
195      cubic_cwnd_accumulate (tc, thresh, tc->bytes_acked);
196    }
197}
198
199static void
200cubic_conn_init (tcp_connection_t * tc)
201{
202  cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
203  tc->ssthresh = tc->snd_wnd;
204  tc->cwnd = tcp_initial_cwnd (tc);
205  cd->w_max = 0;
206  cd->K = 0;
207  cd->t_start = cubic_time (tc->c_thread_index);
208}
209
210static uword
211cubic_unformat_config (unformat_input_t * input)
212{
213  if (!input)
214    return 0;
215
216  unformat_skip_white_space (input);
217
218  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
219    {
220      if (unformat (input, "no-fast-convergence"))
221	cubic_cfg.fast_convergence = 0;
222      else
223	return 0;
224    }
225  return 1;
226}
227
228const static tcp_cc_algorithm_t tcp_cubic = {
229  .name = "cubic",
230  .unformat_cfg = cubic_unformat_config,
231  .congestion = cubic_congestion,
232  .loss = cubic_loss,
233  .recovered = cubic_recovered,
234  .rcv_ack = cubic_rcv_ack,
235  .rcv_cong_ack = newreno_rcv_cong_ack,
236  .init = cubic_conn_init,
237};
238
239clib_error_t *
240cubic_init (vlib_main_t * vm)
241{
242  clib_error_t *error = 0;
243
244  tcp_cc_algo_register (TCP_CC_CUBIC, &tcp_cubic);
245
246  return error;
247}
248
249VLIB_INIT_FUNCTION (cubic_init);
250
251/*
252 * fd.io coding-style-patch-verification: ON
253 *
254 * Local Variables:
255 * eval: (c-set-style "gnu")
256 * End:
257 */
258