Unified analysis of <Emphasis Type="Italic">BMAP</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 cyclic polling models

In this paper we present a unified analysis of the BMAP/G/1 cyclic polling model and its application to the gated and exhaustive service disciplines as examples. The applied methodology is based on the separation of the analysis into service discipline independent and dependent parts. New expressions are derived for the vector-generating function of the stationary number of customers and for its mean in terms of vector quantities depending on the service discipline. They are valid for a broad class of service disciplines and both for zero- and nonzero-switchover-times polling models. We present the service discipline specific solution for the nonzero-switchover-times model with gated and exhaustive service disciplines. We set up the governing equations of the system by using Kronecker product notation. They can be numerically solved by means of a system of linear equations. The resulting vectors are used to compute the service discipline specific vector quantities.     

Markovian polling systems with mixed service disciplines and retrial customers

A Markovian polling model with a mixture of exhaustive and gated type stations is considered. The cuttomers are ofn different tppes and arrive to the system acccording to the Poisson distribution, in batches containing customers of all types (correlated batch arrivals). The customers who find upon arrival the server unavailable repeat their arrival individually after a random amount of time (retrial customers). The service timesT _i and the switchover timesV _ij are arbitrarily distributed with different distributions for the different stations. For such a model we obtain formulae for the expected number of customers in each station in a steady state. Our formulae hold also for zero switchover periods and can easily be adapted to hold for the corresponding ordinary Markovian mixed polling models with/without switchover times and correlated batch arrivals. Numerical calculations are finally used to observe system's performance.     

Polling and greedy servers on a line

A single server moves with speed on a line interval (or a circle) of length (circumference)L. Customers, requiring service of constant durationb, arrive on the interval (or circle) at random at mean rate customers per unit length per unit time. A customer's mean wait for service depends partly on the rules governing the server's motion. We compare two different servers: thepolling server and thegreedy server. Without knowing the locations of waiting customers, a polling server scans endlessly back and forth across the interval (or clockwise around the circle), stopping only where it encounters a waiting customer. Knowing where customers are waiting, a greedy server always travels toward the current nearest one. Except for certain extreme values of ,L, b, and, the polling and greedy servers are roughly equally effective. Indeed, the simpler polling server is often the better. Theoretical results show, in most cases, that the polling server has a high probability of moving toward the nearest customer, i.e. moving as a greedy server would. The greedy server is difficult to analyze, but was simulated on a computer.     

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.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

Waiting-Time Distributions in Polling Systems with Simultaneous Batch Arrivals

We study the delay in asymmetric cyclic polling models with general mixtures of gated and exhaustive service, with generally distributed service times and switch-over times, and in which batches of customers may arrive simultaneously at the different queues. We show that (1–)X _i converges to a gamma distribution with known parameters as the offered load tends to unity, where X _i is the steady-state length of queue i at an arbitrary polling instant at that queue. The result is shown to lead to closed-form expressions for the Laplace–Stieltjes transform (LST) of the waiting-time distributions at each of the queues (under proper scalings), in a general parameter setting. The results show explicitly how the distribution of the delay depends on the system parameters, and in particular, on the simultaneity of the arrivals. The results also suggest simple and fast approximations for the tail probabilities and the moments of the delay in stable polling systems, explicitly capturing the impact of the correlation structure in the arrival processes. Numerical experiments indicate that the approximations are accurate for medium and heavily loaded systems.     

Exact Asymptotics for k i -limited Exponential Polling Models

In this paper we find exact asymptotic expressions for the event that the total queue length is large for a k _i -limited exponential polling model with equal service rates and two classes of customer. It is found that this behaviour divides into two very different regimes, depending on the arrival rates to the system. Using these exact asymptotic expressions, we provide heuristics for choosing the k _i values to provide a given level of quality of service to one class while giving best effort to the other class.     

Towards a unifying theory on branching-type polling systems in heavy traffic

For a broad class of polling models the evolution of the system at specific embedded polling instants is known to constitute a multi-type branching process (MTBP) with immigration. In this paper it is shown that for this class of polling models the vector that describes the state of the system at these polling instants, say X=(X ₁,…,X _M ), satisfies the following heavy-traffic behavior (under mild assumptions):

