A Fast Algorithm of the Optimal Smoothing Scheme for Transmitting Stored Video

Minimum changes bandwidth allocation (MCBA) is an optimal video transmission scheme resulting in the minimum number of rate changes with the minimum peak rate, which can reduce renegotiation frequency in statistical multiplexing service. The existing MCBA algorithm with searching frontiers, however, has a high computational complexity, which depressed the applicability of MCBA. In this paper, we design a fast algorithm of MCBA that examines for the bounded point based on the convex envelopes of the overflow and underflow curve. As a result, our algorithm can work out an MCBA scheme in a shorter time because we can find the bounded point with a linear complexity, and calculate each transmission rate within several iterations. The simulation using real video traces confirmed the philosophy and efficiency of our algorithm.