src/net/80211/rc80211.c

   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 */
 133 struct rc80211_ctx
 134 {
 135         /** Goodness state for each rate, TX and RX */
 136         u32 goodness[2][NET80211_MAX_RATES];
 137
 138         /** Number of packets recorded for each rate */
 139         u8 count[2][NET80211_MAX_RATES];
 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  */
 154 struct rc80211_ctx * rc80211_init ( struct net80211_device *dev __unused )
 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  */
 166 static int rc80211_calc_net_goodness ( struct rc80211_ctx *ctx,
 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 )
 294                 goodness |= RC_PKT_FAILED;
 295         else if ( retries > 1 )
 296                 goodness |= RC_PKT_RETRIED_MULTI;
 297         else if ( retries )
 298                 goodness |= RC_PKT_RETRIED_ONCE;
 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,
 337                                RC_TX_EMERG_FAIL );
 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 }