离散时间排队MAP/PH/3

本文研究具有马尔可夫到达过程的离散时间排队MAP/PH/3,系统中有三个服务台,每个服务台对顾客的服务时间均服从位相型分布。运用矩阵几何解的理论,我们给出了系统平稳的充要条件和系统的稳态队长分布。同时我们也给出了到达顾客所见队长分布和平均等待时间。     

A numerically efficient method for the MAP/D/1/K queue via rational approximations

The Markovian Arrival Process (MAP), which contains the Markov Modulated Poisson Process (MMPP) and the Phase-Type (PH) renewal processes as special cases, is a convenient traffic model for use in the performance analysis of Asynchronous Transfer Mode (ATM) networks. In ATM networks, packets are of fixed length and the buffering memory in switching nodes is limited to a finite numberK of cells. These motivate us to study the MAP/D/1/K queue. We present an algorithm to compute the stationary virtual waiting time distribution for the MAP/D/1/K queue via rational approximations for the deterministic service time distribution in transform domain. These approximations include the well-known Erlang distributions and the Padé approximations that we propose. Using these approximations, the solution for the queueing system is shown to reduce to the solution of a linear differential equation with suitable boundary conditions. The proposed algorithm has a computational complexity independent of the queue storage capacityK. We show through numerical examples that, the idea of using Padé approximations for the MAP/D/1/K queue can yield very high accuracy with tractable computational load even in the case of large queue capacities.This work was done when the author was with the Bilkent University, Ankara, Turkey and the research was supported by TÜBITAK under Grant No. EEEAG-93.     

Distribution of spatial requirements for a MAP/G/1 queue when space and service times are dependent

In this paper, we consider a MAP/G/1 queue in which each customer arrives with a service and a space requirement, which could be dependent. However, the space and service requirements of different customers are assumed to be independent. Each customer occupies its space requirement in a buffer until it has completely received its service, at which time, it relinquishes the space it occupied. We study and solve the problem of finding the steady-state distribution of the total space requirement of all customers present in the system. In the process of doing so, we also generalize the solution of the MAP/G/1 queue and find the time-average joint distribution of the queue-length, the state of the arrival process and the elapsed service time, conditioned on the server being busy. This problem has applications to the design of buffer requirements for a computer or communication system.     

Analysis of the MAP/PH/1/K queue with service control

We consider a finite capacity queue with Markovian arrivals, in which the service rates are controlled by two pre-determined thresholds, M and N. The service rate is increased when the buffer size exceeds N and then brought back to normal service rate when the buffer size drops to M. The normal and fast service times are both assumed to be of phase type with representations (β, S), and β θS), respectively, where θ>1. For this queueing model, steady state analysis is performed. The server duration in normal as well as fast periods is shown to be of phase type. The departure process is modelled as a MAP and the parameter matrices of the MAP are identified. Efficient algorithms for computing system performance measures are presented. We also discuss an optimization problem and present an efficient algorithm for arriving at an optimal solution. Some numerical examples are discussed.     

An MAP/G/1 G-queues with preemptive resume and multiple vacations

In this paper, we consider an MAP/G/1 G-queues with possible preemptive resume service discipline and multiple vacations wherein the arrival process of negative customers is Markovian arrival process (MAP). The arrival of a negative customer may remove the customer being in service. The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service and vacation times are arbitrarily distributed. We obtain the queue length distributions with the method of supplementary variables, combined with the matrix-analytic method and censoring technique. We also obtain the mean of the busy period based on the renewal theory. Finally we provide expressions for a special case.     

Tail asymptotics for the fundamental period in the MAP/G/1 queue

