We study the dynamics of network selection in heterogeneous wireless networks based on client-side control. Clients in such networks selfishly select the best radio access technology (RAT) that maximizes their own throughputs. We study two general classes of throughput models that capture the basic properties of random access (e.g., Wi-Fi) and scheduled access (e.g., WiMAX, LTE, and 3G) networks. Formulating the problem as a non-cooperative game, we study its existence of equilibria, convergence time, efficiency, and practicality. Our results reveal that: 1) single-class RAT selection games converge to Nash equilibria, while an improvement path can be repeated infinitely with a mixture of classes; 2) we provide tight bounds on the convergence time of these games; 3) we analyze the Pareto-efficiency of the Nash equilibria of these games, deriving the conditions under which Nash equilibria are Pareto-optimal, and quantifying the distance of equilibria with respect to the set of Pareto-dominant points when the conditions are not satisfied; and 4) with extensive measurement-driven simulations, we show that RAT selection games converge to Nash equilibria in a small number of steps, and are amenable to practical implementation. We also investigate the impact of noisy throughput estimates, and propose solutions to handle them.

We address the problem of scheduling jobs with utilities that depend solely upon their completion-times in a shared cloud that imposes considerable uncertainty on the jobs' runtime. However, it is very hard to estimate the jobs' runtime in a shared cloud where jobs are often delayed due to reasons such as slow I/O performance and variations in memory availability. Unlike prior works, we acknowledge that runtime estimates are often erroneous and instead shift the burden of robustness to the job scheduler. Specifically, we present a scheduling problem that jointly accounts for: (i) job utilities specified as functions of their completion-time, and (ii) uncertainty in the jobs' runtime. Our proposed solution to this problem achieves lexicographic max-min fairness among the job utilities. We implement this as a robust scheduler, named RUSH, for YARN in Hadoop. Our experiments, using real-world data sets, illustrate RUSH's efficacy when compared with other commonly used schedulers.

We model and analyze a User-Equipment (UE) based wireless network selection method where individuals act on their stochastic knowledge of the expected behavior off their available networks. In particular, we focus on networks with millimeter-wave (mmWave) radio. Modeling mmWave radio access technologies (RATs) as a stochastic 3-state process based on their physical layer characteristics in Line-of-Sight (LOS), Non-Line-of-Sight (NLOS), and Outage states, we make the realistic assumption that users have no knowledge of the statistics of the RATs and must learn these while maximizing the throughput obtained. We develop an online learning-based approach to access network selection: a user-centric Multi-Armed Bandit Problem that incorporates the cost of switching access networks. We develop an online learning policy that groups network access to minimize costs for RAT selection, analyze the regret (loss due to uncertainty) of our algorithm. We also show that our algorithm obtains optimal regret and in numerical examples achieves 24% increase in total throughput compared to existing techniques for high throughput mmWave RATs that vary over a fast timescale.

There is an increasing need for cloud service performance that can be tailored to customer requirements. In the context of jobs submitted to cloud computing clusters, a crucial requirement is the specification of job completion-times. A natural way to model this specification, is through client/job utility functions that are dependent on job completion-times. We present a method to allocate and schedule heterogeneous resources to jointly optimize the utilities of jobs in a cloud. Specifically: (i) we formulate a completion-time optimal resource allocation (CORA) problem to apportion cluster resources across the jobs that enforces max-min fairness among job utilities, and (ii) starting with an integer programming problem, we perform a series of steps to transform it into an equivalent linear programming problem, and (iii) we implement the proposed framework as a utility-aware resource scheduler in the widely used Hadoop data processing framework, and finally (iv) through extensive experiments with real-world datasets, we show that our prototype achieves significant performance improvement over existing resource-allocation policies.

We study the dynamics of network selection in heterogeneous wireless networks (HetNets). Users in such networks selfishly select the best radio access technology (RAT) with the objective of maximizing their own throughputs. We propose two general classes of throughput models that capture the basic properties of random access (e.g., Wi-Fi) and scheduled access (e.g., WiMAX, LTE, 3G) networks. Next, we formulate the problem as a non-cooperative game, and study its convergence, efficiency, and practicality. Our results reveal that: (i) Single-class RAT selection games converge to Nash equilibria, while an improvement path can be repeated infinitely with a mixture of classes. We next introduce a hysteresis mechanism in RAT selection games, and prove that with appropriate hysteresis policies, convergence can still be guaranteed; (ii) We analyze the Pareto-efficiency of the Nash equilibria of these games. We derive the conditions under which Nash equilibria are Pareto-optimal, and we quantify the distance of Nash equilibria with respect to the set of Pareto-dominant points when the conditions are not satisfied; (iii) Finally, with extensive measurement-driven simulations we show that RAT selection games converge to Nash equilibria in a small number of steps, and hence are amenable to practical implementation. We also investigate the impact of noisy throughput measurements, and propose solutions to handle them.