Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as existing ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.

Urban environments are a particularly important application scenario for the Internet of Things (IoT). These environments are usually dense and dynamic; in contrast, IoT devices are resource-constrained, thus making reliable data collection and scalable coordination a challenge. This work leverages the fog networking paradigm to devise a multi-tier data offloading protocol suitable for diverse data-centric applications in urban IoT scenarios. Specifically, it takes advantage of heterogeneity in the network so that sensors can collaboratively offload data to each other or to mobile gateways. Second, it evaluates the performance of this offloading process through the amount of data successfully reported to the cloud. In detail, it provides an analytical characterization of data drop-off rates as a random process and derives a light-weight yet efficient method for collaborative data offloading. Finally, it shows that the proposed fog-based solution significantly decreases the data drop-off rate through both analysis and extensive trace-driven simulations based on human mobility data from real urban settings.

As infrastructure-as-a-service clouds become more popular, cloud providers face the complicated problem of maximizing their resource utilization by handling the dynamics of user demand. Auction-based pricing, such as Amazon EC2 spot pricing, provides an option for users to use idle resources at highly reduced yet dynamic prices; under such a pricing scheme, users place bids for cloud resources, and the provider chooses a threshold “spot” price above which bids are admitted. In this paper, we propose a nonlinear dynamical system model for the time-evolution of the spot price as a function of latent states that characterize user demand in the spot and on-demand markets. This model enables us to adaptively predict future spot prices given past spot price observations, allowing us to derive user bidding strategies for heterogeneous cloud resources that minimize the cost to complete a job with negligible probability of interruption. Along the way, the model also yields novel, empirically verifiable insights into cloud provider behavior. We experimentally validate our model and bidding strategy on two months of Amazon EC2 spot price data and find that our proposed bidding strategy is up to 4 times closer to the optimal strategy in hindsight compared to a baseline regression approach while incurring the same negligible probability of interruption.

As the U.S. mobile data market matures, Internet service providers (ISPs) generally charge their users with some variation on a quota-based data plan with overage charges. Common variants include unlimited, prepaid, and usage-based data plans. However, despite a recent flurry of research on optimizing mobile data pricing, few works have considered how these data plans affect users' consumption behavior. In particular, while users with such plans have a strong incentive to plan their usage over the month, they also face uncertainty in their future data usage needs that would make such planning difficult. In this work, we develop a dynamic programming model of users' consumption decisions over the month that takes this uncertainty into account. We use this model to quantify which types of users would benefit from different types of data plans, using these conditions to extrapolate the optimal types of data plans that ISPs should offer. Our theoretical findings are complemented by numerical simulations on a dataset of user usage from a large U.S. ISP. The results help mobile users to choose data plans that maximize their utilities and ISPs to gain profit by understanding their user behavior while choosing what data plans to offer.

Rate adaptation and power control are two key resource allocation mechanisms in multiuser wireless networks. In the presence of interference, how do we jointly optimize end-to-end source rates and link powers to achieve weighted max-min rate fairness for all sources in the network? This optimization problem is hard to solve as physical layer link rate functions are nonlinear, nonconvex, and coupled in the transmit powers. We show that the weighted max-min rate fairness problem can, in fact, be decoupled into separate fairness problems for flow rate and power control. For a large class of physical layer link rate functions, we characterize the optimal solution analytically by a nonlinear Perron-Frobenius theory through solving a conditional eigenvalue problem that captures the interaction of multiuser interference. We propose an iterative algorithm to compute the optimal flow rate that converges geometrically fast without any parameter configuration. Numerical results demonstrate that our iterative algorithm is computationally fast for the Shannon capacity, CDMA, and piecewise link rate functions.

Cloud Infrastructure as a Service (IaaS) providers continually seek higher resource utilization to better amortize capital costs. Higher utilization not only can enable higher profit for IaaS providers but also provides a mechanism to raise energy efficiency; therefore creating greener cloud services. Unfortunately, achieving high utilization is difficult mainly due to infrastructure providers needing to maintain spare capacity to service demand fluctuations.

