Approximated Transient Queue Length and Waiting Time Distributions via Steady State Analysis

Abstract

We propose a method to approximate the transient performance measures of a discrete time queueing system via a steady state analysis. The main idea is to approximate the system state at time slot t or on the n-th arrival–-depending on whether we are studying the transient queue length or waiting time distribution–-by the system state after a negative binomially distributed number of slots or arrivals. By increasing the number of phases k of the negative binomial distribution, an accurate approximation of the transient distribution of interest can be obtained.

In order to efficiently obtain the system state after a negative binomially distributed number of slots or arrivals, we introduce so-called reset Markov chains, by inserting reset events into the evolution of the queueing system under consideration. When computing the steady state vector of such a reset Markov chain, we exploit the block triangular block Toeplitz structure of the transition matrices involved and we directly obtain the approximation from its steady state vector. The concept of the reset Markov chains can be applied to a broad class of queueing systems and is demonstrated in full detail on a discrete-time queue with Markovian arrivals and phase-type services (i.e., the D-MAP/PH/1 queue). We focus on the queue length distribution at time t and the waiting time distribution of the n-th customer. Other distributions, e.g., the amount of work left behind by the n-th customer, that can be acquired in a similar way, are briefly touched upon.

Using various numerical examples, it is shown that the method provides good to excellent approximations at low computational costs–-as opposed to a recursive algorithm or a numerical inversion of the Laplace transform or generating function involved–-offering new perspectives to the transient analysis of practical queueing systems.     

AN INFINITE-PHASE QUASI-BIRTH-AND-DEATH MODEL FOR THE NON-PREEMPTIVE PRIORITY M/PH/1 QUEUE

This paper considers a single server queue that handles arrivals from N classes of customers on a non-preemptive priority basis. Each of the N classes of customers features arrivals from a Poisson process at rate λ _i and class-dependent phase type service. To analyze the queue length and waiting time processes of this queue, we derive a matrix geometric solution for the stationary distribution of the underlying Markov chain. A defining characteristic of the paper is the fact that the number of distinct states represented within the sub-level is countably infinite, rather than finite as is usually assumed. Among the results we obtain in the two-priority case are tractable algorithms for the computation of both the joint distribution for the number of customers present and the marginal distribution of low-priority customers, and an explicit solution for the marginal distribution of the number of high-priority customers. This explicit solution can be expressed completely in terms of the arrival rates and parameters of the two service time distributions. These results are followed by algorithms for the stationary waiting time distributions for high- and low-priority customers. We then address the case of an arbitrary number of priority classes, which we solve by relating it to an equivalent three-priority queue. Numerical examples are also presented.     

Stationary distributions for a class of Markov-modulated tandem fluid queues

ABSTRACT

We consider a model consisting of two fluid queues driven by the same background continuous-time Markov chain, such that the rates of change of the fluid in the second queue depend on whether the first queue is empty or not: when the first queue is nonempty, the content of the second queue increases, and when the first queue is empty, the content of the second queue decreases.

We analyze the stationary distribution of this tandem model using operator-analytic methods. The various densities (or Laplace–Stieltjes transforms thereof) and probability masses involved in this stationary distribution are expressed in terms of the stationary distribution of some embedded process. To find the latter from the (known) transition kernel, we propose a numerical procedure based on discretization and truncation. For some examples we show the method works well, although its performance is clearly affected by the quality of these approximations, both in terms of accuracy and run time.     

Characterizing the BMAP/MAP/1 Departure Process via the ETAQA Truncation

Abstract

We propose a family of finite approximations for the departure process of a BMAP/MAP/1 queue. The departure process approximations are derived via an exact aggregate solution technique (called ETAQA) applied to M/G/1-type Markov processes. The proposed approximations are indexed by a parameter n(n > 1), which determines the size of the output model as n + 1 block levels of the M/G/1-type process. This output approximation preserves exactly the marginal distribution of the true departure process and the lag correlations of the interdeparture times up to lag n ? 2. Experimental results support the applicability of the proposed approximation in traffic-based decomposition of queueing networks.     

