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.