research-article

Public Access

The PDE Method for the Analysis of Randomized Load Balancing Networks

Authors:

Kavita RamananAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 1, Issue 2

Article No.: 38, Pages 1 - 28

https://doi.org/10.1145/3154497

Published: 19 December 2017 Publication History

Abstract

We introduce a new framework for the analysis of large-scale load balancing networks with general service time distributions, motivated by applications in server farms, distributed memory machines, cloud computing and communication systems. For a parallel server network using the so-called $SQ(d)$ load balancing routing policy, we use a novel representation for the state of the system and identify its fluid limit, when the number of servers goes to infinity and the arrival rate per server tends to a constant. The fluid limit is characterized as the unique solution to a countable system of coupled partial differential equations (PDE), which serve to approximate transient Quality of Service parameters such as the expected virtual waiting time and queue length distribution. In the special case when the service time distribution is exponential, our method recovers the well-known ordinary differential equation characterization of the fluid limit.

Furthermore, we develop a numerical scheme to solve the PDE, and demonstrate the efficacy of the PDE approximation by comparing it with Monte Carlo simulations. We also illustrate how the PDE can be used to gain insight into the performance of large networks in practical scenarios by analyzing relaxation times in a backlogged network. In particular, our numerical approximation of the PDE uncovers two interesting properties of relaxation times under the SQ(2) algorithm. Firstly, when the service time distribution is Pareto with unit mean, the relaxation time decreases as the tail becomes heavier. This is a priori counterintuitive given that for the Pareto distribution, heavier tails have been shown to lead to worse tail behavior in equilibrium. Secondly, for unit mean light-tailed service distributions such as the Weibull and lognormal, the relaxation time decreases as the variance increases. This is in contrast to the behavior observed under random routing, where the relaxation time increases with increase in variance.

References

[1]

Aghajani, R. and Ramanan, K. (2017). Hydrodynamic limit of a randomized load balancing network. arXiv:1707.02005 {math.PR}.

[2]

Asmussen, S. (2003). Applied Probability and Queues. Springer-Verlag, 2nd edition edition.

[3]

Azar, Y., Broder, A. Z., Karlin, A. R., and Upfal, E. (1999). Balanced allocations. SIAM J. Comput., 29(1):180--200.

Digital Library

[4]

Billingsley, P. (1968). Convergence of Probability Measures. John Wiley, New York.

[5]

Bramson, M., Lu, Y., and Prabhakar, B. (2010). Randomized load balancing with general service time distributions. SIGMETRICS Perform. Eval. Rev., 38(1):275--286.

Digital Library

[6]

Bramson, M., Lu, Y., and Prabhakar, B. (2012). Asymptotic independence of queues under randomized load balancing. Queueing Systems, 71(3):247--292.

Digital Library

[7]

Bramson, M., Lu, Y., and Prabhakar, B. (2013). Decay of tails at equilibrium for FIFO join the shortest queue networks. The Annals of Applied Probability, 23(5):1841--1878.

[8]

Brown, L., Gans, N., Mandelbaum, A., Sakov, A., Shen, H., Zeltyn, S., and Zhao, L. (2005). Statistical analysis of a telephone call center. Journal of the American Statistical Association, 100(469):36--50.

[9]

Chen, S., Sun, Y., Kozat, U., Huang, L., Sinha, P., Liang, G., Liu, X., and Shroff, N. (2014). When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds. In INFOCOM, 2014 Proceedings IEEE, pages 1042--1050.

[10]

Courant, R., Isaacson, E., and Rees, M. (1952). On the solution of nonlinear hyperbolic differential equations by finite differences. Communications on Pure and Applied Mathematics, 5(3):243--255.

[11]

Dai, J., Dieker, A., and Gao, X. (2014). Validity of heavy-traffic steady-state approximations in many-server queues with abandonment. Queueing Systems, 78(1):1--29.

Digital Library

[12]

Ethier, S. and Kurtz, T. (1986). Markov processes: characterization and convergence. Wiley series in probability and mathematical statistics. Probability and mathematical statistics. Wiley.

[13]

Evans, L. (1998). Partial Differential Equations. Graduate Studies in Mathematics. American Math. Soc.

[14]

Farias, V., Moallemi, C., and Prabhakar, B. (2005). Load balancing with migration penalties. In Information Theory, 2005. ISIT 2005. Proceedings. International Symposium on, pages 558--562.

[15]

Graham, C. (2000). Chaoticity on path space for a queueing network with selection of the shortest queue among several. Journal of Applied Probability, 37(1):198--211.

[16]

Grossmann, C., Roos, H., and Stynes, M. (2007). Numerical Treatment of Partial Differential Equations. Universitext. Springer Berlin Heidelberg.

[17]

Kardassakis, K. (2014). Load balancing in stochastic networks: Algorithms, analysis, and game theory. Undergraduate Honors Thesis, Brown University.

[18]

Kolesar, P. (1984). Stalking the endangered cat: A queueing analysis of congestion at automatic teller machines. Interfaces, 14(6):16--26.

Digital Library

[19]

Liang, G. and Kozat, U. (2014). TOFEC: achieving optimal throughput-delay trade-off of cloud storage using erasure codes. In INFOCOM, 2014 Proceedings IEEE, pages 826--834.

[20]

Luczak, M. J. and McDiarmid, C. (2006). On the maximum queue length in the supermarket model. The Annals of Probability, 34(2):493--527.

[21]

Luczak, M. J. and Norris, J. (2005). Strong approximation for the supermarket model. The Annals of Applied Probability, 15(3):2038--2061.

[22]

Mitzenmacher, M. (2000). Analyses of load stealing models based on families of differential equations. Theory of Computing Systems, 34(1):77--98.

[23]

