(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
Abstract
Résumé
Organization of the dissertation
1 Introduction
1.1 Networks
1.1.1 What are networks
1.1.2 Network applications
1.1.3 Functionalities of networks
1.1.4 Abstraction of networks
1.2 Queueing theory: a microscopic model for networks
1.2.1 A single queue
1.2.2 The M/M/1 queue
1.2.3 Network of queues
1.2.4 The M/GI/1 queue
1.3 Bandwidth sharing networks: a macroscopic model
1.3.1 Bandwidth sharing networks
1.3.2 Bandwidth sharing networks are useful outside communication networks
1.3.3 One single path
1.3.4 The triangle network
1.4 Statistics
1.4.1 Parametric estimation and estimators
1.4.2 A few classical results
1.4.3 Maximum likelihood estimator
1.4.4 Expectation-Maximization (E-M) algorithm
1.4.5 Design of Experiment
1.5 Network measurements
1.5.1 Communication networks measurement
1.5.2 Internet Tomography
1.5.3 Inverse problems
1.5.4 Bibliography
1.6 Contribution of this dissertation
2 Inverse Problems in Queueing Networks
2.1 Introduction
2.2 Inverse problems in queueing theory
2.2.1 Direct equations of queueing theory
2.2.2 Noise
2.2.3 Probing actions
2.2.4 Observables
2.2.5 Unknown parameters and performance metrics
2.2.6 Intrusiveness, bias and restitution
2.2.7 Identifiability, ambiguity
2.2.8 Estimation problems
2.2.9 The prober’s path(s) to Ground Truth
2.2.10 ISP-centric inverse queueing problems
2.3 Noiseless Inverse Queueing Problems
2.3.1 The M/G/1 Queue
2.3.2 The M/M/1 Queue
2.3.3 The M/M/1/B Queue
2.3.4 The Erlang loss system
2.4 Optimal Probing Strategies
2.4.1 Sampling bias
2.4.2 Variance
2.4.3 Maximum Likelihood
2.5 Summary
2.6 Appendix
2.6.1 Packet pairs in the M/M/1 queue
2.6.2 Proof of Lemma 2.4.2
3 The Single-path Kelly Network
3.1 Introduction
3.2 The parametric model
3.2.1 The system
3.2.2 Model Limitations
3.2.3 The direct equation
3.3 An analytical solution
3.4 Noise Aware moment-based solution
3.5 Maximum likelihood estimators
3.5.1 The one station case
3.5.2 The two stations case
3.5.3 Expectation-Maximization Algorithm
3.5.4 Additive measurement noise
3.6 Experimental Validation
3.6.1 Data Sets and Traces
3.6.2 Semi-Experimental Methodology
3.6.3 Challenge: Router Model
3.6.4 Challenge: Exponential Sizes
3.6.5 Challenge: Equality of Distribution
3.6.6 Challenge: Poisson Arrivals
3.6.7 The Two Station Case
3.7 Summary
3.8 Appendix
3.8.1 Proof of Lemma 3.5.3
3.8.2 Proof of Lemma 3.5.4
4 Extension to Kelly Networks
4.1 Introduction
4.2 A Delay Tomographic Queueing Inverse Problem
4.3 E-M for Exponential Tomography
4.3.1 Specialization of the Iterative Formula
4.4 Explicit Formula for IE(l|d)
4.4.1 Notations
4.4.2 Some simple examples
4.4.3 Inductive Expression
4.4.4 More Examples
4.4.5 Explicit Expression
4.4.6 Implementation
4.4.7 Size of the expression and Complexity of the EM step
4.5 Results
4.5.1 Unary Tree Case
4.5.2 General Case
4.5.3 Speed of convergence
4.5.4 Comparison to the Least Squares Method
4.5.5 Resilience to measurement noise and imperfect models
4.6 Steered Jumping for EM
4.6.1 Analysis of the iteration
4.6.2 The Sampling Method
4.6.3 The Steered Jumping Method
4.7 Summary
4.8 Appendix
4.8.1 Proof of the Density Formula
5 Inverse Problems in Bandwidth Sharing Networks
5.1 Introduction
5.2 The static single path case
5.2.1 Direct equation
5.2.2 The inverse problem
5.2.3 Numerical application
5.3 The static triangle network
5.4 Summary
Bibliography
