On the Transient Behavior of the M/M/1 and M/M/1/M Queues

This paper gives a transient analysis of the classic M/M/1 and M/M/1/K queues. Our results are asymptotic as time and queue length become simultaneously large for the infinite capacity queue, and as the system’s storage capacity K becomes large for the finite capacity queue. We give asymptotic expansions for p_n(t), which is the probability that the system contains n customers at time t. We treat several cases of initial conditions and different traffic intensities. The results are based on (i) asymptotic expansion of an exact integral representation for p_n(t) and (ii) applying the ray method to a scaled form of the forward Kolmogorov equation which describes the time evolution of p_n(t).     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

A Load-Balanced Network with Two Servers

A load-balanced network with two queues Q ₁ and Q ₂ is considered. Each queue receives a Poisson stream of customers at rate _i , i=1,2. In addition, a Poisson stream of rate arrives to the system; the customers from this stream join the shorter of two queues. After being served in the ith queue, i=1,2, customers leave the system with probability 1–p _i ^*, join the jth queue with probability p(i,j), j=1,2, and choose the shortest of two queues with probability p(i,{1,2}). We establish necessary and sufficient conditions for stability of the system.     

Steady-state probability of the randomized server control system with second optional service, server breakdowns and startup

This paper deals with the 〈N,p〉-policy M/G/1 queue with server breakdowns and general startup times, where customers arrive to demand the first essential service and some of them further demand a second optional service. Service times of the first essential service channel are assumed to follow a general distribution and that of the second optional service channel are another general distribution. The server breaks down according to a Poisson process and his repair times obey a general distribution in the first essential service channel and second optional service channel, respectively. The server operation starts only when N (N≥1) customers have accumulated, he requires a startup time before each busy period. When the system becomes empty, turn the server off with probability p (p∈[0,1]) and leave it on with probability (1?p). The method of maximum entropy principle is used to develop the approximate steady-state probability distribution of the queue length in the M/G(G, G)/1 queueing system. A study of the derived approximate results, compared to the established exact results for three different 〈N,p〉-policy queues, suggests that the maximum entropy principle provides a useful method for solving complex queueing systems.     

Heavy-traffic analysis of the sojourn time in a three node Jackson network with overtaking

We consider a Jackson network consisting of three first-in-first-out (FIFO)M/M/1 queues. When customers leave the first queue they can be routed to either the second or third queue. Thus, a customer that traverses the network by going from the first to the second to the third queue, can be overtaken by another customer that is routed from the first queue directly to the third. We study the distribution of the sojourn time of a customer through the three node network, in the heavy traffic limit. A three term heavy traffic asymptotic approximation to the sojourn time density is derived. The leading term shows that the nodes decouple in the heavy traffic limit. The next two terms, however, do show the dependence of the sojourn times at the individual nodes and give quantitative measures of the effects of overtaking.     

A queueing network with a single cyclically roving server

A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation B_i, B _i ^* (s) service time of a customer at queue i and its LST - b_i, b_i ⁽²⁾ mean and second moment of B_i - R_i, R _i ^* (s) duration of switch-over period from queue i and its LST - r_i, r_i mean and second moment of R_i - r, r⁽²⁾ mean and second moment of _i ^N =₁R_i - _i external arrival rate of type-i customers - _i total arrival rate into queue i - _i utilization of queue i; _i=_i - system utilization _i ^N =_1i - c=E[C] the expected cycle length - X _i ^j number of customers in queue j when queue i is polled - X_i=X _i ⁱ number of customers residing in queue i when it is polled - f_i(j) - X _i ^* number of customers residing in queue i at an arbitrary moment - Y_i the duration of a service period of queue i - W_i,T_i the waiting time and sojourn time of an arbitary customer at queue i - F^*(z₁, z₂,..., z_N) GF of number of customers present at the queues at arbitrary moments - F_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at polling instants of queue i - ¯F_i(z₁, z₂,...,z_N) GF of number of customers present at the queues at switching instants of queue i - V_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at service initiation instants at queue i - ¯V_i(z₁,z₂,...,z_N) GF of number of customers present at the queues at service completion instants at queue i The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories.     

On the infinite server shortest queue problem: Non-symmetric case

We consider two parallel M/M/∞ queues. All servers in the first queue work at rate μ₁ and all in the second work at rate μ₂. A new arrival is routed to the system with the lesser number of customers. If both queues have equal occupancy, the arrival joins the first queue with probability ν₁, and the second with probability ν₂ = 1−ν₁. We analyze this model asymptotically. We assume that the arrival rate λ is large compared to the two service rates. We give several different asymptotic formulas, that apply for different ranges of the state space. The numerical accuracy of the asymptotic results is tested. AMS subject classification 60K25 60K30 34E20     

