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