Aggregated bounding Markov processes applied to the analysis of tandem queues

ABSTRACT

Performance evaluation of telecommunication and computer systems is essential but a complex issue in general. Quantitative analysis of systems represented by multidimensional Markov processes models is very difficult and may be intractable if there is no specific solution form. In this study, we propose an algorithm in order to derive aggregated Markov processes providing upper and lower bounds on performance measures. We prove using stochastic comparisons that these aggregated Markov processes give bounds on performance measures defined as increasing reward functions on the transient and stationary distributions. The stochastic comparison has been largely applied in performance evaluation however the state space is generally assumed to be totally ordered which induces less accurate bounds for multidimensional Markov processes.

Our proposed algorithm assumes only a preorder on the state space, and is applied to the analysis of an open tandem queueing network with rejection in order to derive loss probability bounds. Numerical results are computed from two parametric aggregation schemes: a fine and a coarse in order to show the improvement of the accuracy of the bound with respect to the state space size. We propose an attractive solution to the performance study: given a performance measure threshold, we study if it is guaranteed or not by studying less complex aggregated bounding processes.

REFERENCES

• 1: Hind Castel-Taleb , Lynda Mokdad, Performance measure bounds in mobile networks by state space reduction, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.397-406, September 27-29, 2005 [doi>10.1109/MASCOT.2005.53]
• 2: H. Castel-Taleb , L. Mokdad , N. Pekergin, Loss rates bounds for IP switches in MPLS networks, Proceedings of the IEEE International Conference on Computer Systems and Applications, p.208-214, March 08-08, 2006 [doi>10.1109/AICCSA.2006.205091]
• 3: H. Castel, J. M. Fourneau, N. Pekergin, "Stochastic bounds on partial ordering: application to memory overflows due to bursty arrivals", 20th International Symposium on Computer and Information Sciences (ISCIS 2005), October 26-28 2005, Istanbul, Turkey, published in LNCS by Springer-Verlag.
• 4: M. Doisy, "Comparaison de processus Markoviens", PHD thesis, Univ. de Pau et des pays de l'Adour 92.
• 5: Jean-Michel Fourneau , Nihal Pekergin, An Algorithmic Approach to Stochastic Bounds, Performance Evaluation of Complex Systems: Techniques and Tools, Performance 2002, Tutorial Lectures, p.64-88, January 2002
• 6: T. Lindvall, "Lectures on the coupling method", Wiley series in Probability and Mathematical Statistics, 1992.
• 7: T. Lindvall, "Stochastic monotonicities in Jackson queueing networks", Prob. in the Engineering and Informational Sciences 11, 1997, 1--9.
• 8: William A. Massey, Stochastic ordering for Markov processes on partially ordered spaces, Mathematics of Operations Research, v.12 n.2, p.350-367, May 1987 [doi>10.1287/moor.12.2.350]
• 9: Harry G. Perros, Queueing networks with blocking, Oxford University Press, Inc., New York, NY, 1994
• 10: N. Pekergin, "Stochastic performance bounds by state space reduction", Performance evaluation, 36--37, (1--17), 1999.
• 11: W. J. Stewart, "An Introduction to the Numerical Solution of Markov Chains", Princeton, 1993.
• 12: D. Stoyan, "Comparison methods for queues and other stochastic models", J. Wiley and Sons, 1976.
• 13: L. Truffet, "Reduction technique for discrete time Markov chains on totally ordered space using stochastic comparisons", J. App. Prob. 37 (3), 2000.
• 14: L. Zheng, L. Zhang, "Modeling and performance analysis for IP traffic with multi-class QoS in VPN", Milcom2000, 21st Century Military Communications Conference Proceedings, Vol 1, 22--25 Oct. Page 330--334.

INDEX TERMS

Keywords:
Markov processes, loss probability bounds, stochastic comparisons, tandem queueing networks