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.     

Asymptotic expansions for the sojourn time distribution in the M/G/1-PS queue

We consider the M/G/1 queue with a processor sharing server. We study the conditional sojourn time distribution, conditioned on the customer’s service requirement, as well as the unconditional distribution, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. Our results demonstrate the possible tail behaviors of the unconditional distribution, which was previously known in the cases G = M and G = D (where it is purely exponential). We assume that the service density decays at least exponentially fast. We use various methods for the asymptotic expansion of integrals, such as the Laplace and saddle point methods.     

Large-time asymptotics for the Gt/Mt/st+GIt many-server fluid queue with abandonment

We previously introduced and analyzed the G _t /M _t /s _t +GI _t many-server fluid queue with time-varying parameters, intended as an approximation for the corresponding stochastic queueing model when there are many servers and the system experiences periods of overload. In this paper, we establish an asymptotic loss of memory (ALOM) property for that fluid model, i.e., we show that there is asymptotic independence from the initial conditions as time t evolves, under regularity conditions. We show that the difference in the performance functions dissipates over time exponentially fast, again under the regularity conditions. We apply ALOM to show that the stationary G/M/s+GI fluid queue converges to steady state and the periodic G _t /M _t /s _t +GI _t fluid queue converges to a periodic steady state as time evolves, for all finite initial conditions.     

On the single server retrial queue with priority customers

We consider anM ₂/G ₂/1 type queueing system which serves two types of calls. In the case of blocking the first type customers can be queued whereas the second type customers must leave the service area but return after some random period of time to try their luck again. This model is a natural generalization of the classicM ₂/G ₂/1 priority queue with the head-of-theline priority discipline and the classicM/G/1 retrial queue. We carry out an extensive analysis of the system, including existence of the stationary regime, embedded Markov chain, stochastic decomposition, limit theorems under high and low rates of retrials and heavy traffic analysis.Visiting from: Department of Probability, Mechanics and Mathematics, Moscow State University, Moscow 119899, Russia.     

Heavy-traffic limits for nearly deterministic queues: stationary distributions

We establish heavy-traffic limits for stationary waiting times and other performance measures in G _n /G _n /1 queues, where G _n indicates that an original point process is modified by cyclic thinning of order n, i.e., the thinned process contains every nth point from the original point process. The classical example is the Erlang E _n /E _n /1 queue, where cyclic thinning of order n is applied to both the interarrival times and the service times, starting from a “base” M/M/1 model. The models G _n /D/1 and D/G _n /1 are special cases of G _n /G _n /1. Since waiting times before starting service in the G/D/n queue are equivalent to waiting times in an associated G _n /D/1 model, where the interarrival times are the sum of n consecutive interarrival times in the original model, the G/D/n model is a special case as well. As n→∞, the G _n /G _n /1 models approach the deterministic D/D/1 model. We obtain revealing limits by letting ρ _n ↑1 as n→∞, where ρ _n is the traffic intensity in model n.     

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.     

A sample path analysis of the M t /M t /c queue

The exact transient distribution of the queue length of the M _t /M _t /1 single server queue with timedependent Poisson arrival rate and timedependent exponential service rate was recently obtained by Zhang and Coyle [63] in terms of a solution to a Volterra equation. Their method involved the use of generating functions and complex analysis. In this paper, we present an approach that ties the computation of these transient distributions directly to the random sample path behavior of the M _t /M _t /1 queue. We show the versatility of this method by applying it to the M _t /M _t /c multiserver queue, and indicating how it can be applied to queues with timedependent phase arrivals or timedependent phase service.     

Analytical Distribution of Waiting Time in the M/{iD}/1 Queue

We give an analytical formula for the steady-state distribution of queue-wait in the M/G/1 queue, where the service time for each customer is a positive integer multiple of a constant D > 0. We call this an M/{iD}/1 queue. We give numerical algorithms to calculate the distribution. In addition, in the case that the service distribution is sparse, we give revised algorithms that can compute the distribution more quickly.AMS subject classification: 60K25, 90B22     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

Impact of Bursty Traffic on Queues

