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