Diffusion Approximations for Load Balancing Mechanisms in Cloud Storage Systems
| Autor: | Budhiraja, Amarjit, Friedlander, Eric |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 routing scheme for a network of $n$ servers storing a set of files using the Maximum Distance Separable (MDS) code (cf. Li, Ramamoorthy, and Srikant (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\to\infty$). For the central limit theorem, the limit process take values in $\mathbf{\ell}_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$ routing scheme, also known as the supermarket model, is a special case of the model considered here. Comment: 40 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|