Approximate Methods for Analyzing Queueing Network Models of Computing Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate Methods for Analyzing Queueing Network Models of Computing Systems

Full text

Pdf (3.10 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 10 , Issue 3 (September 1978) table of contents

Pages: 281 - 317

Year of Publication: 1978

ISSN:0360-0300

Authors

K. Mani Chandy	Computer Sciences Department, University of Texas at Austin, Austin, Texas
Charles H. Sauer	Computer Sciences Department, University of Texas at Austin, Austin, Texas

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 75, Citation Count: 44

Additional Information:

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/356733.356737 What is a DOI?

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.

	BARD77	BARD, Y. "The modeling of some scheduling strategies for an interactive computer system," m Computer performance, K. M Chandy and M. Reiser (Eds.), Elsevier North-Holland, Inc., New York, 1977, pp. 113-138.
	BARD78	Y. Bard, The VM/370 Performance Predictor, ACM Computing Surveys (CSUR), v.10 n.3, p.333-342, Sept. 1978 [doi>10.1145/356733.356739]
	BASK75	Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
	BROW75	BROWNE, J. C.; CHANDY, K. M.; BROWN, R. M.; KELLER, T. W., TOWSLEY, D. F., AND DmSL~.Y, C W. "Hierarchical techtuques for development of realistic models of complex computer systems," Proc. IEEE 63, (June 1975), 966-975
	BROW77	R. M. Brown , J. C. Browne , K. M. Chandy, Memory management and response time, Communications of the ACM, v.20 n.3, p.153-165, March 1977 [doi>10.1145/359436.359443]
	BUX77	Bux, W.; AND HZRZO~~, U. "The phase concept: approximation of measured data and performance analysis," in Computer performance, K.M. Chandy and M. Reiser (Eds.), Elsevier North-Holland, Inc., New York, 1977, pp. 23-38.
	CHAN72	CHANDY, K. M. "The analysis and solutions for general queueing networks," m Proc. 6th Annual Princeton Conf Informatron Science and Systems, 1972, pp. 224-228.
	CHAN75a	CHANDY, K. M.; HERZOG, U.; AND WOO, L S. "Parametric analysis of queuemg networks," IBM J. Res Dev 19, (Jan. 1975), 36-42.
	CHAN75b	CHANDY, K. M, HERZOG, U, AND Woo, L. S. "Approximate analysis of general queueing networks," IBM J. Res Dev. 19, (Jan. 1975), 43-49.
	CHAN77	K. Mani Chandy , John H. Howard, Jr. , Donald F. Towsley, Product Form and Local Balance in Queueing Networks, Journal of the ACM (JACM), v.24 n.2, p.250-263, April 1977 [doi>10.1145/322003.322009]
	CHIU78	CHIU, W. W.; AND CHOW, W. M. A hybrid hwrarchical model of a multiple vwtual storage (MVS) operatmg system, RC- 6947, IBM Research, Yorktown Heights, N.Y., Jan. 1978.
	COUR75	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]
	COUR77	COURTOIS, P J. Decomposabdzty queueing and computer system apphcatlons, Academic Press, Inc, New York, 1977.
	COX55	Cox, D. R. "A use of complex probabflitms m the theory of stochastm processes," Proc. Cambridge Phdos. Soc. 51, (1955), 313-319
	COX65	Cox, D R., AND MILLER, H. D. The theory of stochastic processes, John Wiley and Sons, Inc., New York, 1965.
	DENN76	Peter J. Denning , Kevin C. Kahn, An L=S criterion for optimal multiprogramming, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.219-229, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806198]
	DENN78	Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978 [doi>10.1145/356733.356735]
	DISN74	DISNEY, R. L" AND CHERRY, W. P "Some topics in queuelng network theory," in Mathematwal methods m queueing theory, A. B. Clarke (Ed.), Springer-Verlag New York, Inc., New York, 1974.
	DRAK67	Alvin W. Drake, Fundamentals of Applied Probability Theory, Mcgraw-Hill College, 1967
	FOSC77	FoscmNI, G. J. "On heavy traffic diffusion analysis and dynamic routing in packet switched networks," in Computer performance, K.M. Chandy and M. Reiser (Eds.), Elsevier North-Holland, Inc., New York, 1977, pp. 419-514.
	FOST74	FOSTER, D. V.; MCGEHEARTY, P. F., SAUER, C, H,; AND WAGGONER, C. N. "A language for analysm of queueing models," in Proc. F~flh Annual P~ttsburgh Modelmg and Simulation Conf., 1974, pp. 381-386.
	GAVE68	GAVER, D. P. "Diffusion approxlmattons and models for certain congestmn problems," J. Appl. Probab. 5, (1968), 607-623.
	GAVE76	Donald P. Gaver , George Humfeld, Multitype multiprogramming: Probability models and numerical procedures, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.38-43, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806180]
	GELE75	Erol Gelenbe, On Approximate Computer System Models, Journal of the ACM (JACM), v.22 n.2, p.261-269, April 1975 [doi>10.1145/321879.321888]
	GELE76	GELENBE, E.; AND PUJOLLE, G "The behavior of a single queue in a general queueing network," Acta Inf 7, (1976), 123-136.
	GORD67	GORDON, W. J.; AND NEWELL, G F. "Closed queuemg networks with exponentml servers," Oper. Res. 15, (1967), 254-265.
	HERZ75	HERZOG, U., Woo, L S.; AND CHANDY, K. M "Solutmn of queuemg problems by a recurswe technique," IBM J. Res Dev. 19, (May 1975), 295-300.
	IGLE78	IGLEHART, D. L "The regenerative method for simulation analysis," in Current trends m programming methodology, Vol. III software modeling and ~ts impact on performance, K. M. Chandy and R. T. Yeh (Eds.), Prentice-Hall, Inc., Englewood Cliffs, N J., 1978, pp 52-71.
	INFO75	INFORMATION RESEARCH ASSOCIATES, User's manual for the ASQ system, I R A, Austin, Texas. 1975.
	IRLA75	IRLAND, M. "Queuemg analysm of a buffer aUocatmn scheme for a packet switch," m Proc. National Telecommunwatlons Conf., IEEE, New York, 1975, p 24
	JACK63	JACKSON, J R "Jobshop-hke queuemg systems," Manage. Sc~ 10, (1963), 131- 142
	KELL73	KELLER, T W. ASQ user's manual, TR- 27, Computer Science Dept., Umv Texas at Austin, Texas, 1973.
	KELL76	Thomas Walter Keller, Jr., Computer system models with passive resources., 1976
	KOBA74	Hisashi Kobayashi, Application of the Diffusion Approximation to Queueing Networks I: Equilibrium Queue Distributions, Journal of the ACM (JACM), v.21 n.2, p.316-328, April 1974 [doi>10.1145/321812.321827]
	KOBA78	KOBAYASHI, H. Modelhng and analysis an mtroductmn to system performance evaluatmn methodology, Addison-Wesley Publ Co, Reading, Mass, 1978, Ch 4
	LAM76	LAM, S. S. "Store-and-forward buffer reqmrements in a packet swRchmg network," IEEE Trans Commun 24, (April 1976}, 394-403.
	LAVE75	LAVENBERG, S. S, AND SLUTZ, D R. "Introductmn to regenerative s~mulatlon," IBM J. Res. Dev 19, (Sept 1975), 458-463.
	LAVE77	LAVENBERG, S S, AND SAUER, C H. "Sequentml stopping rules for the regenerative method of simulation," IBM J Res Dev. 21, (Nov. 1977), 545-558
	LAZO77	LAZOWSKA, E D. "The use of percentiles in modeling CPU servwe time distributions," m Computer performance, K.M. Chandy and M Reiser (Eds.), Elsevmr North-Holland, Inc., New York, 1977, pp. 53-66.
	MACN75	MACNAIR, E. A; AND WOO, L S. Private communicatmn, 1975.
	REIS74	REISER, M., AND KOBAYASHI, H. "Accuracy of the diffusion approximation for some queuelng systems," IBM J. Res Dec. 18, (1974).
	REIS75	REISER, M., AND KOBAYASHI, H. "Queuemg networks with multiple closed chains theory and computational algorithms," IBM J Res. Dec 19, 3 {May 1975), 283-294.
	REIS76	REISER, M "Interactive modehng of computer systems," IBM Syst J 15, (1976), 309-327.
	REIS78	REISER, M;AND SAUER, C H. "Queuelng network models methods of soluhon and their program implementation," in Current trends ~n programmtng methodology, Vol. III software modehng and tts tmpact on performance, K. M Chandy and R. T. Yeh (Eds.), Prentme-Hall, Inc., Englewood Chffs, N J, 1978, pp. 115-167.
	SAUE75a	Charles Herbert Sauer, Configuration of computing systems: an approach using queueing network models., 1975
	SAUE75b	SAUER, C. H, AND CHANDY, K. M "Approximate analysis of central server models," IBM J. Res. Dec 19, (May 1975), 301-313
	SAUE76	SAUER, C H., Woo, L S, AND CHANG, W Hybrid analys~s/slmulatmn" d~strtbuted networks, RC-634I, IBM Research, Yorktown Heights, N Y., June 1976
	SAUE77a	SAUER, C H. Conftdence tntervals for queue~ng s~mulattons of computer systterns, RC-6669, IBM Research, Yorktown Heights, N.Y, July 1977
	SAUE77b	Charles H. Sauer , K. Mani Chandy, The impact of distributions and disciplines on multiple processor systems, Communications of the ACM, v.22 n.1, p.25-34, Jan. 1979 [doi>10.1145/359046.359053]
	SAUE77C	SAUER, C H., AND MACNAIR, E A. Computer/communtcatmn system modehng w~th extended queue~ng networks, RC- 6654, IBM Research, Yorktown Heights, N Y., July 1977.
	SAUE78	SAUER, C H, AND MACNAIR, E A Queue~ng network software of systems modehng, RC-7143, IBM Research, Yorktown Heights, N.Y, May 1978.
	SCHW78	H. D. Schwetman, Hybrid simulation models of computer systems, Communications of the ACM, v.21 n.9, p.718-723, Sept. 1978 [doi>10.1145/359588.359594]
	SEKI71	SEKINO, A Performance evaluatmn of multlprogrammed trine.shared computer systems, Proj. MAC TR-103, MIT, Cambridge, Mass., Sept 1971
	SEVC77a	SEVCIK, K C "Prmrity scheduling dlsclphnes m queueing network models of computer systems," m Proc IFIP Congress 77, North-Holland Publ. Co., Amsterdam, pp. 565-570
	SEVC77b	SEVCIK, K C., LEVY, A I., TRIPATHI, S. K., AND ZAHORJAN, J L. "Improving approxlmatmns of aggregated queuemg network subsystems," m Computer performance, K.M Chandy and M. Reiser (Eds.), Elsewer North-Holland Inc., New York, 1977, pp. 1-22
	SHUM77	Annie W. Shum , Jeffrey P. Buzen, A Method for Obtaining Approximate Solutions to Closed Queueing Networks with General Service Times, Proceedings of the Third International Symposium on Measuring, Modelling and Evaluating Computer Systems, p.201-220, October 03-05, 1977
	STEW78	William J. Stewart, A comparison of numerical techniques in Markov modeling, Communications of the ACM, v.21 n.2, p.144-152, Feb. 1978 [doi>10.1145/359340.359350]
	TOWS75	Donald Fred Towsley, Local balance models of computer systems., 1975
	WALL66	WALLACE, V. L., AND ROSENBERG, R. S "Markovmn models and numermal analysis of computer system behavmr," in Proc. 1966 AFIPS Spring Jr. Computer Conf., Vol 28, Spartan Books, Washington, D C., pp 141-148
	WOLF77	WOLFF, R W. "The effect of servme time regularity on system performance," m Computer performance, K.M. Chandy and M. Relser (Eds.), Elsevier North-Holland, Inc, New York, 1977, ~)~). 297-304.
	WONG78	J. W. Wong, Queueing Network Modeling of Computer Communication Networks, ACM Computing Surveys (CSUR), v.10 n.3, p.343-351, Sept. 1978 [doi>10.1145/356733.356740]
	ZAHO77	ZAHORJAN, J. L. "Iterat~ve aggregatmn with global balance," Project SAM Notes, Umv. of Toronto, Toronto, Ont, Canada, Feb 1977.

