In queueing theory, a discipline within the mathematical theory of probability, a polling system or polling model is a system where a single server visits a set of queues in some order.[1] The model has applications in computer networks and telecommunications,[2] manufacturing[3][4] and road traffic management. The term polling system was coined at least as early as 1968[5][6] and the earliest study of such a system in 1957 where a single repairman servicing machines in the British cotton industry was modelled.[7]
Typically it is assumed that the server visits the different queues in a cyclic manner.[1] Exact results exist for waiting times, marginal queue lengths and joint queue lengths[8] at polling epochs in certain models.[9] Mean value analysis techniques can be applied to compute average quantities.[10]
In a fluid limit, where a very large number of small jobs arrive the individual nodes can be viewed to behave similarly to fluid queues (with a two state process).[11]
A group of n queues are served by a single server, typically in a cyclic order 1, 2, …, n, 1, …. New jobs arrive at queue i according to a Poisson process of rate λi and are served on a first-come, first-served basis with each job having a service time denoted by an independent and identically distributed random variables Si.
The server chooses when to progress to the next node according to one of the following criteria:[12]
If a queueing node is empty the server immediately moves to serve the next queueing node.
The time taken to switch from serving node i − 1 and node i is denoted by the random variable di.
Define ρi = λi E(Si) and write ρ = ρ1 + ρ2 + … + ρn. Then ρ is the long-run fraction of time the server spends attending to customers.[14]
For gated service, the expected waiting time at node i is[12]
and for exhaustive service
where Ci is a random variable denoting the time between entries to node i and[15]
The variance of Ci is more complicated and a straightforward calculation requires solving n2 linear equations and n2 unknowns,[16] however it is possible to compute from n equations.[17]
Main article: Heavy traffic approximation |
The workload process can be approximated by a reflected Brownian motion in a heavily loaded and suitably scaled system if switching servers is immediate[18] and a Bessel process when switching servers takes time.[19]
Polling systems have been used to model Token Ring networks.[20]