LP-SR: Approaching Optimal Storage and Retrieval for Video-on-Demand

In a distributed large-scale video-on-demand (VoD) streaming network, a content provider often deploys local servers close to their users. A movie is partitioned into k segments which the servers collaboratively replicate and retrieve ( k ≥ 1). A critical but challenging problem is how to minimize overall system deployment cost consisting of server bandwidth, server storage, and network traffic among servers. In this paper, we address this problem through jointly optimizing movie storage and retrieval in the server network. We first formulate the optimization problem and show that it is NP-hard. To address the problem, we propose a novel, effective and implementable heuristic termed LP-SR. LP-SR decomposes the optimization problem into two computationally efficient linear programs (LPs) for segment storage and retrieval, respectively. The strength of LP-SR is that it is asymptotically optimal in terms of k, and k is not high to be closely optimal (around 5 to 10 in our study). For large movie pool, we propose a movie grouping algorithm to further reduce the computational complexity without compromising much on the performance. Through extensive simulation, LP-SR is shown to perform significantly the best as compared with other state-of-the-art and traditional schemes, reducing the deployment cost by a wide margin (by multiple times in many cases). It attains performance very close to the global optimum.