Retrial queues with server subject to breakdowns and repairs

In this paper we consider a single server retrial queue where the server is subject to breakdowns and repairs. New customers arrive at the service station according to a Poisson process and demand i.i.d. service times. If the server is idle, the incoming customer starts getting served immediately. If the server is busy, the incoming customer conducts a retrial after an exponential amount of time. The retrial customers behave independently of each other. The server stays up for an exponential time and then fails. Repair times have a general distribution. The failure/repair behavior when the server is idle is different from when it is busy. Two different models are considered. In model I, the failed server cannot be occupied and the customer whose service is interrupted has to either leave the system or rejoin the retrial group. In model II, the customer whose service is interrupted by a failure stays at the server and restarts the service when repair is completed. Model II can be handled as a special case of model I. For model I, we derive the stability condition and study the limiting behavior of the system by using the tools of Markov regenerative processes.Visiting from Department of Applied Mathematics, Korea Advanced Institute of Science and Technology, Cheongryang, Seoul, Korea.     

Flow time distributions in aK classM/G/1 priority feedback queue

In this paper, aK classM/G/1 queueing system with feedback is examined. Each arrival requires at least one, and possibly up toK service phases. A customer is said to be in classk if it is waiting for or receiving itskth phase of service. When a customer finishes its phasek ≤K service, it either leaves the system with probabilityp _k, or it instantaneously reenters the system as a classk + 1 customer with probability (1 −p _k). It is assumed thatp _k = 1. Service is non-preemptive and FCFS within a specified priority ordering of the customer classes. Level crossing analysis of queues and delay cycle results are used to derive the Laplace-Stieltjes Transform (LST) for the PDF of the sojourn time in classes 1,…,k;k ≤K.     

Waiting time analysis of a two-stage queueing system with priorities

A two-stage queueing system with two types of customers and non-preemptive priorities is analyzed. There is no waiting space between stages and so the blocking phenomenon is observed. The arrivals follow a Poisson distribution for the high priority customers and a gamma distribution for the low priority customers, while all service times are arbitrarily distributed. We derive expressions for the Laplace transform of the waiting time density of a low priority customer both in the transient and the steady state.     

Explicit Convergence Rates of the Embedded M/G/1 Queue

This paper investigates the explicit convergence rates to the stationary distribution π of the embedded M/G/1 queue; specifically, for suitable rate functions r（n） which may be polynomial with r（n） = n^l, l 〉 0 or geometric with r（n） = α^n, a 〉 1 and ＂moments＂ f ≥ 1, we find the conditions under which Σ∞n=0 r（n）｜｜P^n（i,·） - π（·）｜｜f ≤ M（i） for all i ∈ E. For the polynomial case, the explicit bounds on M（i） are given in terms of both ＂drift functions＂ and behavior of the first hitting time on the state O; and for the geometric case, the largest geometric convergence rate α＊ is obtained.     

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.      

Analysis of IEEE 802.11 non-saturated DCF by matrix analytic methods

In the IEEE 802.11 MAC layer protocol, the basic access method is the Distributed Coordination Function based on the CSMA/CA. In this paper, we investigate the analytic performance of IEEE 802.11 DCF in the non-saturation mode. We assume that there is a fixed number n of competing stations and the packet arrival process to each station is a Poisson process. We model IEEE 802.11 DCF in non-saturation mode by a 3-dimensional Markov chain and derive the steady state probability of the Markov chain by applying the matrix analytic method. We obtain the probability generating function of Head-of-Line delay (HoL-delay), non-saturation throughput and packet loss probability. Our results can be used for finding the optimal number of stations that can be accommodated while satisfying a given QoS requirement. This research is 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).     

Optimal threshold policies in a two-class preemptive priority queue with admission and termination control

We consider a two-class 1 preemptive priority queue in which there are two essential, on-line decisions that have to be taken. The first is the decision to either accept or reject new type-1 or type-2 jobs. The second is the decision to abort jobs, i.e., to remove any type-1 or type-2 jobs from the system. We show that there exist optimal threshold policies for these two types of, decisions.     

An analytical solution for a tandem queue with blocking

The model considered in this paper involves a tandem queue with two waiting lines, and as soon as the second waiting line reaches a certain upper limit, the first line is blocked. Both lines have exponential servers, and arrivals are Poisson. The objective is to determine the joint distribution of both lines in equilibrium. This joint distribution is found by using generalized eigenvalues. Specifically, a simple formula involving the cotangent is derived. The periodicity of the cotangent is then used to determine the location of the majority of the eigenvalues. Once all eigenvalues are found, the eigenvectors can be obtained recursively. The method proposed has a lower computational complexity than all other known methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the output process of an M/M/1 queue with randomly varying system parameters

In this paper an analysis of the output process from an M/M/1 queue where the arrival and service rates vary randomly is presented. The results include expressions for the mean, variance and distribution of the interdeparture interval, the joint density function of two successive interdeparture intervals and their correlation. An interesting feature of the results is that the moments of the interdeparture time are expressed in terms of the expected times to first and second departures from an arbitrary point in time.     

