src/vnet/tcp/tcp_cubic.c

   1 /*
   2  * Copyright (c) 2018 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
  23 typedef struct cubic_cfg_
  24 {
  25   u8 fast_convergence;
  26 } cubic_cfg_t;
  27
  28 static cubic_cfg_t cubic_cfg = {
  29   .fast_convergence = 1,
  30 };
  31
  32 typedef 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
  46 STATIC_ASSERT (sizeof (cubic_data_t) <= TCP_CC_DATA_SZ, "cubic data len");
  47
  48 static inline f64
  49 cubic_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  */
  59 static inline u64
  60 W_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  */
  71 static inline f64
  72 K_cubic (cubic_data_t * cd)
  73 {
  74   /* K = cubic_root(W_max*(1-beta_cubic)/C) */
  75   return pow (cd->w_max * (1 - beta_cubic) / cubic_c, 1 / 3.0);
  76 }
  77
  78 /**
  79  * RFC 8312 Eq. 4
  80  *
  81  * Estimates the window size of AIMD(alpha_aimd, beta_aimd) for
  82  * alpha_aimd=3*(1-beta_cubic)/(1+beta_cubic) and beta_aimd=beta_cubic.
  83  * Time (t) and rtt should be provided in seconds
  84  */
  85 static inline u32
  86 W_est (cubic_data_t * cd, f64 t, f64 rtt)
  87 {
  88   /* W_est(t) = W_max*beta_cubic+[3*(1-beta_cubic)/(1+beta_cubic)]*(t/RTT) */
  89   return cd->w_max * beta_cubic + west_const * (t / rtt);
  90 }
  91
  92 static void
  93 cubic_congestion (tcp_connection_t * tc)
  94 {
  95   cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
  96   u32 w_max;
  97
  98   w_max = tc->cwnd / tc->snd_mss;
  99   if (cubic_cfg.fast_convergence && w_max < cd->w_max)
 100     w_max = w_max * ((1.0 + beta_cubic) / 2.0);
 101
 102   cd->w_max = w_max;
 103   tc->ssthresh = clib_max (tc->cwnd * beta_cubic, 2 * tc->snd_mss);
 104 }
 105
 106 static void
 107 cubic_recovered (tcp_connection_t * tc)
 108 {
 109   cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
 110   cd->t_start = cubic_time (tc->c_thread_index);
 111   cd->K = K_cubic (cd);
 112   tc->cwnd = tc->ssthresh;
 113 }
 114
 115 static void
 116 cubic_rcv_ack (tcp_connection_t * tc)
 117 {
 118   cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
 119   u64 w_cubic, w_aimd;
 120   f64 t, rtt_sec;
 121   u32 thresh;
 122
 123   /* Constrained by tx fifo, can't grow further */
 124   if (tc->cwnd >= tc->tx_fifo_size)
 125     return;
 126
 127   if (tcp_in_slowstart (tc))
 128     {
 129       tc->cwnd += clib_min (tc->snd_mss, tc->bytes_acked);
 130       return;
 131     }
 132
 133   t = cubic_time (tc->c_thread_index) - cd->t_start;
 134   rtt_sec = clib_min (tc->mrtt_us, (f64) tc->srtt * TCP_TICK);
 135
 136   w_cubic = W_cubic (cd, t + rtt_sec) * tc->snd_mss;
 137   w_aimd = (u64) W_est (cd, t, rtt_sec) * tc->snd_mss;
 138   if (w_cubic < w_aimd)
 139     {
 140       tcp_cwnd_accumulate (tc, tc->cwnd, tc->bytes_acked);
 141     }
 142   else
 143     {
 144       if (w_cubic > tc->cwnd)
 145         {
 146           /* For NewReno and slow start, we increment cwnd based on the
 147            * number of bytes acked, not the number of acks received. In
 148            * particular, for NewReno we increment the cwnd by 1 snd_mss
 149            * only after we accumulate 1 cwnd of acked bytes (RFC 3465).
 150            *
 151            * For Cubic, as per RFC 8312 we should increment cwnd by
 152            * (w_cubic - cwnd)/cwnd for each ack. Instead of using that,
 153            * we compute the number of packets that need to be acked
 154            * before adding snd_mss to cwnd and compute the threshold
 155            */
 156           thresh = (tc->snd_mss * tc->cwnd) / (w_cubic - tc->cwnd);
 157
 158           /* Make sure we don't increase cwnd more often than every
 159            * 2 segments */
 160           thresh = clib_max (thresh, 2 * tc->snd_mss);
 161         }
 162       else
 163         {
 164           /* Practically we can't increment so just inflate threshold */
 165           thresh = 50 * tc->cwnd;
 166         }
 167       tcp_cwnd_accumulate (tc, thresh, tc->bytes_acked);
 168     }
 169 }
 170
 171 static void
 172 cubic_conn_init (tcp_connection_t * tc)
 173 {
 174   cubic_data_t *cd = (cubic_data_t *) tcp_cc_data (tc);
 175   tc->ssthresh = tc->snd_wnd;
 176   tc->cwnd = tcp_initial_cwnd (tc);
 177   cd->w_max = 0;
 178   cd->K = 0;
 179   cd->t_start = cubic_time (tc->c_thread_index);
 180 }
 181
 182 static uword
 183 cubic_unformat_config (unformat_input_t * input)
 184 {
 185   if (!input)
 186     return 0;
 187
 188   unformat_skip_white_space (input);
 189
 190   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 191     {
 192       if (unformat (input, "no-fast-convergence"))
 193         cubic_cfg.fast_convergence = 0;
 194       else
 195         return 0;
 196     }
 197   return 1;
 198 }
 199
 200 const static tcp_cc_algorithm_t tcp_cubic = {
 201   .name = "cubic",
 202   .unformat_cfg = cubic_unformat_config,
 203   .congestion = cubic_congestion,
 204   .recovered = cubic_recovered,
 205   .rcv_ack = cubic_rcv_ack,
 206   .rcv_cong_ack = newreno_rcv_cong_ack,
 207   .init = cubic_conn_init,
 208 };
 209
 210 clib_error_t *
 211 cubic_init (vlib_main_t * vm)
 212 {
 213   clib_error_t *error = 0;
 214
 215   tcp_cc_algo_register (TCP_CC_CUBIC, &tcp_cubic);
 216
 217   return error;
 218 }
 219
 220 VLIB_INIT_FUNCTION (cubic_init);
 221
 222 /*
 223  * fd.io coding-style-patch-verification: ON
 224  *
 225  * Local Variables:
 226  * eval: (c-set-style "gnu")
 227  * End:
 228  */