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

    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
            IdleTime = IdleTime + Diff

        PreviousState = BackupState


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.