Modelling and analysis of M/G a,b /1/N queue – A simple alternative approach

In this paper, we consider a single-server finite-capacity queue with general bulk service rule where customers arrive according to a Poisson process and service times of the batches are arbitrarily distributed. The queue is analyzed using both the supplementary variable and imbedded Markov chain techniques. The relations between state probabilities at departure and arbitrary epochs have been presented in explicit forms.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

The efficiency of two indexed priority queue algorithms

Two priority queue algorithms, a linked linear sublist and ap-subtree algorithm, are analysed. Both of them use a search index that speeds up finding the correct sublist/subtree. In most cases the methods require a short processing time for the so-called HOLD-operation of the discrete event simulation. The relative power of the algorithms depends on the ratior of the total number of elements in the queue and the size of the search index. For large values ofr (16) thep-subtree algorithm is to be preferred. However, the more primitive data structure used by the sublist algorithm makes it possible to use a larger index leading to a smaller ratior.     

A simple proof for the constructions of optical priority queues

Constructions of optical queues by optical Switches and fiber Delay Lines (SDL) have received a lot of attention lately. In this short paper, we provide a simple proof for the construction of a priority queue with a switch and fiber delay lines in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006). Our proof not only gives the insights needed to understand why such a construction works, but also leads to a more general result that recovers the result in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006) as a special case. This research was supported in part by the National Science Council, Taiwan, ROC, under Contract NSC-93-2213-E-007-040, Contract NSC-93-2213-E-007-095, Contract NSC-94-2213-E-007-046, and the Program for Promoting Academic Excellence of Universities NSC 94-2752-E-007-002-PAE.     

Analyzing priority queues with 3 classes using tree-like processes

In this paper we demonstrate how tree-like processes can be used to analyze a general class of priority queues with three service classes, creating a new methodology to study priority queues. The key result is that the operation of a 3-class priority queue can be mimicked by means of an alternate system that is composed of a single stack and queue. The evolution of this alternate system is reduced to a tree-like Markov process, the solution of which is realized through matrix analytic methods. The main performance measures, i.e., the queue length distributions and loss rates, are obtained from the steady state of the tree-like process through a censoring argument. The strength of our approach is demonstrated via a series of numerical examples. AMS Subject Classifications Primary—60K25; Secondary—60M20, 90B22     

Workload in queues having priorities assigned according to service time

System designers often implement priority queueing disciplines in order to improve overall system performance; however, improvement is often gained at the expense of lower priority cystomers. Shortest Processing Time is an example of a priority discipline wherein lower priority customers may suffer very long waiting times when compared to their waiting times under a democratic service discipline. In what follows, we shall investigate a queueing system where customers are divided into a finitie number of priority classes according to their service times.We develop the multivariate generating function characterizing the joint workload among the priority classes. First moments obtained from the generating function yield traffic intensities for each priority class. Second moments address expected workloads, in particular, we obtain simple Pollaczek-Khinchine type formulae for the classes. Higher moments address variance and covariance among the workloads of the priority classes.This work was supported in part by National Science Foundation Grant DDM-8913658.     

二叉树上分支马氏链的等价性质

本文给出了二叉树上分支马氏链定义的离散形式,然后研究了它的两个等价性质.最后,我们指出在二叉树情况下,树指标马氏链就是一类特殊的分支马氏链.     

三叉树上分支马氏链的等价性质

在二叉树上分支马氏链的等价性质研究的基础上,给出了三叉树上分支马氏链定义的离散形式,除了把二叉树上分支马氏链的两个等价性质平移到三叉树上分支马氏链以外,又给出了三叉树上分支马氏链的两个等价性质及两个性质.得出结论的关键方法是在概率乘积公式及条件概率公式的计算中正确处理其中所涉及到的许多繁杂的必然事件.     

Transient solutions of Markov processes and generalized continued fractions

In 1974 J. A. Murphy and M. R. O'Donohoe numerically approximatedthe minimal solution of the Kolmogorov forward equation forthe generalized birth and death process by use of continuedfractions. This paper generalizes this approach by suggestingan algorithm for q-matrices of lower band structure (n, 1).This is achieved by analogy with generalized continued fractions.Applications involving q-matrices of this type include, forexample, many types of queueing systems with batch processingor birth–death–catastrophe population processesin biology.     

On multiple Markov chains

The aim of this paper is to examine multiple Markov dependence for the discrete as well as for the continuous parameter case. In both cases the Markov property with arbitrary parameter values is investigated and it is shown that it leads to the degeneration of the multiple Markov dependence to the simple one.     

马氏环境中马氏链的Poisson极限律

本文研究了马氏环境中马氏链,证明了该过程于小柱集上的回返次数是渐近地服从Poisson分布的,同时还给出了该过程是(?)-混合的一个充分条件以及过程回返于小柱集之概率的一个指数估计式.