Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-22T15:05:20.613Z Has data issue: false hasContentIssue false
  • English
  • Français

Diffusion approximations for load balancing mechanisms in cloud storage systems

Part of: Markov processes Operations research and management science Limit theorems Special processes Stochastic analysis Probability theory on algebraic and topological structures

Published online by Cambridge University Press:  22 July 2019

Amarjit Budhiraja  and
Eric Friedlander
Amarjit Budhiraja*
Affiliation:
University of North Carolina at Chapel Hill
Eric Friedlander*
Affiliation:
University of North Carolina at Chapel Hill
*
*Postal address: Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, NC 27599, USA.
*Postal address: Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, NC 27599, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In large storage systems, files are often coded across several servers to improve reliability and retrieval speed. We study load balancing under the batch sampling routeing scheme for a network of n servers storing a set of files using the maximum distance separable (MDS) code (cf. Li (2016)). Specifically, each file is stored in equally sized pieces across L servers such that any k pieces can reconstruct the original file. When a request for a file is received, the dispatcher routes the job into the k-shortest queues among the L for which the corresponding server contains a piece of the file being requested. We establish a law of large numbers and a central limit theorem as the system becomes large (i.e. n → ∞), for the setting where all interarrival and service times are exponentially distributed. For the central limit theorem, the limit process take values in ℓ2, the space of square summable sequences. Due to the large size of such systems, a direct analysis of the n-server system is frequently intractable. The law of large numbers and diffusion approximations established in this work provide practical tools with which to perform such analysis. The power-of-d routeing scheme, also known as the supermarket model, is a special case of the model considered here.

Keywords

Mean-field approximationdiffusion approximationstochastic networkcylindrical Brownian motionpropagation of chaoscloud storage systemsupermarket modelMDS codingpower-of-d

MSC classification