A cloud computing cluster equipped with a deadline-aware job scheduler faces fairness and efficiency challenges when greedy users falsely advertise the urgency of their jobs. Penalizing such untruthfulness without demotivating users from using the cloud service calls for advanced mechanism design techniques that work together with deadline-aware job scheduling. We propose a Bayesian incentive compatible pricing mechanism based on matching by replica-surrogate valuation functions. User valuations can be discovered by the mechanism, even when the users themselves do not fully understand their own valuations. Furthermore, users who are charged a Bayesian incentive compatible price have no reason to lie about the urgency of their jobs. The proposed mechanism achieves multiple desired truthful properties such as Bayesian incentive compatibility and ex-post individual rationality. We implement the proposed pricing mechanism. Through experiments in a Hadoop cluster with real-world datasets, we show that our prototype is capable of suppressing untruthful behavior from users.

Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.

Fog computing, the distribution of computing resources closer to the end devices along the cloud-to-things continuum, is recently emerging as an architecture for scaling of the Internet of Things (IoT) sensor networking applications. Fog computing requires novel computing program decompositions for heterogeneous hierarchical settings. To evaluate these new decompositions, we designed, developed, and instrumented a fog computing testbed that includes cloud computing and computing gateway execution points collaborating to finish complex data analytics operations. In this interactive demonstration we present one fog-specific algorithmic decomposition we recently examined and adapted for fog computing: a multi-execution point linear regression decomposition that jointly optimizes operation latency, quality, and costs. The demonstration highlights the role fog computing can play in future sensor networking architectures, and highlights some of the challenges of creating computing program decompositions for these architectures. An annotated video of the demonstration is available at [5].

With growing data demand and the current dearth of spectrum, mobile operators are looking for new frequency bands to satisfy data-hungry users. One promising avenue of expansion is TV white spaces, which are currently available to secondary users as long as they do not interfere with primary (i.e., incumbent) users. In this work, we explore the benefits of offloading cellular traffic onto TV white spaces. We develop an analytical model and efficient algorithms to assign users to the cellular network or white space channels by considering their channel gains, multi-user interference on white space channels, and the cost of switching between different networks. We perform extensive data-driven simulations in two representative urban scenarios based on publicly available datasets. Our results show that white spaces can increase capacity by 16-62%, depending on the environment, but careful network selection is necessary to ensure that maximum capacity gains are realized. Moreover, we show that white spaces provide a significant benefit in serving indoor users where cellular channel conditions are poor. Specifically, our algorithms can offload up to 40% of cellular traffic to white spaces for indoor scenarios.

Internet service providers (ISPs) struggle to invest in upgrading their networks to catch up with growing mobile data demand, while users have to face significant data overage fees. Pooling ISPs' network infrastructures can potentially enable better user experience and lower prices. For example, Google recently launched a cross-carrier MVNO (mobile virtual network operator) data plan called Project Fi, where users' devices can automatically access either of two partner cellular networks or any available open WiFi network. We consider the economic impact of cross-carrier MVNOs on the mobile data market. We begin by analyzing a network selection strategy that optimizes cross-carrier users' costs. We then study ISPs' behavior, deriving the prices that partner ISPs charge the cross-carrier MVNO and that the cross-carrier MVNO charges its end users. Although the cross-carrier MVNO may lose money from selling data, it can offset this loss with side revenue, e.g., advertisement revenue when users consume more content. We derive conditions under which the cross-carrier MVNO achieves a profit and its users reduce their costs. Finally, we use a real-world network quality dataset to simulate users' network selection behavior and demonstrate the benefits of the ISP competition brought by the cross-carrier MVNO.

