Skip to Main content Skip to Navigation
Journal articles

Stationary analysis of the shortest queue problem

Plinio S. Dester 1 Christine Fricker 1, 2 Danielle Tibi 3
2 DYOGENE - Dynamics of Geometric Networks
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique - ENS Paris
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.
Document type :
Journal articles
Complete list of metadata
Contributor : Brigitte Briot Connect in order to contact the contributor
Submitted on : Monday, December 18, 2017 - 11:13:53 AM
Last modification on : Friday, January 21, 2022 - 3:18:30 AM

Links full text



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⟩



Les métriques sont temporairement indisponibles