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