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>
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)
82 i = r[cur + adj].rev_index;
88 for (k = j; k >= i; k--)
89 if (r[k].diff <= r[j].diff)
94 for (k = i + 1; k + i < l; k++)
95 if (r[k].diff <= r[i].diff)
102 static void rate_control_pid_adjust_rate(struct ieee80211_local *local,
103 struct sta_info *sta, int adj,
104 struct rc_pid_rateinfo *rinfo)
106 struct ieee80211_sub_if_data *sdata;
107 struct ieee80211_hw_mode *mode;
110 int back = (adj > 0) ? 1 : -1;
112 sdata = IEEE80211_DEV_TO_SUB_IF(sta->dev);
113 if (sdata->bss && sdata->bss->force_unicast_rateidx > -1) {
114 /* forced unicast rate - do not change STA rate */
118 mode = local->oper_hw_mode;
119 maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1;
121 newidx = rate_control_pid_shift_adjust(rinfo, adj, sta->txrate,
124 while (newidx != sta->txrate) {
125 if (rate_supported(sta, mode, newidx) &&
126 (maxrate < 0 || newidx <= maxrate)) {
127 sta->txrate = newidx;
134 #ifdef CONFIG_MAC80211_DEBUGFS
135 rate_control_pid_event_rate_change(
136 &((struct rc_pid_sta_info *)sta->rate_ctrl_priv)->events,
137 newidx, mode->rates[newidx].rate);
141 /* Normalize the failed frames per-rate differences. */
142 static void rate_control_pid_normalize(struct rc_pid_info *pinfo, int l)
144 int i, norm_offset = pinfo->norm_offset;
145 struct rc_pid_rateinfo *r = pinfo->rinfo;
147 if (r[0].diff > norm_offset)
148 r[0].diff -= norm_offset;
149 else if (r[0].diff < -norm_offset)
150 r[0].diff += norm_offset;
151 for (i = 0; i < l - 1; i++)
152 if (r[i + 1].diff > r[i].diff + norm_offset)
153 r[i + 1].diff -= norm_offset;
154 else if (r[i + 1].diff <= r[i].diff)
155 r[i + 1].diff += norm_offset;
158 static void rate_control_pid_sample(struct rc_pid_info *pinfo,
159 struct ieee80211_local *local,
160 struct sta_info *sta)
162 struct rc_pid_sta_info *spinfo = sta->rate_ctrl_priv;
163 struct rc_pid_rateinfo *rinfo = pinfo->rinfo;
164 struct ieee80211_hw_mode *mode;
171 unsigned long period;
173 mode = local->oper_hw_mode;
174 spinfo = sta->rate_ctrl_priv;
176 /* In case nothing happened during the previous control interval, turn
177 * the sharpening factor on. */
178 period = (HZ * pinfo->sampling_period + 500) / 1000;
181 if (jiffies - spinfo->last_sample > 2 * period)
182 spinfo->sharp_cnt = pinfo->sharpen_duration;
184 spinfo->last_sample = jiffies;
186 /* This should never happen, but in case, we assume the old sample is
187 * still a good measurement and copy it. */
188 if (unlikely(spinfo->tx_num_xmit == 0))
189 pf = spinfo->last_pf;
191 pf = spinfo->tx_num_failed * 100 / spinfo->tx_num_xmit;
192 pf <<= RC_PID_ARITH_SHIFT;
195 spinfo->tx_num_xmit = 0;
196 spinfo->tx_num_failed = 0;
198 /* If we just switched rate, update the rate behaviour info. */
199 if (pinfo->oldrate != sta->txrate) {
201 i = rinfo[pinfo->oldrate].rev_index;
202 j = rinfo[sta->txrate].rev_index;
204 tmp = (pf - spinfo->last_pf);
205 tmp = RC_PID_DO_ARITH_RIGHT_SHIFT(tmp, RC_PID_ARITH_SHIFT);
207 rinfo[j].diff = rinfo[i].diff + tmp;
208 pinfo->oldrate = sta->txrate;
210 rate_control_pid_normalize(pinfo, mode->num_rates);
212 /* Compute the proportional, integral and derivative errors. */
213 err_prop = (pinfo->target << RC_PID_ARITH_SHIFT) - pf;
215 err_avg = spinfo->err_avg_sc >> pinfo->smoothing_shift;
216 spinfo->err_avg_sc = spinfo->err_avg_sc - err_avg + err_prop;
217 err_int = spinfo->err_avg_sc >> pinfo->smoothing_shift;
219 err_der = (pf - spinfo->last_pf) *
220 (1 + pinfo->sharpen_factor * spinfo->sharp_cnt);
221 spinfo->last_pf = pf;
222 if (spinfo->sharp_cnt)
225 #ifdef CONFIG_MAC80211_DEBUGFS
226 rate_control_pid_event_pf_sample(&spinfo->events, pf, err_prop, err_int,
230 /* Compute the controller output. */
231 adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i
232 + err_der * pinfo->coeff_d);
233 adj = RC_PID_DO_ARITH_RIGHT_SHIFT(adj, 2 * RC_PID_ARITH_SHIFT);
237 rate_control_pid_adjust_rate(local, sta, adj, rinfo);
240 static void rate_control_pid_tx_status(void *priv, struct net_device *dev,
242 struct ieee80211_tx_status *status)
244 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
245 struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
246 struct rc_pid_info *pinfo = priv;
247 struct sta_info *sta;
248 struct rc_pid_sta_info *spinfo;
249 unsigned long period;
251 sta = sta_info_get(local, hdr->addr1);
256 /* Ignore all frames that were sent with a different rate than the rate
257 * we currently advise mac80211 to use. */
258 if (status->control.rate != &local->oper_hw_mode->rates[sta->txrate])
261 spinfo = sta->rate_ctrl_priv;
262 spinfo->tx_num_xmit++;
264 #ifdef CONFIG_MAC80211_DEBUGFS
265 rate_control_pid_event_tx_status(&spinfo->events, status);
268 /* We count frames that totally failed to be transmitted as two bad
269 * frames, those that made it out but had some retries as one good and
271 if (status->excessive_retries) {
272 spinfo->tx_num_failed += 2;
273 spinfo->tx_num_xmit++;
274 } else if (status->retry_count) {
275 spinfo->tx_num_failed++;
276 spinfo->tx_num_xmit++;
279 if (status->excessive_retries) {
280 sta->tx_retry_failed++;
281 sta->tx_num_consecutive_failures++;
282 sta->tx_num_mpdu_fail++;
284 sta->last_ack_rssi[0] = sta->last_ack_rssi[1];
285 sta->last_ack_rssi[1] = sta->last_ack_rssi[2];
286 sta->last_ack_rssi[2] = status->ack_signal;
287 sta->tx_num_consecutive_failures = 0;
288 sta->tx_num_mpdu_ok++;
290 sta->tx_retry_count += status->retry_count;
291 sta->tx_num_mpdu_fail += status->retry_count;
293 /* Update PID controller state. */
294 period = (HZ * pinfo->sampling_period + 500) / 1000;
297 if (time_after(jiffies, spinfo->last_sample + period))
298 rate_control_pid_sample(pinfo, local, sta);
303 static void rate_control_pid_get_rate(void *priv, struct net_device *dev,
304 struct ieee80211_hw_mode *mode,
306 struct rate_selection *sel)
308 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
309 struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
310 struct sta_info *sta;
313 sta = sta_info_get(local, hdr->addr1);
316 sel->rate = rate_lowest(local, mode, NULL);
321 rateidx = sta->txrate;
323 if (rateidx >= mode->num_rates)
324 rateidx = mode->num_rates - 1;
328 sel->rate = &mode->rates[rateidx];
330 #ifdef CONFIG_MAC80211_DEBUGFS
331 rate_control_pid_event_tx_rate(
332 &((struct rc_pid_sta_info *) sta->rate_ctrl_priv)->events,
333 rateidx, mode->rates[rateidx].rate);
337 static void rate_control_pid_rate_init(void *priv, void *priv_sta,
338 struct ieee80211_local *local,
339 struct sta_info *sta)
341 /* TODO: This routine should consider using RSSI from previous packets
342 * as we need to have IEEE 802.1X auth succeed immediately after assoc..
343 * Until that method is implemented, we will use the lowest supported
344 * rate as a workaround. */
345 sta->txrate = rate_lowest_index(local, local->oper_hw_mode, sta);
348 static void *rate_control_pid_alloc(struct ieee80211_local *local)
350 struct rc_pid_info *pinfo;
351 struct rc_pid_rateinfo *rinfo;
352 struct ieee80211_hw_mode *mode;
355 #ifdef CONFIG_MAC80211_DEBUGFS
356 struct rc_pid_debugfs_entries *de;
359 pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC);
363 /* We can safely assume that oper_hw_mode won't change unless we get
365 mode = local->oper_hw_mode;
366 rinfo = kmalloc(sizeof(*rinfo) * mode->num_rates, GFP_ATOMIC);
372 /* Sort the rates. This is optimized for the most common case (i.e.
373 * almost-sorted CCK+OFDM rates). Kind of bubble-sort with reversed
375 for (i = 0; i < mode->num_rates; i++) {
377 rinfo[i].rev_index = i;
378 if (pinfo->fast_start)
381 rinfo[i].diff = i * pinfo->norm_offset;
383 for (i = 1; i < mode->num_rates; i++) {
385 for (j = 0; j < mode->num_rates - i; j++)
386 if (unlikely(mode->rates[rinfo[j].index].rate >
387 mode->rates[rinfo[j + 1].index].rate)) {
388 tmp = rinfo[j].index;
389 rinfo[j].index = rinfo[j + 1].index;
390 rinfo[j + 1].index = tmp;
391 rinfo[rinfo[j].index].rev_index = j;
392 rinfo[rinfo[j + 1].index].rev_index = j + 1;
399 pinfo->target = RC_PID_TARGET_PF;
400 pinfo->sampling_period = RC_PID_INTERVAL;
401 pinfo->coeff_p = RC_PID_COEFF_P;
402 pinfo->coeff_i = RC_PID_COEFF_I;
403 pinfo->coeff_d = RC_PID_COEFF_D;
404 pinfo->smoothing_shift = RC_PID_SMOOTHING_SHIFT;
405 pinfo->sharpen_factor = RC_PID_SHARPENING_FACTOR;
406 pinfo->sharpen_duration = RC_PID_SHARPENING_DURATION;
407 pinfo->norm_offset = RC_PID_NORM_OFFSET;
408 pinfo->fast_start = RC_PID_FAST_START;
409 pinfo->rinfo = rinfo;
412 #ifdef CONFIG_MAC80211_DEBUGFS
413 de = &pinfo->dentries;
414 de->dir = debugfs_create_dir("rc80211_pid",
415 local->hw.wiphy->debugfsdir);
416 de->target = debugfs_create_u32("target_pf", S_IRUSR | S_IWUSR,
417 de->dir, &pinfo->target);
418 de->sampling_period = debugfs_create_u32("sampling_period",
419 S_IRUSR | S_IWUSR, de->dir,
420 &pinfo->sampling_period);
421 de->coeff_p = debugfs_create_u32("coeff_p", S_IRUSR | S_IWUSR,
422 de->dir, &pinfo->coeff_p);
423 de->coeff_i = debugfs_create_u32("coeff_i", S_IRUSR | S_IWUSR,
424 de->dir, &pinfo->coeff_i);
425 de->coeff_d = debugfs_create_u32("coeff_d", S_IRUSR | S_IWUSR,
426 de->dir, &pinfo->coeff_d);
427 de->smoothing_shift = debugfs_create_u32("smoothing_shift",
428 S_IRUSR | S_IWUSR, de->dir,
429 &pinfo->smoothing_shift);
430 de->sharpen_factor = debugfs_create_u32("sharpen_factor",
431 S_IRUSR | S_IWUSR, de->dir,
432 &pinfo->sharpen_factor);
433 de->sharpen_duration = debugfs_create_u32("sharpen_duration",
434 S_IRUSR | S_IWUSR, de->dir,
435 &pinfo->sharpen_duration);
436 de->norm_offset = debugfs_create_u32("norm_offset",
437 S_IRUSR | S_IWUSR, de->dir,
438 &pinfo->norm_offset);
439 de->fast_start = debugfs_create_bool("fast_start",
440 S_IRUSR | S_IWUSR, de->dir,
447 static void rate_control_pid_free(void *priv)
449 struct rc_pid_info *pinfo = priv;
450 #ifdef CONFIG_MAC80211_DEBUGFS
451 struct rc_pid_debugfs_entries *de = &pinfo->dentries;
453 debugfs_remove(de->fast_start);
454 debugfs_remove(de->norm_offset);
455 debugfs_remove(de->sharpen_duration);
456 debugfs_remove(de->sharpen_factor);
457 debugfs_remove(de->smoothing_shift);
458 debugfs_remove(de->coeff_d);
459 debugfs_remove(de->coeff_i);
460 debugfs_remove(de->coeff_p);
461 debugfs_remove(de->sampling_period);
462 debugfs_remove(de->target);
463 debugfs_remove(de->dir);
470 static void rate_control_pid_clear(void *priv)
474 static void *rate_control_pid_alloc_sta(void *priv, gfp_t gfp)
476 struct rc_pid_sta_info *spinfo;
478 spinfo = kzalloc(sizeof(*spinfo), gfp);
482 #ifdef CONFIG_MAC80211_DEBUGFS
483 spin_lock_init(&spinfo->events.lock);
484 init_waitqueue_head(&spinfo->events.waitqueue);
490 static void rate_control_pid_free_sta(void *priv, void *priv_sta)
492 struct rc_pid_sta_info *spinfo = priv_sta;
496 struct rate_control_ops mac80211_rcpid = {
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 #ifdef CONFIG_MAC80211_DEBUGFS
507 .add_sta_debugfs = rate_control_pid_add_sta_debugfs,
508 .remove_sta_debugfs = rate_control_pid_remove_sta_debugfs,