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_rateinfo *r, int l)
146 if (r[0].diff > RC_PID_NORM_OFFSET)
147 r[0].diff -= RC_PID_NORM_OFFSET;
148 else if (r[0].diff < -RC_PID_NORM_OFFSET)
149 r[0].diff += RC_PID_NORM_OFFSET;
150 for (i = 0; i < l - 1; i++)
151 if (r[i + 1].diff > r[i].diff + RC_PID_NORM_OFFSET)
152 r[i + 1].diff -= RC_PID_NORM_OFFSET;
153 else if (r[i + 1].diff <= r[i].diff)
154 r[i + 1].diff += RC_PID_NORM_OFFSET;
157 static void rate_control_pid_sample(struct rc_pid_info *pinfo,
158 struct ieee80211_local *local,
159 struct sta_info *sta)
161 struct rc_pid_sta_info *spinfo = sta->rate_ctrl_priv;
162 struct rc_pid_rateinfo *rinfo = pinfo->rinfo;
163 struct ieee80211_hw_mode *mode;
171 mode = local->oper_hw_mode;
172 spinfo = sta->rate_ctrl_priv;
174 /* In case nothing happened during the previous control interval, turn
175 * the sharpening factor on. */
176 if (jiffies - spinfo->last_sample > 2 * RC_PID_INTERVAL)
177 spinfo->sharp_cnt = RC_PID_SHARPENING_DURATION;
179 spinfo->last_sample = jiffies;
181 /* This should never happen, but in case, we assume the old sample is
182 * still a good measurement and copy it. */
183 if (unlikely(spinfo->tx_num_xmit == 0))
184 pf = spinfo->last_pf;
186 pf = spinfo->tx_num_failed * 100 / spinfo->tx_num_xmit;
187 pf <<= RC_PID_ARITH_SHIFT;
190 spinfo->tx_num_xmit = 0;
191 spinfo->tx_num_failed = 0;
193 /* If we just switched rate, update the rate behaviour info. */
194 if (pinfo->oldrate != sta->txrate) {
196 i = rinfo[pinfo->oldrate].rev_index;
197 j = rinfo[sta->txrate].rev_index;
199 tmp = (pf - spinfo->last_pf);
200 tmp = RC_PID_DO_ARITH_RIGHT_SHIFT(tmp, RC_PID_ARITH_SHIFT);
202 rinfo[j].diff = rinfo[i].diff + tmp;
203 pinfo->oldrate = sta->txrate;
205 rate_control_pid_normalize(rinfo, mode->num_rates);
207 /* Compute the proportional, integral and derivative errors. */
208 err_prop = RC_PID_TARGET_PF - pf;
210 err_avg = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT;
211 spinfo->err_avg_sc = spinfo->err_avg_sc - err_avg + err_prop;
212 err_int = spinfo->err_avg_sc >> RC_PID_SMOOTHING_SHIFT;
214 err_der = pf - spinfo->last_pf
215 * (1 + RC_PID_SHARPENING_FACTOR * spinfo->sharp_cnt);
216 spinfo->last_pf = pf;
217 if (spinfo->sharp_cnt)
220 #ifdef CONFIG_MAC80211_DEBUGFS
221 rate_control_pid_event_pf_sample(&spinfo->events, pf, err_prop, err_int,
225 /* Compute the controller output. */
226 adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i
227 + err_der * pinfo->coeff_d);
228 adj = RC_PID_DO_ARITH_RIGHT_SHIFT(adj, 2 * RC_PID_ARITH_SHIFT);
232 rate_control_pid_adjust_rate(local, sta, adj, rinfo);
235 static void rate_control_pid_tx_status(void *priv, struct net_device *dev,
237 struct ieee80211_tx_status *status)
239 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
240 struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
241 struct rc_pid_info *pinfo = priv;
242 struct sta_info *sta;
243 struct rc_pid_sta_info *spinfo;
245 sta = sta_info_get(local, hdr->addr1);
250 /* Ignore all frames that were sent with a different rate than the rate
251 * we currently advise mac80211 to use. */
252 if (status->control.rate != &local->oper_hw_mode->rates[sta->txrate])
255 spinfo = sta->rate_ctrl_priv;
256 spinfo->tx_num_xmit++;
258 #ifdef CONFIG_MAC80211_DEBUGFS
259 rate_control_pid_event_tx_status(&spinfo->events, status);
262 /* We count frames that totally failed to be transmitted as two bad
263 * frames, those that made it out but had some retries as one good and
265 if (status->excessive_retries) {
266 spinfo->tx_num_failed += 2;
267 spinfo->tx_num_xmit++;
268 } else if (status->retry_count) {
269 spinfo->tx_num_failed++;
270 spinfo->tx_num_xmit++;
273 if (status->excessive_retries) {
274 sta->tx_retry_failed++;
275 sta->tx_num_consecutive_failures++;
276 sta->tx_num_mpdu_fail++;
278 sta->last_ack_rssi[0] = sta->last_ack_rssi[1];
279 sta->last_ack_rssi[1] = sta->last_ack_rssi[2];
280 sta->last_ack_rssi[2] = status->ack_signal;
281 sta->tx_num_consecutive_failures = 0;
282 sta->tx_num_mpdu_ok++;
284 sta->tx_retry_count += status->retry_count;
285 sta->tx_num_mpdu_fail += status->retry_count;
287 /* Update PID controller state. */
288 if (time_after(jiffies, spinfo->last_sample + RC_PID_INTERVAL))
289 rate_control_pid_sample(pinfo, local, sta);
294 static void rate_control_pid_get_rate(void *priv, struct net_device *dev,
295 struct ieee80211_hw_mode *mode,
297 struct rate_selection *sel)
299 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
300 struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
301 struct sta_info *sta;
304 sta = sta_info_get(local, hdr->addr1);
307 sel->rate = rate_lowest(local, mode, NULL);
312 rateidx = sta->txrate;
314 if (rateidx >= mode->num_rates)
315 rateidx = mode->num_rates - 1;
319 sel->rate = &mode->rates[rateidx];
321 #ifdef CONFIG_MAC80211_DEBUGFS
322 rate_control_pid_event_tx_rate(
323 &((struct rc_pid_sta_info *) sta->rate_ctrl_priv)->events,
324 rateidx, mode->rates[rateidx].rate);
328 static void rate_control_pid_rate_init(void *priv, void *priv_sta,
329 struct ieee80211_local *local,
330 struct sta_info *sta)
332 /* TODO: This routine should consider using RSSI from previous packets
333 * as we need to have IEEE 802.1X auth succeed immediately after assoc..
334 * Until that method is implemented, we will use the lowest supported
335 * rate as a workaround. */
336 sta->txrate = rate_lowest_index(local, local->oper_hw_mode, sta);
339 static void *rate_control_pid_alloc(struct ieee80211_local *local)
341 struct rc_pid_info *pinfo;
342 struct rc_pid_rateinfo *rinfo;
343 struct ieee80211_hw_mode *mode;
347 pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC);
351 /* We can safely assume that oper_hw_mode won't change unless we get
353 mode = local->oper_hw_mode;
354 rinfo = kmalloc(sizeof(*rinfo) * mode->num_rates, GFP_ATOMIC);
360 /* Sort the rates. This is optimized for the most common case (i.e.
361 * almost-sorted CCK+OFDM rates). Kind of bubble-sort with reversed
363 for (i = 0; i < mode->num_rates; i++) {
365 rinfo[i].rev_index = i;
366 if (RC_PID_FAST_START)
369 rinfo[i].diff = i * RC_PID_NORM_OFFSET;
371 for (i = 1; i < mode->num_rates; i++) {
373 for (j = 0; j < mode->num_rates - i; j++)
374 if (unlikely(mode->rates[rinfo[j].index].rate >
375 mode->rates[rinfo[j + 1].index].rate)) {
376 tmp = rinfo[j].index;
377 rinfo[j].index = rinfo[j + 1].index;
378 rinfo[j + 1].index = tmp;
379 rinfo[rinfo[j].index].rev_index = j;
380 rinfo[rinfo[j + 1].index].rev_index = j + 1;
387 pinfo->target = RC_PID_TARGET_PF;
388 pinfo->coeff_p = RC_PID_COEFF_P;
389 pinfo->coeff_i = RC_PID_COEFF_I;
390 pinfo->coeff_d = RC_PID_COEFF_D;
391 pinfo->rinfo = rinfo;
397 static void rate_control_pid_free(void *priv)
399 struct rc_pid_info *pinfo = priv;
404 static void rate_control_pid_clear(void *priv)
408 static void *rate_control_pid_alloc_sta(void *priv, gfp_t gfp)
410 struct rc_pid_sta_info *spinfo;
412 spinfo = kzalloc(sizeof(*spinfo), gfp);
416 #ifdef CONFIG_MAC80211_DEBUGFS
417 spin_lock_init(&spinfo->events.lock);
418 init_waitqueue_head(&spinfo->events.waitqueue);
424 static void rate_control_pid_free_sta(void *priv, void *priv_sta)
426 struct rc_pid_sta_info *spinfo = priv_sta;
430 struct rate_control_ops mac80211_rcpid = {
432 .tx_status = rate_control_pid_tx_status,
433 .get_rate = rate_control_pid_get_rate,
434 .rate_init = rate_control_pid_rate_init,
435 .clear = rate_control_pid_clear,
436 .alloc = rate_control_pid_alloc,
437 .free = rate_control_pid_free,
438 .alloc_sta = rate_control_pid_alloc_sta,
439 .free_sta = rate_control_pid_free_sta,
440 #ifdef CONFIG_MAC80211_DEBUGFS
441 .add_sta_debugfs = rate_control_pid_add_sta_debugfs,
442 .remove_sta_debugfs = rate_control_pid_remove_sta_debugfs,