Assignment of movies to heterogeneous video servers

A video-on-demand (VOD) system provides an electronic video rental service to geographically distributed users. It can adopt multiple servers to serve many users concurrently. As a VOD system is being used and evolved, its servers probably become heterogeneous. For example, if a new server is added to expand the VOD system or replace a failed server, the new server may be faster with a larger storage size. In this paper, we investigate how to assign movies to heterogeneous servers in order to minimize the blocking probability. We prove that this assignment problem is NP-hard and derive a lower bound on the minimal blocking probability. We propose the following approach for movie assignment: (1) problem relaxation: a relaxed movie assignment problem is formulated and solved to determine the ideal load that each server should handle; (2) goal programming: three operations (namely, migration, swapping and replication) are designed to assign and re-assign the movies to the servers iteratively while fulfilling all the constraints, so that the load handled by each server is close to the ideal one. Based on this approach, we design two algorithms for movie assignment with and without replication. We demonstrate that these algorithms can find optimal or close-to-optimal assignments.