Stochastic monotonicity and comparability of Markov chains with block-monotone transition matrices and their applications to queueing systems

ABSTRACT

Motivated by various applications in queueing theory, this article is devoted to the stochastic monotonicity and comparability of Markov chains with block-monotone transition matrices. First, we introduce the notion of block-increasing convex order for probability vectors, and characterize the block-monotone matrices in the sense of the block-increasing order and block-increasing convex order. Second, we characterize the Markov chain with general transition matrix by martingale and provide a stochastic comparison of two block-monotone Markov chains under the two block-monotone orders. Third, the stochastic comparison results for the Markov chains corresponding to the discrete-time GI/G/1 queue with different service distributions under the two block-monotone orders are given, and the lower bound and upper bound of the Markov chain corresponding to the discrete-time GI/G/1 queue in the sense of the block-increasing convex order are found.     

A Spectral Method for a Nonpreemptive Priority BMAP/G/1 QUEUE

Abstract

In this paper we consider a nonpreemptive priority queue with two priority classes of customers. Customers arrive according to a batch Markovian arrival process (BMAP). In order to calculate the boundary vectors we propose a spectral method based on zeros of the determinant of a matrix function and the corresponding eigenvectors. It is proved that there are M zeros in a set Ω, where M is the size of the state space of the underlying Markov process. The zeros are calculated by the Durand-Kerner method, and the stationary joint probability of the numbers of customers of classes 1 and 2 at departures is derived by the inversion of the two-dimensional Fourier transform. For a numerical example, the stationary probability is calculated.     

An RG-Factorization Approach for a BMAP/M/1 Generalized Processor-Sharing Queue

ABSTRACT

In this paper, we study a BMAP/M/1 generalized processor-sharing queue. We propose an RG-factorization approach, which can be applied to a wider class of Markovian block-structured processor-sharing queues. We obtain the expressions for both the distribution of the stationary queue length and the Laplace transform of the sojourn time distribution. From these two expressions, we develop an algorithm to compute the mean and variance of the sojourn time approximately.     

A MARKOV MODULATED FLUID QUEUE WITH BATCH ARRIVALS AND PREEMPTIONS

We consider a preemptive priority fluid queue with two buffers for continuous fluid and batch fluid inputs. Those two types of fluids are governed by a Markov chain with a finite state space, called a background process, and the continuous fluid is preemptively processed over the batch fluid. The stationary joint distribution of the two buffer contents and the background state is obtained in terms of matrix transforms. Numerical computation algorithms are presented for various moments of the two buffer contents.     

Slowing time: Markov-modulated Brownian motions with a sticky boundary

We define a new family of stochastic processes called Markov modulated Brownian motions with a sticky boundary at zero. Intuitively, each process is a regulated Markov-modulated Brownian motion whose boundary behavior is modified to slow down at level zero.

To determine the stationary distribution of a sticky MMBM, we follow a Markov-regenerative approach similar to the one developed with great success in the context of quasi-birth-and-death processes and fluid queues. Our analysis also relies on recent work showing that Markov-modulated Brownian motions arise as limits of a parametrized family of fluid queues.     

The Waiting Time Distribution of a Type k Customer in a Discrete-Time MMAP[K]/PH[K]/c (c = 1, 2) Queue Using QBDs

Abstract

