The maximum factor queue length batching scheme for video-on-demand systems

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 th ey experience long waits, a good video scheduling policy needs to consider not only the batch size but also the viewer defection probabilities and wai t times. Two conventional scheduling policies for hatching are the first-co me-first-served (FCFS) policy, which schedules the video with the longest w aiting request. and the maximum queue length (MQL) policy, which selects th e video with the maximum number of waiting requests. Neither of these polic ies leads to entirely satisfactory results. MQL tends to be too aggressive in scheduling popular videos by considering only the queue length to maximi ze batch size, while FCFS has the opposite effect by completely ignoring th e queue length and focusing on arrival time to reduce defections. In this p aper, we introduce the notion of factored queue length and propose a hatchi ng policy that schedules the video with the maximum factored queue length. We refer to this as the MFQL 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. We also consider MFQL i mplementation issues. A simulation is developed to compare the proposed MFQ L variants with FCFS and MQL. Our study shows that MFQL yields excellent em pirical results in terms of standard performance measures such as average l atency time, defection rates, and fairness.