net/ipv4/tcp_illinois.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * TCP Illinois congestion control.
0004  * Home page:
0005  *  http://www.ews.uiuc.edu/~shaoliu/tcpillinois/index.html
0006  *
0007  * The algorithm is described in:
0008  * "TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm
0009  *  for High-Speed Networks"
0010  * http://tamerbasar.csl.illinois.edu/LiuBasarSrikantPerfEvalArtJun2008.pdf
0011  *
0012  * Implemented from description in paper and ns-2 simulation.
0013  * Copyright (C) 2007 Stephen Hemminger <shemminger@linux-foundation.org>
0014  */
0015
0016 #include <linux/module.h>
0017 #include <linux/skbuff.h>
0018 #include <linux/inet_diag.h>
0019 #include <asm/div64.h>
0020 #include <net/tcp.h>
0021
0022 #define ALPHA_SHIFT 7
0023 #define ALPHA_SCALE (1u<<ALPHA_SHIFT)
0024 #define ALPHA_MIN   ((3*ALPHA_SCALE)/10)    /* ~0.3 */
0025 #define ALPHA_MAX   (10*ALPHA_SCALE)    /* 10.0 */
0026 #define ALPHA_BASE  ALPHA_SCALE     /* 1.0 */
0027 #define RTT_MAX     (U32_MAX / ALPHA_MAX)   /* 3.3 secs */
0028
0029 #define BETA_SHIFT  6
0030 #define BETA_SCALE  (1u<<BETA_SHIFT)
0031 #define BETA_MIN    (BETA_SCALE/8)      /* 0.125 */
0032 #define BETA_MAX    (BETA_SCALE/2)      /* 0.5 */
0033 #define BETA_BASE   BETA_MAX
0034
0035 static int win_thresh __read_mostly = 15;
0036 module_param(win_thresh, int, 0);
0037 MODULE_PARM_DESC(win_thresh, "Window threshold for starting adaptive sizing");
0038
0039 static int theta __read_mostly = 5;
0040 module_param(theta, int, 0);
0041 MODULE_PARM_DESC(theta, "# of fast RTT's before full growth");
0042
0043 /* TCP Illinois Parameters */
0044 struct illinois {
0045     u64 sum_rtt;    /* sum of rtt's measured within last rtt */
0046     u16 cnt_rtt;    /* # of rtts measured within last rtt */
0047     u32 base_rtt;   /* min of all rtt in usec */
0048     u32 max_rtt;    /* max of all rtt in usec */
0049     u32 end_seq;    /* right edge of current RTT */
0050     u32 alpha;      /* Additive increase */
0051     u32 beta;       /* Muliplicative decrease */
0052     u16 acked;      /* # packets acked by current ACK */
0053     u8  rtt_above;  /* average rtt has gone above threshold */
0054     u8  rtt_low;    /* # of rtts measurements below threshold */
0055 };
0056
0057 static void rtt_reset(struct sock *sk)
0058 {
0059     struct tcp_sock *tp = tcp_sk(sk);
0060     struct illinois *ca = inet_csk_ca(sk);
0061
0062     ca->end_seq = tp->snd_nxt;
0063     ca->cnt_rtt = 0;
0064     ca->sum_rtt = 0;
0065
0066     /* TODO: age max_rtt? */
0067 }
0068
0069 static void tcp_illinois_init(struct sock *sk)
0070 {
0071     struct illinois *ca = inet_csk_ca(sk);
0072
0073     ca->alpha = ALPHA_MAX;
0074     ca->beta = BETA_BASE;
0075     ca->base_rtt = 0x7fffffff;
0076     ca->max_rtt = 0;
0077
0078     ca->acked = 0;
0079     ca->rtt_low = 0;
0080     ca->rtt_above = 0;
0081
0082     rtt_reset(sk);
0083 }
0084
0085 /* Measure RTT for each ack. */
0086 static void tcp_illinois_acked(struct sock *sk, const struct ack_sample *sample)
0087 {
0088     struct illinois *ca = inet_csk_ca(sk);
0089     s32 rtt_us = sample->rtt_us;
0090
0091     ca->acked = sample->pkts_acked;
0092
0093     /* dup ack, no rtt sample */
0094     if (rtt_us < 0)
0095         return;
0096
0097     /* ignore bogus values, this prevents wraparound in alpha math */
0098     if (rtt_us > RTT_MAX)
0099         rtt_us = RTT_MAX;
0100
0101     /* keep track of minimum RTT seen so far */
0102     if (ca->base_rtt > rtt_us)
0103         ca->base_rtt = rtt_us;
0104
0105     /* and max */
0106     if (ca->max_rtt < rtt_us)
0107         ca->max_rtt = rtt_us;
0108
0109     ++ca->cnt_rtt;
0110     ca->sum_rtt += rtt_us;
0111 }
0112
0113 /* Maximum queuing delay */
0114 static inline u32 max_delay(const struct illinois *ca)
0115 {
0116     return ca->max_rtt - ca->base_rtt;
0117 }
0118
0119 /* Average queuing delay */
0120 static inline u32 avg_delay(const struct illinois *ca)
0121 {
0122     u64 t = ca->sum_rtt;
0123
0124     do_div(t, ca->cnt_rtt);
0125     return t - ca->base_rtt;
0126 }
0127
0128 /*
0129  * Compute value of alpha used for additive increase.
0130  * If small window then use 1.0, equivalent to Reno.
0131  *
0132  * For larger windows, adjust based on average delay.
0133  * A. If average delay is at minimum (we are uncongested),
0134  *    then use large alpha (10.0) to increase faster.
0135  * B. If average delay is at maximum (getting congested)
0136  *    then use small alpha (0.3)
0137  *
0138  * The result is a convex window growth curve.
0139  */
0140 static u32 alpha(struct illinois *ca, u32 da, u32 dm)
0141 {
0142     u32 d1 = dm / 100;  /* Low threshold */
0143
0144     if (da <= d1) {
0145         /* If never got out of low delay zone, then use max */
0146         if (!ca->rtt_above)
0147             return ALPHA_MAX;
0148
0149         /* Wait for 5 good RTT's before allowing alpha to go alpha max.
0150          * This prevents one good RTT from causing sudden window increase.
0151          */
0152         if (++ca->rtt_low < theta)
0153             return ca->alpha;
0154
0155         ca->rtt_low = 0;
0156         ca->rtt_above = 0;
0157         return ALPHA_MAX;
0158     }
0159
0160     ca->rtt_above = 1;
0161
0162     /*
0163      * Based on:
0164      *
0165      *      (dm - d1) amin amax
0166      * k1 = -------------------
0167      *         amax - amin
0168      *
0169      *       (dm - d1) amin
0170      * k2 = ----------------  - d1
0171      *        amax - amin
0172      *
0173      *             k1
0174      * alpha = ----------
0175      *          k2 + da
0176      */
0177
0178     dm -= d1;
0179     da -= d1;
0180     return (dm * ALPHA_MAX) /
0181         (dm + (da  * (ALPHA_MAX - ALPHA_MIN)) / ALPHA_MIN);
0182 }
0183
0184 /*
0185  * Beta used for multiplicative decrease.
0186  * For small window sizes returns same value as Reno (0.5)
0187  *
0188  * If delay is small (10% of max) then beta = 1/8
0189  * If delay is up to 80% of max then beta = 1/2
0190  * In between is a linear function
0191  */
0192 static u32 beta(u32 da, u32 dm)
0193 {
0194     u32 d2, d3;
0195
0196     d2 = dm / 10;
0197     if (da <= d2)
0198         return BETA_MIN;
0199
0200     d3 = (8 * dm) / 10;
0201     if (da >= d3 || d3 <= d2)
0202         return BETA_MAX;
0203
0204     /*
0205      * Based on:
0206      *
0207      *       bmin d3 - bmax d2
0208      * k3 = -------------------
0209      *         d3 - d2
0210      *
0211      *       bmax - bmin
0212      * k4 = -------------
0213      *         d3 - d2
0214      *
0215      * b = k3 + k4 da
0216      */
0217     return (BETA_MIN * d3 - BETA_MAX * d2 + (BETA_MAX - BETA_MIN) * da)
0218         / (d3 - d2);
0219 }
0220
0221 /* Update alpha and beta values once per RTT */
0222 static void update_params(struct sock *sk)
0223 {
0224     struct tcp_sock *tp = tcp_sk(sk);
0225     struct illinois *ca = inet_csk_ca(sk);
0226
0227     if (tcp_snd_cwnd(tp) < win_thresh) {
0228         ca->alpha = ALPHA_BASE;
0229         ca->beta = BETA_BASE;
0230     } else if (ca->cnt_rtt > 0) {
0231         u32 dm = max_delay(ca);
0232         u32 da = avg_delay(ca);
0233
0234         ca->alpha = alpha(ca, da, dm);
0235         ca->beta = beta(da, dm);
0236     }
0237
0238     rtt_reset(sk);
0239 }
0240
0241 /*
0242  * In case of loss, reset to default values
0243  */
0244 static void tcp_illinois_state(struct sock *sk, u8 new_state)
0245 {
0246     struct illinois *ca = inet_csk_ca(sk);
0247
0248     if (new_state == TCP_CA_Loss) {
0249         ca->alpha = ALPHA_BASE;
0250         ca->beta = BETA_BASE;
0251         ca->rtt_low = 0;
0252         ca->rtt_above = 0;
0253         rtt_reset(sk);
0254     }
0255 }
0256
0257 /*
0258  * Increase window in response to successful acknowledgment.
0259  */
0260 static void tcp_illinois_cong_avoid(struct sock *sk, u32 ack, u32 acked)
0261 {
0262     struct tcp_sock *tp = tcp_sk(sk);
0263     struct illinois *ca = inet_csk_ca(sk);
0264
0265     if (after(ack, ca->end_seq))
0266         update_params(sk);
0267
0268     /* RFC2861 only increase cwnd if fully utilized */
0269     if (!tcp_is_cwnd_limited(sk))
0270         return;
0271
0272     /* In slow start */
0273     if (tcp_in_slow_start(tp))
0274         tcp_slow_start(tp, acked);
0275
0276     else {
0277         u32 delta;
0278
0279         /* snd_cwnd_cnt is # of packets since last cwnd increment */
0280         tp->snd_cwnd_cnt += ca->acked;
0281         ca->acked = 1;
0282
0283         /* This is close approximation of:
0284          * tp->snd_cwnd += alpha/tp->snd_cwnd
0285         */
0286         delta = (tp->snd_cwnd_cnt * ca->alpha) >> ALPHA_SHIFT;
0287         if (delta >= tcp_snd_cwnd(tp)) {
0288             tcp_snd_cwnd_set(tp, min(tcp_snd_cwnd(tp) + delta / tcp_snd_cwnd(tp),
0289                          (u32)tp->snd_cwnd_clamp));
0290             tp->snd_cwnd_cnt = 0;
0291         }
0292     }
0293 }
0294
0295 static u32 tcp_illinois_ssthresh(struct sock *sk)
0296 {
0297     struct tcp_sock *tp = tcp_sk(sk);
0298     struct illinois *ca = inet_csk_ca(sk);
0299     u32 decr;
0300
0301     /* Multiplicative decrease */
0302     decr = (tcp_snd_cwnd(tp) * ca->beta) >> BETA_SHIFT;
0303     return max(tcp_snd_cwnd(tp) - decr, 2U);
0304 }
0305
0306 /* Extract info for Tcp socket info provided via netlink. */
0307 static size_t tcp_illinois_info(struct sock *sk, u32 ext, int *attr,
0308                 union tcp_cc_info *info)
0309 {
0310     const struct illinois *ca = inet_csk_ca(sk);
0311
0312     if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
0313         info->vegas.tcpv_enabled = 1;
0314         info->vegas.tcpv_rttcnt = ca->cnt_rtt;
0315         info->vegas.tcpv_minrtt = ca->base_rtt;
0316         info->vegas.tcpv_rtt = 0;
0317
0318         if (info->vegas.tcpv_rttcnt > 0) {
0319             u64 t = ca->sum_rtt;
0320
0321             do_div(t, info->vegas.tcpv_rttcnt);
0322             info->vegas.tcpv_rtt = t;
0323         }
0324         *attr = INET_DIAG_VEGASINFO;
0325         return sizeof(struct tcpvegas_info);
0326     }
0327     return 0;
0328 }
0329
0330 static struct tcp_congestion_ops tcp_illinois __read_mostly = {
0331     .init       = tcp_illinois_init,
0332     .ssthresh   = tcp_illinois_ssthresh,
0333     .undo_cwnd  = tcp_reno_undo_cwnd,
0334     .cong_avoid = tcp_illinois_cong_avoid,
0335     .set_state  = tcp_illinois_state,
0336     .get_info   = tcp_illinois_info,
0337     .pkts_acked = tcp_illinois_acked,
0338
0339     .owner      = THIS_MODULE,
0340     .name       = "illinois",
0341 };
0342
0343 static int __init tcp_illinois_register(void)
0344 {
0345     BUILD_BUG_ON(sizeof(struct illinois) > ICSK_CA_PRIV_SIZE);
0346     return tcp_register_congestion_control(&tcp_illinois);
0347 }
0348
0349 static void __exit tcp_illinois_unregister(void)
0350 {
0351     tcp_unregister_congestion_control(&tcp_illinois);
0352 }
0353
0354 module_init(tcp_illinois_register);
0355 module_exit(tcp_illinois_unregister);
0356
0357 MODULE_AUTHOR("Stephen Hemminger, Shao Liu");
0358 MODULE_LICENSE("GPL");
0359 MODULE_DESCRIPTION("TCP Illinois");
0360 MODULE_VERSION("1.0");