Computations with Markov Chains

Given a high level specification of a Markov chain, it is desirable to be able to determine if the state space of the Markov chain is finite. If the state space is finite, the entire transition matrix can be generated. If the state space of the Markov chain is infinite, although it is impossible to generate the entire transition matrix, it still may be possible to solve the Markov chain. One interesting and useful class of denumerable state space Markov chains that can be solved consists of those that have a block GI/M/1 or a block M/G/1 form. Block GI/M/1 and block M/G/1 matrices, though infinite, have a repeating structure that allows analytical solution. If it can be detected from the specification that the Markov chain is block GI/M/1 or block M/G/1, then our system can automatically apply matrix analytical methods to obtain a solution. In this paper, a high level specification language for Markov chains is proposed such that the existence of block GI/M/1 or block M/G/1 form may be verified directly from the specification. An algorithm is given to determine whether a Markov chain with a 2 dimensional state space specified in this language is infinite and, if so, whether it can be represented in block GI/M/1 or block M/G/1 form. It is shown that in general, it is undecidable whether a matrix specified in this language with a state space vector of dimension greater than 2 can be represented as a block GI/M/1 or block M/G/1 matrix. Finally a second, less powerful specification language, is provided for which the question is decidable for a specification with a state space vector of any finite dimension.

We observe that the cyclic reduction algorithm leaves unchanged the structure of a block Toeplitz matrix in block Hessenberg form. Based on this fact, we devise a fast algorithm for computing the probability invariant vector of stochastic matrices of a wide class of Toeplitz-like matrices arising in queueing problems. We prove that for any block Toeplitz matrix H in block Hessenberg form it is possible to carry out the cyclic reduction algorithm with O(k3n + k2n log n) arithmetic operations, where k is the size of the blocks and n is the number of blocks in each row and column of H. The probability invariant vector is computed within the same cost. This substantially improves the O(k3n2) arithmetic cost of the known methods based on Gaussian elimination. The algorithm, based on the FFT, is numerically weakly stable. In the case of semi-infinite matrices the cyclic reduction algorithm is rephrased in functional form by means of the concept of generating function and a convergence result is proved.

We consider a positive recurrent M/M/1 queue in a slowly varying Markovian environment, such that in some environments, the arrival rate may be higher than the service rate. The system therefore may oscillate between stable and unstable modes of behaviour. We investigate the limiting distribution as the expected sojourn times in the various environments increase to infinity. We show that the limiting behaviour of the stationary distribution is significantly different when there are unstable environments.

In a general projection technique the original matrix problem of size N is approximated by one of dimension m, typically much smaller than N. A particularly successful class of techniques based on this principle is that of Krylov subspace methods which utilise subspaces of the form span{v, Av,…., Am-1v}. This general principle can be used to solve linear systems and eigenvalue problems which arise when computing stationary probability distributions of Markov chains. It can also be used to approximate the product of the exponential of a matrix by a vector as occurs when following the solutions of transient models. In this paper we give an overview of these ideas and discuss preconditioning techniques which constitute an essential ingredient in the success of Krylov subspace methods.

A parallel block projection method is used to approximate the stationary vector of a finite Markov chain. Block projection methods are very attractive for solving large chains thanks to their potential for parallel computation and robustness. We show that the block Cimmino method is particularly well-suited if the chain is nearly uncoupled, a condition which is often met in the applications. This is due to the favorable spectral distribution of the iteration matrix, in contrast with more traditional iterative solvers which are known to exhibit poor convergence rates when applied to nearly uncoupled problems. We consider conjugate gradient acceleration, and we experiment with different block partitionings and row reorderings of the rate matrix. The results of numerical experiments on a simple reliability model, carried out on the CRAY T3D massively parallel computer, are discussed. The test results point to the fact that this method is well suited for the parallel solution of nearly uncoupled Markov chains.

