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.