rc80211.c File Reference

Simple 802.11 rate-control algorithm. More...

#include <stdlib.h>
#include <gpxe/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_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.

Define Documentation

#define RC_PKT_OK   0x3

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

Definition at line 87 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 90 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 99 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 108 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 111 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 114 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 117 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 120 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 123 of file rc80211.c.

Referenced by rc80211_calc_net_goodness().

#define TX   0

TX direction.

Definition at line 126 of file rc80211.c.

Referenced by rc80211_calc_net_goodness(), and rc80211_update_tx().

#define RX   1

RX direction.

Definition at line 129 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:
dev 802.11 device
Return values:
ctx Rate-control context, to be stored in dev->rctl

Definition at line 153 of file rc80211.c.

References zalloc().

Referenced by net80211_step_associate().

00154 {
00155         struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) );
00156         return ret;
00157 }

static 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 165 of file rc80211.c.

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

Referenced by rc80211_maybe_set_new(), and rc80211_pick_best().

00167 {
00168         int sum[2], num[2], dir, pkt;
00169 
00170         for ( dir = 0; dir < 2; dir++ ) {
00171                 u32 good = ctx->goodness[dir][rate_idx];
00172 
00173                 num[dir] = ctx->count[dir][rate_idx];
00174                 sum[dir] = 0;
00175 
00176                 for ( pkt = 0; pkt < num[dir]; pkt++ )
00177                         sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3;
00178         }
00179 
00180         if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH )
00181                 return -1;
00182 
00183         return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) /
00184                       ( num[TX] * RC_TX_FACTOR + num[RX] ) );
00185 }

static 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 193 of file rc80211.c.

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

00194 {
00195         struct rc80211_ctx *ctx = dev->rctl;
00196         int best_net_good = 0, best_rate = -1, i;
00197 
00198         for ( i = 0; i < dev->nr_rates; i++ ) {
00199                 int net_good = rc80211_calc_net_goodness ( ctx, i );
00200 
00201                 if ( net_good > best_net_good ||
00202                      ( best_net_good > RC_GOODNESS_MIN &&
00203                        net_good > RC_GOODNESS_MIN ) ) {
00204                         best_net_good = net_good;
00205                         best_rate = i;
00206                 }
00207         }
00208 
00209         if ( best_rate >= 0 ) {
00210                 int old_good = rc80211_calc_net_goodness ( ctx, dev->rate );
00211                 if ( old_good != best_net_good )
00212                         DBGC ( ctx, "802.11 RC %p switching from goodness "
00213                                "%d to %d\n", ctx, old_good, best_net_good );
00214 
00215                 ctx->started = 1;
00216                 return best_rate;
00217         }
00218 
00219         return dev->rate;
00220 }

static void rc80211_set_rate ( struct net80211_device *  dev,
int  rate_idx 
) [inline, static]

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

00233 {
00234         DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl,
00235                dev->rates[dev->rate] / 10, dev->rates[rate_idx] / 10 );
00236 
00237         net80211_set_rate_idx ( dev, rate_idx );
00238 }

static 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 245 of file rc80211.c.

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

00246 {
00247         struct rc80211_ctx *ctx = dev->rctl;
00248         int net_good;
00249 
00250         net_good = rc80211_calc_net_goodness ( ctx, dev->rate );
00251 
00252         if ( ! ctx->started ) {
00253                 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
00254                 return;
00255         }
00256 
00257         if ( net_good < 0 )     /* insufficient data */
00258                 return;
00259 
00260         if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) {
00261                 int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 );
00262                 if ( higher > net_good || higher < 0 )
00263                         rc80211_set_rate ( dev, dev->rate + 1 );
00264                 else
00265                         rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
00266         }
00267 
00268         if ( net_good < RC_GOODNESS_MIN ) {
00269                 rc80211_set_rate ( dev, rc80211_pick_best ( dev ) );
00270         }
00271 }

static 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 282 of file rc80211.c.

References rc80211_ctx::count, rc80211_ctx::goodness, rc80211_ctx::packets, 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().

00284 {
00285         struct rc80211_ctx *ctx = dev->rctl;
00286         u32 goodness = ctx->goodness[direction][rate_idx];
00287 
00288         if ( ctx->count[direction][rate_idx] < 16 )
00289                 ctx->count[direction][rate_idx]++;
00290 
00291         goodness <<= 2;
00292         if ( failed )
00293                 goodness |= RC_PKT_FAILED;
00294         else if ( retries > 1 )
00295                 goodness |= RC_PKT_RETRIED_MULTI;
00296         else if ( retries )
00297                 goodness |= RC_PKT_RETRIED_ONCE;
00298         else
00299                 goodness |= RC_PKT_OK;
00300 
00301         ctx->goodness[direction][rate_idx] = goodness;
00302 
00303         ctx->packets++;
00304 
00305         rc80211_maybe_set_new ( dev );
00306 }

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

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

00316 {
00317         struct rc80211_ctx *ctx = dev->rctl;
00318 
00319         if ( ! ctx->started )
00320                 return;
00321 
00322         rc80211_update ( dev, TX, dev->rate, retries, rc );
00323 
00324         /* Check if the last RC_TX_EMERG_FAIL packets have all failed */
00325         if ( ! ( ctx->goodness[TX][dev->rate] &
00326                  ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) {
00327                 if ( dev->rate == 0 )
00328                         DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive "
00329                                "failed TX, but cannot lower rate any further\n",
00330                                dev->rctl, RC_TX_EMERG_FAIL );
00331                 else {
00332                         DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d "
00333                                "Mbps) due to %d consecutive TX failures\n",
00334                                dev->rctl, dev->rates[dev->rate] / 10,
00335                                dev->rates[dev->rate - 1] / 10,
00336                                RC_TX_EMERG_FAIL );
00337 
00338                         rc80211_set_rate ( dev, dev->rate - 1 );
00339                 }
00340         }
00341 }

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

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

Referenced by net80211_rx().

00351 {
00352         int ridx;
00353 
00354         for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate;
00355               ridx++ )
00356                 ;
00357         if ( ridx >= dev->nr_rates )
00358                 return;         /* couldn't find the rate */
00359 
00360         rc80211_update ( dev, RX, ridx, retry, 0 );
00361 }

void rc80211_free ( struct rc80211_ctx *  ctx  ) 

Free rate-control context.

Parameters:
ctx Rate-control context

Definition at line 368 of file rc80211.c.

References free().

Referenced by net80211_free().

00369 {
00370         free ( ctx );
00371 }

Generated on Tue Apr 6 20:01:54 2010 for gPXE by  doxygen 1.5.7.1