iPXE
Data Structures | Defines | Functions
rc80211.c File Reference

Simple 802.11 rate-control algorithm. More...

#include <stdlib.h>
#include <ipxe/net80211.h>

Go to the source code of this file.

Data Structures

struct  rc80211_ctx
 A rate control context. More...

Defines

#define RC_PKT_OK   0x3
 Two-bit packet status indicator for a packet with no retries.
#define RC_PKT_RETRIED_ONCE   0x2
 Two-bit packet status indicator for a packet with one retry.
#define RC_PKT_RETRIED_MULTI   0x1
 Two-bit packet status indicator for a TX packet with multiple retries.
#define RC_PKT_FAILED   0x0
 Two-bit packet status indicator for a TX packet that was never ACKed.
#define RC_TX_FACTOR   4
 Number of times to weight TX packets more heavily than RX packets.
#define RC_TX_EMERG_FAIL   3
 Number of consecutive failed TX packets that cause an automatic rate drop.
#define RC_GOODNESS_MIN   85
 Minimum net goodness below which we will search for a better rate.
#define RC_GOODNESS_MAX   95
 Maximum net goodness above which we will try to increase our rate.
#define RC_UNCERTAINTY_THRESH   4
 Minimum (num RX + RC_TX_FACTOR * num TX) to use a certain rate.
#define TX   0
 TX direction.
#define RX   1
 RX direction.

Functions

 FILE_LICENCE (GPL2_OR_LATER)
struct rc80211_ctxrc80211_init (struct net80211_device *dev __unused)
 Initialize rate-control algorithm.
static int rc80211_calc_net_goodness (struct rc80211_ctx *ctx, int rate_idx)
 Calculate net goodness for a certain rate.
static int rc80211_pick_best (struct net80211_device *dev)
 Determine the best rate to switch to and return it.
static void rc80211_set_rate (struct net80211_device *dev, int rate_idx)
 Set 802.11 device rate.
static void rc80211_maybe_set_new (struct net80211_device *dev)
 Check rate-control state and change rate if necessary.
static void rc80211_update (struct net80211_device *dev, int direction, int rate_idx, int retries, int failed)
 Update rate-control state.
void rc80211_update_tx (struct net80211_device *dev, int retries, int rc)
 Update rate-control state for transmitted packet.
void rc80211_update_rx (struct net80211_device *dev, int retry, u16 rate)
 Update rate-control state for received packet.
void rc80211_free (struct rc80211_ctx *ctx)
 Free rate-control context.

Detailed Description

Simple 802.11 rate-control algorithm.

Definition in file rc80211.c.


Define Documentation

#define RC_PKT_OK   0x3

Two-bit packet status indicator for a packet with no retries.

Definition at line 88 of file rc80211.c.

Referenced by rc80211_update().

#define RC_PKT_RETRIED_ONCE   0x2

Two-bit packet status indicator for a packet with one retry.

Definition at line 91 of file rc80211.c.

Referenced by rc80211_update().

#define RC_PKT_RETRIED_MULTI   0x1

Two-bit packet status indicator for a TX packet with multiple retries.

It is not possible to tell whether an RX packet had one or multiple retries; we rely instead on the fact that failed RX packets won't get to us at all, so if we receive a lot of RX packets on a certain rate it must be pretty good.

Definition at line 100 of file rc80211.c.

Referenced by rc80211_update().

#define RC_PKT_FAILED   0x0

Two-bit packet status indicator for a TX packet that was never ACKed.

It is not possible to tell whether an RX packet was setn if it didn't get through to us, but if we don't see one we won't increase the goodness for its rate. This asymmetry is part of why TX packets are weighted much more heavily than RX.

Definition at line 109 of file rc80211.c.

Referenced by rc80211_update().

#define RC_TX_FACTOR   4

Number of times to weight TX packets more heavily than RX packets.

Definition at line 112 of file rc80211.c.

Referenced by rc80211_calc_net_goodness().

#define RC_TX_EMERG_FAIL   3

Number of consecutive failed TX packets that cause an automatic rate drop.

Definition at line 115 of file rc80211.c.

Referenced by rc80211_update_tx().

#define RC_GOODNESS_MIN   85

Minimum net goodness below which we will search for a better rate.

Definition at line 118 of file rc80211.c.

Referenced by rc80211_maybe_set_new(), and rc80211_pick_best().

#define RC_GOODNESS_MAX   95

Maximum net goodness above which we will try to increase our rate.

Definition at line 121 of file rc80211.c.

Referenced by rc80211_maybe_set_new().

