]>
Commit | Line | Data |
---|---|---|
ad018375 MN |
1 | /* |
2 | * Copyright 2002-2005, Instant802 Networks, Inc. | |
3 | * Copyright 2005, Devicescape Software, Inc. | |
4 | * Copyright 2007, Mattias Nissler <mattias.nissler@gmx.de> | |
5 | * | |
6 | * This program is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License version 2 as | |
8 | * published by the Free Software Foundation. | |
9 | */ | |
10 | ||
11 | #include <linux/netdevice.h> | |
12 | #include <linux/types.h> | |
13 | #include <linux/skbuff.h> | |
14 | ||
15 | #include <net/mac80211.h> | |
16 | #include "ieee80211_rate.h" | |
17 | ||
18 | ||
19 | /* This is an implementation of a TX rate control algorithm that uses a PID | |
20 | * controller. Given a target failed frames rate, the controller decides about | |
21 | * TX rate changes to meet the target failed frames rate. | |
22 | * | |
23 | * The controller basically computes the following: | |
24 | * | |
25 | * adj = CP * err + CI * err_avg + CD * (err - last_err) | |
26 | * | |
27 | * where | |
28 | * adj adjustment value that is used to switch TX rate (see below) | |
29 | * err current error: target vs. current failed frames percentage | |
30 | * last_err last error | |
31 | * err_avg average (i.e. poor man's integral) of recent errors | |
32 | * CP Proportional coefficient | |
33 | * CI Integral coefficient | |
34 | * CD Derivative coefficient | |
35 | * | |
36 | * CP, CI, CD are subject to careful tuning. | |
37 | * | |
38 | * The integral component uses a exponential moving average approach instead of | |
39 | * an actual sliding window. The advantage is that we don't need to keep an | |
40 | * array of the last N error values and computation is easier. | |
41 | * | |
42 | * Once we have the adj value, we need to map it to a TX rate to be selected. | |
43 | * For now, we depend on the rates to be ordered in a way such that more robust | |
44 | * rates (i.e. such that exhibit a lower framed failed percentage) come first. | |
45 | * E.g. for the 802.11b/g case, we first have the b rates in ascending order, | |
46 | * then the g rates. The adj simply decides the index of the TX rate in the list | |
47 | * to switch to (relative to the current TX rate entry). | |
48 | * | |
49 | * Note that for the computations we use a fixed-point representation to avoid | |
50 | * floating point arithmetic. Hence, all values are shifted left by | |
51 | * RC_PID_ARITH_SHIFT. | |
52 | */ | |
53 | ||
54 | /* Sampling period for measuring percentage of failed frames. */ | |
55 | #define RC_PID_INTERVAL (HZ / 8) | |
56 | ||
57 | /* Exponential averaging smoothness (used for I part of PID controller) */ | |
58 | #define RC_PID_SMOOTHING_SHIFT 3 | |
59 | #define RC_PID_SMOOTHING (1 << RC_PID_SMOOTHING_SHIFT) | |
60 | ||
61 | /* Fixed point arithmetic shifting amount. */ | |
62 | #define RC_PID_ARITH_SHIFT 8 | |
63 | ||
64 | /* Fixed point arithmetic factor. */ | |
65 | #define RC_PID_ARITH_FACTOR (1 << RC_PID_ARITH_SHIFT) | |
66 | ||
67 | /* Proportional PID component coefficient. */ | |
68 | #define RC_PID_COEFF_P 15 | |
69 | /* Integral PID component coefficient. */ | |
70 | #define RC_PID_COEFF_I 9 | |
71 | /* Derivative PID component coefficient. */ | |
72 | #define RC_PID_COEFF_D 15 | |
73 | ||
74 | /* Target failed frames rate for the PID controller. NB: This effectively gives | |
75 | * maximum failed frames percentage we're willing to accept. If the wireless | |
76 | * link quality is good, the controller will fail to adjust failed frames | |
77 | * percentage to the target. This is intentional. | |
78 | */ | |
79 | #define RC_PID_TARGET_PF (11 << RC_PID_ARITH_SHIFT) | |
80 | ||
81 | struct rc_pid_sta_info { | |
82 | unsigned long last_change; | |
83 | unsigned long last_sample; | |
84 | ||
85 | u32 tx_num_failed; | |
86 | u32 tx_num_xmit; | |
87 | ||
88 | /* Average failed frames percentage error (i.e. actual vs. target | |
89 | * percentage), scaled by RC_PID_SMOOTHING. This value is computed | |
90 | * using using an exponential weighted average technique: | |
91 | * | |
92 | * (RC_PID_SMOOTHING - 1) * err_avg_old + err | |
93 | * err_avg = ------------------------------------------ | |
94 | * RC_PID_SMOOTHING | |
95 | * | |
96 | * where err_avg is the new approximation, err_avg_old the previous one | |
97 | * and err is the error w.r.t. to the current failed frames percentage | |
98 | * sample. Note that the bigger RC_PID_SMOOTHING the more weight is | |
99 | * given to the previous estimate, resulting in smoother behavior (i.e. | |
100 | * corresponding to a longer integration window). | |
101 | * | |
102 | * For computation, we actually don't use the above formula, but this | |
103 | * one: | |
104 | * | |
105 | * err_avg_scaled = err_avg_old_scaled - err_avg_old + err | |
106 | * | |
107 | * where: | |
108 | * err_avg_scaled = err * RC_PID_SMOOTHING | |
109 | * err_avg_old_scaled = err_avg_old * RC_PID_SMOOTHING | |
110 | * | |
111 | * This avoids floating point numbers and the per_failed_old value can | |
112 | * easily be obtained by shifting per_failed_old_scaled right by | |
113 | * RC_PID_SMOOTHING_SHIFT. | |
114 | */ | |
115 | s32 err_avg_sc; | |
116 | ||
117 | /* Last framed failes percentage sample */ | |
118 | u32 last_pf; | |
119 | }; | |
120 | ||
121 | /* Algorithm parameters. We keep them on a per-algorithm approach, so they can | |
122 | * be tuned individually for each interface. | |
123 | */ | |
124 | struct rc_pid_info { | |
125 | ||
126 | /* The failed frames percentage target. */ | |
127 | u32 target; | |
128 | ||
129 | /* P, I and D coefficients. */ | |
130 | s32 coeff_p; | |
131 | s32 coeff_i; | |
132 | s32 coeff_d; | |
133 | }; | |
134 | ||
135 | ||
136 | static void rate_control_pid_adjust_rate(struct ieee80211_local *local, | |
137 | struct sta_info *sta, int adj) | |
138 | { | |
139 | struct ieee80211_sub_if_data *sdata; | |
140 | struct ieee80211_hw_mode *mode; | |
141 | int newidx = sta->txrate + adj; | |
142 | int maxrate; | |
143 | int back = (adj > 0) ? 1 : -1; | |
144 | ||
145 | sdata = IEEE80211_DEV_TO_SUB_IF(sta->dev); | |
146 | if (sdata->bss && sdata->bss->force_unicast_rateidx > -1) { | |
147 | /* forced unicast rate - do not change STA rate */ | |
148 | return; | |
149 | } | |
150 | ||
151 | mode = local->oper_hw_mode; | |
152 | maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1; | |
153 | ||
154 | if (newidx < 0) | |
155 | newidx = 0; | |
156 | else if (newidx >= mode->num_rates) | |
157 | newidx = mode->num_rates - 1; | |
158 | ||
159 | while (newidx != sta->txrate) { | |
160 | if (rate_supported(sta, mode, newidx) && | |
161 | (maxrate < 0 || newidx <= maxrate)) { | |
162 | sta->txrate = newidx; | |
163 | break; | |
164 | } | |
165 | ||
166 | newidx += back; | |
167 | } | |
168 | } | |
169 | ||
170 | static void rate_control_pid_sample(struct rc_pid_info *pinfo, | |
171 | struct ieee80211_local *local, | |
172 | struct sta_info *sta) | |
173 | { | |
174 | struct rc_pid_sta_info *spinfo = sta->rate_ctrl_priv; | |
175 | u32 pf; | |
176 | s32 err_avg; | |
177 | s32 err_prop; | |
178 | s32 err_int; | |
179 | s32 err_der; | |
180 | int adj; | |
181 | ||
182 | spinfo = sta->rate_ctrl_priv; | |
183 | spinfo->last_sample = jiffies; | |
184 | ||
185 | /* If no frames were transmitted, we assume the old sample is | |
186 | * still a good measurement and copy it. */ | |
187 | if (spinfo->tx_num_xmit == 0) | |
188 | pf = spinfo->last_pf; | |
189 | else { | |
190 | pf = spinfo->tx_num_failed * 100 / spinfo->tx_num_xmit; | |
191 | pf <<= RC_PID_ARITH_SHIFT; | |
192 | ||
193 | spinfo->tx_num_xmit = 0; | |
194 | spinfo->tx_num_failed = 0; | |
195 | } | |
196 | ||
197 | /* Compute the proportional, integral and derivative errors. */ | |
198 | err_prop = RC_PID_TARGET_PF - pf; | |
199 | ||
200 | err_avg = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT; | |
201 | spinfo->err_avg_sc = spinfo->err_avg_sc - err_avg + err_prop; | |
202 | err_int = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT; | |
203 | ||
204 | err_der = pf - spinfo->last_pf; | |
205 | spinfo->last_pf = pf; | |
206 | ||
207 | /* Compute the controller output. */ | |
208 | adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i | |
209 | + err_der * pinfo->coeff_d); | |
210 | ||
211 | /* We need to do an arithmetic right shift. ISO C says this is | |
212 | * implementation defined for negative left operands. Hence, be | |
213 | * careful to get it right, also for negative values. */ | |
214 | adj = (adj < 0) ? -((-adj) >> (2 * RC_PID_ARITH_SHIFT)) : | |
215 | adj >> (2 * RC_PID_ARITH_SHIFT); | |
216 | ||
217 | /* Change rate. */ | |
218 | if (adj) | |
219 | rate_control_pid_adjust_rate(local, sta, adj); | |
220 | } | |
221 | ||
222 | static void rate_control_pid_tx_status(void *priv, struct net_device *dev, | |
223 | struct sk_buff *skb, | |
224 | struct ieee80211_tx_status *status) | |
225 | { | |
226 | struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr); | |
227 | struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data; | |
228 | struct rc_pid_info *pinfo = priv; | |
229 | struct sta_info *sta; | |
230 | struct rc_pid_sta_info *spinfo; | |
231 | ||
232 | sta = sta_info_get(local, hdr->addr1); | |
233 | ||
234 | if (!sta) | |
235 | return; | |
236 | ||
237 | /* Ignore all frames that were sent with a different rate than the rate | |
238 | * we currently advise mac80211 to use. */ | |
239 | if (status->control.rate != &local->oper_hw_mode->rates[sta->txrate]) | |
240 | return; | |
241 | ||
242 | spinfo = sta->rate_ctrl_priv; | |
243 | spinfo->tx_num_xmit++; | |
244 | ||
245 | /* We count frames that totally failed to be transmitted as two bad | |
246 | * frames, those that made it out but had some retries as one good and | |
247 | * one bad frame. */ | |
248 | if (status->excessive_retries) { | |
249 | spinfo->tx_num_failed += 2; | |
250 | spinfo->tx_num_xmit++; | |
251 | } else if (status->retry_count) { | |
252 | spinfo->tx_num_failed++; | |
253 | spinfo->tx_num_xmit++; | |
254 | } | |
255 | ||
256 | if (status->excessive_retries) { | |
257 | sta->tx_retry_failed++; | |
258 | sta->tx_num_consecutive_failures++; | |
259 | sta->tx_num_mpdu_fail++; | |
260 | } else { | |
261 | sta->last_ack_rssi[0] = sta->last_ack_rssi[1]; | |
262 | sta->last_ack_rssi[1] = sta->last_ack_rssi[2]; | |
263 | sta->last_ack_rssi[2] = status->ack_signal; | |
264 | sta->tx_num_consecutive_failures = 0; | |
265 | sta->tx_num_mpdu_ok++; | |
266 | } | |
267 | sta->tx_retry_count += status->retry_count; | |
268 | sta->tx_num_mpdu_fail += status->retry_count; | |
269 | ||
270 | /* Update PID controller state. */ | |
271 | if (time_after(jiffies, spinfo->last_sample + RC_PID_INTERVAL)) | |
272 | rate_control_pid_sample(pinfo, local, sta); | |
273 | ||
274 | sta_info_put(sta); | |
275 | } | |
276 | ||
277 | static void rate_control_pid_get_rate(void *priv, struct net_device *dev, | |
278 | struct ieee80211_hw_mode *mode, | |
279 | struct sk_buff *skb, | |
280 | struct rate_selection *sel) | |
281 | { | |
282 | struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr); | |
283 | struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data; | |
284 | struct sta_info *sta; | |
285 | int rateidx; | |
286 | ||
287 | sta = sta_info_get(local, hdr->addr1); | |
288 | ||
289 | if (!sta) { | |
290 | sel->rate = rate_lowest(local, mode, NULL); | |
291 | sta_info_put(sta); | |
292 | return; | |
293 | } | |
294 | ||
295 | rateidx = sta->txrate; | |
296 | ||
297 | if (rateidx >= mode->num_rates) | |
298 | rateidx = mode->num_rates - 1; | |
299 | ||
300 | sta_info_put(sta); | |
301 | ||
302 | sel->rate = &mode->rates[rateidx]; | |
303 | } | |
304 | ||
305 | static void rate_control_pid_rate_init(void *priv, void *priv_sta, | |
306 | struct ieee80211_local *local, | |
307 | struct sta_info *sta) | |
308 | { | |
309 | /* TODO: This routine should consider using RSSI from previous packets | |
310 | * as we need to have IEEE 802.1X auth succeed immediately after assoc.. | |
311 | * Until that method is implemented, we will use the lowest supported | |
312 | * rate as a workaround. */ | |
313 | sta->txrate = rate_lowest_index(local, local->oper_hw_mode, sta); | |
314 | } | |
315 | ||
316 | static void *rate_control_pid_alloc(struct ieee80211_local *local) | |
317 | { | |
318 | struct rc_pid_info *pinfo; | |
319 | ||
320 | pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC); | |
321 | ||
322 | pinfo->target = RC_PID_TARGET_PF; | |
323 | pinfo->coeff_p = RC_PID_COEFF_P; | |
324 | pinfo->coeff_i = RC_PID_COEFF_I; | |
325 | pinfo->coeff_d = RC_PID_COEFF_D; | |
326 | ||
327 | return pinfo; | |
328 | } | |
329 | ||
330 | static void rate_control_pid_free(void *priv) | |
331 | { | |
332 | struct rc_pid_info *pinfo = priv; | |
333 | kfree(pinfo); | |
334 | } | |
335 | ||
336 | static void rate_control_pid_clear(void *priv) | |
337 | { | |
338 | } | |
339 | ||
340 | static void *rate_control_pid_alloc_sta(void *priv, gfp_t gfp) | |
341 | { | |
342 | struct rc_pid_sta_info *spinfo; | |
343 | ||
344 | spinfo = kzalloc(sizeof(*spinfo), gfp); | |
345 | ||
346 | return spinfo; | |
347 | } | |
348 | ||
349 | static void rate_control_pid_free_sta(void *priv, void *priv_sta) | |
350 | { | |
351 | struct rc_pid_sta_info *spinfo = priv_sta; | |
352 | kfree(spinfo); | |
353 | } | |
354 | ||
355 | struct rate_control_ops mac80211_rcpid = { | |
356 | .name = "pid", | |
357 | .tx_status = rate_control_pid_tx_status, | |
358 | .get_rate = rate_control_pid_get_rate, | |
359 | .rate_init = rate_control_pid_rate_init, | |
360 | .clear = rate_control_pid_clear, | |
361 | .alloc = rate_control_pid_alloc, | |
362 | .free = rate_control_pid_free, | |
363 | .alloc_sta = rate_control_pid_alloc_sta, | |
364 | .free_sta = rate_control_pid_free_sta, | |
365 | }; |