More Web Proxy on the site http://driver.im/

research-article

QMLE: A Methodology for Statistical Inference of Service Demands from Queueing Data

Authors:

Giuliano Casale,

Manoj K. NambiarAuthors Info & Claims

ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), Volume 3, Issue 4

Article No.: 17, Pages 1 - 28

https://doi.org/10.1145/3233180

Published: 22 August 2018 Publication History

Abstract

Estimating the demands placed by services on physical resources is an essential step for the definition of performance models. For example, scalability analysis relies on these parameters to predict queueing delays under increasing loads. In this article, we investigate maximum likelihood (ML) estimators for demands at load-independent and load-dependent resources in systems with parallelism constraints. We define a likelihood function based on state measurements and derive necessary conditions for its maximization. We then obtain novel estimators that accurately and inexpensively obtain service demands using only aggregate state data. With our approach, and also thanks to approximation methods for computing marginal and joint distributions for the load-dependent case, confidence intervals can be rigorously derived, explicitly taking into account both topology and concurrency levels of the services. Our estimators and their confidence intervals are validated against simulations and real system measurements for two multi-tier applications, showing high accuracy also in models with load-dependent resources.

References

[1]

V. Apte, T. V. S. Viswanath, D. Gawali, A. Kommireddy, and A. Gupta. 2017. AutoPerf: Automated load testing and resource usage profiling of multi-tier internet applications. In Proc. of ICPE. ACM, pp. 115--126.

Digital Library

[2]

M. Awad and D. A. Menascé. 2017. Deriving parameters for open and closed QN models of operational systems through black box optimization. In Proc. of ICPE. ACM, pp. 127--138.

Digital Library

[3]

G. Bolch, S. Greiner, H. de Meer, and K. S. Trivedi. 2006. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. John Wiley 8 Sons.

Digital Library

[4]

S. Bruell, G. Balbo, and P. V. Afshari. 1984. Mean value analysis of mixed, multiple class BCMP networks with load dependent service stations. PEVA 4, 4 (1984), 241--260.

[5]

G. Casale. 2009. CoMoM: Efficient class-oriented evaluation of multiclass performance models. IEEE TSE. 35, 2 (2009), 162--177.

Digital Library

[6]

G. Casale, P. Cremonesi, and R. Turrin. 2008. Robust workload estimation in queueing network performance models. In Proc. of IEEE PDP. pp. 183--187.

Digital Library

[7]

G. Casale, J. F. Pérez, and W. Wang. 2015. QD-AMVA: Evaluating systems with queue-dependent service requirements. PEVA 91 (2015), 80--98.

Digital Library

[8]

P. Cremonesi, K. Dhyani, and A. Sansottera. 2010. Service time estimation with a refinement enhanced hybrid clustering algorithm. In Proc. of ASMTA. Springer, pp. 291--305.

Digital Library

[9]

P. Cremonesi and A. Sansottera. 2014. Indirect estimation of service demands in the presence of structural changes. PEVA 73 (2014), 18--40.

Digital Library

[10]

E. De Souza e Silva and R. R. Muntz. 1988. Simple relationships among moments of queue lengths in product form queueing networks. IEEE TC 37, 9 (1988), 1125--1129.

Digital Library

[11]

E. De Souza e Silva and S. Lavenberg. 1989. Calculating joint queue length distributions in product form queueing networks. JACM 36, 1 (1989), 194--207.

Digital Library

[12]

G. Franks, T. Al-Omari, M. Woodside, O. Das, and S. Derisavi. 2009. Enhanced modeling and solution of layered queueing networks. IEEE TSE 35, 2 (2009), 148--161.

Digital Library

[13]

D. Gmach, J. Rolia, L. Cherkasova, and A. Kemper. 2007. Workload analysis and demand prediction of enterprise data center applications. In Proc. of IEEE IISWC. pp. 171--180.

Digital Library

[14]

A. Kalbasi, D. Krishnamurthy, J. Rolia, and S. Dawson. 2012. DEC: Service demand estimation with confidence. IEEE TSE 38, 3 (2012), 561--578.

Digital Library

[15]

A. Kalbasi, D. Krishnamurthy, J. Rolia, and M. Richter. 2011. Mode: Mix driven on-line resource demand estimation. In Proc. of IEEE CNSM. pp. 1--9.

Digital Library

[16]

A. Khan, X. Yan, S. Tao, and N. Anerousis. 2012. Workload characterization and prediction in the cloud: A multiple time series approach. In Proc. of IEEE NOMS. pp. 1287--1294.

[17]

S. Kraft, S. Pacheco-Sanchez, G. Casale, and S. Dawson. 2009. Estimating service resource consumption from response time measurements. In Proc. of ValueTools. p. 48.

Digital Library

[18]

D. Kumar, L. Zhang, and A. Tantawi. 2009. Enhanced inferencing: Estimation of a workload dependent performance model. In Proc. of ValueTools. p. 47.

Digital Library

