Polling system

Polling server serving n queueing nodes

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]

  1. ^ 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.
  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.