Sensitivity Analysis of Queueing Networks

Project Description

Analytical models are particularly well suited for studying the impact of various parameters on system performance. Such studies require numerous evaluations of the model. Simulation models may lead to prohibitively long run times and the approximate nature of corresponding numerical results aggravates their interpretation in the context of sensitivity analysis.
In this research effort, matrix-analytic techniques from queueing theory are combined to establish a framework for the analysis of (large) queueing networks. In a divide-and-conquer fashion, the network is evaluated (possibly iteratively) on a node-by-node basis, while queue output traffic is characterized and directed to downstream queues as input traffic (traffic-based decomposition). Dedicated procedures for the key step of output characterization have been developed as well as new techniques for the analysis of multi-class queueing systems.
Sensitivity analysis indispensibly requires compact models to describe correlated arrival and service processes (i.e., correlated workload), in which single input parameters (like correlation coefficients of the interarrival process or higher moments of service times) can be modified independently of others. Such correlated input models have been provided in form of low-order Markovian Arrival Processes (MAPs), which moreover may also be applied efficiently in simulations.
From sensitivity analysis, new insight for network and traffic engineering could be derived in the context of cooperations with the College of William and Mary, VA, USA and the TU Budapest, Hungary. Prof. Miklos Telek visited our research group.

Project Period

    2004-01-01 – 2011-12-31

Project Members

  • Dr.-Ing. Armin Heindl
  • Prof. Dr. Miklos Telek
  • Prof. Dr. Evgenia Smirni
  • Qi Zhang

Involved Institutions

  • TU Budapest, Hungary
  • College of William and Mary, VA, USA
  1. Armin Heindl, Gábor Horváth und Karsten Gross, “Explicit Inverse Characterization of Acyclic MAPs of Second Order,” Formal Methods and Stochastic Models for Performance Evaluation, Heidelberg, Budapest, Hungary, pp. 108-122, Juni 2006
  2. Armin Heindl und Karsten Gross, “Analytic study of multiplexing effects in two-class queues with correlations,” Proc. 13th GI/ITG Conference, Berlin, Nürnberg, Germany, pp. 399-416, März 2006
  3. Sven Söhnlein und Armin Heindl, “Analytic Computation of End-To-End Delays in Queueing Networks with Batch Markovian Arrival Processes and Phase-Type Sevice Times,” Proc. of 13th International Conference on Analytic and Stochastic Modelling Techniques and Applications, Bonn, Sankt Augustin, Germany, pp. 1-7, 05, 28-31, 2006
  4. Q. Zhang, Armin Heindl und E. Smirni, “Characterizing the BMAP/MAP/1 departure process via the ETAQA truncation,” in Stochastic Models Bd. 21(2-3), pp. 821-846, 2005
  5. Q. Zhang, Armin Heindl und E. Smirni, “Models of the departure process of a BMAP/MAP/1 queue,” in ACM SIGMETRICS Performance Evaluation Review (33/2), pp. 18-20, 2005
  6. Armin Heindl, Q. Zhang und E. Smirni, “ETAQA Truncation Models for the MAP/MAP/1 Departure Process,” Proc. 1st Int. Conf. on the Quantitative Evaluation of Systems, Enschede, the Netherlands, pp. 100-109, September 2004
  7. Armin Heindl, “Sensitivity Analysis for MAP/MAP/1 Queues,” 12th GI/ITG Conf. on Measuring, Modelling and Evaluation of Computer and Communication Systems (MMB) together with 3rd Polish-German Teletraffic Symposium (PGTS), Berlin, Dresden, Germany, pp. 235-244, September 2004
  8. Armin Heindl, “Inverse Characterization of Hyperexponential MAP(2)s,” 11th Int. Conf. on Analytical and Stochastic Modelling Techniques and Applications, Magdeburg, Germany, pp. 183-189, Juni 2004