We consider finding the stationary probability distribution vectors of Markovian queueing models having batch arrivals by using the preconditioned conjugate gradient (PCG) method. The preconditioners are constructed by exploiting the near-Toeplitz structure of the generator matrix of the model and are products of circulant matrices and band-Toeplitz matrices. We prove that if the number of servers s is fixed independent of the queue size n, then for sufficiently large n, the preconditioners are invertible and the preconditioned systems have singular values clustered around 1. Hence if the systems are solved by the preconditioned conjugate gradient method, we expect superlinear convergence. Our numerical results show that the PCG method with our preconditioner converges in finite number of steps independent of n and s whereas the numbers required by the Jacobi method or the PCG method without any preconditioner increase like O(n).

In this note we exploit the knowledge embodied in infinitesimal generators of Markov processes to compute efficiently and economically the transient solution of continuous time Markov processes. We consider the Krylov subspace approximation method which has been analysed by Gallopoulos and Saad for solving partial differential equations and linear ordinary differential equations [7, 17]. We place special emphasis on error bounds and stepsize control. We illustrate the usefulness of the approach by providing some application examples.

Most common performance and reliability models assume that rates associated with events such as arrivals, service completions, failures, repairs, etc. are all constant in time. Many practical systems, however, require time- (age-) dependent rates. For example, the use of Weibull failure rates is quite common in many reliability models. Likewise, most actual local area network (LAN) systems experience surges in the number of users that vary in magnitude over time. These surges may often be approximated by a periodic process. Therefore, nonhomogeneous continuous time Markov chains (CTMCs) may be well suited to model such systems. The transient analysis of time-varying linear systems is highly advanced in the field of systems and control theory. We present a review of some useful results, and then apply them to the analysis of nonhomogeneous CTMCs (especially periodic ones). One of the results of this analysis is, that for a certain class of useful nonhomogeneous CTMCs, a very simple method exists for transforming such a CTMC (and not just a periodic one) to an equivalent homogeneous CTMC that is then amenable to such homogeneous methods as Jensen’s method (also known as uniformization or randomization).

In this paper, we consider various redundant systems attended by a single repairperson that services components in a First Come First Served (FCFS) order. Failure times are taken to be exponentially distributed random variables, while repair times are deterministic. As a result, the underlying stochastic process is not Markovian or semi-Markovian. However, the underlying stochastic process is Markov regenerative and as such we are able to write and solve equations for the process. We compute various dependability measures, such as reliability function, Mean Time To Failure (MTTF), time-dependent and steady-state availability.

In this paper we discuss algorithms for computing the fundamental matrix, the group generalized inverse, and the mean and variance of first passage times for discrete time regular Markov chains. The algorithms are based on the GTH algorithm for computing a stationary vector. We show that although all of these quantities can easily be computed from any one of them, the standard algebraic relations do not produce algorithms that preserve low componentwise relative error in each of them.

Immediate events are events which happen without delay. There are several contexts in which immediate events occur. In particular, they are important for formulating Markovian systems efficiently, they are an integral part of generalised stochastic Petri nets, and they are useful for analysing processes which have different time scales. These applications are reviewed, and a unified theory for finding equilibrium probabilities for such processes is developed. This theory is based on the GTH algorithm, which is augmented by a special algebra.

We introduce a stochastic process algebra, PEPA, as a high-level modelling paradigm for continuous time Markov chains (CTMC). Process algebras are mathematical theories which model concurrent systems by their algebra and provide apparatus for reasoning about the structure and behaviour of the model. Recent extensions of these algebras, associating random variables with actions, make the models also amenable to Markovian analysis. A compositional structure is inherent in the PEPA language. As well as the clear advantages that this offers for model construction, we demonstrate how this compositionality may be exploited to reduce the state space of the CTMC. This leads to an exact aggregation based on lumpability.

