Abstract
Load balancing is one of the key components in many distributed systems as it heavily impacts performance and resource utilization. We consider a heterogeneous system where each server belongs to one of K classes and the speed of the server depends on its class. Arriving jobs are immediately dispatched to a server class in a randomized manner, i.e., with probability \(p_k\) a job is assigned to class k. Within each class a power of d choices rule is used to select the server that executes the job.
For large systems and exponential job size durations the optimal probabilities \(p_k\) to minimize the mean response time can be determined easily via convex optimization. In this paper we develop a mean field model (validated by simulation) to investigate how these optimal probabilities \(p_k\) are affected by the higher moments and in particular by the variability of the job size distribution when the service discipline at each server is first-come-first-served. The main insight provided is that optimizing the probabilities \(p_k\) based on the higher moments is much more involved and provides only a non negligible gain for very specific system load regions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The asymptotic insensitivity under PS was proven given the ansatz of asymptotic independence of the queue length for any finite subset of queues.
- 2.
Redundant representations are order J phase-type distributions \((\alpha ,S)\) that can be represented by a phase-type distribution of a smaller order. For instance, any order \(J > 1\) phase type distribution with S equal to minus the identity matrix is a redundant representation of the exponential distribution with mean one.
References
Mukhopadhyay, A.K.A., Mazumdar, R.R.: Randomized assignment of jobs to servers in heterogeneous clusters of shared servers for low delay. Stoch. Syst. 6(1), 90–131 (2016)
Aghajani, R., Li, X., Ramanan, K.: The PDE method for the analysis of randomized load balancing networks. Proc. ACM Meas. Anal. Comput. Syst. 1(2), 38:1–38:28 (2017)
Altman, E., Ayesta, U., Prabhu, B.: Load balancing in processor sharing systems. In: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools, ValueTools 2008, pp. 12:1–12:10 (2008)
Bachmat, E., Sarfati, H.: Analysis of SITA policies. Perform. Eval. 67(2), 102–120 (2010)
Bause, F., Buchholz, P., Kriege, J.: Profido - the processes fitting toolkit dortmund. In: 2010 Seventh International Conference on the Quantitative Evaluation of Systems, pp. 87–96, September 2010
Bramson, M.: Stability of join the shortest queue networks. Ann. Appl. Probab. 21(4), 1568–1625 (2011)
Bramson, M., Lu, Y., Prabhakar, B.: Randomized load balancing with general service time distributions. In: ACM SIGMETRICS 2010, pp. 275–286 (2010)
Bramson, M., Lu, Y., Prabhakar, B.: Asymptotic independence of queues under randomized load balancing. Queueing Syst. 71(3), 247–292 (2012)
Ethier, S., Kurtz, T.: Markov Processes: Characterization and Convergence. Wiley, New York (1986)
Gandhi, A., Zhang, X., Mittal, N.: HALO: heterogeneity-aware load balancing. In: 23rd IEEE MASCOTS 2015, Atlanta, GA, USA, 5–7 October 2015, pp. 242–251 (2015)
Gast, N.: Expected values estimated via mean-field approximation are 1/n-accurate. Proc. ACM Meas. Anal. Comput. Syst. 1(1), 17:1–17:26 (2017)
Gast, N., Van Houdt, B.: A refined mean field approximation. Proc. ACM Meas. Anal. Comput. Syst. 1(2), 33:1–33:28 (2017)
Gupta, V., Harchol Balter, M., Sigman, K., Whitt, W.: Analysis of join-the-shortest-queue routing for web server farms. Perform. Eval. 64, 1062–1081 (2007)
Harchol-Balter, M.: Task assignment with unknown duration. J. ACM 49(2), 260–288 (2002)
Harchol-Balter, M., Crovella, M.E., Murta, C.D.: On choosing a task assignment policy for a distributed server system. J. Parallel Distrib. Comput. 59(2), 204–228 (1999)
Harchol-Balter, M., Scheller-Wolf, A., Young, A.R.: Surprising results on task assignment in server farms with high-variability workloads. SIGMETRICS Perform. Eval. Rev. 37(1), 287–298 (2009)
Latouche, G., Ramaswami, V.: Introduction to Matrix Analytic Methods and Stochastic Modeling. SIAM, Philadelphia (1999)
Li, Q.-L., Lui, J.C.S., Wang, Y.: A matrix-analytic solution for randomized load balancing models with PH service times. In: Hummel, K.A., Hlavacs, H., Gansterer, W. (eds.) PERFORM 2010. LNCS, vol. 6821, pp. 240–253. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25575-5_20
Mitzenmacher, M.: The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst. 12, 1094–1104 (2001)
Mukhopadhyay, A., Mazumdar, R.R.: Rate-based randomized routing in large heterogeneous processor sharing systems. In: 26th International Teletraffic Congress (ITC), Karlskrona, Sweden, pp. 1–9 (2014)
Pérez, J.F., Riaño, G.: jPhase: an object-oriented tool for modeling phase-type distributions. In: Proceeding from the 2006 Workshop on Tools for Solving Structured Markov Chains, SMCtools 2006. ACM, New York (2006)
Vvedenskaya, N., Dobrushin, R., Karpelevich, F.: Queueing system with selection of the shortest of two queues: an asymptotic approach. Probl. Peredachi Informatsii 32, 15–27 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Van Spilbeeck, I., Van Houdt, B. (2018). On the Impact of Job Size Variability on Heterogeneity-Aware Load Balancing. In: Takahashi, Y., Phung-Duc, T., Wittevrongel, S., Yue, W. (eds) Queueing Theory and Network Applications. QTNA 2018. Lecture Notes in Computer Science(), vol 10932. Springer, Cham. https://doi.org/10.1007/978-3-319-93736-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-93736-6_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-93735-9
Online ISBN: 978-3-319-93736-6
eBook Packages: Computer ScienceComputer Science (R0)