Systems with large flexible server pools: Instability of “natural” load balancing
Systems with large flexible server pools: Instability of “natural” load balancing
复制标题
具有大型灵活服务器池的系统：“自然”负载平衡的不稳定
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
E. Yudovina
中科院分区：
文献类型：
--
作者：
A. Stolyar;E. Yudovina
本文研究了具有多个客户类别和多个服务器（代理）池的一般大规模服务系统，平均服务时间依赖于客户类别和服务器池。假设允许的活动（路由选择）形成一棵树（在图中，顶点既是客户类又是服务器池）。我们研究了自然（负载平衡）的路由/调度规则，最长队列自由服务器（LQFS-LB），在许多服务器的渐近制度下，系统的行为，这样的外源到达率的客户类，以及在每个池中的代理的数量，增长到无穷大的比例，一些缩放参数$r$。LQBS-LB下的系统的平衡点是期望的操作点，其中服务器池负载最小化并且完全平衡。我们的主要结果如下。(a)我们发现，相当令人惊讶的是（树假设），对于某些参数范围内，系统的流体极限可能是不稳定的平衡点附近，这种不稳定性可能会发生，如果活动图不是“太小”。“（B）利用（a），我们证明了扩散标度过程的定态分布序列（测量离平衡点的偏差为O（sqrt{r}））可能是非紧的，实际上可能逃逸到无穷大。(c)在一个特殊的情况下，然而，我们表明，序列的平稳分布的扩散标度的过程是紧密的，和平稳分布的极限是平稳分布的极限扩散过程。
We consider general large-scale service systems with multiple customer classes and multiple server (agent) pools, mean service times depend both on the customer class and server pool. It is assumed that the allowed activities (routing choices) form a tree (in the graph with vertices being both customer classes and server pools). We study the behavior of the system under a natural (load balancing) routing/scheduling rule, Longest-Queue Freest-Server (LQFS-LB), in the many-server asymptotic regime, such that the exogenous arrival rates of the customer classes, as well as the number of agents in each pool, grow to infinity in proportion to some scaling parameter $r$. Equilibrium point of the system under LQBS-LB is the desired operating point, with server pool loads minimized and perfectly balanced. Our main results are as follows. (a) We show that, quite surprisingly (given the tree assumption), for certain parameter ranges, the fluid limit of the system may be unstable in the vicinity of the equilibrium point; such instability may occur if the activity graph is not "too small." (b) Using (a), we demonstrate that the sequence of stationary distributions of diffusion-scaled processes [measuring $O(sqrt{r})$ deviations from the equilibrium point] may be nontight, and in fact may escape to infinity. (c) In one special case of interest, however, we show that the sequence of stationary distributions of diffusion-scaled processes is tight, and the limit of stationary distributions is the stationary distribution of the limiting diffusion process.