Comparison and scaling methods for performance analysis of stochastic networks

L. Leskelä.
D.Sc. Thesis, Helsinki University of Technology, 2005. (pdf)


Stochastic networks are mathematical models for traffic flows in networks with uncertainty. The goal of this thesis is to develop new methods for analyzing performance and stability of stochastic networks, helping to better understand and control uncertainty in complex distributed systems.

The thesis considers three instances of stochastic networks, each representing a specific challenge for analytical modeling. The first case studies the impact of incomplete information to a queueing network with distributed admission control. Stability conditions for various admission policies are derived, together with a numerical algorithm for performance evaluation. In the second case, stochastic comparison is used to derive performance bounds for multiclass loss networks with overflow routing. The third model is a spatial random field generated by a large number of noninteracting sources, for which scaling and renormalization are used to show how the level of randomness of the individual sources may critically affect the macroscopic statistical properties of the field.

The results of the thesis illustrate the feasibility of stochastic comparison and stochastic analysis in deriving approximations and performance bounds for complex physical networks with uncertainty. Approximations and performance bounds based on exact mathematical methods have the advantage that they explicitly state the type of circumstances required for the accuracy of the estimates. The resulting analytical formulas can sometimes reveal interesting properties that are not easily detected using numerical simulation.


Keywords: stochastic network, queueing, admission control, overflow routing, stochastic comparison, scaling, renormalization, spatial random field

AMS subject classification: 60K25, 68M20, 90B15, 90B22, 60E50, 60F17, 60G60, 60G18