Commuting Matrices in the Queue Length and Sojourn Time Analysis of MAP/MAP/1 Queues

Queues with Markovian arrival and service processes, i.e., MAP/MAP/1 queues, have been useful in the analysis of computer and communication systems and different representations for their stationary sojourn time and queue length distribution have been derived. More specifically, the class of MAP/MAP/1 queues lies at the intersection of the class of QBD queues and the class of semi-Markovian queues. While QBD queues have a matrix exponential representation for their queue length and sojourn time distribution of order N and N², respectively, where N is the size of the background continuous time Markov chain, the reverse is true for a semi-Markovian queue. As the class of MAP/MAP/1 queues lies at the intersection, both the queue length and sojourn time distribution of a MAP/MAP/1 queue has an order N matrix exponential representation. The aim of this article is to understand why the order N² distributions of the sojourn time of a QBD queue and the queue length of a semi-Markovian queue can be reduced to an order N distribution in the specific case of a MAP/MAP/1 queue. We show that the key observation exists in establishing the commutativity of some fundamental matrices involved in the analysis of the MAP/MAP/1 queue.     

Sojourn time in an M/M/1 processor sharing queue with permanent customers

We explicitly compute the sojourn time distribution of an arbitrary customer in an M/M/1 processor sharing (PS) queue with permanent customers. We notably exhibit the orthogonal structure associated with this queuing system and we show how sieved Pollaczek polynomials and their associated orthogonality measure can be used to obtain an explicit representation for the complementary cumulative distribution function of the sojourn time of a customer. This explicit formula subsequently allows us to compute the two first moments of this random variable and to study the asymptotic behavior of its distribution. The most salient result is that the decay rate depends on the load of the system and the number K of permanent customers. When the load is above a certain threshold depending on K, the decay rate is identical to that of a regular M/M/1 PS queue.     

BMAP/G/1 Queue Under D-Policy: Queue Length Analysis

ABSTRACT

We study the queue length distribution of a queueing system with BMAP arrivals under D-policy. The idle server begins to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We derive the vector generating functions of the queue lengths both at a departure and at an arbitrary point of time. Mean queue lengths are derived and a numerical example is presented.     

Queue Length Analysis of MAP/G/1 Queue Under D-Policy

Abstract

We study the queue length distribution of a queueing system with MAP arrivals under D-policy. The idle server begins to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We derive the vector generating functions of the queue lengths both at a departure and at an arbitrary point of time. Mean queue lengths will be derived from these transform results. A numerical example is provided.     

Approximating M/G/1 Waiting Time Tail Probabilities

Abstract

We propose a new approximation formula for the waiting time tail probability of the M/G/1 queue with FIFO discipline and unlimited waiting space. The aim is to address the difficulty of obtaining good estimates when the tail probability has non-exponential asymptotics. We show that the waiting time tail probability can be expressed in terms of the waiting time tail probability of a notional M/G/1 queue with truncated service time distribution plus the tail probability of an extreme order statistic. The Cramér–Lundberg approximation is applied to approximate the tail probability of the notional queue. In essence, our technique extends the applicability of the Cramér–Lundberg approximation to cases where the standard Lundberg condition does not hold. We propose a simple moment-based technique for estimating the parameters of the approximation; numerical results demonstrate that our approximation can yield very good estimates over the whole range of the argument.     

The analysis of MX/M/1 queue with two-stage vacations policy

Abstract

In this article, we consider a batch arrival M^X/M/1 queue with two-stage vacations policy that comprises of single working vacation and multiple vacations, denoted by M^X/M/1/SWV?+?MV. Using the matrix analytic method, we derive the probability generating function (PGF) of the stationary system size and investigate the stochastic decomposition structure of stationary system size. Further, we obtain the Laplace–Stieltjes transform (LST) of stationary sojourn time of a customer by the first passage time analysis. At last, we illustrate the effects of various parameters on the performance measures numerically and graphically by some numerical examples.     

DECOMPOSITIONS OF THE QUEUE LENGTH DISTRIBUTIONS IN THE MAP/G/1 QUEUE UNDER MULTIPLE AND SINGLE VACATIONS WITH N-POLICY

In this paper, we establish an explicit form of matrix decompositions for the queue length distributions of the MAP/G/1 queues under multiple and single vacations with N-policy. We show that the vector generating function Y (z) of the queue length at an arbitrary time and X (z) at departures are decomposed into Y (z) = p _idle (z)ζ _Y (z) and X (z) = p _idle (z)ζ _X (z) where p _idle (z) is the vector generating function of the queue length at an arbitrary epoch at which the server is not in service, and ζ _Y (z) and ζ _X (z) are unidentified matrix generating functions.     

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.     

