Commit | Line | Data |
---|---|---|
09c434b8 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
87270762 | 2 | /* |
b7d7a9e3 | 3 | * TCP Westwood+: end-to-end bandwidth estimation for TCP |
87270762 | 4 | * |
b7d7a9e3 LDC |
5 | * Angelo Dell'Aera: author of the first version of TCP Westwood+ in Linux 2.4 |
6 | * | |
7 | * Support at http://c3lab.poliba.it/index.php/Westwood | |
8 | * Main references in literature: | |
9 | * | |
10 | * - Mascolo S, Casetti, M. Gerla et al. | |
11 | * "TCP Westwood: bandwidth estimation for TCP" Proc. ACM Mobicom 2001 | |
12 | * | |
13 | * - A. Grieco, s. Mascolo | |
14 | * "Performance evaluation of New Reno, Vegas, Westwood+ TCP" ACM Computer | |
15 | * Comm. Review, 2004 | |
16 | * | |
17 | * - A. Dell'Aera, L. Grieco, S. Mascolo. | |
18 | * "Linux 2.4 Implementation of Westwood+ TCP with Rate-Halving : | |
19 | * A Performance Evaluation Over the Internet" (ICC 2004), Paris, June 2004 | |
20 | * | |
21 | * Westwood+ employs end-to-end bandwidth measurement to set cwnd and | |
22 | * ssthresh after packet loss. The probing phase is as the original Reno. | |
87270762 SH |
23 | */ |
24 | ||
87270762 SH |
25 | #include <linux/mm.h> |
26 | #include <linux/module.h> | |
27 | #include <linux/skbuff.h> | |
a8c2190e | 28 | #include <linux/inet_diag.h> |
87270762 SH |
29 | #include <net/tcp.h> |
30 | ||
31 | /* TCP Westwood structure */ | |
32 | struct westwood { | |
33 | u32 bw_ns_est; /* first bandwidth estimation..not too smoothed 8) */ | |
34 | u32 bw_est; /* bandwidth estimate */ | |
35 | u32 rtt_win_sx; /* here starts a new evaluation... */ | |
36 | u32 bk; | |
37 | u32 snd_una; /* used for evaluating the number of acked bytes */ | |
38 | u32 cumul_ack; | |
39 | u32 accounted; | |
40 | u32 rtt; | |
41 | u32 rtt_min; /* minimum observed RTT */ | |
f61e2901 | 42 | u8 first_ack; /* flag which infers that this is the first ack */ |
bc726a71 | 43 | u8 reset_rtt_min; /* Reset RTT min to next RTT sample*/ |
87270762 SH |
44 | }; |
45 | ||
87270762 SH |
46 | /* TCP Westwood functions and constants */ |
47 | #define TCP_WESTWOOD_RTT_MIN (HZ/20) /* 50ms */ | |
48 | #define TCP_WESTWOOD_INIT_RTT (20*HZ) /* maybe too conservative?! */ | |
49 | ||
50 | /* | |
51 | * @tcp_westwood_create | |
52 | * This function initializes fields used in TCP Westwood+, | |
53 | * it is called after the initial SYN, so the sequence numbers | |
54 | * are correct but new passive connections we have no | |
55 | * information about RTTmin at this time so we simply set it to | |
56 | * TCP_WESTWOOD_INIT_RTT. This value was chosen to be too conservative | |
57 | * since in this way we're sure it will be updated in a consistent | |
58 | * way as soon as possible. It will reasonably happen within the first | |
59 | * RTT period of the connection lifetime. | |
60 | */ | |
6687e988 | 61 | static void tcp_westwood_init(struct sock *sk) |
87270762 | 62 | { |
6687e988 | 63 | struct westwood *w = inet_csk_ca(sk); |
87270762 SH |
64 | |
65 | w->bk = 0; | |
e905a9ed YH |
66 | w->bw_ns_est = 0; |
67 | w->bw_est = 0; | |
68 | w->accounted = 0; | |
69 | w->cumul_ack = 0; | |
bc726a71 | 70 | w->reset_rtt_min = 1; |
87270762 | 71 | w->rtt_min = w->rtt = TCP_WESTWOOD_INIT_RTT; |
ad5ad69e | 72 | w->rtt_win_sx = tcp_jiffies32; |
6687e988 | 73 | w->snd_una = tcp_sk(sk)->snd_una; |
f61e2901 | 74 | w->first_ack = 1; |
87270762 SH |
75 | } |
76 | ||
77 | /* | |
78 | * @westwood_do_filter | |
79 | * Low-pass filter. Implemented using constant coefficients. | |
80 | */ | |
81 | static inline u32 westwood_do_filter(u32 a, u32 b) | |
82 | { | |
a02cec21 | 83 | return ((7 * a) + b) >> 3; |
87270762 SH |
84 | } |
85 | ||
b3a92eab | 86 | static void westwood_filter(struct westwood *w, u32 delta) |
87270762 | 87 | { |
b3a92eab LDC |
88 | /* If the filter is empty fill it with the first sample of bandwidth */ |
89 | if (w->bw_ns_est == 0 && w->bw_est == 0) { | |
90 | w->bw_ns_est = w->bk / delta; | |
91 | w->bw_est = w->bw_ns_est; | |
92 | } else { | |
93 | w->bw_ns_est = westwood_do_filter(w->bw_ns_est, w->bk / delta); | |
94 | w->bw_est = westwood_do_filter(w->bw_est, w->bw_ns_est); | |
95 | } | |
87270762 SH |
96 | } |
97 | ||
98 | /* | |
99 | * @westwood_pkts_acked | |
100 | * Called after processing group of packets. | |
101 | * but all westwood needs is the last sample of srtt. | |
102 | */ | |
756ee172 LB |
103 | static void tcp_westwood_pkts_acked(struct sock *sk, |
104 | const struct ack_sample *sample) | |
87270762 | 105 | { |
6687e988 | 106 | struct westwood *w = inet_csk_ca(sk); |
30cfd0ba | 107 | |
756ee172 LB |
108 | if (sample->rtt_us > 0) |
109 | w->rtt = usecs_to_jiffies(sample->rtt_us); | |
87270762 SH |
110 | } |
111 | ||
112 | /* | |
113 | * @westwood_update_window | |
114 | * It updates RTT evaluation window if it is the right moment to do | |
115 | * it. If so it calls filter for evaluating bandwidth. | |
116 | */ | |
6687e988 | 117 | static void westwood_update_window(struct sock *sk) |
87270762 | 118 | { |
6687e988 | 119 | struct westwood *w = inet_csk_ca(sk); |
ad5ad69e | 120 | s32 delta = tcp_jiffies32 - w->rtt_win_sx; |
87270762 | 121 | |
b7d7a9e3 | 122 | /* Initialize w->snd_una with the first acked sequence number in order |
f61e2901 SH |
123 | * to fix mismatch between tp->snd_una and w->snd_una for the first |
124 | * bandwidth sample | |
125 | */ | |
e905a9ed | 126 | if (w->first_ack) { |
f61e2901 SH |
127 | w->snd_una = tcp_sk(sk)->snd_una; |
128 | w->first_ack = 0; | |
129 | } | |
130 | ||
87270762 SH |
131 | /* |
132 | * See if a RTT-window has passed. | |
133 | * Be careful since if RTT is less than | |
134 | * 50ms we don't filter but we continue 'building the sample'. | |
135 | * This minimum limit was chosen since an estimation on small | |
136 | * time intervals is better to avoid... | |
137 | * Obviously on a LAN we reasonably will always have | |
138 | * right_bound = left_bound + WESTWOOD_RTT_MIN | |
139 | */ | |
140 | if (w->rtt && delta > max_t(u32, w->rtt, TCP_WESTWOOD_RTT_MIN)) { | |
141 | westwood_filter(w, delta); | |
142 | ||
143 | w->bk = 0; | |
ad5ad69e | 144 | w->rtt_win_sx = tcp_jiffies32; |
87270762 SH |
145 | } |
146 | } | |
147 | ||
bc726a71 LDC |
148 | static inline void update_rtt_min(struct westwood *w) |
149 | { | |
150 | if (w->reset_rtt_min) { | |
151 | w->rtt_min = w->rtt; | |
e905a9ed | 152 | w->reset_rtt_min = 0; |
bc726a71 LDC |
153 | } else |
154 | w->rtt_min = min(w->rtt, w->rtt_min); | |
155 | } | |
156 | ||
87270762 SH |
157 | /* |
158 | * @westwood_fast_bw | |
159 | * It is called when we are in fast path. In particular it is called when | |
160 | * header prediction is successful. In such case in fact update is | |
161 | * straight forward and doesn't need any particular care. | |
162 | */ | |
6687e988 | 163 | static inline void westwood_fast_bw(struct sock *sk) |
87270762 | 164 | { |
6687e988 ACM |
165 | const struct tcp_sock *tp = tcp_sk(sk); |
166 | struct westwood *w = inet_csk_ca(sk); | |
87270762 | 167 | |
6687e988 | 168 | westwood_update_window(sk); |
87270762 SH |
169 | |
170 | w->bk += tp->snd_una - w->snd_una; | |
171 | w->snd_una = tp->snd_una; | |
bc726a71 | 172 | update_rtt_min(w); |
87270762 SH |
173 | } |
174 | ||
175 | /* | |
176 | * @westwood_acked_count | |
177 | * This function evaluates cumul_ack for evaluating bk in case of | |
178 | * delayed or partial acks. | |
179 | */ | |
6687e988 | 180 | static inline u32 westwood_acked_count(struct sock *sk) |
87270762 | 181 | { |
6687e988 ACM |
182 | const struct tcp_sock *tp = tcp_sk(sk); |
183 | struct westwood *w = inet_csk_ca(sk); | |
87270762 SH |
184 | |
185 | w->cumul_ack = tp->snd_una - w->snd_una; | |
186 | ||
e905a9ed YH |
187 | /* If cumul_ack is 0 this is a dupack since it's not moving |
188 | * tp->snd_una. | |
189 | */ | |
190 | if (!w->cumul_ack) { | |
87270762 SH |
191 | w->accounted += tp->mss_cache; |
192 | w->cumul_ack = tp->mss_cache; | |
193 | } | |
194 | ||
e905a9ed | 195 | if (w->cumul_ack > tp->mss_cache) { |
87270762 SH |
196 | /* Partial or delayed ack */ |
197 | if (w->accounted >= w->cumul_ack) { | |
198 | w->accounted -= w->cumul_ack; | |
199 | w->cumul_ack = tp->mss_cache; | |
200 | } else { | |
201 | w->cumul_ack -= w->accounted; | |
202 | w->accounted = 0; | |
203 | } | |
204 | } | |
205 | ||
206 | w->snd_una = tp->snd_una; | |
207 | ||
208 | return w->cumul_ack; | |
209 | } | |
210 | ||
87270762 SH |
211 | /* |
212 | * TCP Westwood | |
213 | * Here limit is evaluated as Bw estimation*RTTmin (for obtaining it | |
214 | * in packets we use mss_cache). Rttmin is guaranteed to be >= 2 | |
215 | * so avoids ever returning 0. | |
216 | */ | |
72dc5b92 | 217 | static u32 tcp_westwood_bw_rttmin(const struct sock *sk) |
87270762 | 218 | { |
72dc5b92 SH |
219 | const struct tcp_sock *tp = tcp_sk(sk); |
220 | const struct westwood *w = inet_csk_ca(sk); | |
688d1945 | 221 | |
72dc5b92 | 222 | return max_t(u32, (w->bw_est * w->rtt_min) / tp->mss_cache, 2); |
87270762 SH |
223 | } |
224 | ||
7354c8c3 FW |
225 | static void tcp_westwood_ack(struct sock *sk, u32 ack_flags) |
226 | { | |
227 | if (ack_flags & CA_ACK_SLOWPATH) { | |
228 | struct westwood *w = inet_csk_ca(sk); | |
229 | ||
230 | westwood_update_window(sk); | |
231 | w->bk += westwood_acked_count(sk); | |
232 | ||
233 | update_rtt_min(w); | |
234 | return; | |
235 | } | |
236 | ||
237 | westwood_fast_bw(sk); | |
238 | } | |
239 | ||
6687e988 | 240 | static void tcp_westwood_event(struct sock *sk, enum tcp_ca_event event) |
87270762 | 241 | { |
6687e988 ACM |
242 | struct tcp_sock *tp = tcp_sk(sk); |
243 | struct westwood *w = inet_csk_ca(sk); | |
b7d7a9e3 | 244 | |
2de979bd | 245 | switch (event) { |
87270762 | 246 | case CA_EVENT_COMPLETE_CWR: |
72dc5b92 | 247 | tp->snd_cwnd = tp->snd_ssthresh = tcp_westwood_bw_rttmin(sk); |
87270762 | 248 | break; |
9b44190d | 249 | case CA_EVENT_LOSS: |
72dc5b92 | 250 | tp->snd_ssthresh = tcp_westwood_bw_rttmin(sk); |
e905a9ed | 251 | /* Update RTT_min when next ack arrives */ |
bc726a71 | 252 | w->reset_rtt_min = 1; |
87270762 | 253 | break; |
87270762 SH |
254 | default: |
255 | /* don't care */ | |
256 | break; | |
257 | } | |
258 | } | |
259 | ||
87270762 | 260 | /* Extract info for Tcp socket info provided via netlink. */ |
31ccd0e6 ED |
261 | static size_t tcp_westwood_info(struct sock *sk, u32 ext, int *attr, |
262 | union tcp_cc_info *info) | |
87270762 | 263 | { |
6687e988 | 264 | const struct westwood *ca = inet_csk_ca(sk); |
688d1945 | 265 | |
73c1f4a0 | 266 | if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) { |
31ccd0e6 ED |
267 | info->vegas.tcpv_enabled = 1; |
268 | info->vegas.tcpv_rttcnt = 0; | |
be7164cd L |
269 | info->vegas.tcpv_rtt = jiffies_to_usecs(ca->rtt); |
270 | info->vegas.tcpv_minrtt = jiffies_to_usecs(ca->rtt_min); | |
26728105 | 271 | |
31ccd0e6 ED |
272 | *attr = INET_DIAG_VEGASINFO; |
273 | return sizeof(struct tcpvegas_info); | |
87270762 | 274 | } |
521f1cf1 | 275 | return 0; |
87270762 SH |
276 | } |
277 | ||
a252bebe | 278 | static struct tcp_congestion_ops tcp_westwood __read_mostly = { |
87270762 SH |
279 | .init = tcp_westwood_init, |
280 | .ssthresh = tcp_reno_ssthresh, | |
281 | .cong_avoid = tcp_reno_cong_avoid, | |
e9799183 | 282 | .undo_cwnd = tcp_reno_undo_cwnd, |
87270762 | 283 | .cwnd_event = tcp_westwood_event, |
7354c8c3 | 284 | .in_ack_event = tcp_westwood_ack, |
87270762 SH |
285 | .get_info = tcp_westwood_info, |
286 | .pkts_acked = tcp_westwood_pkts_acked, | |
287 | ||
288 | .owner = THIS_MODULE, | |
289 | .name = "westwood" | |
290 | }; | |
291 | ||
292 | static int __init tcp_westwood_register(void) | |
293 | { | |
74975d40 | 294 | BUILD_BUG_ON(sizeof(struct westwood) > ICSK_CA_PRIV_SIZE); |
87270762 SH |
295 | return tcp_register_congestion_control(&tcp_westwood); |
296 | } | |
297 | ||
298 | static void __exit tcp_westwood_unregister(void) | |
299 | { | |
300 | tcp_unregister_congestion_control(&tcp_westwood); | |
301 | } | |
302 | ||
303 | module_init(tcp_westwood_register); | |
304 | module_exit(tcp_westwood_unregister); | |
305 | ||
306 | MODULE_AUTHOR("Stephen Hemminger, Angelo Dell'Aera"); | |
307 | MODULE_LICENSE("GPL"); | |
308 | MODULE_DESCRIPTION("TCP Westwood+"); |