Unlike other resources such as CPU or memory in a virtual machine, inter-virtual-machine (inter-VM) bandwidth has not been explicitly priced in datacenter networks. In this article, we argue that tenants of an IaaS cloud computing platform should be given the flexibility to pay more for explicitly priced datacenter bandwidth beyond traditional virtual machines, in order to achieve better (or more predictable) application performance. We show that a much simpler design principle can be followed to allocate bandwidth fairly, and desirable properties related to fairness can be more easily achieved, compared with state-of-the-art proposals. We call such a design principle cost dominant fairness, which stipulates that bandwidth should be allocated based on the total cost that a tenant incurs for running its applications in the cloud. Guided by the principle of cost dominant fairness, we explore the design space of pricing inter-VM bandwidth, as well as achieving fair bandwidth sharing among multiple tenants. Through our study, we believe that it is best to assign per-VM-pair weights based on individualized prices. We present a distributed bandwidth allocation algorithm that is theoretically supported by a network utility maximization formulation, and practically implemented as a shim layer at each virtual machine. We are also concerned with practical issues of billing, where discounts are needed to ensure that a tenant only pays for the bandwidth share that it is allocated. Finally, we have evaluated our pricing framework and per-VM-pair weighted fair bandwidth allocation in the Mininet emulation testbed and simulations.

In today's datacenter topologies, there exist multiple equal-cost paths between each pair of communicating virtual machines. Yet, splitting flows and routing them along multiple paths may lead to packet reordering, which may affect the performance of TCP. In this paper, we propose Promenade, a new protocol that uses random network coding to mitigate the negative effects of packet reordering, while at the same time achieving weighted proportional fairness in bandwidth allocation across different tenants. To achieve weighted proportional fairness when allocating bandwidth to tenants, the problem of rate control is formulated as a convex optimization problem, and Promenade uses its distributed solution as a theoretical foundation to design its bandwidth allocation protocol. With our real-world implementation of Promenade in the Mininet testbed, we are able to show that Promenade is able to achieve weighted proportional fairness in its rate control when individual flows are split into multiple paths.

Fair bandwidth allocation in datacenter networks has received a substantial amount of research attention, as multiple tenants are hosted by virtual machines in a public cloud. In the context of private datacenters, link bandwidth is shared among applications running data parallel frameworks, such as MapReduce, instead. In this paper, we introduce the rigorous definition of performance-centric fairness, with the guiding principle that the performance that data parallel applications will enjoy should be proportional to their weights. We first investigate the problem of maximizing application performance while maintaining strict performance-centric fairness. We then present an inherent tradeoff between fairness and efficiency, which is interpreted from the perspectives of bandwidth utilization and social welfare, respectively. From the first perspective, we propose an algorithm to improve bandwidth utilization by introducing an extended version of fairness. From the second perspective, we formulate an optimization problem of bandwidth allocation that maximizes the social welfare across all the applications, allowing a tunable degree of relaxation on performance-centric fairness. A distributed algorithm is then presented to solve the problem, based on dual based decomposition. With extensive simulations, we demonstrate the effectiveness of our algorithms in improving efficiency and application performance (by up to 1.4X), with flexible degree of relaxation on the performance-centric fairness.

Fair bandwidth allocation in datacenter networks has been a focus of research recently, yet this has not received adequate attention in the context of private cloud, where link bandwidth is often shared among applications running data parallel frameworks, such as MapReduce. In this paper, we introduce a rigorous definition of performance-centric fairness, with the guiding principle that the performance of data parallel applications should be proportional to their weights. We investigate the problem of maximizing application performance while maintaining strict performance-centric fairness and present the inherent tradeoff between resource utilization and fairness. We then formulate the link bandwidth allocation problem with the objective of maximizing social welfare across all applications, so that resource utilization can be manipulated and improved by allowing a tunable degree of relaxation on performance-centric fairness. Based on dual based decomposition, we present a distributed algorithm to solve this problem, and evaluate its performance with extensive simulations.

