1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * TCP Illinois congestion control. |
4 | * Home page: |
5 | * http://www.ews.uiuc.edu/~shaoliu/tcpillinois/index.html |
6 | * |
7 | * The algorithm is described in: |
8 | * "TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm |
9 | * for High-Speed Networks" |
10 | * http://tamerbasar.csl.illinois.edu/LiuBasarSrikantPerfEvalArtJun2008.pdf |
11 | * |
12 | * Implemented from description in paper and ns-2 simulation. |
13 | * Copyright (C) 2007 Stephen Hemminger <shemminger@linux-foundation.org> |
14 | */ |
15 | |
16 | #include <linux/module.h> |
17 | #include <linux/skbuff.h> |
18 | #include <linux/inet_diag.h> |
19 | #include <asm/div64.h> |
20 | #include <net/tcp.h> |
21 | |
22 | #define ALPHA_SHIFT 7 |
23 | #define ALPHA_SCALE (1u<<ALPHA_SHIFT) |
24 | #define ALPHA_MIN ((3*ALPHA_SCALE)/10) /* ~0.3 */ |
25 | #define ALPHA_MAX (10*ALPHA_SCALE) /* 10.0 */ |
26 | #define ALPHA_BASE ALPHA_SCALE /* 1.0 */ |
27 | #define RTT_MAX (U32_MAX / ALPHA_MAX) /* 3.3 secs */ |
28 | |
29 | #define BETA_SHIFT 6 |
30 | #define BETA_SCALE (1u<<BETA_SHIFT) |
31 | #define BETA_MIN (BETA_SCALE/8) /* 0.125 */ |
32 | #define BETA_MAX (BETA_SCALE/2) /* 0.5 */ |
33 | #define BETA_BASE BETA_MAX |
34 | |
35 | static int win_thresh __read_mostly = 15; |
36 | module_param(win_thresh, int, 0); |
37 | MODULE_PARM_DESC(win_thresh, "Window threshold for starting adaptive sizing" ); |
38 | |
39 | static int theta __read_mostly = 5; |
40 | module_param(theta, int, 0); |
41 | MODULE_PARM_DESC(theta, "# of fast RTT's before full growth" ); |
42 | |
43 | /* TCP Illinois Parameters */ |
44 | struct illinois { |
45 | u64 sum_rtt; /* sum of rtt's measured within last rtt */ |
46 | u16 cnt_rtt; /* # of rtts measured within last rtt */ |
47 | u32 base_rtt; /* min of all rtt in usec */ |
48 | u32 max_rtt; /* max of all rtt in usec */ |
49 | u32 end_seq; /* right edge of current RTT */ |
50 | u32 alpha; /* Additive increase */ |
51 | u32 beta; /* Muliplicative decrease */ |
52 | u16 acked; /* # packets acked by current ACK */ |
53 | u8 rtt_above; /* average rtt has gone above threshold */ |
54 | u8 rtt_low; /* # of rtts measurements below threshold */ |
55 | }; |
56 | |
57 | static void rtt_reset(struct sock *sk) |
58 | { |
59 | struct tcp_sock *tp = tcp_sk(sk); |
60 | struct illinois *ca = inet_csk_ca(sk); |
61 | |
62 | ca->end_seq = tp->snd_nxt; |
63 | ca->cnt_rtt = 0; |
64 | ca->sum_rtt = 0; |
65 | |
66 | /* TODO: age max_rtt? */ |
67 | } |
68 | |
69 | static void tcp_illinois_init(struct sock *sk) |
70 | { |
71 | struct illinois *ca = inet_csk_ca(sk); |
72 | |
73 | ca->alpha = ALPHA_MAX; |
74 | ca->beta = BETA_BASE; |
75 | ca->base_rtt = 0x7fffffff; |
76 | ca->max_rtt = 0; |
77 | |
78 | ca->acked = 0; |
79 | ca->rtt_low = 0; |
80 | ca->rtt_above = 0; |
81 | |
82 | rtt_reset(sk); |
83 | } |
84 | |
85 | /* Measure RTT for each ack. */ |
86 | static void tcp_illinois_acked(struct sock *sk, const struct ack_sample *sample) |
87 | { |
88 | struct illinois *ca = inet_csk_ca(sk); |
89 | s32 rtt_us = sample->rtt_us; |
90 | |
91 | ca->acked = sample->pkts_acked; |
92 | |
93 | /* dup ack, no rtt sample */ |
94 | if (rtt_us < 0) |
95 | return; |
96 | |
97 | /* ignore bogus values, this prevents wraparound in alpha math */ |
98 | if (rtt_us > RTT_MAX) |
99 | rtt_us = RTT_MAX; |
100 | |
101 | /* keep track of minimum RTT seen so far */ |
102 | if (ca->base_rtt > rtt_us) |
103 | ca->base_rtt = rtt_us; |
104 | |
105 | /* and max */ |
106 | if (ca->max_rtt < rtt_us) |
107 | ca->max_rtt = rtt_us; |
108 | |
109 | ++ca->cnt_rtt; |
110 | ca->sum_rtt += rtt_us; |
111 | } |
112 | |
113 | /* Maximum queuing delay */ |
114 | static inline u32 max_delay(const struct illinois *ca) |
115 | { |
116 | return ca->max_rtt - ca->base_rtt; |
117 | } |
118 | |
119 | /* Average queuing delay */ |
120 | static inline u32 avg_delay(const struct illinois *ca) |
121 | { |
122 | u64 t = ca->sum_rtt; |
123 | |
124 | do_div(t, ca->cnt_rtt); |
125 | return t - ca->base_rtt; |
126 | } |
127 | |
128 | /* |
129 | * Compute value of alpha used for additive increase. |
130 | * If small window then use 1.0, equivalent to Reno. |
131 | * |
132 | * For larger windows, adjust based on average delay. |
133 | * A. If average delay is at minimum (we are uncongested), |
134 | * then use large alpha (10.0) to increase faster. |
135 | * B. If average delay is at maximum (getting congested) |
136 | * then use small alpha (0.3) |
137 | * |
138 | * The result is a convex window growth curve. |
139 | */ |
140 | static u32 alpha(struct illinois *ca, u32 da, u32 dm) |
141 | { |
142 | u32 d1 = dm / 100; /* Low threshold */ |
143 | |
144 | if (da <= d1) { |
145 | /* If never got out of low delay zone, then use max */ |
146 | if (!ca->rtt_above) |
147 | return ALPHA_MAX; |
148 | |
149 | /* Wait for 5 good RTT's before allowing alpha to go alpha max. |
150 | * This prevents one good RTT from causing sudden window increase. |
151 | */ |
152 | if (++ca->rtt_low < theta) |
153 | return ca->alpha; |
154 | |
155 | ca->rtt_low = 0; |
156 | ca->rtt_above = 0; |
157 | return ALPHA_MAX; |
158 | } |
159 | |
160 | ca->rtt_above = 1; |
161 | |
162 | /* |
163 | * Based on: |
164 | * |
165 | * (dm - d1) amin amax |
166 | * k1 = ------------------- |
167 | * amax - amin |
168 | * |
169 | * (dm - d1) amin |
170 | * k2 = ---------------- - d1 |
171 | * amax - amin |
172 | * |
173 | * k1 |
174 | * alpha = ---------- |
175 | * k2 + da |
176 | */ |
177 | |
178 | dm -= d1; |
179 | da -= d1; |
180 | return (dm * ALPHA_MAX) / |
181 | (dm + (da * (ALPHA_MAX - ALPHA_MIN)) / ALPHA_MIN); |
182 | } |
183 | |
184 | /* |
185 | * Beta used for multiplicative decrease. |
186 | * For small window sizes returns same value as Reno (0.5) |
187 | * |
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 |
190 | * In between is a linear function |
191 | */ |
192 | static u32 beta(u32 da, u32 dm) |
193 | { |
194 | u32 d2, d3; |
195 | |
196 | d2 = dm / 10; |
197 | if (da <= d2) |
198 | return BETA_MIN; |
199 | |
200 | d3 = (8 * dm) / 10; |
201 | if (da >= d3 || d3 <= d2) |
202 | return BETA_MAX; |
203 | |
204 | /* |
205 | * Based on: |
206 | * |
207 | * bmin d3 - bmax d2 |
208 | * k3 = ------------------- |
209 | * d3 - d2 |
210 | * |
211 | * bmax - bmin |
212 | * k4 = ------------- |
213 | * d3 - d2 |
214 | * |
215 | * b = k3 + k4 da |
216 | */ |
217 | return (BETA_MIN * d3 - BETA_MAX * d2 + (BETA_MAX - BETA_MIN) * da) |
218 | / (d3 - d2); |
219 | } |
220 | |
221 | /* Update alpha and beta values once per RTT */ |
222 | static void update_params(struct sock *sk) |
223 | { |
224 | struct tcp_sock *tp = tcp_sk(sk); |
225 | struct illinois *ca = inet_csk_ca(sk); |
226 | |
227 | if (tcp_snd_cwnd(tp) < win_thresh) { |
228 | ca->alpha = ALPHA_BASE; |
229 | ca->beta = BETA_BASE; |
230 | } else if (ca->cnt_rtt > 0) { |
231 | u32 dm = max_delay(ca); |
232 | u32 da = avg_delay(ca); |
233 | |
234 | ca->alpha = alpha(ca, da, dm); |
235 | ca->beta = beta(da, dm); |
236 | } |
237 | |
238 | rtt_reset(sk); |
239 | } |
240 | |
241 | /* |
242 | * In case of loss, reset to default values |
243 | */ |
244 | static void tcp_illinois_state(struct sock *sk, u8 new_state) |
245 | { |
246 | struct illinois *ca = inet_csk_ca(sk); |
247 | |
248 | if (new_state == TCP_CA_Loss) { |
249 | ca->alpha = ALPHA_BASE; |
250 | ca->beta = BETA_BASE; |
251 | ca->rtt_low = 0; |
252 | ca->rtt_above = 0; |
253 | rtt_reset(sk); |
254 | } |
255 | } |
256 | |
257 | /* |
258 | * Increase window in response to successful acknowledgment. |
259 | */ |
260 | static void tcp_illinois_cong_avoid(struct sock *sk, u32 ack, u32 acked) |
261 | { |
262 | struct tcp_sock *tp = tcp_sk(sk); |
263 | struct illinois *ca = inet_csk_ca(sk); |
264 | |
265 | if (after(ack, ca->end_seq)) |
266 | update_params(sk); |
267 | |
268 | /* RFC2861 only increase cwnd if fully utilized */ |
269 | if (!tcp_is_cwnd_limited(sk)) |
270 | return; |
271 | |
272 | /* In slow start */ |
273 | if (tcp_in_slow_start(tp)) |
274 | tcp_slow_start(tp, acked); |
275 | |
276 | else { |
277 | u32 delta; |
278 | |
279 | /* snd_cwnd_cnt is # of packets since last cwnd increment */ |
280 | tp->snd_cwnd_cnt += ca->acked; |
281 | ca->acked = 1; |
282 | |
283 | /* This is close approximation of: |
284 | * tp->snd_cwnd += alpha/tp->snd_cwnd |
285 | */ |
286 | delta = (tp->snd_cwnd_cnt * ca->alpha) >> ALPHA_SHIFT; |
287 | if (delta >= tcp_snd_cwnd(tp)) { |
288 | tcp_snd_cwnd_set(tp, min(tcp_snd_cwnd(tp) + delta / tcp_snd_cwnd(tp), |
289 | (u32)tp->snd_cwnd_clamp)); |
290 | tp->snd_cwnd_cnt = 0; |
291 | } |
292 | } |
293 | } |
294 | |
295 | static u32 tcp_illinois_ssthresh(struct sock *sk) |
296 | { |
297 | struct tcp_sock *tp = tcp_sk(sk); |
298 | struct illinois *ca = inet_csk_ca(sk); |
299 | u32 decr; |
300 | |
301 | /* Multiplicative decrease */ |
302 | decr = (tcp_snd_cwnd(tp) * ca->beta) >> BETA_SHIFT; |
303 | return max(tcp_snd_cwnd(tp) - decr, 2U); |
304 | } |
305 | |
306 | /* Extract info for Tcp socket info provided via netlink. */ |
307 | static size_t tcp_illinois_info(struct sock *sk, u32 ext, int *attr, |
308 | union tcp_cc_info *info) |
309 | { |
310 | const struct illinois *ca = inet_csk_ca(sk); |
311 | |
312 | if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) { |
313 | info->vegas.tcpv_enabled = 1; |
314 | info->vegas.tcpv_rttcnt = ca->cnt_rtt; |
315 | info->vegas.tcpv_minrtt = ca->base_rtt; |
316 | info->vegas.tcpv_rtt = 0; |
317 | |
318 | if (info->vegas.tcpv_rttcnt > 0) { |
319 | u64 t = ca->sum_rtt; |
320 | |
321 | do_div(t, info->vegas.tcpv_rttcnt); |
322 | info->vegas.tcpv_rtt = t; |
323 | } |
324 | *attr = INET_DIAG_VEGASINFO; |
325 | return sizeof(struct tcpvegas_info); |
326 | } |
327 | return 0; |
328 | } |
329 | |
330 | static struct tcp_congestion_ops tcp_illinois __read_mostly = { |
331 | .init = tcp_illinois_init, |
332 | .ssthresh = tcp_illinois_ssthresh, |
333 | .undo_cwnd = tcp_reno_undo_cwnd, |
334 | .cong_avoid = tcp_illinois_cong_avoid, |
335 | .set_state = tcp_illinois_state, |
336 | .get_info = tcp_illinois_info, |
337 | .pkts_acked = tcp_illinois_acked, |
338 | |
339 | .owner = THIS_MODULE, |
340 | .name = "illinois" , |
341 | }; |
342 | |
343 | static int __init tcp_illinois_register(void) |
344 | { |
345 | BUILD_BUG_ON(sizeof(struct illinois) > ICSK_CA_PRIV_SIZE); |
346 | return tcp_register_congestion_control(type: &tcp_illinois); |
347 | } |
348 | |
349 | static void __exit tcp_illinois_unregister(void) |
350 | { |
351 | tcp_unregister_congestion_control(type: &tcp_illinois); |
352 | } |
353 | |
354 | module_init(tcp_illinois_register); |
355 | module_exit(tcp_illinois_unregister); |
356 | |
357 | MODULE_AUTHOR("Stephen Hemminger, Shao Liu" ); |
358 | MODULE_LICENSE("GPL" ); |
359 | MODULE_DESCRIPTION("TCP Illinois" ); |
360 | MODULE_VERSION("1.0" ); |
361 | |