EFFICIENT VIDEO FILE ALLOCATION SCHEMES FOR VIDEO-ON-DEMAND SERVICES

A video-on-demand (VOD) server needs to store hundreds of movie titles and to support thousands of concurrent accesses. This, technically an d economically, imposes a great challenge on the design of the disk st orage subsystem of a VOD server. Due to different demands for differen t movie titles, the numbers of concurrent accesses to each movie can d iffer a lot. We define access profile as the number of concurrent acce sses to each movie title that should be supported by a VOD server. The access profile is derived based on the popularity of each movie title and thus serves as a major design goal for the disk storage subsystem . Since some popular (hot) movie titles may be concurrently accessed b y hundreds of users and a current high-end magnetic disk array (disk) can only support tens of concurrent accesses, it is necessary to repli cate and/or stripe the hot movie files over multiple disk arrays. The consequence of replication and striping of hot movie titles is the pot ential increase on the required number of disk arrays. Therefore, how to replicate, stripe, and place the movie files over a minimum number of magnetic disk arrays such that a given access profile can be suppor ted is an important problem. In this paper, we formulate the problem o f the video file allocation over disk arrays, demonstrate that it is a NP-hard problem, and present some heuristic algorithms to find the ne ar-optimal solutions. The result of this study can be applied to the d esign of the storage subsystem of a VOD server to economically minimiz e the cost or to maximize the utilization of disk arrays.