Mean Waiting Time in Large-Scale and Critically Loaded Power of d Load Balancing Systems

2020/04/02 by Tim Hellemans, Hellemans, Tim, Benny Van Houdt +1
Business, Management and Accounting · Computer Science · #Advanced Queuing Theory Analysis #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #FOS: Mathematics #Performance (cs.PF) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2004.00876

openalex publication_date 2020/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Mean field models are a popular tool used to analyse load balancing policies. In some cases the waiting time distribution of the mean field limit has an explicit form. In other cases it can be computed as the solution of a set of differential equations. Here we study the limit of the mean waiting time E[W_λ] as the arrival rate λ approaches 1 for a number of load balancing policies when job sizes are exponential with mean 1 (i.e. the system gets close to instability). As E[W_λ] diverges to infinity, we scale with -log(1-λ) and present a method to compute the limit lim_{λ→ 1^-}-E[W_λ]/log(1-λ). This limit has a surprisingly simple form for the load balancing algorithms considered. We present a general result that holds for any policy for which the associated differential equation satisfies a list of assumptions. For the LL(d) policy which assigns an incoming job to a server with the least work left among d randomly selected servers these assumptions are trivially verified. For this policy we prove the limit is given by (1)/(d-1). We further show that the LL(d,K) policy, which assigns batches of K jobs to the K least loaded servers among d randomly selected servers, satisfies the assumptions and the limit is equal to (K)/(d-K). For a policy which applies LL(d_i) with probability p_i, we show that the limit is given by (1)/(∑_ip_id_i-1). We further indicate that our main result can also be used for load balancers with redundancy or memory. In addition, we propose an alternate scaling -log(p_λ) instead of -log(1-λ), for which the limit lim_{λ→ 0⁺}-E[W_λ]/log(p_λ) is well defined and non-zero (contrary to lim_{λ→ 0⁺}-E[W_λ]/log(1-λ)), while lim_{λ→ 1^-}log(1-λ) / log(p_λ)=1.

Related

• On the Rate of Convergence of the Power-of-Two-Choices to its Mean-Field Limit
• Performance Analysis of Load Balancing Policies with Memory
• Performance of Load Balancers with Bounded Maximum Queue Length in case of Non-Exponential Job Sizes
• On the Power-of-d-choices with Least Loaded Server Selection
• Mean-field analysis of load balancing principles in large scale systems