This paper presents an improved method to calculate the delay distribution of a type k customer in a first-come-first-serve (FCFS) discrete-time queueing system with multiple types of customers, where each type has different service requirements, and c servers, with c = 1, 2 (the MMAP[K]/PH[K]/c queue). The first algorithms to compute this delay distribution, using the GI/M/1 paradigm, were presented by Van Houdt and Blondia [Van Houdt, B.; Blondia, C. The delay distribution of a type k customer in a first come first served MMAP[K]/PH[K]/1 queue. J. Appl. Probab. 2002, 39 (1), 213–222; The waiting time distribution of a type k customer in a FCFS MMAP[K]/PH[K]/2 queue. Technical Report; 2002]. The two most limiting properties of these algorithms are: (i) the computation of the rate matrix R related to the GI/M/1 type Markov chain, (ii) the amount of memory needed to store the transition matrices A _l and B _l . In this paper we demonstrate that each of the three GI/M/1 type Markov chains used to develop the algorithms in the above articles can be reduced to a QBD with a block size which is only marginally larger than that of its corresponding GI/M/1 type Markov chain. As a result, the two major limiting factors of each of these algorithms are drastically reduced to computing the G matrix of the QBD and storing the 6 matrices that characterize the QBD. Moreover, these algorithms are easier to implement, especially for the system with c = 2 servers. We also include some numerical examples that further demonstrate the reduction in computational resources.     

Response Time Distribution in a D-MAP/PH/1 Queue with General Customer Impatience

ABSTRACT

This paper presents two methods to calculate the response time distribution of impatient customers in a discrete-time queue with Markovian arrivals and phase-type services, in which the customers’ patience is generally distributed (i.e., the D-MAP/PH/1 queue). The first approach uses a GI/M/1 type Markov chain and may be regarded as a generalization of the procedure presented in Van Houdt ^[14] Van Houdt , B. ; Lenin , R. B. ; Blondia , C. Delay distribution of (im)patient customers in a discrete time D-MAP/PH/1 queue with age dependent service times Queueing Systems and Applications 2003 , 45 1 , 59 – 73 . [CROSSREF]  [Google Scholar] for the D-MAP/PH/1 queue, where every customer has the same amount of patience. The key construction in order to obtain the response time distribution is to set up a Markov chain based on the age of the customer being served, together with the state of the D-MAP process immediately after the arrival of this customer. As a by-product, we can also easily obtain the queue length distribution from the steady state of this Markov chain.

We consider three different situations: (i) customers leave the system due to impatience regardless of whether they are being served or not, possibly wasting some service capacity, (ii) a customer is only allowed to enter the server if he is able to complete his service before reaching his critical age and (iii) customers become patient as soon as they are allowed to enter the server. In the second part of the paper, we reduce the GI/M/1 type Markov chain to a Quasi-Birth-Death (QBD) process. As a result, the time needed, in general, to calculate the response time distribution is reduced significantly, while only a relatively small amount of additional memory is needed in comparison with the GI/M/1 approach. We also include some numerical examples in which we apply the procedures being discussed.     

ANALYSIS OF A GI/G Y /1 SYSTEM IN DISCRETE-TIME

ABSTRACT

We consider a class of single server queueing systems in which customers arrive singly and service is provided in batches, depending on the number of customers waiting when the server becomes free. Service is independent of the batch size. This system could also be considered as a batch service queue in which a server visits the queue at arbitrary times and collects a batch of waiting customers for service, or waits for a customer to arrive if there are no waiting customers. A waiting server immediately collects and processes the first arriving customer. The system is considered in discrete time. The interarrival times of customers and the inter-visit times of the server, which we call the service time, have general distributions and are represented as remaining time Markov chains. We analyze this system using the matrix-geometric method and show that the resulting R matrix can be determined explicitly in some special cases and the stationary distributions are known semi-explicitly in some other special cases.     

Transient analysis of a finite source discrete-time queueing system using homogeneous Markov system with state size capacities (HMS/c)

Abstract

In this article, a finite source discrete-time queueing system is modeled as a discrete-time homogeneous Markov system with finite state size capacities (HMS/c) and transition priorities. This Markov system is comprised of three states. The first state of the HMS/c corresponds to the source and the second one to the state with the servers. The second state has a finite capacity which corresponds to the number of servers. The members of the system which can not enter the second state, due to its finite capacity, enter the third state which represents the system's queue. In order to examine the variability of the state sizes recursive formulae for their factorial and mixed factorial moments are derived in matrix form. As a consequence the probability mass function of each state size can be evaluated. Also the expected time in queue is computed by means of the interval transition probabilities. The theoretical results are illustrated by a numerical example.     

