Check out the new USENIX Web site. next up previous
Next: Fairness in AP-based WLANs Up: Analysis Previous: Analysis


Impact of Fairness Notions on Efficiency

We now examine how different notions of fairness impact the overall efficiency of multi-rate WLANs. The measure of fairness between nodes i and j with equal priorities during an interval (t1, t2) is: $\vert\alpha_i(t_1, t_2) - \alpha_j(t_1, t_2)\vert$, where $\alpha_i(t_1, t_2)$ and $\alpha_j(t_1, t_2)$ are their achieved portions of the shared resource. In this paper, we only focus on nodes with equal priorities. Different notions of fairness are captured by differing definitions of $\alpha$. Let $\alpha^t_i(t_1, t_2)$ and $\alpha^r_i(t_1, t_2)$ be the channel occupancy time and the achieved throughput respectively of node i during (t1, t2).

The choice of fairness notion dictates how the network allocates the shared resource (in our case channel capacity) during periods in which demand exceeds supply. The overall network performance as well as the performance of individual nodes can be greatly affected by it. We define network efficiency as the sum of the utility of each competing node based on their shares of shared resource. We use two traffic models, a fluid model [8,27] and a task model [4], to examine the impact of fairness notions on overall network efficiency.

In the fluid model, there is a finite number of flows, each of which continuously transfers infinite streams of bits. The network efficiency can be evaluated using its (average) aggregate sustained throughput (AggrThruput). Note that while the instantaneous throughput of a node will vary depending upon the its data rate, the expected instantaneous total throughput is time invariant.

In the task model, there is a finite number of flows, each of which transfers a finite number of bits. Since we are providing fairness only among competing nodes, we assume that each node has one flow. In this model, the instantaneous aggregate throughput varies with the remaining task mix. Thus, it is more appropriate to look at network efficiency in other ways such as the average task completion time, AvgTaskTime, and the final task completion time, FinalTaskTime. Short AvgTaskTime is especially desirable for mobile nodes since those that have completed their communication tasks can turn-off their wireless cards to save energy or move to another place to go on with their work. Short FinalTaskTime is also desirable since it implies higher long term average aggregate throughput and thus the network can potentially accommodate more tasks.

Figure 3: Achieved TCP throughputs and fractions of channel occupancy time of two competing nodes in three different combinations of data rates: 11vs11, 1vs11 and 1vs1. throughput-based fairness and TF denote the throughput-based and time-based fairness notions respectively. E.g. in  3(a), n1(11) denotes the throughput achieved by node n1 transmitting at 11 Mbps.

Figures 3(a) and 3(b) compare the achieved TCP throughputs and the channel occupancy times of two competing nodes when different fairness notions (RF and TF) are used. These figures assume a flow model or a task model in which no flow has yet completed. The graphs are based on the experiments we conducted. In the remainder of this section we demonstrate that these experimental results are consistent with analytical predictions.

Observe that when both nodes transmit at the same rate (11vs11 and 1vs1), the allocations of both throughputs and channel occupancy times are identical for both fairness notions. However, when one node (n1) transmits at 1 Mbps and the other (n2) at 11 Mbps (see middle bars in figures), nodes achieve equal throughputs under throughput-based fairness, but n2 achieves more throughput than n1 under time-based fairness. The situation is reversed with respect to the allocation of channel occupancy time. Each node achieves an equal amount of channel occupancy time under time-based fairness, but n1 gets a much larger share than n2 under throughput-based fairness.

Compared to throughput-based fairness, time-based fairness benefits faster nodes at the expense of slower nodes. However, the fairness property captured by the baseline property of Section 1 is maintained. Each class of node performs as it would in a single-rate 802.11 WLAN. For instance, the achieved throughput of n1 in both 1vs11 and 1vs1 cases is the same under time-based fairness. The same statement can be made for other performance measures such as per-packet latency.


Table 1: Comparison of different measures when the throughput-based (RF) and time-based (TF) fairness notions are enforced.
Criteria Measure RF TF
Fairness $\vert\alpha^r_i(t_1, t_2) - \alpha^r_j(t_1, t_2)\vert$ Better Worse
  $\vert\alpha^t_i(t_1, t_2) - \alpha^t_j(t_1, t_2)\vert$ Worse Better
Efficiency FinalTaskTime Same Same
(task model) AvgTaskTime Worse Better
Efficiency AggrThruput Worse Better
(fluid model)      


Table 1 compares various measures of fairness and efficiency for scenarios in which nodes within a cell compete using different data rates. As explained in the rest of this section, the conclusions captured in this table hold for any number of nodes. However, for concreteness, we use the 1vs11 case as a concrete example. Under the task model, we assume that each node has an equal amount of data to transfer. Technically, the same results apply so long as each node has a similar distribution of task size.

When the fluid traffic model is used, higher AggrThruput results under time-based fairness as evident in Figure 3(a). FinalTaskTime remains unchanged under the task model since the network is work-conserving under both fairness notions. However, AvgTaskTime under time-based fairness is lower than that under throughput-based fairness. Under throughput-based fairness, AvgTaskTime = FinalTaskTime, since both tasks complete at the same time. Under time-based fairness, in contrast, AvgTaskTime < FinalTaskTime. This is because the task of the 11 Mbps node will complete sooner, since it achieves higher throughput while the completion time of the 1 Mbps node remains the same.

The rest of this section examines how well existing 802.11's DCF achieves each notion of fairness, and presents an analytical framework to predict the network performance in multi-rate WLANs.


next up previous
Next: Fairness in AP-based WLANs Up: Analysis Previous: Analysis
Godfrey Tan 2004-05-04