Optimization of multimedia flows over data networks : the core location problem and the peakedness characterization / Optimisation des flux multimédias sur les réseaux de données : le problème de sélection du noeud central et la caractérisation par peakedness/

Macq, Jean-François
(2005)

Files

these_jfmacq.pdf
  • Open Access
  • Adobe PDF
  • 766.44 KB
Download

Details

Authors
  • Macq, Jean-FrançoisUCLouvain
    author
Supervisors
Macq, Benoit
 ;
Wolsey, Laurence
Abstract
(en) 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 to a set of user terminals, the other being the cost of connecting this core node and the terminals 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 approximation ratios for the two criteria. To state our result informally, we show that there always exists a core location for which each criterion is close to its minimum value (if we were to disregard the other criterion). In the second part, we focus on the protection of multimedia streaming applications against packet losses. Because of real-time constraints, error recovery is often achieved by Forward Error Correction (FEC) techniques which consist of partitioning the packet stream into blocks of consecutive packets and adding redundant data packets to each block. If the number of packets lost within a block is at most the number of redundant packets added, the receiver is able to recover the original data packets. Otherwise some data is irrecoverably lost. In communication networks, FEC techniques are typically impaired by the fact that packet losses are not evenly distributed among blocks but rather occur in long bursts of consecutive losses. However it has been observed that splitting the transmission of a FEC block 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Macq, J.-F. (2005). Optimization of multimedia flows over data networks : the core location problem and the peakedness characterization / Optimisation des flux multimédias sur les réseaux de données : le problème de sélection du noeud central et la caractérisation par peakedness/. https://hdl.handle.net/2078.5/129181