Online Load Balancing and First-Hop Bandwidth Allocation in Public-Area

Recent studies characterizing workloads in Public-Area Wireless Networks (PAWNs) have shown that: (i) user loads are often time varying and location-dependent; (ii) user load is often unevenly distributed across access points (APs); and (iii) 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). In this paper, we address the challenges of improving PAWN utilization and user bandwidth allocation through a common solution -- dynamic, location-aware adaptation. We observe that 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 describe how these algorithms enable the network to transparently adapt to user demands and balance load across its access points. We evaluate the effectiveness of these algorithms on improving user service rates and network utilization using simulations incorporating real workloads from campus, conference, and corporate environments. 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.Pre-2018 CSE ID: CS2003-074