Stochastic Automata Networks (SANs) are an efficient means to describe and analyze parallel systems under Markovian assumptions. The main advantage of SANs is the possibility to describe and analyze a complex parallel system in a compositional way such that the transition matrix of the Markov chain underlying the complete SAN can be described in a compositional way using only small matrices specifying single automata and combine these matrices by means of tensor operations. This approach allows, up to a certain extent, the handling of the state space explosion resulting from complex Markov models. In this paper equivalence relations for stochastic automata are introduced such that an automaton in a network can be substituted by an equivalent and usually smaller automaton without affecting the results of an analysis. We consider equivalence according to stationary and transient analysis of SANs.

We show how some graph theoretical arguments may be used to reduce the complexity of the computation of the steady-state distribution of Markov chain. We consider the directed graph associated to a Markov chain derived from a Stochastic Automata Network (SAN). The structural properties of the automata are used to establish new various results. First, we establish the complexity of the resolution for Stochastic Automata Networks with a sparse matrix representation of the automata. This results are used to compare simple SAN (i.e. without functions) with methods which generates a sparse representation of Markov chains (i.e. Markovian Petri Nets for instance) on some examples.Then, we show how to apply state reduction techniques on a chain associated to a SAN. We present an algorithm to solve the steady-state equations and we prove its complexity. Finally, we extend our algorithm to allow the semi-parametric analysis of Stochastic Automata Networks.

The mandate from the conference chairman was to provide an introductory account of the statistical issues that arise when designing Markov chain sampling experiments and analyzing their output. However, the time limitation makes my objective in this paper considerably more modest. It is merely to provide an account of how the interaction among four design parameters affects statistiical properties of estimates of (1)$$\mu = \mu (g) = {{\smallint }_{\% }}g(x)dF(x)$$ where F denotes an m-dimensional d.f. on $$\% \subseteq {{\mathbb{R}}^{m}}$$ and g satisfies $${{\smallint }_{\% }}{{g}^{4}}(x)dF(x) < \infty$$ A considerably more expanded account appears in Fishman (1995).

We recently developed a new algorithm for calculating the blocking probability of each class in resource-sharing models with upper limit and guaranteed minimum sharing policies as well as the standard complete-sharing policy. These models may have multiple resources and multiple classes, with each class requiring multiple units from each resource. These models may also have state-dependent arrival and service rates. Our new algorithm is based on calculating normalization constants appearing in the product-form steady-state distributions by numerically inverting their generating functions. In the present paper we provide the basis for extending the algorithm to resource-sharing models with batch arrival processes. The batch sizes are mutually independent random variables with distributions depending on the class. We show that the steady-state distribution of the resource-sharing model has a product form for both complete-batch blocking and partial-batch blocking, and we derive the generating functions of the normalization constants for partial-batch blocking. We primarily focus on the Bernoulli-Poisson-Pascal (BPP) special case in which the batches have linear state-dependent arrival rates, which includes finite-source inputs and Poisson inputs for the batches as special cases. With batches, we require exponential service times, but when there are state-dependent arrivals of single customers (no batches), the service-time distributions can be general. By considering state-dependent arrivals for the batches, multiple resources and noncomplete-sharing policies, our treatment extends recent results for resource-sharing models with batch arrivals by van Doom and Panken, by Kaufman and Rege and by Morrison. Even for the batch models previously considered, our algorithm is faster than recursive algorithms when the model is large. We also provide a new derivation of the product-form steady-state distributions that helps explain why service-time insensitivity does not hold when there are batches.

We consider a Markov decision process (MDP) with finite state space S and finite action set A. The state space is partitioned into K sets S₁, S₂, …, S_K. A stationary randomized policy is described by the parameters {α _ia i ∈, S, a ∈ A}, where α_ia = the parobability that action a is taken when the system is in state i. A policy is called implementable if α _ia = α _ja for all α ∈ A whenever states i and j belong to a common subset S _τ for some r = 1, 2,…, K In this paper we discuss the importance of implementable policies and present an algorithm to find implementable policies that (locally) minimize the expected total discounted cost over infinite horizon.

