Time-based Regulator

In the previous sections, we have argued that competing nodes should be given an equal amount of long-term channel occupancy time. As explained before, in AP-based WLANs, the MAC protocol and the queuing scheme at the AP in combination determine the channel time allocation. Therefore, to achieve a desired channel time allocation, coordination is necessary between the MAC protocol and the queuing scheme. Our proposed Time-based Regulator runs at each AP, coordinates with clients when necessary and works in conjunction with any MAC protocol.

TBR provides an equal share of long-term channel occupancy time to each competing client node by

• Dictating how packet transmissions are scheduled at the AP as well as at the clients
• Taking into account the channel occupancy time of traffic in both downlink and uplink directions, and
• Taking into account varying traffic conditions, loss rates, data rates, and frame sizes

A typical implementation of TBR requires no modification to the underlying MAC protocol and to the drivers of mobile clients, allowing incremental deployment and preserving backward compatibility. Modifications to the clients, however, are necessary to preserve correctness in cases where the uplink UDP flows make up a significant fraction of the WLAN traffic. We will discuss more on this issue in the next subsection.

Figure 6: Pseudo-code of TBR

TBR is based on the leaky bucket scheme [3]. The fundamental unit or token used in the implementation is the channel occupancy time in terms of micro-seconds. TBR only schedules the transmission of a packet destined to or originated from a client only if the node has not used up all its available channel time.

Figure 6 shows the pseudo-code of TBR that runs on the AP. TBR sits above the MAC layer and below the network layer and is implemented in five event handlers, each of which is triggered by the upper layer, timer or the MAC layer.

When a node i associates with the AP (i.e. joins the network), ASSOCIATEEVENT is triggered. The procedure i) creates output queue queue_i and ii) initializes tokens_i, the available tokens, bucket_i, the maximum amount of tokens that the node can accumulate, and rate_i, the rate at which tokens are being re-filled.

Whenever the upper layer has a packet p to transmit, it calls APPTXEVENT. TBR simply enqueues the packet to queue_i where i is the destination of p.

TBR adjusts tokens_i according to the channel occupancy time of transmitted frames originated from or destined to node i. Section 4.2 described how TBR computes the channel occupancy time. bucket_i determines the maximum length of the burst period in which node i can transmit successively (if no other nodes can transmit). bucket_i can affect the short-term fairness and we discuss this issue later in Section 4.5.

TBR sets up a timer that periodically calls FILLEVENT, which for each node i, updates tokens_i according to rate_i and t, the time elapsed since the last time FILLEVENT was called. rate_i is the rate at which tokens are being re-filled. We note that $\sum_{i=1}^n{rate_i} = 1$, where n is the number of active client nodes. In general, rate_i can vary among client nodes depending on the desired fairness policy. If each competing node should receive an equal share of the channel occupancy time, $rate_i = \frac{1}{n}$. However, in practice, not all nodes can consume their available channel time according to the allocation. TBR ensures that the system remain work conserving by adjusting the token rates appropriately as discussed in Section 4.3.