Cyclic Bernoulli polling

We introduce, analyse and optimize the class of Bernoulli random polling systems. The server movescyclically among N channels (queues), butChange-over times between stations are composed ofwalking times required to move from one channel to another andswitch-in times that are incurredonly when the server actually enters a station to render service. The server uses aBernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channeli, it switches in with probabilityp _i , or moves on to the next queue (w.p. 1 —p _i ) without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper we analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime we derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a cutomer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all parameterized cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of thep _i 's in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, we develop a Pseudo-conservation law for amixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities {p _i } _i ^N =1 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimalp _i 's are not all equal to one, yields asmaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. We conclude by showing that even in the case of a single queue, it is not always true thatp ₁=1 is the best strategy, and derive conditions under which it is optimal to havep ₁ < 1.Supported by a Grant from the France-Israel Scientific Cooperation (in Computer Science and Engineering) between the French Ministry of Research and Technology and the Israeli Ministry of Science and Technology, Grant Number 3321190.     

Iterative approximation of <Emphasis Type="Italic">k</Emphasis>-limited polling systems

The present paper deals with the problem of calculating queue length distributions in a polling model with (exhaustive) k-limited service under the assumption of general arrival, service and setup distributions. The interest for this model is fueled by an application in the field of logistics. Knowledge of the queue length distributions is needed to operate the system properly. The multi-queue polling system is decomposed into single-queue vacation systems with k-limited service and state-dependent vacations, for which the vacation distributions are computed in an iterative approximate manner. These vacation models are analyzed via matrix-analytic techniques. The accuracy of the approximation scheme is verified by means of an extensive simulation study. The developed approximation turns out to be accurate, robust and computationally efficient. This research is supported by the Technology Foundation STW, applied science division of NWO and the technology programme of the Dutch Ministry of Economic Affairs.     

Ergodicity and analysis of the process describing the system state in polling systems with two queues

Consider a polling system of two queues served by a single server that visits the queues in cyclic order. The polling discipline in each queue is of exhaustive-type, and zero-switchover times are considered. We assume that the arrival times in each queue form a Poisson process and that the service times form sequences of independent and identically distributed random variables, except for the service distribution of the first customer who is served at each polling instant (the time in which the server moves from one queue to the other one). The sufficient and necessary conditions for the ergodicity of such polling system are established as well as the stationary distribution for the continuous-time process describing the state of the system. The proofs rely on the combination of three embedded processes that were previously used in the literature. An important result is that ρ=1 can imply ergodicity in one specific case, where ρ is the typical traffic intensity for polling systems, and ρ<1 is the classical non-saturation condition.     

Pseudo-cyclic policies for multi-queue single server systems

In this paper we evaluate the waiting time performance of cycle-time guided algorithms in semi-dynamic polling models. In these models knowledge of the system state is used by the server in the process of on-line determination of the visit pattern. Our main focus is on pseudo-cyclic algorithms which achievefairness by visiting every station exactly once in each cycle.It is shown that in fully symmetric systems the performance ofevery pseudocyclic policy is bounded between the performance of the cycle maximization and the cycle minimization strategies. In particular, stochastic dominance is shown with regard to system workload, implying dominance of mean waiting times. In a fluid approximation model the performance ratio between the two bounding policies is derived and shown to be always between 1 and 3/4 under the gated service regime and between 1 and 1/2 under the exhaustive service regime. Under both regimes, the ratio approaches 3/4 when the number of stations grows to infinity. Simulation results suggest that a similar performance ratio holds for the general (non-symmetric) stochastic model.Further, we study strategies which are guided by the cycle maximization (minimization) criteria, but which do not constrain themselves to pseudo-cyclic orders. It is shown that depending on the switch-over parameters these more dynamic policies may perform much worse than the pseudo-cyclic schemes.     

Gated Polling Systems with Lévy Inflow and Inter-Dependent Switchover Times: A Dynamical-Systems Approach

