Sojourn time distribution in a MAP/M/1 processor-sharing queue

This paper considers the sojourn time distribution in a processor-sharing queue with a Markovian arrival process and exponential service times. We show a recursive formula to compute the complementary distribution of the sojourn time in steady state. The formula is simple and numerically feasible, and enables us to control the absolute error in numerical results. Further, we discuss the impact of the arrival process on the sojourn time distribution through some numerical examples.     

Sojourn time problems in feedback queues

A brief survey of the literature on sojourn time problems in single node feedback queueing systems is presented. The derivation of the distribution and moments of the sojourn time of a typical customer in a Markov renewal queue with state dependent feedback is considered in depth. The techniques used relate to the derivation of a first passage time distribution in a particular Markov renewal process. These results are applied to birth-death queues with state dependent feedback. For such models an alternative approach using the theory of Markov chains in continuous time is also examined.     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

Asymptotics for the sojourn time distribution in the queue defined by a general QBD process with a countable phase space

We consider a FIFO queue defined by a QBD process. When the number of phases of the QBD process is finite, it has been proved that the stationary distribution of sojourn times in that queue can be represented as a phase-type distribution. In this paper, we extend this result to the case where the number of phases of the QBD process is countably many and obtain several kinds of asymptotic formula for the steady-state tail probability of sojourn times in the queue when the tail probability decays in exact exponential form.     

Transient and periodic solution to the time-inhomogeneous quasi-birth death process

We derive the transient distribution and periodic family of asymptotic distributions and the transient and periodic moments for the quasi-birth-and-death processes with time-varying periodic rates. The distributions and moments are given in terms of integral equations involving the related random-walk process. The method is a straight-forward application of generating functions.      

Sojourn time analysis of a two-phase queueing system with exhaustive batch-service and its vacation model

We consider an M/G/1-type, two-phase queueing system, in which the two phases in series are attended alternatively and exhaustively by a moving single-server according to a batch-service in the first phase and an individual service in the second phase. We show that the two-phase queueing system reduces to a new type of single-vacation model with non-exhaustive service. Using a double transform for the joint distribution of the queue length in each phase and the remaining service time, we derive Laplace-Stieltjes transforms for the sojourn time in each phase and the total sojourn time in the system. Furthermore, we provide the moment formula of sojourn times and numerical examples of an approximate density function of the total sojourn time.     

Block-Structured Fluid Queues Driven by QBD Processes

Abstract

In this paper, a unified approach for studying block-structured fluid models is proposed by means of the RG-factorization. When the stochastic environment (or background) is assumed to be a quasi-birth-and death (QBD) process, with either infinitely many levels or finitely many levels, the Laplace transform for the stationary probability distribution of the buffer content is expressed in terms of the R-measure. At the same time, the Laplace-Stieltjes transforms for both the conditional distribution and the conditional mean of a first passage time in such a fluid queue are derived by the same approach.     

Sojourn time distributions for the M/M/1 queue in a Markovian environment

In this paper, we study a single server queue in which both the arrival rate and service rate depend on the state of an external Markov process (called the environment) with a finite state space. Given that the environment is in state j, the mean arrival and service rates are λ_j and μ_j respectively. For such a queue, the queue length distribution is known to be matrix geometric. In this paper, we characterize the Laplace-Stieltjes transform of the sojourn time distribution under four disciplines - last come first served preemptive resume, last come first served, processor sharing and round robin. We also discuss a potential application of this queue in the are of data communication.     

Approximating queue size and waiting time distributions in general polling systems

