The analysis of a multiserver queue fed by a discrete autoregressive process of order 1

Based on matrix analytic methods and the theory of Markov regenerative processes, we obtain the stationary distributions of the system size and the waiting time in a multiserver queue into which packets arrive according to a discrete autoregressive process of order 1.     

On multiserver feedback retrial queue with finite buffer

This paper deals with a multiserver feedback retrial queueing system with finite waiting position and constant retrial rate. This system is analyzed as a quasi-birth-and-death (QBD) process and the necessary and sufficient condition for stability of the system is investigated. Some important system performance measures are obtained using matrix geometric method. The effect of various parameters on the system performance measures are illustrated numerically. Finally, the algorithmic development of the full busy period for the model under consideration is discussed.     

A multiserver retrial queue: regenerative stability analysis

We consider a multiserver retrial GI/G/m queue with renewal input of primary customers, interarrival time τ with rate , service time S, and exponential retrial times of customers blocked in the orbit. In the model, an arriving primary customer enters the system and gets a service immediately if there is an empty server, otherwise (if all m servers are busy) he joins the orbit and attempts to enter the system after an exponentially distributed time. Exploiting the regenerative structure of the (non-Markovian) stochastic process representing the total number of customers in the system (in service and in orbit), we determine stability conditions of the system and some of its variations. More precisely, we consider a discrete-time process embedded at the input instants and prove that if and , then the regeneration period is aperiodic with a finite mean. Consequently, this queue has a stationary distribution under the same conditions as a standard multiserver queue GI/G/m with infinite buffer. To establish this result, we apply a renewal technique and a characterization of the limiting behavior of the forward renewal time in the (renewal) process of regenerations. The key step in the proof is to show that the service discipline is asymptotically work-conserving as the orbit size increases. Included are extensions of this stability analysis to continuous-time processes, a retrial system with impatient customers, a system with a general retrial rate, and a system with finite buffer for waiting primary customers. We also consider the regenerative structure of a multi-dimensional Markov process describing the system. This work is supported by Russian Foundation for Basic Research under grants 04-07-90115 and 07-07-00088.     

The queue length distributions in the finite buffer bulk-service MAP/G/1 queue with multiple vacations

We consider a finite buffer batch service queueing system with multiple vacations wherein the input process is Markovian arrival process (MAP). The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service- and vacation- times are arbitrarily distributed. We obtain the queue length distributions at service completion, vacation termination, departure, arbitrary and pre-arrival epochs. Finally, some performance measures such as loss probability, average queue lengths are discussed. Computational procedure has been given when the service- and vacation- time distributions are of phase type (PH-distribution).     

On bulk-service MAP/PH L,N /1/N G-Queues with repeated attempts

We consider a retrial queue with a finite buffer of size N, with arrivals of ordinary units and of negative units (which cancel one ordinary unit), both assumed to be Markovian arrival processes. The service requirements are of phase type. In addition, a PH^L,N bulk service discipline is assumed. This means that the units are served in groups of size at least L, where 1≤ L≤ N. If at the completion of a service fewer than L units are present at the buffer, the server switches off and waits until the buffer length reaches the threshold L. Then it switches on and initiates service for such a group of units. On the contrary, if at the completion of a service L or more units are present at the buffer, all units enter service as a group. Units arriving when the buffer is full are not lost, but they join a group of unsatisfied units called “orbit”. Our interest is in the continuous-time Markov chain describing the state of the queue at arbitrary times, which constitutes a level dependent quasi-birth-and-death process. We start by analyzing a simplified version of our queueing model, which is amenable to numerical calculation and is based on spatially homogeneous quasi-birth-and-death processes. This leads to modified matrix-geometric formulas that reveal the basic qualitative properties of our algorithmic approach for computing performance measures. AMS Subject Classification: Primary 60K25 Secondary 68M20 90B22.     

Analysis of the MAP/G/1/N queue with multiple vacations

This paper deals with a batch service queue and multiple vacations. The system consists of a single server and a waiting room of finite capacity. Arrival of customers follows a Markovian arrival process (MAP). The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in batches of maximum size ‘b’ with a minimum threshold value ‘a’. We obtain the queue length distributions at various epochs along with some key performance measures. Finally, some numerical results have been presented.     

