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_supported_band *sband;
108 int back = (adj > 0) ? 1 : -1;
110 sdata = IEEE80211_DEV_TO_SUB_IF(sta->dev);
112 sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
113 maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1;
115 newidx = rate_control_pid_shift_adjust(rinfo, adj, sta->txrate_idx,
118 while (newidx != sta->txrate_idx) {
119 if (rate_supported(sta, sband->band, newidx) &&
120 (maxrate < 0 || newidx <= maxrate)) {
121 sta->txrate_idx = 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, sband->bitrates[newidx].bitrate);
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_supported_band *sband;
165 unsigned long period;
167 sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
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_idx) {
195 i = rinfo[pinfo->oldrate].rev_index;
196 j = rinfo[sta->txrate_idx].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_idx;
204 rate_control_pid_normalize(pinfo, sband->n_bitrates);
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;
245 struct ieee80211_supported_band *sband;
247 sta = sta_info_get(local, hdr->addr1);
248 sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
253 /* Don't update the state if we're not controlling the rate. */
254 sdata = IEEE80211_DEV_TO_SUB_IF(sta->dev);
255 if (sdata->bss && sdata->bss->force_unicast_rateidx > -1) {
256 sta->txrate_idx = sdata->bss->max_ratectrl_rateidx;
260 /* Ignore all frames that were sent with a different rate than the rate
261 * we currently advise mac80211 to use. */
262 if (status->control.tx_rate != &sband->bitrates[sta->txrate_idx])
265 spinfo = sta->rate_ctrl_priv;
266 spinfo->tx_num_xmit++;
268 #ifdef CONFIG_MAC80211_DEBUGFS
269 rate_control_pid_event_tx_status(&spinfo->events, status);
272 /* We count frames that totally failed to be transmitted as two bad
273 * frames, those that made it out but had some retries as one good and
275 if (status->excessive_retries) {
276 spinfo->tx_num_failed += 2;
277 spinfo->tx_num_xmit++;
278 } else if (status->retry_count) {
279 spinfo->tx_num_failed++;
280 spinfo->tx_num_xmit++;
283 if (status->excessive_retries) {
284 sta->tx_retry_failed++;
285 sta->tx_num_consecutive_failures++;
286 sta->tx_num_mpdu_fail++;
288 sta->last_ack_rssi[0] = sta->last_ack_rssi[1];
289 sta->last_ack_rssi[1] = sta->last_ack_rssi[2];
290 sta->last_ack_rssi[2] = status->ack_signal;
291 sta->tx_num_consecutive_failures = 0;
292 sta->tx_num_mpdu_ok++;
294 sta->tx_retry_count += status->retry_count;
295 sta->tx_num_mpdu_fail += status->retry_count;
297 /* Update PID controller state. */
298 period = (HZ * pinfo->sampling_period + 500) / 1000;
301 if (time_after(jiffies, spinfo->last_sample + period))
302 rate_control_pid_sample(pinfo, local, sta);
308 static void rate_control_pid_get_rate(void *priv, struct net_device *dev,
309 struct ieee80211_supported_band *sband,
311 struct rate_selection *sel)
313 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
314 struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
315 struct ieee80211_sub_if_data *sdata;
316 struct sta_info *sta;
320 sta = sta_info_get(local, hdr->addr1);
322 /* Send management frames and broadcast/multicast data using lowest
324 fc = le16_to_cpu(hdr->frame_control);
325 if ((fc & IEEE80211_FCTL_FTYPE) != IEEE80211_FTYPE_DATA ||
326 is_multicast_ether_addr(hdr->addr1) || !sta) {
327 sel->rate = rate_lowest(local, sband, sta);
333 /* If a forced rate is in effect, select it. */
334 sdata = IEEE80211_DEV_TO_SUB_IF(dev);
335 if (sdata->bss && sdata->bss->force_unicast_rateidx > -1)
336 sta->txrate_idx = sdata->bss->force_unicast_rateidx;
338 rateidx = sta->txrate_idx;
340 if (rateidx >= sband->n_bitrates)
341 rateidx = sband->n_bitrates - 1;
343 sta->last_txrate_idx = rateidx;
347 sel->rate = &sband->bitrates[rateidx];
349 #ifdef CONFIG_MAC80211_DEBUGFS
350 rate_control_pid_event_tx_rate(
351 &((struct rc_pid_sta_info *) sta->rate_ctrl_priv)->events,
352 rateidx, sband->bitrates[rateidx].bitrate);
356 static void rate_control_pid_rate_init(void *priv, void *priv_sta,
357 struct ieee80211_local *local,
358 struct sta_info *sta)
360 /* TODO: This routine should consider using RSSI from previous packets
361 * as we need to have IEEE 802.1X auth succeed immediately after assoc..
362 * Until that method is implemented, we will use the lowest supported
363 * rate as a workaround. */
364 struct ieee80211_supported_band *sband;
366 sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
367 sta->txrate_idx = rate_lowest_index(local, sband, sta);
370 static void *rate_control_pid_alloc(struct ieee80211_local *local)
372 struct rc_pid_info *pinfo;
373 struct rc_pid_rateinfo *rinfo;
374 struct ieee80211_supported_band *sband;
377 #ifdef CONFIG_MAC80211_DEBUGFS
378 struct rc_pid_debugfs_entries *de;
381 sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
383 pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC);
387 /* We can safely assume that sband won't change unless we get
389 rinfo = kmalloc(sizeof(*rinfo) * sband->n_bitrates, GFP_ATOMIC);
395 /* Sort the rates. This is optimized for the most common case (i.e.
396 * almost-sorted CCK+OFDM rates). Kind of bubble-sort with reversed
398 for (i = 0; i < sband->n_bitrates; i++) {
400 rinfo[i].rev_index = i;
401 if (pinfo->fast_start)
404 rinfo[i].diff = i * pinfo->norm_offset;
406 for (i = 1; i < sband->n_bitrates; i++) {
408 for (j = 0; j < sband->n_bitrates - i; j++)
409 if (unlikely(sband->bitrates[rinfo[j].index].bitrate >
410 sband->bitrates[rinfo[j + 1].index].bitrate)) {
411 tmp = rinfo[j].index;
412 rinfo[j].index = rinfo[j + 1].index;
413 rinfo[j + 1].index = tmp;
414 rinfo[rinfo[j].index].rev_index = j;
415 rinfo[rinfo[j + 1].index].rev_index = j + 1;
422 pinfo->target = RC_PID_TARGET_PF;
423 pinfo->sampling_period = RC_PID_INTERVAL;
424 pinfo->coeff_p = RC_PID_COEFF_P;
425 pinfo->coeff_i = RC_PID_COEFF_I;
426 pinfo->coeff_d = RC_PID_COEFF_D;
427 pinfo->smoothing_shift = RC_PID_SMOOTHING_SHIFT;
428 pinfo->sharpen_factor = RC_PID_SHARPENING_FACTOR;
429 pinfo->sharpen_duration = RC_PID_SHARPENING_DURATION;
430 pinfo->norm_offset = RC_PID_NORM_OFFSET;
431 pinfo->fast_start = RC_PID_FAST_START;
432 pinfo->rinfo = rinfo;
435 #ifdef CONFIG_MAC80211_DEBUGFS
436 de = &pinfo->dentries;
437 de->dir = debugfs_create_dir("rc80211_pid",
438 local->hw.wiphy->debugfsdir);
439 de->target = debugfs_create_u32("target_pf", S_IRUSR | S_IWUSR,
440 de->dir, &pinfo->target);
441 de->sampling_period = debugfs_create_u32("sampling_period",
442 S_IRUSR | S_IWUSR, de->dir,
443 &pinfo->sampling_period);
444 de->coeff_p = debugfs_create_u32("coeff_p", S_IRUSR | S_IWUSR,
445 de->dir, &pinfo->coeff_p);
446 de->coeff_i = debugfs_create_u32("coeff_i", S_IRUSR | S_IWUSR,
447 de->dir, &pinfo->coeff_i);
448 de->coeff_d = debugfs_create_u32("coeff_d", S_IRUSR | S_IWUSR,
449 de->dir, &pinfo->coeff_d);
450 de->smoothing_shift = debugfs_create_u32("smoothing_shift",
451 S_IRUSR | S_IWUSR, de->dir,
452 &pinfo->smoothing_shift);
453 de->sharpen_factor = debugfs_create_u32("sharpen_factor",
454 S_IRUSR | S_IWUSR, de->dir,
455 &pinfo->sharpen_factor);
456 de->sharpen_duration = debugfs_create_u32("sharpen_duration",
457 S_IRUSR | S_IWUSR, de->dir,
458 &pinfo->sharpen_duration);
459 de->norm_offset = debugfs_create_u32("norm_offset",
460 S_IRUSR | S_IWUSR, de->dir,
461 &pinfo->norm_offset);
462 de->fast_start = debugfs_create_bool("fast_start",
463 S_IRUSR | S_IWUSR, de->dir,
470 static void rate_control_pid_free(void *priv)
472 struct rc_pid_info *pinfo = priv;
473 #ifdef CONFIG_MAC80211_DEBUGFS
474 struct rc_pid_debugfs_entries *de = &pinfo->dentries;
476 debugfs_remove(de->fast_start);
477 debugfs_remove(de->norm_offset);
478 debugfs_remove(de->sharpen_duration);
479 debugfs_remove(de->sharpen_factor);
480 debugfs_remove(de->smoothing_shift);
481 debugfs_remove(de->coeff_d);
482 debugfs_remove(de->coeff_i);
483 debugfs_remove(de->coeff_p);
484 debugfs_remove(de->sampling_period);
485 debugfs_remove(de->target);
486 debugfs_remove(de->dir);
493 static void rate_control_pid_clear(void *priv)
497 static void *rate_control_pid_alloc_sta(void *priv, gfp_t gfp)
499 struct rc_pid_sta_info *spinfo;
501 spinfo = kzalloc(sizeof(*spinfo), gfp);
505 spinfo->last_sample = jiffies;
507 #ifdef CONFIG_MAC80211_DEBUGFS
508 spin_lock_init(&spinfo->events.lock);
509 init_waitqueue_head(&spinfo->events.waitqueue);
515 static void rate_control_pid_free_sta(void *priv, void *priv_sta)
517 struct rc_pid_sta_info *spinfo = priv_sta;
521 static struct rate_control_ops mac80211_rcpid = {
523 .tx_status = rate_control_pid_tx_status,
524 .get_rate = rate_control_pid_get_rate,
525 .rate_init = rate_control_pid_rate_init,
526 .clear = rate_control_pid_clear,
527 .alloc = rate_control_pid_alloc,
528 .free = rate_control_pid_free,
529 .alloc_sta = rate_control_pid_alloc_sta,
530 .free_sta = rate_control_pid_free_sta,
531 #ifdef CONFIG_MAC80211_DEBUGFS
532 .add_sta_debugfs = rate_control_pid_add_sta_debugfs,
533 .remove_sta_debugfs = rate_control_pid_remove_sta_debugfs,
537 MODULE_DESCRIPTION("PID controller based rate control algorithm");
538 MODULE_AUTHOR("Stefano Brivio");
539 MODULE_AUTHOR("Mattias Nissler");
540 MODULE_LICENSE("GPL");
542 int __init rc80211_pid_init(void)
544 return ieee80211_rate_control_register(&mac80211_rcpid);
547 void rc80211_pid_exit(void)
549 ieee80211_rate_control_unregister(&mac80211_rcpid);
552 #ifdef CONFIG_MAC80211_RC_PID_MODULE
553 module_init(rc80211_pid_init);
554 module_exit(rc80211_pid_exit);