Multi-server retrial queue with negative customers and disasters

We consider a multi-server retrial queue with waiting places in service area and four types of arrivals, positive customers, disasters and two types of negative customers, one for deleting customers in orbit and the other for deleting customers in service area. The four types of arrivals occur according to a Markovian arrival process with marked transitions (MMAP) which may induce the dependence among the arrival processes of the four types. We derive a necessary and sufficient condition for the system to be positive recurrent by comparing sample paths of auxiliary systems whose stability conditions can be obtained. We use a generalized truncated system that is obtained by modifying the retrial rates for an approximation of stationary queue length distribution and show the convergence of approximation to the original model. An algorithmic solution for the stationary queue length distribution and some numerical results are presented.      

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.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Recursive computation of invariant distributions of Feller processes

This paper provides a general and abstract approach to compute invariant distributions for Feller processes. More precisely, we show that the recursive algorithm presented in Lamberton and Pagès (2002) and based on simulation algorithms of stochastic schemes with decreasing steps can be used to build invariant measures for general Feller processes. We also propose various applications: Approximation of Markov Brownian diffusion stationary regimes with a Milstein or an Euler scheme and approximation of a Markov switching Brownian diffusion stationary regimes using an Euler scheme.     

Infinite-server systems with Coxian arrivals

We consider a network of infinite-server queues where the input process is a Cox process of the following form: The arrival rate is a vector-valued linear transform of a multivariate generalized (i.e., being driven by a subordinator rather than a compound Poisson process) shot-noise process. We first derive some distributional properties of the multivariate generalized shot-noise process. Then these are exploited to obtain the joint transform of the numbers of customers, at various time epochs, in a single infinite-server queue fed by the above-mentioned Cox process. We also obtain transforms pertaining to the joint stationary arrival rate and queue length processes (thus facilitating the analysis of the corresponding departure process), as well as their means and covariance structure. Finally, we extend to the setting of a network of infinite-server queues.

     

Admission control of a service station when the arrivals are internal

All studies in the admission control of a service station make decisions at arrival epochs. When arrivals are internal and are rejected from a queue, the rejected jobs have to be routed to other stations in the system. However the system will not know whether a job will be admitted to a queue or not until its arrival epoch to that queue. Thus, the system has to react dynamically and agilely to the decisions made at a specific queue and may try several queues before finding a queue that admits the job. This paper remedies these difficulties by changing the decision epochs of the admission control from arrival epochs to departure epochs with the actions of switching (keeping) the arrival stream on or off. Thus upstream stations will have information on the admission status of their downstream stations all the time. It is proved that the optimal policy for this revised admission control system is of control limit type for an M/G/1 queue. Comparisons of the optimal values and optimal policies for the admission controls made at arrival epochs and at departure epochs are included in the paper.     

Shift ergodicity for stationary Markov processes

In this paper shift ergodicity and related topics are studied for certain stationary processes. We first present a simple proof of the conclusion that every stationary Markov process is a generalized convex combination of stationary ergodic Markov processes. A direct consequence is that a stationary distribution of a Markov process is extremal if and only if the corresponding stationary Markov process is time ergodic and every stationary distribution is a generalized convex combination of such extremal ones. We then consider space ergodicity for spin flip particle systems. We prove space shift ergodicity and mixing for certain extremal invariant measures for a class of spin systems, in which most of the typical models, such as the Voter Models and the Contact Models, are included. As a consequence of these results we see that for such systems, under each of those extremal invariant measures, the space and time means of an observable coincide, an important phenomenon in statistical physics. Our results provide partial answers to certain interesting problems in spin systems.     

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.     

Analysis of the GI/Geo/1 queue with N-policy

We consider a discrete-time single server N  -policy GI/Geo/1$\mathit{GI}/\mathit{Geo}/1$ queueing system. The server stops servicing whenever the system becomes empty, and resumes its service as soon as the number of waiting customers in the queue reaches N. Using an embedded Markov chain and a trial solution approach, the stationary queue length distribution at arrival epochs is obtained. Furthermore, we obtain the stationary queue length distribution at arbitrary epochs by using the preceding result and a semi-Markov process. The sojourn time distribution is also presented.     

Asymptotics for transient and stationary probabilities for finite and infinite buffer discrete time queues