This paper studies the tail behavior of the fundamental period in the MAP/G/1 queue. We prove that if the service time distribution has a regularly varying tail, then the fundamental period distribution in the MAP/G/1 queue has also regularly varying tail, and vice versa, by finding an explicit expression for the asymptotics of the tail of the fundamental period in terms of the tail of the service time distribution. Our main result with the matrix analytic proof is a natural extension of the result in (de Meyer and Teugels, J. Appl. Probab. 17: 802–813, 1980) on the M/G/1 queue where techniques rely heavily on analytic expressions of relevant functions. I.-S. Wee’s research was supported by the Korea Research Foundation Grant KRF 2003-070-00008.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Analysis of the finite source MAP/PH/N retrial G-queue operating in a random environment

Finite source retrial G-queues are good mathematical models of communication systems and networks, so their investigation is important for theory and applications. In this paper, we analyze the MAP/PH/N retrial queue with finite number of sources and MAP arrivals of negative customers operating in a finite state Markovian random environment. The arrival of a negative customer with equal probability goes to any busy server to remove the customer being in service. The multi-dimensional Markov chain describing the behavior of the system is investigated. The algorithms for calculating the stationary state probabilities are elaborated. Main performance measures are obtained. Illustrative numerical examples are presented.     

On the M/G/1 queue with feedback and optional server vacations based on a single vacation policy

We study a single server queue with batch arrivals and general (arbitrary) service time distribution. The server provides service to customers, one by one, on a first come, first served basis. Just after completion of his service, a customer may leave the system or may opt to repeat his service, in which case this customer rejoins the queue. Further, just after completion of a customer's service the server may take a vacation of random length or may opt to continue staying in the system to serve the next customer. We obtain steady state results in explicit and closed form in terms of the probability generating functions for the number of customers in the queue, the average number of customers and the average waiting time in the queue. Some special cases of interest are discussed and some known results have been derived. A numerical illustration is provided.     

Fitting correlated arrival and service times and related queueing performance

In this paper, we consider a queue where the inter-arrival times are correlated and, additionally, service times are also correlated with inter-arrival times. We show that the resulting model can be interpreted as an MMAP[K]/PH[K]/1 queue for which matrix geometric solution algorithms are available. The major result of this paper is the presentation of approaches to fit the parameters of the model, namely the MMAP, the PH distribution and the parameters introducing correlation between inter-arrival and service times, according to some trace of inter-arrival and corresponding service times. Two different algorithms are presented. The first algorithm is based on available methods to compute a MAP from the inter-arrival times and a PH distribution from the service times. Afterward, the correlation between inter-arrival and service times is integrated by solving a quadratic programming problem over some joint moments. The second algorithm is of the expectation maximization type and computes all parameters of the MAP and the PH distribution in an iterative way. It is shown that both algorithms yield sufficiently accurate results with an acceptable effort.     

On the BMAP/G/1 G-queues with second optional service and multiple vacations

This paper deals with an BMAP/G/1 G-queues with second optional service and multiple vacations. Arrivals of positive customers and negative customers follow a batch Markovian arrival process (BMAP) and Markovian arrival process (MAP), respectively. After completion of the essential service of a customer, it may go for a second phase of service. The arrival of a negative customer removes the customer being in service. The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. By using the supplementary variables method and the censoring technique, we obtain the queue length distributions. We obtain the mean of the busy period based on the renewal theory.     

A Tandem Queue with Blocking and Markovian Arrival Process

Queueing networks with blocking have proved useful in modelling of data communications and production lines. We study such a network consisting of a sequence of two service stations with an infinite queue allowed before the first station and no intermediate queue allowed between them. This restriction results in the blocking of the first station whenever a unit having completed its service in that station cannot enter into the second one due to the presence of another unit there. The input of units to the network is the MAP (Markovian Arrival Process). At the first station, service requirements are of phase type whereas service times at the second station are arbitrarily distributed. The focus is on the embedded process at departures. The essential tool in our analysis is the general theory on Markov renewal processes of M/G/1-type.     

M/G/1/N vacation model with varying E-limited service discipline

