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.