From Polling to Snowplowing

We study the limiting behavior of gated polling systems, as their dimension (the number of queues) tends to infinity, while the system's total incoming workflow and total switchover time (per cycle) remain unchanged. The polling systems are assumed asymmetric, with incoming workflow obeying general Lévy statistics, and with general inter-dependent switchover times. We prove convergence, in law, to a limiting polling system on the circle. The derivation is based on an asymptotic analysis of the stochastic Poincaré maps of the polling systems. The obtained polling limit is identified as a snowplowing system on the circle—whose evolution, steady-state equilibrium, and statistics have been recently investigated and are known.     

Decomposition results for general polling systems and their applications

In this paper we derive decomposition results for the number of customers in polling systems under arbitrary (dynamic) polling order and service policies. Furthermore, we obtain sharper decomposition results for both the number of customers in the system and the waiting times under static polling policies. Our analysis, which is based on distributional laws, relaxes the Poisson assumption that characterizes the polling systems literature. In particular, we obtain exact decomposition results for systems with either Mixed Generalized Erlang (MGE) arrival processes, or asymptotically exact decomposition results for systems with general renewal arrival processes under heavy traffic conditions. The derived decomposition results can be used to obtain the performance analysis of specific systems. As an example, we evaluate the performance of gated Markovian polling systems operating under heavy traffic conditions. We also provide numerical evidence that our heavy traffic analysis is very accurate even for moderate traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

Continuous polling models and application to ferry assisted WLAN

In this paper we focus on a class of polling systems encountered while modeling the ferry based wireless local area network (FWLAN). A moving ferry, while walking in a predetermined cyclic path, communicates with the static nodes (or users) of the network via a wireless link. The ferry is assumed to stop and communicate with a node that has a packet to send or to receive, when it is closest to that node. The location distribution of the node to which or from which a packet arrives is assumed to have a support of positive Lebesgue measure. These features imply that polling models with finite number of queues cannot be used to model the system. We study in this paper the continuous polling systems with service disciplines that model the use of the FWLAN (and that are more complex than the classical exhaustive or gated services). Our approach is based on discretization of the continuous polling model. We propose a special way of discretizing the continuous system such that: (1)?the known Pseudo conservation laws can be applied to obtain the stationary expected workload of the discrete systems; (2)?the limit, of these ??discretized' expected workloads, equals the stationary expected workload of the continuous system. Our results rely heavily on fixed point analysis of infinite dimensional operators.     

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):

A decomposition result for a class of polling models

Boxma and Groenendijk have shown that the workload in polling models decomposes into two independent variables. This paper demonstrates a different type of decomposition that has an explicit multi-dimensional form. This decomposition does not apply to all polling models, but does, for example, apply to models with constant switch-over times and either exhaustive or gated service disciplines. For such models, we show that the population of customers present in the system (represented by a vector indicating the number of customers at each queue) at key time points breaks into two independent subpopulations: (1) the population of customers present in the related model with zero switch-over times; (2) another population, which is particularly easy to analyze. This result has a number of theoretical and applied implications.     

Gated polling with stationary ergodic walking times, Markovian routing and random feedback

We investigate a gated polling system with semi-linear feedback and Markovian routing. We thereby relax the classical independence assumption on the walking times; the walking times constitute a sequence of stationary ergodic random variables. It is shown that the dynamics of this polling system can be described by semi-linear stochastic recursive equations in a Markovian environment. We obtain expressions for the first and second order moments of the workload and queue content at polling instants and for the mean queue content and workload at random instants.     

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.     

Closed polling models with failing nodes

Closed polling systems with station breakdowns, under the gated, exhaustive or globally gated services regimes, are studied and analyzed. Multi-dimensional sets of probability generating functions of the system's state are derived. They are further utilized to obtain an approximate solution for the mean number of jobs residing in the system's various queues at polling instants. The analysis is then concentrated on the case of cyclic Bernoulli polling. Explicit formulae for the mean number of jobs, as well as for the expected cycle duration and system utilization, are derived. Comparison of the throughputs of the three regimes concludes the paper. This revised version was published online in June 2006 with corrections to the Cover Date.     

On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

Comments on: Polling: past,present and perspective

In their exposé on the past, present and perspective of the analysis of polling systems, professors Borst and Boxma give a first-hand account on the advancement of this particular research field. As any good historical account, the paper highlights some of the key turning points in the advancement of our current understanding of the dynamics of polling systems. Their paper, however, goes far beyond a classical literature review, as it also emphasises recent developments and points to many open problems. In the first section of this present note, we give some introductory comments on polling systems and queueing systems in general, followed by a discussion of Borst and Boxma’s survey of the past and the present in Sect. 2. Finally, we discuss some of their suggestions for further research in Sect. 3.     

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.     

