Performance of Multiclass Markovian Queueing Networks Via Piecewise Linear Lyapunov Functions
Performance of Multiclass Markovian Queueing Networks Via Piecewise Linear Lyapunov Functions
复制标题
通过分段线性 Lyapunov 函数的多类马尔可夫排队网络的性能
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. Tsitsiklis
中科院分区：
文献类型：
--
作者：
D. Bertsimas;D. Gamarnik;J. Tsitsiklis
在稳定的政策下维护网络。我们提出了一种基于李雅普诺夫函数的无限状态马尔可夫链的性能分析的一般方法，并将其具体应用到马尔可夫多类决策网络。我们建立一个更深层次的连接，这样的网络的稳定性和性能表明，如果存在线性和分段线性李雅普诺夫函数，表现出稳定性，那么这些李雅普诺夫函数可以用来建立几何型的下限和上限的尾部概率，从而对期望的队列长度的界限。作为我们结果的一个例子，对于一个具有两个加工站的可重入排队网络，我们在工作守恒策略下，
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 and piecewise linear Lyapunov 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