The MM CPP/GE/c G-Queue: Sojourn Time Distribution

We obtain the sojourn time probability distribution function at equilibrium for a Markov modulated, multi-server, single queue with generalised exponential (GE) service time distribution and compound Poisson arrivals of both positive and negative customers. Such arrival processes can model both burstiness and correlated traffic and are well suited to models of ATM and other telecommunication networks. Negative customers remove (ordinary) customers in the queue and are similarly correlated and bursty. We consider both the cases where negative customers remove positive customers from the front and the end of the queue and, in the latter case, where a customer currently being served can and cannot be killed by a negative customer. These cases can model an unreliable server or load balancing respectively. The results are obtained as Laplace transforms and can be inverted numerically. The MM CPP/GE/c G-Queue therefore holds the promise of being a viable building block for the analysis of queues and queueing networks with bursty, correlated traffic, incorporating load balancing and node-failures, since the equilibrium behaviour of both queue lengths and response times can be determined in a tractable way.     

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.     

The GI/M/1 queue with exponential vacations

In this paper, we give a detailed analysis of the GI/M/1 queue with exhaustive service and multiple exponential vacation. We express the transition matrix of the imbedded Markov chain as a block-Jacobi form and give a matrix-geometric solution. The probability distribution of the queue length at arrival epochs is derived and is shown to decompose into the distribution of the sum of two independent random variables. In addition, we discuss the limiting behavior of the continuous time queue length processes and obtain the probability distributions for the waiting time and the busy period.     

The 1-Center and 1-Highway problem revisited

We consider a two-queue polling model in which customers upon arrival join the shorter of two queues. Customers arrive according to a Poisson process and the service times in both queues are independent and identically distributed random variables having the exponential distribution. The two-dimensional process of the numbers of customers at the queue where the server is and at the other queue is a two-dimensional Markov process. We derive its equilibrium distribution using two methodologies: the compensation approach and a reduction to a boundary value problem.     

Waiting time in a multi-server cutoff-priority gueue, and its application to an urban ambulance service

We consider a priority queue in steady state with N servers, two classes of customers, and a cutoff service discipline. Low priority arrivals are "cut off" (refused immediate service) and placed in a queue whenever N1 or more servers are busy, in order to keep N-N1 servers free for high priority arrivals. A Poisson arrival process for each class, and a common exponential service rate, are assumed. Two models are considered: one where high priority customers queue for service and one where they are lost if all servers are busy at an arrival epoch. Results are obtained for the probability of n servers busy, the expected low priority waiting time, and (in the case where high priority customers do not queue) the complete low priority waiting time distribution. The results are applied to determine the number of ambulances required in an urban fleet which serves both emergency calls and low priority patients transfers.     

Transient and Stationary Distributions for the GI/G/k Queue with Lebesgue-Dominated Inter-Arrival Time Distribution

In this paper, the multi-server queue with general service time distribution and Lebesgue-dominated iid inter-arival times is analyzed. This is done by introducing auxiliary variables for the remaining service times and then examining the embedded Markov chain at arrival instants. The concept of piecewise-deterministic Markov processes is applied to model the inter-arrival behaviour. It turns out that the transition probability kernel of the embedded Markov chain at arrival instants has the form of a lower Hessenberg matrix and hence admits an operator–geometric stationary distribution. Thus it is shown that matrix–analytical methods can be extended to provide a modeling tool even for the general multi-server queue.     

Sojourn Times in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 Processor Sharing Queue

We give in this paper an algorithm to compute the sojourn time distribution in the processor sharing, single server queue with Poisson arrivals and phase type distributed service times. In a first step, we establish the differential system governing the conditional sojourn times probability distributions in this queue, given the number of customers in the different phases of the PH distribution at the arrival instant of a customer. This differential system is then solved by using a uniformization procedure and an exponential of matrix. The proposed algorithm precisely consists of computing this exponential with a controlled accuracy. This algorithm is then used in practical cases to investigate the impact of the variability of service times on sojourn times and the validity of the so-called reduced service rate (RSR) approximation, when service times in the different phases are highly dissymmetrical. For two-stage PH distributions, we give conjectures on the limiting behavior in terms of an M/M/1 PS queue and provide numerical illustrative examples.This revised version was published online in June 2005 with corrected coverdate     

Analysis of a dynamic assignment of impatient customers to parallel queues

Consider a number of parallel queues, each with an arbitrary capacity and multiple identical exponential servers. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process. Upon arrival, a customer joins a queue according to a state-dependent policy or leaves the system immediately if it is full. No jockeying among queues is allowed. An incoming customer to a parallel queue has a general patience time dependent on that queue after which he/she must depart from the system immediately. Parallel queues are of two types: type 1, wherein the impatience mechanism acts on the waiting time; or type 2, a single server queue wherein the impatience acts on the sojourn time. We prove a key result, namely, that the state process of the system in the long run converges in distribution to a well-defined Markov process. Closed-form solutions for the probability density function of the virtual waiting time of a queue of type 1 or the offered sojourn time of a queue of type 2 in a given state are derived which are, interestingly, found to depend only on the local state of the queue. The efficacy of the approach is illustrated by some numerical examples.     

