net/ipv4/tcp_compound.c

   1 /*
   2  * TCP Vegas congestion control
   3  *
   4  * This is based on the congestion detection/avoidance scheme described in
   5  *    Lawrence S. Brakmo and Larry L. Peterson.
   6  *    "TCP Vegas: End to end congestion avoidance on a global internet."
   7  *    IEEE Journal on Selected Areas in Communication, 13(8):1465--1480,
   8  *    October 1995. Available from:
   9  *      ftp://ftp.cs.arizona.edu/xkernel/Papers/jsac.ps
  10  *
  11  * See http://www.cs.arizona.edu/xkernel/ for their implementation.
  12  * The main aspects that distinguish this implementation from the
  13  * Arizona Vegas implementation are:
  14  *   o We do not change the loss detection or recovery mechanisms of
  15  *     Linux in any way. Linux already recovers from losses quite well,
  16  *     using fine-grained timers, NewReno, and FACK.
  17  *   o To avoid the performance penalty imposed by increasing cwnd
  18  *     only every-other RTT during slow start, we increase during
  19  *     every RTT during slow start, just like Reno.
  20  *   o Largely to allow continuous cwnd growth during slow start,
  21  *     we use the rate at which ACKs come back as the "actual"
  22  *     rate, rather than the rate at which data is sent.
  23  *   o To speed convergence to the right rate, we set the cwnd
  24  *     to achieve the right ("actual") rate when we exit slow start.
  25  *   o To filter out the noise caused by delayed ACKs, we use the
  26  *     minimum RTT sample observed during the last RTT to calculate
  27  *     the actual rate.
  28  *   o When the sender re-starts from idle, it waits until it has
  29  *     received ACKs for an entire flight of new data before making
  30  *     a cwnd adjustment decision. The original Vegas implementation
  31  *     assumed senders never went idle.
  32  *
  33  *
  34  *   TCP Compound based on TCP Vegas
  35  *
  36  *   further details can be found here:
  37  *      ftp://ftp.research.microsoft.com/pub/tr/TR-2005-86.pdf
  38  */
  39
  40 #include <linux/config.h>
  41 #include <linux/mm.h>
  42 #include <linux/module.h>
  43 #include <linux/skbuff.h>
  44 #include <linux/inet_diag.h>
  45
  46 #include <net/tcp.h>
  47
  48 /* Default values of the Vegas variables, in fixed-point representation
  49  * with V_PARAM_SHIFT bits to the right of the binary point.
  50  */
  51 #define V_PARAM_SHIFT 1
  52
  53 #define TCP_COMPOUND_ALPHA          3U
  54 #define TCP_COMPOUND_BETA           1U
  55 #define TCP_COMPOUND_KAPPA_POW      3
  56 #define TCP_COMPOUND_KAPPA_NSQRT    2
  57 #define TCP_COMPOUND_GAMMA         30
  58 #define TCP_COMPOUND_ZETA           1
  59
  60 /* TCP compound variables */
  61 struct compound {
  62         u32 beg_snd_nxt;        /* right edge during last RTT */
  63         u32 beg_snd_una;        /* left edge  during last RTT */
  64         u32 beg_snd_cwnd;       /* saves the size of the cwnd */
  65         u8 doing_vegas_now;     /* if true, do vegas for this RTT */
  66         u16 cntRTT;             /* # of RTTs measured within last RTT */
  67         u32 minRTT;             /* min of RTTs measured within last RTT (in usec) */
  68         u32 baseRTT;            /* the min of all Vegas RTT measurements seen (in usec) */
  69
  70         u32 cwnd;
  71         u32 dwnd;
  72 };
  73
  74 /* There are several situations when we must "re-start" Vegas:
  75  *
  76  *  o when a connection is established
  77  *  o after an RTO
  78  *  o after fast recovery
  79  *  o when we send a packet and there is no outstanding
  80  *    unacknowledged data (restarting an idle connection)
  81  *
  82  * In these circumstances we cannot do a Vegas calculation at the
  83  * end of the first RTT, because any calculation we do is using
  84  * stale info -- both the saved cwnd and congestion feedback are
  85  * stale.
  86  *
  87  * Instead we must wait until the completion of an RTT during
  88  * which we actually receive ACKs.
  89  */
  90 static inline void vegas_enable(struct sock *sk)
  91 {
  92         const struct tcp_sock *tp = tcp_sk(sk);
  93         struct compound *vegas = inet_csk_ca(sk);
  94
  95         /* Begin taking Vegas samples next time we send something. */
  96         vegas->doing_vegas_now = 1;
  97
  98         /* Set the beginning of the next send window. */
  99         vegas->beg_snd_nxt = tp->snd_nxt;
 100
 101         vegas->cntRTT = 0;
 102         vegas->minRTT = 0x7fffffff;
 103 }
 104
 105 /* Stop taking Vegas samples for now. */
 106 static inline void vegas_disable(struct sock *sk)
 107 {
 108         struct compound *vegas = inet_csk_ca(sk);
 109
 110         vegas->doing_vegas_now = 0;
 111 }
 112
 113 static void tcp_compound_init(struct sock *sk)
 114 {
 115         struct compound *vegas = inet_csk_ca(sk);
 116         const struct tcp_sock *tp = tcp_sk(sk);
 117
 118         vegas->baseRTT = 0x7fffffff;
 119         vegas_enable(sk);
 120
 121         vegas->dwnd = 0;
 122         vegas->cwnd = tp->snd_cwnd;
 123 }
 124
 125 /* Do RTT sampling needed for Vegas.
 126  * Basically we:
 127  *   o min-filter RTT samples from within an RTT to get the current
 128  *     propagation delay + queuing delay (we are min-filtering to try to
 129  *     avoid the effects of delayed ACKs)
 130  *   o min-filter RTT samples from a much longer window (forever for now)
 131  *     to find the propagation delay (baseRTT)
 132  */
 133 static void tcp_compound_rtt_calc(struct sock *sk, u32 usrtt)
 134 {
 135         struct compound *vegas = inet_csk_ca(sk);
 136         u32 vrtt = usrtt + 1;   /* Never allow zero rtt or baseRTT */
 137
 138         /* Filter to find propagation delay: */
 139         if (vrtt < vegas->baseRTT)
 140                 vegas->baseRTT = vrtt;
 141
 142         /* Find the min RTT during the last RTT to find
 143          * the current prop. delay + queuing delay:
 144          */
 145
 146         vegas->minRTT = min(vegas->minRTT, vrtt);
 147         vegas->cntRTT++;
 148 }
 149
 150 static void tcp_compound_state(struct sock *sk, u8 ca_state)
 151 {
 152
 153         if (ca_state == TCP_CA_Open)
 154                 vegas_enable(sk);
 155         else
 156                 vegas_disable(sk);
 157 }
 158
 159 /*
 160  * If the connection is idle and we are restarting,
 161  * then we don't want to do any Vegas calculations
 162  * until we get fresh RTT samples.  So when we
 163  * restart, we reset our Vegas state to a clean
 164  * slate. After we get acks for this flight of
 165  * packets, _then_ we can make Vegas calculations
 166  * again.
 167  */
 168 static void tcp_compound_cwnd_event(struct sock *sk, enum tcp_ca_event event)
 169 {
 170         if (event == CA_EVENT_CWND_RESTART || event == CA_EVENT_TX_START)
 171                 tcp_compound_init(sk);
 172 }
 173
 174 static void tcp_compound_cong_avoid(struct sock *sk, u32 ack,
 175                                     u32 seq_rtt, u32 in_flight, int flag)
 176 {
 177         struct tcp_sock *tp = tcp_sk(sk);
 178         struct compound *vegas = inet_csk_ca(sk);
 179         u8 inc = 0;
 180
 181         if (vegas->cwnd + vegas->dwnd > tp->snd_cwnd) {
 182                 if (vegas->cwnd > tp->snd_cwnd || vegas->dwnd > tp->snd_cwnd) {
 183                         vegas->cwnd = tp->snd_cwnd;
 184                         vegas->dwnd = 0;
 185                 } else
 186                         vegas->cwnd = tp->snd_cwnd - vegas->dwnd;
 187
 188         }
 189
 190         if (!tcp_is_cwnd_limited(sk, in_flight))
 191                 return;
 192
 193         if (vegas->cwnd <= tp->snd_ssthresh)
 194                 inc = 1;
 195         else if (tp->snd_cwnd_cnt < tp->snd_cwnd)
 196                 tp->snd_cwnd_cnt++;
 197
 198         if (tp->snd_cwnd_cnt >= tp->snd_cwnd) {
 199                 inc = 1;
 200                 tp->snd_cwnd_cnt = 0;
 201         }
 202
 203         if (inc && tp->snd_cwnd < tp->snd_cwnd_clamp)
 204                 vegas->cwnd++;
 205
 206         /* The key players are v_beg_snd_una and v_beg_snd_nxt.
 207          *
 208          * These are so named because they represent the approximate values
 209          * of snd_una and snd_nxt at the beginning of the current RTT. More
 210          * precisely, they represent the amount of data sent during the RTT.
 211          * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt,
 212          * we will calculate that (v_beg_snd_nxt - v_beg_snd_una) outstanding
 213          * bytes of data have been ACKed during the course of the RTT, giving
 214          * an "actual" rate of:
 215          *
 216          *     (v_beg_snd_nxt - v_beg_snd_una) / (rtt duration)
 217          *
 218          * Unfortunately, v_beg_snd_una is not exactly equal to snd_una,
 219          * because delayed ACKs can cover more than one segment, so they
 220          * don't line up nicely with the boundaries of RTTs.
 221          *
 222          * Another unfortunate fact of life is that delayed ACKs delay the
 223          * advance of the left edge of our send window, so that the number
 224          * of bytes we send in an RTT is often less than our cwnd will allow.
 225          * So we keep track of our cwnd separately, in v_beg_snd_cwnd.
 226          */
 227
 228         if (after(ack, vegas->beg_snd_nxt)) {
 229                 /* Do the Vegas once-per-RTT cwnd adjustment. */
 230                 u32 old_wnd, old_snd_cwnd;
 231
 232                 /* Here old_wnd is essentially the window of data that was
 233                  * sent during the previous RTT, and has all
 234                  * been acknowledged in the course of the RTT that ended
 235                  * with the ACK we just received. Likewise, old_snd_cwnd
 236                  * is the cwnd during the previous RTT.
 237                  */
 238                 if (!tp->mss_cache)
 239                         return;
 240
 241                 old_wnd = (vegas->beg_snd_nxt - vegas->beg_snd_una) /
 242                     tp->mss_cache;
 243                 old_snd_cwnd = vegas->beg_snd_cwnd;
 244
 245                 /* Save the extent of the current window so we can use this
 246                  * at the end of the next RTT.
 247                  */
 248                 vegas->beg_snd_una = vegas->beg_snd_nxt;
 249                 vegas->beg_snd_nxt = tp->snd_nxt;
 250                 vegas->beg_snd_cwnd = tp->snd_cwnd;
 251
 252                 /* We do the Vegas calculations only if we got enough RTT
 253                  * samples that we can be reasonably sure that we got
 254                  * at least one RTT sample that wasn't from a delayed ACK.
 255                  * If we only had 2 samples total,
 256                  * then that means we're getting only 1 ACK per RTT, which
 257                  * means they're almost certainly delayed ACKs.
 258                  * If  we have 3 samples, we should be OK.
 259                  */
 260
 261                 if (vegas->cntRTT > 2) {
 262                         u32 rtt, target_cwnd, diff;
 263                         u32 brtt, dwnd;
 264
 265                         /* We have enough RTT samples, so, using the Vegas
 266                          * algorithm, we determine if we should increase or
 267                          * decrease cwnd, and by how much.
 268                          */
 269
 270                         /* Pluck out the RTT we are using for the Vegas
 271                          * calculations. This is the min RTT seen during the
 272                          * last RTT. Taking the min filters out the effects
 273                          * of delayed ACKs, at the cost of noticing congestion
 274                          * a bit later.
 275                          */
 276                         rtt = vegas->minRTT;
 277
 278                         /* Calculate the cwnd we should have, if we weren't
 279                          * going too fast.
 280                          *
 281                          * This is:
 282                          *     (actual rate in segments) * baseRTT
 283                          * We keep it as a fixed point number with
 284                          * V_PARAM_SHIFT bits to the right of the binary point.
 285                          */
 286                         if (!rtt)
 287                                 return;
 288
 289                         brtt = vegas->baseRTT;
 290                         target_cwnd = ((old_wnd * brtt)
 291                                        << V_PARAM_SHIFT) / rtt;
 292
 293                         /* Calculate the difference between the window we had,
 294                          * and the window we would like to have. This quantity
 295                          * is the "Diff" from the Arizona Vegas papers.
 296                          *
 297                          * Again, this is a fixed point number with
 298                          * V_PARAM_SHIFT bits to the right of the binary
 299                          * point.
 300                          */
 301
 302                         diff = (old_wnd << V_PARAM_SHIFT) - target_cwnd;
 303
 304                         dwnd = vegas->dwnd;
 305
 306                         if (diff < (TCP_COMPOUND_GAMMA << V_PARAM_SHIFT)) {
 307                                 u32 i, j, x, x2;
 308                                 u64 v;
 309
 310                                 v = 1;
 311
 312                                 for (i = 0; i < TCP_COMPOUND_KAPPA_POW; i++)
 313                                         v *= old_wnd;
 314
 315                                 for (i = 0; i < TCP_COMPOUND_KAPPA_NSQRT; i++) {
 316                                         x = 1;
 317                                         for (j = 0; j < 200; j++) {
 318                                                 x2 = (x + v / x) / 2;
 319
 320                                                 if (x2 == x || !x2)
 321                                                         break;
 322
 323                                                 x = x2;
 324                                         }
 325                                         v = x;
 326                                 }
 327
 328                                 x = (u32) v >> TCP_COMPOUND_ALPHA;
 329
 330                                 if (x > 1)
 331                                         dwnd = x - 1;
 332                                 else
 333                                         dwnd = 0;
 334
 335                                 dwnd += vegas->dwnd;
 336
 337                         } else if ((dwnd << V_PARAM_SHIFT) <
 338                                    (diff * TCP_COMPOUND_BETA))
 339                                 dwnd = 0;
 340                         else
 341                                 dwnd =
 342                                     ((dwnd << V_PARAM_SHIFT) -
 343                                      (diff *
 344                                       TCP_COMPOUND_BETA)) >> V_PARAM_SHIFT;
 345
 346                         vegas->dwnd = dwnd;
 347
 348                 }
 349
 350                 /* Wipe the slate clean for the next RTT. */
 351                 vegas->cntRTT = 0;
 352                 vegas->minRTT = 0x7fffffff;
 353         }
 354
 355         tp->snd_cwnd = vegas->cwnd + vegas->dwnd;
 356 }
 357
 358 /* Extract info for Tcp socket info provided via netlink. */
 359 static void tcp_compound_get_info(struct sock *sk, u32 ext, struct sk_buff *skb)
 360 {
 361         const struct compound *ca = inet_csk_ca(sk);
 362         if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
 363                 struct tcpvegas_info *info;
 364
 365                 info = RTA_DATA(__RTA_PUT(skb, INET_DIAG_VEGASINFO,
 366                                           sizeof(*info)));
 367
 368                 info->tcpv_enabled = ca->doing_vegas_now;
 369                 info->tcpv_rttcnt = ca->cntRTT;
 370                 info->tcpv_rtt = ca->baseRTT;
 371                 info->tcpv_minrtt = ca->minRTT;
 372         rtattr_failure:;
 373         }
 374 }
 375
 376 static struct tcp_congestion_ops tcp_compound = {
 377         .init           = tcp_compound_init,
 378         .ssthresh       = tcp_reno_ssthresh,
 379         .cong_avoid     = tcp_compound_cong_avoid,
 380         .min_cwnd       = tcp_reno_min_cwnd,
 381         .rtt_sample     = tcp_compound_rtt_calc,
 382         .set_state      = tcp_compound_state,
 383         .cwnd_event     = tcp_compound_cwnd_event,
 384         .get_info       = tcp_compound_get_info,
 385
 386         .owner          = THIS_MODULE,
 387         .name           = "compound",
 388 };
 389
 390 static int __init tcp_compound_register(void)
 391 {
 392         BUG_ON(sizeof(struct compound) > ICSK_CA_PRIV_SIZE);
 393         tcp_register_congestion_control(&tcp_compound);
 394         return 0;
 395 }
 396
 397 static void __exit tcp_compound_unregister(void)
 398 {
 399         tcp_unregister_congestion_control(&tcp_compound);
 400 }
 401
 402 module_init(tcp_compound_register);
 403 module_exit(tcp_compound_unregister);
 404
 405 MODULE_AUTHOR("Angelo P. Castellani, Stephen Hemminger");
 406 MODULE_LICENSE("GPL");
 407 MODULE_DESCRIPTION("TCP Compound");