Sojourn times in a processor sharing queue with service interruptions

We study the sojourn times of customers in an M/M/1 queue with the processor sharing service discipline and a server that is subject to breakdowns. The lengths of the breakdowns have a general distribution, whereas the on-periods are exponentially distributed. A branching process approach leads to a decomposition of the sojourn time, in which the components are independent of each other and can be investigated separately. We derive the Laplace–Stieltjes transform of the sojourn-time distribution in steady state, and show that the expected sojourn time is not proportional to the service requirement. In the heavy-traffic limit, the sojourn time conditioned on the service requirement and scaled by the traffic load is shown to be exponentially distributed. The results can be used for the performance analysis of elastic traffic in communication networks, in particular, the ABR service class in ATM networks, and best-effort services in IP networks.     

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.     

Tail asymptotics for the queue length in an M/G/1 retrial queue

In this paper, we study the tail behavior of the stationary queue length of an M/G/1 retrial queue. We show that the subexponential tail of the stationary queue length of an M/G/1 retrial queue is determined by that of the corresponding M/G/1 queue, and hence the stationary queue length in an M/G/1 retrial queue is subexponential if the stationary queue length in the corresponding M/G/1 queue is subexponential. Our results for subexponential tails also apply to regularly varying tails, and we provide the regularly varying tail asymptotics for the stationary queue length of the M/G/1 retrial queue. AMS subject classifications: 60J25, 60K25     

Heavy-traffic analysis for the GI/G/1 queue with heavy-tailed distributions

We consider a GI/G/1 queue in which the service time distribution and/or the interarrival time distribution has a heavy tail, i.e., a tail behaviour like t ^−ν with 1 < ν ⩽ 2 , so that the mean is finite but the variance is infinite. We prove a heavy-traffic limit theorem for the distribution of the stationary actual waiting time W. If the tail of the service time distribution is heavier than that of the interarrival time distribution, and the traffic load a → 1, then W, multiplied by an appropriate ‘coefficient of contraction’ that is a function of a, converges in distribution to the Kovalenko distribution. If the tail of the interarrival time distribution is heavier than that of the service time distribution, and the traffic load a → 1, then W, multiplied by another appropriate ‘coefficient of contraction’ that is a function of a, converges in distribution to the negative exponential distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic expansions for waiting time probabilities in an M/G/1 queue with long-tailed service time

We consider anM/G/1 queue with FCFS queue discipline. We present asymptotic expansions for tail probabilities of the stationary waiting time when the service time distribution is longtailed and we discuss an extension of our methods to theM ^[x]/G/1 queue with batch arrivals.     

A decomposition theorem and related results for the discriminatory processor sharing queue

In this paper, we study a discriminatory processor sharing queue with Poisson arrivals,K classes and general service times. For this queue, we prove a decomposition theorem for the conditional sojourn time of a tagged customer given the service times and class affiliations of the customers present in the system when the tagged customer arrives. We show that this conditional sojourn time can be decomposed inton+1 components if there aren customers present when the tagged customer arrives. Further, we show that thesen+1 components can be obtained as a solution of a system of non-linear integral equations. These results generalize known results about theM/G/1 egalitarian processor sharing queue.     

Insensitive bounds for the moments of the sojourn time distribution in the M/G/1 processor-sharing queue

This paper studies the M/G/1 processor-sharing (PS) queue, in particular the sojourn time distribution conditioned on the initial job size. Although several expressions for the Laplace-Stieltjes transform (LST) are known, these expressions are not suitable for computational purposes. This paper derives readily applicable insensitive bounds for all moments of the conditional sojourn time distribution. The instantaneous sojourn time, i.e., the sojourn time of an infinitesimally small job, leads to insensitive upper bounds requiring only knowledge of the traffic intensity and the initial job size. Interestingly, the upper bounds involve polynomials with so-called Eulerian numbers as coefficients. In addition, stochastic ordering and moment ordering results for the sojourn time distribution are obtained. AMS Subject Classification: 60K25, 60E15 This work has been partially funded by the Dutch Ministry of Economic Affairs under the program ‘Technologische Samenwerking ICT-doorbraakprojecten’, project TSIT1025 BEYOND 3G.     

Tail asymptotics for the fundamental period in the MAP/G/1 queue

This paper studies the tail behavior of the fundamental period in the MAP/G/1 queue. We prove that if the service time distribution has a regularly varying tail, then the fundamental period distribution in the MAP/G/1 queue has also regularly varying tail, and vice versa, by finding an explicit expression for the asymptotics of the tail of the fundamental period in terms of the tail of the service time distribution. Our main result with the matrix analytic proof is a natural extension of the result in (de Meyer and Teugels, J. Appl. Probab. 17: 802–813, 1980) on the M/G/1 queue where techniques rely heavily on analytic expressions of relevant functions. I.-S. Wee’s research was supported by the Korea Research Foundation Grant KRF 2003-070-00008.     

