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.


Paperback - In het Engels 13,00 €

InfoVoor meer informatie over BTW en andere belatingsmogelijkheden, zie hieronder "Betaling & BTW".

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
01 januari 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