| 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. |