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. This paper investigates how to assign movies to heterogeneous servers in order to minimize the blocking probability. It is proven that this assignment problem is NP-hard, and a lower bound is derived on the minimal blocking probability. The following approach is proposed for assignment: 1) problem relaxation—a relaxed assignment problem is formulated and solved to determine the ideal load that each server should handle, and 2) goal programming—an assignment and reassignment are performed iteratively while fulfilling all the constraints so that the load handled by each server is close to the ideal one. This approach is generic and applicable to many assignment problems. This approach is adopted to design two specific algorithms for movie assignment with and without replication. It is demonstrated that these algorithms can find optimal or close-to-optimal assignments.