TY - JOUR
T1 - Assignment of movies to heterogeneous video servers
AU - LEUNG, Yiu Wing
AU - Hou, Ricky Yuen Tan
N1 - Funding Information:
Manuscript received February 22, 2002; revised April 23, 2004. This project was supported by the RGC Research Grant HKBU 2092/01E. This paper was recommended by Associate Editor C. Hsu. The authors are with the Department of Computer Science, Hong Kong Baptist University, Kowloon Tong, Hong Kong (e-mail: ywleung@comp.hkbu.edu.hk; rickyhou@comp.hkbu.edu.hk). Digital Object Identifier 10.1109/TSMCA.2005.851136
PY - 2005/9
Y1 - 2005/9
N2 - A video-on-demand (VOD) system provides an electronic videb 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.
AB - A video-on-demand (VOD) system provides an electronic videb 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.
KW - Assignment
KW - Server system
KW - Video-on-demand (VOD)
UR - http://www.scopus.com/inward/record.url?scp=27144461257&partnerID=8YFLogxK
U2 - 10.1109/TSMCA.2005.851136
DO - 10.1109/TSMCA.2005.851136
M3 - Article
AN - SCOPUS:27144461257
SN - 1083-4427
VL - 35
SP - 665
EP - 681
JO - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
JF - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans
IS - 5
ER -