Stability of Parallel Server Systems

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 } . Our analyses build on representing the queue process as a continuous-time Markov chain in an ordered space of s -dimensional real-valued vectors, and using a generalized form of the Schur-convex order.