Stability,monotonicity and invariant quantities in general polling systems

Consider a polling system withK1 queues and a single server that visits the queues in a cyclic order. The polling discipline in each queue is of general gated-type or exhaustive-type. We assume that in each queue the arrival times form a Poisson process, and that the service times, the walking times, as well as the set-up times form sequences of independent and identically distributed random variables. For such a system, we provide a sufficient condition under which the vector of queue lengths is stable. We treat several criteria for stability: the ergodicity of the process, the geometric ergodicity, and the geometric rate of convergence of the first moment. The ergodicity implies the weak convergence of station times, intervisit times and cycle times. Next, we show that the queue lengths, station times, intervisit times and cycle times are stochastically increasing in arrival rates, in service times, in walking times and in setup times. The stability conditions and the stochastic monotonicity results are extended to the polling systems with additional customer routing between the queues, as well as bulk and correlated arrivals. Finally, we prove that the mean cycle time, the mean intervisit time and the mean station times are invariant under general service disciplines and general stationary arrival and service processes.     

Dynamic server assignment in a two-queue model

We consider a polling model of two M/G/1 queues, served by a single server. The service policy for this polling model is of threshold type. Service at queue 1 is exhaustive. Service at queue 2 is exhaustive unless the size of queue 1 reaches some level T during a service at queue 2; in the latter case the server switches to queue 1 at the end of that service. Both zero- and nonzero switchover times are considered. We derive exact expressions for the joint queue length distribution at customer departure epochs, and for the steady-state queue-length and sojourn time distributions. In addition, we supply a simple and very accurate approximation for the mean queue lengths, which is suitable for optimization purposes.     

Exact Analysis of the State-Dependent Polling Model

