A software package that facilitates generating large Markov chain models, determines mathematical properties of the chain and computes stationary and transient distributions and mean time to absorption.

Billy's Home Page,   MARCA-Models,   Text Book

MARCA: MARkov Chain Analyzer:
William J. Stewart

MARCA: MARkov Chain Analyzer
Numerical Solution of Markov Models

MARCA Manual (Postscript version, 84 pages)

MARCA Highlights:

MARCA is a software package designed to facilitate the generation of large Markov chain models, to determine mathematical properties of the chain, to compute its stationary probability, and to compute transient distributions and mean time to absorption from arbitrary starting states. It is written in Fortran.

Application Areas:

The MARCA Modelling Facility

One of the four possible ways in which transition matrices may be generated in MARCA, is a special facility to aid in the development of Markov chain models. Some features of this facility are as follows. A complete description may be found in the MARCA Manual.

States and Transitions

The state of any Markov chain may be represented as a vector. In the MARCA generation facility, each component of this state descriptor vector is referred to as a bucket. Each bucket contains a number of balls that is equal to the value of the corresponding vector component. The evolution of the Markov chain is represented by the movement of balls among the buckets. The movement of a ball from one bucket to another is called a transition from a source bucket to a destination bucket, and the rate of transition is defined as the rate at which the source bucket loses balls to the destination bucket. A transition of particular interest is an it instantaneous transition, which means, as its name implies, that the actual movement takes no time at all. Such transitions often serve to implement scheduling policies. It is not necessary for the total number of balls in the description of one state to be equal to that in another; balls may be created or destroyed according to the model characteristics.

State Space Generation

As the states of the Markov chain are generated by MARCA, they are stored in a one dimensional array called list. Simultaneously, the matrix of transition rates is also formed and stored in compact form.

The list of states is built as follows. An initial feasible state supplied by the user is examined to determine which states it can reach in a single transition. For each possible transition, a subroutine written by the user and called rate is used to determine the rate at which transitions to the destination state, newstate, occur. If the transition rate is zero or negative the destination state is ignored. On the other hand, if the transition rate is strictly positive, a second user written subroutine called instant is invoked to see if an instantaneous transition(s) may be made from newstate. If so, the result of the instantaneous transition becomes newstate, so that it is now a single step transition from currentstate. The list of states is now searched to determine if it already contains newstate. If newstate is not in the list of states, then it is added to the end of list and a pointer which denotes the number of states in the list, is incremented by one. The rate of transition computed by rate, is stored in the appropriate location of the compacted transition rate matrix.

A sample output from the state generation phase may look as follows:
MARCA>  Generating States and Transition Matrix:

   Currently at state:     100
                          3060  Last State

   Time to generate states and matrix:    2.24 seconds

     Order of Matrix     Number of Non-zero Elements
     ---------------     ---------------------------
         N =  3060               NZ =    20320

Different levels of output are available for the list of states, ranging from a list of the first 10 states to a complete listing of all the states together with all possible destination states and transition rates to these states from each source state.
SOURCE:     1665       5   2   1   6   7   2   2
(Rate;       Index;    Description) of DESTINATIONS
0.7500D+00  1899       4   1   1   7   7   2   2
0.2250D+01  1901       4   2   1   7   7   2   2
0.1000D+01  1905       4   2   1   6   8   2   2
0.1000D+01  1906       4   2   2   6   8   2   2
0.1500D+01  1339       6   2   1   5   7   1   2
0.1500D+01  1395       6   2   1   5   7   2   1

Numerical Solutions

Once the matrix has been generated, the same global facilities for analyzing the Markov chain and computing stationary and transient distributions are available.

Thus, for example, a large number of numerical solution procedures are available. This means that MARCA has an appropriate solution method for just about any problem. There are direct solvers for tightly banded systems; iterative aggregation disaggregation for difficult NCD systems; single vector iterative methods, which use a minimum amount of memory, like SOR; and general purpose projection methods such as preconditioned Arnoldi and GMRES which provide the best performance in normal circumstances. The user has complete freedom as to which method is selected to solve a given problem. All methods work with the transition matrix stored in compact form.

Measures of Effectiveness

MARCA computes the marginal probabilities distribution for each of the components of the state descriptor vector (i.e., each bucket) as well as its mean and standard deviation. This may not be adequate for a specific application; for example, a user may wish to examine or manipulate the state probabilities of a very specific subset of states. A facility is included in MARCA to allow such interaction. A user may access the list of states, the hashing functions used to locate a given state in this list and the computed state probability vector. From these, a user may compute any measures of effectiveness needed.

XMARCA: A Graphical Interface

XMARCA is a graphical X-windows interface to MARCA. It has been designed to facilitate quick, efficient implementation and analysis of queueing network models. XMARCA allows a user to build these models using a mouse to click icons of queueing components such as stations, queues, servers, connectors, etc. and to combine these in an arbitrary fashion. XMARCA provides ``mouse-driven'' access to the same numerical solution and analysis procedures that are in MARCA.

The ``Quick-build'' feature of XMARCA allows users to create customized stations automatically by simply specifying the number and types of queues and servers in a station. A user may also ``Capture'' a group of components and identify that group as a User Defined Station, UDS, which is referenced by a single name. User Defined Stations can be archived in XMARCA libraries for use at a later time.

Unfortunately, XMARCA was built using widgets that are no longer available. It is not distributed as part of the Marca software package.

To order MARCA, please contact:

Mr. Jason M. Lamb, J.D., LL.M.
Licensing Associate,
Office of Technology Transfer,
North Carolina State University.

Mailing Address:
Poulton Innovation Center,
Campus Box 8210
1021 Main Campus Drive, Suite 200
Raleigh, NC 27695-8210

Tel: (1) 919-515-7199
Fax: (1) 919-515-3773

Keywords for Search Engines

MARCA, Markov, Markov chain, Markov process, Markov model, generation, classification, decomposability, NCD, periodicity, embedded, equilibrium, transient, mtta, effectiveness, numerical techniques, power, Gauss, SOR, Arnoldi, aggregation, blocks, projection, GMRES, preconditioning, randomization, uniformization, Runge-Kutta, Adams, sparse, storage, applications, 2D, telecommunications, reliability, queuing, queueing, networks.

Billy's Home Page,   MARCA-Models,   Text Book