TITLE: New Methods for Large State Spaces in Performance Evaluation with Markovian Modelling - I PRINCIPAL INVESTIGATORS: Tugrul Dayar, Ph.D. Jean-Michel Fourneau, Ph.D. OTHER RESEARCHERS: Denizhan N. Alparslan, B.S. Nihal Pekergin, Ph.D. Oleg Gusak, M.S. 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 Scientifique (CNRS) AMOUNT: ~15,000 FF (to Turkish side) DURATION: 1 January 1999 - 31 December 1999 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. For stochastic automata networks, a state space analysis algorithm that classifies the states in a system as transient and recurrent, and a partitioning algorithm that decomposes the system into nearly completely decomposable blocks using the first algorithm are devised. Numerical experiments are conducted with both algorithms on three large examples. Besides, an improved version using reordering of states of a two-level algorithm that is based on decomposition and aggregation and that uses stochastic comparison to compute lower and upper bounds on transient and/or stationary probabilities of nearly completely decomposable Markov chains is given. It is shown that the st-monotone lower and upper bounding Markov chains computed at both levels of this algorithm each possess a single irreducible class of states. A new algorithm that computes a lower bounding st-monotone Markov chain for a given Markov chain is devised. Numerical experiments are performed with the two-level algorithm on a system having a single cell and a single carrier and that integrates data and two types of voice calls in a wirelless network. KEY WORDS: Markov chains, stationary solution, transient solution, stochastic comparison, stochastic automata networks, near complete decomposability, reordering.