The Role of Wait Tolerance in Effective Batching: A Paradigm for Multimedia Scheduling Schemes

In a video-on-demand (VOD) environment, batching requests for the same video to share a common video stream can lead to significant improvement in throughput. Using the wait tolerance characteristic that is commonly observed in viewers behavior, we introduce a new paradigm for scheduling in VOD systems. We propose and analyze two classes of scheduling schemes: the Max_Batch and Min_Idle schemes, that provide two alternative ways for using a given stream capacity for effective batching. In making a video selection, the proposed schemes take into consideration the next stream completion time as well as the viewer wait tolerance. We compared the proposed schemes with the two previously studied schemes: (1) first-come-fisrt-served (FCFS) that schedules the video with the longest waiting request and (2) the maximum queue length (MQL) scheme that selects the video with the maximum number of waiting requests. We show through simulations that the proposed schemes outperform substantially FCFS and MQL in reducing the viewer turn-away probability, while maintaining a small average response time. In terms of system resources, it is found that by exploring the viewer wait tolerance, the proposed schemes can reduce significantly the server capacity required for achieving a given level of throughput and turn-away probability as compared to the FCFS and MQL. Furthermore, our study shows that an aggressive use of the viewer wait tolerance for batching may not yield the best strategy, and that other factors, such as the resulting response time and the total expected loss of viewers, should be taken into account.

By: Hadas Shachnai and Philip S. Yu

Published in: RC20038 in 1995


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.

Questions about this service can be mailed to .