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.     

Large Closed Queueing Networks in Semi-Markov Environment and Their Application

The paper studies closed queueing networks containing a server station and k client stations. The server station is an infinite server queueing system, and client stations are single-server queueing systems with autonomous service, i.e. every client station serves customers (units) only at random instants generated by a strictly stationary and ergodic sequence of random variables. The total number of units in the network is N. The expected times between departures in client stations are (N μ _j )⁻¹. After a service completion in the server station, a unit is transmitted to the jth client station with probability p _j (j=1,2,…,k), and being processed in the jth client station, the unit returns to the server station. The network is assumed to be in a semi-Markov environment. A semi-Markov environment is defined by a finite or countable infinite Markov chain and by sequences of independent and identically distributed random variables. Then the routing probabilities p _j (j=1,2,…,k) and transmission rates (which are expressed via parameters of the network) depend on a Markov state of the environment. The paper studies the queue-length processes in client stations of this network and is aimed to the analysis of performance measures associated with this network. The questions risen in this paper have immediate relation to quality control of complex telecommunication networks, and the obtained results are expected to lead to the solutions to many practical problems of this area of research.      

Exact asymptotics for the stationary distribution of a Markov chain: a production model

We derive rough and exact asymptotic expressions for the stationary distribution π of a Markov chain arising in a queueing/production context. The approach we develop can also handle “cascades,” which are situations where the fluid limit of the large deviation path from the origin to the increasingly rare event is nonlinear. Our approach considers a process that starts at the rare event. In our production example, we can have two sequences of states that asymptotically lie on the same line, yet π has different asymptotics on the two sequences.     

Stability analysis of parallel server systems under longest queue first

We consider the stability of parallel server systems under the longest queue first (LQF) rule. We show that when the underlying graph of a parallel server system is a tree, the standard nominal traffic condition is sufficient for the stability of that system under LQF when interarrival and service times have general distributions. Then we consider a special parallel server system, which is known as the X-model, whose underlying graph is not a tree. We provide additional “drift” conditions for the stability and transience of these queueing systems with exponential interarrival and service times. Drift conditions depend in general on the stationary distribution of an induced Markov chain that is derived from the underlying queueing system. We illustrate our results with examples and simulation experiments. We also demonstrate that the stability of the LQF depends on the tie-breaking rule used and that it can be unstable even under arbitrary low loads.     

Switching stochastic models and applications in retrial queues

Some special classes of Switching Processes such as Recurrent Processes of a Semi-Markov type and Processes with Semi-Markov Switches are introduced. Limit theorems of Averaging Principle and Diffusion Approximation types are given. Applications to the asymptotic analysis of overloading state-dependent Markov and semi-Markov queueing modelsM _SM,Q /M _SM,Q /1/∞ and retrial queueing systemsM/G/1/w.r in transient conditions are studied. The paper was supported by INTAS Project 96-0828     

Heavy traffic analysis of M/G/1 type queueing systems with Markov-modulated arrivals

M/G/1 type queueing systems whose arrival rate is a function of an independent continuous time Markov chain are considered. We suggest a simple analytical approach which allows rigorous mathematical analysis of the stationary characteristics under heavy traffic. Their asymptotic behaviour is described in terms of characteristics of the modulating process (defined as a solution of a set of linear algebraic equations). The analysis is based on certain “semi-explicit” formulas for the performance characteristics. This research was supported by INTAS under grant No. 96-0828.     

Fluid approximation of a controlled multiclass tandem network

A two-station, four-class queueing network with dynamic scheduling of servers is analyzed. It is shown that the corresponding Markov decision problem converges under fluid scaling to a fluid optimal control model. The structure of the optimal policy for the fluid network, and of an asymptotically optimal policy for the queueing network are derived in an explicit form. They concur with the tandem μ-rule, if this policy gives priority to the same flow of customers in both stations. In general, they are monotone with a linear switching surface. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the M/G/1 retrial queueing system with linear control policy

Summary This paper is concerned with the study of a newM/G/1 retrial queueing system in which the delays between retrials are exponentially distributed random variables with linear intensityg(n)=α+nμ, when there aren≥1 customers in the retrial group. This new retrial discipline will be calledlinear control policy. We carry out an extensive analysis of the model, including existence of stationary regime, stationary distribution of the embedded Markov chain at epochs of service completions, joint distribution of the orbit size and the server state in steady state and busy period. The results agree with known results for special cases.     

A queueing system with linear repeated attempts,bernoulli schedule and feedback

We analyse a single-server retrial queueing system with infinite buffer, Poisson arrivals, general distribution of service time and linear retrial policy. If an arriving customer finds the server occupied, he joins with probabilityp a retrial group (called orbit) and with complementary probabilityq a priority queue in order to be served. After the customer is served completely, he will decide either to return to the priority queue for another service with probability ϑ or to leave the system forever with probability =1−ϑ, where 0≤ϑ<1. We study the ergodicity of the embedded Markov chain, its stationary distribution function and the joint generating function of the number of customers in both groups in the steady-state regime. Moreover, we obtain the generating function of system size distribution, which generalizes the well-knownPollaczek-Khinchin formula. Also we obtain a stochastic decomposition law for our queueing system and as an application we study the asymptotic behaviour under high rate of retrials. The results agree with known special cases. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

On the Full Idle Time in Multiphase Queueing Systems

The modern queueing theory is a powerful tool for a quantitative and qualitative analysis of communication systems, computer networks, transportation systems, and many other technical systems. The paper is designated to the analysis of queueing systems arising in the network theory and communications theory (such as the so-called multiphase queueing systems, tandem queues, or series of queueing systems). We present heavy traffic limit theorems for the full idle time in multiphase queueing systems. We prove functional limit theorems for values of the full idle time of a queueing system, which is its important probability characteristic. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 367–386, July–September, 2005.     

Queues with hysteretic control by vacation and post-vacation periods

The paper investigates the queueing process in stochastic systems with bulk input, batch state dependent service, server vacations, and three post-vacation disciplines. The policy of leaving and entering busy periods is hysteretic, meaning that, initially, the server leaves the system on multiple vacation trips whenever the queue falls below r (⩾1), and resumes service when during his absence the system replenishes to N or more customers upon one of his returns. During his vacation trips, the server can be called off on emergency, limiting his trips by a specified random variable (thereby encompassing several classes of vacation queues, such as ones with multiple and single vacations). If by then the queue has not reached another fixed threshold M (⩽ N), the server enters a so-called “post-vacation period” characterized by three different disciplines: waiting, or leaving on multiple vacation trips with or without emergency. For all three disciplines, the probability generating functions of the discrete and continuous time parameter queueing processes in the steady state are obtained in a closed analytic form. The author uses a semi-regenerative approach and enhances fluctuation techniques (from his previous studies) preceding the analysis of queueing systems. Various examples demonstrate and discuss the results obtained. This revised version was published online in June 2006 with corrections to the Cover Date.     

Regularly varying tails in a queue with discrete autoregressive arrivals of order p

We consider a discrete time single server queueing system where the service time of a customer is one slot, and the arrival process is governed by a discrete autoregressive process of order p (DAR(p)). For this queueing system, we investigate the tail behavior of the queue size and the waiting time distributions. Specifically, we show that if the stationary distribution of DAR(p) input has a tail of regular variation with index −β−1, then the stationary distributions of the queue size and the waiting time have tails of regular variation with index −β. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

On exponential ergodicity of multiclass queueing networks

One of the key performance measures in queueing systems is the decay rate of the steady-state tail probabilities of the queue lengths. It is known that if a corresponding fluid model is stable and the stochastic primitives have finite moments, then the queue lengths also have finite moments, so that the tail probability ℙ(⋅>s) decays faster than s ⁻ⁿ for any n. It is natural to conjecture that the decay rate is in fact exponential.     

Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K]/PH[K]/N/LCFS non-preemptive queue

This paper studies a multi-server queueing system with multiple types of customers and last-come-first-served (LCFS) non-preemptive service discipline. First, a quasi-birth-and-death (QBD) Markov process with a tree structure is defined and some classical results of QBD Markov processes are generalized. Second, the MMAP[K]/PH[K]/N/LCFS non-preemptive queue is introduced. Using results of the QBD Markov process with a tree structure, explicit formulas are derived and an efficient algorithm is developed for computing the stationary distribution of queue strings. Numerical examples are presented to show the impact of the correlation and the pattern of the arrival process on the queueing process of each type of customer.     

A semidefinite optimization approach to the steady-state analysis of queueing systems

Obtaining (tail) probabilities from a transform function is an important topic in queueing theory. To obtain these probabilities in discrete-time queueing systems, we have to invert probability generating functions, since most important distributions in discrete-time queueing systems can be determined in the form of probability generating functions. In this paper, we calculate the tail probabilities of two particular random variables in discrete-time priority queueing systems, by means of the dominant singularity approximation. We show that obtaining these tail probabilities can be a complex task, and that the obtained tail probabilities are not necessarily exponential (as in most ‘traditional’ queueing systems). Further, we show the impact and significance of the various system parameters on the type of tail behavior. Finally, we compare our approximation results with simulations.     

The acquisition queue

We propose a new queueing model named the acquisition queue. It differs from conventional queueing models in that the server not only serves customers, but also performs acquisition of new customers. The server has to divide its energy between both activities. The number of newly acquired customers is uncertain, and the effect of the server’s acquisition efforts can only be seen after some fixed time period δ (delay). The acquisition queue constitutes a (δ+1)-dimensional Markov chain. The limiting queue length distribution is derived in terms of its probability generating function, and an exact expression for the mean queue length is given. For large values of δ the numerical procedures needed for calculating the mean queue length become computationally cumbersome. We therefore complement the exact expression with a fluid approximation. One of the key features of the acquisition queue is that the server performs more acquisition when the queue is small. Together with the delay, this causes the queue length process to show a strongly cyclic behavior. We propose and investigate several ways of planning the acquisition efforts. In particular, we propose an acquisition scheme that is designed specifically to reduce the cyclic behavior of the queue length process. This research was financially supported by the European Network of Excellence Euro-NGI. The work of the second author was supported in part by a TALENT grant from the Netherlands Organisation for Scientific Research (NWO).     

Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.      

The limit distribution for the emptying times of a single-channel queueing system with Markov arrival stream admitting consolidation of states

We study the limit behavior of the emptying times of anM _r /G/1/n single-channel queueing system under heavy load conditions. It is assumed that the arrival stream is governed by a Markov chain admitting state consolidation.Translated fromTeoriya Sluchaínykh Protsessov, Vol. 14, pp. 55–61, 1986.