With an abundance of computing resources, cloud computing systems have been widely used to elastically offload the execution of computation-intensive applications on mobile devices, leading to performance gains and better power efficiency. However, existing works have so far focused on one application only, and multiple applications are not coordinated when sending their offloading requests to the cloud. In this paper, we propose the new technique of coalesced offloading, which exploits the potential for multiple applications to coordinate their offloading requests with the objective of saving additional energy on mobile devices. The intuition is that, by sending these requests in “bundles,” the period of time that the network interface stays in the high-power state can be reduced. We present two online algorithms, collectively referred to as Ready, Set, Go (RSG), that make near-optimal decisions on how offloading requests from multiple applications are to be best coalesced. We show, both analytically and experimentally using actual smartphones, that RSG is able to achieve additional energy savings while maintaining satisfactory performance.

As an increasing number of infrastructure-as-a-service (IaaS) cloud providers start to provide cloud computing services, they form a competition market to compete for users of these services. Due to different resource capacities and service workloads, users may observe different finishing times for their cloud computing tasks and experience different levels of service qualities as a result. To compete for cloud users, it is critically important for each cloud service provider to select an "optimalâ' price that best corresponds to their service qualities, yet remaining attractive to cloud users. To achieve this goal, the underlying rationale and characteristics in this competition market need to be better understood. In this paper, we present an in-depth game theoretic study of such a competition market with multiple competing IaaS cloud providers. We characterize the nature of noncooperative competition in an IaaS cloud market, with a goal of capturing how each IaaS cloud provider will select its optimal prices to compete with the others. Our analyses lead to sufficient conditions for the existence of a Nash equilibrium, and we characterize the equilibrium analytically in special cases. Based on our analyses, we propose iterative algorithms for IaaS cloud providers to compute equilibrium prices, which converge quickly in our study.

Thanks to the “on-demand” nature of cloud computing, a large number of applications have been recently migrated to the cloud. To take full advantage of superior connectivities between geo-distributed datacenters, application traffic can be “ferried” through the cloud to provide better service and user experience. However, implementing and deploying such inter-datacenter protocols for various applications, such as messaging, streaming and conferencing, are not without challenges, due to complex requirements of applications and unique characteristics of datacenters. In order to simplify the design and implementation of new inter-datacenter protocols, we design and implement a new system framework, called Bellini, in this paper. Bellini provides customizable elements shared by the new category of inter-datacenter protocols, including a variety of transport protocols, routing policies, and rate allocation strategies. Bellini is also optimized to perform well in virtual machines, utilizing available resources efficiently. With case studies on video conferencing and messaging, we demonstrate the benefits of Bellini when it comes to designing and evaluating new inter-datacenter protocols to serve the needs of cloud-based applications.

It is typical for enterprises to rely on services from cloud providers in order to build a scalable platform with abundant available resources to satisfy user demand, and for cloud providers to deploy a number of datacenters inter-connected with high-capacity links, across different geographical regions. In this paper, we propose that video conferencing, even with its stringent delay constraints, should also be provided as a cloud service, taking full advantage of the inter-datacenter network in the cloud. We design Airlift, a new protocol designed for the inter-datacenter network, tailored to the needs of a cloud-based video conferencing service. Airlift delivers packets in live video conferences to their respective destination datacenters, with the objective of maximizing the total throughput across all conferences, yet without violating end-to-end delay constraints. In order to simplify our protocol design in Airlift, we use intra-session network coding and the concept of conceptual flows, such that the optimization problem that can be conveniently formulated as a linear program. Our real-world implementation of Airlift has been deployed over the Amazon EC2 cloud. We show that Airlift delivers a substantial performance advantage over state-of-the-art peer-to-peer solutions.

