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> | |
11 | #include <linux/tcp_diag.h> | |
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 | */ | |
43 | static void tcp_westwood_init(struct tcp_sock *tp) | |
44 | { | |
45 | struct westwood *w = tcp_ca(tp); | |
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; | |
54 | w->snd_una = tp->snd_una; | |
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 | */ | |
77 | static void tcp_westwood_pkts_acked(struct tcp_sock *tp, u32 cnt) | |
78 | { | |
79 | struct westwood *w = tcp_ca(tp); | |
80 | if (cnt > 0) | |
81 | w->rtt = tp->srtt >> 3; | |
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 | */ | |
89 | static void westwood_update_window(struct tcp_sock *tp) | |
90 | { | |
91 | struct westwood *w = tcp_ca(tp); | |
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 | */ | |
117 | static inline void westwood_fast_bw(struct tcp_sock *tp) | |
118 | { | |
119 | struct westwood *w = tcp_ca(tp); | |
120 | ||
121 | westwood_update_window(tp); | |
122 | ||
123 | w->bk += tp->snd_una - w->snd_una; | |
124 | w->snd_una = tp->snd_una; | |
125 | w->rtt_min = min(w->rtt, w->rtt_min); | |
126 | } | |
127 | ||
128 | /* | |
129 | * @westwood_acked_count | |
130 | * This function evaluates cumul_ack for evaluating bk in case of | |
131 | * delayed or partial acks. | |
132 | */ | |
133 | static inline u32 westwood_acked_count(struct tcp_sock *tp) | |
134 | { | |
135 | struct westwood *w = tcp_ca(tp); | |
136 | ||
137 | w->cumul_ack = tp->snd_una - w->snd_una; | |
138 | ||
139 | /* If cumul_ack is 0 this is a dupack since it's not moving | |
140 | * tp->snd_una. | |
141 | */ | |
142 | if (!w->cumul_ack) { | |
143 | w->accounted += tp->mss_cache; | |
144 | w->cumul_ack = tp->mss_cache; | |
145 | } | |
146 | ||
147 | if (w->cumul_ack > tp->mss_cache) { | |
148 | /* Partial or delayed ack */ | |
149 | if (w->accounted >= w->cumul_ack) { | |
150 | w->accounted -= w->cumul_ack; | |
151 | w->cumul_ack = tp->mss_cache; | |
152 | } else { | |
153 | w->cumul_ack -= w->accounted; | |
154 | w->accounted = 0; | |
155 | } | |
156 | } | |
157 | ||
158 | w->snd_una = tp->snd_una; | |
159 | ||
160 | return w->cumul_ack; | |
161 | } | |
162 | ||
163 | static inline u32 westwood_bw_rttmin(const struct tcp_sock *tp) | |
164 | { | |
165 | struct westwood *w = tcp_ca(tp); | |
166 | return max_t(u32, (w->bw_est * w->rtt_min) / tp->mss_cache, 2); | |
167 | } | |
168 | ||
169 | /* | |
170 | * TCP Westwood | |
171 | * Here limit is evaluated as Bw estimation*RTTmin (for obtaining it | |
172 | * in packets we use mss_cache). Rttmin is guaranteed to be >= 2 | |
173 | * so avoids ever returning 0. | |
174 | */ | |
175 | static u32 tcp_westwood_cwnd_min(struct tcp_sock *tp) | |
176 | { | |
177 | return westwood_bw_rttmin(tp); | |
178 | } | |
179 | ||
180 | static void tcp_westwood_event(struct tcp_sock *tp, enum tcp_ca_event event) | |
181 | { | |
182 | struct westwood *w = tcp_ca(tp); | |
183 | ||
184 | switch(event) { | |
185 | case CA_EVENT_FAST_ACK: | |
186 | westwood_fast_bw(tp); | |
187 | break; | |
188 | ||
189 | case CA_EVENT_COMPLETE_CWR: | |
190 | tp->snd_cwnd = tp->snd_ssthresh = westwood_bw_rttmin(tp); | |
191 | break; | |
192 | ||
193 | case CA_EVENT_FRTO: | |
194 | tp->snd_ssthresh = westwood_bw_rttmin(tp); | |
195 | break; | |
196 | ||
197 | case CA_EVENT_SLOW_ACK: | |
198 | westwood_update_window(tp); | |
199 | w->bk += westwood_acked_count(tp); | |
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. */ | |
211 | static void tcp_westwood_info(struct tcp_sock *tp, u32 ext, | |
212 | struct sk_buff *skb) | |
213 | { | |
214 | const struct westwood *ca = tcp_ca(tp); | |
215 | if (ext & (1<<(TCPDIAG_VEGASINFO-1))) { | |
216 | struct rtattr *rta; | |
217 | struct tcpvegas_info *info; | |
218 | ||
219 | rta = __RTA_PUT(skb, TCPDIAG_VEGASINFO, sizeof(*info)); | |
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, | |
234 | .min_cwnd = tcp_westwood_cwnd_min, | |
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 | { | |
245 | BUG_ON(sizeof(struct westwood) > TCP_CA_PRIV_SIZE); | |
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+"); |