Next: Analysis
Up: Time-based Fairness Improves Performance
Previous: abstract
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.
Next: Analysis
Up: Time-based Fairness Improves Performance
Previous: abstract
Godfrey Tan
2004-05-04