Polling system

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 S_i.

The server chooses when to progress to the next node according to one of the following criteria:{{Cite journal | last1 = Everitt | first1 = D. | title = Simple Approximations for Token Rings | doi = 10.1109/TCOM.1986.1096599 | journal = IEEE Transactions on Communications| volume = 34 | issue = 7 | pages = 719–721 | year = 1986 }}

• 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.{{Cite journal | last1 = Takagi | first1 = H. | doi = 10.1145/62058.62059 | title = Queuing analysis of polling models | journal = ACM Computing Surveys| volume = 20 | pages = 5–28 | year = 1988 }}

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.

Define ρ_i = λ_i E(S_i) and write ρ = ρ₁ + ρ₂ + … + ρ_n. Then ρ is the long-run fraction of time the server spends attending to customers.{{cite book | title = Analysis of Queues: Methods and Applications | first = Natarajan | last = Gautam | year = 2012 | publisher = CRC Press | isbn = 9781439806586}}

For gated service, the expected waiting time at node i is

:$\backslash mathbb\{E\}(W\_i)\; =\; \backslash frac\{1+\backslash rho\_i\}\{2\}\; \backslash mathbb\{E\}(C)\; +\; \backslash frac\{(1+\backslash rho\_i)\; \backslash text\{Var\}(C\_i)\}\{2\; \backslash mathbb\{E\}(C)\}$

and for exhaustive service

:$\backslash mathbb\{E\}(W\_i)\; =\; \backslash frac\{1-\backslash rho\_i\}\{2\}\; \backslash mathbb\{E\}(C)\; +\; \backslash frac\{(1-\backslash rho\_i)\; \backslash text\{Var\}(C\_\{i+1\})\}\{2\; \backslash mathbb\{E\}(C)\}$

where C_i is a random variable denoting the time between entries to node i and{{Cite journal | last1 = Eisenberg | first1 = M. | title = Queues with Periodic Service and Changeover Time | doi = 10.1287/opre.20.2.440 | journal = Operations Research| volume = 20 | issue = 2 | pages = 440–451 | jstor = 169005| year = 1972 }}

:$\backslash mathbb\{E\}(C)\; =\; \backslash sum\_\{i=1\}^n\; \backslash frac\{\backslash mathbb\{E\}(d\_i)\}\{1-\backslash rho\}$

The variance of C_i is more complicated and a straightforward calculation requires solving n² linear equations and n² unknowns,{{Cite journal | last1 = Ferguson | first1 = M. | title = Computation of the Variance of the Waiting Time for Token Rings | doi = 10.1109/JSAC.1986.1146407 | journal = IEEE Journal on Selected Areas in Communications| volume = 4 | issue = 6 | pages = 775–782 | year = 1986 }} however it is possible to compute from n equations.{{Cite journal | last1 = Sarkar | first1 = D. | last2 = Zangwill | first2 = W. I. | doi = 10.1287/mnsc.35.12.1463 | title = Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems—Exact Results and Applications | journal = Management Science| volume = 35 | issue = 12 | pages = 1463 | year = 1989 | jstor = 2632232}}

{{main|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{{Cite journal | last1 = Coffman | first1 = E. G. | author-link1 = Edward G. Coffman, Jr.| last2 = Puhalskii | first2 = A. A. | last3 = Reiman | first3 = M. I. | doi = 10.1214/aoap/1177004701 | title = Polling Systems with Zero Switchover Times: A Heavy-Traffic Averaging Principle | journal = The Annals of Applied Probability | volume = 5 | issue = 3 | pages = 681 | year = 1995 | url = http://www.ee.columbia.edu/~egc/webpapers/system.ps| jstor = 2245120| doi-access = free }} and a Bessel process when switching servers takes time.{{Cite journal | last1 = Coffman | first1 = E. G. | author-link1 = Edward G. Coffman, Jr. | last2 = Puhalskii | first2 = A. A. | last3 = Reiman | first3 = M. I. | doi = 10.1287/moor.23.2.257 | title = Polling Systems in Heavy Traffic: A Bessel Process Limit | journal = Mathematics of Operations Research | volume = 23 | issue = 2 | pages = 257–304 | year = 1998 | jstor = 3690512 | citeseerx = 10.1.1.27.6730 }}

Polling systems have been used to model Token Ring networks.{{Cite journal | last1 = Bux | first1 = W. | title = Token-ring local-area networks and their performance | doi = 10.1109/5.18625 | journal = Proceedings of the IEEE| volume = 77 | issue = 2 | pages = 238–256 | year = 1989 }}

• [http://infoshako.sk.tsukuba.ac.jp/~takagi/polling.html Bibliography on polling models] (papers published 1984–1993) by Hideaki Takagi

{{Reflist}}

{{Queueing theory}}

Category:Queueing theory