Stability of join the shortest queue networks (Q640066)

An arriving job is presented with a random subset \(B\) of queues, with probability depending only on the stream and chooses the queue in \(B\) with the fewest number of jobs; when two or more queues have the fewest jobs, one of these queues is chosen according to some rule. Jobs at queues are served according to some discipline, upon completion leave the network. For nonexponential service time distributions the stability of even subcritical networks is not obvious. Jobs might be assigned to short queues where the remaining work is high, this can cause service inactivity for queues with many jobs but low remaining work. The paper assumes multiple arrival streams and general service disciplines, instead of fluid limit techniquea applies an appropriate Lyapunov function. First one shows the stability of subcritical networks for nonidling disciplines, obtains uniform bounds on the tails of marginal distributions of the equilibria for families of such networks, they are used to show the relative compactness of the marginal distributions. The uniform bounds and relative compactness are important tools for the investigation of equilibria distributions for different service disciplines. There is presented a family of subcritical mean field networks where the service discipline is chosen so that the equilibria have much larger workload than the corresponding M/G/1 queues, this shows that JSQ rule does not always provides efficient service of jobs.