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 BMAP/G/1 Retrial Queue with a Server Subject to Breakdowns and Repairs

In this paper, we consider a BMAP/G/1 retrial queue with a server subject to breakdowns and repairs, where the life time of the server is exponential and the repair time is general. We use the supplementary variable method, which combines with the matrix-analytic method and the censoring technique, to study the system. We apply the RG-factorization of a level-dependent continuous-time Markov chain of M/G/1 type to provide the stationary performance measures of the system, for example, the stationary availability, failure frequency and queue length. Furthermore, we use the RG-factorization of a level-dependent Markov renewal process of M/G/1 type to express the Laplace transform of the distribution of a first passage time such as the reliability function and the busy period.     

Exact Convergence Rate for the Distributions of GI/M/c/K Queue as K Tends to Infinity

We obtain the exact convergence rate of the stationary distribution ^(K) of the embedded Markov chain in GI/M/c/K queue to the stationary distribution of the embedded Markov chain in GI/M/c queue as K. Similar result for the time-stationary distributions of queue size is also included. These generalize Choi and Kim's results of the case c=1 by nontrivial ways. Our results also strengthen the Simonot's results [5].     

Transient and Stationary Distributions for the GI/G/k Queue with Lebesgue-Dominated Inter-Arrival Time Distribution

In this paper, the multi-server queue with general service time distribution and Lebesgue-dominated iid inter-arival times is analyzed. This is done by introducing auxiliary variables for the remaining service times and then examining the embedded Markov chain at arrival instants. The concept of piecewise-deterministic Markov processes is applied to model the inter-arrival behaviour. It turns out that the transition probability kernel of the embedded Markov chain at arrival instants has the form of a lower Hessenberg matrix and hence admits an operator–geometric stationary distribution. Thus it is shown that matrix–analytical methods can be extended to provide a modeling tool even for the general multi-server queue.     

The MAP/PH/N retrial queue in a random environment

We consider the MAP/PH/N retrial queue with a finite number of sources operating in a finite state Markovian random environment. Two different types of multi-dimensional Markov chains are investigated describing the behavior of the system based on state space arrangements. The special features of the two formulations are discussed. The algorithms for calculating the stationary state probabilities are elaborated, based on which the main performance measures are obtained, and numerical examples are presented as well.     

Analysis of the finite source MAP/PH/N retrial G-queue operating in a random environment

Finite source retrial G-queues are good mathematical models of communication systems and networks, so their investigation is important for theory and applications. In this paper, we analyze the MAP/PH/N retrial queue with finite number of sources and MAP arrivals of negative customers operating in a finite state Markovian random environment. The arrival of a negative customer with equal probability goes to any busy server to remove the customer being in service. The multi-dimensional Markov chain describing the behavior of the system is investigated. The algorithms for calculating the stationary state probabilities are elaborated. Main performance measures are obtained. Illustrative numerical examples are presented.     

Algorithmic approximations for the busy period distribution of the M/M/c retrial queue

In this paper we deal with the main multiserver retrial queue of M/M/c type with exponential repeated attempts. This model is known to be analytically intractable due to the spatial heterogeneity of the underlying Markov chain, caused by the retrial feature. For this reason several models have been proposed for approximating its stationary distribution, that lead to satisfactory numerical implementations. This paper extends these studies by developing efficient algorithmic procedures for calculating the busy period distribution of the main approximation models of Wilkinson [Wilkinson, R.I., 1956. Theories for toll traffic engineering in the USA, The Bell System Technical Journal 35, 421–514], Falin [Falin, G.I., 1983. Calculations of probability characteristics of a multiline system with repeated calls, Moscow University Computational Mathematics and Cybernetics 1, 43–49] and Neuts and Rao [Neuts, M.F., Rao, B.M., 1990. Numerical investigation of a multiserver retrial model, Queueing Systems 7, 169–190]. Moreover, we develop stable recursive schemes for the computation of the busy period moments. The corresponding distributions for the total number of customers served during a busy period are also studied. Several numerical results illustrate the efficiency of the methods and reveal interesting facts concerning the behavior of the M/M/c retrial queue.     

Estimating Joint Distributions of Markov Chains

Suppose we observe a stationary Markov chain with unknown transition distribution. The empirical estimator for the expectation of a function of two successive observations is known to be efficient. For reversible Markov chains, an appropriate symmetrization is efficient. For functions of more than two arguments, these estimators cease to be efficient. We determine the influence function of efficient estimators of expectations of functions of several observations, both for completely unknown and for reversible Markov chains. We construct simple efficient estimators in both cases.     

Retrial queues with collision arising from unslottedCSMA/CD protocol

We consider a retrial queueing model with collision arising from the specific communication protocolCSMAICD. Under the retrial control policy in which the retrial rate is inversely proportional to the number of customers in the retrial group, we derive the generating function of the limiting distribution of the number of customers in the retrial group at the moment when the channel is free. Using the theory of Markov regenerative processes, we also obtain the limiting distribution of the number of customers in the system at arbitrary time points.This paper was supported in part by the Non-Directed Research Fund, Korea Research Foundation, 1990.     

On the class of Markov chains with finite convergence time

We study the necessary and sufficient conditions for a finite ergodic Markov chain to converge in a finite number of transitions to its stationary distribution. Using this result, we describe the class of Markov chains which attain the stationary distribution in a finite number of steps, independent of the initial distribution. We then exhibit a queueing model that has a Markov chain embedded at the points of regeneration that falls within this class. Finally, we examine the class of continuous time Markov processes whose embedded Markov chain possesses the property of rapid convergence, and find that, in the case where the distribution of sojourn times is independent of the state, we can compute the distribution of the system at time t in the form of a simple closed expression.     