Two different techniques for bounding the steady-state solution of large Markov chains are presented. The first one is a verification technique based on monotone iterative methods. The second one is a decomposition technique based on the concepts of eigen-vector polyhedron. The computation of the availability of repairable fault-tolerant systems is used to illustrate the performances and the numerical aspects of both methods.

A new version of the Power-Series Algorithm is developed to compute the steady-state distribution of a rich class of Markovian queueing networks. The arrival process is a Multi-queue Markovian Arrival Process, which is a multi-queue generalization of the BMAP. It includes Poisson, fork and round-robin arrivals. At each queue the service process is a Markovian Service Process, which includes sequences of phase-type distributions, set-up times and multi-server queues. The routing is Markovian. The resulting queueing network model is extremely general, which makes the Power-Series Algorithm a useful tool to study load-balancing, capacity-assignment and sequencing problems.

We revisit and extend the original definition of discrete-time stochastic Petri nets, by allowing the firing times to have a “defective discrete phase distribution”. We show that this formalism still corresponds to an underlying discrete-time Markov chain. The structure of the state for this process describes both the marking of the Petri net and the phase of the firing time for of each transition, resulting in a large state space. We then modify the well-known power method to perform a transient analysis even when the state space is infinite, subject to the condition that only a finite number of states can be reached in a finite amount of time. Since the memory requirements might still be excessive, we suggest a bounding technique based on truncation.

We extend the class of Markov Regenerative Stochastic Petri Nets* (MRSPN*s), removing the restriction that at most one generally distributed timed transition can be enabled in any marking. This new class of Petri Nets, which we call Concurrent Generalized Petri Nets (CGPNs) allows simultaneous enabling of immediate, exponentially distributed and generally distributed time transitions, under the hypothesis that the latter are all enabled at the same instant. The stochastic process underlying a CGPN is shown to be still an MRGP. We evaluate the kernel distribution of the underlying MRGP and define the steps required to generate it automatically.

We introduce a refined algorithm for determining the transition probability matrix of the embedded Markov chain underlying a Markov Regenerative Stochastic Petri Net (MRSPN), which continues previous work on improving the efficiency of the numerical solution method for MRSPNs. By observing that the digraph corresponding to the Markov chains subordinated to timed transitions with non-exponentially distributed firing delays of a MRSPN constitute a forest, we show how isomorphisms between its connected components can be exploited in order to reduce the computation time of their transient analysis. Furthermore, special structures for subordinated Markov chains are introduced for which the computational effort of the transient analysis can also be reduced. The computational benefit of the proposed approach is illustrated by four MRSPNs taken from the literature.

Iterative aggregation/disaggregation procedures are a convenient numerical solution method for computing the stationary distribution vector of an ergodic homogeneous Markov chain with a finite state space. We show the equivalence of this method and a two-level multigrid method. Based on error results of the A/D-method, we provide an error analysis of an efficient multigrid variant of the multiplicative Schwars-iteration method. Furthermore, we apply these results to a multigrid version of the replacement process approach developed by Sumita and Rieders.

Recently the Multi-Level algorithm was introduced as a general purpose solver for the solution of steady state Markov chains. In this paper we consider the performance of the Multi-Level algorithm for solving Nearly Completely Decomposable (NCD) Markov chains, for which special-purpose iterative aggregation/disaggregation algorithms such as the Koury-McAllister-Stewart (KMS) method have been developed that can exploit the decomposability of the the Markov chain. We present experimental results indicating that the general-purpose Multi-Level algorithm is competitive, and can be significantly faster than the special-purpose KMS algorithm when Gauss-Seidel and Gaussian Elimination are used for solving the individual blocks.

