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.