A G/M/1-queue with exponential retrial

Summary We consider a G/M/1 retrial model in which the delays between retrials are i.i.d. exponentially distributed random variables. We investigate the steady-state distribution of the embedded Markov chain at completion service epochs, the stationary distribution at anytime and the virtual waiting time.     

Algorithmic analysis of the Geo/Geo/c retrial queue

In this paper, we consider a discrete-time queue of Geo/Geo/c type with geometric repeated attempts. It is known that its continuous counterpart, namely the M/M/c queue with exponential retrials, is analytically intractable due to the spatial heterogeneity of the underlying Markov chain, caused from the retrial feature. In discrete-time, the occurrence of multiple events at each slot increases the complexity of the model and raises further computational difficulties. We propose several algorithmic procedures for the efficient computation of the main performance measures of this system. More specifically, we investigate the stationary distribution of the system state, the busy period and the waiting time. Several numerical examples illustrate the analysis.     

Computation of the steady state distribution for multi-server retrial queues with phase type service process

We consider a multi-server retrial queueing system with the Batch Markovian Arrival Process and phase type service time distribution. Such a general queueing system suits for modeling and decision making in many real life objects including modern wireless communication networks. Behavior of such a system is described by the level dependent multi-dimensional Markov chain. Blocks of the generator of this chain, which is the block structured matrix of infinite size, can have large size if the number of servers is large and distribution of service time is not exponential. Due to this fact, the existing in literature algorithms allow to compute key performance measures of such a system only for a small number of servers. Here we describe the algorithm that allows to compute the stationary distribution of the system for larger number of servers and numerically illustrate its advantage. Importance of taking into account correlation in the arrival process is numerically demonstrated.     

Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory

Multi-dimensional asymptotically quasi-Toeplitz Markov chains with discrete and continuous time are introduced. Ergodicity and non-ergodicity conditions are proven. Numerically stable algorithm to calculate the stationary distribution is presented. An application of such chains in retrial queueing models with Batch Markovian Arrival Process is briefly illustrated. AMS Subject Classifications Primary 60K25 · 60K20     

Comparison of Three Web Search Algorithms

In this paper we discuss three important kinds of Markov chains used in Web search algorithms-the maximal irreducible Markov chain, the miuimal irreducible Markov chain and the middle irreducible Markov chain, We discuss the stationary distributions, the convergence rates and the Maclaurin series of the stationary distributions of the three kinds of Markov chains. Among other things, our results show that the maximal and minimal Markov chains have the same stationary distribution and that the stationary distribution of the middle Markov chain reflects the real Web structure more objectively. Our results also prove that the maximal and middle Markov chains have the same convergence rate and that the maximal Markov chain converges faster than the minimal Markov chain when the damping factor α 〉1/√2.     

Steady-state analysis of M/M/c/c-type retrial queueing systems with constant retrial rate

The paper deals with a research of bivariate Markov process \(\{X(t), t\ge 0\}\) whose state space is a lattice semistrip \(S(X)=\{0,1,{\ldots },c\} \times Z_{+}\). The process \(\{X(t), t\ge 0\}\) describes the service policy of a multi-server retrial queue in which the rate of repeated flow does not depend on the number of sources of retrial calls. In this class of queues, a vector–matrix representation of steady-state distribution was obtained. This representation allows to write down the stationary probabilities through the model parameters in closed form and to propose the closed formulas of its main performance measures. The investigative techniques use an approximation of the initial model by means of the truncated one and the direct passage to the limit.     

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.      

马氏链平稳分布存在与唯一性的简洁证明与计算

本文考虑可数状态离散时间齐次马氏链平稳分布的存在与唯一性.放弃以往大多数文献中要求马氏链是不可约,正常返且非周期(即遍历)的条件,本文仅需要马氏链是不可约和正常返的(但可能是周期的,因而可能是非遍历的).在此较弱的条件下,本文不仅给出了平稳分布存在与唯一性的简洁证明,而且还给出了平稳分布的计算方法.     

Retrial queue with discipline of adaptive permanent pooling

A novel customer service discipline for a single-server retrial queue is proposed and analysed. Arriving customers are accumulated in a pool of finite capacity. Customers arriving when the pool is full go into orbit and attempt to access the service later. It is assumed that customers access the service as a group. The size of the group is defined by the number of customers in the pool at the instant the service commences. All customers within a group finish receiving the service simultaneously. If the pool is full at the point the service finishes, a new service begins immediately and all customers from the pool begin to be served. Otherwise, the customer admission period starts. The duration of this period is random and depends on the number of customers in the pool when the admission period begins. However, if the pool becomes full before the admission period expires, this period is terminated and a new service begins. The system behaviour is described by a multi-dimensional Markov chain. The generator and the condition of ergodicity of this Markov chain are derived, and an algorithm for computing the stationary probability distribution of the states of the Markov chain is given. Formulas for computing various performance measures of the system are presented, and the results of numerical experiments show that these measures essentially depend on the capacity of the pool and the distribution of the duration of the admission period. The advantages of the proposed customer service discipline over the classical discipline and the discipline in which customers cannot enter the pool during the service period are illustrated numerically.     

Inverse problems for ergodicity of Markov chains

For continuous-time Markov chains, we provide criteria for non-ergodicity, non-algebraic ergodicity, non-exponential ergodicity, and non-strong ergodicity. For discrete-time Markov chains, criteria for non-ergodicity, non-algebraic ergodicity, and non-strong ergodicity are given. Our criteria are in terms of the existence of solutions to inequalities involving the Q-matrix (or transition matrix P in time-discrete case) of the chain. Meanwhile, these practical criteria are applied to some examples, including a special class of single birth processes and several multi-dimensional models.