research-article

Bound analysis of closed queueing networks with workload burstiness

Authors:

Giuliano Casale,

Evgenia SmirniAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 36, Issue 1

Pages 13 - 24

https://doi.org/10.1145/1384529.1375460

Published: 02 June 2008 Publication History

Abstract

Burstiness and temporal dependence in service processes are often found in multi-tier architectures and storage devices and must be captured accurately in capacity planning models as these features are responsible of significant performance degradations. However, existing models and approximations for networks of first-come first-served (FCFS) queues with general independent (GI) service are unable to predict performance of systems with temporal dependence in workloads.

To overcome this difficulty, we define and study a class of closed queueing networks where service times are represented by Markovian Arrival Processes (MAPs), a class of point processes that can model general distributions, but also temporal dependent features such as burstiness in service times. We call these models MAP queueing networks. We introduce provable upper and lower bounds for arbitrary performance indexes (e.g., throughput, response time, utilization) that we call Linear Reduction (LR) bounds. Numerical experiments indicate that LR bounds achieve a mean accuracy error of 2 percent.

The result promotes LR bounds as a versatile and reliable bounding methodology of the performance of modern computer systems.

References

[1]

A. T. Andersen and B. F. Nielsen. A Markovian approach for modeling packet traffic with long-range dependence. IEEE JSAC, 16(5):719--732, 1998.

Digital Library

[2]

M. F. Arlitt and C. L. Williamson. Web server workload characterization: The search for invariants. In Proc. of ACM SIGMETRICS, pp. 126--137, 1996.

Digital Library

[3]

M. Arlitt and T. Jin. Workload characterization of the 1998 world cup web site. TR HPL-1999-35R1, HP Labs, 1999.

[4]

S. Asmussen and F. Koole. Marked point processes as limits of Markovian arrival streams. J. App. Prob., 30:365--372, 1993.

[5]

F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios. Open, closed, and mixed networks of queues with different classes of customers. JACM, 22(2):248--260, 1975.

Digital Library

[6]

D. Bertsimas and J. Tsitsiklis. Introduction to Linear Optimization. Athena, 1997.

Digital Library

[7]

G. Bolch, S. Greiner, H. de Meer, and K. S. Trivedi. Queueing Networks and Markov Chains. Wiley, 1998.

Digital Library

[8]

A. B. Bondi and W. Whitt. The influence of service-time variability in a closed network of queues. Perf. Eval., 6:219--234, 1986.

Digital Library

[9]

G. Casale, N. Mi, and E.Smirni. Bound analysis of closed queueing networks with nonrenewal workloads. TR WM-CS-2008-03, College of William and Mary, 2008.

[10]

G. Casale. An efficient algorithm for the exact analysis of multiclass queueing networks with large population sizes. In Proceedings of joint ACM SIGMETRICS/IFIP Performance 2006, pages 169--180. ACM Press, 2006.

Digital Library

[11]

G. Casale, E.Z. Zhang, and E. Smirni. Interarrival Times Characterization and Fitting for Markovian Traffic Analysis. TR WM-CS-2008-02, College of William and Mary, 2008.

[12]

K. M. Chandy, U. Herzog, and L. Woo. Parametric analysis of queueing networks. IBM J. Res. Dev., 19(1):36--42, 1975.

Digital Library

[13]

P. J. Courtois. Decomposability, instabilities, and saturation in multiprogramming systems. CACM, 18(7):371--377, 1975.

Digital Library

[14]

D. R. Cox and P. A. W. Lewis. The Statistical Analysis of Series of Events. John Wiley and Sons, New York, 1966.

[15]

MAP Queueing Networks Webpage. http://www.cs.wm.edu/MAPQN/.

[16]

D. L. Eager, D. J. Sorin, and M. K. Vernon. AMVA techniques for high service time variability. In Proc. of ACM SIGMETRICS, pp. 217--228. ACM Press, 2000.

Digital Library

[17]

W. Fischer and K. S. Meier-Hellstern. The Markov- Modulated Poisson Process (MMPP) cookbook. Perf. Eval., 18(2):149--171, 1993.

