Large-scale join-idle-queue system with general service times

DOI10.1017/JPR.2017.49MaRDI QIDQ4684905zbMATH OpenOpenAlexFDO

Authors Alexander L. Stolyar, Sergey Foss

Publication date 26 September 2018

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.05968

zbMATH Keywords

asymptotic optimalityfluid limitjoin-idle-queuelarge-scale service systemload balancingpull-based load distributionstationary distribution

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22)

Abstract: A parallel server system with $n$ identical servers is considered. The service time distribution has a finite mean $1/mu$, but otherwise is arbitrary. Arriving customers are be routed to one of the servers immediately upon arrival. Join-Idle-Queue routing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where $noinfty$ and the customer input flow rate is $lambdan$. Under the condition $lambda/mu<1/2$, we prove that, as $noinfty$, the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant equal $lambda/mu$. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.

Recommendations

• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Many-server scaling of the N-system under FCFS-ALIS
• Two parallel queues with infinite servers and \textit{join the shortest queue} discipline
• Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
• Queue-and-idleness-ratio controls in many-server service systems

Cites work

• Asymptotic independence of queues under randomized load balancing
• Decay of tails at equilibrium for FIFO join the shortest queue networks
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• Large-scale heterogeneous service systems with general packing constraints
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• Pull-based load distribution in large-scale heterogeneous service systems
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Universality of load balancing schemes on the diffusion scale

Cited in

(14)

• Asymptotics of insensitive load balancing and blocking phases
• Many-server scaling of the N-system under FCFS-ALIS
• A load balancing system in the many-server heavy-traffic asymptotics
• Zero-wait load balancing with sparse messaging
• Stability of JSQ in queues with general server-job class compatibilities
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• A skill based parallel service system under FCFS-ALIS -- steady state, overloads, and abandonments
• Stationary waiting time in parallel queues with synchronization
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Delay, memory, and messaging tradeoffs in distributed service systems
• Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System
• Parallel Server Systems with Cancel-on-Completion Redundancy
• <scp>Steady‐state</scp> analysis of load balancing with Coxian‐2 distributed service times
• Invariance principle and McKean-Vlasov limit for randomized load balancing in heavy traffic

This page was built for publication: Large-scale join-idle-queue system with general service times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4684905)