A Two‐Queue Polling Model with Regularly Varying Service and/or Switchover Times

Abstract

We consider the cyclic polling system with two queues. One queue is severed according to the exhaustive discipline, and the other queue is served according to the 1‐limited discipline. At least one of the service and/or switchover times has a regularly varying tail. We obtain the tail behavior of the waiting time distributions. When one of the service and/or switchover times has an infinite second moment, we derive the heavy‐traffic behavior of the waiting time distribution at the 1‐limited queue.     

Workload Process,Waiting Times,and Sojourn Times in a Discrete Time MMAP[K]/SM[K]/1/FCFS Queue

Abstract

In this paper, we study the total workload process and waiting times in a queueing system with multiple types of customers and a first-come-first-served service discipline. An M/G/1 type Markov chain, which is closely related to the total workload in the queueing system, is constructed. A method is developed for computing the steady state distribution of that Markov chain. Using that steady state distribution, the distributions of total workload, batch waiting times, and waiting times of individual types of customers are obtained. Compared to the GI/M/1 and QBD approaches for waiting times and sojourn times in discrete time queues, the dimension of the matrix blocks involved in the M/G/1 approach can be significantly smaller.     

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.     

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.     

The analysis of unreliable M[X]/G/1 queuing system with loss,vacation and two delays of verification

This paper considers an M^[X]/G/1 queue with breakdowns, repair, Bernoulli vacation, two delays and geometric loss. In this paper, a special attention is given to the limiting distribution of system states. We obtain simplified expressions for the Probability Generating Functions (PGFs) of the joint distribution of server state and system size. Some performance measures were derived from the analysis of the steady state probabilities. PGF of a departure point system size distribution is developed. Particular cases of the studied system were investigated. The effect of system parameters on the main performance measures are illustrated and discussed.     

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.     

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.     

Stationary analysis of a BMAP/R/1 queue with R-type multiple working vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple working vacation policy. The service time during a working vacation is generally distributed random variable which is independent of the service times during a normal busy period as well as the arrival process. Duration of service times during a normal busy period and duration of working vacation times follow the class of distributions whose Laplace-Stieltjes transforms are rational functions (R-type distributions). The service time during a normal busy period, working vacation time, and the service time during a working vacation are independent of each other as well as of the arrival process. If a working vacation terminates while service is going on for a customer at head of the queue in vacation mode then, the server switches to normal mode and the customer at head of the queue is entitled to receive a full service time in the normal busy period irrespective of the amount of service received by the customer at head of the queue during the previous working vacation period. We obtain system-length distributions at various epoch, such as post-departure, pre-arrival, arbitrary, and pre-service. The proposed analysis is based on the use of matrix-analytic procedure to obtain system-length distribution at post-departure epoch. Later, we use supplementary variable technique and simple algebraic manipulations to obtain system-length distribution at arbitrary epoch using the system-length distribution at post-departure epoch. Some important performance measures, such as mean system lengths and mean waiting time have been obtained. Finally, some numerical results have been presented in the form of tables and graphs to show the applicability of the results obtained in this article. The model has potential application in areas of computer and communication networks, such as ethernet passive optical network (EPON).     

Analysis of an unreliable MX/G1G2/1/repeated service queue with delayed repair under randomized vacation policy

Abstract

In this article we consider an unreliable M^X/G/1 queue with two types of general heterogeneous service and optional repeated service subject to server’s break down and delayed repair under randomized vacation policy. We assume that customer arrive to the system according to a compound Poisson process. The server provides two types of general heterogeneous service and a customer can choose either type of service before its service start. After the completion of either type of service, the customer has the further option to repeat the same type of service once again. While the server is working with any types of service or repeated service, it may breakdown at any instant. Further the concept of randomized vacation is also introduced. For this model, we first derive the joint distribution of state of the server and queue size by considering both elapsed and remaining time, which is one of the objective of this article. Next, we derive Laplace Stieltjes transform of busy period distribution. Finally, we obtain some important performance measure and reliability indices of this model.     

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.     

Estimation in M/Er /1 queueing systems

In this paper, the maximum likelihood estimates of the parameters for the M/E_r /1 queueing model are derived when the queue size at each departure point is observed. A numerical example is generated by simulating a finite Markov chain to illustrate the methodology for estimating the parameters with variable Erlang service time distribution. The problem of hypothesis testing and simultaneous Confidence regions of the parameter is also investigated.0