Digital Library

[18]

R. Fourer and D. M. Gay and B. W. Kernighan. AMPL - A Modeling Language for Mathematical Programming. Springer-Verlag, 1995.

[19]

GNU GLPK 4.8. http://www.gnu.org/software/glpk/.

[20]

A. Horváth and M. Telek. Markovian modeling of real data traffic: Heuristic phase type and MAP fitting of heavy tailed and fractal like samples. In Performance Evaluation of Complex Systems: Techniques and Tools, IFIP Performance 2002, LNCS Tutorial Series Vol 2459, pages 405--434, 2002.

Digital Library

[21]

S. Kounev and A. Buchmann. Performance modeling and evaluation of large-scale J2EE applications. In Proc. of the 29th International Conference of the Computer Measurement Group (CMG), pages 273--283, 2003.

[22]

E. D. Lazowska, J. Zahorjan, G. Graham, and K. C. Sevcik. Quantitative System Performance. Prentice-Hall, 1984.

Digital Library

[23]

W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson. On the self-similar nature of ethernet traffic. IEEE/ACM T. Networking, 2(1):1--15, 1994.

Digital Library

[24]

Z. Liu. Long range dependence and heavy tail distributions (special issue). Perf. Eval., 61(2-3):91--93, 2005.

Digital Library

[25]

N. Mi, Q. Zhang, A. Riska, E. Smirni, and E. Riedel. Performance impacts of autocorrelated flows in multi-tiered systems. Perf. Eval., 64(9-12):1082--1101, 2007.

Digital Library

[26]

J. Morrison and P.R. Kumar. New linear program performance bounds for closed queueing networks. Discrete Event Dynamic Systems: Theory and Applications, 11:291--317, 2001.

Digital Library

[27]

R. R. Muntz and J. W. Wong. Asymptotic properties of closed queueing network models. In Proc. Ann. Princeton Conf. on Inf. Sci. and Sys., pp. 348--352, 1974.

[28]

M. F. Neuts. Structured Stochastic Matrices of M/G/1 Type and Their Applications. Marcel Dekker, NY, 1989.

[29]

M. Reiser. A queueing network analysis of computer communication networks with window flow control. IEEE T. Comm., 27(8):1199--1209, 1979.

[30]

M. Reiser and S. S. Lavenberg. Mean-value analysis of closed multichain queueing networks. JACM, 27(2):312--322, 1980.

Digital Library

[31]

A. Riska and E. Riedel. Long-range dependence at the disk drive level. In Proc. of 3rd Conf. on Quantitative Eval. of Systems (QEST), pp. 41--50, IEEE Press, 2006.

Digital Library

[32]

J. Zahorjan, E. D. Lazowska, and R. L. Garner. A decomposition approach to modelling high service time variability. Perf. Eval., 3:35--54, 1983.

[33]

Q. Zhang, N. Mi, A. Riska, and E. Smirni Performance-Guided Load (Un)Balancing Under Autocorrelated Flows. IEEE T. on Parall. and Distrib. Sys., 19(5):652--665, May 2008.

Digital Library

Cited By

Bjorkqvist MGautam NBirke RChen LBinder W(2018)Optimizing for Tail Sojourn Times of Cloud ClustersIEEE Transactions on Cloud Computing10.1109/TCC.2015.24743676:1(156-167)Online publication date: 1-Jan-2018
https://doi.org/10.1109/TCC.2015.2474367
Berger DGland PSingla SCiucu F(2014)Exact analysis of TTL cache networksPerformance Evaluation10.1016/j.peva.2014.07.00179(2-23)Online publication date: Sep-2014
https://doi.org/10.1016/j.peva.2014.07.001
Rodriguez RJulvez JMerseguer J(2013)On the Performance Estimation and Resource Optimization in Process Petri NetsIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2013.224511843:6(1385-1398)Online publication date: Nov-2013
https://doi.org/10.1109/TSMC.2013.2245118
Show More Cited By

Index Terms

Bound analysis of closed queueing networks with workload burstiness
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies

Recommendations

