Efficient algorithms for computation of the loss curve of video sources

The loss curve of a video source characterizes the loss rate of the video stream generated by the source as a function of the allocated buffer size for a given transmission rate. The loss curve is useful in the optimal allocation of resources when the video stream is transmitted over a packet network, so that the desired tradeoff can be reached among the loss rate, bandwidth and the buffer space to be allocated in the network. We present an algorithm for computation of the entire loss curve of an elementary video stream. In contrast to earlier algorithms which employ statistical approaches, our algorithm is deterministic and computes the exact loss curve of the video stream. The algorithm exploits the piecewise linearity of the loss curve and computes only the points at which the slope of the loss curve changes. We also present an extension of the algorithm to MPEG-2 transport streams. The efficiency of the algorithm is demonstrated by results from several example video streams. For example, the algorithm was able to compute the entire loss curve of a 2-h elementary video stream in approximately 11 s on a Sun Ultra-2 workstation.