ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
Linearizer: a heuristic algorithm for queueing network models of computing systems
Full text PdfPdf (670 KB)
Source
Communications of the ACM archive
Volume 25 ,  Issue 2  (February 1982) table of contents
Pages: 126 - 134  
Year of Publication: 1982
ISSN:0001-0782
Authors
K. Mani Chandy  Univ. of Texas, Austin
Doug Neuse  Univ. of Texas, Austin
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 4,   Downloads (12 Months): 41,   Citation Count: 52
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/358396.358403
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.

1
Yonathan Bard, A model of shared DASD and multipathing, Communications of the ACM, v.23 n.10, p.564-572, Oct. 1980  [doi>10.1145/359015.359019]
 
2
Yonathan Bard, Some Extensions to Multiclass Queueing Network Analysis, Proceedings of the Third International Symposium on Modelling and Performance Evaluation of Computer Systems: Performance of Computer Systems, p.51-62, February 06-08, 1979
3
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]
4
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]
 
5
Buzen, J.P., and Denning, P.J. Measuring and calculating queue length distributions. Computer 13,4 (April 1980), 33--46.
 
6
Chandy, K.M., Herzog, U., and Woo, L. Approximate analysis of general queueing networks. IBM J. Res. Develop. 19,1 (Jan. 1975), 43-49.
 
7
Comput. Surv. 10,3 (Sept. 78), Special Issue on Queueing Network Models of Computer System Performance.
 
8
Lavenberg, S.S., and Reiser, M. Stationary state probabilities of arrival instants for closed queueing networks with multiple types of customers. Res. Rep. RC 7592, IBM Corp., April 1979. IBM Thomas J. Watson Research Center, Yorktown Heights, NY.
 
9
Little, J.D.C. A proof of the queueing formula L = W. Oper. Res. 9 (1961), 383-387.
10
M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980  [doi>10.1145/322186.322195]
 
11
Sauer, C.H., and Chandy, K.M. Computer System Performance Modeling: A Primer. Prentice-Hall, Englewood Cliffs, N J, 1980.
 
12
Schweitzer, P. Approximate analysis of multiclass closed networks of queues. Presented at the Int. Conf. Stochastic Control and Optimization, Amsterdam, 1979.
13
K. C. Sevcik , I. Mitrani, The Distribution of Queuing Network States at Input and Output Instants, Journal of the ACM (JACM), v.28 n.2, p.358-371, April 1981  [doi>10.1145/322248.322257]
 
14
John Zahorjan, The approximate solution of large queueing network models, 1980