#define RC_UNCERTAINTY_THRESH   4

Minimum (num RX + RC_TX_FACTOR * num TX) to use a certain rate.

Definition at line 124 of file rc80211.c.

Referenced by rc80211_calc_net_goodness().

#define TX   0

TX direction.

Definition at line 127 of file rc80211.c.

Referenced by rc80211_calc_net_goodness(), and rc80211_update_tx().

#define RX   1

RX direction.

Definition at line 130 of file rc80211.c.

Referenced by rc80211_calc_net_goodness(), and rc80211_update_rx().


Function Documentation

FILE_LICENCE ( GPL2_OR_LATER  )
struct rc80211_ctx* rc80211_init ( struct net80211_device *dev  __unused) [read]

Initialize rate-control algorithm.

Parameters:
dev802.11 device
Return values:
ctxRate-control context, to be stored in dev->rctl

Definition at line 154 of file rc80211.c.

References ret, and zalloc().

Referenced by net80211_step_associate().

{
        struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
        return ret;
}
static int rc80211_calc_net_goodness ( struct rc80211_ctx ctx,
int  rate_idx 
) [static]

Calculate net goodness for a certain rate.

Parameters:
ctxRate-control context
rate_idxIndex of rate to calculate net goodness for

Definition at line 166 of file rc80211.c.

References rc80211_ctx::count, rc80211_ctx::goodness, num, RC_TX_FACTOR, RC_UNCERTAINTY_THRESH, RX, and TX.

Referenced by rc80211_maybe_set_new(), and rc80211_pick_best().

{
        int sum[2], num[2], dir, pkt;

        for ( dir = 0; dir < 2; dir++ ) {
                u32 good = ctx->goodness[dir][rate_idx];

                num[dir] = ctx->count[dir][rate_idx];
                sum[dir] = 0;

                for ( pkt = 0; pkt < num[dir]; pkt++ )
                        sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3;
        }

        if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH )
                return -1;

        return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) /
                      ( num[TX] * RC_TX_FACTOR + num[RX] ) );
}
static int rc80211_pick_best ( struct net80211_device dev) [static]

Determine the best rate to switch to and return it.

Parameters:
dev802.11 device
Return values:
rate_idxIndex of the best rate to switch to

Definition at line 194 of file rc80211.c.

References ctx, DBGC, net80211_device::nr_rates, net80211_device::rate, rc80211_calc_net_goodness(), RC_GOODNESS_MIN, net80211_device::rctl, and rc80211_ctx::started.

Referenced by rc80211_maybe_set_new().

{
        struct rc80211_ctx *ctx = dev->rctl;
        int best_net_good = 0, best_rate = -1, i;

        for ( i = 0; i < dev->nr_rates; i++ ) {
                int net_good = rc80211_calc_net_goodness ( ctx, i );

                if ( net_good > best_net_good ||
                     ( best_net_good > RC_GOODNESS_MIN &&
                       net_good > RC_GOODNESS_MIN ) ) {
                        best_net_good = net_good;
                        best_rate = i;
                }
        }

        if ( best_rate >= 0 ) {
                int old_good = rc80211_calc_net_goodness ( ctx, dev->rate );
                if ( old_good != best_net_good )
                        DBGC ( ctx, "802.11 RC %p switching from goodness "
                               "%d to %d\n", ctx, old_good, best_net_good );

                ctx->started = 1;
                return best_rate;
        }

        return dev->rate;
}
static void rc80211_set_rate ( struct net80211_device dev,
int  rate_idx 
) [inline, static]

Set 802.11 device rate.

Parameters:
dev802.11 device
rate_idxIndex of rate to switch to

This is a thin wrapper around net80211_set_rate_idx to insert a debugging message where appropriate.

Definition at line 232 of file rc80211.c.

References DBGC, net80211_set_rate_idx(), net80211_device::rate, net80211_device::rates, and net80211_device::rctl.

Referenced by rc80211_maybe_set_new(), and rc80211_update_tx().

{
        DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl,
               dev->rates[dev->rate] / 10, dev->rates[rate_idx] / 10 );

        net80211_set_rate_idx ( dev, rate_idx );
}
static void rc80211_maybe_set_new ( struct net80211_device dev) [static]

Check rate-control state and change rate if necessary.

Parameters:
dev802.11 device

Definition at line 246 of file rc80211.c.

References ctx, net80211_device::nr_rates, net80211_device::rate, rc80211_calc_net_goodness(), rc80211_pick_best(), rc80211_set_rate(), RC_GOODNESS_MAX, RC_GOODNESS_MIN, net80211_device::rctl, and rc80211_ctx::started.

