Bucket-filling : an asymptotically optimal video-on-demand network with source coding

Abstract

There has been growing interest in recent years 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 contents with each other to serve their local users. A critical challenge is hence 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 approach asymptotically the global minimum cost as q increases. Even when q is low (say, 30), 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 remarkably the lowest cost, outperforming traditional and state-of-the-art heuristics with a substantially wide margin (of multiple times in many cases).

Date of Award	2015
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology