TY - JOUR

T1 - Non-product form equilibrium probabilities in a class of two-station closed reentrant queueing networks

AU - Kim, Woo sung

AU - Morrison, James R.

N1 - Funding Information:
Acknowledgements This work was supported in part by Korea Research Foundation (KRF) Grant 20110005696. The authors are grateful for the insightful and helpful comments of the reviewers and editorial team. The paper is much improved for their guidance.

PY - 2013/3

Y1 - 2013/3

N2 - While many single station queues possess explicit forms for their equilibrium probabilities, queueing networks are more problematic. Outside of the class of product form networks (e. g., Jackson, Kelly, and BCMP networks), one must resort to bounds, simulation, asymptotic studies or approximations. By focusing on a class of two-station closed reentrant queueing networks under the last buffer first served (LBFS) policy, we show that non-product form equilibrium probabilities can be obtained. When the number of customer classes in the network is five or fewer, explicit solutions can be obtained. Otherwise, we require the roots of a characteristic polynomial and a matrix inversion that depend only on the network topology. The approach relies on two key points. First, under LBFS, the state space can be reduced to four dimensions independent of the number of buffers in the system. Second, there is a sense of spatial causality in the global balance equations that can then be exploited. To our knowledge, these two-station closed reentrant queueing networks under LBFS represent the first class of queueing networks for which explicit non-product form equilibrium probabilities can be constructed (for five customer classes or less), the generic form of the equilibrium probabilities can be deduced and matrix analytic approaches can be applied. As discussed via example, there may be other networks for which related observations can be exploited.

AB - While many single station queues possess explicit forms for their equilibrium probabilities, queueing networks are more problematic. Outside of the class of product form networks (e. g., Jackson, Kelly, and BCMP networks), one must resort to bounds, simulation, asymptotic studies or approximations. By focusing on a class of two-station closed reentrant queueing networks under the last buffer first served (LBFS) policy, we show that non-product form equilibrium probabilities can be obtained. When the number of customer classes in the network is five or fewer, explicit solutions can be obtained. Otherwise, we require the roots of a characteristic polynomial and a matrix inversion that depend only on the network topology. The approach relies on two key points. First, under LBFS, the state space can be reduced to four dimensions independent of the number of buffers in the system. Second, there is a sense of spatial causality in the global balance equations that can then be exploited. To our knowledge, these two-station closed reentrant queueing networks under LBFS represent the first class of queueing networks for which explicit non-product form equilibrium probabilities can be constructed (for five customer classes or less), the generic form of the equilibrium probabilities can be deduced and matrix analytic approaches can be applied. As discussed via example, there may be other networks for which related observations can be exploited.

KW - Buffer priority policy

KW - Closed form solution

KW - Closed queueing networks

KW - Product form queueing networks

UR - http://www.scopus.com/inward/record.url?scp=84873525952&partnerID=8YFLogxK

U2 - 10.1007/s11134-012-9310-1

DO - 10.1007/s11134-012-9310-1

M3 - Article

AN - SCOPUS:84873525952

VL - 73

SP - 317

EP - 339

JO - Queueing Systems

JF - Queueing Systems

SN - 0257-0130

IS - 3

ER -