[802.11] Add rate control support; fix two bugs; remove high rate bits
[people/oremanj/gpxe.git] / src / net / 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  * Rate control philosophy:
28  *
29  * We want to maximize our transmission speed, to the extent that we
30  * can do that without dropping undue numbers of packets. We also
31  * don't want to take up very much code space, so our algorithm has to
32  * be pretty simple
33  *
34  * When we receive a packet, we know what rate it was transmitted at,
35  * and whether it had to be retransmitted to get to us.
36  *
37  * When we send a packet, we hear back how many times it had to be
38  * retried to get through, and whether it got through at all.
39  *
40  * Indications of TX success are more reliable than RX success, but RX
41  * information helps us know where to start.
42  *
43  * To handle all of this, we keep for each rate and each direction (TX
44  * and RX separately) some "goodness" information for the most recent
45  * packets on that rate and the number of packets for which we have
46  * information. The "goodness" indicator is a 32-bit unsigned integer
47  * in which two bits represent a packet: 11 if it went through well,
48  * 10 if it went through with one retry, 01 if it went through with
49  * more than one retry, or 00 if it didn't go through at all. The
50  * goodness is the sum of all the 2-bit fields divided by the number
51  * of them that contain valid data (eventually 16, but less when we're
52  * starting out). It's measured as a percent.
53  *
54  * In deciding which rates are best, we find the weighted average of
55  * TX and RX goodness, where the weighting is by number of packets
56  * with data and TX packets are worth 4 times as much as RX packets.
57  * If 3 consecutive packets fail transmission outright, we
58  * automatically ratchet down the rate; otherwise, we switch to the
59  * best rate whenever the current rate's goodness falls below some
60  * threshold, and try increasing our rate when the goodness is really
61  * high.
62  *
63  * This system is optimized for gPXE's style of usage. Because normal
64  * operation always involves receiving something, we'll make our way
65  * to the best rate pretty quickly. We tend to follow the lead of the
66  * sending AP in choosing rates, but we won't use rates for long that
67  * have asymmetry properties in the current environment. We assume
68  * gPXE won't be running for long enough that rate patterns will
69  * change much, so we don't have to keep time counters or the like.
70  * And if this doesn't work well in practice there are many ways it
71  * could be tweaked.
72  *
73  * To avoid staying at 1Mbps for a long time, we don't track any
74  * transmitted packets until we've set our rate based on received
75  * packets. 
76  */
77
78 #define RC_PKT_OK               0x3
79 #define RC_PKT_RETRIED_ONCE     0x2
80 #define RC_PKT_RETRIED_MULTI    0x1
81 #define RC_PKT_FAILED           0x0
82
83 #define RC_TX_FACTOR            4
84 #define RC_TX_EMERG_FAIL        3
85
86 #define RC_GOODNESS_MIN         85
87 #define RC_GOODNESS_MAX         95
88
89 #define RC_UNCERTAINTY_THRESH   4
90
91 #define TX      0
92 #define RX      1
93
94 /** A rate control context */
95 struct rc80211_ctx 
96 {
97         /** Goodness state for each rate, TX and RX */
98         u32 goodness[2][NET80211_MAX_RATES];
99
100         /** Number of packets recorded for each rate */
101         u8 count[2][NET80211_MAX_RATES];
102
103         /** Indication of whether we've set the device rate yet */
104         int started;
105
106         /** Counter of all packets sent and received */
107         int packets;
108 };
109
110 struct rc80211_ctx * rc80211_init ( struct net80211_device *dev __unused )
111 {
112         struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
113         return ret;
114 }
115
116 static int rc80211_calc_net_goodness ( struct rc80211_ctx *ctx,
117                                        int rate_idx )
118 {
119         int sum[2], num[2], dir, pkt;
120
121         for ( dir = 0; dir < 2; dir++ ) {
122                 u32 good = ctx->goodness[dir][rate_idx];
123
124                 num[dir] = ctx->count[dir][rate_idx];
125                 sum[dir] = 0;
126
127                 for ( pkt = 0; pkt < num[dir]; pkt++ )
128                         sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3;
129         }
130
131         if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH )
132                 return -1;
133
134         return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) /
135                       ( num[TX] * RC_TX_FACTOR + num[RX] ) );
136 }
137
138 /* rc80211_pick_best => set 'started' */
139
140 static int rc80211_pick_best ( struct net80211_device *dev )
141 {
142         struct rc80211_ctx *ctx = dev->rctl;
143         int best_net_good = 0, best_rate = -1, i;
144
145         for ( i = 0; i < dev->nr_rates; i++ ) {
146                 int net_good = rc80211_calc_net_goodness ( ctx, i );
147
148                 if ( net_good > best_net_good ||
149                      ( best_net_good > RC_GOODNESS_MIN &&
150                        net_good > RC_GOODNESS_MIN ) ) {
151                         best_net_good = net_good;
152                         best_rate = i;
153                 }
154         }
155
156         if ( best_rate >= 0 ) {
157                 int old_good = rc80211_calc_net_goodness ( ctx, dev->rate );
158                 if ( old_good != best_net_good )
159                         DBGC ( ctx, "802.11 RC %p switching from goodness "
160                                "%d to %d\n", ctx, old_good, best_net_good );
161
162                 ctx->started = 1;
163                 return best_rate;
164         }
165
166         return dev->rate;
167 }
168
169 static inline void rc80211_set_rate ( struct net80211_device *dev,
170                                       int rate )
171 {
172         DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl,
173                dev->rates[dev->rate] / 10, dev->rates[rate] / 10 );
174
175         net80211_set_rate_idx ( dev, rate );
176 }
177
178 static void rc80211_maybe_set_new ( struct net80211_device *dev )
179 {
180         struct rc80211_ctx *ctx = dev->rctl;
181         int net_good;
182
183         net_good = rc80211_calc_net_goodness ( ctx, dev->rate );
184
185         if ( ! ctx->started ) {
186                 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
187                 return;
188         }
189
190         if ( net_good < 0 )     /* insufficient data */
191                 return;
192
193         if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) {
194                 int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 );
195                 if ( higher > net_good || higher < 0 )
196                         rc80211_set_rate ( dev, dev->rate + 1 );
197                 else
198                         rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
199         }
200
201         if ( net_good < RC_GOODNESS_MIN ) {
202                 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
203         }
204 }
205
206 static void rc80211_update ( struct net80211_device *dev, int direction,
207                              int rate_idx, int retries, int failed ) 
208 {
209         struct rc80211_ctx *ctx = dev->rctl;
210         u32 goodness = ctx->goodness[direction][rate_idx];
211
212         if ( ctx->count[direction][rate_idx] < 16 )
213                 ctx->count[direction][rate_idx]++;
214
215         goodness <<= 2;
216         if ( failed )
217                 goodness |= RC_PKT_FAILED;
218         else if ( retries > 1 )
219                 goodness |= RC_PKT_RETRIED_MULTI;
220         else if ( retries )
221                 goodness |= RC_PKT_RETRIED_ONCE;
222         else
223                 goodness |= RC_PKT_OK;
224
225         ctx->goodness[direction][rate_idx] = goodness;
226
227         ctx->packets++;
228
229         rc80211_maybe_set_new ( dev );
230 }
231
232 void rc80211_update_tx ( struct net80211_device *dev, int retries, int rc )
233 {
234         struct rc80211_ctx *ctx = dev->rctl;
235
236         if ( ! ctx->started )
237                 return;
238
239         rc80211_update ( dev, TX, dev->rate, retries, rc );
240
241         /* Check if the last RC_TX_EMERG_FAIL packets have all failed */
242         if ( ! ( ctx->goodness[TX][dev->rate] &
243                  ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) {
244                 if ( dev->rate == 0 )
245                         DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive "
246                                "failed TX, but cannot lower rate any further\n",
247                                dev->rctl, RC_TX_EMERG_FAIL );
248                 else {
249                         DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d "
250                                "Mbps) due to %d consecutive TX failures\n",
251                                dev->rctl, dev->rates[dev->rate] / 10,
252                                dev->rates[dev->rate - 1] / 10,
253                                RC_TX_EMERG_FAIL );
254
255                         rc80211_set_rate ( dev, dev->rate - 1 );
256                 }
257         }
258 }
259
260 void rc80211_update_rx ( struct net80211_device *dev, int retry, u16 rate )
261 {
262         int ridx;
263
264         for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate;
265               ridx++ )
266                 ;
267         if ( ridx >= dev->nr_rates )
268                 return;         /* couldn't find the rate */
269
270         rc80211_update ( dev, RX, ridx, retry, 0 );
271 }
272
273 void rc80211_free ( struct rc80211_ctx *ctx )
274 {
275         free ( ctx );
276 }