Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers

Alexander L. Stolyar ()
Additional contact information
Alexander L. Stolyar: Lehigh University

Queueing Systems: Theory and Applications, 2017, vol. 85, issue 1, No 2, 65 pages

Abstract: Abstract 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 $$ n → ∞ , 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).

Keywords: Large-scale heterogeneous service systems; Multiple routers (dispatchers); Pull-based load distribution; Load balancing; Fluid limits; Asymptotic optimality; 90B15; 60K25 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-016-9508-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:85:y:2017:i:1:d:10.1007_s11134-016-9508-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-016-9508-8

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().