Join-the-shortest queue diffusion limit in Halfin–Whitt regime: Tail asymptotics and scaling of extrema
Join-the-shortest queue diffusion limit in Halfin–Whitt regime: Tail asymptotics and scaling of extrema
复制标题
Halfin–Whitt 机制中的加入最短队列扩散极限：尾部渐近和极值缩放
DOI：
10.1214/18-aap1436
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Debankur Mukherjee
中科院分区：
文献类型：
--
作者：
Sayantan Banerjee;Debankur Mukherjee
考虑一个系统的$N$并行单服务器队列与单位指数的服务时间分布和一个单一的调度器的任务到达率为泊松过程$\lambda（N）$。当一个任务到达时，调度程序根据Join-the-Shortest Queue（JSQ）策略将其分配给其中一个服务器。Eschenfeldt和Gamarnik（2015）建立了在Halfin-Whitt制度中，其中$（N-\lambda（N））/\sqrt{N}\to\beta>0$为$N\to\infty$，JSQ策略下系统的适当缩放的占用测度在任何有限时间间隔上弱收敛到某个扩散过程为$N\to\infty$。最近，Braverman（2018）进一步建立了系统的静态占用测度弱收敛到扩散过程的稳态，为$N\to\infty$。
在本文中，我们执行上述扩散过程的稳态的详细分析。具体来说，我们建立精确的尾部渐近的平稳分布和缩放的极值过程的大时间间隔。我们的结果意味着，渐近稳态缩放的服务器的队列长度为2或更大的数量表现出指数尾，而空闲服务器的数量原来是高斯。从方法论的角度来看，所考虑的扩散过程超越了扩散过程稳态研究的最新技术。缺乏任何封闭形式的表达的稳态和复杂的相互依赖的过程动态的本地时间的分析显着的挑战。我们开发了一种技术，涉及再生过程的理论，提供了一个易于处理的形式的固定措施，并结合几个尖锐的命中时间估计，作为一个关键的车辆在建立的结果。
Consider a system of $N$ parallel single-server queues with unit-exponential service time distribution and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(N)$. When a task arrives, the dispatcher assigns it to one of the servers according to the Join-the-Shortest Queue (JSQ) policy. Eschenfeldt and Gamarnik (2015) established that in the Halfin-Whitt regime where $(N-\lambda(N))/\sqrt{N}\to\beta>0$ as $N\to\infty$, appropriately scaled occupancy measure of the system under the JSQ policy converges weakly on any finite time interval to a certain diffusion process as $N\to\infty$. Recently, it was further established by Braverman (2018) that the stationary occupancy measure of the system converges weakly to the steady state of the diffusion process as $N\to\infty$.
In this paper we perform a detailed analysis of the steady state of the above diffusion process. Specifically, we establish precise tail-asymptotics of the stationary distribution and scaling of extrema of the process on large time-interval. Our results imply that the asymptotic steady-state scaled number of servers with queue length two or larger exhibits an Exponential tail, whereas that for the number of idle servers turns out to be Gaussian. From the methodological point of view, the diffusion process under consideration goes beyond the state-of-the-art techniques in the study of the steady-state of diffusion processes. Lack of any closed form expression for the steady state and intricate interdependency of the process dynamics on its local times make the analysis significantly challenging. We develop a technique involving the theory of regenerative processes that provides a tractable form for the stationary measure, and in conjunction with several sharp hitting time estimates, acts as a key vehicle in establishing the results.
DOI：
10.48550/arxiv.1510.02328
发表时间：
2015
期刊：
arXiv e-prints
影响因子：
--
作者：
Banerjee Sayan
通讯作者：
Banerjee Sayan