Constructing dependency trees for rate-distortion optimized media streaming

Finding adequate packet transmission strategies for media streaming systems is a challenging algorithmic task. Recently, we proposed an efficient dynamic programming algorithm for streams in which the dependencies between packets, such as those prescribed between video frames by video codecs, can be modeled with a tree. In this contribution, we propose a heuristic algorithm for arbitrary dependency graphs. This algorithm consists of first transforming the dependency graph into a tree by adding dependencies, and then applying the dynamic programming algorithm on the tree thus obtained. The algorithm is both simple and efficient, as shown by experimental results on video sequences