net/ipv4/tcp_yeah.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  *
0004  *   YeAH TCP
0005  *
0006  * For further details look at:
0007  *   https://web.archive.org/web/20080316215752/http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf
0008  *
0009  */
0010 #include <linux/mm.h>
0011 #include <linux/module.h>
0012 #include <linux/skbuff.h>
0013 #include <linux/inet_diag.h>
0014
0015 #include <net/tcp.h>
0016
0017 #include "tcp_vegas.h"
0018
0019 #define TCP_YEAH_ALPHA       80 /* number of packets queued at the bottleneck */
0020 #define TCP_YEAH_GAMMA        1 /* fraction of queue to be removed per rtt */
0021 #define TCP_YEAH_DELTA        3 /* log minimum fraction of cwnd to be removed on loss */
0022 #define TCP_YEAH_EPSILON      1 /* log maximum fraction to be removed on early decongestion */
0023 #define TCP_YEAH_PHY          8 /* maximum delta from base */
0024 #define TCP_YEAH_RHO         16 /* minimum number of consecutive rtt to consider competition on loss */
0025 #define TCP_YEAH_ZETA        50 /* minimum number of state switches to reset reno_count */
0026
0027 #define TCP_SCALABLE_AI_CNT  100U
0028
0029 /* YeAH variables */
0030 struct yeah {
0031     struct vegas vegas; /* must be first */
0032
0033     /* YeAH */
0034     u32 lastQ;
0035     u32 doing_reno_now;
0036
0037     u32 reno_count;
0038     u32 fast_count;
0039 };
0040
0041 static void tcp_yeah_init(struct sock *sk)
0042 {
0043     struct tcp_sock *tp = tcp_sk(sk);
0044     struct yeah *yeah = inet_csk_ca(sk);
0045
0046     tcp_vegas_init(sk);
0047
0048     yeah->doing_reno_now = 0;
0049     yeah->lastQ = 0;
0050
0051     yeah->reno_count = 2;
0052
0053     /* Ensure the MD arithmetic works.  This is somewhat pedantic,
0054      * since I don't think we will see a cwnd this large. :) */
0055     tp->snd_cwnd_clamp = min_t(u32, tp->snd_cwnd_clamp, 0xffffffff/128);
0056 }
0057
0058 static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack, u32 acked)
0059 {
0060     struct tcp_sock *tp = tcp_sk(sk);
0061     struct yeah *yeah = inet_csk_ca(sk);
0062
0063     if (!tcp_is_cwnd_limited(sk))
0064         return;
0065
0066     if (tcp_in_slow_start(tp)) {
0067         acked = tcp_slow_start(tp, acked);
0068         if (!acked)
0069             goto do_vegas;
0070     }
0071
0072     if (!yeah->doing_reno_now) {
0073         /* Scalable */
0074         tcp_cong_avoid_ai(tp, min(tcp_snd_cwnd(tp), TCP_SCALABLE_AI_CNT),
0075                   acked);
0076     } else {
0077         /* Reno */
0078         tcp_cong_avoid_ai(tp, tcp_snd_cwnd(tp), acked);
0079     }
0080
0081     /* The key players are v_vegas.beg_snd_una and v_beg_snd_nxt.
0082      *
0083      * These are so named because they represent the approximate values
0084      * of snd_una and snd_nxt at the beginning of the current RTT. More
0085      * precisely, they represent the amount of data sent during the RTT.
0086      * At the end of the RTT, when we receive an ACK for v_beg_snd_nxt,
0087      * we will calculate that (v_beg_snd_nxt - v_vegas.beg_snd_una) outstanding
0088      * bytes of data have been ACKed during the course of the RTT, giving
0089      * an "actual" rate of:
0090      *
0091      *     (v_beg_snd_nxt - v_vegas.beg_snd_una) / (rtt duration)
0092      *
0093      * Unfortunately, v_vegas.beg_snd_una is not exactly equal to snd_una,
0094      * because delayed ACKs can cover more than one segment, so they
0095      * don't line up yeahly with the boundaries of RTTs.
0096      *
0097      * Another unfortunate fact of life is that delayed ACKs delay the
0098      * advance of the left edge of our send window, so that the number
0099      * of bytes we send in an RTT is often less than our cwnd will allow.
0100      * So we keep track of our cwnd separately, in v_beg_snd_cwnd.
0101      */
0102 do_vegas:
0103     if (after(ack, yeah->vegas.beg_snd_nxt)) {
0104         /* We do the Vegas calculations only if we got enough RTT
0105          * samples that we can be reasonably sure that we got
0106          * at least one RTT sample that wasn't from a delayed ACK.
0107          * If we only had 2 samples total,
0108          * then that means we're getting only 1 ACK per RTT, which
0109          * means they're almost certainly delayed ACKs.
0110          * If  we have 3 samples, we should be OK.
0111          */
0112
0113         if (yeah->vegas.cntRTT > 2) {
0114             u32 rtt, queue;
0115             u64 bw;
0116
0117             /* We have enough RTT samples, so, using the Vegas
0118              * algorithm, we determine if we should increase or
0119              * decrease cwnd, and by how much.
0120              */
0121
0122             /* Pluck out the RTT we are using for the Vegas
0123              * calculations. This is the min RTT seen during the
0124              * last RTT. Taking the min filters out the effects
0125              * of delayed ACKs, at the cost of noticing congestion
0126              * a bit later.
0127              */
0128             rtt = yeah->vegas.minRTT;
0129
0130             /* Compute excess number of packets above bandwidth
0131              * Avoid doing full 64 bit divide.
0132              */
0133             bw = tcp_snd_cwnd(tp);
0134             bw *= rtt - yeah->vegas.baseRTT;
0135             do_div(bw, rtt);
0136             queue = bw;
0137
0138             if (queue > TCP_YEAH_ALPHA ||
0139                 rtt - yeah->vegas.baseRTT > (yeah->vegas.baseRTT / TCP_YEAH_PHY)) {
0140                 if (queue > TCP_YEAH_ALPHA &&
0141                     tcp_snd_cwnd(tp) > yeah->reno_count) {
0142                     u32 reduction = min(queue / TCP_YEAH_GAMMA ,
0143                                 tcp_snd_cwnd(tp) >> TCP_YEAH_EPSILON);
0144
0145                     tcp_snd_cwnd_set(tp, tcp_snd_cwnd(tp) - reduction);
0146
0147                     tcp_snd_cwnd_set(tp, max(tcp_snd_cwnd(tp),
0148                                  yeah->reno_count));
0149
0150                     tp->snd_ssthresh = tcp_snd_cwnd(tp);
0151                 }
0152
0153                 if (yeah->reno_count <= 2)
0154                     yeah->reno_count = max(tcp_snd_cwnd(tp)>>1, 2U);
0155                 else
0156                     yeah->reno_count++;
0157
0158                 yeah->doing_reno_now = min(yeah->doing_reno_now + 1,
0159                                0xffffffU);
0160             } else {
0161                 yeah->fast_count++;
0162
0163                 if (yeah->fast_count > TCP_YEAH_ZETA) {
0164                     yeah->reno_count = 2;
0165                     yeah->fast_count = 0;
0166                 }
0167
0168                 yeah->doing_reno_now = 0;
0169             }
0170
0171             yeah->lastQ = queue;
0172         }
0173
0174         /* Save the extent of the current window so we can use this
0175          * at the end of the next RTT.
0176          */
0177         yeah->vegas.beg_snd_una  = yeah->vegas.beg_snd_nxt;
0178         yeah->vegas.beg_snd_nxt  = tp->snd_nxt;
0179         yeah->vegas.beg_snd_cwnd = tcp_snd_cwnd(tp);
0180
0181         /* Wipe the slate clean for the next RTT. */
0182         yeah->vegas.cntRTT = 0;
0183         yeah->vegas.minRTT = 0x7fffffff;
0184     }
0185 }
0186
0187 static u32 tcp_yeah_ssthresh(struct sock *sk)
0188 {
0189     const struct tcp_sock *tp = tcp_sk(sk);
0190     struct yeah *yeah = inet_csk_ca(sk);
0191     u32 reduction;
0192
0193     if (yeah->doing_reno_now < TCP_YEAH_RHO) {
0194         reduction = yeah->lastQ;
0195
0196         reduction = min(reduction, max(tcp_snd_cwnd(tp)>>1, 2U));
0197
0198         reduction = max(reduction, tcp_snd_cwnd(tp) >> TCP_YEAH_DELTA);
0199     } else
0200         reduction = max(tcp_snd_cwnd(tp)>>1, 2U);
0201
0202     yeah->fast_count = 0;
0203     yeah->reno_count = max(yeah->reno_count>>1, 2U);
0204
0205     return max_t(int, tcp_snd_cwnd(tp) - reduction, 2);
0206 }
0207
0208 static struct tcp_congestion_ops tcp_yeah __read_mostly = {
0209     .init       = tcp_yeah_init,
0210     .ssthresh   = tcp_yeah_ssthresh,
0211     .undo_cwnd      = tcp_reno_undo_cwnd,
0212     .cong_avoid = tcp_yeah_cong_avoid,
0213     .set_state  = tcp_vegas_state,
0214     .cwnd_event = tcp_vegas_cwnd_event,
0215     .get_info   = tcp_vegas_get_info,
0216     .pkts_acked = tcp_vegas_pkts_acked,
0217
0218     .owner      = THIS_MODULE,
0219     .name       = "yeah",
0220 };
0221
0222 static int __init tcp_yeah_register(void)
0223 {
0224     BUILD_BUG_ON(sizeof(struct yeah) > ICSK_CA_PRIV_SIZE);
0225     tcp_register_congestion_control(&tcp_yeah);
0226     return 0;
0227 }
0228
0229 static void __exit tcp_yeah_unregister(void)
0230 {
0231     tcp_unregister_congestion_control(&tcp_yeah);
0232 }
0233
0234 module_init(tcp_yeah_register);
0235 module_exit(tcp_yeah_unregister);
0236
0237 MODULE_AUTHOR("Angelo P. Castellani");
0238 MODULE_LICENSE("GPL");
0239 MODULE_DESCRIPTION("YeAH TCP");