motivation | topic1 | topic2 | topic3 | topic4 | topic5 | downloads

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.

  ©Copyright 2001-2003 Cal-(IT)2, Adaptive Systems Lab.