Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
详细信息 查看全文
- 作者：Alexander L. Stolyar
- 关键词：Large ; scale heterogeneous service systems ; Multiple routers (dispatchers) ; Pull ; based load distribution ; Load balancing ; Fluid limits ; Asymptotic optimality
- 刊名：Queueing Systems
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：85
- 期：1-2
- 页码：31-65
- 全文大小：
- 刊物类别：Business and Economics
- 刊物主题：Operation Research/Decision Theory; Computer Communication Networks; Probability Theory and Stochastic Processes; Supply Chain Management; Systems Theory, Control;
- 出版者：Springer US
- ISSN：1572-9443
- 卷排序：85
文摘
The model is a service system, consisting of several large server pools. A server’s processing speed and buffer size (which may be finite or infinite) depend on the pool. The input flow of customers is split equally among a fixed number of routers, which must assign customers to the servers immediately upon arrival. We consider an asymptotic regime in which the total customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to a scaling parameter n, while the number of routers remains fixed. We define and study a multi-router generalization of the pull-based customer assignment (routing) algorithm PULL, introduced in Stolyar (Queueing Syst 80(4): 341–361, 2015) for the single-router model. Under the PULL algorithm, when a server becomes idle it sends a “pull-message” to a randomly uniformly selected router; each router operates independently—it assigns an arriving customer to a server according to a randomly uniformly chosen available (at this router) pull-message, if there is any, or to a randomly uniformly selected server in the entire system otherwise. Under Markov assumptions (Poisson arrival process and independent exponentially distributed service requirements), and under subcritical system load, we prove asymptotic optimality of PULL: as \(n\rightarrow \infty \), the steady-state probability of an arriving customer experiencing blocking or waiting vanishes. Furthermore, PULL has an extremely low router–server message exchange rate of one message per customer. These results generalize some of the single-router results in Stolyar (2015).