Datacenters can be used to host large-scale video streaming services with better operational efficiency, as the multiplexing achieved by virtualization technologies allows different videos to share resources at the same physical server. Live migration of videos from servers that are overloaded to those that are under-utilized may be a solution to handle a flash crowd of requests, in the form of virtual machines (VMs). However, such migration has to be performed with a well-designed mechanism to fully utilize available resources in all three resource dimensions: storage, bandwidth and CPU cycles. In this paper, we show why the challenge of maximizing resource utilization in a video streaming datacenter is equivalent to maximizing the joint profit in the context of Nash bargaining solutions, by defining utility functions properly. Having servers participating as players to bargain with each other, and VMs as commodities in the game, trades conducted after bargaining govern VM migration decisions in each server. With extensive simulations driven by real-world traces from UUSee Inc., we show that our new VM migration algorithm based on such Nash bargaining solutions increases both the resource utilization ratio and the number of video streaming requests handled by the datacenter, yet achievable in a lightweight fashion.

With the proliferation of mobile devices in both smartphone and tablet form factors, it is intuitive and natural for users to socially interact with their collaborators or competitors in multi-party conferencing, productivity, or gaming applications. In this paper, we make a case that such social interactions should be much more spontaneous to users in these applications. We design and implement a new system framework, Reflex, to provide the required system support to achieve spontaneous social interaction with other users in the same mobile application, be they in the same living room or around the world. Reflex features a simple and intuitive application programming interface (API), and uses cloud computing services from Google App Engine to offer the scalability and performance required to support spontaneous social networking at a large scale. Reflex is able to transparently switch to local interactions over Bluetooth or Wi-Fi interfaces, available on mobile devices, whenever possible. In order to evaluate Reflex in the iOS platform, we developed a real-world music composition application, called MusicScore, from scratch on the iPad, which takes advantage of Reflex to let music composers collaborate in real time.

It is typical for video streaming service providers (such as NetFlix) to rely on services from cloud providers (such as Amazon), in order to build a scalable video streaming platform with high availability. The trend is largely driven by the fact that cloud providers deploy a number of datacenters inter-connected by high-capacity links, spanning different geographical regions. Video traffic across datacenters, such as video replication and transit server-to-customer video serving, constitutes a large portion of a cloud provider's inter-datacenter traffic. Charged by ISPs, such inter-datacenter video traffic incurs substantial operational costs to a cloud provider. In this paper, we argue that costs incurred by such inter-datacenter video traffic can be reduced or even minimized by carefully choosing paths, and by assigning flow rates on each inter-datacenter link along every path. We present Jetway, a new set of algorithms designed to minimize cloud providers' operational costs on inter-datacenter video traffic, by optimally routing video flows in an online fashion. Algorithms in Jetway are designed by following a methodical approach based on an in-depth theoretical analysis. As a highlight of this paper, we have built a real-world system framework to implement and deploy Jetway in the Amazon EC2 datacenters. With both simulations and real-world experiments using our implementation, we show that Jetway effectively helps transmitting videos across datacenters with reduced costs to cloud providers and satisfactory real-world performance.

In this paper, we present our design of MusicScore, a professional grade application on the iOS platform for music composition and live performance tracking, used by composers and amateurs alike. As its foundation, we have designed and implemented a high-quality music engraver, capable of real-time interactive rendering on mobile devices, as well as an intuitive user interface based on multi-touch, both built from scratch using Objective-C and Cocoa Touch. To make MusicScore appealing to the general population for their practice and fun, we have introduced a unique auditory capability to MusicScore, so that it can "listen" to and analyze live instrument performance in real time. In order to compensate for the imperfect audio sensing system on mobile devices, we have proposed a collaborative sensing solution to better capture music signals in real time. To maximize the accuracy of live progress tracking and performance evaluation using a mobile device, we have designed a collection of note detection and tempo-based note matching algorithms, using a combination of microphone and accelerometer sensors. Based on our real-world implementation of MusicScore, extensive evaluation results show that MusicScore can achieve acceptably low error ratios, even for music pieces performed by highly inexperienced players.

