In order to decide whether and how much a station is cheating on the Distributed Coordination Function (DCF), we need to know how much a well-behaved station can get. This cannot be pre-calculated as it is highly dependent on network dynamics. The same station can get a lower throughput in a more noisy channel or within a busy network, than a quiet place as it sits next to the access-point.
Our approach to estimating the fair throughput is called the Virtual MAC. The idea is to run a virtual station within the access-point. This station listens to the channel, detects idle and busy slots (according to Bianchi’s definition of slots), and uses this information to calculate the fair throughput. The virtual MAC is an important part of the policing scheme for obvious reasons. Below is the procedure we currently use in the b43 firmware to gather this information (the original code is in assembly, but here is a simplified pseudo-code). This procedure runs on the device’s idle time, and roughly every one or two microseconds:
VMAC_Iteration (TSF, StatusFlag)
if Inited = FALSE then
StartTime = TSF
CurrentState = INVALID
PreviousState = BUSY
Inited = TRUE
if CurrentState = StatusFlag then
return
BackupState = CurrentState
CurrentState = StatusFlag
Diff = TSF - StartTime
if not (BackupState = BUSY and Diff < 192) and
not (BackupState = IDLE and Diff < 50) and
not PreviousState = BackupState then
PreviousState = BackupState
if BackupState = BUSY then
BusySlots = BusySlots + 1
else
IdleTime = IdleTime + Diff
PreviousState = BackupState
START_TIME = TSF
In the above pseudo-code, BusySlots and IdleTime are shared with the driver. Our b43 driver is modified to perform the main part of the policing algorithm, which is ACK-dropping probability calculation. It uses the shared information provided by the firmware to estimate the fair throughput. Below pseudo-code shows how this is done:
FailedBusySlots = BusySlots - ReceivedFrames TotalSlots = BusySlots + (IdleTime - BusySlots * DIFS - FailedBusySlots * PLCP) / SlotTime - SentBeacons Pf = BusySlots / TotalSlots Tau = (1 - 2 * Pf) / ((2 * Pf - 1) * (W + 1) + W * (Pf * (2 * Pf) ^ 5 - 1)) Estimate = CorrectionRatio * Tau * (1 - Pf) * TotalSlots
In the above, W is the minimum contention window (which depends on the TX queue), Pf is the probability of failure, and Tau is the probability of transmission.