The growing volume of mobile data traffic has led many Internet service providers (ISPs) to cap the monthly data usage of their users and to charge overage fees, when the data caps are exceeded. Yet data caps imperfectly capture the reality of heterogeneous data usage over a month-even the same user may have varied requirements from month to month. In response, some ISPs are providing alternative avenues for users to customize data plans to their needs. In this paper, we examine a secondary data market, as for example created by China Mobile Hong Kong, in which users can buy and sell leftover data caps from one another. While similar to an auction in that users submit bids to buy and sell data, it differs from traditional double auctions in that the ISP serves as the middleman between buyers and sellers. Such a market faces two questions. First, can users learn each others' trading behavior well enough for the market to function, and second, do ISPs have a financial incentive to offer such a market? Different users' abilities to trade data depend on others, thus forcing users to not only optimize the amounts of data they bid, but also to learn and adjust for other users' trading behavior. We derive users' optimal behavior and propose an algorithm for ISPs to match buyers and sellers. We compare the optimal matchings for different ISP objectives and derive conditions under which the secondary market increases ISP revenue: while the ISP loses revenue from overage fees, it can assess administration fees and profit from the differences between the buyer and seller prices. Finally, we use one year of usage data from 100 U.S. mobile users to simulate the market dynamics and to illustrate that sustainable conditions for a revenue increase for the ISP can hold in practice.

Cloud service providers (CSPs) often face highly dynamic user demands for their resources, which can make it difficult for them to maintain consistent quality-of-service. Some CSPs try to stabilize user demands by offering sustained-use discounts to jobs that consume more instance-hours per month. These discounts present an opportunity for users to pool their usage together into a single ``job.'' In this paper, we examine the viability of a middleman, the cloud virtual service provider (CVSP), that rents cloud resources from a CSP and then resells them to users. We show that the CVSP's business model is only viable if the average job runtimes and thresholds for sustained-use discounts are sufficiently small; otherwise, the CVSP cannot simultaneously maintain low job waiting times while qualifying for a sustained-use discount. We quantify these viability conditions by modeling the CVSP's job scheduling and then use this model to derive users' utility-maximizing demands and the CVSP's profit-maximizing price, as well as the optimal number of instances that the CVSP should rent from the CSP. We verify our results on a one-month trace from Google's production compute cluster, through which we first validate our assumptions on the job arrival and runtime distributions, and then show that the CVSP is viable under these workload traces. Indeed, the CVSP can earn a positive profit without significantly impacting the CSP's revenue, indicating that the CSP and CVSP can coexist in the cloud market.

This paper presents a systematic approach for solving wireless max-min utility fairness optimization problems in multiuser wireless networks with general monotonic constraints. These problems are often challenging to solve due to their nonconvexity. By establishing a connection between this class of optimization problems and the class of conditional eigenvalue problems that can be addressed by a generalized nonlinear Perron-Frobenius theory, we show how these problems can be solved optimally using an iterative algorithm that converges geometrically fast. The mathematical development in this paper unifies previous work and allows us to handle a broader class of competitive utility functions with general nonlinear monotonic constraints. Several representative applications illustrate the effectiveness of the proposed framework, including the max-min quality-of-service subject to robust interference temperature constraints in cognitive radio networks, the min-max weighted mean-square error subject to signal-to-interference-and-noise ratio constraints in multiuser downlink systems, the max-min throughput subject to nonlinear power constraints in energyefficient wireless networks, the max-min sigmoid utility in multimedia wireless networks, and the min-max outage probability subject to outage constraints in heterogeneous wireless networks. Numerical results are presented to demonstrate the fast-convergence behavior of the algorithms to the optimal fixed-point solution characterized by our generalized nonlinear Perron-Frobenius theoretic framework.

The growing volume of mobile data traffic has led many Internet service providers (ISPs) to cap their users' monthly data usage, with overage fees for exceeding their caps. In this work, we examine a secondary data market in which users can buy and sell leftover data caps from each other. China Mobile Hong Kong recently introduced such a market. While similar to an auction in that users submit bids to buy and sell data, it differs from traditional double auctions in that the ISP serves as the middleman between buyers and sellers. We derive the optimal prices and amount of data that different buyers and sellers are willing to bid in this market and then propose an algorithm for ISPs to match buyers and sellers. We compare the optimal matching for different ISP objectives and derive conditions under which an ISP can obtain higher revenue with the secondary market: while the ISP loses revenue from overage fees, it can assess administration fees and take the differences between the buyer and seller prices. Finally, we use one year of usage data from 100 U.S. mobile users to illustrate that the conditions for a revenue increase can hold in practice.

