Stationary analysis of the shortest queue problem

Abstract : A simple analytical solution is proposed for the stationary loss system of two parallel queues with finite capacity K, in which new customers join the shortest queue, or one of the two with equal probability if their lengths are equal. The arrival process is Poisson, service times at each queue have exponential distributions with the same parameter, and both queues have equal capacity. Using standard generating function arguments, a simple expression for the blocking probability is derived, which as far as we know is original. Using coupling arguments and explicit formulas, comparisons with related loss systems are then provided. Bounds are similarly obtained for the average total number of customers, with the stationary distribution explicitly determined on {K,…,2K}, and elsewhere upper bounded. Furthermore, from the balance equations, all stationary probabilities are obtained as explicit combinations of their values at states (0,k) for 0≤k≤K. These expressions extend to the infinite capacity and asymmetric cases, i.e., when the queues have different service rates. For the initial symmetric finite capacity model, the stationary probabilities of states (0,k) can be obtained recursively from the blocking probability. In the other cases, they are implicitly determined through a functional equation that characterizes their generating function. The whole approach shows that the stationary distribution of the infinite capacity symmetric process is the limit of the corresponding finite capacity distributions. For the infinite capacity symmetric model, we provide an elementary proof of a result by Cohen which gives the solution of the functional equation in terms of an infinite product with explicit zeroes and poles.
Type de document :
Article dans une revue
Queueing Systems, Springer Verlag, 2017, 87 (3-4), pp.211-243. 〈10.1007/s11134-017-9556-8〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01666312
Contributeur : Brigitte Briot <>
Soumis le : lundi 18 décembre 2017 - 11:13:53
Dernière modification le : jeudi 26 avril 2018 - 10:28:47

Lien texte intégral

Identifiants

Collections

Citation

Plinio S. Dester, Christine Fricker, Danielle Tibi. Stationary analysis of the shortest queue problem. Queueing Systems, Springer Verlag, 2017, 87 (3-4), pp.211-243. 〈10.1007/s11134-017-9556-8〉. 〈hal-01666312〉

Partager

Métriques

Consultations de la notice

85