A computationally efficient algorithm for characterizing the superposition process of N heterogeneous and independent Interrupted Bernoulli Processes is introduced. The algorithm is then used to analyze a statistical multiplexer with finite buffer.Finally, numerical examples highlighting the algorithm accuracy are given.

In this paper we propose and implement a generalized Folding-algorithm for the transient analysis of finite QBD processes. It is a numerical method for the direct computation of xP= a where P is the QBD generator matrix in block tri-diagonal form. Define the QBD state space in two dimensions with N phases and K levels, so that $$P \in {{R}^{{NK \times NK}}}andx,a \in {{R}^{{J \times NK}}},\forall J$$. The time complexity of the algorithm for solving x P = a is the greater of O(N3 log₂K) and O(N2KJ). The algorithm is found to be highly stable with superior error performance. In numerical studies we analyze the transient performance of MMPP/M/1 queueing system with finite buffer capacity. The MMPP arrival process is constructed to reflect the diversity of the second-order input statistics. We examine the effect of the second-order input statistics on transient queueing performance.

Although the use of embedded Markov chains has been known for some time, the application of this technique has been very ad hoc and has not been established as a standard approach for a wide class of models. Recently however, there has been progress in the direction of identifying an interesting class of models which are not Markovian but which can yield to a well defined solution method based on the analysis of an embedded Markov chain. Example applications that yield to this approach include polling models with deterministic timeout periods and models with deterministic service time queues. In this paper we derive efficient methods for computing both the transition probabilities for the embedded chain and performance measures expressible as Markov reward functions. Calculating the transition probabilities for the embedded chain requires transient analysis, and our computational procedures are based on uniformization. Examples are given to demonstrate the effectiveness of the methods and the extended class of models that are solvable with these techniques.

In packet-switched communication networks information generation is bursty, resulting in traffic at multiplexers, switches and transmission channels which fluctuates randomly, often with a high correlation in time. Accurate models and efficient analytical techniques are needed to study these networks. We consider typical statistical multiplexing systems where traffic from many bursty sources is buffered if necessary and transmitted over channels (servers). We focus on models in which the traffic from each source is a Markov-modulated Poisson process and information units (packets) contain exponentially distributed number of bits. The capacity of the channels (servers) may be constant or Markov-modulated to reflect capacity sharing among systems. Utilizing the structural properties of the model we derive theory and algorithms for the exact calculation of the spectral expansion of the buffer content distribution and from which performance measures are obtained. The efficiency of the method is derived from an algebraic theory, which gives the (exact) decomposition of the eigenvalue problem into small coupled problems, and expresses the eigenvectors in Kronecker-product form. When the sources/servers are identical or can be grouped into classes, the eigenvalues are given as roots of polynomials of small degree and the eigenvectors are given in closed form. We give a characterization of the dominant eigenvalue in the general setting of heterogeneous sources and servers, which is insightful and considerably reduces the computational burden. The results are useful in deriving bounds and approximations of tail probabilities. The approaches and techniques developed here extend naturally to more general Markovian sources and servers in the family of MAP processes. It is shown that the rate matrix in the matrix-geometric theory can be efficiently computed from our spectral representation regardless of traffic conditions.

Computation of transient state occupancy probabilities of continuous-time Markov chains is important for evaluating many performance, dependability, and performability models. A number of numerical methods have been developed to perform this computation, including ordinary differential equation solution methods and uniformization. The performance of these methods degrades when the highest departure rate in the chain increases with respect to a fixed time point. A new variant of uniformization, called adaptive uniformization (AU), has been proposed that can potentially avoid such degradation, when several state transitions must occur before a state with a high departure rate is reached. However, in general, AU has a higher time complexity than standard uniformization, and it is not clear, without an implementation, when All will be advantageous. This paper presents the results of three different AU implementations, differing in the method by which the “jump probabilities” are calculated. To evaluate the methods, relative to standard uniformization, a C++ class was developed to compute a bound on the round-off error incurred by each implementation, as well as count the number of arithmetic instructions that must be performed, categorized both by operation type and phase of the algorithm they belong to. An extended machine-repairman reliability model is solved to illustrate use of the class and compare the adaptive uniformization implementations with standard uniformization. Results show that for certain models and mission times, adaptive uniformization can realize significant efficiency gains, relative to standard uniformization, while maintaining the stability of standard uniformization.

