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.     

The busy period distribution in a closed tandem of queues

We derive the busy period distribution in a closed tandem of FCFS queues with general service times.     

A survey of retrial queues

We present a survey of the main results and methods of the theory of retrial queues, concentrating on Markovian single and multi-channel systems. For the single channel case we consider the main model as well as models with batch arrivals, multiclasses, customer impatience, double connection, control devices, two-way communication and buffer. The stochastic processes arising from these models are considered in the stationary as well as the nonstationary regime. For multi-channel queues we survey numerical investigations of stationary distributions, limit theorems for high and low retrial intensities and heavy and light traffic behaviour.     

Busy periods of discrete-time queues using the Lagrange implicit function theorem

In this paper, we study the busy-period distribution for discrete-time queues assuming a Bernoulli arrival process, with arbitrary service-time and batch-arrival distributions. We derive explicit analytic formulas for these distributions using the Lagrange Implicit Function Theorem applied to probability generating functions. The convenient coefficient operator notation used in these formulas leads to a computationally efficient method for obtaining the distributions in their entirety from these analytic formulas.     

Stochastic comparisons for bulk queues

We consider two important classes of single-server bulk queueing models: M^(X)/G^(Y)/1 with Poisson arrivals of customer groups, and G^(X)/m^(Y)1 with batch service times having exponential density. In each class we compare two systems and prove that one is more congested than the other if their basic random variables are stochastically ordered in an appropriate manner. However, it must be recognized that a system that appears congested to customers might be working efficiently from the system manager's point of view. We apply the results of this comparison to (i) the family {M/G^(s)/1,s 1} of systems with Poisson input of customers and batch service times with varying service capacity; (ii) the family {G^(s)/1,s 1} of systems with exponential customer service time density and group arrivals with varying group size; and (iii) the family {M/D/s,s 1} of systems with Poisson arrivals, constant service time and varying number of servers. Within each family, we find the system that is the best for customers, but this turns out to be the worst for the manager (or vice versa). We also establish upper (or lower) bounds for the expected queue length in steady state and the expected number of batches (or groups) served during a busy period. The approach of the paper is based on the stochastic comparison of random walks underlying the models.This research was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

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.     

Analysis of preemptive loss priority queues with preemption distance

In a queueing system with preemptive loss priority discipline, customers disappear from the system immediately when their service is preempted by the arrival of another customer with higher priority. Such a system can model a case in which old requests of low priority are not worthy of deferred service. This paper is concerned with preemptive loss priority queues in which customers of each priority class arrive in a Poisson process and have general service time distribution. The strict preemption in the existing model is extended by allowing the preemption distance parameterd such that arriving customers of only class 1 throughp — d can preempt the service of a customer of classp. We obtain closed-form expressions for the mean waiting time, sojourn time, and queue size from their distributions for each class, together with numerical examples. We also consider similar systems with server vacations.     

On M/M/1 queues with a smart machine

This paper discusses a class of M/M/1 queueing models in which the service time of a customer depends on the number of customers served in the current busy period. It is particularly suited for applications in which the server has kind of learning ability and warms up gradually. We present a simple and computationally tractable scheme which recursively determines the stationary probabilities of the queue length. Other performance measures such as the Laplace transform of the busy period are also obtained. For the firstN exceptional services model which can be considered as a special case of our model, we derive a closed-formula for the generating function of the stationary queue length distribution. Numerical examples are also provided.     

匹配排队网络的忙期

本文考虑了匹配排队网络ＰＨ／Ｍ／ｃ→ｏＰＨ／１,研究了两个子系统和整个网络的忙期与非闲期的概率分布,得到了具有一致误差的算法。,然后证明了这些算法的时间与空间的计算复杂性都是多项式的．最后给出了数例。     

Markovian Controllable Queueing Systems with Hysteretic Policies: Busy Period and Waiting Time Analysis

We study Markovian queueing systems in which the service rate varies whenever the queue length changes. More specifically we consider controllable queues operating under the so-called hysteretic policy which provides a rather versatile class of operating rules for increasing and decreasing service rate at the arrival and service completion times. The objective of this paper is to investigate algorithmically the busy period and the waiting time distributions. Our analysis supplements the classical work of Yadin and Naor (1967) who focused on the steady-state probabilities of the system state. AMS 2000 Subject Classification 60K25, 90B22     

Services within a Busy Period of an M/M/1 Queue and Dyck Paths