CITED BY 44

	Darral J. Freund , James N. Bexfield, A new aggregation approximation procedure for solving closed queueing networks with simultaneous resource possession, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.214-223, August 29-31, 1983, Minneapolis, Minnesota, United States
	Clifford A. Rose, A Measurement Procedure for Queueing Network Models of Computer Systems, ACM Computing Surveys (CSUR), v.10 n.3, p.263-280, Sept. 1978
	Doug Neuse , K. Mani Chandy, HAM: the heuristic aggregation method for solving general closed queueing network models of computer systems, ACM SIGMETRICS Performance Evaluation Review, v.11 n.4, December 1982
	A. E. Krzesinski , P. Teunissen, Multiclass queueing networks with population constrainted subnetworks, ACM SIGMETRICS Performance Evaluation Review, v.13 n.2, p.128-139, Aug. 1985
	D. Potier , Ph. Leblanc, Analysis of locking policies in database management systems, Communications of the ACM, v.23 n.10, p.584-593, Oct. 1980
	Karen D. Gordon , Lawrence W. Dowdy, The impact of certain parameter estimation errors in queueing network models, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.3-9, Summer 1980
	Rajan Suri , Gregory W. Diehl, A new 'building block' for performance evaluation of queueing networks with finite buffers, ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.134-142, August 1984
	Subhash C. Agrawal , Jeffrey P. Buzen , Annie W. Shum, Response Time Preservation: A general technique for developing approximate algorithms for queueing networks, ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.63-77, August 1984
	Edward E. Balkovich , John A. Morse, Performance of distributed software implemented by a contention bus, Proceedings of the ACM '81 conference, p.39-45, January 1981
	Edward D. Lazowska , John Zahorjan, Analytic modelling of disk I/O subsystems: A tutorial, ACM SIGMETRICS Performance Evaluation Review, v.10 n.3, p.33-35, Fall 1981
	Raif O. Onvural, Survey of closed queueing networks with blocking, ACM Computing Surveys (CSUR), v.22 n.2, p.83-121, June 1990
	William J. Stewart , Gerald A. Zeiszler, On the existence of composite flow equivalent markovian servers, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.105-116, Summer 1980
	Hisao Kameda, Effects of job loading policies for multiprogramming systems in processing a job stream, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.71-106, Feb. 1986
	Alexander Thomasian , Paul Bay, Analysis of Queueing Network Models with population size constraints and delayed blocked customers, ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.202-216, August 1984
	Shmuel Rotenstreich, An adaptable and distributed load adjustment algorithm, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.418-423, February 1988, Atlanta, Georgia, United States
	Don Towsley, An approximate analysis of multiprocessor systems, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.207-213, August 29-31, 1983, Minneapolis, Minnesota, United States
	Richard R. Muntz, Queueing Networks: A Critique of the State of the Art and Directions for the Future, ACM Computing Surveys (CSUR), v.10 n.3, p.353-359, Sept. 1978
	Alexandre Brandwajn, Further results on equivalence and decomposition in queueing network models, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.93-104, Summer 1980
	Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978
	Charles H. Sauer, Computational algorithms for state-dependent queueing networks, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.67-92, Feb. 1983
	Jane Fedorowicz, Database performance evaluation in an indexed file environment, ACM Transactions on Database Systems (TODS), v.12 n.1, p.85-110, March 1987
	Leo H. Groner, QMOD: A system for automatically generating and solving analytical queueing network models, ACM SIGAPL APL Quote Quad, v.12 n.1, p.125-128, September 1981
	Patricia A. Jacobson , Edward D. Lazowska, The method of surrogate delays: Simultaneous resource possession in analytic models of computer systems, ACM SIGMETRICS Performance Evaluation Review, v.10 n.3, p.165-174, Fall 1981
	Patricia A. Jacobson , Edward D. Lazowska, Analyzing queueing networks with simultaneous resource possession, Communications of the ACM, v.25 n.2, p.142-151, Feb 1982
	Y. C. Tay , Rajan Suri , Nathan Goodman, A mean value performance model for locking in databases: the no-waiting case, Journal of the ACM (JACM), v.32 n.3, p.618-651, July 1985
	Y. Bard, The VM/370 Performance Predictor, ACM Computing Surveys (CSUR), v.10 n.3, p.333-342, Sept. 1978
	Rajan Suri, Infinitesimal perturbation analysis for general discrete event systems, Journal of the ACM (JACM), v.34 n.3, p.686-717, July 1987
	Randolph D. Nelson, The mathematics of product form queuing networks, ACM Computing Surveys (CSUR), v.25 n.3, p.339-369, Sept. 1993
	Alexander Thomasian , Behzad Nadji, Aggregation of stations in queueing network models of multiprogrammed computers, ACM SIGMETRICS Performance Evaluation Review, v.10 n.3, p.86-104, Fall 1981
	Charles H. Sauer, Numerical solution of some multiple chain queueing networks, ACM SIGMETRICS Performance Evaluation Review, v.12 n.4, p.19-28, Winter 1984-1985
	T. L. Lo, Computer capacity planning using queueing network models, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.145-152, Summer 1980
	Giovanni Chiola , Marco Ajmone Marsan , Gianfranco Balbo, Product-Form Solution Techniques for the Performance Analysis of Multiple-Bus Multiprocessor Systems with Nonuniform Memory References, IEEE Transactions on Computers, v.37 n.5, p.532-540, May 1988
	Ashwani K. Ramani , Pradip K. Chande , Pramod C. Sharma, A General Model for Performance Investigations of Priority Based Multiprocessor System, IEEE Transactions on Computers, v.41 n.6, p.747-754, June 1992
	Edward D. Lazowska , John Zahorjan, Multiple class memory constrained queueing networks, ACM SIGMETRICS Performance Evaluation Review, v.11 n.4, December 1982
	Alexander Thomasian , Kameshwar Gargeya, Speeding up computer system simulations using hierarchical modeling, ACM SIGMETRICS Performance Evaluation Review, v.12 n.4, p.34-39, Winter 1984-1985
	A. E. Fateyev , S. M. Porotskiy , V. I. Drujinin, Comparative evaluation of approximate methods for modelling of network systems, ACM SIGMETRICS Performance Evaluation Review, v.19 n.2, p.44-48, Aug. 1991
	Berth Eklundh, Queueing structure modelling, Proceedings of the 14th conference on Winter Simulation, December 06-08, 1982, San Diego, California
	Charles H. Sauer, Numerical solution of some multiple chain queueing networks, ACM SIGMETRICS Performance Evaluation Review, v.10 n.4, p.47-56, Winter 1981-1982
	Khaled Salah, Integrated performance evaluating criterion for selecting between interrupt coalescing and normal interruption, International Journal of High Performance Computing and Networking, v.3 n.5/6, p.434-445, March 2005
	Y. C. Tay , Rajan Suri, Choice and Performance in Locking for Databases, Proceedings of the 10th International Conference on Very Large Data Bases, p.119-128, August 27-31, 1984
	Sunkyo Kim , Ravi Muralidharan , Colm A. O'Cinneide, Taking Account of Correlations Between Streams in Queueing Network Approximations, Queueing Systems: Theory and Applications, v.49 n.3-4, p.261-281, April 2005
	Charles H. Sauer , Edward A. Macnair , James F. Kurose, The research queueing package: past, present, and future, Proceedings of the June 7-10, 1982, national computer conference, June 07-10, 1982, Houston, Texas
	Charles H. Sauer, Approximate solution of queueing networks with simultaneous resource possession, IBM Journal of Research and Development, v.25 n.6, p.894-903, November 1981
	Charles H. Sauer , Edward A. MacNair , Silvio Salza, A language for extended queuing network models, IBM Journal of Research and Development, v.24 n.6, p.747-755, November 1980