Queues of M/G/1 type give rise to infinite embedded Markov chains whose transition matrices are upper block Hessenberg. The traditional algorithms for solving these queues have involved the computation of an intermediate matrix G. Recently a recursive descent method for solving block Hessenberg systems has been proposed. In this paper we explore the interrelations of the two methods.

The world of iterative numerical analysis techniques for continuous time Markov chains (CTMCs) as described by generalized stochastic Petri nets (GSPNs) is split apart: On the one side we find the classical technique performing three main steps 1. state space exploration, 2. elimination of vanishing markings and generation of the stochastic generator matrix Q, and 3. application of an iteration scheme, e.g. Jacobi overrelaxation (JOR). This technique offers a fast iteration if sufficient primary memory is available to store all non zero matrix entries. Due to the well known state space explosion this technique often collapses already in step 1 or 2 without(!) any useful results. On the other side sophisticated iteration techniques based on tensor algebra, cf. [1], allow the application of an iterative scheme without explicitly generating the stochastic generator of the CTMC. S. Donatelli describes in [2] how this technique is employed for CTMCs which are given by superposed generalized stochastic Petri nets (SGSPNs). A SGSPN consists of several GSPNs which are synchronized by a set of synchronizing transitions. The tensor based technique represents Q by a tensor product Q = ⊗ _i Qi of small matrices Qi. This representation of Q drastically reduces memory requirements and slightly increases the computational effort for a single iteration step compared to the conventional technique, provided Q can be stored in primary memory. It especially avoids representing zero entries in Q. Nevertheless for a matrix-vector multiplication zero vector entries cause a lot of redundant multiplications as well. Considering zero vector entries the tensor based approach reveals two drawbacks: 1It regards the cartesian product of the tangible reachability sets (TRSi) of the isolated GSPNs as the relevant state space. Due to synchronization of transitions this set is usually a superset of the tangible reachability set (TRS) which causes a (model-dependent) overhead, i.e. $$\[\left| {TRS} \right| \leqslant I{I_i}\left| {TR{S^i}} \right|\]$$ This overhead can be extremely large. For all unreachable states, vector entries will remain zero during the whole iteration process, hence all multiplications involving these states are a waste of time and their corresponding matrix columns are not relevant.2The tensor based technique generates the TRS implicitly by iteration, since the matrix-vector multiplication performed with Q is similar to Breadth-FirstSearch. This requires a rather unfortunate initial distribution, which assigns all probability mass to the initial marking M_o of the SGSPN, i.e. P[M₀] = 1.0. Consequently for large state spaces a lot of iteration steps are necessary to distribute probability mass on reachable tangible states. Hence a lot of vector entries remain zero for a certain number of iteration steps and their corresponding matrix columns are irrelevant in these iteration steps.

For details of the adaptive smoothing and the multi-level algorithms, as well as a complete list references, we refer the reader to [1].