We analyze the service times of customers in a stable M/M/1 queue in equilibrium depending on their position in a busy period. We give the law of the service of a customer at the beginning, at the end, or in the middle of the busy period. It enables as a by-product to prove that the process of instants of beginning of services is not Poisson. We then proceed to a more precise analysis. We consider a family of polynomial generating series associated with Dyck paths of length 2n and we show that they provide the correlation function of the successive services in a busy period with n+1 customers.     

A sequential technique for the control of traffic intensity in Markovian queues

A sequential parameter control technique previously introduced by the author is modified in this paper so as to make it simple in practice. The detailed procedure involving two phases, a warning phase with control limits and a testing phase using an appropriate test is illustrated for a queueing system with an embedded Markov chain. Operating characteristics of the procedure are also examined.     

Transient and busy period analysis of theGI/G/1 queue: The method of stages

In this paper we study the transient behavior of the MGE_L/MGE_M/1 queueing system, where MGE is the class of mixed generalized Erlang distributions which can approximate an arbitrary distribution. We use the method of stages combined with the separation of variables and root finding techniques together with linear and tensor algebra. We find simple closed form expressions for the Laplace transforms of the queue length distribution and the waiting time distribution under FCFS when the system is initially empty and the busy period distribution. We report computational results by inverting these expressions numerically in the time domain. Because of the simplicity of the expressions derived our algorithm is very fast and robust.The research of the author was partially supported by grants from the Leaders for Manufacturing program at MIT and from Draper Laboratory.     

Smoothed perturbation analysis for queues with finite buffers

Applying the technique of smoothed perturbation analysis (SPA) to theGI/G/1/K queue, we derive gradient estimators for two performance measures: the mean steady-state system time of a served customer and the probability that an arriving customer is rejected. Unbiasedness of the estimators follows from results of a previous general framework on SPA estimators. However, in that framework, the estimators often require the simulation of numerous additional sample subpaths, possibly making the technique practically infeasible in applications. We exploit some of the special structure of theGI/G/1/K queue to come up with an estimator which requires at most the simulation of a single additional sample subpath. By establishing certain regenerative properties, we provide a strong consistency proof for the estimator.     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.     

Busy period for the first subsystem in a matched queueing network

We formulate the busy period for the first subsystem in the matched queueing network PH/M/c→°PH/PH/1 as the first passage time of a Markov process and then present an approximate algorithm with uniform error for it. A numerical example is presented to illustrate the algorithm.     

Busy period analysis for the GI/M/1 queue with exponential vacations

We consider the busy period in the GI/M/1 queue with multiple exponential vacations. We derive the transform of the joint distribution of the length of a busy period, the number of customers served during the busy period, and the residual interarrival time at the instant the busy period ends.     

Traffic processes in a class of finite Markovian queues

This paper exposes the stochastic structure of traffic processes in a class of finite state queueing systems which are modeled in continuous time as Markov processes. The theory is presented for theM/E _k /φ/L class under a wide range of queue disciplines. Particular traffic processes of interest include the arrival, input, output, departure and overflow processes. Several examples are given which demonstrate that the theory unifies many earlier works, as well as providing some new results. Several extensions to the model are discussed.     

Optimal buffer allocation in tandems of last come first served queues

A large fixed number of buffer spaces is given. We consider the problem of allocating these spaces among the nodes of a tandem of last-come-first-served queues with general service time distributions and Poisson external arrivals so as to optimize some performance criterion associated with the time to buffer overflow, such as maximizing its mean or maximizing the probability that it exceeds some value. Consider the following rule of thumb: allocate the buffer spaces in inverse proportion to the logarithms of the effective service rates at the nodes. Here effective service rate denotes the ratio of the service rate to the stationary arrival rate. We prove that this rule of thumb achieves a nearly optimal buffer allocation under the assumption that the service time distributions satisfy an exponential tail condition. This problem has been studied earlier in the context of Jackson networks, where it was shown that the same rule of thumb achieves an allocation that is close to optimal. The technique of proof here is similar, but there are important differences. Both Jackson networks and the LCFS tandems considered here are product form networks (with infinite buffers). Optimism should lead us to expect that the near optimality of this rule of thumb holds much more generally for product-form networks, but this remains a conjecture at present.Research supported by NSF under NCR 8857731, by AT&T, and by Bellcore Inc.Research supported by IBM under a graduate fellowship.