Martingales and buffer overflow for the symmetric shortest queue model

Danielle Tibi ()
Additional contact information
Danielle Tibi: LPSM - Université Paris Diderot, Bâtiment Sophie Germain

Queueing Systems: Theory and Applications, 2019, vol. 93, issue 1, No 7, 153-190

Abstract: Abstract A variant of the standard symmetric system of two parallel queues under the join-the-shortest-queue policy is introduced. Here, the shortest queue has service rate $$\mu _1$$ μ 1 , while the longest queue has rate $$\mu _2$$ μ 2 , where $$\mu _1 + \mu _2 = 1$$ μ 1 + μ 2 = 1 . In the case of equality, both queues are served at rate 1 / 2. Each queue has capacity K, which may be finite or infinite, and the global Poisson arrival rate is $$\rho $$ ρ . Couplings show that, as $$\mu _2$$ μ 2 varies, the model is totally ordered, in terms of both total number N(t) of customers in the system and longest queue length. The two extreme cases $$\mu _2= 0$$ μ 2 = 0 and $$\mu _2= 1$$ μ 2 = 1 then provide simple stochastic bounds for N(t) for arbitrary $$\mu _2$$ μ 2 . The ordering partially extends to the enlarged model in which, whenever the shortest queue is empty, the idle server at that queue helps—or on the contrary disturbs—the other server. The previous bounds remain valid. In the extended setup, different martingales are next built from the infinite capacity process. Those lead to simple explicit formulations of the means and Laplace transforms of the hitting time of saturation, for the process with finite K started from any initial state. Asymptotics are then derived, as K gets large. Using one particular mean time, the stationary blocking probability is explicitly obtained, extending the result by Dester et al. regarding the standard symmetric model. Finally, the joint distribution of the time and state of the system at the first queue-length equality is expressed as a function of the inverse of a simple explicit matrix.

Keywords: Shortest queue; Martingales; Hitting times; Finite capacity; Blocking probability; 60J27; 60K25 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-019-09628-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:93:y:2019:i:1:d:10.1007_s11134-019-09628-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-019-09628-9

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().