Polling system

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]

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 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:^[12]

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.^[13]

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 ρ = ρ₁ + ρ₂ + … + ρ_n. Then ρ is the long-run fraction of time the server spends attending to customers.^[14]

Waiting time

Expected waiting time

For gated service, the expected waiting time at node i is^[12]

\mathbb {E} (W_{i})={\frac {1+\rho _{i}}{2}}\mathbb {E} (C)+{\frac {(1+\rho _{i}){\text{Var}}(C_{i})}{2\mathbb {E} (C)}}

and for exhaustive service

\mathbb {E} (W_{i})={\frac {1-\rho _{i}}{2}}\mathbb {E} (C)+{\frac {(1-\rho _{i}){\text{Var}}(C_{i+1})}{2\mathbb {E} (C)}}

where C_i is a random variable denoting the time between entries to node i and^[15]

\mathbb {E} (C)=\sum _{i=1}^{n}{\frac {\mathbb {E} (d_{i})}{1-\rho }}

The variance of C_i is more complicated and a straightforward calculation requires solving n² linear equations and n² unknowns,^[16] however it is possible to compute from n equations.^[17]

Heavy traffic

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]

Applications

Polling systems have been used to model Token Ring networks.^[20]

External links

Bibliography on polling models (papers published 1984–1993) by Hideaki Takagi

References

^ ^a ^b Boxma, O. J.; Weststrate, J. A. (1989). "Waiting Times in Polling Systems with Markovian Server Routing". Messung, Modellierung und Bewertung von Rechensystemen und Netzen. Informatik-Fachberichte. Vol. 218. p. 89. doi:10.1007/978-3-642-75079-3_8. ISBN 978-3-540-51713-9.
^ Carsten, R.; Newhall, E.; Posner, M. (1977). "A Simplified Analysis of Scan Times in an Asymmetrical Newhall Loop with Exhaustive Service". IEEE Transactions on Communications. 25 (9): 951. doi:10.1109/TCOM.1977.1093936.
^ Karmarkar, U. S. (1987). "Lot Sizes, Lead Times and In-Process Inventories". Management Science. 33 (3): 409–418. doi:10.1287/mnsc.33.3.409. JSTOR 2631860.
^ Zipkin, P. H. (1986). "Models for Design and Control of Stochastic, Multi-Item Batch Production Systems". Operations Research. 34 (1): 91–104. doi:10.1287/opre.34.1.91. JSTOR 170674.
^ Leibowitz, M. A. (1968). "Queues". Scientific American. 219 (2): 96–103. doi:10.1038/scientificamerican0868-96.
^ Takagi, H. (2000). "Analysis and Application of Polling Models". Performance Evaluation: Origins and Directions. LNCS. Vol. 1769. pp. 423–442. doi:10.1007/3-540-46506-5_18. hdl:2241/530. ISBN 978-3-540-67193-0.
^ Mack, C.; Murphy, T.; Webb, N. L. (1957). "The Efficiency of N Machines Uni-Directionally Patrolled by One Operative when Walking Time and Repair Times are Constants". Journal of the Royal Statistical Society. Series B (Methodological). 19 (1): 166–172. doi:10.1111/j.2517-6161.1957.tb00253.x. JSTOR 2984003.
^ Resing, J. A. C. (1993). "Polling systems and multitype branching processes". Queueing Systems. 13 (4): 409–426. doi:10.1007/BF01149263.
^ Borst, S. C. (1995). "Polling systems with multiple coupled servers" (PDF). Queueing Systems. 20 (3–4): 369–393. doi:10.1007/BF01245325.
^ Wierman, A.; Winands, E. M. M.; Boxma, O. J. (2007). "Scheduling in polling systems" (PDF). Performance Evaluation. 64 (9–12): 1009. CiteSeerX 10.1.1.486.2326. doi:10.1016/j.peva.2007.06.015.
^ Czerniak, O.; Yechiali, U. (2009). "Fluid polling systems" (PDF). Queueing Systems. 63 (1–4): 401–435. doi:10.1007/s11134-009-9129-6.
^ ^a ^b Everitt, D. (1986). "Simple Approximations for Token Rings". IEEE Transactions on Communications. 34 (7): 719–721. doi:10.1109/TCOM.1986.1096599.
^ Takagi, H. (1988). "Queuing analysis of polling models". ACM Computing Surveys. 20: 5–28. doi:10.1145/62058.62059.
^ Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586.
^ Eisenberg, M. (1972). "Queues with Periodic Service and Changeover Time". Operations Research. 20 (2): 440–451. doi:10.1287/opre.20.2.440. JSTOR 169005.
^ Ferguson, M. (1986). "Computation of the Variance of the Waiting Time for Token Rings". IEEE Journal on Selected Areas in Communications. 4 (6): 775–782. doi:10.1109/JSAC.1986.1146407.
^ Sarkar, D.; Zangwill, W. I. (1989). "Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems—Exact Results and Applications". Management Science. 35 (12): 1463. doi:10.1287/mnsc.35.12.1463. JSTOR 2632232.
^ Coffman, E. G.; Puhalskii, A. A.; Reiman, M. I. (1995). "Polling Systems with Zero Switchover Times: A Heavy-Traffic Averaging Principle". The Annals of Applied Probability. 5 (3): 681. doi:10.1214/aoap/1177004701. JSTOR 2245120.
^ Coffman, E. G.; Puhalskii, A. A.; Reiman, M. I. (1998). "Polling Systems in Heavy Traffic: A Bessel Process Limit". Mathematics of Operations Research. 23 (2): 257–304. CiteSeerX 10.1.1.27.6730. doi:10.1287/moor.23.2.257. JSTOR 3690512.
^ Bux, W. (1989). "Token-ring local-area networks and their performance". Proceedings of the IEEE. 77 (2): 238–256. doi:10.1109/5.18625.

