Using the exact state space of a Markov model to compute approximate stationary measures

ABSTRACT

We present a new approximation algorithm based on an exact representation of the state space S, using decision diagrams, and of the transition rate matrix R, using Kronecker algebra, for a Markov model with K submodels. Our algorithm builds and solves K Markov chains, each corresponding to a different aggregation of the exact process, guided by the structure of the decision diagram, and iterates on their solution until their entries are stable. We prove that exact results are obtained if the overall model has a product-form solution. Advantages of our method include good accuracy, low memory requirements, fast execution times, and a high degree of automation, since the only additional information required to apply it is a partition of the model into the K submodels. As far as we know, this is the first time an approximation algorithm has been proposed where knowledge of the exact state space is explicitly used.

REFERENCES

• 1: R. I. Bahar , E. A. Frohm , C. M. Gaona , G. D. Hachtel , E. Macii , A. Pardo , F. Somenzi, Algebric Decision Diagrams and Their Applications, Formal Methods in System Design, v.10 n.2-3, p.171-206, April -May 1997 [doi>10.1023/A:1008699807402]
• 2: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 3: P. Buchholz. Numerical solution methods based on structured descriptions of Markovian models. In G. Balbo and G. $erazzi, editors, Computer performance evaluation, pages 251-267. Elsevier Science Publishers B.V. (North-Holland), 1991.
• 4: Peter Buchholz , Gianfranco Ciardo , Susanna Donatelli , Peter Kemper, Complexity of Memory-Efficient Kronecker Operations with Applications to the Solution of Markov Models, INFORMS Journal on Computing, v.12 n.3, p.203-222, July 2000 [doi>10.1287/ijoc.12.3.203.12634]
• 5: Javier Campos , Susanna Donatelli , Manuel Silva, Structured Solution of Stochastic DSSP Systems, Proceedings of the 6th International Workshop on Petri Nets and Performance Models, p.91, June 02-06, 1997
• 6: K. M. Chandy, U. Iterzog, and L. Woo. Parametric analysis of queueing networks. IBM J. Res. and Dev., 19:36-42, Jan. 1975.
• 7: Hoon Choi , Kishor S. Trivedi, Approximate performance models of polling systems using Stochastic Petri nets, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.2306-2314, May 1992, Florence, Italy
• 8: G. Ciardo, G. Luettgen, and R. Siminiceanu. Eiticiem symbolic state-space construction for a-synchronous systems. In M. Nielsen and D. Simpson, editors, Application and Theory of Petri Nets 2000 (Prec. 21th Int. Conf. on Applications and Theor~y of Petri Nets, Aarhus, Denmark). Springer-Verlag, June 2000. To appear.
• 9: Gianfranco Ciardo , Andrew S. Miner, SMART: Simulation and Markovian Analyzer for Reliability and Timing, Proceedings of the 2nd International Computer Performance and Dependability Symposium (IPDS '96), p.60, September 04-06, 1996
• 10: Gianfranco Ciardo , Andrew S. Miner, Storage Alternatives for Large Structured State Spaces, Proceedings of the 9th International Conference on Computer Performance Evaluation: Modelling Techniques and Tools, p.44-57, June 03-06, 1997
• 11: Gianfranco Ciardo , Andrew S. Miner, A Data Structure for the Efficient Kronecker Solution of GSPNs, Proceedings of the The 8th International Workshop on Petri Nets and Performance Models, p.22, September 08-10, 1999
• 12: Gianfranco Ciardo , Kishor S. Trivedi, A decomposition approach for stochastic reward net models, Performance Evaluation, v.18 n.1, p.37-59, July 1993 [doi>10.1016/0166-5316(93)90026-Q]
• 13: S. Donatelli, Superposed stochastic automata: a class of stochastic Petri nets with parallel solution and distributed state space, Performance Evaluation, v.18 n.1, p.21-36, July 1993 [doi>10.1016/0166-5316(93)90025-P]
• 14: Paulo Fernandes , Brigitte Plateau , William J. Stewart, Efficient descriptor-vector multiplications in stochastic automata networks, Journal of the ACM (JACM), v.45 n.3, p.381-414, May 1998 [doi>10.1145/278298.278303]
• 15: P. Heidelberger and K. S. Trivedi. Queueing network models for parallel processing with asynchronous tasks. IEEE 7)~ans. Comp., C-31(}1):1099-1109, Nov. 1982.
• 16: P. Heidelberger and K. S. Trivedi. Analytic queueing models for programs with internal concurrency. IEEE Trans. Comp., C-32(1):73-82, Jan. :{983.
• 17: O. C. Ibe, R. C. Howe, and K. S. Trivedi. Approximate availability analysis of VAXcluster systems. IEEE Trans. Ret., 38(1):146-152, Apr. 1989.
• 18: V. Mainkar , K. S. Trivedi, Fixed point iteration using stochastic reward nets, Proceedings of the Sixth International Workshop on Petri Nets and Performance Models, p.21, October 03-06, 1995
• 19: Andrew S. Miner , Gianfranco Ciardo, Efficient Reachability Set Generation and Storage Using Decision Diagrams, Proceedings of the 20th International Conference on Application and Theory of Petri Nets, p.6-25, June 21-25, 1999
• 20: Enric Pastor , Oriol Roig , Jordi Cortadella , Rosa M. Badia, Petri Net Analysis Using Boolean Manipulation, Proceedings of the 15th International Conference on Application and Theory of Petri Nets, p.416-435, June 20-24, 1994
• 21: Brigitte Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.147-154, August 1985, Austin, Texas, United States
• 22: K. C. Sevcik. Priority scheduling disciplines in queueing network models of computer systems. In 1977 IFIP Congr. Prec., 1977.
• 23: A. Srinivasan, T. Kam, S. Malik, and R. K. Brayton. Algorithms for discrete function manipulation. In International Conference on CAD, pages 92-95. IEEE Computer Society~ 1990.
• 24: W. J. Stewart, K. Atif, and B. Plateau. The numerical solution of stochastic automata networks. Europ. J. of Oper. Res., 86:503-525, 1995.
• 25: Y. Takahashi. Aggregate approximation for acyclic queuing networks with communication blocking. In It. G. Perros and T. Altiok, editors, Queueing Networks with Blocking, pages 33-47. Elsevier Science Publishers B.V., 1989.
• 26: Lorrie A. Tomek , Kishor S. Trivedi, Fixed Point Iteration in Availability Modeling, Proceedings of the 5th International GI/ITG/GMA Conference on Fault-Tolerant Computing Systems, Tests, Diagnosis, Fault Treatment, p.229-240, September 25-27, 1991
• 27: C. Murray Woodside, Throughput calculation for basic stochastic rendezvous networks, Performance Evaluation, v.9 n.2, p.143-160, April 1989 [doi>10.1016/0166-5316(89)90039-4]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Performance, Theory