Network Performance and
Congestion Relief in Public-area Wireless Networks
We have recently characterized
workloads in Public-Area Wireless Networks (PAWNs),
and have shown that: (1) user loads are often
time varying and location-dependent; (2) user
load is often unevenly distributed across access
points (APs); and (3) the load on the APs at any
given time is not well correlated with the number
of users associated with those APs. Administrators
in such networks thus have to address the challenge
of unbalanced network utilization resulting from
unbalanced user load, and also guarantee its users
a minimum level of quality of service (e.g., sufficient
wireless bandwidth).
We have addressed the challenges of improving
PAWN utilization and user bandwidth allocation
using a common solution: dynamic, location-aware
adaptation. By adaptively varying the bandwidth
allocated to users in the wireless hop within
certain bounds, coupled with admission control
at each AP, the network can accommodate more users
as its capacity changes with time. Further, by
adaptively selecting the AP that users associate
with, the network can relieve
sporadic user congestion at popular locations
and increase the likelihood of admitting users
at pre-negotiated service levels.
We present the problem of first-hop wireless bandwidth
allocation as a special case of the wellknown
online load balancing problem, and have proved
that the general online problem of finding an
optimal assignment of users to APs in an arbitrary
network with arbitrarily sized user bandwidth
requests is NP-complete. We therefore developed
three online heuristic algorithms for first-hop
bandwidth allocation. We describe how these algorithms
enable the network to
transparently adapt to user demands and balance
load across its access points.
Finally, we have evaluated the
effectiveness of these algorithms on improving
user service rates and network utilization via
simulation, incorporating real workloads from
campus, conference, and corporate environments.
We show that our algorithms improve the degree
of balance in the system by over 45% and allocate
over 30% more bandwidth to users in comparison
to existing schemes that offer little or no load
balancing.
