1 /* 2 * Simple 802.11 rate-control algorithm for gPXE. 3 * 4 * Copyright (c) 2009 Joshua Oreman <oremanj (at) 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 } 372
