A Markov chain modeling methodology for evaluating the performance and reliability of computer and communication systems
Steven Berson · 1993
Large increases in the speed of computers and the availability of large inexpensive computer memories have made Markov chains an excellent option for modeling complex computer and communication systems. However new tools and techniques are necessary to make Markov chain specification, generation, and querying more accessible to both experts and casual users. This dissertation describes an advanced environment that makes it easy for experts to specify models, generate Markov chains from those models, and query the models for results. There are three parts to this dissertation. The first part describes a language based on logic programming for specifying the building blocks of a model. These building blocks can be combined to form a complete specification. The generator for the Markov chain for the complete model is then generated from the specification and desired performance measures can be specified and computed. We refer to the specification of desired performance measures as queries against the model. The second part of the dissertation describes the language for queries and the solution/optimization techniques for evaluating these queries. These queries often involve computations on sequences or more generally patterns of states. A language based on regular grammars is defined for specifying queries. A query in this language (and a Markov chain) can be transformed into a modified Markov chain that can be fed into various existing solvers. The third major part of this dissertation involves Markov chains with an infinite state space. An important class of infinite state space Markov chains, those with block GI/M/1 or block M/G/1 form, can be effectively solved using matrix geometric solution techniques. Normal Markov chain generation techniques based on generating all the states and transitions will not work when the Markov chain has an unbounded number of states. We describe a restricted language for specifying Markov chains and we give an algorithm for deciding whether that matrix has a matrix geometric solution. We also describe a more powerful language for which an algorithm is given for deciding, in certain important cases, whether the Markov chain has a matrix geometric solution. It is also shown that for other classes of model specification, it is undecidable whether the Markov chain has a matrix geometric solution.