Queues with Service Rate Controlled by a Delayed Feedback

We consider a single queue with a Markov modulated Poisson arrival process. Its service rate is controlled by a scheduler. The scheduler receives the workload information from the queue after a delay. This queue models the buffer in an earth station in a satellite network where the scheduler resides in the satellite. We obtain the conditions for stability, rates of convergence to the stationary distribution and the finiteness of the stationary moments. Next we extend these results to the system where the scheduler schedules the service rate among several competing queues based on delayed information about the workloads in the different queues.     

Analysis of M/M/S queues with 1-limited service

In this paper, a multiple server queue, in which each server takes a vacation after serving one customer is studied. The arrival process is Poisson, service times are exponentially distributed and the duration of a vacation follows a phase distribution of order 2. Servers returning from vacation immediately take another vacation if no customers are waiting. A matrix geometric method is used to find the steady state joint probability of number of customers in the system and busy servers, and the mean and the second moment of number of customers and mean waiting time for this model. This queuing model can be used for the analysis of different kinds of communication networks, such as multi-slotted networks, multiple token rings, multiple server polling systems and mobile communication systems.     

Distributional Form of Little's Law for FIFO Queues with Multiple Markovian Arrival Streams and Its Application to Queues with Vacations

This paper considers stationary queues with multiple arrival streams governed by an irreducible Markov chain. In a very general setting, we first show an invariance relationship between the time-average joint queue length distribution and the customer-average joint queue length distribution at departures. Based on this invariance relationship, we provide a distributional form of Little's law for FIFO queues with simple arrivals (i.e., the superposed arrival process has the orderliness property). Note that this law relates the time-average joint queue length distribution with the stationary sojourn time distributions of customers from respective arrival streams. As an application of the law, we consider two variants of FIFO queues with vacations, where the service time distribution of customers from each arrival stream is assumed to be general and service time distributions of customers may be different for different arrival streams. For each queue, the stationary waiting time distribution of customers from each arrival stream is first examined, and then applying the Little's law, we obtain an equation which the probability generating function of the joint queue length distribution satisfies. Further, based on this equation, we provide a way to construct a numerically feasible recursion to compute the joint queue length distribution.     

Analysis of a Discrete-Time Finite-Capacity Single-Server Queue with Markovian-Arrival Process and Random-Bulk-Service: D-MAP/G Y /1/M

In this article, we consider a single-server, finite-capacity queue with random bulk service rule where customers arrive according to a discrete-time Markovian arrival process (D-MAP). The model is denoted by D-MAP/G ^Y /1/M where server capacity (bulk size for service) is determined by a random variable Y at the starting point of services. A simple analysis of this model is given using the embedded Markov chain technique and the concept of the mean sojourn time of the phase of underlying Markov chain of D-MAP. A complete solution to the distribution of the number of customers in the D-MAP/G ^Y /1/M queue, some computational results, and performance measures such as the average number of customers in the queue and the loss probability are presented.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

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 MAP/G a ,b /1/N Queue

The Markovian arrival process (MAP) is used to represent the bursty and correlated traffic arising in modern telecommunication network. In this paper, we consider a single server finite capacity queue with general bulk service rule in which arrivals are governed by MAP and service times are arbitrarily distributed. The distributions of the number of customers in the queue at arbitrary, post-departure and pre-arrival epochs have been obtained using the supplementary variable and the embedded Markov chain techniques. Computational procedure has been given when the service time distribution is of phase type.     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

A Markov-modulated M/G/1 queue II: Busy period and time for buffer overflow

We consider an M/G/1 queue where the arrival and service processes are modulated by a two state Markov chain. We assume that the arrival rate, service time density and the rates at which the Markov chain switches its state, are functions of the total unfinished work (buffer content) in the queue. We compute asymptotic approximations to performance measures such as the mean residual busy period, mean length of a busy period, and the mean time to reach capacity.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.     

A Queue with Semi-Markovian Batch Plus Poisson Arrivals with Application to the MPEG Frame Sequence

We consider a queueing system with a single server having a mixture of a semi-Markov process (SMP) and a Poisson process as the arrival process, where each SMP arrival contains a batch of customers. The service times are exponentially distributed. We derive the distributions of the queue length of both SMP and Poisson customers when the sojourn time distributions of the SMP have rational Laplace–Stieltjes transforms. We prove that the number of unknown constants contained in the generating function for the queue length distribution equals the number of zeros of the denominator of this generating function in the case where the sojourn times of the SMP follow exponential distributions. The linear independence of the equations generated by those zeros is discussed for the same case with additional assumption. The necessary and sufficient condition for the stability of the system is also analyzed. The distributions of the waiting times of both SMP and Poisson customers are derived. The results are applied to the case in which the SMP arrivals correspond to the exact sequence of Motion Picture Experts Group (MPEG) frames. Poisson arrivals are regarded as interfering traffic. In the numerical examples, the mean and variance of the waiting time of the ATM cells generated from the MPEG frames of real video data are evaluated.