Optimization of Multimedia Flows over Data Networks
The core location problem and the peakedness characterisation
Editie 1
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.
Voor meer informatie over BTW en andere belatingsmogelijkheden, zie hieronder "Gegevens
- Uitgever
- Presses universitaires de Louvain
- Titel deel
-
Numéro 61
- Auteur
- Jean-François Macq,
- Collectie
- Thèses de la Faculté des sciences économiques, sociales, politiques et de communication
- Taal
- Engels
- Categorie uitgever
- > Toegepaste wetenschappen > Elektriciteit
- BISAC Subject Heading
- BUS000000 BUSINESS & ECONOMICS
- Onix Audience Codes
- 06 Professional and scholarly
- CLIL (2013)
- 3283 SCIENCES POLITIQUES
- Voor het eerst gepubliceerd
- 2005
- Type werk
- Thesis
Paperback
- Publicatie datum
- 01 januari 2005
- ISBN-13
- 9782930344904
- Omvang
- Aantal pagina's hoofdinhoud : 134
- Code
- 71757
- Formaat
- 16 x 24 x 0,8 cm
- Gewicht
- 232 grams
- Aanbevolen verkoopprijs
- 13,00 €
- ONIX XML
- Version 2.1, Version 3
Google Book Preview
Schrijf een reactie
Inhoud
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