]>
Commit | Line | Data |
---|---|---|
87270762 SH |
1 | /* |
2 | * TCP Westwood+ | |
3 | * | |
4 | * Angelo Dell'Aera: TCP Westwood+ support | |
5 | */ | |
6 | ||
7 | #include <linux/config.h> | |
8 | #include <linux/mm.h> | |
9 | #include <linux/module.h> | |
10 | #include <linux/skbuff.h> | |
a8c2190e | 11 | #include <linux/inet_diag.h> |
87270762 SH |
12 | #include <net/tcp.h> |
13 | ||
14 | /* TCP Westwood structure */ | |
15 | struct westwood { | |
16 | u32 bw_ns_est; /* first bandwidth estimation..not too smoothed 8) */ | |
17 | u32 bw_est; /* bandwidth estimate */ | |
18 | u32 rtt_win_sx; /* here starts a new evaluation... */ | |
19 | u32 bk; | |
20 | u32 snd_una; /* used for evaluating the number of acked bytes */ | |
21 | u32 cumul_ack; | |
22 | u32 accounted; | |
23 | u32 rtt; | |
24 | u32 rtt_min; /* minimum observed RTT */ | |
25 | }; | |
26 | ||
27 | ||
28 | /* TCP Westwood functions and constants */ | |
29 | #define TCP_WESTWOOD_RTT_MIN (HZ/20) /* 50ms */ | |
30 | #define TCP_WESTWOOD_INIT_RTT (20*HZ) /* maybe too conservative?! */ | |
31 | ||
32 | /* | |
33 | * @tcp_westwood_create | |
34 | * This function initializes fields used in TCP Westwood+, | |
35 | * it is called after the initial SYN, so the sequence numbers | |
36 | * are correct but new passive connections we have no | |
37 | * information about RTTmin at this time so we simply set it to | |
38 | * TCP_WESTWOOD_INIT_RTT. This value was chosen to be too conservative | |
39 | * since in this way we're sure it will be updated in a consistent | |
40 | * way as soon as possible. It will reasonably happen within the first | |
41 | * RTT period of the connection lifetime. | |
42 | */ | |
6687e988 | 43 | static void tcp_westwood_init(struct sock *sk) |
87270762 | 44 | { |
6687e988 | 45 | struct westwood *w = inet_csk_ca(sk); |
87270762 SH |
46 | |
47 | w->bk = 0; | |
48 | w->bw_ns_est = 0; | |
49 | w->bw_est = 0; | |
50 | w->accounted = 0; | |
51 | w->cumul_ack = 0; | |
52 | w->rtt_min = w->rtt = TCP_WESTWOOD_INIT_RTT; | |
53 | w->rtt_win_sx = tcp_time_stamp; | |
6687e988 | 54 | w->snd_una = tcp_sk(sk)->snd_una; |
87270762 SH |
55 | } |
56 | ||
57 | /* | |
58 | * @westwood_do_filter | |
59 | * Low-pass filter. Implemented using constant coefficients. | |
60 | */ | |
61 | static inline u32 westwood_do_filter(u32 a, u32 b) | |
62 | { | |
63 | return (((7 * a) + b) >> 3); | |
64 | } | |
65 | ||
66 | static inline void westwood_filter(struct westwood *w, u32 delta) | |
67 | { | |
68 | w->bw_ns_est = westwood_do_filter(w->bw_ns_est, w->bk / delta); | |
69 | w->bw_est = westwood_do_filter(w->bw_est, w->bw_ns_est); | |
70 | } | |
71 | ||
72 | /* | |
73 | * @westwood_pkts_acked | |
74 | * Called after processing group of packets. | |
75 | * but all westwood needs is the last sample of srtt. | |
76 | */ | |
6687e988 | 77 | static void tcp_westwood_pkts_acked(struct sock *sk, u32 cnt) |
87270762 | 78 | { |
6687e988 | 79 | struct westwood *w = inet_csk_ca(sk); |
87270762 | 80 | if (cnt > 0) |
6687e988 | 81 | w->rtt = tcp_sk(sk)->srtt >> 3; |
87270762 SH |
82 | } |
83 | ||
84 | /* | |
85 | * @westwood_update_window | |
86 | * It updates RTT evaluation window if it is the right moment to do | |
87 | * it. If so it calls filter for evaluating bandwidth. | |
88 | */ | |
6687e988 | 89 | static void westwood_update_window(struct sock *sk) |
87270762 | 90 | { |
6687e988 | 91 | struct westwood *w = inet_csk_ca(sk); |
87270762 SH |
92 | s32 delta = tcp_time_stamp - w->rtt_win_sx; |
93 | ||
94 | /* | |
95 | * See if a RTT-window has passed. | |
96 | * Be careful since if RTT is less than | |
97 | * 50ms we don't filter but we continue 'building the sample'. | |
98 | * This minimum limit was chosen since an estimation on small | |
99 | * time intervals is better to avoid... | |
100 | * Obviously on a LAN we reasonably will always have | |
101 | * right_bound = left_bound + WESTWOOD_RTT_MIN | |
102 | */ | |
103 | if (w->rtt && delta > max_t(u32, w->rtt, TCP_WESTWOOD_RTT_MIN)) { | |
104 | westwood_filter(w, delta); | |
105 | ||
106 | w->bk = 0; | |
107 | w->rtt_win_sx = tcp_time_stamp; | |
108 | } | |
109 | } | |
110 | ||
111 | /* | |
112 | * @westwood_fast_bw | |
113 | * It is called when we are in fast path. In particular it is called when | |
114 | * header prediction is successful. In such case in fact update is | |
115 | * straight forward and doesn't need any particular care. | |
116 | */ | |
6687e988 | 117 | static inline void westwood_fast_bw(struct sock *sk) |
87270762 | 118 | { |
6687e988 ACM |
119 | const struct tcp_sock *tp = tcp_sk(sk); |
120 | struct westwood *w = inet_csk_ca(sk); | |
87270762 | 121 | |
6687e988 | 122 | westwood_update_window(sk); |
87270762 SH |
123 | |
124 | w->bk += tp->snd_una - w->snd_una; | |
125 | w->snd_una = tp->snd_una; | |
126 | w->rtt_min = min(w->rtt, w->rtt_min); | |
127 | } | |
128 | ||
129 | /* | |
130 | * @westwood_acked_count | |
131 | * This function evaluates cumul_ack for evaluating bk in case of | |
132 | * delayed or partial acks. | |
133 | */ | |
6687e988 | 134 | static inline u32 westwood_acked_count(struct sock *sk) |
87270762 | 135 | { |
6687e988 ACM |
136 | const struct tcp_sock *tp = tcp_sk(sk); |
137 | struct westwood *w = inet_csk_ca(sk); | |
87270762 SH |
138 | |
139 | w->cumul_ack = tp->snd_una - w->snd_una; | |
140 | ||
141 | /* If cumul_ack is 0 this is a dupack since it's not moving | |
142 | * tp->snd_una. | |
143 | */ | |
144 | if (!w->cumul_ack) { | |
145 | w->accounted += tp->mss_cache; | |
146 | w->cumul_ack = tp->mss_cache; | |
147 | } | |
148 | ||
149 | if (w->cumul_ack > tp->mss_cache) { | |
150 | /* Partial or delayed ack */ | |
151 | if (w->accounted >= w->cumul_ack) { | |
152 | w->accounted -= w->cumul_ack; | |
153 | w->cumul_ack = tp->mss_cache; | |
154 | } else { | |
155 | w->cumul_ack -= w->accounted; | |
156 | w->accounted = 0; | |
157 | } | |
158 | } | |
159 | ||
160 | w->snd_una = tp->snd_una; | |
161 | ||
162 | return w->cumul_ack; | |
163 | } | |
164 | ||
87270762 SH |
165 | |
166 | /* | |
167 | * TCP Westwood | |
168 | * Here limit is evaluated as Bw estimation*RTTmin (for obtaining it | |
169 | * in packets we use mss_cache). Rttmin is guaranteed to be >= 2 | |
170 | * so avoids ever returning 0. | |
171 | */ | |
72dc5b92 | 172 | static u32 tcp_westwood_bw_rttmin(const struct sock *sk) |
87270762 | 173 | { |
72dc5b92 SH |
174 | const struct tcp_sock *tp = tcp_sk(sk); |
175 | const struct westwood *w = inet_csk_ca(sk); | |
176 | return max_t(u32, (w->bw_est * w->rtt_min) / tp->mss_cache, 2); | |
87270762 SH |
177 | } |
178 | ||
6687e988 | 179 | static void tcp_westwood_event(struct sock *sk, enum tcp_ca_event event) |
87270762 | 180 | { |
6687e988 ACM |
181 | struct tcp_sock *tp = tcp_sk(sk); |
182 | struct westwood *w = inet_csk_ca(sk); | |
87270762 SH |
183 | |
184 | switch(event) { | |
185 | case CA_EVENT_FAST_ACK: | |
6687e988 | 186 | westwood_fast_bw(sk); |
87270762 SH |
187 | break; |
188 | ||
189 | case CA_EVENT_COMPLETE_CWR: | |
72dc5b92 | 190 | tp->snd_cwnd = tp->snd_ssthresh = tcp_westwood_bw_rttmin(sk); |
87270762 SH |
191 | break; |
192 | ||
193 | case CA_EVENT_FRTO: | |
72dc5b92 | 194 | tp->snd_ssthresh = tcp_westwood_bw_rttmin(sk); |
87270762 SH |
195 | break; |
196 | ||
197 | case CA_EVENT_SLOW_ACK: | |
6687e988 ACM |
198 | westwood_update_window(sk); |
199 | w->bk += westwood_acked_count(sk); | |
87270762 SH |
200 | w->rtt_min = min(w->rtt, w->rtt_min); |
201 | break; | |
202 | ||
203 | default: | |
204 | /* don't care */ | |
205 | break; | |
206 | } | |
207 | } | |
208 | ||
209 | ||
210 | /* Extract info for Tcp socket info provided via netlink. */ | |
6687e988 | 211 | static void tcp_westwood_info(struct sock *sk, u32 ext, |
87270762 SH |
212 | struct sk_buff *skb) |
213 | { | |
6687e988 | 214 | const struct westwood *ca = inet_csk_ca(sk); |
73c1f4a0 | 215 | if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) { |
87270762 SH |
216 | struct rtattr *rta; |
217 | struct tcpvegas_info *info; | |
218 | ||
73c1f4a0 | 219 | rta = __RTA_PUT(skb, INET_DIAG_VEGASINFO, sizeof(*info)); |
87270762 SH |
220 | info = RTA_DATA(rta); |
221 | info->tcpv_enabled = 1; | |
222 | info->tcpv_rttcnt = 0; | |
223 | info->tcpv_rtt = jiffies_to_usecs(ca->rtt); | |
224 | info->tcpv_minrtt = jiffies_to_usecs(ca->rtt_min); | |
225 | rtattr_failure: ; | |
226 | } | |
227 | } | |
228 | ||
229 | ||
230 | static struct tcp_congestion_ops tcp_westwood = { | |
231 | .init = tcp_westwood_init, | |
232 | .ssthresh = tcp_reno_ssthresh, | |
233 | .cong_avoid = tcp_reno_cong_avoid, | |
72dc5b92 | 234 | .min_cwnd = tcp_westwood_bw_rttmin, |
87270762 SH |
235 | .cwnd_event = tcp_westwood_event, |
236 | .get_info = tcp_westwood_info, | |
237 | .pkts_acked = tcp_westwood_pkts_acked, | |
238 | ||
239 | .owner = THIS_MODULE, | |
240 | .name = "westwood" | |
241 | }; | |
242 | ||
243 | static int __init tcp_westwood_register(void) | |
244 | { | |
6687e988 | 245 | BUG_ON(sizeof(struct westwood) > ICSK_CA_PRIV_SIZE); |
87270762 SH |
246 | return tcp_register_congestion_control(&tcp_westwood); |
247 | } | |
248 | ||
249 | static void __exit tcp_westwood_unregister(void) | |
250 | { | |
251 | tcp_unregister_congestion_control(&tcp_westwood); | |
252 | } | |
253 | ||
254 | module_init(tcp_westwood_register); | |
255 | module_exit(tcp_westwood_unregister); | |
256 | ||
257 | MODULE_AUTHOR("Stephen Hemminger, Angelo Dell'Aera"); | |
258 | MODULE_LICENSE("GPL"); | |
259 | MODULE_DESCRIPTION("TCP Westwood+"); |