Performance analysis of polling systems with retrials and glue periods

We consider gated polling systems with two special features: (i) retrials and (ii) glue or reservation periods. When a type-i customer arrives, or retries, during a glue period of the station i, it will be served in the following service period of that station. Customers arriving at station i in any other period join the orbit of that station and will retry after an exponentially distributed time. Such polling systems can be used to study the performance of certain switches in optical communication systems. When the glue periods are exponentially distributed, we obtain equations for the joint generating functions of the number of customers in each station. We also present an algorithm to obtain the moments of the number of customers in each station. When the glue periods are generally distributed, we consider the distribution of the total workload in the system, using it to derive a pseudo-conservation law which in turn is used to obtain accurate approximations of the individual mean waiting times. We also investigate the problem of choosing the lengths of the glue periods, under a constraint on the total glue period per cycle, so as to minimize a weighted sum of the mean waiting times.     

Stability of multi-server polling system with server limits

We consider a multi-server polling system with server limits, that is the number of servers that can attend a queue simultaneously is limited. Stability conditions are available when service policies are unlimited. The definition of stability conditions when both server limits and limited service policies apply remains an open problem. We postulate a conjecture for the stability condition in this case that is supported by our simulation results. The study of this particular variant of the multi-server polling system is motivated by the performance evaluation of next generation passive optical access networks.     

A new look at a smart polling model

We analyze a Markovian smart polling model, which is a special case of the smart polling models studied in the work of Boon et al. (Queueing Syst 66:239–274, 2010), as well as a generalization of the gated M / M / 1 queue considered in Resing and Rietman (Stat Neerlandica 58:97–110, 2004). We first derive tractable expressions for the stationary distribution (when it exists) as well as the Laplace transforms of the transition functions of this polling model—while further assuming the system is empty at time zero—and we also present simple necessary and sufficient conditions for ergodicity of the smart polling model. Finally, we conclude the paper by briefly explaining how these techniques can be used to study other interesting variants of this smart polling model.     

Efficient visit frequencies for polling tables: minimization of waiting cost

Polling systems have been used as a central model for the modeling and analysis of many communication systems. Examples include the Token Ring network and a communications switch. The common property of these systems is the need to efficiently share a single resource (server) amongN entities (stations). In spite of the massive research effort in this area, very little work has been devoted to the issue of how toefficiently operate these systems.In the present paper we deal with this problem, namely with how to efficiently allocate the server's attention among theN stations. We consider a framework in which a predetermined fixed visit order (polling table) is used to establish the order by which the server visits the stations, and we address the problem of how to construct an efficient (optimal) polling table. In selecting a polling table the objective is to minimize the mean waiting cost of the system, a weighted sum of the mean delays with arbitrary cost parameters. Since the optimization problem involved is very hard, we use an approximate approach. Using two independent analyses, based on a lower bound and on mean delay approximations, we derive very simple rules for the determination of efficient polling tables. The two rules are very similar and even coincide in most cases. Extensive numerical examination shows that the rules perform well and that in most cases the system operates very close to its optimal operation point.     

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.     

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.     

Polling systems and multitype branching processes

The joint queue length process in polling systems with and without switchover times is studied. If the service discipline in each queue satisfies a certain property it is shown that the joint queue length process at polling instants of a fixed queue is a multitype branching process (MTBP) with immigration. In the case of polling models with switchover times, it turns out that we are dealing with an MTBP with immigration in each state, whereas in the case of polling models without switchover times we are dealing with an MTBP with immigration in state zero. The theory of MTBPs leads to expressions for the generating function of the joint queue length process at polling instants. Sufficient conditions for ergodicity and moment calculations are also given.This work was done while the author was at the Centre for Mathematics and Computer Science (CWI) in Amsterdam, The Netherlands.     

The achievable region method in the optimal control of queueing systems; formulations,bounds and policies

We survey a new approach that the author and his co-workers have developed to formulate stochastic control problems (predominantly queueing systems) asmathematical programming problems. The central idea is to characterize the region of achievable performance in a stochastic control problem, i.e., find linear or nonlinear constraints on the performance vectors that all policies satisfy. We present linear and nonlinear relaxations of the performance space for the following problems: Indexable systems (multiclass single station queues and multiarmed bandit problems), restless bandit problems, polling systems, multiclass queueing and loss networks. These relaxations lead to bounds on the performance of an optimal policy. Using information from the relaxations we construct heuristic nearly optimal policies. The theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic control problems parallels efforts of the mathematical programming community in the last twenty years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization and new algorithms for indexable systems to tight lower bounds and nearly optimal algorithms for restless bandit problems, polling systems, multiclass queueing and loss networks.