Amazon's Elastic Compute Cloud (EC2) uses auction-based spot pricing to sell spare capacity, allowing users to bid for cloud resources at a highly reduced rate. Amazon sets the spot price dynamically and accepts user bids above this price. Jobs with lower bids (including those already running) are interrupted and must wait for a lower spot price before resuming. Spot pricing thus raises two basic questions: how might the provider set the price, and what prices should users bid? Computing users' bidding strategies is particularly challenging: higher bid prices reduce the probability of, and thus extra time to recover from, interruptions, but may increase users' cost. We address these questions in three steps: (1) modeling the cloud provider's setting of the spot price and matching the model to historically offered prices, (2) deriving optimal bidding strategies for different job requirements and interruption overheads, and (3) adapting these strategies to MapReduce jobs with master and slave nodes having different interruption overheads. We run our strategies on EC2 for a variety of job sizes and instance types, showing that spot pricing reduces user cost by 90% with a modest increase in completion time compared to on-demand pricing.

In this paper, we investigate the joint design of transmit beamforming and power control to maximize the weighted sum rate in the multiple-input single-output (MISO) cognitive radio network constrained by arbitrary power budgets and interference temperatures. The nonnegativity of the physical quantities, e.g., channel parameters, powers, and rates, is exploited to enable key tools in nonnegative matrix theory, such as the (linear and nonlinear) Perron-Frobenius theory, quasi-invertibility, and Friedland-Karlin inequalities, to tackle this nonconvex problem. Under certain (quasi-invertibility) sufficient conditions, we propose a tight convex relaxation technique that relaxes multiple constraints to bound the global optimal value in a systematic way. Then, a single-input multiple-output (SIMO)-MISO duality is established through a virtual dual SIMO network and Lagrange duality. This SIMO-MISO duality proved to have the zero duality gap that connects the optimality conditions of the primal MISO network and the virtual dual SIMO network. Moreover, by exploiting the SIMO-MISO duality, an algorithm is developed to optimally solve the sum rate maximization problem. Numerical examples demonstrate the computational efficiency of our algorithm, when the number of transmit antennas is large.

This paper presents a unifying and systematic framework to solve wireless max-min utility fairness optimization problems in multiuser wireless networks with generalized monotonic constraints. These problems are often challenging to solve due to their nonlinearity and non-convexity. Our framework leverages a general result in nonlinear Perron-Frobenius theory to characterize the global optimal solution of these problems analytically, and to design scalable and fast-convergent algorithms for the computation of the optimal solution. This work advances the state-of-the-art in handling wireless utility optimization problems with nonlinear monotonic constraints, which existing methodologies cannot handle, and also unifies previous works in this area. Several representative applications are considered to illustrate the effectiveness of the proposed framework, including max-min quality of service subject to robust interference temperature constraints in cognitive radio networks, min-max outage subject to outage constraints in heterogeneous networks, and min-max weighted MSE subject to SINR constraints in multiuser downlink system.

We study the feasibility of the total power minimization problem subject to power budget and Signal-to-Interference-plus-Noise Ratio (SINR) constraints in cognitive radio networks. As both the primary and the secondary users are allowed to transmit simultaneously on a shared spectrum, uncontrolled access of secondary users degrades the performance of primary users and can even lead to system infeasibility. To find the largest feasible set of secondary users (i.e., the system capacity) that can be supported in the network, we formulate a vector-cardinality optimization problem. This nonconvex problem is however hard to solve, and we propose a convex relaxation heuristic based on the sum-of-infeasibilities in optimization theory. Our methodology leads to the notion of admission price for spectrum access that can characterize the tradeoff between the total energy consumption and the system capacity. Price-driven algorithms for joint power and admission control are then proposed that quantify the benefits of energy-infeasibility balance. Numerical results are presented to show that our algorithms are theoretically sound and practically implementable.

