Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions

• 成果类型: Article
• 署名作者: Bertsimas, D; Gamarnik, D; Tsitsiklis, JN
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); International Business Machines (IBM); IBM USA; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2001
• 页码: 1384-1428
• 关键词: queuing-networks; scheduling policies; STABILITY; bounds

摘要

We study the distribution of steady-state queue lengths in multiclass queueing networks under a stable policy. We propose a general methodology based on Lyapunov functions for the performance analysis of infinite state Markov chains and apply it specifically to Markovian multiclass queueing networks. We establish a deeper connection between stability and performance of such networks by showing that if there exist linear or piece-wise linear Lapunov functions that show stability, then these Lyapunov functions can be used to establish geometric-type lower and upper bounds on the tail probabilities, and thus bounds on the expectation of the queue lengths. As an example of our results, for a reentrant line queueing network with two processing stations operating under a work-conserving policy, we show that E[L] = O(1/(1-rho*)(2)) where L is the total number of customers in the system, and rho* is the maximal actual or virtual traffic intensity in the network. In a Markovian setting, this extends a recent result by Dai and Vande Vate, which states that a reentrant line queueing network with two stations is globally stable if rho* < 1. We also present several results on the performance of multiclass queueing networks operating under general Markovian and, in particular, priority policies. The results in this paper are the first that establish explicit geometric-type upper and lower bounds on tail probabilities of queue lengths for networks of such generality. Previous results provide numerical bounds and only on the expectation, not the distribution, of queue lengths.