Fast adaptive media scheduling based on expected run-time distortion

In delay-constrained multimedia communications over the Internet, scalable compressed media formats are useful in that they allow the rate and quality of video delivery to adapt to the changes in the available bandwidth. Previously, we introduced the expected run-time distortion based scheduling (ERDBS) algorithm (Miao and Ortega, Proc. 12th Int. Packet Video Workshop, 2002), which allowed the media source to select in what order packets should be transmitted, where packets contain different "layers" in the scalable representation of the transmitted signal. The basic idea of ERDBS was to calculate at any given time the "importance" of each candidate packet in the transmission buffer, and then proceed to send the most important packet. We now present techniques to reduce the complexity of the ERDBS approach, which could be significant when the set of candidate packets is large. Our proposed algorithm decomposes the packet importance calculation into several stages. We show how, through a proper decomposition of these calculations, the results obtained for some stages during past iterations can be re-used, with updates based on the new information received in the meantime. With this recursive definition of the packet importance calculation, we show that the complexity of ERDBS is reduced without sacrificing its performance.