Stability of Parallel Server Systems

• Published in: Operations research 2022-07, Vol.70 (4), p.2456-2476
• Main Authors: Moyal, Pascal, Perry, Ohad
• Format: Article
• Language: English
• Subjects: Arrivals; instability of subcritical systems; Markov analysis; Markov chains; Mathematical analysis; Mathematics; Operations research; parallel servers; Policies; Probability; Queues; Queuing theory; Routing; Servers; Stability; Statistical analysis; Stochastic Models; Vectors (mathematics); Workload; Workloads
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.2021.2125

A parallel server system is a queueing system in which jobs are routed upon their arrivals to one of several buffers, each handled by a different server. The main operational and theoretical problem in such systems is to find an efficient routing policy that maximizes their throughput (or minimizes waiting times). The paper “Stability of Parallel Server Systems” considers a large class of routing policies, which includes the most prevalent policies studies in the literature, under the assumption that routing errors may occur because ofincomplete information about the state of the system at decision epochs. The stability region for this class of policies is studied as a function of the error probability, and it is shown that the standard stability condition, namely, that the traffic intensity is smaller than one, does not guarantee that the system is stable. The fundamental problem in the study of parallel-server systems is that of finding and analyzing routing policies of arriving jobs to the servers that efficiently balance the load on the servers. The most well-studied policies are (in decreasing order of efficiency) join the shortest workload (JSW), which assigns arrivals to the server with the least workload; join the shortest queue (JSQ), which assigns arrivals to the smallest queue; the power-of- d (PW( d )), which assigns arrivals to the shortest among d ≥ 1 queues that are sampled from the total of s queues uniformly at random; and uniform routing, under which arrivals are routed to one of the s queues uniformly at random. In this paper we study the stability problem of parallel-server systems, assuming that routing errors may occur, so that arrivals may be routed to the wrong queue (not the smallest among the relevant queues) with a positive probability. We treat this routing mechanism as a probabilistic routing policy, named a p -allocation policy, that generalizes the PW( d ) policy, and thus also the JSQ and uniform routing, where p is an s -dimensional vector whose components are the routing probabilities. Our goal is to study the (in)stability problem of the system under this routing mechanism, and under its “nonidling” version, which assigns new arrivals to an idle server, if such a server is available, and otherwise routes according to the p -allocation rule. We characterize a sufficient condition for stability, and prove that the stability region, as a function of the system’s primitives and p , is in general smaller than the set { ρ < 1 }