Solving layered queueing networks of large client-server systems with symmetric replication

ABSTRACT

Large distributed client-server systems often contain subsystems which are either identical to each other, or very nearly so, and this simplifies the system description for planning purposes. These replicated components and subsystems all have the same workload and performance parameters. It is known how to exploit this symmetry to simplify the solution of some kinds of performance models, using state aggregation in Markov Chains. This work considers the same problem for layered queueing models, using mean value analysis. The mean values are found for each group of replicas just once, and then are inserted appropriately into the solution of the system as a whole. An algorithm has been implemented in the Layered Queueing Network Solver (LQNS), including approximations to deal with interactions among the replicas, and is evaluated for accuracy and for efficiency. The resulting solver is insensitive (in time of solution) to the number of replicas in a group, and can efficiently calculate waiting times and throughputs for systems with tens of thousands of nodes and processes.

REFERENCES

• 1: Luiz André Barroso , Jeffrey Dean , Urs Hölzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, v.23 n.2, p.22-28, March 2003 [doi>10.1109/MM.2003.1196112]
• 2: Lorenzo Capra , Giuliana Franceschinis , Claude Dutheillet , Jean Michel Ilie, Towards Performance Analysis with Partially Symmetrical SWN, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.148, March 24-28, 1999
• 3: K. Mani Chandy , Doug Neuse, Linearizer: a heuristic algorithm for queueing network models of computing systems, Communications of the ACM, v.25 n.2, p.126-134, Feb 1982 [doi>10.1145/358396.358403]
• 4: O. Das and M. Woodside. Dependability modeling of self-healing client-server applications. In R. D. Lemos, C. Gacek, and A. Romanovsky, editors, Architecting Dependable Systems II, volume 3069 of Lecture Notes in Computer Science, pages 266--285. Springer-Verlag, Dec. 2004.
• 5: G. de Vahl Davis. Numerical Methods in Engineering and Science. Allen Unwin Ltd., London, 1986.
• 6: G. Franks, S. Majumdar, J. Neilson, D. Petriu, J. Rolia, and M. Woodside. Performance analysis of distributed server systems. In The 6th Int. Conf. on Software Quality (6ICSQ), pages 15--26, Ottawa, Canada, Oct. 1996.
• 7: Roy Gregory Franks , C. Murray Woodside, Performance analysis of distributed server systems, 2000
• 8: P. Kähkipuro. UML-Based performance modeling framework for component-based systems. In R. Dumke, C. Rautenstrauch, A. Schmietendorf, and A. Scholz, editors, Performance Engineering. Spinger, Berlin, 2001.
• 9: Houda Lamehamedi , Zujun Shentu , Boleslaw Szymanski , Ewa Deelman, Simulation of Dynamic Data Replication Strategies in Data Grids, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.100.2, April 22-26, 2003
• 10: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 11: An Overview of Data Replication on the Internet, Proceedings of the 2002 International Symposium on Parallel Architectures, Algorithms and Networks, p.31, May 22-24, 2002
• 12: Daniel A. Menascé , Virgílio A. F. Almeida , Larry W. Dowdy, Capacity planning and performance modeling: from mainframes to client-server systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 13: D. A. Menascé, Two-Level Iterative Queuing Modeling of Software Contention, Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'02), p.267, October 11-16, 2002
• 14: A. M. Pan. Solving stochastic rendezvous networks of large client-server systems with symmetric replication. Master's thesis, Department of Systems and Computer Engineering, Carleton University, Sept. 1996.
• 15: Sridhar Ramesh , Harry G. Perros, A Multilayer Client-Server Queueing Network Model with Synchronous and Asynchronous Messages, IEEE Transactions on Software Engineering, v.26 n.11, p.1086-1100, November 2000 [doi>10.1109/32.881719 ]
• 16: J. A. Rolia , K. C. Sevcik, The Method of Layers, IEEE Transactions on Software Engineering, v.21 n.8, p.689-700, August 1995 [doi>10.1109/32.403785 ]
• 17: W. H. Sanders and J. F. Meyer. Reduced base model construction methods for stochastic activity networks. IEEE J. on Selected Areas of Communications, 9(1):25--36, Jan. 1991.
• 18: F. Sheihk, J. Rolia, P. Garg, and A. S. S. Frolund. Layered modelling of large scale distributed applications. In Proc. 1st World Congress on Systems Simulation, Quality of Service Modelling, pages 247--254, Singapore, Sept. 1--3 1997.
• 19: Connie U. Smith, Performance Engineering of Software Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 20: B. Spitznagel and D. Garlan. Architecture-based performance analysis. In Proc. 1998 Conf. on Software Engineering and Knowledge Engineering (SEKE'98), June 1998.
• 21: C. M. Woodside, Performance potential of communications interface processors, Proceedings of the eighth symposium on Data communications, p.245-253, October 03-06, 1983, North Falmouth, Massachusetts, United States
• 22: C. Murray Woodside , John E. Neilson , Dorina C. Petriu , Shikharesh Majumdar, The Stochastic Rendezvous Network Model for Performance of Synchronous Client-Server-like Distributed Software, IEEE Transactions on Computers, v.44 n.1, p.20-34, January 1995 [doi>10.1109/12.368012 ]