Return to rc80211.c CVS log

Up to [Qemu by Fabrice Bellard] / qemu / roms / ipxe / src / net / 80211

Annotation of qemu/roms/ipxe/src/net/80211/rc80211.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Simple 802.11 rate-control algorithm for iPXE.
        !             3:  *
        !             4:  * Copyright (c) 2009 Joshua Oreman <[email protected]>.
        !             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 <ipxe/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 iPXE'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 iPXE 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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.