A key challenge in wireless cognitive radio networks is to maximize the total throughput also known as the sum rates of all the users while avoiding the interference of unlicensed band secondary users from overwhelming the licensed band primary users. We study the weighted sum rate maximization problem with both power budget and interference temperature constraints in a cognitive radio network. This problem is nonconvex and generally hard to solve. We propose a reformulation-relaxation technique that leverages nonnegative matrix theory to first obtain a relaxed problem with nonnegative matrix spectral radius constraints. A useful upper bound on the sum rates is then obtained by solving a convex optimization problem over a closed bounded convex set. It also enables the sum-rate optimality to be quantified analytically through the spectrum of specially-crafted nonnegative matrices. Furthermore, we obtain polynomial-time verifiable sufficient conditions that can identify polynomial-time solvable problem instances, which can be solved by a fixed-point algorithm. As a by-product, an interesting optimality equivalence between the nonconvex sum rate problem and the convex max-min rate problem is established. In the general case, we propose a global optimization algorithm by utilizing our convex relaxation and branch-and-bound to compute an ε-optimal solution. Our technique exploits the nonnegativity of the physical quantities, e.g., channel parameters, powers and rates, that enables key tools in nonnegative matrix theory such as the (linear and nonlinear) Perron-Frobenius theorem, quasi-invertibility, Friedland-Karlin inequalities to be employed naturally. Numerical results are presented to show that our proposed algorithms are theoretically sound and have relatively fast convergence time even for large-scale problems

We study the network utility maximization problems in wireless networks for service differentiation that optimize the Signal-to-Interference-plus-Noise Radio (SINR) and reliability under Rayleigh fading. Though seemingly nonconvex, we show that these problems can be decomposed into an optimization framework where each user calculates a payment for a given resource allocation, and the network uses the payment to optimize the performance of the user. We study three important examples of this utility maximization, namely the weighted sum logarithmic SINR maximization, the weighted sum inverse SINR minimization and the weighted sum logarithmic reliability maximization. These problems have hitherto been solved suboptimally in the literature. By exploiting the positivity, quasi-concavity and homogeneity properties in these problems and using the nonlinear Perron-Frobenius theory, we propose fixed-point algorithms that converge geometrically fast to the globally optimal solution. Numerical evaluations show that our algorithms are stable (free of parameter configuration) and computationally fast.

Epidemic evolution is the spread of a computer or biological virus over a network. The goal is to control the speed of the epidemic evolution with limited network control resources and to study how users in the network can be infected. The epidemic evolution can be modeled by a probabilistic dynamical system over a connected graph. We consider several epidemic evolution models in the literature, and formulate their evolution control under a common framework that requires solving a non convex optimization problem with an objective that is the spectral radius function of a nonnegative matrix. We propose two algorithms to tackle this optimization problem. The first one is a suboptimal but computation ally fast algorithm based on successive convex relaxation, while the second one can compute a global optimal solution using branch-and-bound techniques that leverage some key inequalities in non negative matrix theory.

We study a utility maximization framework for spectrum sharing among cognitive secondary users and licensed primary users in cognitive radio networks. All the users maximize the network utility by adapting their signal-to-interference-plus-noise ratio (SINR) assignment and transmit power subject to power budget constraints and additional interference temperature constraint for the secondary users. The utility maximization problem is challenging to solve optimally in a distributed manner due to the nonconvexity and the tight coupling between the power budget and interference temperature constraint sets. We first study a special case where egalitarian SINR fairness is the utility, and a tuning-free distributed algorithm with a geometric convergence rate is developed to solve it optimally. Then, we answer the general utility maximization question by developing a cognitive radio network duality to decouple the SINR assignment, the transmit power and the interference temperature allocation. This leads to a utility maximization algorithm that leverages the egalitarian fairness power control as a submodule to maintain a desirable separability in the SINR assignment between the secondary and primary users. This algorithm has the advantage that it can be distributively implemented, and the method converges relatively fast. Numerical results are presented to show that our proposed algorithms are theoretically sound and practically implementable.