With the proliferation of multi-touch mobile devices, such as smartphones and tablets, users interact with devices in non-conventional gesture-intensive ways. As a new way to interact with mobile devices, gestures have been proven to be intuitive and natural with a minimal learning curve, and can be used in interactive multimedia applications. In order for multiple users to collaborate in an interactive manner, we propose that gestures can be streamed in multiple broadcast sessions, with each session corresponding to one of the users as the source of a gesture stream. During the interactive session, the Quality of Experience (QoE) of mobile users hinges upon delays from when gestures are entered by the source to when they are recognized by each of the receivers, which we refer to as gesture recognizing delays. In this paper, we present the design of GestureFlow, a gesture broadcast protocol designed specifically for concurrent gesture streams in multiple broadcast sessions, such that the gesture recognizing delay in each session is minimized. We motivate the effectiveness and practicality of using inter-session network coding, and address challenges introduced by the linear dependence of coded packets. We evaluate our protocol design using an extensive array of real-world experiments on mobile devices, involving a new gesture-intensive interactive multimedia application, called MusicScore, that we developed from scratch.

Multi-touch mobile devices (e.g. iPhone and iPad) and motion-sensing game controllers (e.g. Kinect for Xbox 360) share one common feature: users interact with computing devices in non-conventional gesture-intensive ways, be they multi-touch gestures on the iPad or body motion gestures with the Kinect. As a new way to interact with computing devices, gestures have been proven to be intuitive and natural, with very minimal learning curve. They can be used in applications beyond games, such as those that allow the creation of artistic and musical content in a collaborative fashion. In order for multiple users to collaborate or compete in real time, however, such gestures need to be streamed in multiple broadcast sessions with an “all-to-all” broadcast nature, with each session corresponding to one of users as a source of a gesture stream. These streams of gestures typically incur low yet bursty bit rates, but have unique requirements with respect to delay and loss. In this paper, we present the design of GestureFlow, a gesture broadcast protocol designed specifically for concurrent gesture streams in multiple broadcast sessions. We motivate the effectiveness and practicality of using inter-session network coding, and address challenges introduced by linear dependence, discovered in our extensive experiments involving a new gesture-intensive iPad application that we developed from scratch.

With the advent of mobile devices with large displays, it is intuitive and natural for users to interact with an application on a mobile device using multi-touch gestures. In this paper, we propose that these multi-touch gestures can be streamed on-the-fly among multiple participating users, making it possible to engage users in a collaborative or competitive experience. Such multi-touch streams, featuring very low streaming bit rates, can be rendered on receivers to precisely reconstruct the states of an application. We present the challenges, system framework, embedded algorithm design, and real-world evaluation of TouchTime, a new system that has been designed from scratch to facilitate the streaming of multi-touch gestures among multiple users. By seamlessly combining local computation on mobile devices and services from the "cloud," we explore the design space of suitable mechanisms to represent and packetize multi-touch gestures, and of practical protocols to transport concurrent live multi-touch streams over the Internet. Specifically, we propose an auction-based reflector selection algorithm to achieve the minimal end-to-end delay in a live multi-touch streaming session. To demonstrate TouchTime, we have developed a new real-world music composition application --- called MusicScore --- using the Apple iPad Programming SDK, and used it as our running example and experimental testbed to evaluate our design choices and implementation of TouchTime.

In peer-assisted video-on-demand (VoD) streaming systems, server bandwidth costs can be astronomical when the number of videos and peers scales up. Since peers are able to seek to an arbitrary point of playback in any video at any time, prefetching is often considered a desirable way to redistribute media content in the entire system so that less server bandwidth may be consumed. In this paper, we point out that the benefits of prefetching in peer-assisted VoD do not come without considerable upfront costs of bandwidth, and as such prefetching strategies should be carefully designed to remain beneficial, but practically carried out in a decentralized manner. We show how the challenge of minimizing server bandwidth is equivalent to maximizing the system-wide utility in the context of double auction markets, where each peer participates in a number of double auctions by bidding for and selling video segments. With simulations, we show that prefetching strategies based on such double auction markets are decentralized, and are effective in reducing the consumption of server bandwidth as well, as compared to existing alternative heuristics in the literature.