[boxma-1] Boxma, O. J.; Weststrate, J. A. (1989). "Waiting Times in Polling Systems with Markovian Server Routing". Messung, Modellierung und Bewertung von Rechensystemen und Netzen. Informatik-Fachberichte. Vol. 218. p. 89. doi:10.1007/978-3-642-75079-3_8. ISBN 978-3-540-51713-9.

[2] Carsten, R.; Newhall, E.; Posner, M. (1977). "A Simplified Analysis of Scan Times in an Asymmetrical Newhall Loop with Exhaustive Service". IEEE Transactions on Communications. 25 (9): 951. doi:10.1109/TCOM.1977.1093936.

[3] Karmarkar, U. S. (1987). "Lot Sizes, Lead Times and In-Process Inventories". Management Science. 33 (3): 409–418. doi:10.1287/mnsc.33.3.409. JSTOR 2631860.

[4] Zipkin, P. H. (1986). "Models for Design and Control of Stochastic, Multi-Item Batch Production Systems". Operations Research. 34 (1): 91–104. doi:10.1287/opre.34.1.91. JSTOR 170674.

[5] Leibowitz, M. A. (1968). "Queues". Scientific American. 219 (2): 96–103. doi:10.1038/scientificamerican0868-96.

[6] Takagi, H. (2000). "Analysis and Application of Polling Models". Performance Evaluation: Origins and Directions. LNCS. Vol. 1769. pp. 423–442. doi:10.1007/3-540-46506-5_18. hdl:2241/530. ISBN 978-3-540-67193-0.

[7] Mack, C.; Murphy, T.; Webb, N. L. (1957). "The Efficiency of N Machines Uni-Directionally Patrolled by One Operative when Walking Time and Repair Times are Constants". Journal of the Royal Statistical Society. Series B (Methodological). 19 (1): 166–172. doi:10.1111/j.2517-6161.1957.tb00253.x. JSTOR 2984003.

[8] Resing, J. A. C. (1993). "Polling systems and multitype branching processes". Queueing Systems. 13 (4): 409–426. doi:10.1007/BF01149263.

[9] Borst, S. C. (1995). "Polling systems with multiple coupled servers" (PDF). Queueing Systems. 20 (3–4): 369–393. doi:10.1007/BF01245325.

[10] Wierman, A.; Winands, E. M. M.; Boxma, O. J. (2007). "Scheduling in polling systems" (PDF). Performance Evaluation. 64 (9–12): 1009. CiteSeerX 10.1.1.486.2326. doi:10.1016/j.peva.2007.06.015.

[11] Czerniak, O.; Yechiali, U. (2009). "Fluid polling systems" (PDF). Queueing Systems. 63 (1–4): 401–435. doi:10.1007/s11134-009-9129-6.

[everitt-12] Everitt, D. (1986). "Simple Approximations for Token Rings". IEEE Transactions on Communications. 34 (7): 719–721. doi:10.1109/TCOM.1986.1096599.

[takagi-13] Takagi, H. (1988). "Queuing analysis of polling models". ACM Computing Surveys. 20: 5–28. doi:10.1145/62058.62059.

[14] Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586.

[15] Eisenberg, M. (1972). "Queues with Periodic Service and Changeover Time". Operations Research. 20 (2): 440–451. doi:10.1287/opre.20.2.440. JSTOR 169005.

[16] Ferguson, M. (1986). "Computation of the Variance of the Waiting Time for Token Rings". IEEE Journal on Selected Areas in Communications. 4 (6): 775–782. doi:10.1109/JSAC.1986.1146407.

[17] Sarkar, D.; Zangwill, W. I. (1989). "Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems—Exact Results and Applications". Management Science. 35 (12): 1463. doi:10.1287/mnsc.35.12.1463. JSTOR 2632232.

[18] Coffman, E. G.; Puhalskii, A. A.; Reiman, M. I. (1995). "Polling Systems with Zero Switchover Times: A Heavy-Traffic Averaging Principle". The Annals of Applied Probability. 5 (3): 681. doi:10.1214/aoap/1177004701. JSTOR 2245120.

[19] Coffman, E. G.; Puhalskii, A. A.; Reiman, M. I. (1998). "Polling Systems in Heavy Traffic: A Bessel Process Limit". Mathematics of Operations Research. 23 (2): 257–304. CiteSeerX 10.1.1.27.6730. doi:10.1287/moor.23.2.257. JSTOR 3690512.

[20] Bux, W. (1989). "Token-ring local-area networks and their performance". Proceedings of the IEEE. 77 (2): 238–256. doi:10.1109/5.18625.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]