The Maximum Factor Queue Length Batching Scheme for Video-on-Demand Systems

Copyright [©] (2001) by IEEE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

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 viewer defection probabilities and wait times. Two conventional scheduling policies for batching are the first- 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 waiting requests. Neither of these policies lead to entirely satisfactory results. MQL tends to be too aggressive in scheduling popular videos by considering only 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 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 implementation issues. A simulation is developed to compare the proposed MFQL variants with FCFS and MQL. Our study shows that MFQL yields excellent empirical results in terms of standard performance measures such as average latency time, defection rates and fairness.

By: Charu C. Aggarwal, Joel L. Wolf and Philip S. Yu

Published in: IEEE Transactions on Computers, volume 50, (no 2), pages 97-110 in 2001

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

8419.ps.gz

Questions about this service can be mailed to reports@us.ibm.com .