[19]

S. S. Lam and Y. L. Lien. 1983. A tree convolution algorithm for the solution of queueing networks. CACM 26 (1983), 203--215.

Digital Library

[20]

S. S. Lavenberg and G. S. Shedler. 1975. Derivation of confidence intervals for work rate estimators in a closed queuing network. SIAM J. Comput. 4, 2 (1975), 108--124.

Digital Library

[21]

Z. Liu, L. Wynter, C. H. Xia, and F. Zhang. 2006. Parameter inference of queueing models for IT systems using end-to-end measurements. PEVA 63 (2006), 36--60.

Digital Library

[22]

D. A. Menascé. 2008. Computing missing service demand parameters for performance models. In Int. CMG Conf. pp. 241--248.

[23]

D. A. Menascé, V. A. F. Almeida, L. W. Dowdy, and L. Dowdy. 2004. Performance by Design: Computer Capacity Planning by Example. Prentice Hall.

Digital Library

[24]

J. Moschetta and G. Casale. 2012. OFBench: An enterprise application benchmark for cloud resource management studies. In Proc. of SYNASC. pp. 393--399.

Digital Library

[25]

I. J. Myung. 2003. Tutorial on maximum likelihood estimation. JMP 47, 1 (2003), 90--100.

Digital Library

[26]

A. Kattepur and M. K. Nambiar. 2017. Service demand modeling and performance prediction with single-user tests. PEVA 110 (2017), 1--21.

[27]

G. Pacifici, W. Segmuller, M. Spreitzer, and A. Tantawi. 2008. CPU demand for web serving: Measurement analysis and dynamic estimation. PEVA 65, 6 (2008), 531--553.

Digital Library

[28]

Y. Pawitan. 2001. In All Likelihood: Statistical Modelling and Inference Using Likelihood. Oxford University Press.

[29]

J. F. Perez, G. Casale, and S. Pacheco-Sanchez. 2015. Estimating computational requirements in multi-threaded applications. IEEE TSE 41, 3 (2015), 264--278.

Digital Library

[30]

M. Reiser and H. Kobayashi. 1975. Queuing networks with multiple closed chains: Theory and computational algorithms. IBM J. Res. Dev. 19, 3 (1975), 283--294.

Digital Library

[31]

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

Digital Library

[32]

J. Rolia and V. Vetland. 1995. Parameter estimation for performance models of distributed application systems. In Proc. of CASCON. p. 54.

Digital Library

[33]

J. Rolia and V. Vetland. 1998. Correlating resource demand information with arm data for application services. In Proc. of ACM WOSP. pp. 219--230.

Digital Library

[34]

J. V. Ross, T. Taimre, and P. K. Pollett. 2007. Estimation for queues from queue length data. Queueing Syst. 55, 2 (2007), 131--138.

Digital Library

[35]

P. J. Schweitzer. 1979. Approximate analysis of multiclass closed networks of queues. In Proc. of Int. Conf. Stoc. Cont. Opt. pp. 25--29.

[36]

A. B Sharma, R. Bhagwan, M. Choudhury, L. Golubchik, R. Govindan, and G. M. Voelker. 2008. Automatic request categorization in internet services. ACM SIGMETRICS PER 36, 2 (2008), 16--25.

Digital Library

[37]

S. Spinner, G. Casale, F. Brosig, and S. Kounev. 2015. Evaluating approaches to resource demand estimation. PEVA 92 (2015), 51--71.

Digital Library

[38]

C. Sutton and M. I. Jordan. 2011. Bayesian inference for queueing networks and modeling of internet services. Ann. Appl. Stat. 5, 1 (2011), 254--282.

[39]

W. Wang, X. Huang, X. Qin, W. Zhang, J. Wei, and H. Zhong. 2012. Application-level cpu consumption estimation: Towards performance isolation of multi-tenancy web applications. In Proc. of IEEE CLOUD. IEEE, pp. 439--446.

Digital Library

[40]

W. Wang, G. Casale, and C. Sutton. 2016. A Bayesian approach to parameter inference in queueing networks. ACM Trans. Model. Comput. Simul. 27, 1 (Nov. 2016), Article No. 2.

Digital Library

[41]

W. Wang, G. Casale, A. Kattepur, and M. Nambiar. 2016. Maximum likelihood estimation of closed queueing network demands from queue length data. Proc. of ACM/SPEC ICPE. pp. 3--14.

Digital Library

[42]

X. Wu and M. Woodside. 2008. A calibration framework for capturing and calibrating software performance models. In Computer Performance Engineering. Springer, pp. 32--47.

Digital Library

[43]

Q. Zhang, L. Cherkasova, and E. Smirni. 2007. A regression-based analytic model for dynamic resource provisioning of multi-tier applications. In Proc. of IEEE ICAC. pp. 27--27.

Digital Library

[44]

T. Zheng, M. Woodside, and M. Litoiu. 2008. Performance model estimation and tracking using optimal filters. IEEE TSE 34, 3 (2008), 391--406.

