Distributed joint optimization for large-scale video-on-demand

We first formulate the joint optimization problem and prove that it is NP-hard. We then propose a simple and distributed algorithm called CR-SS-SP to address it. CR-SS-SP achieves good storage allocation, replicates segments collaboratively and adaptively to achieve high locality, and selects servers efficiently with a simple lookup. Simulation results on both Internet-like and real ISP topologies show that CR-SS-SP significantly outperforms existing and state-of-the-art approaches by a wide margin (often by multiple times).