Consider a discrete time queue with i.i.d. arrivals (see the generalisation below) and a single server with a buffer length m. Let τm be the first time an overflow occurs. We obtain asymptotic rate of growth of moments and distributions of τm as m → ∞. We also show that under general conditions, the overflow epochs converge to a compound Poisson process. Furthermore, we show that the results for the overflow epochs are qualitatively as well as quantitatively different from the excursion process of an infinite buffer queue studied in continuous time in the literature. Asymptotic results for several other characteristics of the loss process are also studied, e.g., exponential decay of the probability of no loss (for a fixed buffer length) in time [0,η], η → ∞, total number of packets lost in [0, η, maximum run of loss states in [0, η]. We also study tails of stationary distributions. All results extend to the multiserver case and most to a Markov modulated arrival process. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Stationary Distribution of the GI X /M Y /1 Queueing System

For the GI ^X /M/1 queue, it has been recently proved that there exist geometric distributions that are stochastic lower and upper bounds for the stationary distribution of the embedded Markov chain at arrival epochs. In this note we observe that this is also true for the GI ^X /M ^Y /1 queue. Moreover, we prove that the stationary distribution of its embedded Markov chain is asymptotically geometric. It is noteworthy that the asymptotic geometric parameter is the same as the geometric parameter of the upper bound. This fact justifies previous numerical findings about the quality of the bounds.     

The MMCPP/GE/c Queue

We obtain the queue length probability distribution at equilibrium for a multi-server, single queue with generalised exponential (GE) service time distribution and a Markov modulated compound Poisson arrival process (MMCPP) – i.e., a Poisson point process with bulk arrivals having geometrically distributed batch size whose parameters are modulated by a Markovian arrival phase process. This arrival process has been considered appropriate in ATM networks and the GE service times provide greater flexibility than the more conventionally assumed exponential distribution. The result is exact and is derived, for both infinite and finite capacity queues, using the method of spectral expansion applied to the two dimensional (queue length by phase of the arrival process) Markov process that describes the dynamics of the system. The Laplace transform of the interdeparture time probability density function is then obtained. The analysis therefore could provide the basis of a building block for modelling networks of switching nodes in terms of their internal arrival processes, which may be both correlated and bursty.     

A Markov Renewal Based Model for Wireless Networks

We propose a queueing network model which can be used for the integration of the mobility and teletraffic aspects that are characteristic of wireless networks. In the general case, the model is an open network of infinite server queues where customers arrive according to a non-homogeneous Poisson process. The movement of a customer in the network is described by a Markov renewal process. Moreover, customers have attributes, such as a teletraffic state, that are driven by continuous time Markov chains and, therefore, change as they move through the network. We investigate the transient and limit number of customers in disjoint sets of nodes and attributes. These turn out to be independent Poisson random variables. We also calculate the covariances of the number of customers in two sets of nodes and attributes at different time epochs. Moreover, we conclude that the arrival process per attribute to a node is the sum of independent Poisson cluster processes and derive its univariate probability generating function. In addition, the arrival process to an outside node of the network is a non-homogeneous Poisson process. We illustrate the applications of the queueing network model and the results derived in a particular wireless network.     

Markov modulation of a two-sided reflected Brownian motion with application to fluid queues

In this paper, we study a reflected Markov-modulated Brownian motion with a two sided reflection in which the drift, diffusion coefficient and the two boundaries are (jointly) modulated by a finite state space irreducible continuous time Markov chain. The goal is to compute the stationary distribution of this Markov process, which in addition to the complication of having a stochastic boundary can also include jumps at state change epochs of the underlying Markov chain because of the boundary changes. We give the general theory and then specialize to the case where the underlying Markov chain has two states.     

A G/M/1-queue with exponential retrial

Summary We consider a G/M/1 retrial model in which the delays between retrials are i.i.d. exponentially distributed random variables. We investigate the steady-state distribution of the embedded Markov chain at completion service epochs, the stationary distribution at anytime and the virtual waiting time.     

The BMAP/SM/1 retrial queue with controllable operation modes

We deal with a single-server retrial queueing system having two modes of operation. Under the fixed mode, the system operates as an usual system with a batch Markovian arrival process (BMAP), semi-Markovian (SM) service process and a constant total retrial rate. Different modes are distinguished by characteristics of the input, service and retrial rate. The mode of operation can be switched at the service completion epochs depending on the queue-length. The strategy of control belongs to the class of hysteretic strategies. We calculate a stationary distribution of numbers of calls in the orbit at service completion epochs. We also discuss the problem of optimizing the strategy of control.     

Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K]/PH[K]/N/LCFS non-preemptive queue

This paper studies a multi-server queueing system with multiple types of customers and last-come-first-served (LCFS) non-preemptive service discipline. First, a quasi-birth-and-death (QBD) Markov process with a tree structure is defined and some classical results of QBD Markov processes are generalized. Second, the MMAP[K]/PH[K]/N/LCFS non-preemptive queue is introduced. Using results of the QBD Markov process with a tree structure, explicit formulas are derived and an efficient algorithm is developed for computing the stationary distribution of queue strings. Numerical examples are presented to show the impact of the correlation and the pattern of the arrival process on the queueing process of each type of customer.