The impact of bursty traffic on queues is investigated in this paper. We consider a discrete-time single server queue with an infinite storage room, that releases customers at the constant rate of c customers/slot. The queue is fed by an M/G/∞ process. The M/G/∞ process can be seen as a process resulting from the superposition of infinitely many ‘sessions’: sessions become active according to a Poisson process; a station stays active for a random time, with probability distribution G, after which it becomes inactive. The number of customers entering the queue in the time-interval [t, t + 1) is then defined as the number of active sessions at time t (t = 0,1, ...) or, equivalently, as the number of busy servers at time t in an M/G/∞ queue, thereby explaining the terminology. The M/G/∞ process enjoys several attractive features: First, it can display various forms of dependencies, the extent of which being governed by the service time distribution G. The heavier the tail of G, the more bursty the M/G/∞ process. Second, this process arises naturally in teletraffic as the limiting case for the aggregation of on/off sources [27]. Third, it has been shown to be a good model for various types of network traffic, including telnet/ftp connections [37] and variable-bit-rate (VBR) video traffic [24]. Last but not least, it is amenable to queueing analysis due to its very strong structural properties. In this paper, we compute an asymptotic lower bound for the tail distribution of the queue length. This bound suggests that the queueing delays will dramatically increase as the burstiness of the M/G/∞ input process increases. More specifically, if the tail of G is heavy, implying a bursty input process, then the tail of the queue length will also be heavy. This result is in sharp contrast with the exponential decay rate of the tail distribution of the queue length in presence of ‘non-bursty’ traffic (e.g. Poisson-like traffic). This revised version was published online in August 2006 with corrections to the Cover Date.     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

Transient behavior ofM/M ij/1 queues

We obtain the time dependent probabilities for the joint distribution of the number of arrivals and departures in [0,t] for theM/M ^ij/1 queue. This queue has the exponential service with parametersμ _ij, depending on the types of the successive customers attended. We provide an intuitive interpretation of the solution and also present some numerical results, including time dependent event probabilities and queue length.     

On Markov?CKrein characterization of the mean waiting time in M/G/K and other queueing systems

We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems??via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov?CKrein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.     

Time-dependent analysis of virtual waiting time behaviour in discrete time queues

Discrete time queueing models have been shown previously to be of practical use for modelling the approximate time-dependent behaviour of queue length in systems of the form M(t)/G/c. In this paper we extend these models to include the time-dependent behaviour of virtual waiting time.     

A simple method for computing state probabilities of theM/G/1 andGI/M/1 finite waiting space queues

This paper presents a simple method for computing steady state probabilities at arbitrary and departure epochs of theM/G/1/K queue. The method is recursive and works efficiently for all service time distributions. The only input required for exact evaluation of state probabilities is the Laplace transform of the probability density function of service time. Results for theGI/M/1/K –1 queue have also been obtained from those ofM/G/1/K queue.     

An Exact Solution for an M(t)/M(t)/1 Queue with Time-Dependent Arrivals and Service

We consider an M/M/1 queue with a time dependent arrival rate (t) and service rate (t). For a special form of the traffic intensity, we obtain an exact, explicit expression for the probability p _n (t) that there are n customers at time t. If the service rate is constant (=), this corresponds to (t)=(t)/=(b–at)^–2. We also discuss the heavy traffic diffusion approximation to this model. We evaluate our results numerically.     

The Baer-invariant of a semidirect product

In 1972 K.I. Tahara [7,2, Theorem 2.2.5], using cohomological methods, showed that if a finite group is the semidirect product of a normal subgroup N and a subgroup T, then M(T) is a direct factor of M(G), where M(G) is the Schur-multiplicator of G and in the finite case, is the second cohomology group of G. In 1977 W. Haebich [1, Theorem 1.7] gave another proof using a different method for an arbitrary group G.In this paper we generalize the above theorem. We will show that scN_cM(T) is a direct factor of _cM(G), where _c[3, p. 102] is the variety of nilpotent groups of class at most c ≥ 1 and _cM(G) is the Baer-invariant of the group G with respect to the variety _c [3, p. 107].     

Erlang loss bounds for OT–ICU systems

In hospitals, patients can be rejected at both the operating theater (OT) and the intensive care unit (ICU) due to limited ICU capacity. The corresponding ICU rejection probability is an important service factor for hospitals. Rejection of an ICU request may lead to health deterioration for patients, and for hospitals to costly actions and a loss of precious capacity when an operation is canceled. There is no simple expression available for this ICU rejection probability that takes the interaction with the OT into account. With c the ICU capacity (number of ICU beds), this paper proves and numerically illustrates a lower bound by an M|G|c|c system and an upper bound by an M|G|c-1|c-1 system, hence by simple Erlang loss expressions. The result is based on a product form modification for a special OT–ICU tandem formulation and proved by a technically complicated Markov reward comparison approach. The upper bound result is of particular practical interest for dimensioning an ICU to secure a prespecified service quality. The numerical results include a case study.     

Time-dependent analysis of M/G/1 vacation models with exhaustive service

We analyze the time-dependent process in severalM/G/1 vacation models, and explicitly obtain the Laplace transform (with respect to an arbitrary point in time) of the joint distribution of server state, queue size, and elapsed time in that state. Exhaustive-serviceM/G/1 systems with multiple vacations, single vacations, an exceptional service time for the first customer in each busy period, and a combination ofN-policy and setup times are considered. The decomposition property in the steady-state joint distribution of the queue size and the remaining service time is demonstrated.