Exploring wait tolerance in effective batching for video-on-demand scheduling

In a video-on-demand (VOD) computer system, batching requests for the same video to share a common data 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 MaxBatch and MinIdle 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: first-come-first-served (FCFS) that schedules the video with the longest waiting request; and 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, we show that by exploiting the viewers 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, fairness, and loss of viewers, should be taken into account