LP-based optimization of storage and retrieval for distributed video-on-demand

In a distributed large-scale video-on-demand (VoD), a content provider often deploys local servers close to their users. A movie is partitioned into k segments which the servers collaboratively store and retrieve (k ≥ 1). A critical but challenging problem is how to minimize overall system deployment cost due to 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 to an integer program. To address its tractability, we propose a novel, effective and implementable heuristic. The heuristic, termed LP-SR, decomposes the 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 does not need to be high to achieve near optimality (around 5 to 10 in our study). Through extensive simulation study, 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 minimum cost.