Structured Markov Matrix Market



The web-page contains solution programs and example models for structured Markovian modeling. The examples have been published in the literature over the last two or three decades. All models are structured which means that they are composed of several interacting subcomponents of the model. For each model the generator matrix is available as a set of matrices that allow one to represent the transition matrix in compact form as a hierarchical sum Kronecker product of small matrices. This format is used as input for the solution programs which are also made available. The idea of representing generator matrices in this form is for examples described in [1]. Details on the formats used to store sparse matrices and structured matrices can be found in [3]. In some cases, also a sparse representation of the whole matrix is given too. The sparse matrix format is described in [2] and may be used as input for sparse matrix solvers to compare them with the structured approaches.

Our goal is to make available an archive of examples that can be used to test numerical solvers for Markov chains and to compare their performance. Any suggestions for additional examples or changes are very welcome.

Example matrices

The following examples have been published in the literature and used in several studies as benchmark models (see [5] and [6] for the use of our own methods on the benchmarks).

MSMQ-System

The multi-server multi-queue (MSMQ) system has been introduced in [7], a structured description of the model variant that is used here can be found in [6]. We consider three versions of the model here:

  1. A small version with 3 queues. The resulting Markov chain has 1,020 states and the sparse matrix description contains 3,969 non-zero entries excluding diagonal elements. The structured description can be downloaded here, the sparse matrix representation here.

  2. A medium sized version with 5 queues. The resulting Markov chain has 42,880 states and the sparse matrix description contains 235,680 non-zero entries excluding diagonal elements. The structured description can be downloaded here, the sparse matrix representation here.

  3. A large version with 7 queues. The resulting Markov chain has 1,311,744 states and the sparse matrix description contains 9,241,344 non-zero entries excluding diagonal elements. The structured description can be downloaded here, the sparse matrix representation here.

Kanban-System

The kanban system is described in [5]. We consider three versions of the model here:

  1. A medium version with 527,076 states and 3,001,405 non-zero entries (excluding diagonal elements) in the sparse matrix description . The structured description can be downloaded here, the sparse matrix representation here.

  2. A large version with 1.742.400 states and 10,183,360 non-zero entries (excluding diagonal elements) in the sparse matrix description . The structured description can be downloaded here.

  3. A large version where machines can fail and are repaired by a repair unit. The matrix contains entries owhich differ by five orders of magnitude but the partition is not an NCD partition. The Markov chains has 2.302.911 states and 14,313,663 non-zero entries (excluding diagonal elements) in the sparse matrix description . The structured description can be downloaded here.

Courier Protocol

The Courier protocol model has been originally defined in [8], a hierarchical version containing four components can be found in [9]. We consider two different versions.

  1. A medium version with 419,400 states and 2,281,620 non-zero entries (excluding diagonal elements) in the sparse matrix description . The structured description can be downloaded here, the sparse matrix representation here.

  2. A large version with 1.632.600 states and 9,732,330 non-zero entries (excluding diagonal elements) in the sparse matrix description . The structured description can be downloaded here.

Solution software

I have developed and implemented in the recent decades different solution techniques which should be made available for research. Parts of this software have been developed with colleagues. In particular with Peter Kemper (College of William and Marry) and Tugrul Dayar (Bilkent University). All programs are written in C and are compiled for 32bit Linux on x86 processors. If another architecture is required do not hesitate to contact me. It is also possible to obtain source codes for research purposes on request. As usual all programs are given without any warranty.

Nsolve

Nsolve is the basic program which contains a large number of numerical solvers (download). A short introduction for the program can be found in [4]. A paper that describes several of the implemented algorithms is [5].
Currently we are working on a data structure for the compact representation of the iteration vector. First results can be found in [10] and in [11].

References

[1] Peter Buchholz, Peter Kemper: Kronecker Based Matrix Representations for Large Markov Models. In: Validation of Stochastic Systems 2004, Springer LNCS 2925, pp. 256-295.

[2] Peter Buchholz. The Spare Matrix File Format. Working Paper 2010.

[3] Peter Buchholz. The Nsolve File Formats. Working Paper 2010.

[4] Peter Buchholz. The Nsolve Program. Working Paper 2010

[5] Peter Buchholz. Structured Analysis Approaches for Large Markov Chains. Applied Numerical Mathematics 31(4) 1999, 375-404.

[6] Peter Buchholz, Tugrul Dayar. Comparison of Multilevel Methods for Kronecker Based Markovian Representations. Computing 73, 2004, 349-371.

[7] Marco Ajmone Marsan, Susanna Donatelli, Fabio Neri: GSPN Models of Markovian Multiserver Multiqueue Systems. Perform. Eval. 11(4): 227-240 (1990).

[8] C.M. Woodside and Y. Li, Performance Petri Net Analysis of Communications Protocol Software by Delay Equivalent Aggregation, Proc. Fourth Int’l Workshop Petri Nets and Performance Models. pp. 64–73, IEEE CS Press, 1991

[9] Peter Buchholz. Hierarchical Structuring of Superposed GSPNs. IEEE Transactions on Software Engineering 25 (2) 1999, 166-181.

[10] Peter Buchholz, Tugrul Dayar, Jan Kriege, M. Can Orhan. Compact Representation of Solution Vectors in Kronecker-Based Markovian Analysis. QEST 2016, Springer LNCS 9826, 260-276.

[11] Peter Buchholz, Tugrul Dayar. .A HTD Data Structure for the Analysis of Structured Markov Chains. Internal Report 2017