CITED BY  52
Greg Franks , Murray Woodside, Performance of multi-level client-server systems with parallel service operations, Proceedings of the 1st international workshop on Software and performance, p.120-130, October 12-16, 1998, Santa Fe, New Mexico, United States
K. R. Pattipati , M. M. Kostreva , J. L. Teele, Approximate mean value analysis algorithms for queuing networks: existence, uniqueness, and convergence results, Journal of the ACM (JACM), v.37 n.3, p.643-673, July 1990
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
John Zahorjan , Edward D. Lazowska, Incorporating load dependent servers in approximate mean value analysis, ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.52-62, August 1984
A. E. Conway , N. D. Georganas, RECAL—a new efficient algorithm for the exact analysis of multiple-chain closed queuing networks, Journal of the ACM (JACM), v.33 n.4, p.768-791, Oct. 1986
Kenneth C. Sevcik , Hai Wang, Solution properties and convergence of an approximate mean value analysis algorithm, ACM SIGMETRICS Performance Evaluation Review, v.29 n.4, March 2002
Randolph D. Nelson, The mathematics of product form queuing networks, ACM Computing Surveys (CSUR), v.25 n.3, p.339-369, Sept. 1993
A. Krzesinski , J. Greyling, Improved lineariser methods for queueing networks with queue dependent centres, ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.41-51, August 1984
Raymond M. Bryant , Anthony E. Krzesinski , M. Seetha Lakshmi , K. Mani Chandy, The MVA priority approximation, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.335-359, Nov. 1984
Jeffrey P. Buzen, An overview of performance prediction in MVS systems and SNA networks, Proceedings of 1986 ACM Fall joint computer conference, p.751-759, November 1986, Dallas, Texas, United States
Debasis Mitra , J. McKenna, Asymptotic expansions for closed Markovian networks with state-dependent service rates, Journal of the ACM (JACM), v.33 n.3, p.568-592, July 1986
Gordon E. Anderson, The coordinated use of five performance evaluation methodologies, Communications of the ACM, v.27 n.2, p.119-125, Feb. 1984
M. Litoiu , Hamid Khafagy , Bin Qin , Anita Rass Wan , J. Rolia, A performance engineering tool and method for distributing applications, Proceedings of the 1997 conference of the Centre for Advanced Studies on Collaborative research, p.14, November 10-13, 1997, Toronto, Ontario, Canada
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
Simon S. Lam , Y. Luke Lien, A tree convolution algorithm for the solution of queueing networks, Communications of the ACM, v.26 n.3, p.203-215, March 1983
Peter J. Denning, ACM president's letter: performance analysis: experimental computer science as its best, Communications of the ACM, v.24 n.11, p.725-727, Nov. 1981
S. F. Lam, An empirical study of computer capacity planning in Japan, Communications of the ACM, v.31 n.8, p.965-976, Aug. 1988
Raymond M. Bryant , Anthony E. Krzesinski , Peter Teunissen, The MVA Pre-empt resume priority approximation, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.12-27, August 29-31, 1983, Minneapolis, Minnesota, United States
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
Alexander Thomasian , Paul Bay, Analytic solution of an integrated performance model of a computer communication network with window flow control, ACM SIGCOMM Computer Communication Review, v.14 n.2, p.225-232, June 1984
Keith W. Ross , Danny H. K. Tsang , Jie Wang, Monte Carlo summation and integration applied to multiclass queuing networks, Journal of the ACM (JACM), v.41 n.6, p.1110-1135, Nov. 1994
J. McKenna , Debasis Mitra, Asymptotic Expansions and Integral Representations of Moments of Queue Lengths in Closed Markovian Networks, Journal of the ACM (JACM), v.31 n.2, p.346-360, April 1984
Derek L. Eager , Kenneth C. Sevcik, Bound hierarchies for multiple-class queuing networks, Journal of the ACM (JACM), v.33 n.1, p.179-206, Jan. 1986
Robert Berry , K. Mani Chandy, Performance models of token ring local area networks, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.266-274, August 29-31, 1983, Minneapolis, Minnesota, United States
C.-H. Hsieh , S. S. Lam, PAM-a noniterative approximate solution method for closed multichain queueing networks, ACM SIGMETRICS Performance Evaluation Review, v.16 n.1, p.261-269, May 1988
Johann Strelen, A generalization of mean value analysis to higher moments: moment analysis, ACM SIGMETRICS Performance Evaluation Review, v.14 n.1, p.129-140, May 1986
Subhash C. Agrawal , Jeffrey P. Buzen, The aggregate server method for analyzing serialization delays in computer systems, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.116-143, May 1983
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
Matteo Sereno, Approximate Mean Value Analysis for Stochastic Marked Graphs, IEEE Transactions on Software Engineering, v.22 n.9, p.654-664, September 1996
A. Masud Khandker , Jerome A. Rolia , Toby J. Teorey, Performance modeling of the distributed computing environment, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.38, November 07-09, 1995, Toronto, Ontario, Canada
William C. Cheng , Richard R. Muntz, Bounding errors introduced by clustering of customers in closed product-form queuing networks, Journal of the ACM (JACM), v.43 n.4, p.641-669, July 1996
Derek L. Eager , Kenneth C. Sevcik, Performance bound hierarchies for queueing networks, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.99-115, May 1983
Elias Drakopoulos , Matt J. Merges, Performance Analysis of Client-Server Storage Systems, IEEE Transactions on Computers, v.41 n.11, p.1442-1452, November 1992
E. de Souza e Silva , R. R. Muntz, A Note on the Computational Cost of the Linearizer Algorithm for Queueing Networks, IEEE Transactions on Computers, v.39 n.6, p.840-842, June 1990
P. S. Yu , S. Balsamo , Y. H. Lee, Dynamic Transaction Routing in Distributed Database Systems, IEEE Transactions on Software Engineering, v.14 n.9, p.1307-1318, September 1988
Paolo Cremonesi , Paul J. Schweitzer , Giuseppe Serazzi, A Unifying Framework for the Approximate Solution of Closed Multiclass Queuing Networks, IEEE Transactions on Computers, v.51 n.12, p.1423-1434, December 2002
Edward D. Lazowska , John Zahorjan, Multiple class memory constrained queueing networks, ACM SIGMETRICS Performance Evaluation Review, v.11 n.4, December 1982
Marin Litoiu , Jerome Rolia , Giuseppe Serazzi, Designing Process Replication and Activation: A Quantitative Approach, IEEE Transactions on Software Engineering, v.26 n.12, p.1168-1178, December 2000
J. A. Rolia , K. C. Sevcik, The Method of Layers, IEEE Transactions on Software Engineering, v.21 n.8, p.689-700, August 1995
Lindsey E. Stephens , Lawrence W. Dowdy, Convolutional bound hierarchies, ACM SIGMETRICS Performance Evaluation Review, v.12 n.3, p.120-133, August 1984
Hartmut Deike-Glindemann, SIQUEUE-PET: an environment for queueing network modelling, ACM SIGMETRICS Performance Evaluation Review, v.19 n.3, p.36-44, Feb. 1992
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
V. S. Adve , M. K. Vernon, Performance Analysis of Mesh Interconnection Networks with Deterministic Routing, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.225-246, March 1994
Tariq Omari , Greg Franks , Murray Woodside , Amy Pan, Solving layered queueing networks of large client-server systems with symmetric replication, Proceedings of the 5th international workshop on Software and performance, p.159-166, July 12-14, 2005, Palma, Illes Balears, Spain
J. Etkin , J. A. Zinky, Development Life Cycle of Computer Networks: The Executable Model Approach, IEEE Transactions on Software Engineering, v.15 n.9, p.1078-1089, September 1989
Giuliano Casale, An efficient algorithm for the exact analysis of multiclass queueing networks with large population sizes, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
K. R. Pattipati , M. M. Kostreva, On the properties of approximate mean value analysis algorithms for queueing networks, ACM SIGMETRICS Performance Evaluation Review, v.16 n.1, p.244-252, May 1988
Tariq Omari , Greg Franks , Murray Woodside , Amy Pan, Efficient performance models for layered server systems with replicated servers and parallel behaviour, Journal of Systems and Software, v.80 n.4, p.510-527, April, 2007
Tariq Omari , Salem Derisavi , Greg Franks, Deriving distribution of thread service time in layered queueing networks, Proceedings of the 6th international workshop on Software and performance, February 05-08, 2007, Buenes Aires, Argentina
Kwang-Hoon Kim , Clarence A. Ellis, Performance Analytic Models and Analyses for Workflow Architectures, Information Systems Frontiers, v.3 n.3, p.339-355, September 2001
Hai Wang , Kenneth C. Sevcik , Giuseppe Serazzi , Shouhong Wang, The general form linearizer algorithms: A new family of approximate mean value analysis algorithms, Performance Evaluation, v.65 n.2, p.129-151, February, 2008
Dinkar Sitaram, The inconsistency index method for estimating the accuracy of Schweitzer's approximation, IBM Journal of Research and Development, v.31 n.4, p.475-483, July 1, 1987

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis


General Terms:
Algorithms, Experimentation, Performance


Keywords:
closed queueing network, local balance queueing network, product-form queueing network

Collaborative Colleagues:
K. Mani Chandy: colleagues
Doug Neuse: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player