Variance reduction applied to product form multiclass queuing networks

Abstract

Performance of product-form multiclass queuing networks can be determined from normalization constants. For large models, the evaluation of these performance metrics is not possible because of the required amount of computer resources (either by using normalization constants or by using MVA approaches). Such large models can be evaluated with Monte Carlo summation and integration methods. This article proposes two cluster sampling Monte Carlo techniques to deal with such models. First, for a particular type of network, we propose a variance reduction technique based on antithetic variates. It leads to an improvement of Ross, Tsang and Wang's algorithm which is designed to analyze the same family of models. Second, for a more general class of models, we use a mixture of Monte Carlo and quasi-Monte Carlo methods to improve the estimate with respect to Monte Carlo alone.

References

1. ANTONOV, I. AND SALEEV, V. 1979. An economic method of computing lp~-sequences. USSR Comput. Math. Math. Phys. 19, 1, 252-256.
2. BASKETT, F., CHANDY, M., MUNTZ, R., AND PALACIOS, J. 1975. Open, closed and mixed networks of queues with different classes of customers. J. ACM 22, 248-260.
3. BECK, J. AND CHEN, W. 1987. Irregularities of Distribution. Cambridge University Press.
4. BOREL, J., PAGES, G., AND XIAO, Y. 1991. Probabilitds numdriques, Chapter suites ~ discr~pance faible et integration num~rique. INRIA. collection didactique.
5. BOULEAU, N. AND LEPINGLE, D. 1993. Numerical Methods For Stochastic Processes. Wiley, New York.
6. BUZEN, J. 1973. Computational algorithms for closed queueing networks with exponential servers. Commun. ACM 16, 527-531.
7. CRANLEY, R. AND PATTERSON, T. 1976. Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 13, 6 (Dec.), 904-914.
8. HAMMERSLEY, J. M. AND HANDSCOMB, D.C. 1964. Monte Carlo Methods. Methuen, London.
9. KUIPERS, L. AND NIEDERREITER, H. 1974. Uniform Distribution of Sequences. Wiley, New York.
10. MCKENNA, J. AND MITRA, D. 1982. Integral representations and asymptotic expansions for closed Markovian queueing networks: Normal usage. Bell Syst. Tech. J. 61, 5 (May-June), 661-683.
11. MCKENNA, J. AND MITRA, D. 1984. Asymptotic expansions and integral representations of moments of queue lengths in closed Markovian networks. J. ACM 31, 2 (April), 346-360.
12. MCKENNA, J., MITRA, D., AND RAMAKRISHNAN, K.G. 1981. A class of closed Markovian queuing networks: Integral representations, asymptotic expansions, and generalizations. Bell Syst. Tech. J. 60, 5 (May-June), 599-641.
13. MOROKOFF, W. J. AND CAFLISCH, R.E. 1984. Quasi-random sequences and their discrepancies. SIAM J. Sci. Comput., (Dec.), 1571-1599.
14. NIEDERREITER, H. 1972. Discrepancy and convex programming. Ann. Matematica 93, 89-97.
15. NIEDERREITER, H. 1978. Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Am. Math. Soc. 84, 957-1041.
16. NIEDERREITER, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. CBMS-SIAM 63, Philadelphia, PA.
17. OWEN, A.B. 1994. Monte Carlo variance of scrambled equidistribution quadrature. Tech. Rep., Dept. of Statistics, Stanford Univ.
18. OWEN, A.B. 1995. Randomly permuted (t, m, s)-nets and (t, s)-sequences. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S. Shiue, Eds., Vol. 106, Lecture Notes in Statistics, Springer, New York, 299-315.
19. OWEN, A.B. 1996. Scrambled net variance for integrals of smooth functions. Tech. Rep., Dept. of Statistics, Stanford Univ.
20. RAMAKRISHNAN, K. AND MITRA, D. 1982. An overview of PANACEA, a software package for analyzing Markovian queueing networks. Bell Syst. Tech. J. 61, 2849-2872.
21. REISER, M. AND KOBAYASHI, H. 1975. Queueing networks with multiple closed chains: Theory and computational algorithms. IBM J. Res. Devel. 19, 283-294.
22. Ross, K., TSANG, D., AND WANG, J. 1994. Monte Carlo summation and integration applied to multichain queuing networks. J. ACM 41, 6 (Nov.), 1110-1135.
23. Ross, K. AND WANG, J. 1993. Asymptotically optimal importance sampling for product-form queueing networks. ACM Trans. Model. Comput. Simul. 3, 244-268.
24. Ross, K. AND WANG, J. 1997. Implementation of Monte Carlo integration for the analysis of product-form queueing networks. Perform. Eval. 29, 4, 273-292.
25. SHAW, J. E.H. 1988. A quasirandom approach to integration in Bayesian statistics. Ann. Star. 16, 895-914.
26. SOBOL, I. 1967. The distribution of points in a cube and the approsimate evaluation of integrals. USSR Comput. Math. Math. Phys. 7, 86-112.
27. SOBOL, I. 1976. Uniformly distributed sequences with an additional uniform property. USSR Comput. Math. Math. Phys. 16, 5, 236-242.
28. TUFFIN, B. 1996. On the use of low discrepancy sequences in Monte Carlo methods. Monte Carlo Methods Appl. 2, 4, 295-320.
29. WANG, J. AND ROSS, K. 1994. Asymptotic analysis for closed multiclass queueing networks in critical usage. Queueing Syst. Theor. Appl. 16, 167-191.
30. WOZNIAKOWSKI, H. 1991. Average case complexity of multivariate integration. Bull. Am. Math. Soc. 24, 1 (Jan.), 185-194.
31. ZAREMBA, S.K. 1968. Some applications of multidimensional integration by parts. Ann. Pol. Math XXI, 85-96.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation types and techniques

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic reasoning algorithms

      • Markov-chain Monte Carlo methods

      • Sequential Monte Carlo methods