Analysis of an algorithm of distributed generation of matrices for markovian models of a congestion control mechanism

Jarosław Bylina, Beata Bylina


We consider the parallel generation of matrices corresponding to models of congestion control mechanisms’ behavior. We develop a piece of software for a cluster architecture and analyze its performance times, amount of commu¬nication, each processor’s load. The resulting application is scalable and also produces a substantial speedup and efficiency.


Markovian models; queuing models; parallel algorithms; distributed algorithms

Full Text:



Benzi M., Tuma M.: A parallel solver for large-scale Markov chains. Applied Numerical Mathematics 41,2002, p. 135-153.

Bradley J. T., Dingle N. J., Knottenbelt W. J., Wilson H. J.: Hypergraph based parallel computation of passage time densities in large semi-Markov processes. Proceedings of the Fourth International Conference on the Numerical Solution of Markov Chains (NSNC '03), Urbana-Champaing, IL, September 2003, p. 99-120.

Buchholz P., Fischer M., Kemper P.: Distrbuted steady state analysis using Kronecker algebra. Proceedings of the Third International Conference on the Numerical Solution of Markov Chains (NSNC '99), Zaragoza, Spain, September 1999, p. 76-95.

Bylina J.: A distributed approach to solve large Markov chains. Proceedings from EuroNGI Workshop: New Trends in Modeling, Quantitive Methods and Measurements. Jacek Skalmierski Computer Studio, Gliwice 2004, p. 145-154.

Bylina J., Bylina B.: A Markovian model of the RED mechanism solved with a cluster of computers. Annales UMCS Informatica 5, 2006, p. 19-27.

Bylina J., Bylina B.: Development of a distributed algorithm of matrix generation for Markovian models of congestion control and its performance analysis on a computer cluster. Contemporary Aspects of Computer Networks, t. 2, WKŁ Warszawa 2008, p. 251-258.

Bylina J., Bylina B.: Distributed generation of Markov chains infinitesimal generators with the use of the low level network interface. Proceedings of 4th International Conference Aplimat 2005, part n, p. 257-262.

Bylina J., Bylina B., Czachórski T.: Rozproszona aplikacja do rozwiązywania markowskich modeli mechanizmów sieciowych. Nowe technologie sieci komputerowych, t. 1, WKŁ, Warszawa 2006, p. 331-338.

Dingle N. J., Harrison P. G., Knottenbelt W. J.: Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models. Journal of Parallel and Distributed Computing 64,2004, p. 908-920.

Knottenbelt W.: Distributed disk-based solution techniques for large Markov models. Proceedings of the Third International Conference on the Numerical Solution of Markov Chains (NSNC '99), Zaragoza, Spain, September 1999.

Ng Chee Hock: Queuing Modelling Fundamentals. Wiley, New York 1996.

National CLUSTER of LinuX Systems [@:] .