Back to Publications

Author(s) Röder, M.
Title Efficient rate-distortion optimized media streaming
Abstract This thesis considers the problem of finding optimal transmission strategies in ratedistortion optimized media streaming over a packet erasure channel with random delay. A compressed media stream, such as an audio or video stream, that is split into a set of usually interdependent data units, is to be sent to a receiver for instant playback. The data unit dependencies are modeled as a directed acyclic graph. The goal is to find transmission strategies that minimize the expected playback distortion for a given transmission rate and the loss and delay characteristics of the channel. We show that the problem can be solved in two steps. The first step is to find all optimal transmission policies for a single data unit, the second step is to combine these optimal transmission policies into optimal transmission strategies for a group of interdependent data units. We develop algorithms for both steps. For the first step, we propose branch and bound algorithms that are exact and faster than all previously proposed methods. We also propose branch and bound algorithms for the second step. They are much slower than previously proposed methods, but they are the only algorithms that are exact for any data unit dependency structure. For the special case where the dependencies between data units can be represented as a tree, we propose more efficient dynamic programming algorithms that are exact as well. We develop two heuristics to make these dynamic programming algorithms suitable for application in a practical streaming system. One heuristic reduces the computational complexity of the algorithms, the other one constructs trees for arbitrary dependency structures. Although exactness is lost by the use of these heuristics, experimental results show that the solutions found are better than the solutions found by previously proposed heuristic methods. In addition to channel simulations, the methods presented in this thesis are also evaluated in a practical streaming system on an Internet connection.
Download Roeder2007.pdf