On Optimal Batching Policies for Video-on-Demand Storage Servers

In a video-on-demand environment, batching of video requests is often used to reduce I/O demand and improve throughput. Since viewers may defect if they experience long waits, a good video scheduling policy needs to consider not only the batch size but also the view defection probabilities and wait times. Two conventional scheduling policies for batching are the frist-come-first-served (FCFS) policy which schedules the video with the longest waiting request, and the maximum queue length (MQL) policy which selects the video with the maximum number of waiing requests. Neither of these policies leasd to entirely satisfactory results. MQL tends to be too aggressive in scheduling popular videos by only considering the queue length to maximize batch size, while FCFS has the opposite effect by completely ignoring the queue length and focusing on arrival time to reduce defections. In this paper, we introduce the notion of factored queue length and propose a batching policy that schedules the video with the maximum factored queue length. We refer to this as the MFQ policy. The factored queue length is obtained by weighting each video queue length with a factor which is biased against the more popular videos. An optimization problem is formulated to solve for the best weighting factors for the various videos. A simulation is developed to compare the proposed MFQ policy with FCFS and MQL. Our study shows that MFQ yields excellent empirical results in terms of standard performance measures such as average latency time, defection rates and fairness.