25-08-2017, 09:32 PM
The Case for Non-cooperative Multihoming of Users to Access Points in IEEE 802.11 WLANs
The Case for Non-cooperative.pdf (Size: 234.39 KB / Downloads: 11)
Abstract
In many cases, a mobile user has the option of
connecting to one of several IEEE 802.11 access points (APs),
each using an independent channel. User throughput in each
AP is determined by the number of other users as well as the
frame size and physical rate being used. We consider the scenario
where users could multihome, i.e., split their traffic amongst all
the available APs, based on the throughput they obtain and the
price charged. Thus, they are involved in a non-cooperative game
with each other. We convert the problem into a fluid model
and show that under a pricing scheme, which we call the cost
price mechanism, the total system throughput is maximized,
i.e., the system suffers no loss of efficiency due to selfish
dynamics. We also study the case where the Internet Service
Provider (ISP) could charge prices greater than that of the cost
price mechanism. We show that even in this case multihoming
outperforms unihoming, both in terms of throughput as well as
profit to the ISP.
INTRODUCTION
The IEEE 802.11 protocl is currently the standard for wireless
LANs (WLANs), with no fundamental difference between
the different flavors. It has been deployed ubiquitously in
airports, coffee shops and homes. Very often there is a choice
of access points (APs) to which a mobile user could connect to.
Users scan the wireless channel in order to find the AP which
shows the highest signal strength and associate to it. They then
transmit at different rates (often called the PHY rate) based
on the signal strength indicated. The algorithm that selects the
PHY rate chooses a higher rate if the signal strength is good
and progressively cuts down the rate as signal strength decays.
It achieves such rate adaptation by keeping the transmit power
almost constant, while changing the constellation used. Thus,
it would use BPSK for a bad channel, QPSK for a better one
and so on. But this also means that for a frame transmission
of the same size, some users occupy the channel longer than
others.
Related Work
There has recently been much interest in understanding the
behavior of wireless LANs. They make use of the distributed
coordination function (DCF) with an RTS-CTS handshake
and hence cannot directly be modeled in the same manner
as traditional Ethernet systems. One intriguing question has
been that of why users using different PHY rates all obtain
the same throughput. This question was studied using simulation
and experiments in [1]. In [4] the system was studied
as a two-player game, with each user trying to maximize
their individual throughput and results were presented on the
inefficiency of the system as compared to the cooperative
optimum. Bianchi [5] used fixed point analysis in order to
provide an analytical framework for 802.11 WLANs. The
results were extended in [6], to provide expressions for the
throughput of users with disparate frame sizes and PHY rates.
Our work relies heavily on the expressions obtained in the
above. The analytical work has been further extended in [7]
and a simulation based verification provided.
Organization of the Paper
The paper is organized as follows. In Section II we discuss
the game theoretic concepts used. We then discuss the required
background on 802.11 WLANs in Section III. The section
presents the expressions derived in [6] that are relevant to this
work. In Section IV, we specify the model of the WLAN with
multiple classes of users and present its fluid equivalent. We
then proceed in Section V, to study the dynamics of the system
in a non-cooperative scenario. The idea here is to show that the
system is stable using Lyapunov techniques. We next study the
efficiency of such an equilibrium in Section VI and show that
the Wardrop equilibrium is efficient. We study the economic
impact of multihoming in Section VII. We show that allowing
users to multihome does not hurt profits and that even under
differentiated pricing, multihoming outperforms unihoming in
terms of throughput. We also briefly discuss price selection
and conclude with pointers to extensions in Section VIII.
BACKGROUND ON IEEE 802.11 WLANS
We provide the relevant background on expressions relating
to the throughput of an IEEE 802.11 cell.
The single cell
We begin by recalling uplink throughput expressions for
a cell containing a single AP obtained in [6], [9]. It holds
when the nearest co-channel AP is farther away than the
carrier-sense range (as we assumed in Figure 1). We use
this throughput as a measure of the payoff derived from
associating to a particular AP. The expressions are for the
MAC layer. Let there be n active users in a single cell IEEE
802.11 WLAN contending to transmit data. Each user uses
the Distributed Coordination Function (DCF) protocol with an
RTS/CTS frame exchange before any data-ack frame exchange
and has an equal probability of the channel being allocated to
it. It is assumed that every user has infinitely many packets
backlogged in its transmission buffer. In other words, the
transmission buffer of each user is saturated in the sense that
there are always packets to transmit when a user gets a chance
to do so. It is also assumed that all the users use the same backoff
parameters. Let β denote the long run average attempt rate
per user per slot (0 ≤ β ≤ 1) in back-off time 1 (Conditions
for the existence of a unique such β are given in [7].)
Fluid Model
We wish to study the effects of the movement of masses
of individuals of each class on their individual payoffs in
a deterministic fashion. In order to do this we would like
to consider users as infinitesimally divisible, i.e., consider
a fluid model. Since all the expressions are in terms of
integral quantities, we scale the system by letting n → ∞,
i.e., we consider the case where the number of users gets
large. When scaling the number of users in this fashion, we
must preserve the relative presence of each class of users in
the whole. We then have a model, wherein different classes
of users can distribute their masses amongst the different
available APs. As before, a particular strategy distribution is
the way the population partitions itself among the different
APs available. As mentioned in the introduction, the ratio in
which the masses are divided amongst the different APs is
proportional to the probabilities of associating with them. Note
that all the payoffs would be in the expected sense, i.e., users
would actually be considering the expected payoff of assigning
particular probabilities to the different APs.
Effect on Throughput
We now turn to the question of what effect multihoming has
on the throughput of a system given a price vector P. From the
discussion of this paper so far, we would expect the throughput
to be higher and here we show that this is indeed the case.
We again have a game among the users. We would like to
know what the equilibrium of the system would look like. As
in the previous sections we identify a potential function for
the system so as to convert it into a potential game.
CONCLUSION
In this paper we have sought to make a convincing case
for ISPs to allow multihoming in IEEE 802.11 WLANs. We
constructed a fluid model of user populations in a WLAN
and understood how their throughputs varied with movement
of user masses. We showed that users charged by a simple
mechanism, using selfish dynamics would actually maximize
the system throughput when allowed the option of multihoming.
We thus established that under the multihoming scenario,
anarchy comes at zero price. We also studied the economics
of multihoming as seen by the ISP and showed that there
is no loss of profit or throughput when users are allowed to
multihome.