A heavy-traffic analysis of a closed queueing system with a GI/∞ service center

This paper studies the heavy-traffic behavior of a closed system consisting of two service stations. The first station is an infinite server and the second is a single server whose service rate depends on the size of the queue at the station. We consider the regime when both the number of customers, n, and the service rate at the single-server station go to infinity while the service rate at the infinite-server station is held fixed. We show that, as n→∞, the process of the number of customers at the infinite-server station normalized by n converges in probability to a deterministic function satisfying a Volterra integral equation. The deviations of the normalized queue from its deterministic limit multiplied by √n converge in distribution to the solution of a stochastic Volterra equation. The proof uses a new approach to studying infinite-server queues in heavy traffic whose main novelty is to express the number of customers at the infinite server as a time-space integral with respect to a time-changed sequential empirical process. This gives a new insight into the structure of the limit processes and makes the end results easy to interpret. Also the approach allows us to give a version of the classical heavy-traffic limit theorem for the G/GI/∞ queue which, in particular, reconciles the limits obtained earlier by Iglehart and Borovkov. This revised version was published online in June 2006 with corrections to the Cover Date.     

Maximum likelihood estimation for single server queues from waiting time data

Maximum likelihood estimators for the parameters of a GI/G/1 queue are derived based on the information on waiting times {W _t },t=1,...,n, ofn successive customers. The consistency and asymptotic normality of the estimators are established. A simulation study of the M/M/1 and M/E _k /1 queues is presented.     

Power series approximations for two-class generalized processor sharing systems

We develop power series approximations for a discrete-time queueing system with two parallel queues and one processor. If both queues are nonempty, a customer of queue 1 is served with probability β, and a customer of queue 2 is served with probability 1−β. If one of the queues is empty, a customer of the other queue is served with probability 1. We first describe the generating function U(z ₁,z ₂) of the stationary queue lengths in terms of a functional equation, and show how to solve this using the theory of boundary value problems. Then, we propose to use the same functional equation to obtain a power series for U(z ₁,z ₂) in β. The first coefficient of this power series corresponds to the priority case β=0, which allows for an explicit solution. All higher coefficients are expressed in terms of the priority case. Accurate approximations for the mean stationary queue lengths are obtained from combining truncated power series and Padé approximation.     

Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

Attractiveness of Brownian queues in tandem

Consider a sequence of n bi-infinite and stationary Brownian queues in tandem. Assume that the arrival process entering the first queue is a zero mean ergodic process. We prove that the departure process from the n-th queue converges in distribution to a Brownian motion as n goes to infinity. In particular this implies that the Brownian motion is an attractive invariant measure for the Brownian queueing operator. Our proof exploits the relationship between Brownian queues in tandem and the last-passage Brownian percolation model, developing a coupling technique in the second setting. The result is also interpreted in the related context of Brownian particles acting under one-sided reflection.

     

Equilibria of a class of transport equations arising in congestion control

We consider a multi-queue multi-server system with n servers (processors) and m queues. At the system there arrives a stationary and ergodic stream of m different types of requests with service requirements which are served according to the following k-limited head of the line processor sharing discipline: The first k requests at the head of the m queues are served in processor sharing by the n processors, where each request may receive at most the capacity of one processor. By means of sample path analysis and Loynes’ monotonicity method, a stationary and ergodic state process is constructed, and a necessary as well as a sufficient condition for the stability of the m separate queues are given, which are tight within the class of all stationary ergodic inputs. These conditions lead to tight necessary and sufficient conditions for the whole system, also in case of permanent customers, generalizing an earlier result by the authors for the case of n=k=1. This work was supported by a grant from the Siemens AG.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

Maximum Antichains in Random Subsets of a Finite Set

We consider the random poset (n, p) which is generated by first selecting each subset of [n]={1, …, n} with probability p and then ordering the selected subsets by inclusion. We give asymptotic estimates of the size of the maximum antichain for arbitrary p=p(n). In particular, we prove that if pn/log n→∞, an analogue of Sperner's theorem holds: almost surely the maximum antichain is (to first order) no larger than the antichain which is obtained by selecting all elements of (n, p) with cardinality n/2. This is almost surely not the case if pn=∞.     

Strong approximations for priority queues; head-of-the-line-first discipline

In this paper, we obtain strong approximation theorems for a single server queue withr priority classes of customers and a head-of-the-line-first discipline. By using priority queues of preemptive-resume discipline as modified systems, we prove strong approximation theorems for the number of customers of each priority in the system at timet, the number of customers of each priority that have departed in the interval [0,t], the work load in service time of each priority class facing the server at timet, and the accumulated time in [0,t] during which there are neither customers of a given priority class nor customers of priority higher than that in the system.Research supported by the National Natural Science Foundation of China.