Predicting the distortion of a reconstructed media presentation at a receiver in the event of missing (whether late or lost) packets is difficult because of the complex distortion interactions associated with the missing packets. We propose a mathematical model, which we call Distortion Chains, for predicting the mean-square error (MSE) distortion at the receiver in the event of packet loss (note that this also includes late loss, i.e., media packets arriving after their delivery deadlines). This model provides a simple, causal approach for predicting the distortion in the reconstructed media presentation for general packet loss patterns. The idea behing Distortion Chains is analogous to the Markov Chains model from Probability Theory. Specifically, let k = (k₁,k₂,k₃,..., k_N,k_N+1,...k_M) denote an arbitrary packet loss pattern of length M. Then, the contribution to the overall distortion associated with the loss of packet k_n (for 1 ≤ n ≤ M), given that packets k₁,k₂,...,k_n-1 are already lost, is a function of at most the P previous lost packets (see Figure 1), where P is the order of the Distortion Chain. Note that through P the prediction accuracy and the complexity of the model can be traded-off. We employ Distortion Chains to construct the distortion-rate tables for hint track based streaming systems, as discussed next.

Figure 1.  Distortion Chains for distortion prediction.

The following research can be thought of as an intermediate step between a streaming system that is completely ignorant of the importance of individual packets and their interdependence and a streaming system running our advanced RaDiO framework. The motivation for such a research lies in the fact that virtually all streaming systems existing in practice today can be accurately described as the former one. Therefore, we feel that a streaming system based on the research proposed in this section can be the first example of intelligent or media aware streaming systems and thus can represent a first step towards complete RaDiO streaming. In essence, such systems can motivate the transition towards RaDiO streaming in the Internet and hence can make it happen sooner.

We propose to design a streaming system based on a rate-distortion table and simple algorithms. Specifically, the table contains distortion-rate pairs (D_i,R_i) for different packet loss patterns, where D_i represents the reconstruction distortion associated with the loss pattern i, while R_i is the size of the pattern in bits. The algorithms comprise a method for predicting the distortion for a general packet loss pattern based on the already existing entries in the table and a decision method for finding the least harmful packet loss pattern in a rate-distortion sense. We jointly denote the table and the associated algorithms as a hint track as they are supposed to provide hints to a streaming system regarding its transmission decisions. In particular, a streaming system can then follow a hint track and make transmission decisions in the event of insufficient transmission bandwidth and/or packet loss. An illustration of the proposed system is shown in Figure 2.

Figure 2.  Low-complexity RaDiO streaming.

A hint track based streaming system achieves substantial improvement in performance over a streaming system that is oblivious to the distortion information associated with each packet, when determining the transmission schedule for the video packets. Furthermore, these gains are achieved with complexity comparable to that of the oblivious system. An alternative approach to achieving low complexity RaDiO streaming is by reducing the computational complexity of our advanced framework for packet scheduling. As part of this study, we also investigated the complexity savings relative to the advanced RaDiO framework and the associated performance-complexity trade-offs.

A major part of this research was a joint work with the Streaming Media Systems group from Hewlett-Packard Laboratories, in Palo Alto, CA, where I spent the summer of 2003 as a visiting researcher.