TITLE: New Methods for Large State Spaces in Performance Evaluation with Markovian Modelling - II PRINCIPAL INVESTIGATORS: Tugrul Dayar, Ph.D. Nihal Pekergin, Ph.D. OTHER RESEARCHERS: Denizhan N. Alparslan, B.S. Oleg Gusak, M.S. Jean-Michel Fourneau, Ph.D. Franck Quessette, Ph.D. INSTITUTIONS: Bilkent University, Department of Computer Engineering Universite de Versailles, Laboratoire PRiSM SUPPORT: The Scientific and Technical Research Council of Turkey (TUBITAK) Centre National de la Recherche et Scientifique (CNRS) AMOUNT: ~12,000 FF (to Turkish side) DURATION: 1 January 2000 - 31 December 2000 ABSTRACT: In this work, new methods for large state spaces in performance evaluation with Markovian modelling are investigated. New numerical and stochastic methods that will reduce the effects of the state space explosion problem encountered in analysis are trying to be developed. To this end, the modular modelling method based on synchronization and decomposition, numerical methods suitable for this method, and stochastic comparison are being considered. An improved version of a two-level algorithm that is based on decomposition and aggregation and that uses stochastic comparison to compute lower and upper bounds on probabilities of nearly completely decomposable Markov chains is given. The devised algorithm is compared with iterative aggregation-disaggregation and it is shown that it has much better running time. More suitable structures for stochastic comparison are investigated and it is shown that a transformation performed on the Markov chain leads to the computation of better st-monotone bounding matrices. The transformation of interest is one that makes the Markov chain diagonally dominant. For discrete- and continuous-time stochastic automata networks, an iterative aggregtion- disaggregation algorithm is devised. This algorithm has the property that, when possible, it performs aggregation only once. Numerical experiments are conducted on models of computer and communication systems and it is shown that the devised algorithm yields the solution in a shorter time than Block Gauss- Seidel, which is one of the best available solvers for stochastic automata networks. KEY WORDS: Markov chains, stochastic comparison, stochastic automata networks, iterative aggregation-disaggregation.