Introduction

802.11 is the de facto wireless networking standard. In a typical deployment, a mobile node or station equipped with an 802.11 interface communicates over the air to an access point (AP) or base station that is connected to a wired backbone. There are a number of different 802.11 standards. For concreteness, we focus primarily on 802.11b, the most widely used version of 802.11. When multiple mobile nodes wish to use the wireless channel simultaneously, the channel must be apportioned in some ``fair'' way among them. In 802.11 networks, the apportioning is controlled by DCF at the MAC layer and the queuing mechanism used at the APs. For reasons we discuss later, nodes connected to 802.11 WLANs transfer data at a number of different rates. So, for example, the channel capacity might have to be apportioned between nodes transferring data at 11 Mbps and nodes transferring data at 1 Mbps. In this paper, we first demonstrate that DCF and the existing queuing schemes at the APs provide a notion of fairness that is inherently inefficient, and then propose and evaluate a better mechanism. The signal strength and loss rate of indoor wireless channels vary widely, even for nodes that are equidistant from access points [19]. When the 802.11 MAC detects a packet loss (due to the absence of a synchronous ack), it continues retransmitting the packet until the maximum retry limit has been reached. However, this is futile when the average signal strength at the receiver is consistently lower than the threshold required for successful packet reception. In such cases, the sender can transmit at a lower data rate (using a more resilient modulation scheme) so that the channel bit error rate (BER) is reduced. In general, there is a trade-off between data rate and BER [11,16]. Many vendors of APs and client cards implement automatic rate control schemes in which the sending stations adaptively change the data rate based on perceived channel conditions [7,16,21]. Many cards also allow users to manually set the data rate. The 802.11b standard defines four different data rates, 1, 2, 5.5 and 11 Mbps respectively. This leads to rate diversity in the system, where competing nodes within a cell use different data rates to communicate with the AP (in both uplink and downlink directions). As shown in Figure 1, various data transmission rates were used during 90-minute sessions of a student workshop that took place at MIT. Furthermore, WLANs carry significant amounts of traffic, and thus many APs experience several congested periods. In Section, 3, we discuss the prevalence of rate diversity in more detail. When multiple nodes are simultaneously exchanging data using different data rates during congested periods, the total network throughput is quite different from what one might expect. Figure 2 illustrates how the aggregate throughput can be dramatically reduced when two competing nodes use different data rates to upload files using TCP. The achieved throughput of the node with the higher transmission rate is reduced by about 3.75 times. The root cause of this behavior is the definition of fairness used by DCF. This variant of the CSMA medium access protocol is designed to give approximately equal transmission opportunities to each competing node. That is to say each node will have approximately the same number of opportunities to send a data frame, irrespective of the amount of time required to transmit a packet. When the same-sized packets are used and channel conditions are similar, each competing node, regardless of its data rate, achieves roughly the same throughput, as shown in Figure 2.

Figure 1: Fractions of bytes transferred at various data rates during three 90-minute workshop sessions (WS) and an experiment (EXP-1).

Since the node transmitting at 1 Mbps will take several times longer to transmit a frame than the node transmitting at 11 Mbps, the channel is being used most of the time by the slower node. In Figure 2, the fraction of the channel time used by the slower node is 6.4 times as much as that used by the faster node. Hence, the total throughput is reduced to a level much closer to what one gets when both competing nodes are slow. The faster node pays a penalty for competing against a slow node rather than against another fast node. Aggregate throughput is also impacted. Naively, one might expect the total throughput of an 11 Mbps and a 1 Mbps channel to be somewhere around 2.93 Mbps, the average of the total throughputs achieved by a pair of 11 Mbps channels (5.08 Mbps) and a pair of 1 Mbps channels (0.78 Mbps). However, it is only 1.34 Mbps, less than half of what one might expect. And the situation is likely to become worse as the emerging 802.11g networks, with a maximum data rate of 54 Mbps, are deployed alongside relatively slower 802.11b networks. 802.11g users may see far less performance improvement than expected, thus lowering the incentive for users to upgrade to 802.11g cards.

Figure 2: TCP throughputs achieved and fractions of channel occupancy time used by two competing nodes when i) both sending at 11 Mbps and ii) one sending at 11 Mbps and the other at 1 Mbps.

DCF mainly affects the channel capacity allocation in the uplink direction. The packet scheduling mechanism at the AP dictates the channel capacity allocation to clients in the downlink direction. When there are multiple backlogged packets destined to more than one clients, the scheduling scheme must decide the order of transmission. Again, since the channel conditions at the clients vary, different data transmission rates are often used for different clients. Scheduling schemes in the literature [8,9,24] provide throughput-based fairness that has been widely-accepted in wired networks and single-rate 802.11 WLAN, in which the data rate for each transmission on the shared medium is the same. When such scheduling schemes are employed at the APs of multi-rate WLANs, the channel capacity allocation on the downlink direction is impacted in a similar undesirable way as in the uplink direction. We believe that these inefficiencies are best addressed by adopting a notion of fairness that gives each competing client node an approximately equal amount of the shared channel resource: channel occupancy time. This notion of of Time-based fairness is quite different from the throughput-based fairness notion widely accepted in wired networks and single-rate WLANs. Time-based fairness provides an important property in multi-rate WLANs that throughput-based fairness does not:

Baseline property:

The long-term throughput of a node competing against any number of nodes running at different speeds is equal to the throughput that the node would achieve in an existing single-rate 802.11 WLAN in which all competing nodes were running at its rate.

I.e., the throughput a node achieves when competing against n nodes is identical to what it would achieve if it were competing against n nodes all using its data rate. Fairness is, of course, a subjective notion (as any parent of multiple children knows). We do not claim that one notion is ``fairer'' than the other. However, we do point out that in the presence of rate diversity during congested periods, time-based fairness does improve the overall network performance. In this paper, we:

• Examine the impact of both time-based and throughput-based fairness on various measures of network efficiency
• Present an analytic framework in which the impact of rate diversity on the network performance is quantitatively evaluated for each fairness notion used
• Validate our model against a deployed 802.11b network
• Show, by collecting and analyzing trace data, that current 802.11b networks indeed suffer the predicted performance degradation in the presence of rate diversity
• Present an effective and efficient scheme, TBR (for Time-based Regulator), for deploying time-based fairness in existing AP-based WLANs, irrespective of the MAC protocol used
• Describe an efficient 802.11-based implementation of TBR that requires changing only the driver on the access point, and
• Demonstrate the relative advantage of time-based fairness, both analytically (using our model) and experimentally (using the 802.11-based implementation)

The rest of this paper is organized as follows. Section 2 analyzes the expected performance impact of both notions of fairness and examines which notion of fairness DCF achieves under various circumstances. Section 3 presents network trace analyses and experiments that demonstrate that rate diversity is common in today's networks. Section 4 describes in detail our scheme to achieve the time-based fairness, Section 5 evaluates our scheme's performance and Section 6 discusses related work.