Project Topics
Get Complete Project Material File(s) Now! »
Direct equations of queueing theory
Queueing theory studies the dynamics of stochastic processes in a network of queueing stations, such as queue sizes, losses and delays, as a function of certain parameters. These parameters can be related to the structure of the stations (the number of servers, buffer sizes, service disciplines) or can be the distribution of the stochastic processes driving the queueing network (e.g. the rate of some exogenous Poisson arrival point process, or the law of the service times in a given station). The associated direct equations may bear either on the joint law of these stochastic processes (e.g. the queue sizes form a Markov chain in a Jackson network), or on the recursions satisfied by the random variables themselves (e.g. Lindley’s equation for the end-to-end delays for ./GI/1 FIFO queues in series).
The solution of the direct equation bears on the law of these stochastic processes and might be the steady state or the transient distribution. The solution in the recursion viewpoint might be the steady state or the transient random state random variable.
In the network probing setting, there are two types of customers in the network: the customers (or packets) sent by regular users, often referred to as cross–traffic, and the customers (or probes) sent by the prober performing the measurement experiment. The former are typically fixed, namely the prober has no way to act on the cross–traffic offered to the network, whereas the latter can be sent at will, at least in the case of active probes.
Note that probes are themselves packets. In the active measurement case, their sizes may be chosen at will within a range of values. In the case of the Internet, all IP packets contain a header carrying essential information such as the IP address of the destination, so that 0 size probes are not possible. The maximal size of an IP packet is also fixed, which translates to an upper bound on probe size. In the passive measurement case, probes are just normal packets sent as part of a given application, for instance the packets of a Transport Control Protocol (TCP) flow in charge of a file transfer. The probe sizes are then determined by the selected application and associated network protocol.
Probing actions
The observables are generated through certain actions of the network prober. We below describe what actions are allowed.
Choice of topology Whenever probes traverse more than a single station, the route they follow must be specified. We have seen in section1.1.3), and that the routes on the Internet are determined by the network functionalities, based on the addresses of the origin and destination, and that the sender has no control on (or even knowledge about) that route. Hence, a route is here an input-output/origin-destination pair. Within the IP network setting these end points correspond to interfaces in IP routers. In queueing theory, a natural incarnation is that of a route in the sense of Kelly-type networks as presented in section 1.2.3. The chief scenarios are as follows. The network probing is:
• point-to-point when probes are sent from a single source to a single destination.
• point-to-multipoint when probes are sent from a single source to multiple destinations (the network of queues traversed then has a tree-like topology).
• multipoint-to-point in the case of multiple sources to a single destination.
• multipoint-to-multipoint in the case of multiple sources to multiple destinations.
Unknown parameters and performance metrics
In the context of communication network probing, typical parameters to be identified would be:
• structure parameters of the nodes/queueing stations traversed by the probes such as the speed of the link/server, the buffer size, the service discipline used (e.g. to check neutrality, an important requirement of the IETF that packets should not be discriminated against on the basis of the application they stem from).
• cross–traffic parameters at a given node if the law of the cross–traffic is in a known parametric class, or otherwise its full distribution.
It is often desirable to estimate certain performance metrics such as the packet loss probability, or the distribution of packet latency, along a route or at a given node, in the context of incomplete knowledge of the system parameters.
Intrusiveness, bias and restitution
Since probes are processed as customers by the queueing system, and moreover have a minimum size which is positive, they interact with cross–traffic and so are inherently intrusive.
At first glance, this seems to make the inverse problems more difficult. In fact, as we shall see, intrusiveness may be useful and can be leveraged in many cases (for example see the poly-phase methods introduced below).
As a result of intrusiveness, in general, the performance metrics of the system with cross–traffic and probes differ from those of the system with cross–traffic only. The performance metrics (or the parameters) of the system « without the probes » are often referred to as the ground truth in the network probing literature. For instance the probability that a typical packet of the cross–traffic on a given route will be lost if there were no probes, or the mean cross–traffic load at the k-th router on a route, belong to the ground truth. More generally, the parameters listed above (structural or pertaining to cross–traffic) are by definition part of the ground truth.
An important question is the reconstruction of some ground truth metric from the observation or the estimation of the metric for the perturbed system. This will be referred to as restitution below. Restitution may even be needed even in the non-intrusive case (for example when probes have zero size and system time is the metric of interest) because of the sampling bias problem: a typical example is when the ground truth can be evaluated from certain time-averages and where probe-averages do not coincide with time-averages.
The prober’s path(s) to Ground Truth
Let us summarize by stressing that all paths to a given ground truth or performance metric require the following series of steps:
1. a tractable and yet realistic direct equation for the dynamics of the observables.
2. a proof of the identifiability of the perturbed metric from the observables.
3. the definition (and possibly the optimization) of estimators for these metrics.
4. the design of a restitution mechanism allowing one to reconstruct the ground truth from the perturbed or biased metrics.
The aim of the following sections is to illustrate the above in a few fundamental scenarios. Fortunately enough, some of the requirements may be relaxed in some cases, one may for instance.
• idealize step 3, by assuming an infinite time series and therefore, for example, a full knowledge of the stationary distribution of some observable; this leads to deterministic problems that will be illustrated in section 2.3.
• avoid step 4, by selecting an active probing strategy involving probes rare and small enough to have almost no impact, which justifies a claim that the perturbed and unperturbed systems are the same in practice.
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
