Deliverable D5
Deliverable D5Introduction to Deliverable D5
The performance analysis of parallel and distributed systems leads in a natural way to multi-dimensional queueing models and multi-dimensional random walks.
In Deliverable D5, we have therefore investigated which classes of multi-dimensional queueing models and random walks are amenable to an exact analysis; in the course of this investigation, we have developed new methods of analysis of multi-dimensional random walks.
i/ We have analyzed a class of two dimensional random walks on the lattice in the first quadrant. For positive recurrent nearest-neighbouring semi-homogeneous random walks, the bivariate generating function of the stationary distribution is studied for the case where one-step transitions to the north, north-east and east at interior points are not possible. It is shown that this generating function can be represented by meromorphic functions. The construction of this representation is exposed for a variety of one-step transition vectors at the boundary of the state space. [J.W. Cohen (1992). On a class of two-dimensional nearest-neighbouring random walks, Stochastic Models, 8, 359-374.]
ii/ A special example of two dimensional random walk occurs for the asymmetric buffered 2x2 switch. The 2x2 switch is the basic unit in a switching system that is employed in parallel computer architectures to route messages between the network elements and to resolve conflicts. The joint queue length distribution at the output buffers of the 2x2 switch is determined using the recently developed compensation approach. A further methodological contribution is made by a detailed comparison of this approach with two established complex variable methods that have successfully tackled two-dimensional fork-join, shortest queue and coupled processor models: the uniformization technique and the boundary value method [O.J. Boxma and G.J. van Houtum (1993), The Compensation Approach Applied to a 2x2 Switch, accepted for publication in the Engineering and Information Sciences 8].
iii/ A more generally applicable method for the analysis of multidimensional random walks and queueing models is the recently developed power series algorithm. Research in the framework of QMIPS has shown that this method can be applied formally to each Markov chain with a single recurrent class. A proper proof of convergence of the method has so far only been provided in special cases. The power series algorithm has been successfully applied to analyze a multi-dimensional fork-join queue as arises in parallel processing. A paper on the method will appear in the proceedings of the Torino workshop on solution methods [G. Koole (1993), in preparation].
iv/ A spectral expansion method has been developed for the analysis of Markov processes whose state space is a two-dimensional semi-infinite lattice strip. The efficiency of this method has been evaluated and has in many cases been shown to be superior to the well-established matrix-geometric method.
The spectral expansion method has been used to study a model of a heterogeneous multiprocessor system with breakdowns and repairs. The problem of finding a repair strategy that maximizes the processing capacity of the system was examined. [ I. Mitrani and R. Chakka (1993), Heterogeneous Multiprocessor Systems with Breakdowns: Performance and Optimal Repair Strategies, to appear in Theoretical Computer Science].
The method has also recently been applied to the study of a multiprocessor queue with multiprogramming [M. Ettl and I. Mitrani, paper in preparation, to appear in the proceedings of the Torino workshop].
v/ We have studied a model of N parallel servers subject to breakdown and repair. Poisson arrivals are divided over the servers according to certain weights. In the case N=2, the joint equilibrium distribution of the numbers of jobs in both queues has been obtained by reduction to a Dirichlet boundary value problem. In the case of general N, the marginal queue size distribution is derived. The results are used to study the problem of choosing routing weights [Isi Mitrani and Paul E. Wright, Routing in the Presence of Breakdowns, to appear in the Proceedings of Performance '93].