iPXE
rc80211.c
Go to the documentation of this file.
00001 /*
00002  * Simple 802.11 rate-control algorithm for iPXE.
00003  *
00004  * Copyright (c) 2009 Joshua Oreman <oremanj@rwcr.net>.
00005  *
00006  * This program is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU General Public License as
00008  * published by the Free Software Foundation; either version 2 of the
00009  * License, or any later version.
00010  *
00011  * This program is distributed in the hope that it will be useful, but
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License
00017  * along with this program; if not, write to the Free Software
00018  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00019  * 02110-1301, USA.
00020  */
00021 
00022 FILE_LICENCE ( GPL2_OR_LATER );
00023 
00024 #include <stdlib.h>
00025 #include <ipxe/net80211.h>
00026 
00027 /**
00028  * @file
00029  *
00030  * Simple 802.11 rate-control algorithm
00031  */
00032 
00033 /** @page rc80211 Rate control philosophy
00034  *
00035  * We want to maximize our transmission speed, to the extent that we
00036  * can do that without dropping undue numbers of packets. We also
00037  * don't want to take up very much code space, so our algorithm has to
00038  * be pretty simple
00039  *
00040  * When we receive a packet, we know what rate it was transmitted at,
00041  * and whether it had to be retransmitted to get to us.
00042  *
00043  * When we send a packet, we hear back how many times it had to be
00044  * retried to get through, and whether it got through at all.
00045  *
00046  * Indications of TX success are more reliable than RX success, but RX
00047  * information helps us know where to start.
00048  *
00049  * To handle all of this, we keep for each rate and each direction (TX
00050  * and RX separately) some state information for the most recent
00051  * packets on that rate and the number of packets for which we have
00052  * information. The state is a 32-bit unsigned integer in which two
00053  * bits represent a packet: 11 if it went through well, 10 if it went
00054  * through with one retry, 01 if it went through with more than one
00055  * retry, or 00 if it didn't go through at all. We define the
00056  * "goodness" for a particular (rate, direction) combination as the
00057  * sum of all the 2-bit fields, times 33, divided by the number of
00058  * 2-bit fields containing valid information (16 except when we're
00059  * starting out). The number produced is between 0 and 99; we use -1
00060  * for rates with less than 4 RX packets or 1 TX, as an indicator that
00061  * we do not have enough information to rely on them.
00062  *
00063  * In deciding which rates are best, we find the weighted average of
00064  * TX and RX goodness, where the weighting is by number of packets
00065  * with data and TX packets are worth 4 times as much as RX packets.
00066  * The weighted average is called "net goodness" and is also a number
00067  * between 0 and 99.  If 3 consecutive packets fail transmission
00068  * outright, we automatically ratchet down the rate; otherwise, we
00069  * switch to the best rate whenever the current rate's goodness falls
00070  * below some threshold, and try increasing our rate when the goodness
00071  * is very high.
00072  *
00073  * This system is optimized for iPXE's style of usage. Because normal
00074  * operation always involves receiving something, we'll make our way
00075  * to the best rate pretty quickly. We tend to follow the lead of the
00076  * sending AP in choosing rates, but we won't use rates for long that
00077  * don't work well for us in transmission. We assume iPXE won't be
00078  * running for long enough that rate patterns will change much, so we
00079  * don't have to keep time counters or the like.  And if this doesn't
00080  * work well in practice there are many ways it could be tweaked.
00081  *
00082  * To avoid staying at 1Mbps for a long time, we don't track any
00083  * transmitted packets until we've set our rate based on received
00084  * packets.
00085  */
00086 
00087 /** Two-bit packet status indicator for a packet with no retries */
00088 #define RC_PKT_OK               0x3
00089 
00090 /** Two-bit packet status indicator for a packet with one retry */
00091 #define RC_PKT_RETRIED_ONCE     0x2
00092 
00093 /** Two-bit packet status indicator for a TX packet with multiple retries
00094  *
00095  * It is not possible to tell whether an RX packet had one or multiple
00096  * retries; we rely instead on the fact that failed RX packets won't
00097  * get to us at all, so if we receive a lot of RX packets on a certain
00098  * rate it must be pretty good.
00099  */
00100 #define RC_PKT_RETRIED_MULTI    0x1
00101 
00102 /** Two-bit packet status indicator for a TX packet that was never ACKed
00103  *
00104  * It is not possible to tell whether an RX packet was setn if it
00105  * didn't get through to us, but if we don't see one we won't increase
00106  * the goodness for its rate. This asymmetry is part of why TX packets
00107  * are weighted much more heavily than RX.
00108  */
00109 #define RC_PKT_FAILED           0x0
00110 
00111 /** Number of times to weight TX packets more heavily than RX packets */
00112 #define RC_TX_FACTOR            4
00113 
00114 /** Number of consecutive failed TX packets that cause an automatic rate drop */
00115 #define RC_TX_EMERG_FAIL        3
00116 
00117 /** Minimum net goodness below which we will search for a better rate */
00118 #define RC_GOODNESS_MIN         85
00119 
00120 /** Maximum net goodness above which we will try to increase our rate */
00121 #define RC_GOODNESS_MAX         95
00122 
00123 /** Minimum (num RX + @c RC_TX_FACTOR * num TX) to use a certain rate */
00124 #define RC_UNCERTAINTY_THRESH   4
00125 
00126 /** TX direction */
00127 #define TX      0
00128 
00129 /** RX direction */
00130 #define RX      1
00131 
00132 /** A rate control context */
00133 struct rc80211_ctx
00134 {
00135         /** Goodness state for each rate, TX and RX */
00136         u32 goodness[2][NET80211_MAX_RATES];
00137 
00138         /** Number of packets recorded for each rate */
00139         u8 count[2][NET80211_MAX_RATES];
00140 
00141         /** Indication of whether we've set the device rate yet */
00142         int started;
00143 
00144         /** Counter of all packets sent and received */
00145         int packets;
00146 };
00147 
00148 /**
00149  * Initialize rate-control algorithm
00150  *
00151  * @v dev       802.11 device
00152  * @ret ctx     Rate-control context, to be stored in @c dev->rctl
00153  */
00154 struct rc80211_ctx * rc80211_init ( struct net80211_device *dev __unused )
00155 {
00156         struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
00157         return ret;
00158 }
00159 
00160 /**
00161  * Calculate net goodness for a certain rate
00162  *
00163  * @v ctx       Rate-control context
00164  * @v rate_idx  Index of rate to calculate net goodness for
00165  */
00166 static int rc80211_calc_net_goodness ( struct rc80211_ctx *ctx,
00167                                        int rate_idx )
00168 {
00169         int sum[2], num[2], dir, pkt;
00170 
00171         for ( dir = 0; dir < 2; dir++ ) {
00172                 u32 good = ctx->goodness[dir][rate_idx];
00173 
00174                 num[dir] = ctx->count[dir][rate_idx];
00175                 sum[dir] = 0;
00176 
00177                 for ( pkt = 0; pkt < num[dir]; pkt++ )
00178                         sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3;
00179         }
00180 
00181         if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH )
00182                 return -1;
00183 
00184         return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) /
00185                       ( num[TX] * RC_TX_FACTOR + num[RX] ) );
00186 }
00187 
00188 /**
00189  * Determine the best rate to switch to and return it
00190  *
00191  * @v dev               802.11 device
00192  * @ret rate_idx        Index of the best rate to switch to
00193  */
00194 static int rc80211_pick_best ( struct net80211_device *dev )
00195 {
00196         struct rc80211_ctx *ctx = dev->rctl;
00197         int best_net_good = 0, best_rate = -1, i;
00198 
00199         for ( i = 0; i < dev->nr_rates; i++ ) {
00200                 int net_good = rc80211_calc_net_goodness ( ctx, i );
00201 
00202                 if ( net_good > best_net_good ||
00203                      ( best_net_good > RC_GOODNESS_MIN &&
00204                        net_good > RC_GOODNESS_MIN ) ) {
00205                         best_net_good = net_good;
00206                         best_rate = i;
00207                 }
00208         }
00209 
00210         if ( best_rate >= 0 ) {
00211                 int old_good = rc80211_calc_net_goodness ( ctx, dev->rate );
00212                 if ( old_good != best_net_good )
00213                         DBGC ( ctx, "802.11 RC %p switching from goodness "
00214                                "%d to %d\n", ctx, old_good, best_net_good );
00215 
00216                 ctx->started = 1;
00217                 return best_rate;
00218         }
00219 
00220         return dev->rate;
00221 }
00222 
00223 /**
00224  * Set 802.11 device rate
00225  *
00226  * @v dev       802.11 device
00227  * @v rate_idx  Index of rate to switch to
00228  *
00229  * This is a thin wrapper around net80211_set_rate_idx to insert a
00230  * debugging message where appropriate.
00231  */
00232 static inline void rc80211_set_rate ( struct net80211_device *dev,
00233                                       int rate_idx )
00234 {
00235         DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl,
00236                dev->rates[dev->rate] / 10, dev->rates[rate_idx] / 10 );
00237 
00238         net80211_set_rate_idx ( dev, rate_idx );
00239 }
00240 
00241 /**
00242  * Check rate-control state and change rate if necessary
00243  *
00244  * @v dev       802.11 device
00245  */
00246 static void rc80211_maybe_set_new ( struct net80211_device *dev )
00247 {
00248         struct rc80211_ctx *ctx = dev->rctl;
00249         int net_good;
00250 
00251         net_good = rc80211_calc_net_goodness ( ctx, dev->rate );
00252 
00253         if ( ! ctx->started ) {
00254                 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
00255                 return;
00256         }
00257 
00258         if ( net_good < 0 )     /* insufficient data */
00259                 return;
00260 
00261         if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) {
00262                 int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 );
00263                 if ( higher > net_good || higher < 0 )
00264                         rc80211_set_rate ( dev, dev->rate + 1 );
00265                 else
00266                         rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
00267         }
00268 
00269         if ( net_good < RC_GOODNESS_MIN ) {
00270                 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
00271         }
00272 }
00273 
00274 /**
00275  * Update rate-control state
00276  *
00277  * @v dev               802.11 device
00278  * @v direction         One of the direction constants TX or RX
00279  * @v rate_idx          Index of rate at which packet was sent or received
00280  * @v retries           Number of times packet was retried before success
00281  * @v failed            If nonzero, the packet failed to get through
00282  */
00283 static void rc80211_update ( struct net80211_device *dev, int direction,
00284                              int rate_idx, int retries, int failed )
00285 {
00286         struct rc80211_ctx *ctx = dev->rctl;
00287         u32 goodness = ctx->goodness[direction][rate_idx];
00288 
00289         if ( ctx->count[direction][rate_idx] < 16 )
00290                 ctx->count[direction][rate_idx]++;
00291 
00292         goodness <<= 2;
00293         if ( failed )
00294                 goodness |= RC_PKT_FAILED;
00295         else if ( retries > 1 )
00296                 goodness |= RC_PKT_RETRIED_MULTI;
00297         else if ( retries )
00298                 goodness |= RC_PKT_RETRIED_ONCE;
00299         else
00300                 goodness |= RC_PKT_OK;
00301 
00302         ctx->goodness[direction][rate_idx] = goodness;
00303 
00304         ctx->packets++;
00305 
00306         rc80211_maybe_set_new ( dev );
00307 }
00308 
00309 /**
00310  * Update rate-control state for transmitted packet
00311  *
00312  * @v dev       802.11 device
00313  * @v retries   Number of times packet was transmitted before success
00314  * @v rc        Return status code for transmission
00315  */
00316 void rc80211_update_tx ( struct net80211_device *dev, int retries, int rc )
00317 {
00318         struct rc80211_ctx *ctx = dev->rctl;
00319 
00320         if ( ! ctx->started )
00321                 return;
00322 
00323         rc80211_update ( dev, TX, dev->rate, retries, rc );
00324 
00325         /* Check if the last RC_TX_EMERG_FAIL packets have all failed */
00326         if ( ! ( ctx->goodness[TX][dev->rate] &
00327                  ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) {
00328                 if ( dev->rate == 0 )
00329                         DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive "
00330                                "failed TX, but cannot lower rate any further\n",
00331                                dev->rctl, RC_TX_EMERG_FAIL );
00332                 else {
00333                         DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d "
00334                                "Mbps) due to %d consecutive TX failures\n",
00335                                dev->rctl, dev->rates[dev->rate] / 10,
00336                                dev->rates[dev->rate - 1] / 10,
00337                                RC_TX_EMERG_FAIL );
00338 
00339                         rc80211_set_rate ( dev, dev->rate - 1 );
00340                 }
00341         }
00342 }
00343 
00344 /**
00345  * Update rate-control state for received packet
00346  *
00347  * @v dev       802.11 device
00348  * @v retry     Whether the received packet had been retransmitted
00349  * @v rate      Rate at which packet was received, in 100 kbps units
00350  */
00351 void rc80211_update_rx ( struct net80211_device *dev, int retry, u16 rate )
00352 {
00353         int ridx;
00354 
00355         for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate;
00356               ridx++ )
00357                 ;
00358         if ( ridx >= dev->nr_rates )
00359                 return;         /* couldn't find the rate */
00360 
00361         rc80211_update ( dev, RX, ridx, retry, 0 );
00362 }
00363 
00364 /**
00365  * Free rate-control context
00366  *
00367  * @v ctx       Rate-control context
00368  */
00369 void rc80211_free ( struct rc80211_ctx *ctx )
00370 {
00371         free ( ctx );
00372 }