Digital Library

Cited By

Zoppi TMungiello ICeccarelli ACirillo ASarti LEsposito LScaglione GRepetto SBondavalli A(2023)Safe Maintenance of Railways using COTS Mobile Devices: The Remote Worker DashboardACM Transactions on Cyber-Physical Systems10.1145/36071937:4(1-20)Online publication date: 14-Oct-2023
https://dl.acm.org/doi/10.1145/3607193
Zabrovskiy AAgrawal PKashansky VKersche RTimmerer CProdan R(2022)FSpot: Fast and Efficient Video Encoding Workloads Over Amazon Spot InstancesComputers, Materials & Continua10.32604/cmc.2022.02363071:3(5677-5697)Online publication date: 2022
https://doi.org/10.32604/cmc.2022.023630
Ciavotta MGibilisco GArdagna DNitto ELattuada Mda Silva M(2022)Architectural Design of Cloud Applications: A Performance-Aware Cost Minimization ApproachIEEE Transactions on Cloud Computing10.1109/TCC.2020.301570310:3(1571-1591)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TCC.2020.3015703
Show More Cited By

Index Terms

QMLE: A Methodology for Statistical Inference of Service Demands from Queueing Data
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic inference problems
      1. Maximum likelihood estimation

Recommendations

A novel approximation of NDA ML estimation for UWB channels

Novel non-data-aided near-maximum-likelihood estimators for the delays and the attenuations in an ultra-wide bandwidth channel are proposed by using an approximation to the maximum likelihood equation. Numerical results show that these new estimators ...
Combining the data from two normal populations to estimate the mean of one when their means difference is bounded

In this paper we address the problem of estimating θ₁ when Y_i∼^indN(θ_i, σ_i²), i = 1, 2, are observed and |θ₁ - θ₂|≤ c for a known constant c. Clearly Y₂ contains information about θ₁. We show how the so-called weighted likelihood function may be used to ...
Departures from a Queue with Many Busy Servers

<P>To analyze networks of queues, it is important to be able to analyze departure processes from single queues. For the M/M/s and M/G/∞ models, the stationary departure process is simple Poisson, but in general the stationary departure process is quite ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Performance Evaluation of Computing Systems

ACM Transactions on Modeling and Performance Evaluation of Computing Systems Volume 3, Issue 4

December 2018

175 pages

ISSN:2376-3639

EISSN:2376-3647

DOI:10.1145/3271433

Editors:
Sem Borst
Nokia Bell Labs / Eindhoven University of Technology, Netherlands
,
Carey Williamson
University of Calgary, Canada

Issue’s Table of Contents

Copyright © 2018 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: 22 August 2018

Accepted: 01 June 2018

Revised: 01 May 2018

Received: 01 December 2017

Published in TOMPECS Volume 3, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Amazon AWS in Education Research
European Commission
EPSRC

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
145
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)3

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zoppi TMungiello ICeccarelli ACirillo ASarti LEsposito LScaglione GRepetto SBondavalli A(2023)Safe Maintenance of Railways using COTS Mobile Devices: The Remote Worker DashboardACM Transactions on Cyber-Physical Systems10.1145/36071937:4(1-20)Online publication date: 14-Oct-2023
https://dl.acm.org/doi/10.1145/3607193
Zabrovskiy AAgrawal PKashansky VKersche RTimmerer CProdan R(2022)FSpot: Fast and Efficient Video Encoding Workloads Over Amazon Spot InstancesComputers, Materials & Continua10.32604/cmc.2022.02363071:3(5677-5697)Online publication date: 2022
https://doi.org/10.32604/cmc.2022.023630
Ciavotta MGibilisco GArdagna DNitto ELattuada Mda Silva M(2022)Architectural Design of Cloud Applications: A Performance-Aware Cost Minimization ApproachIEEE Transactions on Cloud Computing10.1109/TCC.2020.301570310:3(1571-1591)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TCC.2020.3015703
Liu XQi DLi WZhang H(2022)Exploring the Internet of Things sequence-structure detection and supertask network generation of temporal-spatial-based graph convolutional neural networkThe Journal of Supercomputing10.1007/s11227-021-04041-778:4(5029-5049)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11227-021-04041-7
Peng CHe DChen JKumar NKhan M(2021)EPRT: An Efficient Privacy-Preserving Medical Service Recommendation and Trust Discovery Scheme for eHealth SystemACM Transactions on Internet Technology10.1145/339767821:3(1-24)Online publication date: 16-Jun-2021
https://dl.acm.org/doi/10.1145/3397678
Dipietro SCasale G(2019)SD: A Divergence-Based Estimation Method for Service Demands in Cloud Systems2019 7th International Conference on Future Internet of Things and Cloud (FiCloud)10.1109/FiCloud.2019.00035(197-204)Online publication date: Aug-2019
https://doi.org/10.1109/FiCloud.2019.00035

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents