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.     

Processor sharing for two queues with vastly different rates

We consider a 2-class queueing system, operating under a generalized processor-sharing discipline, in an asymptotic regime where the arrival and service rates of the two classes are vastly different. We use regular and singular perturbation analyses in a small parameter measuring this difference in rates. It is assumed that the system is stable, and not close to instability. Three different regimes are analyzed, corresponding to an underloaded, an overloaded and a critically loaded fast queue, respectively. In the first two regimes the lowest order approximation to the joint stationary distribution of the queue lengths is derived. For a critically loaded fast queue only the mean queue lengths are investigated, and the asymptotic matching, to lowest order, with the results for an underloaded and an overloaded fast queue is established.      

Limit non-stationary behavior of large closed queueing networks with bottlenecks

In this paper martingales methods are applied for analyzing limit non-stationary behavior of the queue length processes in closed Jackson queueing networks with a single class consisting of a large number of customers, a single infinite server queue, and a fixed number of single server queues with large state independent service rates. It is assumed that one of the single server nodes forms a bottleneck. For the non-bottleneck nodes we show that the queue length distribution at timet converges in generalized sense to the stationary distribution of the M/M/1 queue whose parameters explicitly depend ont. For the bottleneck node a diffusion approximation with reflection is proved in the moderate usage regime while fluid and Gaussian diffusion approximations are established for the heavy usage regime.     

Some Results for Large Closed Queueing Networks with and without Bottleneck: Up- and Down-Crossings Approach

The paper provides the up- and down-crossing method to study the asymptotic behavior of queue-length and waiting time in closed Jackson-type queueing networks. These queueing networks consist of central node (hub) and k single-server satellite stations. The case of infinite server hub with exponentially distributed service times is considered in the first section to demonstrate the up- and down-crossing approach to such kind of problems and help to understand the readers the main idea of the method. The main results of the paper are related to the case of single-server hub with generally distributed service times depending on queue-length. Assuming that the first k–1 satellite nodes operate in light usage regime, we consider three cases concerning the kth satellite node. They are the light usage regime and limiting cases for the moderate usage regime and heavy usage regime. The results related to light usage regime show that, as the number of customers in network increases to infinity, the network is decomposed to independent single-server queueing systems. In the limiting cases of moderate usage regime, the diffusion approximations of queue-length and waiting time processes are obtained. In the case of heavy usage regime it is shown that the joint limiting non-stationary queue-lengths distribution at the first k–1 satellite nodes is represented in the product form and coincides with the product of stationary GI/M/1 queue-length distributions with parameters depending on time.     

Limiting results for multiprocessor systems with breakdowns and repairs

An M/M/N queue, where each of the processors is subject to independent random breakdowns and repairs, is analyzed in the steady state under two limiting regimes. The first is the usual heavy traffic limit where the offered load approaches the available processing capacity. The (suitably normalized) queue size is shown to be asymptotically exponentially distributed and independent of the number of operative processors. The second limiting regime involves increasing the average lengths of the operative and inoperative periods, while keeping their ratio constant. Again the asymptotic distribution of an appropriately normalized queue size is determined. This time it turns out to have a rational Laplace transform with simple poles. In both cases, the relevant parameters are easily computable.     

Heavy Tails in Multi-Server Queue

In this paper, the asymptotic behaviour of the distribution tail of the stationary waiting time W in the GI/GI/2 FCFS queue is studied. Under subexponential-type assumptions on the service time distribution, bounds and sharp asymptotics are given for the probability P{W > x}. We also get asymptotics for the distribution tail of a stationary two-dimensional workload vector and of a stationary queue length. These asymptotics depend heavily on the traffic load. AMS subject classification: 60K25     

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).     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Unconditional Sojourn Time Distribution in the Queue GI/M/1-K with Processor Sharing Service

We consider a processor shared GI/M/1 queue which can accommodate a finite number K of customers. Using singular perturbation techniques, we construct asymptotic expansions for the distribution of a tagged customer's sojourn time. We assume that K is large and treat several different cases of the model parameters.     

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.     

Queues with random back-offs

We consider a broad class of queueing models with random state-dependent vacation periods, which arise in the analysis of queue-based back-off algorithms in wireless random-access networks. In contrast to conventional models, the vacation periods may be initiated after each service completion, and can be randomly terminated with certain probabilities that depend on the queue length. We first present exact queue-length and delay results for some specific cases and we derive stochastic bounds for a much richer set of scenarios. Using these, together with stochastic relations between systems with different vacation disciplines, we examine the scaled queue length and delay in a heavy-traffic regime, and demonstrate a sharp trichotomy, depending on how the activation rate and vacation probability behave as function of the queue length. In particular, the effect of the vacation periods may either (i) completely vanish in heavy-traffic conditions, (ii) contribute an additional term to the queue lengths and delays of similar magnitude, or even (iii) give rise to an order-of-magnitude increase. The heavy-traffic trichotomy provides valuable insight into the impact of the back-off algorithms on the delay performance in wireless random-access networks.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

A retrial model in a nonstationary regime

Summary In this article we analyze a retrial queuing system where customers in the orbit join a queue with FCFS discipline. We adopt a nonstationary regime. We derive some probabilities using the theory of semiregenerative processes. We obtain an integral estimation for the difference between blocking probabilities in stationary and nonstationary regimes.     

Heavily loaded queue coupled to two underloaded queues

We consider a system of three parallel queues with Poisson arrivals and exponentially distributed service requirements. The service rate for the heavily loaded queue depends on which of the two underloaded queues are empty. We derive the lowest-order asymptotic approximation to the joint stationary distribution of the queue lengths, in terms of a small parameter measuring the closeness of the heavily loaded queue to instability. To this order the queue lengths are independent, and the underloaded queues and the heavily loaded queue have geometrically and, after suitable scaling, exponentially distributed lengths, respectively. The expression for the exponential decay rate for the heavily loaded queue involves the solution to an inhomogeneous linear functional equation. Explicit results are obtained for this decay rate when the two underloaded queues have vastly different arrival and service rates.     

Corrected asymptotics for a multi-server queue in the Halfin-Whitt regime

To investigate the quality of heavy-traffic approximations for queues with many servers, we consider the steady-state number of waiting customers in an M/D/s queue as s→∞. In the Halfin-Whitt regime, it is well known that this random variable converges to the supremum of a Gaussian random walk. This paper develops methods that yield more accurate results in terms of series expansions and inequalities for the probability of an empty queue, and the mean and variance of the queue length distribution. This quantifies the relationship between the limiting system and the queue with a small or moderate number of servers. The main idea is to view the M/D/s queue through the prism of the Gaussian random walk: as for the standard Gaussian random walk, we provide scalable series expansions involving terms that include the Riemann zeta function.      

Optimality of routing and servicing in dependent parallel processing systems

In a system of dependent, parallel processing service stations, when is it optimal to route customers to the shortest queue and to devote auxiliary capacity to serve the longest queue? We show that this RSQ/SLQ policy is optimal for a wide class of Markovian systems, where the arrival and service rates at the stations, which may depend on the numbers of customers at all the stations, satisfy certain symmetry and monotonicity conditions. Under this policy, the queue lengths will be stochastically smaller in the weak submajorization ordering than the queue lengths under any other policy. Furthermore, this policy minimizes standard discounted and average cost functionals over finite and infinite horizons.     

Asymptotic analysis for closed multichain queueing networks with bottlenecks

We consider a two-chain exponential queueing network with a large number of customers that consists of one infinite-server (IS) station and two processor-sharing (PS) or FCFS single-server stations. The asymptotic behavior of the partition function is studied for such a network when one or both PS (FCFS) nodes are heavily loaded. The results are derived using methods of multidimensional complex analysis (the theory of homologies and residues) and the saddle-point method.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

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.     

Rare event asymptotics for a random walk in the quarter plane

This paper presents a novel technique for deriving asymptotic expressions for the occurrence of rare events for a random walk in the quarter plane. In particular, we study a tandem queue with Poisson arrivals, exponential service times and coupled processors. The service rate for one queue is only a fraction of the global service rate when the other queue is non-empty; when one queue is empty, the other queue has full service rate. The bivariate generating function of the queue lengths gives rise to a functional equation. In order to derive asymptotic expressions for large queue lengths, we combine the kernel method for functional equations with boundary value problems and singularity analysis.