Computation Of Loss Curve Of Multimedia Traffic
Tech ID: 10168 / UC Case 2000-138-0
BACKGROUNDThe explosion of the Internet has spawned a variety of video-based services over packet networks, such as streaming video and video-on-demand. Many of these applications require, or can benefit from, the network's ability to provide Quality-of-Service (QoS) guarantees. The QoS guarantees are usually in the form of bandwidth, end-to-end delay, or loss rate experienced by the traffic system. 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.
DESCRIPTIONScientists at the University of California have developed a deterministic algorithm for the exact computation of the entire loss curve of an elementary 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. The algorithm was able to compute the entire loss curve of a 2-hour elementary video stream in approximately 11 seconds on a Sun Ultra-2 workstation. An extension of the algorithm has been developed for MPEG-2 Transport Streams.
APPLICATIONSExperiments with several video traces suggest that the algorithm can be used in off-line environments in which the video stream is stored (e.g. video servers) as well as on-line systems such as real-time TV broadcasting. For the latter case, the video stream can be segmented to fixed time intervals and the loss curve can be constructed for each segment, facilitating per-segment QoS provisioning and call admission control. The algorithm is also useful for QoS provisioning in both IP and ATM networks.
ADVANTAGESBy characterizing only the points at which the slope of the loss curve changes, the algorithm achieves optimality in the number of points needed for the exact computation of the loss curve. The algorithm also exhibits low time- and space-complexity.
See also UC Case 2000-140, Computation of Burstiness Curve of Multimedia Traffic.
|United States Of America||Issued Patent||6,944,126||09/13/2005||2000-138|
- Tryfonas, Christos
- Varma, Anujan