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...

Macros
#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)
	FILE_SECBOOT (FORBIDDEN)
struct rc80211_ctx *	rc80211_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.

Macro Definition Documentation

RC_PKT_OK

#define RC_PKT_OK   0x3

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

Definition at line 89 of file rc80211.c.

Referenced by rc80211_update().

RC_PKT_RETRIED_ONCE

#define RC_PKT_RETRIED_ONCE   0x2

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

Definition at line 92 of file rc80211.c.

Referenced by rc80211_update().

RC_PKT_RETRIED_MULTI

#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 101 of file rc80211.c.

Referenced by rc80211_update().

RC_PKT_FAILED

#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 110 of file rc80211.c.

Referenced by rc80211_update().

RC_TX_FACTOR

#define RC_TX_FACTOR   4

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

Definition at line 113 of file rc80211.c.

Referenced by rc80211_calc_net_goodness().

RC_TX_EMERG_FAIL

#define RC_TX_EMERG_FAIL   3

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

Definition at line 116 of file rc80211.c.

Referenced by rc80211_update_tx().

RC_GOODNESS_MIN

#define RC_GOODNESS_MIN   85

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

Definition at line 119 of file rc80211.c.

Referenced by rc80211_maybe_set_new(), and rc80211_pick_best().

RC_GOODNESS_MAX

#define RC_GOODNESS_MAX   95

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

Definition at line 122 of file rc80211.c.

Referenced by rc80211_maybe_set_new().

RC_UNCERTAINTY_THRESH

#define RC_UNCERTAINTY_THRESH   4

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

Definition at line 125 of file rc80211.c.

Referenced by rc80211_calc_net_goodness().

TX

#define TX   0

TX direction.

Definition at line 128 of file rc80211.c.

Referenced by rc80211_calc_net_goodness(), and rc80211_update_tx().

RX

#define RX   1

RX direction.

Definition at line 131 of file rc80211.c.

Referenced by rc80211_calc_net_goodness(), and rc80211_update_rx().

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER

)

FILE_SECBOOT()

FILE_SECBOOT

(

FORBIDDEN

)

rc80211_init()

struct rc80211_ctx * rc80211_init

(

struct net80211_device *dev

__unused

)

Initialize rate-control algorithm.

Parameters

dev	802.11 device

Return values

ctx	Rate-control context, to be stored in dev->rctl

Definition at line 155 of file rc80211.c.

{
        struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
        return ret;
}

References __unused, and zalloc().

Referenced by net80211_step_associate().

rc80211_calc_net_goodness()

int rc80211_calc_net_goodness ( struct rc80211_ctx * ctx, int rate_idx )

static

Calculate net goodness for a certain rate.

Parameters

ctx	Rate-control context
rate_idx	Index of rate to calculate net goodness for

Definition at line 167 of file rc80211.c.

{
        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] ) );
}

References ctx, num, RC_TX_FACTOR, RC_UNCERTAINTY_THRESH, RX, TX, and u32.

Referenced by rc80211_maybe_set_new(), and rc80211_pick_best().

rc80211_pick_best()

int rc80211_pick_best ( struct net80211_device * dev )

static

Determine the best rate to switch to and return it.

Parameters

dev	802.11 device

Return values

rate_idx

Index of the best rate to switch to

Definition at line 195 of file rc80211.c.

{
        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;
}

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

Referenced by rc80211_maybe_set_new().

rc80211_set_rate()

void rc80211_set_rate ( struct net80211_device * dev, int rate_idx )

inlinestatic

Set 802.11 device rate.

Parameters

dev	802.11 device
rate_idx	Index 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 233 of file rc80211.c.

{
        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 );
}

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().

rc80211_maybe_set_new()

void rc80211_maybe_set_new ( struct net80211_device * dev )

static

Check rate-control state and change rate if necessary.

Parameters

dev	802.11 device

Definition at line 247 of file rc80211.c.

{
        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 ) );
        }
}

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, and net80211_device::rctl.

Referenced by rc80211_update().

rc80211_update()

void rc80211_update ( struct net80211_device * dev, int direction, int rate_idx, int retries, int failed )

static

Update rate-control state.

Parameters

dev	802.11 device
direction	One of the direction constants TX or RX
rate_idx	Index of rate at which packet was sent or received
retries	Number of times packet was retried before success
failed	If nonzero, the packet failed to get through

Definition at line 284 of file rc80211.c.

{
        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 );
}

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

Referenced by rc80211_update_rx(), and rc80211_update_tx().

rc80211_update_tx()

void rc80211_update_tx	(	struct net80211_device *	dev,
		int	retries,
		int	rc )

Update rate-control state for transmitted packet.

Parameters

dev	802.11 device
retries	Number of times packet was transmitted before success
rc	Return status code for transmission

Definition at line 317 of file rc80211.c.

{
        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 );
                }
        }
}

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

Referenced by net80211_tx_complete().

rc80211_update_rx()

void rc80211_update_rx	(	struct net80211_device *	dev,
		int	retry,
		u16	rate )

Update rate-control state for received packet.

Parameters

dev	802.11 device
retry	Whether the received packet had been retransmitted
rate	Rate at which packet was received, in 100 kbps units

Definition at line 352 of file rc80211.c.

{
        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 );
}

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

Referenced by net80211_rx().

rc80211_free()

void rc80211_free

(

struct rc80211_ctx *

ctx

)

Free rate-control context.

Parameters

ctx	Rate-control context

Definition at line 370 of file rc80211.c.

{
        free ( ctx );
}

References ctx, and free.

Referenced by net80211_free().