On the Asymptotic Insensitivity of the Supermarket Model in Processor Sharing Systems
- 7 June 2021
- journal article
- meeting abstracts
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 49 (1), 29-30
- https://doi.org/10.1145/3543516.3460100
Abstract
The supermarket model is a popular load balancing model where each incoming job is assigned to a server with the least number of jobs among d randomly selected servers. Several authors have shown that the large scale limit in case of processor sharing servers has a unique insensitive fixed point, which naturally leads to the belief that the queue length distribution in such a system is insensitive to the job size distribution as the number of servers tends to infinity. Simulation results that support this belief have also been reported. However, global attraction of the unique fixed point of the large scale limit was not proven except for exponential job sizes, which is needed to formally prove asymptotic insensitivity. The difficulty lies in the fact that with processor sharing servers, the limiting system is in general not monotone. In this paper we focus on the class of hyperexponential distributions of order $2$ and demonstrate that for this class of distributions global attraction of the unique fixed point can still be established using monotonicity by picking a suitable state space and partial order. This allows us to formally show that we have asymptotic insensitivity within this class of job size distributions. We further demonstrate that our result can be leveraged to prove asymptotic insensitivity within this class of distributions for other load balancing systems.
Keywords
Funding Information
- FWO (G033119N)
This publication has 7 references indexed in Scilit:
- On the Asymptotic Insensitivity of the Supermarket Model in Processor Sharing SystemsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2021
- Performance Analysis of Workload Dependent Load Balancing PoliciesACM SIGMETRICS Performance Evaluation Review, 2019
- Global Attraction of ODE-based Mean Field Models with Hyperexponential Job SizesProceedings of the ACM on Measurement and Analysis of Computing Systems, 2019
- The mean-field behavior of processor sharing systems with general job lengths under the SQ() policyPerformance Evaluation, 2018
- Asymptotic independence of queues under randomized load balancingQueueing Systems, 2012
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001
- A Generalization of Erlang's Loss System to State Dependent Arrival and Service RatesMathematics of Operations Research, 1978