Jointly optimal selection and scheduling for lossy transmission of dependent frames with delay constraint

We present a jointly optimal selection and scheduling scheme for the lossy transmission of frames governed by a dependency relation and a delay constraint over a link with limited capacity. A main application for this is scalable video streaming. Our objective is to select a subset of frames and decide their transmission schedule such that the overall video quality at the receiver is maximized. The problem is solved for two of the most common classes of dependency structures for video encoding, which include as a special case the popular hierarchical dyadic structure. We formally characterize the structural properties of an optimal transmission schedule in terms of frame dependency. It is shown that regardless of the subset of frames selected for transmission, any optimal schedule has an equivalent canonical form that is a subsequence of a unique universal sequence containing all frames. The canonical form can be computed efficiently through the construction of a dependency tree. This leads to separable but jointly optimal frame selection and scheduling algorithms that have quadratic computational complexity in the number of frames. Simulation with video traces demonstrates that the optimal scheme can substantially outperform existing suboptimal alternatives.