We define and analyze anM/G/1/N vacation model that uses a service discipline that we call theE-limited with limit variation discipline. According to this discipline, the server provides service until either the system is emptied (i.e. exhausted) or a randomly chosen limit ofl customers has been served. The server then goes on a vacation before returning to service the queue again. The queue length distribution and the Laplace-Stieltjes transforms of the waiting time, busy period and cycle time distributions are found. Further, an expression for the mean waiting time is developed. Several previously analyzed service disciplines, including Bernoulli scheduling, nonexhaustive service and limited service, are special cases of the general varying limit discipline that is analyzed in this paper.     

An M/G/1 Queueing Model with Gated Random Order of Service

We analyse an M/G/1 queueing model with gated random order of service. In this service discipline there are a waiting room, in which arriving customers are collected, and a service queue. Each time the service queue becomes empty, all customers in the waiting room are put instantaneously and in random order into the service queue. The service times of customers are generally distributed with finite mean. We derive various bivariate steady-state probabilities and the bivariate Laplace–Stieltjes transform (LST) of the joint distribution of the sojourn times in the waiting room and the service queue. The derivation follows the line of reasoning of Avi-Itzhak and Halfin [4]. As a by-product, we obtain the joint sojourn times LST for several other gated service disciplines.     

带止步与中途退出策略的M~x/M/1/N单重工作休假排队系统

研究了带有止步和中途退出的M~x/M/1/N单重工作休假排队系统.顾客成批到达,到达后每批中的顾客,或者以概率b决定进入队列等待服务,或者以概率1-b止步(不进入系统).顾客进入系统后可能因为等待的不耐烦而在没有接受服务的情况下离开系统(中途退出).系统中一旦没有顾客,服务员立即进入单重工作休假.首先,利用马尔科夫过程理论建立了系统稳态概率满足的方程组.其次利用矩阵解法求出了稳态概率的矩阵解并得到了系统的平均队长、平均等待队长以及顾客的平均消失概率等性能指标.最后通过数值例子分析了工作休假时的低服务率η和休假率θ这两个参数对系统平均队长的影响.     

A MAP/G/1 Queue with Negative Customers

In this paper, we consider a MAP/G/1 queue with MAP arrivals of negative customers, where there are two types of service times and two classes of removal rules: the RCA and RCH, as introduced in section 2. We provide an approach for analyzing the system. This approach is based on the classical supplementary variable method, combined with the matrix-analytic method and the censoring technique. By using this approach, we are able to relate the boundary conditions of the system of differential equations to a Markov chain of GI/G/1 type or a Markov renewal process of GI/G/1 type. This leads to a solution of the boundary equations, which is crucial for solving the system of differential equations. We also provide expressions for the distributions of stationary queue length and virtual sojourn time, and the Laplace transform of the busy period. Moreover, we provide an analysis for the asymptotics of the stationary queue length of the MAP/G/1 queues with and without negative customers.     

The Periodic BMAP/PH/c Queue

In queueing theory, most models are based on time-homogeneous arrival processes and service time distributions. However, in communication networks arrival rates and/or the service capacity usually vary periodically in time. In order to reflect this property accurately, one needs to examine periodic rather than homogeneous queues. In the present paper, the periodic BMAP/PH/c queue is analyzed. This queue has a periodic BMAP arrival process, which is defined in this paper, and phase-type service time distributions. As a Markovian queue, it can be analysed like an (inhomogeneous) Markov jump process. The transient distribution is derived by solving the Kolmogorov forward equations. Furthermore, a stability condition in terms of arrival and service rates is proven and for the case of stability, the asymptotic distribution is given explicitly. This turns out to be a periodic family of probability distributions. It is sketched how to analyze the periodic BMAP/M _t /c queue with periodically varying service rates by the same method.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

Geometric tail of queue length of low-priority customers in a nonpreemptive priority MAP/PH/1 queue

We consider a MAP/PH/1 queue with two priority classes and nonpreemptive discipline, focusing on the asymptotic behavior of the tail probability of queue length of low-priority customers. A sufficient condition under which this tail probability decays asymptotically geometrically is derived. Numerical methods are presented to verify this sufficient condition and to compute the decay rate of the tail probability.