Optimization of Multimedia Flows over Data Networks

In the first part of the thesis, we address the optimization of multimedia
applications such as videoconferences or multi-player games in which user-
dependent information has to be sent from the users to a core node to be
chosen, and then global information has to be multicast back from the core
node to all users. For a given communication network, this optimization seeks
a core node under two potentially competing criteria, one being the sum of the
distances the users, the other being the cost of connecting this core node and
the users with a multicast (or Steiner) tree. We first consider the problem of
minimizing a weighted sum of the two criteria and propose a heuristic which
rapidly computes a solution guaranteed to be within a few percent of the
optimum. Then we characterize the worst-case trade-offs between the two
criteria and show that there always exists a core location for which each
criterion is close to its minimum value.

The second part concerns the protection of multimedia streaming applications
against packet losses. By adding redundancy within blocks of consecutive data
packets, losses can be recovered by the receiver unless long bursts of packets
are lost inside the network. It has thus been observed that splitting packet
streams onto several paths typically decreases the probability of an
irrecoverable loss. Whereas current approaches rely on an exact computation of
the probability and are consequently restricted to very small network
instances, we propose to approximate this probability by measuring the impact
of the chosen routing on the peakedness of the received packet stream. The
peakedness of a stream may be seen as a measure of how packets are spread over
time within the stream. Numerical experiments are presented and show that our
method yields good approximations of the probability of irrecoverable loss.