Polling system models are extensively used to model a large variety of computer and communication networks as well as production and service systems in which multiple customer classes or a number of distinct items compete for the capacity of a common server or production facility. In this paper we describe an efficient approximation method for the steady state distributions of the queue sizes and waiting times. This method is highly accurate as demonstrated by an extensive numerical study. In addition, it is highly adaptable to a variety of arrival patterns and switching protocols, including exhaustive and gated regimes, simple cyclical systems as well as general polling tables. For a system withN stations, one finds the firstK probability density function values of the steady state queue size in any given station inO(max(N, K ²) time only. When executed on an IBM system RS/6000, we have observed an average CPU time of less than 1 second for systems with as many as 50 stations over a large variety of parameter settings.     

Sojourn time asymptotics in the M/G/1 processor sharing queue

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ν, ν non-integer, iff the sojourn time distribution is regularly varying of index -ν. This result is derived from a new expression for the Laplace–Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the kth moment of the sojourn time is finite iff the kth moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

About the Sojourn Time Process in Multiphase Queueing Systems

Multiphase queueing systems (MQS) (tandem queues, queues in series) are of special interest both in theory and in practical applications (packet switch structures, cellular mobile networks, message switching systems, retransmission of video images, asembly lines, etc.). In this paper, we deal with approximations of MQS and present a heavy traffic limit theorems for the sojourn time of a customer in MQS. Functional limit theorems are proved for the customer sojourn time – an important probability characteristic of the queueing system under conditions of heavy traffic.      

Sojourn times with finite time-horizon in finite semi-markov processes

Let Y = {Y_t:t ≥ 0} be a semi-Markov process with finite state space S. Assume that Y is either irreducible and S is then partitioned into two classes A and B, or, that Y is absorbing and S is partitioned into A, B and C, where C is the set of all absorbing states of Y. Denote by T_{A, m}(t) the mth sojourn time of Y in A during [0, t]. T_{A, m}(t) is thus defined as the duration in [0, t] of the mth visit of Y to A if A is visited by Y during [0, t] at least m times; T_{A, m}(t) = 0 otherwise. We derive a recurrence relation for the vectors of double Laplace transforms g_m**(T₁,T₂) = {g_m**(T₁, T₂;S):sSC}, m = 1,2,… which are defined by with T₁, T₂, Re(T₁), Re(T₂) > 0. This result is then applied to alternating renewal processes. Symbolic Laplace transform inversion with MAPLE is used to obtain the first two moments of T_{A, m}(t). The assumed holding time distributions are exponential and Erlang respectively. This paper is a continuation of some of the author's recent work on the distribution theory of sojourn times in a subset of the finite state space of a (semi-)Markov process where the time horizon t = + ∞. The practical importance of considering a finite time horizon for semi-Markov reliability models has been discussed recently by Jack (1991), Jack and Dagpunar (1992), and Christer and Jack (1991).     

Synchronized abandonments in a single server unreliable queue

We consider a single server unreliable queue represented by a 2-dimensional continuous-time Markov chain. At failure times, the present customers leave the system. Moreover, customers become impatient and perform synchronized abandonments, as long as the server is down. We analyze this model and derive the main performance measures using results from the basic q-hypergeometric series.     

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.     

Asymptotic behavior of the stationary distribution in a finite QBD process with zero mean drift

We consider a finite QBD process with m levels. Assuming that the mean drift is 0, we obtain an asymptotic behavior as m→∞ in the stationary distribution , by finding an explicit expression for vector c. This solves the problem that was conjectured by Miyazawa et al. [Asymptotic behaviors of the loss probability for a finite buffer queue with QBD structure, 23 (2007) 79-95].     

Sojourn times in a processor sharing queue with service interruptions

We study the sojourn times of customers in an M/M/1 queue with the processor sharing service discipline and a server that is subject to breakdowns. The lengths of the breakdowns have a general distribution, whereas the on-periods are exponentially distributed. A branching process approach leads to a decomposition of the sojourn time, in which the components are independent of each other and can be investigated separately. We derive the Laplace–Stieltjes transform of the sojourn-time distribution in steady state, and show that the expected sojourn time is not proportional to the service requirement. In the heavy-traffic limit, the sojourn time conditioned on the service requirement and scaled by the traffic load is shown to be exponentially distributed. The results can be used for the performance analysis of elastic traffic in communication networks, in particular, the ABR service class in ATM networks, and best-effort services in IP networks.     

Performance evaluation for general queueing networks in manufacturing systems: Characterizing the trade-off between queue time and utilization

Performance evaluation plays a key role in manufacturing system design and productivity improvement. Characterizing performance objectively is the first step. Inspired by the underlying structure of tandem queues, we have derived an approximate model to characterize the system performance. The model decomposes system queue time and variability into bottleneck and non-bottleneck parts while capturing the dependence among workstations. Compared the new model with prior approaches, the new model not only is more accurate but also requires less information. The property of manufacturing system performance is given based on the insight from the model.     

Approximate analysis of non-stationary loss queues and networks of loss queues with general service time distributions

A Fixed Point Approximation (FPA) method has recently been suggested for non-stationary analysis of loss queues and networks of loss queues with Exponential service times. Deriving exact equations relating time-dependent mean numbers of busy servers to blocking probabilities, we generalize the FPA method to loss systems with general service time distributions. These equations are combined with associated formulae for stationary analysis of loss systems in steady state through a carried load to offered load transformation. The accuracy and speed of the generalized methods are illustrated through a wide set of examples.     

On sojourn times in the finite capacity queue with processor sharing

We consider a processor shared M/M/1 queue that can accommodate at most a finite number K of customers. We give an exact expression for the sojourn time distribution in this finite capacity model, in terms of a Laplace transform. We then give the tail behavior, for the limit K→∞.