]>
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> | |
90d501d6 | 5 | * Copyright 2007, Stefano Brivio <stefano.brivio@polimi.it> |
ad018375 MN |
6 | * |
7 | * This program is free software; you can redistribute it and/or modify | |
8 | * it under the terms of the GNU General Public License version 2 as | |
9 | * published by the Free Software Foundation. | |
10 | */ | |
11 | ||
12 | #include <linux/netdevice.h> | |
13 | #include <linux/types.h> | |
14 | #include <linux/skbuff.h> | |
15 | ||
16 | #include <net/mac80211.h> | |
17 | #include "ieee80211_rate.h" | |
18 | ||
19 | ||
20 | /* This is an implementation of a TX rate control algorithm that uses a PID | |
21 | * controller. Given a target failed frames rate, the controller decides about | |
22 | * TX rate changes to meet the target failed frames rate. | |
23 | * | |
24 | * The controller basically computes the following: | |
25 | * | |
26 | * adj = CP * err + CI * err_avg + CD * (err - last_err) | |
27 | * | |
28 | * where | |
29 | * adj adjustment value that is used to switch TX rate (see below) | |
30 | * err current error: target vs. current failed frames percentage | |
31 | * last_err last error | |
32 | * err_avg average (i.e. poor man's integral) of recent errors | |
33 | * CP Proportional coefficient | |
34 | * CI Integral coefficient | |
35 | * CD Derivative coefficient | |
36 | * | |
37 | * CP, CI, CD are subject to careful tuning. | |
38 | * | |
39 | * The integral component uses a exponential moving average approach instead of | |
40 | * an actual sliding window. The advantage is that we don't need to keep an | |
41 | * array of the last N error values and computation is easier. | |
42 | * | |
90d501d6 SB |
43 | * Once we have the adj value, we map it to a rate by means of a learning |
44 | * algorithm. This algorithm keeps the state of the percentual failed frames | |
45 | * difference between rates. The behaviour of the lowest available rate is kept | |
46 | * as a reference value, and every time we switch between two rates, we compute | |
47 | * the difference between the failed frames each rate exhibited. By doing so, | |
48 | * we compare behaviours which different rates exhibited in adjacent timeslices, | |
49 | * thus the comparison is minimally affected by external conditions. This | |
50 | * difference gets propagated to the whole set of measurements, so that the | |
51 | * reference is always the same. Periodically, we normalize this set so that | |
52 | * recent events weigh the most. By comparing the adj value with this set, we | |
53 | * avoid pejorative switches to lower rates and allow for switches to higher | |
54 | * rates if they behaved well. | |
ad018375 MN |
55 | * |
56 | * Note that for the computations we use a fixed-point representation to avoid | |
57 | * floating point arithmetic. Hence, all values are shifted left by | |
58 | * RC_PID_ARITH_SHIFT. | |
59 | */ | |
60 | ||
61 | /* Sampling period for measuring percentage of failed frames. */ | |
62 | #define RC_PID_INTERVAL (HZ / 8) | |
63 | ||
64 | /* Exponential averaging smoothness (used for I part of PID controller) */ | |
65 | #define RC_PID_SMOOTHING_SHIFT 3 | |
66 | #define RC_PID_SMOOTHING (1 << RC_PID_SMOOTHING_SHIFT) | |
67 | ||
68 | /* Fixed point arithmetic shifting amount. */ | |
69 | #define RC_PID_ARITH_SHIFT 8 | |
70 | ||
71 | /* Fixed point arithmetic factor. */ | |
72 | #define RC_PID_ARITH_FACTOR (1 << RC_PID_ARITH_SHIFT) | |
73 | ||
74 | /* Proportional PID component coefficient. */ | |
75 | #define RC_PID_COEFF_P 15 | |
76 | /* Integral PID component coefficient. */ | |
77 | #define RC_PID_COEFF_I 9 | |
78 | /* Derivative PID component coefficient. */ | |
79 | #define RC_PID_COEFF_D 15 | |
80 | ||
81 | /* Target failed frames rate for the PID controller. NB: This effectively gives | |
82 | * maximum failed frames percentage we're willing to accept. If the wireless | |
83 | * link quality is good, the controller will fail to adjust failed frames | |
84 | * percentage to the target. This is intentional. | |
85 | */ | |
86 | #define RC_PID_TARGET_PF (11 << RC_PID_ARITH_SHIFT) | |
87 | ||
90d501d6 SB |
88 | /* Rate behaviour normalization quantity over time. */ |
89 | #define RC_PID_NORM_OFFSET 3 | |
90 | ||
91 | /* Push high rates right after loading. */ | |
92 | #define RC_PID_FAST_START 0 | |
93 | ||
94 | /* Arithmetic right shift for positive and negative values for ISO C. */ | |
95 | #define RC_PID_DO_ARITH_RIGHT_SHIFT(x, y) \ | |
96 | (x) < 0 ? -((-(x)) >> (y)) : (x) >> (y) | |
97 | ||
ad018375 MN |
98 | struct rc_pid_sta_info { |
99 | unsigned long last_change; | |
100 | unsigned long last_sample; | |
101 | ||
102 | u32 tx_num_failed; | |
103 | u32 tx_num_xmit; | |
104 | ||
105 | /* Average failed frames percentage error (i.e. actual vs. target | |
106 | * percentage), scaled by RC_PID_SMOOTHING. This value is computed | |
107 | * using using an exponential weighted average technique: | |
108 | * | |
109 | * (RC_PID_SMOOTHING - 1) * err_avg_old + err | |
110 | * err_avg = ------------------------------------------ | |
111 | * RC_PID_SMOOTHING | |
112 | * | |
113 | * where err_avg is the new approximation, err_avg_old the previous one | |
114 | * and err is the error w.r.t. to the current failed frames percentage | |
115 | * sample. Note that the bigger RC_PID_SMOOTHING the more weight is | |
116 | * given to the previous estimate, resulting in smoother behavior (i.e. | |
117 | * corresponding to a longer integration window). | |
118 | * | |
119 | * For computation, we actually don't use the above formula, but this | |
120 | * one: | |
121 | * | |
122 | * err_avg_scaled = err_avg_old_scaled - err_avg_old + err | |
123 | * | |
124 | * where: | |
125 | * err_avg_scaled = err * RC_PID_SMOOTHING | |
126 | * err_avg_old_scaled = err_avg_old * RC_PID_SMOOTHING | |
127 | * | |
128 | * This avoids floating point numbers and the per_failed_old value can | |
129 | * easily be obtained by shifting per_failed_old_scaled right by | |
130 | * RC_PID_SMOOTHING_SHIFT. | |
131 | */ | |
132 | s32 err_avg_sc; | |
133 | ||
134 | /* Last framed failes percentage sample */ | |
135 | u32 last_pf; | |
136 | }; | |
137 | ||
138 | /* Algorithm parameters. We keep them on a per-algorithm approach, so they can | |
139 | * be tuned individually for each interface. | |
140 | */ | |
90d501d6 SB |
141 | struct rc_pid_rateinfo { |
142 | ||
143 | /* Map sorted rates to rates in ieee80211_hw_mode. */ | |
144 | int index; | |
145 | ||
146 | /* Map rates in ieee80211_hw_mode to sorted rates. */ | |
147 | int rev_index; | |
148 | ||
149 | /* Comparison with the lowest rate. */ | |
150 | int diff; | |
151 | }; | |
152 | ||
ad018375 MN |
153 | struct rc_pid_info { |
154 | ||
155 | /* The failed frames percentage target. */ | |
156 | u32 target; | |
157 | ||
158 | /* P, I and D coefficients. */ | |
159 | s32 coeff_p; | |
160 | s32 coeff_i; | |
161 | s32 coeff_d; | |
90d501d6 SB |
162 | |
163 | /* Rates information. */ | |
164 | struct rc_pid_rateinfo *rinfo; | |
165 | ||
166 | /* Index of the last used rate. */ | |
167 | int oldrate; | |
ad018375 MN |
168 | }; |
169 | ||
90d501d6 SB |
170 | /* Shift the adjustment so that we won't switch to a lower rate if it exhibited |
171 | * a worse failed frames behaviour and we'll choose the highest rate whose | |
172 | * failed frames behaviour is not worse than the one of the original rate | |
173 | * target. While at it, check that the adjustment is within the ranges. Then, | |
174 | * provide the new rate index. */ | |
175 | static int rate_control_pid_shift_adjust(struct rc_pid_rateinfo *r, | |
176 | int adj, int cur, int l) | |
177 | { | |
178 | int i, j, k, tmp; | |
179 | ||
180 | if (cur + adj < 0) | |
181 | return 0; | |
182 | if (cur + adj >= l) | |
183 | return l - 1; | |
184 | ||
185 | i = r[cur + adj].rev_index; | |
186 | ||
187 | j = r[cur].rev_index; | |
188 | ||
189 | if (adj < 0) { | |
190 | tmp = i; | |
191 | for (k = j; k >= i; k--) | |
192 | if (r[k].diff <= r[j].diff) | |
193 | tmp = k; | |
194 | return r[tmp].index; | |
195 | } else if (adj > 0) { | |
196 | tmp = i; | |
197 | for (k = i + 1; k + i < l; k++) | |
198 | if (r[k].diff <= r[i].diff) | |
199 | tmp = k; | |
200 | return r[tmp].index; | |
201 | } | |
202 | return cur + adj; | |
203 | } | |
ad018375 MN |
204 | |
205 | static void rate_control_pid_adjust_rate(struct ieee80211_local *local, | |
90d501d6 SB |
206 | struct sta_info *sta, int adj, |
207 | struct rc_pid_rateinfo *rinfo) | |
ad018375 MN |
208 | { |
209 | struct ieee80211_sub_if_data *sdata; | |
210 | struct ieee80211_hw_mode *mode; | |
90d501d6 | 211 | int newidx; |
ad018375 MN |
212 | int maxrate; |
213 | int back = (adj > 0) ? 1 : -1; | |
214 | ||
215 | sdata = IEEE80211_DEV_TO_SUB_IF(sta->dev); | |
216 | if (sdata->bss && sdata->bss->force_unicast_rateidx > -1) { | |
217 | /* forced unicast rate - do not change STA rate */ | |
218 | return; | |
219 | } | |
220 | ||
221 | mode = local->oper_hw_mode; | |
222 | maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1; | |
223 | ||
90d501d6 SB |
224 | newidx = rate_control_pid_shift_adjust(rinfo, adj, sta->txrate, |
225 | mode->num_rates); | |
ad018375 MN |
226 | |
227 | while (newidx != sta->txrate) { | |
228 | if (rate_supported(sta, mode, newidx) && | |
229 | (maxrate < 0 || newidx <= maxrate)) { | |
230 | sta->txrate = newidx; | |
231 | break; | |
232 | } | |
233 | ||
234 | newidx += back; | |
235 | } | |
236 | } | |
237 | ||
90d501d6 SB |
238 | /* Normalize the failed frames per-rate differences. */ |
239 | static void rate_control_pid_normalize(struct rc_pid_rateinfo *r, int l) | |
240 | { | |
241 | int i; | |
242 | ||
243 | if (r[0].diff > RC_PID_NORM_OFFSET) | |
244 | r[0].diff -= RC_PID_NORM_OFFSET; | |
245 | else if (r[0].diff < -RC_PID_NORM_OFFSET) | |
246 | r[0].diff += RC_PID_NORM_OFFSET; | |
247 | for (i = 0; i < l - 1; i++) | |
248 | if (r[i + 1].diff > r[i].diff + RC_PID_NORM_OFFSET) | |
249 | r[i + 1].diff -= RC_PID_NORM_OFFSET; | |
250 | else if (r[i + 1].diff <= r[i].diff) | |
251 | r[i + 1].diff += RC_PID_NORM_OFFSET; | |
252 | } | |
253 | ||
ad018375 MN |
254 | static void rate_control_pid_sample(struct rc_pid_info *pinfo, |
255 | struct ieee80211_local *local, | |
256 | struct sta_info *sta) | |
257 | { | |
258 | struct rc_pid_sta_info *spinfo = sta->rate_ctrl_priv; | |
90d501d6 SB |
259 | struct rc_pid_rateinfo *rinfo = pinfo->rinfo; |
260 | struct ieee80211_hw_mode *mode; | |
ad018375 MN |
261 | u32 pf; |
262 | s32 err_avg; | |
263 | s32 err_prop; | |
264 | s32 err_int; | |
265 | s32 err_der; | |
90d501d6 | 266 | int adj, i, j, tmp; |
ad018375 | 267 | |
90d501d6 | 268 | mode = local->oper_hw_mode; |
ad018375 MN |
269 | spinfo = sta->rate_ctrl_priv; |
270 | spinfo->last_sample = jiffies; | |
271 | ||
272 | /* If no frames were transmitted, we assume the old sample is | |
273 | * still a good measurement and copy it. */ | |
274 | if (spinfo->tx_num_xmit == 0) | |
275 | pf = spinfo->last_pf; | |
276 | else { | |
277 | pf = spinfo->tx_num_failed * 100 / spinfo->tx_num_xmit; | |
278 | pf <<= RC_PID_ARITH_SHIFT; | |
279 | ||
280 | spinfo->tx_num_xmit = 0; | |
281 | spinfo->tx_num_failed = 0; | |
282 | } | |
283 | ||
90d501d6 SB |
284 | /* If we just switched rate, update the rate behaviour info. */ |
285 | if (pinfo->oldrate != sta->txrate) { | |
286 | ||
287 | i = rinfo[pinfo->oldrate].rev_index; | |
288 | j = rinfo[sta->txrate].rev_index; | |
289 | ||
290 | tmp = (pf - spinfo->last_pf); | |
291 | tmp = RC_PID_DO_ARITH_RIGHT_SHIFT(tmp, RC_PID_ARITH_SHIFT); | |
292 | ||
293 | rinfo[j].diff = rinfo[i].diff + tmp; | |
294 | pinfo->oldrate = sta->txrate; | |
295 | } | |
296 | rate_control_pid_normalize(rinfo, mode->num_rates); | |
297 | ||
ad018375 MN |
298 | /* Compute the proportional, integral and derivative errors. */ |
299 | err_prop = RC_PID_TARGET_PF - pf; | |
300 | ||
301 | err_avg = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT; | |
302 | spinfo->err_avg_sc = spinfo->err_avg_sc - err_avg + err_prop; | |
303 | err_int = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT; | |
304 | ||
305 | err_der = pf - spinfo->last_pf; | |
306 | spinfo->last_pf = pf; | |
307 | ||
308 | /* Compute the controller output. */ | |
309 | adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i | |
310 | + err_der * pinfo->coeff_d); | |
90d501d6 | 311 | adj = RC_PID_DO_ARITH_RIGHT_SHIFT(adj, 2 * RC_PID_ARITH_SHIFT); |
ad018375 MN |
312 | |
313 | /* Change rate. */ | |
314 | if (adj) | |
90d501d6 | 315 | rate_control_pid_adjust_rate(local, sta, adj, rinfo); |
ad018375 MN |
316 | } |
317 | ||
318 | static void rate_control_pid_tx_status(void *priv, struct net_device *dev, | |
319 | struct sk_buff *skb, | |
320 | struct ieee80211_tx_status *status) | |
321 | { | |
322 | struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr); | |
323 | struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data; | |
324 | struct rc_pid_info *pinfo = priv; | |
325 | struct sta_info *sta; | |
326 | struct rc_pid_sta_info *spinfo; | |
327 | ||
328 | sta = sta_info_get(local, hdr->addr1); | |
329 | ||
330 | if (!sta) | |
331 | return; | |
332 | ||
333 | /* Ignore all frames that were sent with a different rate than the rate | |
334 | * we currently advise mac80211 to use. */ | |
335 | if (status->control.rate != &local->oper_hw_mode->rates[sta->txrate]) | |
336 | return; | |
337 | ||
338 | spinfo = sta->rate_ctrl_priv; | |
339 | spinfo->tx_num_xmit++; | |
340 | ||
341 | /* We count frames that totally failed to be transmitted as two bad | |
342 | * frames, those that made it out but had some retries as one good and | |
343 | * one bad frame. */ | |
344 | if (status->excessive_retries) { | |
345 | spinfo->tx_num_failed += 2; | |
346 | spinfo->tx_num_xmit++; | |
347 | } else if (status->retry_count) { | |
348 | spinfo->tx_num_failed++; | |
349 | spinfo->tx_num_xmit++; | |
350 | } | |
351 | ||
352 | if (status->excessive_retries) { | |
353 | sta->tx_retry_failed++; | |
354 | sta->tx_num_consecutive_failures++; | |
355 | sta->tx_num_mpdu_fail++; | |
356 | } else { | |
357 | sta->last_ack_rssi[0] = sta->last_ack_rssi[1]; | |
358 | sta->last_ack_rssi[1] = sta->last_ack_rssi[2]; | |
359 | sta->last_ack_rssi[2] = status->ack_signal; | |
360 | sta->tx_num_consecutive_failures = 0; | |
361 | sta->tx_num_mpdu_ok++; | |
362 | } | |
363 | sta->tx_retry_count += status->retry_count; | |
364 | sta->tx_num_mpdu_fail += status->retry_count; | |
365 | ||
366 | /* Update PID controller state. */ | |
367 | if (time_after(jiffies, spinfo->last_sample + RC_PID_INTERVAL)) | |
368 | rate_control_pid_sample(pinfo, local, sta); | |
369 | ||
370 | sta_info_put(sta); | |
371 | } | |
372 | ||
373 | static void rate_control_pid_get_rate(void *priv, struct net_device *dev, | |
374 | struct ieee80211_hw_mode *mode, | |
375 | struct sk_buff *skb, | |
376 | struct rate_selection *sel) | |
377 | { | |
378 | struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr); | |
379 | struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data; | |
380 | struct sta_info *sta; | |
381 | int rateidx; | |
382 | ||
383 | sta = sta_info_get(local, hdr->addr1); | |
384 | ||
385 | if (!sta) { | |
386 | sel->rate = rate_lowest(local, mode, NULL); | |
387 | sta_info_put(sta); | |
388 | return; | |
389 | } | |
390 | ||
391 | rateidx = sta->txrate; | |
392 | ||
393 | if (rateidx >= mode->num_rates) | |
394 | rateidx = mode->num_rates - 1; | |
395 | ||
396 | sta_info_put(sta); | |
397 | ||
398 | sel->rate = &mode->rates[rateidx]; | |
399 | } | |
400 | ||
401 | static void rate_control_pid_rate_init(void *priv, void *priv_sta, | |
402 | struct ieee80211_local *local, | |
403 | struct sta_info *sta) | |
404 | { | |
405 | /* TODO: This routine should consider using RSSI from previous packets | |
406 | * as we need to have IEEE 802.1X auth succeed immediately after assoc.. | |
407 | * Until that method is implemented, we will use the lowest supported | |
408 | * rate as a workaround. */ | |
409 | sta->txrate = rate_lowest_index(local, local->oper_hw_mode, sta); | |
410 | } | |
411 | ||
412 | static void *rate_control_pid_alloc(struct ieee80211_local *local) | |
413 | { | |
414 | struct rc_pid_info *pinfo; | |
90d501d6 SB |
415 | struct rc_pid_rateinfo *rinfo; |
416 | struct ieee80211_hw_mode *mode; | |
417 | int i, j, tmp; | |
418 | bool s; | |
ad018375 MN |
419 | |
420 | pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC); | |
90d501d6 SB |
421 | if (!pinfo) |
422 | return NULL; | |
423 | ||
424 | /* We can safely assume that oper_hw_mode won't change unless we get | |
425 | * reinitialized. */ | |
426 | mode = local->oper_hw_mode; | |
427 | rinfo = kmalloc(sizeof(*rinfo) * mode->num_rates, GFP_ATOMIC); | |
428 | if (!rinfo) { | |
429 | kfree(pinfo); | |
430 | return NULL; | |
431 | } | |
432 | ||
433 | /* Sort the rates. This is optimized for the most common case (i.e. | |
434 | * almost-sorted CCK+OFDM rates). Kind of bubble-sort with reversed | |
435 | * mapping too. */ | |
436 | for (i = 0; i < mode->num_rates; i++) { | |
437 | rinfo[i].index = i; | |
438 | rinfo[i].rev_index = i; | |
439 | if (RC_PID_FAST_START) | |
440 | rinfo[i].diff = 0; | |
441 | else | |
442 | rinfo[i].diff = i * RC_PID_NORM_OFFSET; | |
443 | } | |
444 | for (i = 1; i < mode->num_rates; i++) { | |
445 | s = 0; | |
446 | for (j = 0; j < mode->num_rates - i; j++) | |
447 | if (unlikely(mode->rates[rinfo[j].index].rate > | |
448 | mode->rates[rinfo[j + 1].index].rate)) { | |
449 | tmp = rinfo[j].index; | |
450 | rinfo[j].index = rinfo[j + 1].index; | |
451 | rinfo[j + 1].index = tmp; | |
452 | rinfo[rinfo[j].index].rev_index = j; | |
453 | rinfo[rinfo[j + 1].index].rev_index = j + 1; | |
454 | s = 1; | |
455 | } | |
456 | if (!s) | |
457 | break; | |
458 | } | |
ad018375 MN |
459 | |
460 | pinfo->target = RC_PID_TARGET_PF; | |
461 | pinfo->coeff_p = RC_PID_COEFF_P; | |
462 | pinfo->coeff_i = RC_PID_COEFF_I; | |
463 | pinfo->coeff_d = RC_PID_COEFF_D; | |
90d501d6 SB |
464 | pinfo->rinfo = rinfo; |
465 | pinfo->oldrate = 0; | |
ad018375 MN |
466 | |
467 | return pinfo; | |
468 | } | |
469 | ||
470 | static void rate_control_pid_free(void *priv) | |
471 | { | |
472 | struct rc_pid_info *pinfo = priv; | |
90d501d6 | 473 | kfree(pinfo->rinfo); |
ad018375 MN |
474 | kfree(pinfo); |
475 | } | |
476 | ||
477 | static void rate_control_pid_clear(void *priv) | |
478 | { | |
479 | } | |
480 | ||
481 | static void *rate_control_pid_alloc_sta(void *priv, gfp_t gfp) | |
482 | { | |
483 | struct rc_pid_sta_info *spinfo; | |
484 | ||
485 | spinfo = kzalloc(sizeof(*spinfo), gfp); | |
486 | ||
487 | return spinfo; | |
488 | } | |
489 | ||
490 | static void rate_control_pid_free_sta(void *priv, void *priv_sta) | |
491 | { | |
492 | struct rc_pid_sta_info *spinfo = priv_sta; | |
493 | kfree(spinfo); | |
494 | } | |
495 | ||
496 | struct rate_control_ops mac80211_rcpid = { | |
497 | .name = "pid", | |
498 | .tx_status = rate_control_pid_tx_status, | |
499 | .get_rate = rate_control_pid_get_rate, | |
500 | .rate_init = rate_control_pid_rate_init, | |
501 | .clear = rate_control_pid_clear, | |
502 | .alloc = rate_control_pid_alloc, | |
503 | .free = rate_control_pid_free, | |
504 | .alloc_sta = rate_control_pid_alloc_sta, | |
505 | .free_sta = rate_control_pid_free_sta, | |
506 | }; |