Reduction of closed queueing networks for efficient simulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reduction of closed queueing networks for efficient simulation

Full text

Pdf (682 KB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 19 , Issue 3 (June 2009) table of contents

Article No. 10

Year of Publication: 2009

ISSN:1049-3301

Authors

John F. Shortle	George Mason University, Fairfax, VA
Brian L. Mark	George Mason University, Fairfax, VA
Donald Gross	George Mason University, Fairfax, VA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 35, Downloads (12 Months): 85, Citation Count: 1

Additional Information:

appendices and supplements abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1540530.1540531 What is a DOI?

APPENDICES and SUPPLEMENTS

Shortle Appendix

Online appendix to reduction of closed queueing networks for efficient simulation. The appendix supports the information on article 10.

ABSTRACT

This article gives several methods for approximating a closed queueing network with a smaller one. The objective is to reduce the simulation time of the network. We consider Jackson-like networks with Markovian routing and with general service distributions. The basic idea is to first divide the network into two parts—the core nodes of interest and the remaining nodes. We suppose that only metrics at the core nodes are of interest. The remaining nodes are collapsed into a reduced set of nodes, in an effort to approximate the flows into and out of the set of core nodes. The core nodes and their interactions are preserved in the reduced network. We test the network reductions for accuracy and speed. By randomly generating sample networks, we test the reductions on a large variety of test networks, rather than on a few specific cases. The main conclusion is that the reductions work well when the squared coefficients of variation of the service distributions are not all small (that is, the network is not close to being deterministic) and for nodes where the utilization is not too high or too low.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Albert, R. and Barabási, A. L. 2002. Statistical mechanics of complex networks. Rev. Mod. Physics 74, 1, 47--97.
	2	Barabási, A. L. and Bonabeau, E. 2003. Scale-free networks. Sci. Amer. 288, 5, 60--69.
	3	Gabriel R. Bitran , Devanath Tirupati, Multiproduct queueing networks with deterministic routing: decomposition approach and the notion of interference, Management Science, v.34 n.1, p.75-100, Jan. 1988 [doi>10.1287/mnsc.34.1.75]
	4	Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor Shridharbhai Trivedi, Queueing Networks and Markov Chains, Wiley-Interscience, 2005
	5	Boucherie, R. J. and Stewart, M. 1998. Norton's equivalent for batch routing queueing networks with independently routing customers. Stochastic Models 14, 5, 1091--1112.
	6	Boucherie, R. J. and van Dijk, N. M. 1993. A generalization of Norton's theorem for queueing networks. Queueing Syst. 13, 251--289.
	7	Chandy, K. M. and Georganas, N. D. 1975. Decomposition and aggregation by class in closed queueing networks. IEEE Trans. Softw. Eng. 19, 36--42.
	8	Chandy, K. M., Herzog, U., and Woo, L. 1975. Parametric analysis of queueing networks. IBM J. Res. Devel. 19, 43--49.
	9	Cowie, J., Liu, H., Liu, J., Nicol, D., and Ogielski, A. 1999. Towards realistic million-node Internet simulations. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications.
	10	P. J. Courtois, Decomposability, instabilities, and saturation in multiprogramming systems, Communications of the ACM, v.18 n.7, p.371-377, July 1975 [doi>10.1145/360881.360887]
	11	Curtois, P. 1977. Decomposability Queueing and Computer Science Applications. ACM monograph series, Academic Press, New York.
	12	Dai, J. G. and Harrison, J. M. 1992. Reflected Brownian motion in an orthant: Numerical methods for steady-state analysis. Ann. Appl. Prob. 2, 65--86.
	13	Dai, J. G. and Harrison, J. M. 1993. The QNET method for two-moment analysis of closed manufacturing systems. Ann. Appl. Prob. 3, 968--1012.
	14	Dai, J. G., Nguyen, V., and Reiman, M. I. 1994. Sequential bottleneck decomposition: An approximation method for generalized Jackson networks. Oper. Res. 42, 119--136.
	15	Dai, J. G., Yeh, D. H., and Zhou, C. 1997. The QNET method for re-entrant queueing networks with priority disciplines. Oper. Res. 45, 4, 610--623.
	16	E. Gelenbe , G. Pujolle , J. C. C. Nelson, Introduction to queueing networks, John Wiley & Sons, Inc., New York, NY, 1987
	17	Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
	18	J. M. Harrison , V. Nguyen, The QNET method for two-moment analysis of open queueing networks, Queueing Systems: Theory and Applications, v.6 n.1, p.1-32, Apr. 1990 [doi>10.1007/BF02411463]
	19	Kim, S. 2004. The heavy-traffic bottleneck phenomenon under splitting and superposition. Europ. J. Oper. Res. 157, 736--745.
	20	Kuehn, P. J. 1979. Approximate analysis of general queueing networks by decomposition. IEEE Trans. Comm. 27, 113--126.
	21	Liu, B., Guo, Y., Kurose, J., Towsley, D., and Gong, W. 1999. Fluid simulation of large scale networks: Issues and tradeoffs. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications.
	22	Yong Liu , Francesco Lo Presti , Vishal Misra , Don Towsley , Yu Gu, Fluid models and solutions for large-scale IP networks, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
	23	David M. Nicol , Michael Liljenstam , Jason Liu, Advanced concepts in large-scale network simulation, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
	24	David M. Nicol , Jason Liu , Michael Liljenstam , Guanhua Yan, Simulation of large scale networks I: simulation of large-scale networks using SSF, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	25	Dhananjai Madhava Rao , Philip A. Wilsey, Simulation of Ultra-large Communication Networks, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.112, March 24-28, 1999
	26	Reiman, M. 1984. Open queueing networks in heavy traffic. Math. Oper. Res. 9, 3, 441--458.
	27	Reiman, M. I. 1990. Asymptotically exact decomposition approximations for open queueing networks. Oper. Res. Lett. 9, 363--370.
	28	Riley, G. and Ammar, M. H. 2002. Simulating large networks—how big is big enough&quest; In Proceedings of the 1st International Conference on Grand Challenges for Modeling and Simulation.
	29	George F. Riley, Simulation of large scale networks II: large-scale network simulations with GTNetS, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
	30	John F. Shortle , Brian L. Mark , Donald Gross, Reduction of closed queueing networks for efficient simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.19 n.3, p.1-22, June 2009 [doi>10.1145/1540530.1540531]
	31	Suresh, S. and Whitt, W. 1990. The heavy-traffic bottleneck phenomenon in open queueing networks. Oper. Res. Lett. 9, 355--362.
	32	Whitt, W. 1982. Approximating a point process by a renewal process, I: Two basic methods. Oper. Res. 30, 125--147.
	33	Whitt, W. 1983a. Performance of the QNA. Bell Syst. Tech. J. 62, 9, 2816--2843.
	34	Whitt, W. 1983b. The queueing network analyzer. Bell Syst. Tech. J. 62, 9, 2779--2815.
	35	Whitt, W. 1984. Open and closed models for networks of queues. AT&T Bell Lab. Tech. J. 63, 9, 1911--1979.
	36	Ward Whitt, Variability functions for parametric-decomposition approximations of queueing networks, Management Science, v.41 n.10, p.1704-1715, Oct. 1995 [doi>10.1287/mnsc.41.10.1704]
	37	Yousefi, A., Donohue, G. L., and Qureshi, K. M. 2003. Investigation of en-route metrics for model validation and airspace design using the Total Airport and Airspace Modeler (TAAM). In Proceedings of the 5th EUROCONTROL/FAA ATM R&D Conference. Budapest, Hungary.