Analysis of the discrete-time bulk-service queue Geo/G/1/N+B

This paper considers a discrete-time bulk-service queueing system with variable capacity, finite waiting space and independent Bernoulli arrival process: Geo/G^Y/1/N+B. Both the analytic and computational aspects of the distributions of the number of customers in the queue at post-departure, random and pre-arrival epochs are discussed.     

Synchronous working vacation policy for finite-buffer multiserver queueing system

This paper presents modeling and analysis of unreliable Markovian multiserver finite-buffer queue with discouragement and synchronous working vacation policy. According to this policy, c servers keep serving the customers until the number of idle servers reaches the threshold level d; then d idle servers take vacation altogether. Out of these d vacationing servers, d_W servers may opt for working vacation i.e. they serve the secondary customers with different rates during the vacation period. On the other hand, the remaining d − d_W = d_V servers continue to be on vacation. During the vacation of d servers, the other e = c − d servers must be present in the system even if they are idle. On returning from vacation, if the queue size does not exceed e, then these d servers take another vacation together; otherwise start serving the customers. The servers may undergo breakdown simultaneously both in regular busy period and working vacation period due to the failure of a main control unit. This main unit is then repaired by the repairman in at most two phases. We obtain the stationary performance measures such as expected queue length, average balking and reneging rate, throughput, etc. The steady state and transient behaviours of the arriving customers and the servers are examined by using matrix analytical method and numerical approach based on Runge-Kutta method of fourth order, respectively. The sensitivity analysis is facilitated for the transient model to demonstrate the validity of the analytical results and to examine the effect of different parameters on various performance indices.     

Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues

Scheller-Wolf [12] established necessary and sufficient conditions for finite stationary delay moments in stable FIFO GI/GI/s queues that incorporate the interaction between service time distribution, traffic intensity (ρ) and the number of servers in the queue. These conditions can be used to show that when the service time has finite first but infinite αth moment, s slow servers can give lower delays than one fast server. In this paper, we derive an alternative derivation of these moment results: Both upper bounds, that serve as sufficient conditions, and lower bounds, that serve as necessary conditions are presented. In addition, we extend the class of service time distributions for which the necessary conditions are valid. Our new derivations provide a structural interpretation of the moment bounds, giving intuition into their origin: We show that FIFO GI/GI/s delay can be represented as the minimum of (s − k) i.i.d. GI/GI/1 delays, when ρ satisfies k < ρ < k+1. AMS Subject Classification 60K25     

Numerical investigation of finite-source multiserver systems with different vacation policies

Systems with vacations are usually modeled and analyzed by queueing theory, and almost all works assume that the customer source is infinite and the arrival process is Poisson. This paper aims to present an approach for modeling and analyzing finite-source multiserver systems with single and multiple vacations of servers or all stations, using the Generalized Stochastic Petri nets model. We show how this high level formalism, allows a simple construction of detailed and compact models for such systems and to obtain easily the underlying Markov chains. However, for real vacation systems, the models may have a huge state space. To overcome this problem, we give the algorithms for automatically computing the infinitesimal generator, for the different vacation policies. In addition, we develop the formulas of the main exact stationary performance indices. Through numerical examples, we discuss the effect of server number, vacation rate and vacation policy on the system’s performances.     

Analyzing discrete-time D-BMAP/G/1/N queue with single and multiple vacations

This paper analyzes a single-server finite-buffer vacation (single and multiple) queue wherein the input process follows a discrete-time batch Markovian arrival process (D-BMAP). The service and vacation times are generally distributed and their durations are integral multiples of a slot duration. We obtain the state probabilities at service completion, vacation termination, arbitrary, and prearrival epochs. The loss probabilities of the first-, an arbitrary- and the last-customer in a batch, and other performance measures along with numerical aspects have been discussed. The analysis of actual waiting time of these customers in an accepted batch is also carried out.     

Delay and partial system contents for a discrete-time G-D-c queue

