Live video traffic has been widely observed to vary significantly within short timescale. In order to manage such traffic dynamic of overlay live streaming, the Content Provider (CP) may deploy a set of geo-dispersed auto-scaling servers where the pay-as-you-go deployment cost is charged by the amount of resources used due to server uploading and data transmission between servers. To support geo-distributed user demands, we study a novel multi-origin multi-channel auto-scaling live streaming cloud that pushes each channel stream in the core network overlay as a tree covering the end servers who have local demand for the channel. The Origin-to-End (O2E) delay from an origin to an end server is due to the Server-to-Server (S2S) delays of the overlay links along the path. By optimizing the overlay of the core network, we seek to minimize the deployment cost and O2E delays of the channels (i.e., a bi-criteria problem), which can be equivalently phrased as minimizing the deployment cost while meeting certain given maximum O2E delay constraints. We formulate a realistic problem capturing the major cost and delay components, and show its NP-hardness. We proposeCost-optimized Multi-Origin Multi-ChannelOverlayStreaming (COCOS), a novel, efficient and near-optimal bi-criteria approximation algorithm with proven approximation ratio. Trace-driven extensive experimental results based on real-world live streaming service data validate that COCOS outperforms other state-of-the-art schemes by a wide margin (cutting the cost in general by more than 50%).

In a video-on-demand (VoD) service, blockbuster videos have stable and predictable popularity, but the traffic can vary significantly within short timescale. To efficiently serve the user pool in a geographic region, we consider a regional auto-scaling cloud-based data center consisting of multiple servers. For efficient storage, we partition the videos into fixed-size blocks. To respond to dynamic user traffic in a timely and cost-effective manner, we may activate or deactivate each server according to the traffic while keeping at least one replica for each block in the active servers. We maximize the user capacity of the active servers (and hence minimizing the number of active servers at any time) by jointly optimizing block allocation in the servers, server selection at each traffic level, and request dispatching to a server. We believe that this is the first work to study such problem for an auto-scaling cloud-based VoD data center. We first formulate the problem and show its NP-hardness. We then propose AVARDO (Auto-scalingVideoAllocation andRequestDistributionOptimization), a simple but efficient approximation algorithm with proven optimality. AVARDO operates the servers like a stack, with a server being pushed into or popped from the existing active server set according to some optimized traffic thresholds. We prove that AVARDO approaches the theoretical optimum as the block size reduces. Trace-driven experimental results based on large-scale real-world video data further validate that AVARDO is closely optimal. It achieves significantly higher user capacity as compared with other state-of-the-art and traditional schemes, and reduces the optimality gap by multiple times.

We consider providing large-scale Netflix-like video-on-demand (VoD) service on a cloud platform, where cloud proxy servers are placed close to user pools. Videos may have heterogeneous popularity at different geo-locations. A repository provides video backup for the network, and the proxy servers collaboratively store and stream videos. To deploy the VoD cloud, the content provider rents resources consisting of link capacities among servers, server storage, and server processing capacity to handle remote requests. We study how to minimize the deployment cost by jointly optimizing video management (in terms of video placement and retrieval at servers) and resource allocation (in terms of link, storage, and processing capacities), subject to a certain user delay requirement on video access. We first formulate the joint optimization problem and show that it is NP-hard. To address it, we propose Resource allocation And Video management Optimization (RAVO), a novel and efficient algorithm based on linear programming with proven optimality gap. For a large video pool, we propose a video clustering algorithm to substantially reduce the run-time computational complexity without compromising performance. Using extensive simulation and trace-driven real data, we show that RAVO achieves close-to-optimal performance, outperforming other advanced schemes significantly (often by multiple times).

In order to provide scalable live streaming service, a content provider often deploys an overlay cloud consisting of distributed servers which collaboratively exchange streams with each other. We consider an overlay consisting of multiple live channels originating from multiple sources. Server bandwidth and end-to-end network bandwidth are shared among these channels. The stream of each channel is divided into multiple substreams of a certain bitrate, each of which is pushed via a tree to the servers that subscribe to the channel. The critical and challenging issue is then how to optimize the topology of the substream trees so as to minimize the maximum channel delay (defined as the delay from the source to the subscribing servers). There has been little work on the optimization of such multisource multi-channel live streaming network. We first formulate the problem which comprehensively and realistically captures various delay and bandwidth components, and show that it is NP-hard. We then propose an efficient algorithm called COMMOS (Collaborative Multi-source Multi-channel Streaming Overlay) which achieves low channel delay. Extensive simulation results based on real Internet topologies show that COMMOS outperforms other state-of-the-art schemes by a wide margin (often by more than 40%), due to its better utilization of network resources.

There has recently been growing interest for content providers to provide video-on-demand (VoD) as a cloud service. In such a network, the content provider may rent heterogeneous resources (such as streaming and storage capacities ) from geographically distributed data centers deployed close to user pools. These data centers (or proxy servers) collaboratively share content with each other to serve their local users. A critical challenge is to optimize movie storage and retrieval to minimize the deployment cost consisting of streaming, storage, and network transmission between data centers. We propose a novel and effective movie storage and retrieval using linear source coding. All the movies are source-encoded once at the repository, by taking every q source symbols of movie m to generate n(m)coded symbols. These coded symbols are then distributed to the servers in the cloud. Based on a general and comprehensive cost model, we optimize n(m)and the number of symbols to retrieve from remote servers for a local movie request. The optimal solution can be efficiently computed with a linear programming (LP) formulation . Our solution is proved to asymptotically approach the global minimum cost as q increases. Even when q is low, near optimality can be achieved. To accommodate large movie pool and system parameter changes, we propose algorithms for movie grouping and on-line re-optimization which significantly reduce the computational complexity with little compromise on optimality. Through extensive simulation, our algorithm is shown to achieve the lowest cost, outperforming traditional and state-of-the-art heuristics with a substantially wide margin.