This paper discusses various approaches for decomposing large Markov chains in a way that facilitates the use of aggregation type algorithms and increases the efficiency of such methods. For a Markov chain defined on state space N = {1,…, N} governed by transition probability matrix (t.p.m.)P, we are interesetd in finding the stationary distribution π, satisfying πT = πT, with π > 0, πTe =1, where e is the vector containing all ones. Agggregation disaggregation (A/D) algorithms are based on a decomposition of the state space N into smaller groups of states $$\mathcal{N} = \cup _{{m = 1}}^{M}L\left( m \right);$$L(m) ∩ L(n) = Ø for m ≠ n. For an approximation π₁ of π, one defines two mappings Y: RN → RM (typically based on π₁) and E: RM→RN, and an aggregate matrix A = Y P E. In the aggregation step one finds a probability vector γ that solves the aggregated system γT = γT A. In the disaggregation step, one assigns a conditional probability vector y_L(m) to the states in lump L(m). This may be achieved by constructing a new Markov chain on L(m) representing flow within L(m) as well as flow to and from the other sets. A new approximation of it is then obtained by setting π_2:L(m) = γ_my_L(m)A/D algorithms proceed iteratively, until convergence is reached. Examples of A/D methods for Markov chains include Takahashi’s algorithm [7] and the replacement process algorithm of Sumita and Rieders [6].

The aggregation/disaggregation method (the A/D method) is an iterative method for calculating the stationary probabilities of large scale Markov chains numerically. It consists of two phases; the aggregation phase and the disaggregation phase. In the disaggregation phase, a number of linear equations have to be solved. Since these calculations can be done in parallel, the A/D method is a suitable numerical method for parallel computers.

We are concerned with computing the steady-state distribution it of an finite irreducible Markov chain with transition matrix P. We will use the GTH [1]algorithm which has excellent numerical properties which have been demonstrated empirically[2] and mathematically [3] We have at our disposal workstations and a massively parallel computer; we want to see how execution times on the latter compare to execution times on the former. Embedded in this endeavor is an exploration of how to harness the massively parallel computer to work on the GTH algorithm. Our main conclusions are: Our massively parallel computer can solve a problem with one thousand states one hundred times as fast as a serial computer. Extrapolation of our experience using one-eighth of the available memory indicates that for a problem with eleven thousand states,the serial machine would require 104 as much time as the parallel machineHaving enough memory to store the transition matrix is the limiting factor for our parallel computer.When the transition matrix has the block tridiagonal form, our parallel computer can store many thousands of states (depending on the block size; 16 × 106 states can be stored when the blocks are 2 × 2) and compute the steady-state distribution in a few hours. The 16 × 106 state example can be done in 24 hours.

Finding the stationary distribution of a finite-state, discrete time, irreducible Markov chain is equivalent to seeking the left eigenvector corresponding to the eigenvalue 1 of a transition matrix P of order n. Grassmann, Taksar and Heyman [1] introduced a direct algorithm, the GTH algorithm, to find the steady-state vector π. Later O’Cinneide [2] showed that the computed vector π has low componentwise relative error. In order to reach high performance over a large class of computers, O’Leary and Wu [3] developed a block form algorithm, the block-GTH algorithm, and successfully demonstrated the efficiency of the algorithm on vector pipeline machines and on workstations with cache memory.

The method of decomposition of queues has been widely used in solution of large and complex queueing networks for which exact solutions do not exist. We apply the basic paradigm of decomposition in computing approximations to the sojourn-time distribution in open queueing networks in which the service times and arrival processes are non-Markovian. For doing so we have made use of existing results on sojourn time distribution at a single queue. Using these, a queueing network is translated into a semi-Markov chain, whose absorption time distribution approximates the sojourn time distribution of the queueing network. However, the semi-Markov model does not represent the state of the queueing network (i.e., number of jobs at each queue). The state-space size of the semi-Markov models is thus linear in the number of queues in the network. This is achieved by having one state in the semi-Markov model corresponding to each queue in the queueing network, and one absorbing state to denote exit out of the network. The states are then connected together according to the topology of the network. The holding time distribution of a state is the sojourn time distribution at the corresponding queue. This sojourn time distribution must be computed by considering each queue in isolation. We approximate the arrival process to each queue to a phase-type arrival process, and then compute the sojourn time distribution assuming it is a PH/G/1 queue. Once we have the holding time distributions and the routing probability matrix, the absorption time distribution of the semi-Markov chain can be computed. The absorption time distribution approximates the sojourn time distribution of the queueing network.