Mitzenmacher, M. (2001). The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst., 12(10):1094--1104.

Digital Library

[24]

Mukherjee, D., Borst, S., van Leeuwaarden, J., and Whiting, P. (2016). Universality of power-of-d load balancing in many-server systems. arXiv:1612.00723 {math.PR}.

[25]

Seelen, L. (1986). An algorithm for ph/ph/c queues. European Journal of Operational Research, 23(1):118 -- 127.

[26]

Vvedenskaya, N. D., Dobrushin, R. L., and Karpelevich, F. I. (1996). A queueing system with a choice of the shorter of two queues--an asymptotic approach. Problemy Peredachi Informatsii, 32(1):20--34.

Cited By

Abdul Jaleel JDoroudi SGardner K(2024)Queue-length-aware dispatching in large-scale heterogeneous systemsQueueing Systems10.1007/s11134-024-09918-x108:1-2(125-184)Online publication date: 3-Aug-2024
https://doi.org/10.1007/s11134-024-09918-x
Atar RKang WKaspi HRamanan K(2023)Long-Time Limit of Nonlinearly Coupled Measure-Valued Equations that Model Many-Server Queues with RenegingSIAM Journal on Mathematical Analysis10.1137/21M143312555:6(7189-7239)Online publication date: 7-Nov-2023
https://doi.org/10.1137/21M1433125
der Boor MBorst SVan Leeuwaarden JMukherjee D(2022)Scalable Load Balancing in Networked Systems: A Survey of Recent AdvancesSIAM Review10.1137/20M132374664:3(554-622)Online publication date: 4-Aug-2022
https://doi.org/10.1137/20M1323746
Show More Cited By

Index Terms

The PDE Method for the Analysis of Randomized Load Balancing Networks
1. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Partial differential equations
    2. Numerical analysis
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Statistical paradigms
      1. Queueing theory
2. Networks
  1. Network performance evaluation
    1. Network performance analysis

Recommendations

The PDE Method for the Analysis of Randomized Load Balancing Networks
SIGMETRICS '18

We introduce a new framework for the analysis of large-scale load balancing networks with general service time distributions, motivated by applications in server farms, distributed memory machines, cloud computing and communication systems. For a ...
Randomized load balancing with general service time distributions
Performance evaluation review

Randomized load balancing greatly improves the sharing of resources in a number of applications while being simple to implement. One model that has been extensively used to study randomized load balancing schemes is the supermarket model. In this model, ...
The PDE Method for the Analysis of Randomized Load Balancing Networks
SIGMETRICS '18: Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems

We introduce a new framework for the analysis of large-scale load balancing networks with general service time distributions, motivated by applications in server farms, distributed memory machines, cloud computing and communication systems. For a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 1, Issue 2

December 2017

480 pages

EISSN:2476-1249

DOI:10.1145/3175501

Editors:
Augustin Chaintreau
Columbia University
,
Aditya Akella
University of Wisconsin-Madison
,
Adam Wierman
California Institute of Technology

Issue’s Table of Contents

Copyright © 2017 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: 19 December 2017

Published in POMACS Volume 1, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
416
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abdul Jaleel JDoroudi SGardner K(2024)Queue-length-aware dispatching in large-scale heterogeneous systemsQueueing Systems10.1007/s11134-024-09918-x108:1-2(125-184)Online publication date: 3-Aug-2024
https://doi.org/10.1007/s11134-024-09918-x
Atar RKang WKaspi HRamanan K(2023)Long-Time Limit of Nonlinearly Coupled Measure-Valued Equations that Model Many-Server Queues with RenegingSIAM Journal on Mathematical Analysis10.1137/21M143312555:6(7189-7239)Online publication date: 7-Nov-2023
https://doi.org/10.1137/21M1433125
der Boor MBorst SVan Leeuwaarden JMukherjee D(2022)Scalable Load Balancing in Networked Systems: A Survey of Recent AdvancesSIAM Review10.1137/20M132374664:3(554-622)Online publication date: 4-Aug-2022
https://doi.org/10.1137/20M1323746
Hellemans TVan Houdt B(2022)Performance analysis of load balancing policies with memoryPerformance Evaluation10.1016/j.peva.2021.102259153:COnline publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1016/j.peva.2021.102259
Ramanan K(2022)Beyond mean-field limits for the analysis of large-scale networksQueueing Systems: Theory and Applications10.1007/s11134-022-09845-9100:3-4(345-347)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11134-022-09845-9
Hellemans TVan Houdt B(2020)Performance Analysis of Load Balancing Policies with MemoryProceedings of the 13th EAI International Conference on Performance Evaluation Methodologies and Tools10.1145/3388831.3388839(27-34)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3388831.3388839
KhudaBukhsh WKar SAlt BRizk AKoeppl H(2020)Generalized Cost-Based Job Scheduling in Very Large Heterogeneous Cluster SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.299777131:11(2594-2604)Online publication date: 1-Nov-2020
https://doi.org/10.1109/TPDS.2020.2997771
Aghajani RRamanan K(2019)The hydrodynamic limit of a randomized load balancing networkThe Annals of Applied Probability10.1214/18-AAP144429:4Online publication date: 1-Aug-2019
https://doi.org/10.1214/18-AAP1444
Hellemans TBodas TVan Houdt B(2019)Performance Analysis of Workload Dependent Load Balancing PoliciesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3341617.33261503:2(1-35)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3341617.3326150
Hellemans TBodas TVan Houdt BNahum EBonald TDuffield N(2019)Performance Analysis of Workload Dependent Load Balancing PoliciesAbstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems10.1145/3309697.3331504(7-8)Online publication date: 20-Jun-2019
https://dl.acm.org/doi/10.1145/3309697.3331504
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents