Optimization of Multimedia Flows over Data Networks

The core location problem and the peakedness characterisation
First Edition

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 English 13.00 €

InfoFor more information on VAT and other payment methods, see "Payment & VAT".

Specifications


Publisher
Presses universitaires de Louvain
Title Part
Numéro 61
Author
Jean-François Macq,
Collection
Thèses de la Faculté des sciences économiques, sociales, politiques et de communication
Language
English
Publisher Category
Applied Sciences > Electricity
BISAC Subject Heading
BUS000000 BUSINESS & ECONOMICS
Onix Audience Codes
06 Professional and scholarly
CLIL (Version 2013-2019)
3283 SCIENCES POLITIQUES
Title First Published
01 January 2005
Type of Work
Thesis

Livre broché


Publication Date
01 January 2002
ISBN-13
9782930344072
Extent
Main content page count : 160
Code
55582
Dimensions
16 x 24 x 0.9 cm
Weight
348 grammes
List Price
12.50 €
ONIX XML
Version 2.1, Version 3

Google Book Preview


Write a commentary

Contents


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