aboutsummaryrefslogtreecommitdiffstats
path: root/net/mac80211
diff options
context:
space:
mode:
authorStefano Brivio <stefano.brivio@polimi.it>2007-12-18 19:26:34 -0500
committerDavid S. Miller <davem@davemloft.net>2008-01-28 17:59:42 -0500
commit90d501d610c0065dce43120c26744a49d8e0490c (patch)
tree4a452627ae56eb3fdc81a7a1f8cf8fa951274783 /net/mac80211
parentc21b39aca4f8f4975784e54cd3a1b80bab80dcc0 (diff)
rc80211-pid: add rate behaviour learning algorithm
This patch introduces a learning algorithm in order for the PID controller to learn how to map adjustment values to rates. This is better described in code comments. Signed-off-by: Stefano Brivio <stefano.brivio@polimi.it> Signed-off-by: John W. Linville <linville@tuxdriver.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/mac80211')
-rw-r--r--net/mac80211/rc80211_pid.c181
1 files changed, 161 insertions, 20 deletions
diff --git a/net/mac80211/rc80211_pid.c b/net/mac80211/rc80211_pid.c
index b358824b5ac..1116dc67ddd 100644
--- a/net/mac80211/rc80211_pid.c
+++ b/net/mac80211/rc80211_pid.c
@@ -2,6 +2,7 @@
2 * Copyright 2002-2005, Instant802 Networks, Inc. 2 * Copyright 2002-2005, Instant802 Networks, Inc.
3 * Copyright 2005, Devicescape Software, Inc. 3 * Copyright 2005, Devicescape Software, Inc.
4 * Copyright 2007, Mattias Nissler <mattias.nissler@gmx.de> 4 * Copyright 2007, Mattias Nissler <mattias.nissler@gmx.de>
5 * Copyright 2007, Stefano Brivio <stefano.brivio@polimi.it>
5 * 6 *
6 * This program is free software; you can redistribute it and/or modify 7 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 as 8 * it under the terms of the GNU General Public License version 2 as
@@ -39,12 +40,18 @@
39 * an actual sliding window. The advantage is that we don't need to keep an 40 * an actual sliding window. The advantage is that we don't need to keep an
40 * array of the last N error values and computation is easier. 41 * array of the last N error values and computation is easier.
41 * 42 *
42 * Once we have the adj value, we need to map it to a TX rate to be selected. 43 * Once we have the adj value, we map it to a rate by means of a learning
43 * For now, we depend on the rates to be ordered in a way such that more robust 44 * algorithm. This algorithm keeps the state of the percentual failed frames
44 * rates (i.e. such that exhibit a lower framed failed percentage) come first. 45 * difference between rates. The behaviour of the lowest available rate is kept
45 * E.g. for the 802.11b/g case, we first have the b rates in ascending order, 46 * as a reference value, and every time we switch between two rates, we compute
46 * then the g rates. The adj simply decides the index of the TX rate in the list 47 * the difference between the failed frames each rate exhibited. By doing so,
47 * to switch to (relative to the current TX rate entry). 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.
48 * 55 *
49 * Note that for the computations we use a fixed-point representation to avoid 56 * Note that for the computations we use a fixed-point representation to avoid
50 * floating point arithmetic. Hence, all values are shifted left by 57 * floating point arithmetic. Hence, all values are shifted left by
@@ -78,6 +85,16 @@
78 */ 85 */
79#define RC_PID_TARGET_PF (11 << RC_PID_ARITH_SHIFT) 86#define RC_PID_TARGET_PF (11 << RC_PID_ARITH_SHIFT)
80 87
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
81struct rc_pid_sta_info { 98struct rc_pid_sta_info {
82 unsigned long last_change; 99 unsigned long last_change;
83 unsigned long last_sample; 100 unsigned long last_sample;
@@ -121,6 +138,18 @@ struct rc_pid_sta_info {
121/* Algorithm parameters. We keep them on a per-algorithm approach, so they can 138/* Algorithm parameters. We keep them on a per-algorithm approach, so they can
122 * be tuned individually for each interface. 139 * be tuned individually for each interface.
123 */ 140 */
141struct 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
124struct rc_pid_info { 153struct rc_pid_info {
125 154
126 /* The failed frames percentage target. */ 155 /* The failed frames percentage target. */
@@ -130,15 +159,56 @@ struct rc_pid_info {
130 s32 coeff_p; 159 s32 coeff_p;
131 s32 coeff_i; 160 s32 coeff_i;
132 s32 coeff_d; 161 s32 coeff_d;
162
163 /* Rates information. */
164 struct rc_pid_rateinfo *rinfo;
165
166 /* Index of the last used rate. */
167 int oldrate;
133}; 168};
134 169
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. */
175static 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}
135 204
136static void rate_control_pid_adjust_rate(struct ieee80211_local *local, 205static void rate_control_pid_adjust_rate(struct ieee80211_local *local,
137 struct sta_info *sta, int adj) 206 struct sta_info *sta, int adj,
207 struct rc_pid_rateinfo *rinfo)
138{ 208{
139 struct ieee80211_sub_if_data *sdata; 209 struct ieee80211_sub_if_data *sdata;
140 struct ieee80211_hw_mode *mode; 210 struct ieee80211_hw_mode *mode;
141 int newidx = sta->txrate + adj; 211 int newidx;
142 int maxrate; 212 int maxrate;
143 int back = (adj > 0) ? 1 : -1; 213 int back = (adj > 0) ? 1 : -1;
144 214
@@ -151,10 +221,8 @@ static void rate_control_pid_adjust_rate(struct ieee80211_local *local,
151 mode = local->oper_hw_mode; 221 mode = local->oper_hw_mode;
152 maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1; 222 maxrate = sdata->bss ? sdata->bss->max_ratectrl_rateidx : -1;
153 223
154 if (newidx < 0) 224 newidx = rate_control_pid_shift_adjust(rinfo, adj, sta->txrate,
155 newidx = 0; 225 mode->num_rates);
156 else if (newidx >= mode->num_rates)
157 newidx = mode->num_rates - 1;
158 226
159 while (newidx != sta->txrate) { 227 while (newidx != sta->txrate) {
160 if (rate_supported(sta, mode, newidx) && 228 if (rate_supported(sta, mode, newidx) &&
@@ -167,18 +235,37 @@ static void rate_control_pid_adjust_rate(struct ieee80211_local *local,
167 } 235 }
168} 236}
169 237
238/* Normalize the failed frames per-rate differences. */
239static 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
170static void rate_control_pid_sample(struct rc_pid_info *pinfo, 254static void rate_control_pid_sample(struct rc_pid_info *pinfo,
171 struct ieee80211_local *local, 255 struct ieee80211_local *local,
172 struct sta_info *sta) 256 struct sta_info *sta)
173{ 257{
174 struct rc_pid_sta_info *spinfo = sta->rate_ctrl_priv; 258 struct rc_pid_sta_info *spinfo = sta->rate_ctrl_priv;
259 struct rc_pid_rateinfo *rinfo = pinfo->rinfo;
260 struct ieee80211_hw_mode *mode;
175 u32 pf; 261 u32 pf;
176 s32 err_avg; 262 s32 err_avg;
177 s32 err_prop; 263 s32 err_prop;
178 s32 err_int; 264 s32 err_int;
179 s32 err_der; 265 s32 err_der;
180 int adj; 266 int adj, i, j, tmp;
181 267
268 mode = local->oper_hw_mode;
182 spinfo = sta->rate_ctrl_priv; 269 spinfo = sta->rate_ctrl_priv;
183 spinfo->last_sample = jiffies; 270 spinfo->last_sample = jiffies;
184 271
@@ -194,6 +281,20 @@ static void rate_control_pid_sample(struct rc_pid_info *pinfo,
194 spinfo->tx_num_failed = 0; 281 spinfo->tx_num_failed = 0;
195 } 282 }
196 283
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
197 /* Compute the proportional, integral and derivative errors. */ 298 /* Compute the proportional, integral and derivative errors. */
198 err_prop = RC_PID_TARGET_PF - pf; 299 err_prop = RC_PID_TARGET_PF - pf;
199 300
@@ -207,16 +308,11 @@ static void rate_control_pid_sample(struct rc_pid_info *pinfo,
207 /* Compute the controller output. */ 308 /* Compute the controller output. */
208 adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i 309 adj = (err_prop * pinfo->coeff_p + err_int * pinfo->coeff_i
209 + err_der * pinfo->coeff_d); 310 + err_der * pinfo->coeff_d);
210 311 adj = RC_PID_DO_ARITH_RIGHT_SHIFT(adj, 2 * RC_PID_ARITH_SHIFT);
211 /* We need to do an arithmetic right shift. ISO C says this is
212 * implementation defined for negative left operands. Hence, be
213 * careful to get it right, also for negative values. */
214 adj = (adj < 0) ? -((-adj) >> (2 * RC_PID_ARITH_SHIFT)) :
215 adj >> (2 * RC_PID_ARITH_SHIFT);
216 312
217 /* Change rate. */ 313 /* Change rate. */
218 if (adj) 314 if (adj)
219 rate_control_pid_adjust_rate(local, sta, adj); 315 rate_control_pid_adjust_rate(local, sta, adj, rinfo);
220} 316}
221 317
222static void rate_control_pid_tx_status(void *priv, struct net_device *dev, 318static void rate_control_pid_tx_status(void *priv, struct net_device *dev,
@@ -316,13 +412,57 @@ static void rate_control_pid_rate_init(void *priv, void *priv_sta,
316static void *rate_control_pid_alloc(struct ieee80211_local *local) 412static void *rate_control_pid_alloc(struct ieee80211_local *local)
317{ 413{
318 struct rc_pid_info *pinfo; 414 struct rc_pid_info *pinfo;
415 struct rc_pid_rateinfo *rinfo;
416 struct ieee80211_hw_mode *mode;
417 int i, j, tmp;
418 bool s;
319 419
320 pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC); 420 pinfo = kmalloc(sizeof(*pinfo), GFP_ATOMIC);
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 }
321 459
322 pinfo->target = RC_PID_TARGET_PF; 460 pinfo->target = RC_PID_TARGET_PF;
323 pinfo->coeff_p = RC_PID_COEFF_P; 461 pinfo->coeff_p = RC_PID_COEFF_P;
324 pinfo->coeff_i = RC_PID_COEFF_I; 462 pinfo->coeff_i = RC_PID_COEFF_I;
325 pinfo->coeff_d = RC_PID_COEFF_D; 463 pinfo->coeff_d = RC_PID_COEFF_D;
464 pinfo->rinfo = rinfo;
465 pinfo->oldrate = 0;
326 466
327 return pinfo; 467 return pinfo;
328} 468}
@@ -330,6 +470,7 @@ static void *rate_control_pid_alloc(struct ieee80211_local *local)
330static void rate_control_pid_free(void *priv) 470static void rate_control_pid_free(void *priv)
331{ 471{
332 struct rc_pid_info *pinfo = priv; 472 struct rc_pid_info *pinfo = priv;
473 kfree(pinfo->rinfo);
333 kfree(pinfo); 474 kfree(pinfo);
334} 475}
335 476