Bound analysis of closed queueing networks with workload burstiness
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Burstiness and temporal dependence in service processes are often found in multi-tier architectures and storage devices and must be captured accurately in capacity planning models as these features are responsible of significant performance ...
Sojourn time approximations in queueing networks with feedback

This paper is motivated by the response-time analysis of distributed information systems, where transactions are handled by a sequence of front-end server and back-end server actions. We study sojourn times in an open queueing network with a single ...
Response times in a two-node queueing network with feedback

The study presented in this paper is motivated by the performance analysis of response times in distributed information systems, where transactions are handled by iterative server and database actions. We model system response times as sojourn times in ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 36, Issue 1

SIGMETRICS '08

June 2008

469 pages

ISSN:0163-5999

DOI:10.1145/1384529

Issue’s Table of Contents

SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2008
486 pages
ISBN:9781605580050
DOI:10.1145/1375457
General Chair:
Zhen Liu
IBM T. J. Watson Research Center, USA
,
Program Chairs:
Vishal Misra
Columbia University, USA
,
Prashant Shenoy
University of Massachusetts, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2008

Published in SIGMETRICS Volume 36, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
451
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bjorkqvist MGautam NBirke RChen LBinder W(2018)Optimizing for Tail Sojourn Times of Cloud ClustersIEEE Transactions on Cloud Computing10.1109/TCC.2015.24743676:1(156-167)Online publication date: 1-Jan-2018
https://doi.org/10.1109/TCC.2015.2474367
Berger DGland PSingla SCiucu F(2014)Exact analysis of TTL cache networksPerformance Evaluation10.1016/j.peva.2014.07.00179(2-23)Online publication date: Sep-2014
https://doi.org/10.1016/j.peva.2014.07.001
Rodriguez RJulvez JMerseguer J(2013)On the Performance Estimation and Resource Optimization in Process Petri NetsIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2013.224511843:6(1385-1398)Online publication date: Nov-2013
https://doi.org/10.1109/TSMC.2013.2245118
Kraft SCasale GKrishnamurthy DGreer DKilpatrick P(2012)Performance models of storage contention in cloud environmentsSoftware & Systems Modeling10.1007/s10270-012-0227-212:4(681-704)Online publication date: 1-Mar-2012
https://doi.org/10.1007/s10270-012-0227-2
Kraft SCasale GKrishnamurthy DGreer DKilpatrick PKounev SCortellessa VMirandola RLilja DSachs K(2011)IO performance prediction in consolidated virtualized environmentsProceedings of the 2nd ACM/SPEC International Conference on Performance engineering10.1145/1958746.1958789(295-306)Online publication date: 14-Mar-2011
https://dl.acm.org/doi/10.1145/1958746.1958789
Casale GMi NSmirni E(2010)Model-Driven System Capacity Planning under Workload BurstinessIEEE Transactions on Computers10.1109/TC.2009.13559:1(66-80)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1109/TC.2009.135
Ekren BHeragu S(2010)Approximate analysis of load-dependent generally distributed queuing networks with low service time variabilityEuropean Journal of Operational Research10.1016/j.ejor.2010.01.022205:2(381-389)Online publication date: Sep-2010
https://doi.org/10.1016/j.ejor.2010.01.022
Mi NCasale GCherkasova LSmirni E(2010)Sizing multi-tier systems with temporal dependence: benchmarks and analytic modelsJournal of Internet Services and Applications10.1007/s13174-010-0012-91:2(117-134)Online publication date: 21-Sep-2010
https://doi.org/10.1007/s13174-010-0012-9
Casale GKalbasi AKrishnamurthy DRolia J(2009)Automatic Stress Testing of Multi-tier Systems by Dynamic Bottleneck Switch GenerationMiddleware 200910.1007/978-3-642-10445-9_20(393-413)Online publication date: 2009
https://doi.org/10.1007/978-3-642-10445-9_20
Youssef AKrishnamurthy D(2017)Burstiness-aware service level planning for enterprise application cloudsJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-017-0087-y6:1(1-21)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1186/s13677-017-0087-y
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents