On the Asymptotic Insensitivity of the Supermarket Model in Processor Sharing Systems

作     者：Kielanski, Grzegorz Van Houdt, Benny 

作者机构：Univ Antwerp Middelheimlaan 1 B-2020 Antwerp Belgium 

出 版 物：《PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS》 (Proc. ACM Meas. Anal. Comput. Syst.)

年 卷 期：2021年第5卷第2期

页      面：1–28页

核心收录：

基　　金：FWO [G033119N] 

主　　题：Power-of-d-choices load balancing supermarket model large-scale systems processor sharing asymptotic insensitivity 

摘      要：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.