The interdeparture-time distribution for each class in the ∑ i M i /G i /1 queue

A stationary queueing system is described in which a single server handles several competing Poisson arrival streams on a first-come first-served basis. Each class has its own generally distributed service time characteristics. The principal result is the Laplace-Stieltjes transform, for each class, of the interdeparture time distribution function. Examples are given and applications are discussed.     

The M/G/1 queue with disasters and working breakdowns

In this paper, we analyze the M/G/1 queueing system with disasters and working breakdown services. The system consists of a main server and a substitute server, and disasters only occur while the main server is in operation. The occurrence of disasters forces all customers to leave the system and causes the main server to fail. At a failure instant, the main server is sent to the repair shop and the repair period immediately begins. During the repair period, the system is equipped with the substitute server which provides the working breakdown services to arriving customers. After introducing the concept of working breakdown services, we derive the system size distribution and the sojourn time distribution. We also obtain the results of the cycle analysis. In addition, numerical works are given to examine the relation between the sojourn time and the some system parameters.     

The conditional sojourn time distribution in the GI/M/1 processor-sharing queue in heavy traffic

We treat the GI/M/1 queue with a processor-sharing server, in the heavy traffic case. Using perturbation methods, we construct asymptotic expansions for the conditional sojourn time distribution of a tagged customer conditioned on the tagged customer's service time. The resulting approximation is simple in form and involves only the first three moments of the interarrival time distribution.     

An M/G/1-type queuing model with service times depending on queue length

A study is made of an M/G/1-type queuing model in which customers receive one type of service until such time as, at the end of a service, the queue size is found to exceed a given value N, N ≥ 1. Then a second type of service is put into effect and remains in use until the queue size is reduced to a fixed value K, 0 ≤ K ≤ N. Equations are derived for the stationary probabilities both at departure times and at general times. An algorithm is developed that allows the rapid computation of the mean queue length and some important probabilities.     

Higher moments of the waiting time distribution in M/G/1 retrial queues

This work analyzes the waiting time distribution in the M/G/1 retrial queue. The first two moments of the waiting time distribution are known from the literature. In this work we obtain all the moments of the waiting time distribution.     

On the longest service time in a busy period of the M⧸G⧸1 queue

This paper considers the supremum m of the service times of the customers served in a busy period of the M?G?1 queueing system. An implicit expression for the distribution m(w) of m is derived. This expression leads to some bounds for m(w), while it can also be used to obtain numerical results. The tail behaviour of m(w) is investigated, too. The results are particularly useful in the analysis of a class of tandem queueing systems.     

Optimization of the T policy M/G/1 queue with server breakdowns and general startup times

This paper investigates the T$T$ policy M/G/1 queue with server breakdowns, and startup times. Customers arrive at the system according to a Poisson process. Service times, repair times, and startup times are assumed to be generally distributed. The server is turned on after a fixed length of time T$T$ repeatedly until at least one customer is present in the waiting line. The server needs a startup time before starting the service. We analyze various system performance measures and develop the total expected cost function per unit time in which T$T$ is a decision variable. We determine the optimum threshold T^∗$T^{\ast }$ and derive analytical results for sensitivity investigations. The sensitivity analysis is particularly valuable to the system analyst when evaluating future conditions. We also present extensive numerical computation for illustration purpose.     

Continuous time control of the arrival process in an m/g/1 queue

The problem of continuously controlling the arrival process in an M/G/1 queue is studied. The control is exercised by keeping the facility open or closed for potential arrivals, and is based on the residual workload process. The reward structure includes a reward rate R when the server is busy, and a holding cost rate cx when the residual workload is x. The economic criterion used is long run average return. A control limit policy is shown to be optimal. An iterative method for calculating this control limit policy is suggested.     

Tail asymptotics for M/G/1 type queueing processes with subexponential increments

Bivariate regenerative Markov modulated queueing processes {I _n ,L _n } are described. {I _n } is the phase process, and {L _n } is the level process. Increments in the level process have subexponential distributions. A general boundary behavior at the level 0 is allowed. The asymptotic tail of the cycle maximum, , during a regenerative cycle, , and the asymptotic tail of the stationary random variable L _∞, respectively, of the level process are given and shown to be subexponential with L _∞ having the heavier tail. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Markov-modulated M/G/1 queue I: Stationary distribution

We consider an M/G/1 queueing system in which the arrival rate and service time density are functions of a two-state stochastic process. We describe the system by the total unfinished work present and allow the arrival and service rate processes to depend on the current value of the unfinished work. We employ singular perturbation methods to compute asymptotic approximations to the stationary distribution of unfinished work and in particular, compute the stationary probability of an empty queue.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/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.