World Library  
Flag as Inappropriate
Email this Article

Polling system

Article Id: WHEBN0040871220
Reproduction Date:

Title: Polling system  
Author: World Heritage Encyclopedia
Language: English
Subject: Queueing theory, Traffic equations, Fluid limit, Beneš method, Kingman's formula
Collection: Queueing Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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]

Contents

  • Model definition 1
    • Utilization 1.1
  • Waiting time 2
    • Expected waiting time 2.1
  • Heavy traffic 3
  • Applications 4
  • External links 5
  • References 6

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 a 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]

  • 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 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]

\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 Ci 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 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]

External links

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

References

  1. ^ a b
  2. ^
  3. ^
  4. ^
  5. ^
  6. ^
  7. ^
  8. ^
  9. ^
  10. ^
  11. ^
  12. ^ a b
  13. ^
  14. ^
  15. ^
  16. ^
  17. ^
  18. ^
  19. ^
  20. ^
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.