Polling system

Last updated
Polling server serving n queueing nodes Polling system.svg
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]

Contents

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

Utilization

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]

Waiting time

Expected waiting time

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]

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]

Related Research Articles

Queueing theory Mathematical study of waiting lines, or queues

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 results are often used when making business decisions about the resources needed to provide a service.

The birth–death process is a special case of continuous-time Markov process where the state transitions are of only two types: "births", which increase the state variable by one and "deaths", which decrease the state by one. The model's name comes from a common application, the use of such models to represent the current size of a population where the transitions are literal births and deaths. Birth–death processes have many applications in demography, queueing theory, performance engineering, epidemiology, biology and other areas. They may be used, for example, to study the evolution of bacteria, the number of people with a disease within a population, or the number of customers in line at the supermarket.

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has a product-form solution. It was the first significant development in the theory of networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research, including ideas used in the development of the Internet. The networks were first identified by James R. Jackson and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’

In queueing theory, a discipline within the mathematical theory of probability, Buzen's algorithm is an algorithm for calculating the normalization constant G(N) in the Gordon–Newell theorem. This method was first proposed by Jeffrey P. Buzen in 1973. Computing G(N) is required to compute the stationary probability distribution of a closed queueing network.

Merton's portfolio problem is a well known problem in continuous-time finance and in particular intertemporal portfolio choice. An investor must choose how much to consume and must allocate his wealth between stocks and a risk-free asset so as to maximize expected utility. The problem was formulated and solved by Robert C. Merton in 1969 both for finite lifetimes and for the infinite case. Research has continued to extend and generalize the model to include factors like transaction costs and bankruptcy.

In queueing theory, a discipline within the mathematical theory of probability, a G-network is an open network of G-queues first introduced by Erol Gelenbe as a model for queueing systems with specific control functions, such as traffic re-routing or traffic destruction, as well as a model for neural networks. A G-queue is a network of queues with several types of novel and useful customers:

In queueing theory, a discipline within the mathematical theory of probability, the Pollaczek–Khinchine formula states a relationship between the queue length and service time distribution Laplace transforms for an M/G/1 queue. The term is also used to refer to the relationships between the mean queue length and mean waiting/service time in such a model.

M/M/1 queue Queue with Markov (Poisson) arrival process, exponential service time distribution and one server

In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution. The model name is written in Kendall's notation. The model is the most elementary of queueing models and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. An extension of this model with more than one server is the M/M/c queue.

In queueing theory, a discipline within the mathematical theory of probability, Kingman's formula also known as the VUT equation, is an approximation for the mean waiting time in a G/G/1 queue. The formula is the product of three terms which depend on utilization (U), variability (V) and service time (T). It was first published by John Kingman in his 1961 paper The single server queue in heavy traffic. It is known to be generally very accurate, especially for a system operating close to saturation.

In queueing theory, a discipline within the mathematical theory of probability, the Gordon–Newell theorem is an extension of Jackson's theorem from open queueing networks to closed queueing networks of exponential servers where customers cannot leave the network. Jackson's theorem cannot be applied to closed networks because the queue length at a node in the closed network is limited by the population of the network. The Gordon–Newell theorem calculates the open network solution and then eliminates the infeasible states by renormalizing the probabilities. Calculation of the normalizing constant makes the treatment more awkward as the whole state space must be enumerated. Buzen's algorithm or mean value analysis can be used to calculate the normalizing constant more efficiently.

Fork–join queue

In queueing theory, a discipline within the mathematical theory of probability, a fork–join queue is a queue where incoming jobs are split on arrival for service by numerous servers and joined before departure. The model is often used for parallel computations or systems where products need to be obtained simultaneously from different suppliers. The key quantity of interest in this model is usually the time taken to service a complete job. The model has been described as a "key model for the performance analysis of parallel and distributed systems." Few analytical results exist for fork–join queues, but various approximations are known.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are c servers, and job service times are exponentially distributed. It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian, service times have a General distribution and there is a single server. The model name is written in Kendall's notation, and is an extension of the M/M/1 queue, where service times must be exponentially distributed. The classic application of the M/G/1 queue is to model performance of a fixed head hard disk.

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying. The term dam theory was used in earlier literature for these models. The model has been used to approximate discrete models, model the spread of wildfires, in ruin theory and to model high speed data networks. The model applies the leaky bucket algorithm to a stochastic source.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/k queue is a queue model where arrivals are Markovian, service times have a General distribution and there are k servers. The model name is written in Kendall's notation, and is an extension of the M/M/c queue, where service times must be exponentially distributed and of the M/G/1 queue with a single server. Most performance metrics for this queueing system are not known and remain an open problem.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/∞ queue is a multi-server queueing model where every arrival experiences immediate service and does not wait. In Kendall's notation it describes a system where arrivals are governed by a Poisson process, there are infinitely many servers, so jobs do not need to wait for a server. Each job has an exponentially distributed service time. It is a limit of the M/M/c queue model where the number of servers c becomes very large.

In queueing theory, a discipline within the mathematical theory of probability, a heavy traffic approximation is the matching of a queueing model with a diffusion process under some limiting conditions on the model's parameters. The first such result was published by John Kingman who showed that when the utilisation parameter of an M/M/1 queue is near 1 a scaled version of the queue length process can be accurately approximated by a reflected Brownian motion.

In queueing theory, a discipline within the mathematical theory of probability, an M/D/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation. Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory. An extension of this model with more than one server is the M/D/c queue.

In queueing theory, a discipline within the mathematical theory of probability, an M/D/c queue represents the queue length in a system having c servers, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation. Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory. The model is an extension of the M/D/1 queue which has only a single server.

In queueing theory, a discipline within the mathematical theory of probability, the G/M/1 queue represents the queue length in a system where interarrival times have a general distribution and service times for each job have an exponential distribution. The system is described in Kendall's notation where the G denotes a general distribution, M the exponential distribution for service times and the 1 that the model has a single server.

References

  1. 1 2 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. 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. 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.
  12. 1 2 Everitt, D. (1986). "Simple Approximations for Token Rings". IEEE Transactions on Communications . 34 (7): 719–721. doi:10.1109/TCOM.1986.1096599.
  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. 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.