net/ipv4/tcp_htcp.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * H-TCP congestion control. The algorithm is detailed in:
0004  * R.N.Shorten, D.J.Leith:
0005  *   "H-TCP: TCP for high-speed and long-distance networks"
0006  *   Proc. PFLDnet, Argonne, 2004.
0007  * https://www.hamilton.ie/net/htcp3.pdf
0008  */
0009
0010 #include <linux/mm.h>
0011 #include <linux/module.h>
0012 #include <net/tcp.h>
0013
0014 #define ALPHA_BASE  (1<<7)  /* 1.0 with shift << 7 */
0015 #define BETA_MIN    (1<<6)  /* 0.5 with shift << 7 */
0016 #define BETA_MAX    102 /* 0.8 with shift << 7 */
0017
0018 static int use_rtt_scaling __read_mostly = 1;
0019 module_param(use_rtt_scaling, int, 0644);
0020 MODULE_PARM_DESC(use_rtt_scaling, "turn on/off RTT scaling");
0021
0022 static int use_bandwidth_switch __read_mostly = 1;
0023 module_param(use_bandwidth_switch, int, 0644);
0024 MODULE_PARM_DESC(use_bandwidth_switch, "turn on/off bandwidth switcher");
0025
0026 struct htcp {
0027     u32 alpha;      /* Fixed point arith, << 7 */
0028     u8  beta;           /* Fixed point arith, << 7 */
0029     u8  modeswitch; /* Delay modeswitch
0030                    until we had at least one congestion event */
0031     u16 pkts_acked;
0032     u32 packetcount;
0033     u32 minRTT;
0034     u32 maxRTT;
0035     u32 last_cong;  /* Time since last congestion event end */
0036     u32 undo_last_cong;
0037
0038     u32 undo_maxRTT;
0039     u32 undo_old_maxB;
0040
0041     /* Bandwidth estimation */
0042     u32 minB;
0043     u32 maxB;
0044     u32 old_maxB;
0045     u32 Bi;
0046     u32 lasttime;
0047 };
0048
0049 static inline u32 htcp_cong_time(const struct htcp *ca)
0050 {
0051     return jiffies - ca->last_cong;
0052 }
0053
0054 static inline u32 htcp_ccount(const struct htcp *ca)
0055 {
0056     return htcp_cong_time(ca) / ca->minRTT;
0057 }
0058
0059 static inline void htcp_reset(struct htcp *ca)
0060 {
0061     ca->undo_last_cong = ca->last_cong;
0062     ca->undo_maxRTT = ca->maxRTT;
0063     ca->undo_old_maxB = ca->old_maxB;
0064
0065     ca->last_cong = jiffies;
0066 }
0067
0068 static u32 htcp_cwnd_undo(struct sock *sk)
0069 {
0070     struct htcp *ca = inet_csk_ca(sk);
0071
0072     if (ca->undo_last_cong) {
0073         ca->last_cong = ca->undo_last_cong;
0074         ca->maxRTT = ca->undo_maxRTT;
0075         ca->old_maxB = ca->undo_old_maxB;
0076         ca->undo_last_cong = 0;
0077     }
0078
0079     return tcp_reno_undo_cwnd(sk);
0080 }
0081
0082 static inline void measure_rtt(struct sock *sk, u32 srtt)
0083 {
0084     const struct inet_connection_sock *icsk = inet_csk(sk);
0085     struct htcp *ca = inet_csk_ca(sk);
0086
0087     /* keep track of minimum RTT seen so far, minRTT is zero at first */
0088     if (ca->minRTT > srtt || !ca->minRTT)
0089         ca->minRTT = srtt;
0090
0091     /* max RTT */
0092     if (icsk->icsk_ca_state == TCP_CA_Open) {
0093         if (ca->maxRTT < ca->minRTT)
0094             ca->maxRTT = ca->minRTT;
0095         if (ca->maxRTT < srtt &&
0096             srtt <= ca->maxRTT + msecs_to_jiffies(20))
0097             ca->maxRTT = srtt;
0098     }
0099 }
0100
0101 static void measure_achieved_throughput(struct sock *sk,
0102                     const struct ack_sample *sample)
0103 {
0104     const struct inet_connection_sock *icsk = inet_csk(sk);
0105     const struct tcp_sock *tp = tcp_sk(sk);
0106     struct htcp *ca = inet_csk_ca(sk);
0107     u32 now = tcp_jiffies32;
0108
0109     if (icsk->icsk_ca_state == TCP_CA_Open)
0110         ca->pkts_acked = sample->pkts_acked;
0111
0112     if (sample->rtt_us > 0)
0113         measure_rtt(sk, usecs_to_jiffies(sample->rtt_us));
0114
0115     if (!use_bandwidth_switch)
0116         return;
0117
0118     /* achieved throughput calculations */
0119     if (!((1 << icsk->icsk_ca_state) & (TCPF_CA_Open | TCPF_CA_Disorder))) {
0120         ca->packetcount = 0;
0121         ca->lasttime = now;
0122         return;
0123     }
0124
0125     ca->packetcount += sample->pkts_acked;
0126
0127     if (ca->packetcount >= tcp_snd_cwnd(tp) - (ca->alpha >> 7 ? : 1) &&
0128         now - ca->lasttime >= ca->minRTT &&
0129         ca->minRTT > 0) {
0130         __u32 cur_Bi = ca->packetcount * HZ / (now - ca->lasttime);
0131
0132         if (htcp_ccount(ca) <= 3) {
0133             /* just after backoff */
0134             ca->minB = ca->maxB = ca->Bi = cur_Bi;
0135         } else {
0136             ca->Bi = (3 * ca->Bi + cur_Bi) / 4;
0137             if (ca->Bi > ca->maxB)
0138                 ca->maxB = ca->Bi;
0139             if (ca->minB > ca->maxB)
0140                 ca->minB = ca->maxB;
0141         }
0142         ca->packetcount = 0;
0143         ca->lasttime = now;
0144     }
0145 }
0146
0147 static inline void htcp_beta_update(struct htcp *ca, u32 minRTT, u32 maxRTT)
0148 {
0149     if (use_bandwidth_switch) {
0150         u32 maxB = ca->maxB;
0151         u32 old_maxB = ca->old_maxB;
0152
0153         ca->old_maxB = ca->maxB;
0154         if (!between(5 * maxB, 4 * old_maxB, 6 * old_maxB)) {
0155             ca->beta = BETA_MIN;
0156             ca->modeswitch = 0;
0157             return;
0158         }
0159     }
0160
0161     if (ca->modeswitch && minRTT > msecs_to_jiffies(10) && maxRTT) {
0162         ca->beta = (minRTT << 7) / maxRTT;
0163         if (ca->beta < BETA_MIN)
0164             ca->beta = BETA_MIN;
0165         else if (ca->beta > BETA_MAX)
0166             ca->beta = BETA_MAX;
0167     } else {
0168         ca->beta = BETA_MIN;
0169         ca->modeswitch = 1;
0170     }
0171 }
0172
0173 static inline void htcp_alpha_update(struct htcp *ca)
0174 {
0175     u32 minRTT = ca->minRTT;
0176     u32 factor = 1;
0177     u32 diff = htcp_cong_time(ca);
0178
0179     if (diff > HZ) {
0180         diff -= HZ;
0181         factor = 1 + (10 * diff + ((diff / 2) * (diff / 2) / HZ)) / HZ;
0182     }
0183
0184     if (use_rtt_scaling && minRTT) {
0185         u32 scale = (HZ << 3) / (10 * minRTT);
0186
0187         /* clamping ratio to interval [0.5,10]<<3 */
0188         scale = min(max(scale, 1U << 2), 10U << 3);
0189         factor = (factor << 3) / scale;
0190         if (!factor)
0191             factor = 1;
0192     }
0193
0194     ca->alpha = 2 * factor * ((1 << 7) - ca->beta);
0195     if (!ca->alpha)
0196         ca->alpha = ALPHA_BASE;
0197 }
0198
0199 /*
0200  * After we have the rtt data to calculate beta, we'd still prefer to wait one
0201  * rtt before we adjust our beta to ensure we are working from a consistent
0202  * data.
0203  *
0204  * This function should be called when we hit a congestion event since only at
0205  * that point do we really have a real sense of maxRTT (the queues en route
0206  * were getting just too full now).
0207  */
0208 static void htcp_param_update(struct sock *sk)
0209 {
0210     struct htcp *ca = inet_csk_ca(sk);
0211     u32 minRTT = ca->minRTT;
0212     u32 maxRTT = ca->maxRTT;
0213
0214     htcp_beta_update(ca, minRTT, maxRTT);
0215     htcp_alpha_update(ca);
0216
0217     /* add slowly fading memory for maxRTT to accommodate routing changes */
0218     if (minRTT > 0 && maxRTT > minRTT)
0219         ca->maxRTT = minRTT + ((maxRTT - minRTT) * 95) / 100;
0220 }
0221
0222 static u32 htcp_recalc_ssthresh(struct sock *sk)
0223 {
0224     const struct tcp_sock *tp = tcp_sk(sk);
0225     const struct htcp *ca = inet_csk_ca(sk);
0226
0227     htcp_param_update(sk);
0228     return max((tcp_snd_cwnd(tp) * ca->beta) >> 7, 2U);
0229 }
0230
0231 static void htcp_cong_avoid(struct sock *sk, u32 ack, u32 acked)
0232 {
0233     struct tcp_sock *tp = tcp_sk(sk);
0234     struct htcp *ca = inet_csk_ca(sk);
0235
0236     if (!tcp_is_cwnd_limited(sk))
0237         return;
0238
0239     if (tcp_in_slow_start(tp))
0240         tcp_slow_start(tp, acked);
0241     else {
0242         /* In dangerous area, increase slowly.
0243          * In theory this is tp->snd_cwnd += alpha / tp->snd_cwnd
0244          */
0245         if ((tp->snd_cwnd_cnt * ca->alpha)>>7 >= tcp_snd_cwnd(tp)) {
0246             if (tcp_snd_cwnd(tp) < tp->snd_cwnd_clamp)
0247                 tcp_snd_cwnd_set(tp, tcp_snd_cwnd(tp) + 1);
0248             tp->snd_cwnd_cnt = 0;
0249             htcp_alpha_update(ca);
0250         } else
0251             tp->snd_cwnd_cnt += ca->pkts_acked;
0252
0253         ca->pkts_acked = 1;
0254     }
0255 }
0256
0257 static void htcp_init(struct sock *sk)
0258 {
0259     struct htcp *ca = inet_csk_ca(sk);
0260
0261     memset(ca, 0, sizeof(struct htcp));
0262     ca->alpha = ALPHA_BASE;
0263     ca->beta = BETA_MIN;
0264     ca->pkts_acked = 1;
0265     ca->last_cong = jiffies;
0266 }
0267
0268 static void htcp_state(struct sock *sk, u8 new_state)
0269 {
0270     switch (new_state) {
0271     case TCP_CA_Open:
0272         {
0273             struct htcp *ca = inet_csk_ca(sk);
0274
0275             if (ca->undo_last_cong) {
0276                 ca->last_cong = jiffies;
0277                 ca->undo_last_cong = 0;
0278             }
0279         }
0280         break;
0281     case TCP_CA_CWR:
0282     case TCP_CA_Recovery:
0283     case TCP_CA_Loss:
0284         htcp_reset(inet_csk_ca(sk));
0285         break;
0286     }
0287 }
0288
0289 static struct tcp_congestion_ops htcp __read_mostly = {
0290     .init       = htcp_init,
0291     .ssthresh   = htcp_recalc_ssthresh,
0292     .cong_avoid = htcp_cong_avoid,
0293     .set_state  = htcp_state,
0294     .undo_cwnd  = htcp_cwnd_undo,
0295     .pkts_acked = measure_achieved_throughput,
0296     .owner      = THIS_MODULE,
0297     .name       = "htcp",
0298 };
0299
0300 static int __init htcp_register(void)
0301 {
0302     BUILD_BUG_ON(sizeof(struct htcp) > ICSK_CA_PRIV_SIZE);
0303     BUILD_BUG_ON(BETA_MIN >= BETA_MAX);
0304     return tcp_register_congestion_control(&htcp);
0305 }
0306
0307 static void __exit htcp_unregister(void)
0308 {
0309     tcp_unregister_congestion_control(&htcp);
0310 }
0311
0312 module_init(htcp_register);
0313 module_exit(htcp_unregister);
0314
0315 MODULE_AUTHOR("Baruch Even");
0316 MODULE_LICENSE("GPL");
0317 MODULE_DESCRIPTION("H-TCP");