We consider a polling model in which a number of queues are served, in cyclic order, by a single server. Each queue has its own distinct Poisson arrival stream, service time, and switchover time (the server's travel time from that queue to the next) distribution. A setup time is incurred if the polled queue has one or more customers present. This is the polling model with State-Dependent service (the SD model). The SD model is inherently complex; hence, it has often been approximated by the much simpler model with State-Independent service (the SI model) in which the server always sets up for a service at the polled queue, regardless of whether it has customers or not. We provide an exact analysis of the SD model and obtain the probability generating function of the joint queue length distribution at a polling epoch, from which the moments of the waiting times at the various queues are obtained. A number of numerical examples are presented, to reveal conditions under which the SD model could perform worse than the corresponding SI model or, alternately, conditions under which the SD model performs better than a corresponding model in which all setup times are zero. We also present expressions for a variant of the SD model, namely, the SD model with a patient server.     

Symmetric queues served in cyclic order

Consider a symmetrical system of n queues served in cyclic order by a single server. It is shown that the stationary number of customers in the system is distributed as the sum of three independent random variables, one being the stationary number of customers in a standard M/G/1 queue. This fact is used to establish an upper bound for the mean waiting time for the case where at most k customers are served at each queue per visit by the server. This approach is also used to rederive the mean waiting times for the cases of exhaustive service, gated service, and serve at most one customer at each queue per visit by the server.     

Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines

The stability of a cyclic polling system, with a single server and two infinite-buffer queues, is considered. Customers arrive at the two queues according to independent batch Markovian arrival processes. The first queue is served according to the gated service discipline, and the second queue is served according to a state-dependent time-limited service discipline with the preemptive repeat-different property. The state dependence is that, during each cycle, the predetermined limited time of the server’s visit to the second queue depends on the queue length of the first queue at the instant when the server last departed from the first queue. The mean of the predetermined limited time for the second queue either decreases or remains the same as the queue length of the first queue increases. Due to the two service disciplines, the customers in the first queue have higher service priority than the ones in the second queue, and the service fairness of the customers with different service priority levels is also considered. In addition, the switchover times for the server traveling between the two queues are considered, and their means are both positive as well as finite. First, based on two embedded Markov chains at the cycle beginning instants, the sufficient and necessary condition for the stability of the cyclic polling system is obtained. Then, the calculation methods for the variables related to the stability condition are given. Finally, the influence of some parameters on the stability condition of the cyclic polling system is analyzed. The results are useful for engineers not only checking whether the given cyclic polling system is stable, but also adjusting some parameters to make the system satisfy some requirements under the condition that the system is stable.     

Sojourn times in a processor sharing queue with multiple vacations

We study an M/G/1 processor sharing queue with multiple vacations. The server only takes a vacation when the system has become empty. If he finds the system still empty upon return, he takes another vacation, and so on. Successive vacations are identically distributed, with a general distribution. When the service requirements are exponentially distributed we determine the sojourn time distribution of an arbitrary customer. We also show how the same approach can be used to determine the sojourn time distribution in an M/M/1-PS queue of a polling model, under the following constraints: the service discipline at that queue is exhaustive service, the service discipline at each of the other queues satisfies a so-called branching property, and the arrival processes at the various queues are independent Poisson processes. For a general service requirement distribution we investigate both the vacation queue and the polling model, restricting ourselves to the mean sojourn time.     

Mixed gated/exhaustive service in a polling model with priorities

In this paper we consider a single-server polling system with switch-over times. We introduce a new service discipline, mixed gated/exhaustive service, that can be used for queues with two types of customers: high and low priority customers. At the beginning of a visit of the server to such a queue, a gate is set behind all customers. High priority customers receive priority in the sense that they are always served before any low priority customers. But high priority customers have a second advantage over low priority customers. Low priority customers are served according to the gated service discipline, i.e. only customers standing in front of the gate are served during this visit. In contrast, high priority customers arriving during the visit period of the queue are allowed to pass the gate and all low priority customers before the gate. We study the cycle time distribution, the waiting time distributions for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type. Through numerical examples we illustrate that the mixed gated/exhaustive service discipline can significantly decrease waiting times of high priority jobs. In many cases there is a minimal negative impact on the waiting times of low priority customers but, remarkably, it turns out that in polling systems with larger switch-over times there can be even a positive impact on the waiting times of low priority customers.     

A polling model with an autonomous server

This paper considers polling systems with an autonomous server that remains at a queue for an exponential amount of time before moving to a next queue incurring a generally distributed switch-over time. The server remains at a queue until the exponential visit time expires, also when the queue becomes empty. If the queue is not empty when the visit time expires, service is preempted upon server departure, and repeated when the server returns to the queue. The paper first presents a necessary and sufficient condition for stability, and subsequently analyzes the joint queue-length distribution via an embedded Markov chain approach. As the autonomous exponential visit times may seem to result in a system that closely resembles a system of independent queues, we explicitly investigate the approximation of our system via a system of independent vacation queues. This approximation is accurate for short visit times only.      

A Communication Multiplexer Problem: Two Alternating Queues with Dependent Randomly-Timed Gated Regime

Two random traffic streams are competing for the service time of a single server (multiplexer). The streams form two queues, primary (queue 1) and secondary (queue 0). The primary queue is served exhaustively, after which the server switches over to queue 0. The duration of time the server resides in the secondary queue is determined by the dynamic evolution in queue 1. If there is an arrival to queue 1 while the server is still working in queue 0, the latter is immediately gated, and the server completes service there only to the gated jobs, upon which it switches back to the primary queue. We formulate this system as a two-queue polling model with a single alternating server and with randomly-timed gated (RTG) service discipline in queue 0, where the timer there depends on the arrival stream to the primary queue. We derive Laplace–Stieltjes transforms and generating functions for various key variables and calculate numerous performance measures such as mean queue sizes at polling instants and at an arbitrary moment, mean busy period duration and mean cycle time length, expected number of messages transmitted during a busy period and mean waiting times. Finally, we present graphs of numerical results comparing the mean waiting times in the two queues as functions of the relative loads, showing the effect of the RTG regime.     

Fluid polling systems

We study N-queues single-server fluid polling systems, where a fluid is continuously flowing into the queues at queue-dependent rates. When visiting and serving a queue, the server reduces the amount of fluid in the queue at a queue-dependent rate. Switching from queue i to queue j requires two random-duration steps: (i) departing queue i, and (ii) reaching queue j. The length of time the server resides in a queue depends on the service regime. We consider three main regimes: Exhaustive, Gated, and Globally-Gated. Two polling procedures are analyzed: (i) cyclic and (ii) probabilistic. Under steady-state, we derive the Laplace–Stieltjes transform (LST), mean, and second moment of the amount of flow at each queue at polling instants, as well as at an arbitrary moment. We further calculate the LST and mean of the “waiting time” of a drop at each queue and derive expressions for the mean total load in the system for the various service regimes. Finally, we explore optimal switching procedures.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

A two-queue model with Bernoulli service schedule and switching times

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability p_i, it serves the next customer; with probability 1-p_i, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. This revised version was published online in June 2006 with corrections to the Cover Date.     

Relating polling models with zero and nonzero switchover times

We consider a system ofN queues served by a single server in cyclic order. Each queue has its own distinct Poisson arrival stream and its own distinct general service-time distribution (asymmetric queues), and each queue has its own distinct distribution of switchover time (the time required for the server to travel from that queue to the next). We consider two versions of this classical polling model: In the first, which we refer to as the zero-switchover-times model, it is assumed that all switchover times are zero and the server stops traveling whenever the system becomes empty. In the second, which we refer to as the nonzero-switchover-times model, it is assumed that the sum of all switchover times in a cycle is nonzero and the server does not stop traveling when the system is empty. After providing a new analysis for the zero-switchover-times model, we obtain, for a host of service disciplines, transform results that completely characterize the relationship between the waiting times in these two, operationally-different, polling models. These results can be used to derive simple relations that express (all) waiting-time moments in the nonzero-switchover-times model in terms of those in the zero-switchover-times model. Our results, therefore, generalize corresponding results for the expected waiting times obtained recently by Fuhrmann [Queueing Systems 11 (1992) 109—120] and Cooper, Niu, and Srinivasan [to appear in Oper. Res.].Research supported in part by the National Science Foundation under grant DDM-9001751.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

Multiqueue System with Non-Exhaustive Cyclic Service Modelled as a Linear-Programming Problem

In modern processor-controlled systems, it is common to find a central processor polling a number of message queues, where at most one message is processed from each queue during one polling cycle. This paper shows how one important parameter can be estimated quickly, namely the cycle-time distribution. This is the distribution of times taken for the cyclic server to perform one complete cycle in its continuous scan of a number of queues. The method of solution is to identify various constraints which will determine the cycle-time distribution, formulate them as linear inequality and equality constraints and, by determining an appropriate objective function, apply the simplex method to find upper and lower bounds on the values taken by the cycle-time distribution itself. A great strength of this technique is its overall simplicity, which enables it to be used to obtain important results very quickly and cheaply.     

A Discrete-Time Geo /G/1 Retrial Queue with General Retrial Times

We consider a discrete-time Geo/G/1 retrial queue in which the retrial time has a general distribution and the server, after each service completion, begins a process of search in order to find the following customer to be served. We study the Markov chain underlying the considered queueing system and its ergodicity condition. We find the generating function of the number of customers in the orbit and in the system. We derive the stochastic decomposition law and as an application we give bounds for the proximity between the steady-state distributions for our queueing system and its corresponding standard system. Also, we develop recursive formulae for calculating the steady-state distribution of the orbit and system sizes. Besides, we prove that the M/G/1 retrial queue with general retrial times can be approximated by our corresponding discrete-time system. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

Steady-state probability of the randomized server control system with second optional service, server breakdowns and startup

This paper deals with the 〈N,p〉-policy M/G/1 queue with server breakdowns and general startup times, where customers arrive to demand the first essential service and some of them further demand a second optional service. Service times of the first essential service channel are assumed to follow a general distribution and that of the second optional service channel are another general distribution. The server breaks down according to a Poisson process and his repair times obey a general distribution in the first essential service channel and second optional service channel, respectively. The server operation starts only when N (N≥1) customers have accumulated, he requires a startup time before each busy period. When the system becomes empty, turn the server off with probability p (p∈[0,1]) and leave it on with probability (1?p). The method of maximum entropy principle is used to develop the approximate steady-state probability distribution of the queue length in the M/G(G, G)/1 queueing system. A study of the derived approximate results, compared to the established exact results for three different 〈N,p〉-policy queues, suggests that the maximum entropy principle provides a useful method for solving complex queueing systems.     

M/M/∞ Queues in series with non-homogeneous inputs

This paper studies the transient behaviour of tandem queueing system consisting of an arbitrary number r of queues in series with infinite server service facility at each queue. Poisson arrivals with time dependent parameter and exponential service times have been assumed. Infinite server queues realistically describe those queues in which sufficient service capacity exist to prevent virtually any waiting by the customer present. The model is suitable for both phase type service as well services in series. Very elegant solutions have been obtained and it has been shown that if the queue sizes are initially independent and Poisson then they remain independent and Poisson for all t.     

The 1-Center and 1-Highway problem revisited

We consider a two-queue polling model in which customers upon arrival join the shorter of two queues. Customers arrive according to a Poisson process and the service times in both queues are independent and identically distributed random variables having the exponential distribution. The two-dimensional process of the numbers of customers at the queue where the server is and at the other queue is a two-dimensional Markov process. We derive its equilibrium distribution using two methodologies: the compensation approach and a reduction to a boundary value problem.     

A single-server batch arrival queue with returning customers

We consider a new class of batch arrival retrial queues. By contrast to standard batch arrival retrial queues we assume if a batch of primary customers arrives into the system and the server is free then one of the customers starts to be served and the others join the queue and then are served according to some discipline. With the help of Lyapunov functions we have obtained a necessary and sufficient condition for ergodicity of embedded Markov chain and the joint distribution of the number of customers in the queue and the number of customers in the orbit in steady state. We also have suggested an approximate method of analysis based on the corresponding model with losses.