[802.11] Add support for 802.11 devices with software MAC layer
[people/oremanj/gpxe.git] / src / net / 80211 / rc80211.c
1 /*
2  * Simple 802.11 rate-control algorithm for gPXE.
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., 675 Mass Ave, Cambridge, MA 02139, USA.
19  */
20
21 FILE_LICENCE ( GPL2_OR_LATER );
22
23 #include <stdlib.h>
24 #include <gpxe/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 gPXE'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 gPXE 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 }