Shortest delay scheduling algorithm for lossless quality transmission of stored VBR video under limited bandwidth

Abstract

In this paper, we propose scheduling algorithms for call admission control servers. For each requested video, the server sends it according to its smoothed profile aims at maximizing resource utilization and ease of network management. Given limited bandwidth, if the server transmits the video immediately after receiving the request, data transmitted at some intervals will not satisfy playback without loss of quality and thus conflict occurs. Delay introduction can avoid such conflict without any rate distortion. We first give an optimal algorithm to find the shortest delay with complexity <l O( n2 ) or O( n2 log n), depending on the smoothing algorithm chosen. Then, we propose a fast scheduling algorithm using a new concept: safe interval. For each requested video, through calculation of safe intervals, the server finds the shortest delay to deliver it in O(K x L), where K and L are numbers of bandwidth changes in the current residual bandwidth profile and the requested video's smoothed profile respectively. Complexity analysis on our algorithms is given as well as experimental results. Algorithm 2 for deciding whether a conflict exists is also given as part of the optimal algorithm.