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

该项目的一个主要主题是开发一种理论方法和有用的工具，用于研究出现在排队网络中的固定分布的不对称尾部行为，并将其应用于各种模型以查看其性能。除特殊案例（所谓的产品形式网络）外，该不对称问题非常困难。它们通常是通过大型出发理论研究的。但是，该理论在排队网络中被限制。此外，它仅提供其衰减的命令。在该研究项目中，我们对更详细的信息感兴趣，特别是在轻尾假设下的几何衰减对服务时间分布。我们开始猜测典型排队网络（如广义杰克逊网络）的不对称行为。这些猜想得到了我们自己和其他一些猜想的部分验证。但是，它们通常很难验证。因此，我们首先使用反思……更多TED Markov加法过程来制定衰减率问题。我们将此称为Markov添加剂方法，嗨，这个公式，我们选择了感兴趣的特征作为附加组件，并将所有其他信息都放在背景状态中。由于网络状态是多维的，因此该特征沿给定方向采用值，以使其具有一维。通常，特征是无负的，并且在原点周围具有复杂的状态过渡，而它远离原点时具有一定的均匀添加剂结构。因此，在许多情况下，我们可以将它们作为马尔可夫添加剂过程。通过这种方式，我们具有反射的马尔可夫添加剂过程。由于我们将所有信息放在了感兴趣的特征之外，因此背景状态空间通常是无限的。这是一个与排队文献中研究的相应过程不同的困难方面。稍后通常假设有限的背景状态空间。我们使用马尔可夫添加剂过程中的维纳·霍普（Wiener-Hope）分解来克服这一困难。然后，我们为固定尾巴得出足够的条件。具有几何术语的不对称衰变特征的概率，并识别该术语的预成分。在这里，我们将反射的马尔可夫添加剂过程的固定分布扭曲，并应用Markov Renewal定理以获取几何衰减率和相应的预取子。我们将这些结果应用于排队及其网络。特别是，我们在三个模型上发现了有趣的不对称行为，这是一个带有截短的缓冲区的两个节点杰克逊网络，两个平行的队列，其中到达客户选择最短的队列，一个有限的缓冲系统，其中到达和服务时间由有限的状态Markov链控制。例如，使用基本模型参数，例如到达和服务速率以及路由可能性，我们表征了无限队列的固定尾尾概率的限制衰减率，而另一个队列的截断级别变大。这揭示了极限衰减率的意外行为。我们还研究流体队列及其网络。这些研究有助于开发马尔可夫添加剂方法。较少的