Fundamental research for performance evaluation of queueing networks

排队网络性能评估基础研究

基本信息

批准号：
13680532
负责人：
MIYAZAWA Masakiyo
金额：
$ 2.3万
依托单位：
Tokyo University of Science
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2004
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680532/
关键词：
Queueing network Decay rate of the tail probability Markov additive process Wiener-Hopf factorization Fluid queue Shortest queue discipline Buffer truncation in a network Loss probability of finite queues 国際研究交流カナダ:ポーランド GI G 1形式待

项目摘要

A main subject of this project is to develop a theoretical method and useful tools for studying asymptotic tail behaviors of the stationary distributions that appear in queueing networks, and to apply them to various models to see their performance. Except for special cases, so called product form networks, this asymptotic problem is known to be very hard. They are usually studied by the large deviation theory. However, this theory is limited in use for queueing networks. Furthermore, it only provides the orders of their decays. In this research project, we are interested in more detailed information, in particular, the geometric decay under the light tail assumptions on service time distributions.We start to conjecture asymptotic behaviors of typical queueing networks such as the generalized Jackson networks. These conjectures are partially verified by ourselves and some others. However, they are generally very hard to verify. So, we first formulate the decay rate problem using reflec … More ted Markov additive processes. We term this a Markov additive approach, hi this formulation, we choose the characteristic of interest as an additive component and put all the other information into background states. Since the network states are multidimensional, this characteristic takes values along a given direction so that it is one-dimensional. Usually, the characteristic is nonnegative and has complicated state transitions around the origin, while it has certain uniform additive structure when it is away from the origin. Hence, we can formulate them as a Markov additive process in many cases.In this way, we have the reflected Markov additive process. Since we put all the information except for the characteristics of interest, the background state space is usually infinite. This is a difficult aspect different from the corresponding processes studied in the queueing literature. The latter usually assume the finite background state spaces. We overcome this difficulty using the Wiener-Hope factorization on a Markov additive process. We then derive sufficient conditions for the stationary tail. probabilities of the characteristic to asymptotically decay with a geometric term, and identify a prefactor of the term. Here, we twist the stationary distribution of the reflected Markov additive process provided it exists, and apply the Markov renewal theorem to get the geometric decay rate and the corresponding prefactor.We apply these results to queues and their networks. In particular, we found interesting asymptotic behaviors on three models, a two node Jackson network with a truncated buffer, two parallel queue in which arriving customers choose the shortest queue, a finite buffer system in which arrival and service times are controlled by a finite state Markov chain. For example, using basic model parameters such as arrival and service rates and routing probabilities, we characterize the limiting decay rate of the stationary tail probability of the unlimited queue when the truncation level of the other queue gets large. This reveals unexpected behaviors of the limiting decay rate. We also studies fluid queues and their networks. These studies have contributed to develop the Markov additive approach. Less

该项目的一个主要主题是开发一种理论方法和有用的工具来研究排队网络中出现的平稳分布的渐近尾部行为，并将其应用于各种模型以查看其性能（特殊情况除外），即所谓的乘积。众所周知，这种渐近问题非常困难，但该理论在排队网络中的应用受到限制。，我们感兴趣的是更多详细信息，特别是服务时间分布的轻尾假设下的几何衰减。我们开始推测典型排队网络（例如广义杰克逊网络）的渐近行为，这些猜想已被我们自己和其他人部分验证。通常很难验证。因此，我们首先使用反射马尔可夫加法过程来制定衰减率问题，我们将其称为马尔可夫加法方法，在这个公式中，我们选择感兴趣的特征作为加法成分，并将所有特征放入其中。由于网络状态是多维的，因此该特征沿给定方向取值，因此它是一维的，通常该特征是非负的，并且在原点周围有复杂的状态转换。因此，在许多情况下，我们可以将它们表示为马尔可夫加性过程。这样，我们就得到了反映的马尔可夫加性过程，因为我们把除了的特征之外的所有信息都包含在内。有趣的是，背景状态空间通常是无限的，这是一个困难。与排队文献中研究的相应过程不同，后者通常假设有限的背景状态空间，然后我们使用马尔可夫加性过程的维纳-霍普分解来克服这一困难。用几何项进行渐近衰减的特征，并确定该项的前因子在这里，我们扭曲反射马尔可夫加性过程的平稳分布（如果它存在），并应用马尔可夫更新定理来获得几何衰减率和。我们将这些结果应用于队列及其网络，特别是，我们在三个模型上发现了有趣的渐近行为：带有截断缓冲区的两节点 Jackson 网络、两个并行队列（其中到达的客户选择最短队列）、一个有限队列。例如，使用到达率和服务率以及路由概率等基本模型参数，我们刻画了无限队列的平稳尾部概率的极限衰减率。这其他队列的截断水平变大。我们还研究了流体队列及其网络，这些研究有助于开发马尔可夫加性方法。