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 | ||
6687e988 | 165 | static inline u32 westwood_bw_rttmin(const struct sock *sk) |
87270762 | 166 | { |
6687e988 ACM |
167 | const struct tcp_sock *tp = tcp_sk(sk); |
168 | const struct westwood *w = inet_csk_ca(sk); | |
87270762 SH |
169 | return max_t(u32, (w->bw_est * w->rtt_min) / tp->mss_cache, 2); |
170 | } | |
171 | ||
172 | /* | |
173 | * TCP Westwood | |
174 | * Here limit is evaluated as Bw estimation*RTTmin (for obtaining it | |
175 | * in packets we use mss_cache). Rttmin is guaranteed to be >= 2 | |
176 | * so avoids ever returning 0. | |
177 | */ | |
6687e988 | 178 | static u32 tcp_westwood_cwnd_min(struct sock *sk) |
87270762 | 179 | { |
6687e988 | 180 | return westwood_bw_rttmin(sk); |
87270762 SH |
181 | } |
182 | ||
6687e988 | 183 | static void tcp_westwood_event(struct sock *sk, enum tcp_ca_event event) |
87270762 | 184 | { |
6687e988 ACM |
185 | struct tcp_sock *tp = tcp_sk(sk); |
186 | struct westwood *w = inet_csk_ca(sk); | |
87270762 SH |
187 | |
188 | switch(event) { | |
189 | case CA_EVENT_FAST_ACK: | |
6687e988 | 190 | westwood_fast_bw(sk); |
87270762 SH |
191 | break; |
192 | ||
193 | case CA_EVENT_COMPLETE_CWR: | |
6687e988 | 194 | tp->snd_cwnd = tp->snd_ssthresh = westwood_bw_rttmin(sk); |
87270762 SH |
195 | break; |
196 | ||
197 | case CA_EVENT_FRTO: | |
6687e988 | 198 | tp->snd_ssthresh = westwood_bw_rttmin(sk); |
87270762 SH |
199 | break; |
200 | ||
201 | case CA_EVENT_SLOW_ACK: | |
6687e988 ACM |
202 | westwood_update_window(sk); |
203 | w->bk += westwood_acked_count(sk); | |
87270762 SH |
204 | w->rtt_min = min(w->rtt, w->rtt_min); |
205 | break; | |
206 | ||
207 | default: | |
208 | /* don't care */ | |
209 | break; | |
210 | } | |
211 | } | |
212 | ||
213 | ||
214 | /* Extract info for Tcp socket info provided via netlink. */ | |
6687e988 | 215 | static void tcp_westwood_info(struct sock *sk, u32 ext, |
87270762 SH |
216 | struct sk_buff *skb) |
217 | { | |
6687e988 | 218 | const struct westwood *ca = inet_csk_ca(sk); |
73c1f4a0 | 219 | if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) { |
87270762 SH |
220 | struct rtattr *rta; |
221 | struct tcpvegas_info *info; | |
222 | ||
73c1f4a0 | 223 | rta = __RTA_PUT(skb, INET_DIAG_VEGASINFO, sizeof(*info)); |
87270762 SH |
224 | info = RTA_DATA(rta); |
225 | info->tcpv_enabled = 1; | |
226 | info->tcpv_rttcnt = 0; | |
227 | info->tcpv_rtt = jiffies_to_usecs(ca->rtt); | |
228 | info->tcpv_minrtt = jiffies_to_usecs(ca->rtt_min); | |
229 | rtattr_failure: ; | |
230 | } | |
231 | } | |
232 | ||
233 | ||
234 | static struct tcp_congestion_ops tcp_westwood = { | |
235 | .init = tcp_westwood_init, | |
236 | .ssthresh = tcp_reno_ssthresh, | |
237 | .cong_avoid = tcp_reno_cong_avoid, | |
238 | .min_cwnd = tcp_westwood_cwnd_min, | |
239 | .cwnd_event = tcp_westwood_event, | |
240 | .get_info = tcp_westwood_info, | |
241 | .pkts_acked = tcp_westwood_pkts_acked, | |
242 | ||
243 | .owner = THIS_MODULE, | |
244 | .name = "westwood" | |
245 | }; | |
246 | ||
247 | static int __init tcp_westwood_register(void) | |
248 | { | |
6687e988 | 249 | BUG_ON(sizeof(struct westwood) > ICSK_CA_PRIV_SIZE); |
87270762 SH |
250 | return tcp_register_congestion_control(&tcp_westwood); |
251 | } | |
252 | ||
253 | static void __exit tcp_westwood_unregister(void) | |
254 | { | |
255 | tcp_unregister_congestion_control(&tcp_westwood); | |
256 | } | |
257 | ||
258 | module_init(tcp_westwood_register); | |
259 | module_exit(tcp_westwood_unregister); | |
260 | ||
261 | MODULE_AUTHOR("Stephen Hemminger, Angelo Dell'Aera"); | |
262 | MODULE_LICENSE("GPL"); | |
263 | MODULE_DESCRIPTION("TCP Westwood+"); |