ALGORITHMS FOR RETURN PROBABILITIES FOR STOCHASTIC FLUID FLOWS

Abstract

We consider several known algorithms and introduce some new algorithms that can be used to calculate the probability of return to the initial level in the Markov stochastic fluid flow model. We give the physical interpretations of these algorithms within the fluid flow environment. The rates of convergence are explained in terms of the physical properties of the fluid flow processes. We compare these algorithms with respect to the number of iterations required and their complexity. The performance of the algorithms depends on the nature of the process considered in the analysis. We illustrate this with examples and give appropriate recommendations.     

Transient Analysis of Averaged Queue Length in Markovian Queues

Abstract

We consider a Markovian queue and its associated exponentially averaged length. The set of partial differential equations satisfied by the joint distribution of the queue and the averaged queue length is given. We obtain a recursive expression for the moments of the averaged queue length, and develop a stable algorithm to compute them. These results are illustrated through numerical examples.     

A Tandem Queue with Server Slow-Down and Blocking

Abstract

We consider two variants of a two-station tandem network with blocking. In both variants the first server ceases to work when the queue length at the second station hits a ‘blocking threshold.’ In addition, in variant 2 the first server decreases its service rate when the second queue exceeds a ‘slow-down threshold, ’ which is smaller than the blocking level. In both variants the arrival process is Poisson and the service times at both stations are exponentially distributed. Note, however, that in case of slow-downs, server 1 works at a high rate, a slow rate, or not at all, depending on whether the second queue is below or above the slow-down threshold or at the blocking threshold, respectively. For variant 1, i.e., only blocking, we concentrate on the geometric decay rate of the number of jobs in the first buffer and prove that for increasing blocking thresholds the sequence of decay rates decreases monotonically and at least geometrically fast to max{ρ₁, ρ₂}, where ρ _i is the load at server i. The methods used in the proof also allow us to clarify the asymptotic queue length distribution at the second station. Then we generalize the analysis to variant 2, i.e., slow-down and blocking, and establish analogous results.     

Mixing and moments properties of a non-stationary copula-based Markov process

Abstract

We provide conditions under which a non-stationary copula-based Markov process is geometric β-mixing and geometric ρ-mixing. Our results generalize some results of Beare who considers the stationary case. As a particular case we introduce a stochastic process, that we call convolution-based Markov process, whose construction is obtained by using the C-convolution operator which allows the increments to be dependent. Within this subclass of processes we characterize a modified version of the standard random walk where copulas and marginal distributions involved are in the same elliptical family. We study mixing and moments properties to identify the differences compared to the standard case.     

An (s,k, S) fluid inventory model with exponential leadtimes and order cancellations

We consider a stochastic fluid inventory model based on a (s, k, S) policy. The content level W = {W(t): t ≥ 0} increases or decreases according to a fluid-flow rate modulated by an n-state continuous time Markov chain (CTMC). W starts at W(0) = S; whenever W(t) drops to level s, an order is placed to take the inventory back to level S, which the supplier will carry out after an exponential leadtime. However, if during the leadtime the content level reaches k, the order is suppressed. We obtain explicit formulas for the expected discounted costs. The derivations are based on the optional sampling theorem (OST) to the multidimensional martingale and on fluid flow techniques.     

A transient analysis of Markov fluid models with jumps

In this paper, we consider Markov fluid models with jumps which are useful for e.g. insurance risk modeling and the performance analysis of high-speed data networks. Recently, Ahn and Ramaswami [Ahn, S. & Ramaswami, V. (2004). Transient analysis of fluid flow models via stochastic coupling to a queue. Stochastic Models, 20 (1) 71–101] provided a transient analysis of the Markov modulated fluid flow model using stochastic coupling to a queueing model. Here we extend their results and provide a transient analysis of Markov fluid models with jumps. We also present some numerical examples.