iPXE
rc80211.c
Go to the documentation of this file.
1 /*
2  * Simple 802.11 rate-control algorithm for iPXE.
3  *
4  * Copyright (c) 2009 Joshua Oreman <oremanj@rwcr.net>.
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License as
8  * published by the Free Software Foundation; either version 2 of the
9  * License, or any later version.
10  *
11  * This program is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19  * 02110-1301, USA.
20  */
21 
22 FILE_LICENCE ( GPL2_OR_LATER );
23 
24 #include <stdlib.h>
25 #include <ipxe/net80211.h>
26 
27 /**
28  * @file
29  *
30  * Simple 802.11 rate-control algorithm
31  */
32 
33 /** @page rc80211 Rate control philosophy
34  *
35  * We want to maximize our transmission speed, to the extent that we
36  * can do that without dropping undue numbers of packets. We also
37  * don't want to take up very much code space, so our algorithm has to
38  * be pretty simple
39  *
40  * When we receive a packet, we know what rate it was transmitted at,
41  * and whether it had to be retransmitted to get to us.
42  *
43  * When we send a packet, we hear back how many times it had to be
44  * retried to get through, and whether it got through at all.
45  *
46  * Indications of TX success are more reliable than RX success, but RX
47  * information helps us know where to start.
48  *
49  * To handle all of this, we keep for each rate and each direction (TX
50  * and RX separately) some state information for the most recent
51  * packets on that rate and the number of packets for which we have
52  * information. The state is a 32-bit unsigned integer in which two
53  * bits represent a packet: 11 if it went through well, 10 if it went
54  * through with one retry, 01 if it went through with more than one
55  * retry, or 00 if it didn't go through at all. We define the
56  * "goodness" for a particular (rate, direction) combination as the
57  * sum of all the 2-bit fields, times 33, divided by the number of
58  * 2-bit fields containing valid information (16 except when we're
59  * starting out). The number produced is between 0 and 99; we use -1
60  * for rates with less than 4 RX packets or 1 TX, as an indicator that
61  * we do not have enough information to rely on them.
62  *
63  * In deciding which rates are best, we find the weighted average of
64  * TX and RX goodness, where the weighting is by number of packets
65  * with data and TX packets are worth 4 times as much as RX packets.
66  * The weighted average is called "net goodness" and is also a number
67  * between 0 and 99. If 3 consecutive packets fail transmission
68  * outright, we automatically ratchet down the rate; otherwise, we
69  * switch to the best rate whenever the current rate's goodness falls
70  * below some threshold, and try increasing our rate when the goodness
71  * is very high.
72  *
73  * This system is optimized for iPXE's style of usage. Because normal
74  * operation always involves receiving something, we'll make our way
75  * to the best rate pretty quickly. We tend to follow the lead of the
76  * sending AP in choosing rates, but we won't use rates for long that
77  * don't work well for us in transmission. We assume iPXE won't be
78  * running for long enough that rate patterns will change much, so we
79  * don't have to keep time counters or the like. And if this doesn't
80  * work well in practice there are many ways it could be tweaked.
81  *
82  * To avoid staying at 1Mbps for a long time, we don't track any
83  * transmitted packets until we've set our rate based on received
84  * packets.
85  */
86 
87 /** Two-bit packet status indicator for a packet with no retries */
88 #define RC_PKT_OK 0x3
89 
90 /** Two-bit packet status indicator for a packet with one retry */
91 #define RC_PKT_RETRIED_ONCE 0x2
92 
93 /** Two-bit packet status indicator for a TX packet with multiple retries
94  *
95  * It is not possible to tell whether an RX packet had one or multiple
96  * retries; we rely instead on the fact that failed RX packets won't
97  * get to us at all, so if we receive a lot of RX packets on a certain
98  * rate it must be pretty good.
99  */
100 #define RC_PKT_RETRIED_MULTI 0x1
101 
102 /** Two-bit packet status indicator for a TX packet that was never ACKed
103  *
104  * It is not possible to tell whether an RX packet was setn if it
105  * didn't get through to us, but if we don't see one we won't increase
106  * the goodness for its rate. This asymmetry is part of why TX packets
107  * are weighted much more heavily than RX.
108  */
109 #define RC_PKT_FAILED 0x0
110 
111 /** Number of times to weight TX packets more heavily than RX packets */
112 #define RC_TX_FACTOR 4
113 
114 /** Number of consecutive failed TX packets that cause an automatic rate drop */
115 #define RC_TX_EMERG_FAIL 3
116 
117 /** Minimum net goodness below which we will search for a better rate */
118 #define RC_GOODNESS_MIN 85
119 
120 /** Maximum net goodness above which we will try to increase our rate */
121 #define RC_GOODNESS_MAX 95
122 
123 /** Minimum (num RX + @c RC_TX_FACTOR * num TX) to use a certain rate */
124 #define RC_UNCERTAINTY_THRESH 4
125 
126 /** TX direction */
127 #define TX 0
128 
129 /** RX direction */
130 #define RX 1
131 
132 /** A rate control context */
134 {
135  /** Goodness state for each rate, TX and RX */
137 
138  /** Number of packets recorded for each rate */
140 
141  /** Indication of whether we've set the device rate yet */
142  int started;
143 
144  /** Counter of all packets sent and received */
145  int packets;
146 };
147 
148 /**
149  * Initialize rate-control algorithm
150  *
151  * @v dev 802.11 device
152  * @ret ctx Rate-control context, to be stored in @c dev->rctl
153  */
155 {
156  struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
157  return ret;
158 }
159 
160 /**
161  * Calculate net goodness for a certain rate
162  *
163  * @v ctx Rate-control context
164  * @v rate_idx Index of rate to calculate net goodness for
165  */
167  int rate_idx )
168 {
169  int sum[2], num[2], dir, pkt;
170 
171  for ( dir = 0; dir < 2; dir++ ) {
172  u32 good = ctx->goodness[dir][rate_idx];
173 
174  num[dir] = ctx->count[dir][rate_idx];
175  sum[dir] = 0;
176 
177  for ( pkt = 0; pkt < num[dir]; pkt++ )
178  sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3;
179  }
180 
181  if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH )
182  return -1;
183 
184  return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) /
185  ( num[TX] * RC_TX_FACTOR + num[RX] ) );
186 }
187 
188 /**
189  * Determine the best rate to switch to and return it
190  *
191  * @v dev 802.11 device
192  * @ret rate_idx Index of the best rate to switch to
193  */
194 static int rc80211_pick_best ( struct net80211_device *dev )
195 {
196  struct rc80211_ctx *ctx = dev->rctl;
197  int best_net_good = 0, best_rate = -1, i;
198 
199  for ( i = 0; i < dev->nr_rates; i++ ) {
200  int net_good = rc80211_calc_net_goodness ( ctx, i );
201 
202  if ( net_good > best_net_good ||
203  ( best_net_good > RC_GOODNESS_MIN &&
204  net_good > RC_GOODNESS_MIN ) ) {
205  best_net_good = net_good;
206  best_rate = i;
207  }
208  }
209 
210  if ( best_rate >= 0 ) {
211  int old_good = rc80211_calc_net_goodness ( ctx, dev->rate );
212  if ( old_good != best_net_good )
213  DBGC ( ctx, "802.11 RC %p switching from goodness "
214  "%d to %d\n", ctx, old_good, best_net_good );
215 
216  ctx->started = 1;
217  return best_rate;
218  }
219 
220  return dev->rate;
221 }
222 
223 /**
224  * Set 802.11 device rate
225  *
226  * @v dev 802.11 device
227  * @v rate_idx Index of rate to switch to
228  *
229  * This is a thin wrapper around net80211_set_rate_idx to insert a
230  * debugging message where appropriate.
231  */
232 static inline void rc80211_set_rate ( struct net80211_device *dev,
233  int rate_idx )
234 {
235  DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl,
236  dev->rates[dev->rate] / 10, dev->rates[rate_idx] / 10 );
237 
238  net80211_set_rate_idx ( dev, rate_idx );
239 }
240 
241 /**
242  * Check rate-control state and change rate if necessary
243  *
244  * @v dev 802.11 device
245  */
246 static void rc80211_maybe_set_new ( struct net80211_device *dev )
247 {
248  struct rc80211_ctx *ctx = dev->rctl;
249  int net_good;
250 
251  net_good = rc80211_calc_net_goodness ( ctx, dev->rate );
252 
253  if ( ! ctx->started ) {
254  rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
255  return;
256  }
257 
258  if ( net_good < 0 ) /* insufficient data */
259  return;
260 
261  if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) {
262  int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 );
263  if ( higher > net_good || higher < 0 )
264  rc80211_set_rate ( dev, dev->rate + 1 );
265  else
266  rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
267  }
268 
269  if ( net_good < RC_GOODNESS_MIN ) {
270  rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
271  }
272 }
273 
274 /**
275  * Update rate-control state
276  *
277  * @v dev 802.11 device
278  * @v direction One of the direction constants TX or RX
279  * @v rate_idx Index of rate at which packet was sent or received
280  * @v retries Number of times packet was retried before success
281  * @v failed If nonzero, the packet failed to get through
282  */
283 static void rc80211_update ( struct net80211_device *dev, int direction,
284  int rate_idx, int retries, int failed )
285 {
286  struct rc80211_ctx *ctx = dev->rctl;
287  u32 goodness = ctx->goodness[direction][rate_idx];
288 
289  if ( ctx->count[direction][rate_idx] < 16 )
290  ctx->count[direction][rate_idx]++;
291 
292  goodness <<= 2;
293  if ( failed )
295  else if ( retries > 1 )
297  else if ( retries )
299  else
300  goodness |= RC_PKT_OK;
301 
302  ctx->goodness[direction][rate_idx] = goodness;
303 
304  ctx->packets++;
305 
306  rc80211_maybe_set_new ( dev );
307 }
308 
309 /**
310  * Update rate-control state for transmitted packet
311  *
312  * @v dev 802.11 device
313  * @v retries Number of times packet was transmitted before success
314  * @v rc Return status code for transmission
315  */
316 void rc80211_update_tx ( struct net80211_device *dev, int retries, int rc )
317 {
318  struct rc80211_ctx *ctx = dev->rctl;
319 
320  if ( ! ctx->started )
321  return;
322 
323  rc80211_update ( dev, TX, dev->rate, retries, rc );
324 
325  /* Check if the last RC_TX_EMERG_FAIL packets have all failed */
326  if ( ! ( ctx->goodness[TX][dev->rate] &
327  ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) {
328  if ( dev->rate == 0 )
329  DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive "
330  "failed TX, but cannot lower rate any further\n",
331  dev->rctl, RC_TX_EMERG_FAIL );
332  else {
333  DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d "
334  "Mbps) due to %d consecutive TX failures\n",
335  dev->rctl, dev->rates[dev->rate] / 10,
336  dev->rates[dev->rate - 1] / 10,
338 
339  rc80211_set_rate ( dev, dev->rate - 1 );
340  }
341  }
342 }
343 
344 /**
345  * Update rate-control state for received packet
346  *
347  * @v dev 802.11 device
348  * @v retry Whether the received packet had been retransmitted
349  * @v rate Rate at which packet was received, in 100 kbps units
350  */
351 void rc80211_update_rx ( struct net80211_device *dev, int retry, u16 rate )
352 {
353  int ridx;
354 
355  for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate;
356  ridx++ )
357  ;
358  if ( ridx >= dev->nr_rates )
359  return; /* couldn't find the rate */
360 
361  rc80211_update ( dev, RX, ridx, retry, 0 );
362 }
363 
364 /**
365  * Free rate-control context
366  *
367  * @v ctx Rate-control context
368  */
369 void rc80211_free ( struct rc80211_ctx *ctx )
370 {
371  free ( ctx );
372 }
uint16_t u16
Definition: stdint.h:21
static void rc80211_maybe_set_new(struct net80211_device *dev)
Check rate-control state and change rate if necessary.
Definition: rc80211.c:246
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
static int rc80211_pick_best(struct net80211_device *dev)
Determine the best rate to switch to and return it.
Definition: rc80211.c:194
static void rc80211_update(struct net80211_device *dev, int direction, int rate_idx, int retries, int failed)
Update rate-control state.
Definition: rc80211.c:283
static int rc80211_calc_net_goodness(struct rc80211_ctx *ctx, int rate_idx)
Calculate net goodness for a certain rate.
Definition: rc80211.c:166
#define RC_PKT_FAILED
Two-bit packet status indicator for a TX packet that was never ACKed.
Definition: rc80211.c:109
#define RX
RX direction.
Definition: rc80211.c:130
#define DBGC(...)
Definition: compiler.h:505
uint8_t direction
Direction.
Definition: ena.h:14
int packets
Counter of all packets sent and received.
Definition: rc80211.c:145
void rc80211_update_tx(struct net80211_device *dev, int retries, int rc)
Update rate-control state for transmitted packet.
Definition: rc80211.c:316
#define RC_PKT_RETRIED_MULTI
Two-bit packet status indicator for a TX packet with multiple retries.
Definition: rc80211.c:100
int started
Indication of whether we've set the device rate yet.
Definition: rc80211.c:142
A rate control context.
Definition: rc80211.c:133
void net80211_set_rate_idx(struct net80211_device *dev, int rate)
Set data transmission rate for 802.11 device.
Definition: net80211.c:2000
#define RC_PKT_RETRIED_ONCE
Two-bit packet status indicator for a packet with one retry.
Definition: rc80211.c:91
struct rc80211_ctx * rctl
Rate control state.
Definition: net80211.h:989
u32 goodness[2][NET80211_MAX_RATES]
Goodness state for each rate, TX and RX.
Definition: rc80211.c:136
#define RC_TX_EMERG_FAIL
Number of consecutive failed TX packets that cause an automatic rate drop.
Definition: rc80211.c:115
char unsigned long * num
Definition: xenstore.h:17
u8 nr_rates
The number of transmission rates in the rates array.
Definition: net80211.h:821
static void(* free)(struct refcnt *refcnt))
Definition: refcnt.h:54
void * zalloc(size_t size)
Allocate cleared memory.
Definition: malloc.c:624
The iPXE 802.11 MAC layer.
Structure encapsulating the complete state of an 802.11 device.
Definition: net80211.h:786
struct golan_eq_context ctx
Definition: CIB_PRM.h:28
#define RC_TX_FACTOR
Number of times to weight TX packets more heavily than RX packets.
Definition: rc80211.c:112
u16 rates[NET80211_MAX_RATES]
A list of all possible TX rates we might use.
Definition: net80211.h:818
struct rc80211_ctx * rc80211_init(struct net80211_device *dev __unused)
Initialize rate-control algorithm.
Definition: rc80211.c:154
FILE_LICENCE(GPL2_OR_LATER)
void rc80211_free(struct rc80211_ctx *ctx)
Free rate-control context.
Definition: rc80211.c:369
#define RC_PKT_OK
Two-bit packet status indicator for a packet with no retries.
Definition: rc80211.c:88
#define __unused
Declare a variable or data structure as unused.
Definition: compiler.h:573
#define NET80211_MAX_RATES
The maximum number of TX rates we allow to be configured simultaneously.
Definition: net80211.h:272
#define RC_UNCERTAINTY_THRESH
Minimum (num RX + RC_TX_FACTOR * num TX) to use a certain rate.
Definition: rc80211.c:124
#define TX
TX direction.
Definition: rc80211.c:127
static void rc80211_set_rate(struct net80211_device *dev, int rate_idx)
Set 802.11 device rate.
Definition: rc80211.c:232
#define RC_GOODNESS_MIN
Minimum net goodness below which we will search for a better rate.
Definition: rc80211.c:118
u8 rate
The rate currently in use, as an index into the rates array.
Definition: net80211.h:824
uint8_t u8
Definition: stdint.h:19
uint32_t u32
Definition: stdint.h:23
#define RC_GOODNESS_MAX
Maximum net goodness above which we will try to increase our rate.
Definition: rc80211.c:121
u8 count[2][NET80211_MAX_RATES]
Number of packets recorded for each rate.
Definition: rc80211.c:139
void rc80211_update_rx(struct net80211_device *dev, int retry, u16 rate)
Update rate-control state for received packet.
Definition: rc80211.c:351