![Polling system](https://upload.wikimedia.org/wikipedia/commons/f/f7/Polling_system.svg)
In
queueing theory
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
, a discipline within the mathematical
theory of probability
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
, a polling system or polling model is a system where a single server visits a set of queues in some order.
The model has applications in computer networks and
telecommunications
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that fe ...
,
manufacturing
Manufacturing is the creation or production of goods with the help of equipment, labor, machines, tools, and chemical or biological processing or formulation. It is the essence of secondary sector of the economy. The term may refer to a r ...
and
road traffic management
: ''For the road traffic science, see various articles under Road traffic management.''
Road traffic control involves directing vehicular and pedestrian traffic around a construction zone, accident or other road disruption, thus ensuring the safety ...
. The term polling system was coined at least as early as 1968 and the earliest study of such a system in 1957 where a single repairman servicing machines in the British cotton industry was modelled.
Typically it is assumed that the server visits the different queues in a cyclic manner.
Exact results exist for waiting times, marginal queue lengths and joint queue lengths at polling epochs in certain models.
Mean value analysis In queueing theory, a discipline within the mathematical theory of probability, mean value analysis (MVA) is a recursive technique for computing expected queue lengths, waiting time at queueing nodes and throughput in equilibrium for a closed separ ...
techniques can be applied to compute average quantities.
In a
fluid limit In queueing theory, a discipline within the mathematical theory of probability, a fluid limit, fluid approximation or fluid analysis of a stochastic model is a deterministic real-valued process which approximates the evolution of a given stochastic ...
, where a very large number of small jobs arrive the individual nodes can be viewed to behave similarly to
fluid queue In queueing theory, a discipline within the mathematical theory of probability, a fluid queue (fluid model, fluid flow model or stochastic fluid model) is a mathematical model used to describe the fluid level in a reservoir subject to randomly deter ...
s (with a two state process).
Model definition
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
In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of one ...
of rate ''λ''
''i'' and are served on a
first-come, first-served
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
basis with each job having a service time denoted by an
independent and identically distributed random variables
In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is us ...
''S''
''i''.
The server chooses when to progress to the next node according to one of the following criteria:
* exhaustive service, where a node continues to receive service until the buffer is empty.
* gated service, where the node serves all traffic that was present at the instant that the server arrived and started serving, but subsequent arrivals during this service time must wait until the next server visit.
* limited service, where a maximum fixed number of jobs can be served in each visit by the server.
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 ''d''
''i''.
Utilization
Define ''ρ''
''i'' = ''λ''
''i'' E(''S''
''i'') and write ''ρ'' = ''ρ''
1 + ''ρ''
2 + … + ''ρ''
''n''. Then ''ρ'' is the long-run fraction of time the server spends attending to customers.
Waiting time
Expected waiting time
For gated service, the expected waiting time at node ''i'' is
:
and for exhaustive service
:
where ''C''
''i'' is a random variable denoting the time between entries to node ''i'' and
:
The variance of ''C''
''i'' is more complicated and a straightforward calculation requires solving ''n''
2 linear equations and ''n''
2 unknowns, however it is possible to compute from ''n'' equations.
Heavy traffic
The workload process can be approximated by a
reflected Brownian motion
In probability theory, reflected Brownian motion (or regulated Brownian motion, both with the acronym RBM) is a Wiener process in a space with reflecting boundaries. In the physical literature, this process describes diffusion in a confined spac ...
in a heavily loaded and suitably scaled system if switching servers is immediate and a
Bessel process In mathematics, a Bessel process, named after Friedrich Bessel, is a type of stochastic process.
Formal definition
The Bessel process of order ''n'' is the real-valued process ''X'' given (when ''n'' ≥ 2) by
:X_t = \, W_t \, ,
whe ...
when switching servers takes time.
Applications
Polling systems have been used to model
Token Ring
Token Ring network
IBM hermaphroditic connector with locking clip. Screen contacts are prominently visible, gold-plated signal contacts less so.
Token Ring is a computer networking technology used to build local area networks. It was introduc ...
networks.
External links
Bibliography on polling models(papers published 1984–1993) by Hideaki Takagi
References
{{Queueing theory
Queueing theory