zbMATH — the first resource for mathematics

Join the shortest queue: Stability and exact asymptotics. (English) Zbl 1016.60078
This paper deals with the stability of a network serving a patchwork of overlapping regions where customers from a local region are assigned to a collection of local servers. These customers join the queue of the local server with the shortest queue of waiting requests. The authors describe how the backlog in the network overloads. It is done in the simple case of two servers each of which receives a dedicated stream of customers in addition to requests from a stream of smart customers who join the shorter. There are three distinct ways the backlog can overload, namely: unpooled, strongly pooled, weakly pooled cases. The emphasis of the results here is on the sharp asymptotics, not rough asymptotics as in large deviations. Moreover, the limiting distributions are for the unscaled process, not for the fluid limit as in the large deviation theory. In the strongly poooled case, for instance, the authors give the limiting distribution of the difference between the two queues as the backlog grows. They also give the exact asymptotics of the mean time until overload.

60K25 Queueing theory (aspects of probability theory)
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)