Referenced by rc80211_update().

{
        struct rc80211_ctx *ctx = dev->rctl;
        int net_good;

        net_good = rc80211_calc_net_goodness ( ctx, dev->rate );

        if ( ! ctx->started ) {
                rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
                return;
        }

        if ( net_good < 0 )     /* insufficient data */
                return;

        if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) {
                int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 );
                if ( higher > net_good || higher < 0 )
                        rc80211_set_rate ( dev, dev->rate + 1 );
                else
                        rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
        }

        if ( net_good < RC_GOODNESS_MIN ) {
                rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
        }
}
static void rc80211_update ( struct net80211_device dev,
int  direction,
int  rate_idx,
int  retries,
int  failed 
) [static]

Update rate-control state.

Parameters:
dev802.11 device
directionOne of the direction constants TX or RX
rate_idxIndex of rate at which packet was sent or received
retriesNumber of times packet was retried before success
failedIf nonzero, the packet failed to get through

Definition at line 283 of file rc80211.c.

References rc80211_ctx::count, ctx, direction, rc80211_ctx::goodness, rc80211_ctx::packets, rc80211_maybe_set_new(), RC_PKT_FAILED, RC_PKT_OK, RC_PKT_RETRIED_MULTI, RC_PKT_RETRIED_ONCE, and net80211_device::rctl.

Referenced by rc80211_update_rx(), and rc80211_update_tx().

{
        struct rc80211_ctx *ctx = dev->rctl;
        u32 goodness = ctx->goodness[direction][rate_idx];

        if ( ctx->count[direction][rate_idx] < 16 )
                ctx->count[direction][rate_idx]++;

        goodness <<= 2;
        if ( failed )
                goodness |= RC_PKT_FAILED;
        else if ( retries > 1 )
                goodness |= RC_PKT_RETRIED_MULTI;
        else if ( retries )
                goodness |= RC_PKT_RETRIED_ONCE;
        else
                goodness |= RC_PKT_OK;

        ctx->goodness[direction][rate_idx] = goodness;

        ctx->packets++;

        rc80211_maybe_set_new ( dev );
}
void rc80211_update_tx ( struct net80211_device dev,
int  retries,
int  rc 
)

Update rate-control state for transmitted packet.

Parameters:
dev802.11 device
retriesNumber of times packet was transmitted before success
rcReturn status code for transmission

Definition at line 316 of file rc80211.c.

References ctx, DBGC, rc80211_ctx::goodness, net80211_device::rate, net80211_device::rates, rc80211_set_rate(), rc80211_update(), RC_TX_EMERG_FAIL, net80211_device::rctl, rc80211_ctx::started, and TX.

Referenced by net80211_tx_complete().

{
        struct rc80211_ctx *ctx = dev->rctl;

        if ( ! ctx->started )
                return;

        rc80211_update ( dev, TX, dev->rate, retries, rc );

        /* Check if the last RC_TX_EMERG_FAIL packets have all failed */
        if ( ! ( ctx->goodness[TX][dev->rate] &
                 ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) {
                if ( dev->rate == 0 )
                        DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive "
                               "failed TX, but cannot lower rate any further\n",
                               dev->rctl, RC_TX_EMERG_FAIL );
                else {
                        DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d "
                               "Mbps) due to %d consecutive TX failures\n",
                               dev->rctl, dev->rates[dev->rate] / 10,
                               dev->rates[dev->rate - 1] / 10,
                               RC_TX_EMERG_FAIL );

                        rc80211_set_rate ( dev, dev->rate - 1 );
                }
        }
}
void rc80211_update_rx ( struct net80211_device dev,
int  retry,
u16  rate 
)

Update rate-control state for received packet.

Parameters:
dev802.11 device
retryWhether the received packet had been retransmitted
rateRate at which packet was received, in 100 kbps units

Definition at line 351 of file rc80211.c.

References net80211_device::nr_rates, net80211_device::rates, rc80211_update(), and RX.

Referenced by net80211_rx().

{
        int ridx;

        for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate;
              ridx++ )
                ;
        if ( ridx >= dev->nr_rates )
                return;         /* couldn't find the rate */

        rc80211_update ( dev, RX, ridx, retry, 0 );
}
void rc80211_free ( struct rc80211_ctx ctx)

Free rate-control context.

Parameters:
ctxRate-control context

Definition at line 369 of file rc80211.c.

References free.

Referenced by net80211_free().

{
        free ( ctx );
}