Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T07:51:00.397Z Has data issue: false hasContentIssue false
  • English
  • Français

A Strong Law for the Rate of Growth of Long Latency Periods in a Cloud Computing Service

Part of: Limit theorems Stochastic processes

Published online by Cambridge University Press:  04 January 2016

Souvik Ghosh  and
Soumyadip Ghosh
Souvik Ghosh*
Affiliation:
Columbia University
Soumyadip Ghosh*
Affiliation:
IBM T. J. Watson Research Centre
*
∗ Current address: LinkedIn Corporation, 2029 Stierlin Court, Mountain View, CA 94043, USA.
∗∗ Postal address: IBM T. J. Watson Research Center, 1101 Kitchawan Road, Yorktown Heights, NY 10598, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Cloud-computing shares a common pool of resources across customers at a scale that is orders of magnitude larger than traditional multiuser systems. Constituent physical compute servers are allocated multiple ‘virtual machines' (VMs) to serve simultaneously. Each VM user should ideally be unaffected by others’ demand. Naturally, this environment produces new challenges for the service providers in meeting customer expectations while extracting an efficient utilization from server resources. We study a new cloud service metric that measures prolonged latency or delay suffered by customers. We model the workload process of a cloud server and analyze the process as the customer population grows. The capacity required to ensure that the average workload does not exceed a threshold over long segments is characterized. This can be used by cloud operators to provide service guarantees on avoiding long durations of latency. As part of the analysis, we provide a uniform large deviation principle for collections of random variables that is of independent interest.

Keywords

Cloud computinglarge deviationslong strange segmentlatency periodmoving averagenonstationary process

MSC classification

Primary: 60F10: Large deviations
Secondary: 60F15: Strong theorems 60G99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 44 , Issue 4 , December 2012 , pp. 995 - 1017
Copyright
© Applied Probability Trust 

References

Apostol, T. M. (1974). Mathematical Analysis. Addison-Wesley, Reading, MA.Google Scholar
Arnold, B. C. (1980). Majorization and the Lorenz Order: A Brief Introduction (Lecture Notes Statist. 43). Springer.Google Scholar
Arratia, R., Gordon, L. and Waterman, M. S. (1990). The Erdös-Rényi law in distribution, for coin tossing and sequence matching. Ann. Statist. 18, 539–570.Google Scholar
Bryc, W. and Dembo, A. (1996). Large deviations and strong mixing. Ann. Inst. H. Poincaré Prob. Statist. 32, 549–569.Google Scholar
Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications, 2nd edn. Springer, New York.Google Scholar
Deuschel, J.-D. and Stroock, D. W. (1989). Large Deviations. Academic Press, Boston, MA.Google Scholar
Ellis, R. S. (1984). Large deviations for a general class of random vectors. Ann. Prob. 12, 1–12.Google Scholar
Erdös, P. and Rényi, A. (1970). On a new law of large numbers. J. Analyse Math. 23, 103–111.Google Scholar
Gartner, J. (1977). On large deviations from the invariant measure. Theory Prob. Appl. 22, 24–39.Google Scholar
Ghosh, S. and Samorodnitsky, G. (2009). The effect of memory on functional large deviations of infinite moving average processes. Stoch. Process. Appl. 119, 534–561.Google Scholar
Ghosh, S. and Samorodnitsky, G. (2010). Long strange segments, ruin probabilities and the effect of memory on moving average processes. Stoch. Process. Appl. 120, 2302–2330.Google Scholar
Khan, A., Yan, X., Tao, S. and Anerousis, N. (2012). Workload characterization and prediction in the cloud: a multiple time series approach. Submitted.Google Scholar
Li, H. et al. (2009). Developing an enterprise cloud computing strategy. White Paper, Intel Corporation.Google Scholar
Li, T.-H. (2005). A hierarchical framework for modeling and forecasting web server workload. J. Amer. Statist. Assoc. 100, 748–763.Google Scholar
Li, T.-H. (2007). A statistical framework of optimal workload consolidation with application to capacity planning for on-demand computing. J. Amer. Statist. Assoc. 102, 841–855.Google Scholar
Mansfield, P., Rachev, S. T. and Samorodnitsky, G. (2001). Long strange segments of a stochastic process. Ann. Appl. Prob. 11, 878–921.CrossRefGoogle Scholar
Mendler, C. (2010). Cloud 99.99: the small print exposed. Analyst Report, Yankee Group.Google Scholar
Rachev, S. T. and Samorodnitsky, G. (2001). Long strange segments in a long-range-dependent moving average. Stoch. Process. Appl. 93, 119–148.Google Scholar
Reid, S. et al. (2011). Sizing the cloud: understanding and quantifying the future of cloud computing. Tech. Rep., Forrester Research. Available at http://forrester.com/rb/Research/sizing_cloud/q/id/58161/t/2.Google Scholar
Varadhan, S. R. S. (1984). Large Deviations and Applications. SIAM, Philadelphia, PA.Google Scholar