Primary: 60K25: Queueing theory 60K35: Interacting random processes; statistical mechanics type models; percolation theory 60F05: Central limit and other weak theorems 60H30: Applications of stochastic analysis (to PDE, etc.)
Secondary: 90B22: Queues and service 60J28: Applications of continuous-time Markov processes on discrete state spaces 60J70: Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) 60B12: Limit theorems for vector-valued random variables (infinite-dimensional case)
Type
Original Article
Information
Advances in Applied Probability , Volume 51 , Issue 1 , March 2019 , pp. 41 - 86
Copyright
© Applied Probability Trust 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aghajani, R. and Ramanan, K. (2015). Ergodicity of an spde associated with a many-server queue. Preprint. Available at https://arxiv.org/abs/1512.02929v1.Google Scholar
Anderson, D. F. and Kurtz, T. G. (2015). Stochastic Analysis of Biochemical Systems, Vol. 1. Springer, Cham.CrossRefGoogle Scholar
Antunes, N., Fricker, C., Robert, P. and Tibi, D. (2008). Stochastic networks with multiple stable points. Ann. Prob. 36, 255–278.CrossRefGoogle Scholar
Atar, R. and Shifrin, M. (2014). An asymptotic optimality result for the multiclass queue with finite buffers in heavy traffic. Stoch. Systems 4, 556–603.CrossRefGoogle Scholar
Bell, S. L. and Williams, R. J. (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. Ann. Appl. Prob. 11, 608–649.Google Scholar
Bramson, M., Lu, Y. and Prabhakar, B. (2012). Asymptotic independence of queues under randomized load balancing. Queueing Systems 71, 247–292.CrossRefGoogle Scholar
Budhiraja, A. and Friedlander, E. (2017). Diffusion approximations for controlled weakly interacting large finite state systems with simultaneous jumps. Ann. Appl. Prob. 28, 204–249.CrossRefGoogle Scholar
Budhiraja, A. and Ghosh, A. P. (2012). Controlled stochastic networks in heavy traffic: convergence of value functions. Ann. Appl. Prob. 22, 734–791.CrossRefGoogle Scholar
Budhiraja, A. Ghosh, A. P. and Lee, C. (2011). Ergodic rate control problem for single class queueing networks. SIAM J. Control Optimization 49, 1570–1606.CrossRefGoogle Scholar
Da Prato, G. and Zabczyk, J. (2014). Stochastic Equations in Infinite Dimensions. Cambridge University Press.CrossRefGoogle Scholar
Dai, J. G. and Lin, W. (2008). Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Prob. 18, 2239–2299.CrossRefGoogle Scholar
Decreusefond, L. and Moyal, P. (2008). A functional central limit theorem for the M/GI/∞ queue. Ann. Appl. Prob. 18, 2156–2178.CrossRefGoogle Scholar
Eschenfeldt, P. and Gamarnik, D. (2015). Join the shortest queue with many servers. The heavy traffic asymptotics. Preprint. Available at https://arxiv.org/abs/1502.00999.Google Scholar
Ethier, S. N. and Kurtz, T. G. (2009). Markov Processes: Characterization and Convergence, Vol. 282. John Wiley, Hoboken.Google Scholar
Friedlander, E. (2018). Steady-state behavior of some load balancing mechanisms in cloud storage systems. Preprint. Available at https://arxiv.org/abs/1801.02979.Google Scholar
Graham, C. (2000). Chaoticity on path space for a queueing network with selection of the shortest queue among several. J. Appl. Prob. 37, 198–211.CrossRefGoogle Scholar
Harrison, J. M. (1988). Brownian models of queueing networks with heterogeneous customer populations. In Stochastic Differential Systems, Stochastic Control Theory and Applications, Springer, New York, pp. 147–186.CrossRefGoogle Scholar
Ikeda, N. and Watanabe, S. (1989). Stochastic Differential Equations and Diffusion Processes, 2nd edn. North-Holland Publishing, Amsterdam.Google Scholar
Jacod, J. and Shiryaev, A. N. (1987). Limit Theorems for Stochastic Processes. Springer, Heidelberg.CrossRefGoogle Scholar
Joffe, A. and Métivier, M. (1986). Weak convergence of sequences of semimartingales with applications to multitype branching processes. Adv. Appl. Prob. 18, 20–65.CrossRefGoogle Scholar
Kallianpur, G. and Xiong, J. (1995). Stochastic Differential Equations in Infinite-Dimensional Spaces (IMS Lecture Notes Monogr. Ser. 26). Institute of Mathematical Statistics, Hayward, CA.Google Scholar
Kang, H.-W. Kurtz, T. G. and Popovic, L. (2014). Central limit theorems and diffusion approximations for multiscale Markov chain models. Ann. Appl. Prob. 24, 721–759.CrossRefGoogle Scholar
Kaspi, H. and Ramanan, K. (2013). SPDE limits of many-server queues. Ann. Appl. Prob. 23, 145–229.CrossRefGoogle Scholar
Kurtz, T. G. (1971). Limit theorems for sequences of jump Markov processes approximating ordinary differential processes. J. Appl. Prob. 8, 344–356.CrossRefGoogle Scholar
Kurtz, T. G. (1980). Representations of Markov processes as multiparameter time changes. Ann. Prob. 8, 682–715.CrossRefGoogle Scholar
Kurtz, T. G. (1981). Approximation of Population Processes. SIAM, Philadelphia.CrossRefGoogle Scholar
Kushner, H. J. (2001). Heavy Traffic Analysis of Controlled Queueing and Communication Networks (Appl. Math. (New York) 47). Springer, New York.CrossRefGoogle Scholar
Li, B., Ramamoorthy, A. and Srikant, R. (2016). Mean-field-analysis of coding versus replication in cloud storage systems. In IEEE INFOCOM 2016, IEEE, Piscataway, NJ.Google Scholar
Lin, S. and Costello, D. J. (2004). Error Control Coding. Pearson Education India.Google Scholar
Métivier, M. (1982). Semimartingales: A Course on Sstochastic Processes, Vol. 2. Walter De Gruyter, Berlin.Google Scholar
Mitzenmacher, M. (2001). The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12, 1094–1104.CrossRefGoogle Scholar
Mukherjee, D., Borst, S. C., van Leeuwaarden, J. S. H. and WHITING, P. A. (2015). Universality of load balancing schemes on diffusion scale. Preprint. Available at https://arxiv.org/abs/1510.02657v1.Google Scholar
Reed, J. and Talreja, R. (2015). Distribution-valued heavy-traffic limits for the G/GI/∞ queue. Ann. Appl. Prob. 25, 1420–1474.CrossRefGoogle Scholar
Reed, M. and Simon, B. (1980). Functional Analysis, Vol. 1. Academic Press.Google Scholar
Stolyar, A. L. (2015). Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80, 341–361.CrossRefGoogle Scholar
Sznitman, A.-S. (1991). Topics in propagation of chaos. In Ecole d’été de probabilités de Saint-Flour XIX (Lecture Notes Math. 1464). Springer, Berlin, pp. 165–251.Google Scholar
Vvedenskaya, N. D., Dobrushin, R. L. and Karpelevich, F. I. (1996). Queueing system with selection of the shortest of two queues: an asymptotic approach. Probl. Peredachi Inf. 32. 20–34.Google Scholar
Whitt, W. (2002). Stochastic-Process Limits: an Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, New York.CrossRefGoogle Scholar