Load Balancing Under Strict Compatibility Constraints

DOI10.1287/MOOR.2022.1258MaRDI QIDQ6199240zbMATH OpenOpenAlexFDO

Authors Debankur Mukherjee

Publication date 23 February 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.07562

zbMATH Keywords

data localityload balancing on networkmany-server asymptoticsmean-field limitpower of \(d\)queueing theorystochastic coupling

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Continuous-time Markov processes on discrete state spaces (60J27) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: We study large-scale systems operating under the JSQ$(d)$ policy in the presence of stringent task-server compatibility constraints. Consider a system with $N$ identical single-server queues and $M(N)$ task types, where each server is able to process only a small subset of possible task types. Each arriving task selects $dgeq2$ random servers compatible to its type, and joins the shortest queue among them. The compatibility constraint is naturally captured by a fixed bipartite graph $G_N$ between the servers and the task types. When $G_N$ is complete bipartite, the meanfield approximation is proven to be accurate. However, such dense compatibility graphs are infeasible due to their overwhelming implementation cost and prohibitive storage capacity requirement at the servers. Our goal in this paper is to characterize the class of sparse compatibility graphs for which the meanfield approximation remains valid. To achieve this, first, we introduce a novel graph expansion-based notion, called proportional sparsity, and establish that systems with proportionally sparse compatibility graphs match the performance of a fully flexible system, asymptotically in the large-system limit. Furthermore, for any $c(N)$ satisfying ${\displaystyle }$frac{Nc(N)}{M(N)ln(N)} o inftyquad ext{and}quad c(N) o infty,${\displaystyle }$ as $Noinfty$, we show that proportionally sparse random compatibility graphs can be designed, so that the degree of each server is at most $c(N)$. This reduces the server-degree almost by a factor $N/ln(N)$, compared to the complete bipartite compatibility graph, while maintaining the same asymptotic performance. Extensive simulation experiments are conducted to corroborate the theoretical results.

Recommendations

• Exploiting data locality to improve performance of heterogeneous server clusters
• Universality of power-of-d load balancing in many-server systems
• Universality of load balancing schemes on the diffusion scale
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems

Cited in

(6)

• Exploiting data locality to improve performance of heterogeneous server clusters
• Optimal rate-matrix pruning for large-scale heterogeneous systems
• Fluid limits for interacting queues in sparse dynamic graphs
• Mean-field analysis for load balancing on spatial graphs
• Geometric lower bounds for the steady-state occupancy of processing networks with limited connectivity
• Mean-field analysis of large-scale bipartite queueing models for threshold-based and stochastic offloading multi-access edge computing

This page was built for publication: Load Balancing Under Strict Compatibility Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199240)