Assignment of Movies to Heterogeneous Video Server

Project Description

A video-on-demand system provides an electronic 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. 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: i) Problem Relaxation: A relaxed movie assignment problem is formulated and solved to determine the ideal load that each server should handle. ii) Goal Programming: We assign and re-assign the movies to the servers iteratively while fulfilling all the constraints such that the load handled by each server is as close to the ideal one as possible. We demonstrate that the resulting assignments are optimal or close-to-optimal.

Publication

Y. W. Leung and R. Y. T. Hou, “Assignment of movies to heterogeneous video servers,” IEEE Transactions on Systems, Man and Cybernetics, vol. 35, no. 5, pp. 665-681, September 2005.