2 * Copyright 2002-2005, Instant802 Networks, Inc.
3 * Copyright 2005, Devicescape Software, Inc.
4 * Copyright 2007, Mattias Nissler <mattias.nissler@gmx.de>
5 * Copyright 2007, Stefano Brivio <stefano.brivio@polimi.it>
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.
12 #include <linux/netdevice.h>
13 #include <linux/types.h>
14 #include <linux/skbuff.h>
15 #include <linux/debugfs.h>
16 #include <net/mac80211.h>
17 #include "ieee80211_rate.h"
19 #include "rc80211_pid.h"
22 /* This is an implementation of a TX rate control algorithm that uses a PID
23 * controller. Given a target failed frames rate, the controller decides about
24 * TX rate changes to meet the target failed frames rate.
26 * The controller basically computes the following:
28 * adj = CP * err + CI * err_avg + CD * (err - last_err) * (1 + sharpening)
31 * adj adjustment value that is used to switch TX rate (see below)
32 * err current error: target vs. current failed frames percentage
34 * err_avg average (i.e. poor man's integral) of recent errors
35 * sharpening non-zero when fast response is needed (i.e. right after
36 * association or no frames sent for a long time), heading
38 * CP Proportional coefficient
39 * CI Integral coefficient
40 * CD Derivative coefficient
42 * CP, CI, CD are subject to careful tuning.
44 * The integral component uses a exponential moving average approach instead of
45 * an actual sliding window. The advantage is that we don't need to keep an
46 * array of the last N error values and computation is easier.
48 * Once we have the adj value, we map it to a rate by means of a learning
49 * algorithm. This algorithm keeps the state of the percentual failed frames
50 * difference between rates. The behaviour of the lowest available rate is kept
51 * as a reference value, and every time we switch between two rates, we compute
52 * the difference between the failed frames each rate exhibited. By doing so,
53 * we compare behaviours which different rates exhibited in adjacent timeslices,
54 * thus the comparison is minimally affected by external conditions. This
55 * difference gets propagated to the whole set of measurements, so that the
56 * reference is always the same. Periodically, we normalize this set so that
57 * recent events weigh the most. By comparing the adj value with this set, we
58 * avoid pejorative switches to lower rates and allow for switches to higher
59 * rates if they behaved well.
61 * Note that for the computations we use a fixed-point representation to avoid
62 * floating point arithmetic. Hence, all values are shifted left by
67 /* Shift the adjustment so that we won't switch to a lower rate if it exhibited
68 * a worse failed frames behaviour and we'll choose the highest rate whose
69 * failed frames behaviour is not worse than the one of the original rate
70 * target. While at it, check that the adjustment is within the ranges. Then,
71 * provide the new rate index. */
72 static int rate_control_pid_shift_adjust(struct rc_pid_rateinfo
*r
,
73 int adj
, int cur
, int l
)
83 return r
[l
- 1].index
;
88 for (k
= j
; k
>= i
; k
--)
89 if (r
[k
].diff
<= r
[j
].diff
)
92 for (k
= i
+ 1; k
+ i
< l
; k
++)
93 if (r
[k
].diff
<= r
[i
].diff
)
100 static void rate_control_pid_adjust_rate(struct ieee80211_local
*local
,
101 struct sta_info
*sta
, int adj
,
102 struct rc_pid_rateinfo
*rinfo
)
104 struct ieee80211_sub_if_data
*sdata
;
105 struct ieee80211_hw_mode
*mode
;
108 int back
= (adj
> 0) ? 1 : -1;
110 sdata
= IEEE80211_DEV_TO_SUB_IF(sta
->dev
);
112 mode
= local
->oper_hw_mode
;
113 maxrate
= sdata
->bss
? sdata
->bss
->max_ratectrl_rateidx
: -1;
115 newidx
= rate_control_pid_shift_adjust(rinfo
, adj
, sta
->txrate
,
118 while (newidx
!= sta
->txrate
) {
119 if (rate_supported(sta
, mode
, newidx
) &&
120 (maxrate
< 0 || newidx
<= maxrate
)) {
121 sta
->txrate
= newidx
;
128 #ifdef CONFIG_MAC80211_DEBUGFS
129 rate_control_pid_event_rate_change(
130 &((struct rc_pid_sta_info
*)sta
->rate_ctrl_priv
)->events
,
131 newidx
, mode
->rates
[newidx
].rate
);
135 /* Normalize the failed frames per-rate differences. */
136 static void rate_control_pid_normalize(struct rc_pid_info
*pinfo
, int l
)
138 int i
, norm_offset
= pinfo
->norm_offset
;
139 struct rc_pid_rateinfo
*r
= pinfo
->rinfo
;
141 if (r
[0].diff
> norm_offset
)
142 r
[0].diff
-= norm_offset
;
143 else if (r
[0].diff
< -norm_offset
)
144 r
[0].diff
+= norm_offset
;
145 for (i
= 0; i
< l
- 1; i
++)
146 if (r
[i
+ 1].diff
> r
[i
].diff
+ norm_offset
)
147 r
[i
+ 1].diff
-= norm_offset
;
148 else if (r
[i
+ 1].diff
<= r
[i
].diff
)
149 r
[i
+ 1].diff
+= norm_offset
;
152 static void rate_control_pid_sample(struct rc_pid_info
*pinfo
,
153 struct ieee80211_local
*local
,
154 struct sta_info
*sta
)
156 struct rc_pid_sta_info
*spinfo
= sta
->rate_ctrl_priv
;
157 struct rc_pid_rateinfo
*rinfo
= pinfo
->rinfo
;
158 struct ieee80211_hw_mode
*mode
;
165 unsigned long period
;
167 mode
= local
->oper_hw_mode
;
168 spinfo
= sta
->rate_ctrl_priv
;
170 /* In case nothing happened during the previous control interval, turn
171 * the sharpening factor on. */
172 period
= (HZ
* pinfo
->sampling_period
+ 500) / 1000;
175 if (jiffies
- spinfo
->last_sample
> 2 * period
)
176 spinfo
->sharp_cnt
= pinfo
->sharpen_duration
;
178 spinfo
->last_sample
= jiffies
;
180 /* This should never happen, but in case, we assume the old sample is
181 * still a good measurement and copy it. */
182 if (unlikely(spinfo
->tx_num_xmit
== 0))
183 pf
= spinfo
->last_pf
;
185 pf
= spinfo
->tx_num_failed
* 100 / spinfo
->tx_num_xmit
;
186 pf
<<= RC_PID_ARITH_SHIFT
;
189 spinfo
->tx_num_xmit
= 0;
190 spinfo
->tx_num_failed
= 0;
192 /* If we just switched rate, update the rate behaviour info. */
193 if (pinfo
->oldrate
!= sta
->txrate
) {
195 i
= rinfo
[pinfo
->oldrate
].rev_index
;
196 j
= rinfo
[sta
->txrate
].rev_index
;
198 tmp
= (pf
- spinfo
->last_pf
);
199 tmp
= RC_PID_DO_ARITH_RIGHT_SHIFT(tmp
, RC_PID_ARITH_SHIFT
);
201 rinfo
[j
].diff
= rinfo
[i
].diff
+ tmp
;
202 pinfo
->oldrate
= sta
->txrate
;
204 rate_control_pid_normalize(pinfo
, mode
->num_rates
);
206 /* Compute the proportional, integral and derivative errors. */
207 err_prop
= (pinfo
->target
<< RC_PID_ARITH_SHIFT
) - pf
;
209 err_avg
= spinfo
->err_avg_sc
>> pinfo
->smoothing_shift
;
210 spinfo
->err_avg_sc
= spinfo
->err_avg_sc
- err_avg
+ err_prop
;
211 err_int
= spinfo
->err_avg_sc
>> pinfo
->smoothing_shift
;
213 err_der
= (pf
- spinfo
->last_pf
) *
214 (1 + pinfo
->sharpen_factor
* spinfo
->sharp_cnt
);
215 spinfo
->last_pf
= pf
;
216 if (spinfo
->sharp_cnt
)
219 #ifdef CONFIG_MAC80211_DEBUGFS
220 rate_control_pid_event_pf_sample(&spinfo
->events
, pf
, err_prop
, err_int
,
224 /* Compute the controller output. */
225 adj
= (err_prop
* pinfo
->coeff_p
+ err_int
* pinfo
->coeff_i
226 + err_der
* pinfo
->coeff_d
);
227 adj
= RC_PID_DO_ARITH_RIGHT_SHIFT(adj
, 2 * RC_PID_ARITH_SHIFT
);
231 rate_control_pid_adjust_rate(local
, sta
, adj
, rinfo
);
234 static void rate_control_pid_tx_status(void *priv
, struct net_device
*dev
,
236 struct ieee80211_tx_status
*status
)
238 struct ieee80211_local
*local
= wdev_priv(dev
->ieee80211_ptr
);
239 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
240 struct ieee80211_sub_if_data
*sdata
;
241 struct rc_pid_info
*pinfo
= priv
;
242 struct sta_info
*sta
;
243 struct rc_pid_sta_info
*spinfo
;
244 unsigned long period
;
246 sta
= sta_info_get(local
, hdr
->addr1
);
251 /* Don't update the state if we're not controlling the rate. */
252 sdata
= IEEE80211_DEV_TO_SUB_IF(sta
->dev
);
253 if (sdata
->bss
&& sdata
->bss
->force_unicast_rateidx
> -1) {
254 sta
->txrate
= sdata
->bss
->max_ratectrl_rateidx
;
258 /* Ignore all frames that were sent with a different rate than the rate
259 * we currently advise mac80211 to use. */
260 if (status
->control
.rate
!= &local
->oper_hw_mode
->rates
[sta
->txrate
])
263 spinfo
= sta
->rate_ctrl_priv
;
264 spinfo
->tx_num_xmit
++;
266 #ifdef CONFIG_MAC80211_DEBUGFS
267 rate_control_pid_event_tx_status(&spinfo
->events
, status
);
270 /* We count frames that totally failed to be transmitted as two bad
271 * frames, those that made it out but had some retries as one good and
273 if (status
->excessive_retries
) {
274 spinfo
->tx_num_failed
+= 2;
275 spinfo
->tx_num_xmit
++;
276 } else if (status
->retry_count
) {
277 spinfo
->tx_num_failed
++;
278 spinfo
->tx_num_xmit
++;
281 if (status
->excessive_retries
) {
282 sta
->tx_retry_failed
++;
283 sta
->tx_num_consecutive_failures
++;
284 sta
->tx_num_mpdu_fail
++;
286 sta
->last_ack_rssi
[0] = sta
->last_ack_rssi
[1];
287 sta
->last_ack_rssi
[1] = sta
->last_ack_rssi
[2];
288 sta
->last_ack_rssi
[2] = status
->ack_signal
;
289 sta
->tx_num_consecutive_failures
= 0;
290 sta
->tx_num_mpdu_ok
++;
292 sta
->tx_retry_count
+= status
->retry_count
;
293 sta
->tx_num_mpdu_fail
+= status
->retry_count
;
295 /* Update PID controller state. */
296 period
= (HZ
* pinfo
->sampling_period
+ 500) / 1000;
299 if (time_after(jiffies
, spinfo
->last_sample
+ period
))
300 rate_control_pid_sample(pinfo
, local
, sta
);
306 static void rate_control_pid_get_rate(void *priv
, struct net_device
*dev
,
307 struct ieee80211_hw_mode
*mode
,
309 struct rate_selection
*sel
)
311 struct ieee80211_local
*local
= wdev_priv(dev
->ieee80211_ptr
);
312 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
313 struct sta_info
*sta
;
316 sta
= sta_info_get(local
, hdr
->addr1
);
319 sel
->rate
= rate_lowest(local
, mode
, NULL
);
324 rateidx
= sta
->txrate
;
326 if (rateidx
>= mode
->num_rates
)
327 rateidx
= mode
->num_rates
- 1;
331 sel
->rate
= &mode
->rates
[rateidx
];
333 #ifdef CONFIG_MAC80211_DEBUGFS
334 rate_control_pid_event_tx_rate(
335 &((struct rc_pid_sta_info
*) sta
->rate_ctrl_priv
)->events
,
336 rateidx
, mode
->rates
[rateidx
].rate
);
340 static void rate_control_pid_rate_init(void *priv
, void *priv_sta
,
341 struct ieee80211_local
*local
,
342 struct sta_info
*sta
)
344 /* TODO: This routine should consider using RSSI from previous packets
345 * as we need to have IEEE 802.1X auth succeed immediately after assoc..
346 * Until that method is implemented, we will use the lowest supported
347 * rate as a workaround. */
348 sta
->txrate
= rate_lowest_index(local
, local
->oper_hw_mode
, sta
);
351 static void *rate_control_pid_alloc(struct ieee80211_local
*local
)
353 struct rc_pid_info
*pinfo
;
354 struct rc_pid_rateinfo
*rinfo
;
355 struct ieee80211_hw_mode
*mode
;
358 #ifdef CONFIG_MAC80211_DEBUGFS
359 struct rc_pid_debugfs_entries
*de
;
362 pinfo
= kmalloc(sizeof(*pinfo
), GFP_ATOMIC
);
366 /* We can safely assume that oper_hw_mode won't change unless we get
368 mode
= local
->oper_hw_mode
;
369 rinfo
= kmalloc(sizeof(*rinfo
) * mode
->num_rates
, GFP_ATOMIC
);
375 /* Sort the rates. This is optimized for the most common case (i.e.
376 * almost-sorted CCK+OFDM rates). Kind of bubble-sort with reversed
378 for (i
= 0; i
< mode
->num_rates
; i
++) {
380 rinfo
[i
].rev_index
= i
;
381 if (pinfo
->fast_start
)
384 rinfo
[i
].diff
= i
* pinfo
->norm_offset
;
386 for (i
= 1; i
< mode
->num_rates
; i
++) {
388 for (j
= 0; j
< mode
->num_rates
- i
; j
++)
389 if (unlikely(mode
->rates
[rinfo
[j
].index
].rate
>
390 mode
->rates
[rinfo
[j
+ 1].index
].rate
)) {
391 tmp
= rinfo
[j
].index
;
392 rinfo
[j
].index
= rinfo
[j
+ 1].index
;
393 rinfo
[j
+ 1].index
= tmp
;
394 rinfo
[rinfo
[j
].index
].rev_index
= j
;
395 rinfo
[rinfo
[j
+ 1].index
].rev_index
= j
+ 1;
402 pinfo
->target
= RC_PID_TARGET_PF
;
403 pinfo
->sampling_period
= RC_PID_INTERVAL
;
404 pinfo
->coeff_p
= RC_PID_COEFF_P
;
405 pinfo
->coeff_i
= RC_PID_COEFF_I
;
406 pinfo
->coeff_d
= RC_PID_COEFF_D
;
407 pinfo
->smoothing_shift
= RC_PID_SMOOTHING_SHIFT
;
408 pinfo
->sharpen_factor
= RC_PID_SHARPENING_FACTOR
;
409 pinfo
->sharpen_duration
= RC_PID_SHARPENING_DURATION
;
410 pinfo
->norm_offset
= RC_PID_NORM_OFFSET
;
411 pinfo
->fast_start
= RC_PID_FAST_START
;
412 pinfo
->rinfo
= rinfo
;
415 #ifdef CONFIG_MAC80211_DEBUGFS
416 de
= &pinfo
->dentries
;
417 de
->dir
= debugfs_create_dir("rc80211_pid",
418 local
->hw
.wiphy
->debugfsdir
);
419 de
->target
= debugfs_create_u32("target_pf", S_IRUSR
| S_IWUSR
,
420 de
->dir
, &pinfo
->target
);
421 de
->sampling_period
= debugfs_create_u32("sampling_period",
422 S_IRUSR
| S_IWUSR
, de
->dir
,
423 &pinfo
->sampling_period
);
424 de
->coeff_p
= debugfs_create_u32("coeff_p", S_IRUSR
| S_IWUSR
,
425 de
->dir
, &pinfo
->coeff_p
);
426 de
->coeff_i
= debugfs_create_u32("coeff_i", S_IRUSR
| S_IWUSR
,
427 de
->dir
, &pinfo
->coeff_i
);
428 de
->coeff_d
= debugfs_create_u32("coeff_d", S_IRUSR
| S_IWUSR
,
429 de
->dir
, &pinfo
->coeff_d
);
430 de
->smoothing_shift
= debugfs_create_u32("smoothing_shift",
431 S_IRUSR
| S_IWUSR
, de
->dir
,
432 &pinfo
->smoothing_shift
);
433 de
->sharpen_factor
= debugfs_create_u32("sharpen_factor",
434 S_IRUSR
| S_IWUSR
, de
->dir
,
435 &pinfo
->sharpen_factor
);
436 de
->sharpen_duration
= debugfs_create_u32("sharpen_duration",
437 S_IRUSR
| S_IWUSR
, de
->dir
,
438 &pinfo
->sharpen_duration
);
439 de
->norm_offset
= debugfs_create_u32("norm_offset",
440 S_IRUSR
| S_IWUSR
, de
->dir
,
441 &pinfo
->norm_offset
);
442 de
->fast_start
= debugfs_create_bool("fast_start",
443 S_IRUSR
| S_IWUSR
, de
->dir
,
450 static void rate_control_pid_free(void *priv
)
452 struct rc_pid_info
*pinfo
= priv
;
453 #ifdef CONFIG_MAC80211_DEBUGFS
454 struct rc_pid_debugfs_entries
*de
= &pinfo
->dentries
;
456 debugfs_remove(de
->fast_start
);
457 debugfs_remove(de
->norm_offset
);
458 debugfs_remove(de
->sharpen_duration
);
459 debugfs_remove(de
->sharpen_factor
);
460 debugfs_remove(de
->smoothing_shift
);
461 debugfs_remove(de
->coeff_d
);
462 debugfs_remove(de
->coeff_i
);
463 debugfs_remove(de
->coeff_p
);
464 debugfs_remove(de
->sampling_period
);
465 debugfs_remove(de
->target
);
466 debugfs_remove(de
->dir
);
473 static void rate_control_pid_clear(void *priv
)
477 static void *rate_control_pid_alloc_sta(void *priv
, gfp_t gfp
)
479 struct rc_pid_sta_info
*spinfo
;
481 spinfo
= kzalloc(sizeof(*spinfo
), gfp
);
485 #ifdef CONFIG_MAC80211_DEBUGFS
486 spin_lock_init(&spinfo
->events
.lock
);
487 init_waitqueue_head(&spinfo
->events
.waitqueue
);
493 static void rate_control_pid_free_sta(void *priv
, void *priv_sta
)
495 struct rc_pid_sta_info
*spinfo
= priv_sta
;
499 static struct rate_control_ops mac80211_rcpid
= {
501 .tx_status
= rate_control_pid_tx_status
,
502 .get_rate
= rate_control_pid_get_rate
,
503 .rate_init
= rate_control_pid_rate_init
,
504 .clear
= rate_control_pid_clear
,
505 .alloc
= rate_control_pid_alloc
,
506 .free
= rate_control_pid_free
,
507 .alloc_sta
= rate_control_pid_alloc_sta
,
508 .free_sta
= rate_control_pid_free_sta
,
509 #ifdef CONFIG_MAC80211_DEBUGFS
510 .add_sta_debugfs
= rate_control_pid_add_sta_debugfs
,
511 .remove_sta_debugfs
= rate_control_pid_remove_sta_debugfs
,
515 MODULE_DESCRIPTION("PID controller based rate control algorithm");
516 MODULE_AUTHOR("Stefano Brivio");
517 MODULE_AUTHOR("Mattias Nissler");
518 MODULE_LICENSE("GPL");
520 int __init
rc80211_pid_init(void)
522 return ieee80211_rate_control_register(&mac80211_rcpid
);
525 void __exit
rc80211_pid_exit(void)
527 ieee80211_rate_control_unregister(&mac80211_rcpid
);
530 #ifdef CONFIG_MAC80211_RC_PID_MODULE
531 module_init(rc80211_pid_init
);
532 module_exit(rc80211_pid_exit
);