Optimization of Multimedia Flows over Data Networks

The core location problem and the peakedness characterisation
Première édition

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.


Livre broché - En anglais 13,00 €

InfoPour plus d'informations à propos de la TVA et d'autres moyens de paiement, consultez la rubrique "Paiement & TVA".
Info Les commandes en ligne se font via notre partenaire i6doc.

Spécifications


Éditeur
Presses universitaires de Louvain
Partie du titre
Numéro 61
Auteur
Jean-François Macq,
Collection
Thèses de la Faculté des sciences économiques, sociales, politiques et de communication
Langue
anglais
Catégorie (éditeur)
Sciences appliquées > Electricité
BISAC Subject Heading
BUS000000 BUSINESS & ECONOMICS
Code publique Onix
06 Professionnel et académique
CLIL (Version 2013-2019 )
3283 SCIENCES POLITIQUES
Date de première publication du titre
01 janvier 2005
Subject Scheme Identifier Code
Classification thématique Thema: Sciences politiques et théorie
Type d'ouvrage
Thèse

Livre broché


Date de publication
01 janvier 2005
ISBN-13
978-2-93034-490-4
Ampleur
Nombre de pages de contenu principal : 134
Code interne
71757
Format
16 x 24 x 0,8 cm
Poids
229 grammes
Prix
13,00 €
ONIX XML
Version 2.1, Version 3

Google Livres Aperçu


Publier un commentaire sur cet ouvrage

Si vous avez une question, utilisez plutôt notre formulaire de contact

Sommaire


Contents ii

List of Abbreviations and Notations v

List of Figures vii

1 Introduction 1

1.1 Design Philosophy of the Internet . . . . . . . . . . . . . . . . 1

1.2 Shortcomings of the Internet Architecture for Multimedia Application Support . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 Unicast vs Multicast Routing . . . . . . . . . . . . . . 3

1.2.2 Automatic Repeat reQuest vs Forward Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Thesis Contribution and Organization . . . . . . . . . . . . . 6

I The Core Location Problem 9

2 Core Selection for Multimedia Applications 11

2.1 Definitions and Problem Formulation . . . . . . . . . . . . . 13

2.2 Computation of the Cost Function . . . . . . . . . . . . . . . 14

2.3 Algorithm for the Minimum Bandwidth Cost Core Location Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.1 Algorithm Description . . . . . . . . . . . . . . . . . . 18

2.3.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4 Computational Results . . . . . . . . . . . . . . . . . . . . . . 22

2.4.1 Problem Instances Generation . . . . . . . . . . . . . 22

2.4.2 Performance Measure . . . . . . . . . . . . . . . . . . 22

2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Trade-offs Between the 1-median and Steiner Criteria 29

3.1 Definition of ® and ¯ Parameters . . . . . . . . . . . . . . . . 31

3.2 Relationship between ® and ¯ . . . . . . . . . . . . . . . . . . 32

3.2.1 Basic Inequalities . . . . . . . . . . . . . . . . . . . . . 32

3.2.2 Better Inequalities Using Tree Partitions . . . . . . . . 33

3.3 Application to the Minimum Bandwidth Cost Core Location Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

II Approximation of Forward Error Correction Robustness with the Peakedness Characterization 45

4 Increasing Forward Error Correction Robustness with Multipath Routing 47

4.1 Path Diversity Models for Multimedia Streaming . . . . . . . 51

4.1.1 Network Model . . . . . . . . . . . . . . . . . . . . . . 51

4.1.2 Loss Model . . . . . . . . . . . . . . . . . . . . . . . . 52

4.1.3 Packet Traffic Modeling Issues . . . . . . . . . . . . . 55

4.1.4 Computing FEC Robustness when Routing on Parallel Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.2 Peakedness Descriptor . . . . . . . . . . . . . . . . . . . . . . 68

4.2.1 Peakedness Definition and Properties . . . . . . . . . 70

4.2.2 Using Peakedness to Approximate the robustness of FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5 Fluid Traffic Formulation 77

5.1 Rate Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.1.1 Point Processes . . . . . . . . . . . . . . . . . . . . . . 78

5.1.2 Fluid Flow Processes . . . . . . . . . . . . . . . . . . . 79

5.2 Fluid Formulation for the FEC Robustness Problem . . . . . 80

5.2.1 Network Model and Routing Assumptions . . . . . . 80

5.2.2 Fluid Interpretation of FEC Coding . . . . . . . . . . 81

5.2.3 Loss Characterization on One Arc . . . . . . . . . . . 82

5.3 Second-order Characterization of Rate Processes . . . . . . . 85

5.4 Peakedness of Rate Processes . . . . . . . . . . . . . . . . . . 87

5.4.1 Peakedness properties . . . . . . . . . . . . . . . . . . 88

5.4.2 Link with Original Peakedness Definition . . . . . . . 90

5.4.3 Peakedness Transformation Properties in Networks with Markovian Losses . . . . . . . . . . . . . . . . . 91

5.5 Quality of the Peakedness Based Approximation . . . . . . . 92

5.5.1 Parallel Arcs . . . . . . . . . . . . . . . . . . . . . . . . 93

5.5.2 More General Topologies . . . . . . . . . . . . . . . . 97

5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6 Conclusion and FutureWork 107

A List of Publications 111

A.1 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

A.2 In Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Bibliography 113