We study asymmetric polling systems where: (i) the incoming workflow processes follow general Lévy-subordinator statistics; and, (ii) the server attends the channels according to the gated service regime, and incurs random inter-dependentswitchover times when moving from one channel to the other. The analysis follows a dynamical-systems approach: a stochastic Poincaré map, governing the one-cycle dynamics of the polling system is introduced, and its statistical characteristics are studied. Explicit formulae regarding the evolution of the mean, covariance, and Laplace transform of the Poincaré map are derived. The forward orbit of the maps transform – a nonlinear deterministic dynamical system in Laplace space – fully characterizes the stochastic dynamics of the polling system. This enables us to explore the long-term behavior of the system: we prove convergence to a (unique) steady-state equilibrium, prove the equilibrium is stationary, and compute its statistical characteristics.     

An approximate analysis of a cyclic server queue with limited service and reservations

In this paper, we examine a queueing problem motivated by the pipeline polling protocol in satellite communications. The model is an extension of the cyclic queueing system withM-limited service. In this service mechanism, each queue, after receiving service on cyclej, makes a reservation for its service requirement in cyclej + 1. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.     

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.     

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.     

Threshold start-up control policy for polling systems

A threshold start-up policy is appealing for manufacturing (service) facilities that incur a cost for keeping the machine (server) on, as well as for each restart of the server from its dormant state. Analysis of single product (customer) systems operating under such a policy, also known as the N-policy, has been available for some time. This article develops mathematical analysis for multiproduct systems operating under a cyclic exhaustive or globally gated service regime and a threshold start-up rule. It pays particular attention to modeling switchover (setup) times. The analysis extends/unifies existing literature on polling models by obtaining as special cases, the continuously roving server and patient server polling models on the one hand, and the standard M/G/1 queue with N-policy, on the other hand. We provide a computationally efficient algorithm for finding aggregate performance measures, such as the mean waiting time for each customer type and the mean unfinished work in system. We show that the search for the optimal threshold level can be restricted to a finite set of possibilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

Two-Queue Polling Models with a Patient Server

We consider two-queue polling models with the special feature that a timer mechanism is employed at Q ₁: whenever the server polls Q ₁ and finds it empty, it activates a timer and remains dormant, waiting for the first arrival. If such an arrival occurs before the timer expires, a busy period starts in accordance with Q ₁'s service discipline. However, if the timer is shorter than the interarrival time to Q ₁, the server does not wait any more and switches back to Q ₂. We consider three configurations: (i) Q ₁ is controlled by the 1-limited protocol while Q ₂ is served exhaustively, (ii) Q ₁ employs the exhaustive regime while Q ₂ follows the 1-limited procedure, and (iii) both queues are served exhaustively. In all cases, we assume Poisson arrivals and allow general service and switchover time distributions. Our main results include the queue length distributions at polling instants, the waiting time distributions and the distribution of the total workload in the system.     

Large deviations of Markovian polling models with applications to admission control

In this paper we consider large deviations and admission control problems for a discrete-time Markovian polling system. The system consists of two-parallel queues and multiple heterogeneous servers. The arrival process of each queue is a superposition of mutually independent Markovian on/off processes, and the multiple servers serve independently the two queues according to the so called Bernoulli service schedule. Using the large deviations techniques, we derive upper and lower bounds of the overflow probabilities, and then we present an admission control criterion by which different Quality of Service (QoS) requirements for the two queues are guaranteed.     

Delay analysis of extended rtPS for VoIP service in IEEE 802.16e by matrix analytic method

Extended real time polling service (ErtPS) is added to IEEE 802.16e-2005 standards in order for VoIP service to use uplink resources efficiently by considering on/off characteristic of voice source. Recently average queueing delay of ErtPS algorithm for VoIP service was investigated, and it was shown that ErtPS allows to admit more users than UGS algorithm. But we need the probability distribution of queueing delay rather than average queueing delay in order to provide a necessary information for QoS. In this paper we obtain the probability distribution of queueing delay of ErtPS for VoIP service by using the matrix analytic method for the GI/M/1 type and the M/G/1 type matrices in cases of the service time being exponential and deterministic respectively. By applying the results on deterministic service time we find the maximum allowable number of VoIP users with the required constraint on queueing delay. This research was 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).