With wide application of virtualization technology, tenants are able to access isolated cloud services by renting the shared resources in Infrastructure-as-a-Service (IaaS) datacenters. Unlike ...resources such as CPU and memory, datacenter network, which relies on traditional transport-layer protocols, suffers unfairness due to a lack of virtual machine (VM)-level bandwidth guarantees. In this paper, we model the datacenter bandwidth allocation as a cooperative game, toward VM-based fairness across the datacenter with two main objectives: 1) guarantee bandwidth for VMs based on their base bandwidth requirements, and 2) share residual bandwidth in proportion to the weights of VMs. Through a bargaining game approach, we propose a bandwidth allocation algorithm, Falloc, to achieve the asymmetric Nash bargaining solution (NBS) in datacenter networks, which exactly meets our objectives. The cooperative structure of the algorithm is exploited to develop an online algorithm for practical real-world implementation. We validate Falloc with experiments under diverse scenarios and show that by adapting to different network requirements of VMs, Falloc can achieve fairness among VMs and balance the tradeoff between bandwidth guarantee and proportional bandwidth sharing. Our large-scale trace-driven simulations verify that Falloc achieves high utilization while maintaining fairness among VMs in datacenters.
Mobile edge computing (MEC) and device-to-device (D2D) offloading are two promising paradigms in the industrial Internet of Things (IIoT). In this article, we investigate task co-offloading, where ...computing-intensive industrial tasks can be offloaded to MEC servers via cellular links or nearby IIoT devices via D2D links. This co-offloading delivers small computation delay while avoiding network congestion. However, erratic movements, the selfish nature of devices and incomplete offloading information bring inherent challenges. Motivated by these, we propose a co-offloading framework, integrating migration cost and offloading willingness, in D2D-assisted MEC networks. Then, we investigate a learning-based task co-offloading algorithm, with the goal of minimal system cost (i.e., task delay and migration cost). The proposed algorithm enables IIoT devices to observe and learn the system cost from candidate edge nodes, thereby selecting the optimal edge node without requiring complete offloading information. Furthermore, we conduct simulations to verify the proposed co-offloading algorithm.
Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based ...on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept of Shapley value and its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit-sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits and encourage ISP connectivity so as to limit balkanization.
In enterprise management systems (EMS), augmented Intelligence of Things (AIoT) devices generate delay-sensitive and energy-intensive tasks for learning analytics, articulate clarifications, and ...immersive experiences. To guarantee effective task processing, in this work, we present a cloud-assisted fog computing framework with task offloading and service caching. In the framework, tasks make offloading decisions to determine local processing, fog processing, and cloud processing with the goal of minimal task delay and energy consumption, conditioned on dynamic service caching. To this end, we first propose a distributed task offloading algorithm based on noncooperative game theory. Then, we adopt the 0-1 knapsack method to realize dynamic service caching. At last, we adjust the offloading decisions for the tasks offloaded to the fog server but without caching service support. In addition, we conduct extensive experiments and the results validate the effectiveness of our proposed algorithms.
Contextual bandit is a popular sequential decision-making framework to balance the exploration and exploitation tradeoff in many applications such as recommender systems, search engines, etc. ...Motivated by two important factors in real-world applications: 1) latent contexts (or features) often exist and 2) feedbacks often have humans in the loop leading to human biases, we formulate a generalized contextual bandit framework with latent contexts. Our proposed framework includes a two-layer probabilistic interpretable model for the feedbacks from human with latent features. We design a GCL-PS algorithm for the proposed framework, which utilizes posterior sampling to balance the exploration and exploitation tradeoff. We prove a sublinear regret upper bound for GCL-PS, and prove a lower bound for the proposed bandit framework revealing insights on the optimality of GCL-PS. To further improve the computational efficiency of GCL-PS, we propose a Markov Chain Monte Carlo (MCMC) algorithm to generate approximate samples, resulting in our GCL-PSMC algorithm. We not only prove a sublinear Bayesian regret upper bound for our GCL-PSMC algorithm, but also reveal insights into the tradeoff between computational efficiency and sequential decision accuracy. Finally, we apply the proposed framework to hotel recommendations and news article recommendations, and show its superior performance over a variety of baselines via experiments on two public datasets.
We can now outsource data backups off-site to third-party cloud storage services so as to reduce data management costs. However, we must provide security guarantees for the outsourced data, which is ...now maintained by third parties. We design and implement FADE, a secure overlay cloud storage system that achieves fine-grained, policy-based access control and file assured deletion. It associates outsourced files with file access policies, and assuredly deletes files to make them unrecoverable to anyone upon revocations of file access policies. To achieve such security goals, FADE is built upon a set of cryptographic key operations that are self-maintained by a quorum of key managers that are independent of third-party clouds. In particular, FADE acts as an overlay system that works seamlessly atop today's cloud storage services. We implement a proof-of-concept prototype of FADE atop Amazon S3, one of today's cloud storage services. We conduct extensive empirical studies, and demonstrate that FADE provides security protection for outsourced data, while introducing only minimal performance and monetary cost overhead. Our work provides insights of how to incorporate value-added security features into today's cloud storage services.
How to generate more revenues is crucial to cloud providers. Evidences from the Amazon cloud system indicate that "dynamic pricing" would be more profitable than "static pricing." The challenges are: ...How to set the price in real-time so to maximize revenues? How to estimate the price dependent demand so to optimize the pricing decision? We first design a discrete-time based dynamic pricing scheme and formulate a Markov decision process to characterize the evolving dynamics of the price-dependent demand. We formulate a revenue maximization framework to determine the optimal price and theoretically characterize the "structure" of the optimal revenue and optimal price. We apply the <inline-formula> <tex-math notation="LaTeX">Q </tex-math></inline-formula>-learning to infer the optimal price from historical transaction data and derive sufficient conditions on the model to guarantee its convergence to the optimal price, but it converges slowly. To speed up the convergence, we incorporate the structure of the optimal revenue that we obtained earlier, leading to the VpQ-learning (<inline-formula> <tex-math notation="LaTeX">Q </tex-math></inline-formula>-learning with value projection) algorithm. We derive sufficient conditions, under which the VpQ-learning algorithm converges to the optimal policy. Experiments on a real-world dataset show that the VpQ-learning algorithm outperforms a variety of baselines, i.e., improves the revenue by as high as 50% over the <inline-formula> <tex-math notation="LaTeX">Q </tex-math></inline-formula>-learning, speedy <inline-formula> <tex-math notation="LaTeX">Q </tex-math></inline-formula>-learning, and adaptive real-time dynamic programming (ARTDP), and by as high as 20% over the fixed pricing scheme.
Typical analysis of content caching algorithms using the metric of steady state hit probability under a stationary request process does not account for performance loss under a variable request ...arrival process. In this paper, we instead conceptualize caching algorithms as complexity-limited online distribution learning algorithms and use this vantage point to study their adaptability from two perspectives: 1) the accuracy of learning a fixed popularity distribution and 2) the speed of learning items' popularity. In order to attain this goal, we compute the distance between the stationary distributions of several popular algorithms with that of a genie-aided algorithm that has the knowledge of the true popularity ranking, which we use as a measure of learning accuracy. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both the abovementioned measures to obtain the "learning error" representing both how quickly and how accurately an algorithm learns the optimal caching distribution and use this to determine the trade-off between these two objectives of many popular caching algorithms. Informed by the results of our analysis, we propose a novel hybrid algorithm, adaptive-least recently used, that learns both faster and better the changes in the popularity. We show numerically that it also outperforms all other candidate algorithms when confronted with either a dynamically changing synthetic request process or using real world traces.
Nowadays distributed machine learning (ML) jobs usually adopt a parameter server (PS) framework to train models over large-scale datasets. Such ML job deploys hundreds of concurrent workers, and ...model parameter updates are exchanged frequently between workers and PSs. Current practice is that workers and PSs may be placed on different physical servers, bringing uncertainty in jobs' runtime. Existing cloud pricing policy often charges a fixed price according to the job's runtime. Although this pricing strategy is simple to implement, such pricing mechanism is not suitable for distributed ML jobs whose runtime is stochastic and can only be estimated according to its placement after job admission. To supplement existing cloud pricing schemes, we design a dynamic pricing and placement algorithm, DPS, for distributed ML jobs. DPS aims to maximize the cloud service provider's profit, which dynamically calculates unit resource price upon a job's arrival, and determines job's placement to minimize its runtime if offered price is accepted to users. Our design exploits the multi-armed bandit (MAB) technique to learn unknown information based on past sales. DPS balances the exploration and exploitation stage, and selects the best price based on the reward which is related to job runtime. Our learning-based algorithm can increase the provider's profit by 200%, and achieves a sub-linear regret with both the time horizon and the total job number, compared to benchmark pricing schemes. Extensive evaluations using real-world data also validates the efficacy of DPS.
Many mobile applications require frequent wireless transmissions between the content provider and mobile devices, consuming much energy in mobile devices. Motivated by the popularity of ...prefetch-friendly or delay-tolerant apps (e.g., social networking, app updates, cloud storage), we design and implement an application-layer transmission protocol, AppATP, which leverages cloud computing to manage data transmissions for mobile apps, transferring data to and from mobile devices in an energy efficient manner. Measurements show that significantly amount of energy is consumed by mobile devices during poor connectivity. Based on this observation, AppATP adaptively seizes periods of good bandwidth condition to prefetch frequently used data with minimum energy consumption, while deferring delay-tolerant data during poor network connectivity. Using the stochastic control framework, AppATP only relies on the current network information and data queue sizes to make an online decision on transmission scheduling, and performs well under unpredictable wireless network conditions. We implement AppATP on Samsung Note 2 smartphones and Amazon EC2. Results from both trace-driven simulations and extensive real-world experiments show that AppATP can be applied to a variety of application scenarios while achieving 30-50 percent energy savings for mobile devices.
PDF