We consider a discrete-time multiserver queueing system with infinite buffer size, constant service times of multiple slots and a first-come-first-served queueing discipline. A relationship between the probability distributions of the partial system contents and the packet delay is established. The relationship is general in the sense that it doesn’t require knowledge of the exact nature of the arrival process. By means of the relationship, results for the distribution of the partial system contents for a wide variety of discrete-time queueing models can be transformed into corresponding results for the delay distribution. As a result, a separate full analysis of the packet delay becomes unnecessary.      

On a bulk arrival bulk service infinite service queue

This paper considers an infinite server queue in continuous time in which arrivals are in batches of variable size X and service is provided in groups of fixed size R. We obtain analytical results for the number of busy servers and waiting customers at arbitrary time points. For the number of busy servers, we obtain a recursive relation for the partial binomial moments both in transient and steady states. Special cases are also discussed     

Analysis of multiserver retrial queueing system: A martingale approach and an algorithm of solution

The paper studies a multiserver retrial queueing system withm servers. Arrival process is a point process with strictly stationary and ergodic increments. A customer arriving to the system occupies one of the free servers. If upon arrival all servers are busy, then the customer goes to the secondary queue, orbit, and after some random time retries more and more to occupy a server. A service time of each customer is exponentially distributed random variable with parameter μ₁. A time between retrials is exponentially distributed with parameter μ₂ for each customer. Using a martingale approach the paper provides an analysis of this system. The paper establishes the stability condition and studies a behavior of the limiting queue-length distributions as μ₂ increases to infinity. As μ₂→∞, the paper also proves the convergence of appropriate queue-length distributions to those of the associated “usual” multiserver queueing system without retrials. An algorithm for numerical solution of the equations, associated with the limiting queue-length distribution of retrial systems, is provided. AMS 2000 Subject classifications: 60K25 60H30.     

A consistent diffusion approximation for finite-capacity multiserver queues

A diffusion approximation is developed for general multiserver queues with finite waiting spaces, which are typical models of manufacturing systems as well as computer and communication systems. The model is the standard GI/G/s/s + r queue with s identical servers in parallel, r extra waiting spaces, and the first-come, first-served discipline. The main focus is on the steady-state distribution of the number of customers in the system. The process of the number of customers is approximated by a time-homogeneous diffusion process on a closed interval in the nonnegative real line. A conservation law plus some heuristics standing on solid theoretical ground generate approximation formulas for the steady-state distribution and other congestion measures. These formulas are consistent with the exact results for the M/G/s/s and M/M/s/s + r queues. The accuracy of approximations for principal congestion measures are numerically examined for some particular cases.     

An efficient computation algorithm for a multiserver feedback retrial queue with a large queueing capacity

Kumar et al. consider the M/M/c/N+c feedback queue with constant retrial rate [1]. They provide a solution for the steady state probabilities based on the matrix-geometric method. We show that there exists a more efficient computation method to calculate the steady state probabilities when N+c$N+c$ is large. We prove that the number of zero-eigenvalues of the characteristic matrix polynomial associated with the balance equation is ⌊(N+c+2)/2⌋$\lfloor (N+c+2)/2\rfloor$. As consequence, the remaining eigenvalues inside the unit circle can be computed in a quick manner based on the Sturm sequences. Therefore, the steady state probabilities can be determined in an efficient way.     

A queue with a pair of instantaneous independent bernoulli feedback processes

In this paper we are concerned with several random processes that occur in M/G₂/l queue with instantaneous feedback in which the feedback decision process is a pair of independent Bernoulli processes. The stationary distribution of the output process has been obtained. Results for particular queues with feedback and without feedback are obtained. Some operating characteristics are derived for this queue. Some interesting results are obtained for departure processes. Optimum service rate is obtained. Numerical examples are provided to test the feasibility of the queueing model     

A queue with instantaneous tri-route decision process

This paper focuses on the study of several random processes associated with M/G1 queue with instantaneous tri-route decision process. The stationary distribution of the output process is derived. Some particular queues with feedback and without feedback are also analysed. Some operating characteristics are studied for this queue. Optimum service rate is obtained. A numerical study is carried out to test the feasibility of the queueing model.     

Remarks on the remaining service time upon reaching a target level in the M/G/1 queue

In this note we establish connections between new and previous results on the remaining service time upon reaching a target level in the M/G/1 queue.