Join the shortest queue among $$k$$ parallel queues: tail asymptotics of its stationary distribution

摘要

We are concerned with an $M/M$-type join the shortest queue ($M/M$-JSQ forshort) with $k$ parallel queues for an arbitrary positive integer $k$, wherethe servers may be heterogeneous. We are interested in the tail asymptotic ofthe stationary distribution of this queueing model, provided the system isstable. We prove that this asymptotic for the minimum queue length is exactlygeometric, and its decay rate is the $k$-th power of the traffic intensity ofthe corresponding $k$ server queues with a single waiting line. For this, weuse two formulations, a quasi-birth-and-death (QBD for short) process and areflecting random walk on the boundary of the $k+1$-dimensional orthant. TheQBD process is typically used in the literature for studying the JSQ with 2parallel queues, but the random walk also plays a key roll in our arguments,which enables us to use the existing results on tail asymptotics for the QBDprocess.