1 // SPDX-License-Identifier: GPL-2.0-only
8  * "TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm
9  *  for High-Speed Networks"
12  * Implemented from description in paper and ns-2 simulation.
13  * Copyright (C) 2007 Stephen Hemminger <shemminger@linux-foundation.org>
35 static int win_thresh __read_mostly = 15;
39 static int theta __read_mostly = 5;
51 	u32	beta;		/* Muliplicative decrease */  member
57 static void rtt_reset(struct sock *sk)  in rtt_reset()
62 	ca->end_seq = tp->snd_nxt;  in rtt_reset()
63 	ca->cnt_rtt = 0;  in rtt_reset()
64 	ca->sum_rtt = 0;  in rtt_reset()
69 static void tcp_illinois_init(struct sock *sk)  in tcp_illinois_init()
73 	ca->alpha = ALPHA_MAX;  in tcp_illinois_init()
74 	ca->beta = BETA_BASE;  in tcp_illinois_init()
75 	ca->base_rtt = 0x7fffffff;  in tcp_illinois_init()
76 	ca->max_rtt = 0;  in tcp_illinois_init()
78 	ca->acked = 0;  in tcp_illinois_init()
79 	ca->rtt_low = 0;  in tcp_illinois_init()
80 	ca->rtt_above = 0;  in tcp_illinois_init()
86 static void tcp_illinois_acked(struct sock *sk, const struct ack_sample *sample)  in tcp_illinois_acked()
89 	s32 rtt_us = sample->rtt_us;  in tcp_illinois_acked()
91 	ca->acked = sample->pkts_acked;  in tcp_illinois_acked()
102 	if (ca->base_rtt > rtt_us)  in tcp_illinois_acked()
103 		ca->base_rtt = rtt_us;  in tcp_illinois_acked()
106 	if (ca->max_rtt < rtt_us)  in tcp_illinois_acked()
107 		ca->max_rtt = rtt_us;  in tcp_illinois_acked()
109 	++ca->cnt_rtt;  in tcp_illinois_acked()
110 	ca->sum_rtt += rtt_us;  in tcp_illinois_acked()
114 static inline u32 max_delay(const struct illinois *ca)  in max_delay()
116 	return ca->max_rtt - ca->base_rtt;  in max_delay()
120 static inline u32 avg_delay(const struct illinois *ca)  in avg_delay()
122 	u64 t = ca->sum_rtt;  in avg_delay()
124 	do_div(t, ca->cnt_rtt);  in avg_delay()
125 	return t - ca->base_rtt;  in avg_delay()
140 static u32 alpha(struct illinois *ca, u32 da, u32 dm)  in alpha()
146 		if (!ca->rtt_above)  in alpha()
152 		if (++ca->rtt_low < theta)  in alpha()
153 			return ca->alpha;  in alpha()
155 		ca->rtt_low = 0;  in alpha()
156 		ca->rtt_above = 0;  in alpha()
160 	ca->rtt_above = 1;  in alpha()
165 	 *      (dm - d1) amin amax  in alpha()
166 	 * k1 = -------------------  in alpha()
167 	 *         amax - amin  in alpha()
169 	 *       (dm - d1) amin  in alpha()
170 	 * k2 = ----------------  - d1  in alpha()
171 	 *        amax - amin  in alpha()
174 	 * alpha = ----------  in alpha()
178 	dm -= d1;  in alpha()
179 	da -= d1;  in alpha()
181 		(dm + (da  * (ALPHA_MAX - ALPHA_MIN)) / ALPHA_MIN);  in alpha()
185  * Beta used for multiplicative decrease.
188  * If delay is small (10% of max) then beta = 1/8
189  * If delay is up to 80% of max then beta = 1/2
192 static u32 beta(u32 da, u32 dm)  in beta()  function
207 	 *       bmin d3 - bmax d2  in beta()
208 	 * k3 = -------------------  in beta()
209 	 *         d3 - d2  in beta()
211 	 *       bmax - bmin  in beta()
212 	 * k4 = -------------  in beta()
213 	 *         d3 - d2  in beta()
217 	return (BETA_MIN * d3 - BETA_MAX * d2 + (BETA_MAX - BETA_MIN) * da)  in beta()
218 		/ (d3 - d2);  in beta()
221 /* Update alpha and beta values once per RTT */
222 static void update_params(struct sock *sk)  in update_params()
228 		ca->alpha = ALPHA_BASE;  in update_params()
229 		ca->beta = BETA_BASE;  in update_params()
230 	} else if (ca->cnt_rtt > 0) {  in update_params()
234 		ca->alpha = alpha(ca, da, dm);  in update_params()
235 		ca->beta = beta(da, dm);  in update_params()
244 static void tcp_illinois_state(struct sock *sk, u8 new_state)  in tcp_illinois_state()
249 		ca->alpha = ALPHA_BASE;  in tcp_illinois_state()
250 		ca->beta = BETA_BASE;  in tcp_illinois_state()
251 		ca->rtt_low = 0;  in tcp_illinois_state()
252 		ca->rtt_above = 0;  in tcp_illinois_state()
260 static void tcp_illinois_cong_avoid(struct sock *sk, u32 ack, u32 acked)  in tcp_illinois_cong_avoid()
265 	if (after(ack, ca->end_seq))  in tcp_illinois_cong_avoid()
280 		tp->snd_cwnd_cnt += ca->acked;  in tcp_illinois_cong_avoid()
281 		ca->acked = 1;  in tcp_illinois_cong_avoid()
284 		 * tp->snd_cwnd += alpha/tp->snd_cwnd  in tcp_illinois_cong_avoid()
286 		delta = (tp->snd_cwnd_cnt * ca->alpha) >> ALPHA_SHIFT;  in tcp_illinois_cong_avoid()
289 						 (u32)tp->snd_cwnd_clamp));  in tcp_illinois_cong_avoid()
290 			tp->snd_cwnd_cnt = 0;  in tcp_illinois_cong_avoid()
295 static u32 tcp_illinois_ssthresh(struct sock *sk)  in tcp_illinois_ssthresh()
302 	decr = (tcp_snd_cwnd(tp) * ca->beta) >> BETA_SHIFT;  in tcp_illinois_ssthresh()
303 	return max(tcp_snd_cwnd(tp) - decr, 2U);  in tcp_illinois_ssthresh()
307 static size_t tcp_illinois_info(struct sock *sk, u32 ext, int *attr,  in tcp_illinois_info()
312 	if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {  in tcp_illinois_info()
313 		info->vegas.tcpv_enabled = 1;  in tcp_illinois_info()
314 		info->vegas.tcpv_rttcnt = ca->cnt_rtt;  in tcp_illinois_info()
315 		info->vegas.tcpv_minrtt = ca->base_rtt;  in tcp_illinois_info()
316 		info->vegas.tcpv_rtt = 0;  in tcp_illinois_info()
318 		if (info->vegas.tcpv_rttcnt > 0) {  in tcp_illinois_info()
319 			u64 t = ca->sum_rtt;  in tcp_illinois_info()
321 			do_div(t, info->vegas.tcpv_rttcnt);  in tcp_illinois_info()
322 			info->vegas.tcpv_rtt = t;  in tcp_illinois_info()
330 static struct tcp_congestion_ops tcp_illinois __read_mostly = {
343 static int __init tcp_illinois_register(void)  in tcp_illinois_register()
349 static void __exit tcp_illinois_unregister(void)  in tcp_illinois_unregister()