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

We study the provisioning of large-scale video-on-demand (VoD) services to distributed users. In order to achieve scalability in user capacity overcoming the limitation in core network bandwidth, servers are deployed close to user pools. They replicate movie segments cooperatively under the constraint of their storages. Considering the realistic scenario that access delay is a function of the total traffic in the underlay link (including cross-traffic), we address the following optimization issues in the server overlay: (1) Which segments should each server replicate to achieve network-wide good locality effect? This is the so-called content replication (CR) problem; (2) Given a segment miss at a server and a number of remote servers storing the segment, which of them should serve the local server to conserve network bandwidth? This is the so-called server selection (SS) problem; and (3) Given a certain total storage budget in the VoD network, what should be the capacity allocated to each server to achieve low access delay? This is so-called storage planning (SP) problem. Clearly the decisions of CR, SS and SP are inter-dependent, and hence need to be jointly optimized. 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).