词条 | 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 definitionA 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. UtilizationDefine ρ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 timeExpected waiting timeFor 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{{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[18] and a Bessel process when switching servers takes time.[19] ApplicationsPolling systems have been used to model token ring networks.[20] External links
References1. ^1 {{Cite book | last1 = Boxma | first1 = O. J. | authorlink1 = Onno Boxma| last2 = Weststrate | first2 = J. A. | chapter = Waiting Times in Polling Systems with Markovian Server Routing | doi = 10.1007/978-3-642-75079-3_8 | title = Messung, Modellierung und Bewertung von Rechensystemen und Netzen | series = Informatik-Fachberichte | volume = 218 | pages = 89 | year = 1989 | isbn = 978-3-540-51713-9 | pmid = | pmc = }} {{Queueing theory}}2. ^{{Cite journal | last1 = Carsten | first1 = R. | last2 = Newhall | first2 = E. | last3 = Posner | first3 = M. | doi = 10.1109/TCOM.1977.1093936 | title = A Simplified Analysis of Scan Times in an Asymmetrical Newhall Loop with Exhaustive Service | journal = IEEE Transactions on Communications | volume = 25 | issue = 9 | pages = 951 | year = 1977 | pmid = | pmc = }} 3. ^{{Cite journal | last1 = Karmarkar | first1 = U. S. | title = Lot Sizes, Lead Times and In-Process Inventories | doi = 10.1287/mnsc.33.3.409 | journal = Management Science| volume = 33 | issue = 3 | pages = 409–418 | year = 1987 | pmid = | jstor = 2631860| pmc = }} 4. ^{{Cite journal | last1 = Zipkin | first1 = P. H. | doi = 10.1287/opre.34.1.91 | title = Models for Design and Control of Stochastic, Multi-Item Batch Production Systems | journal = Operations Research| volume = 34 | issue = 1 | pages = 91–104 | jstor = 170674| year = 1986 | pmid = | pmc = }} 5. ^{{Cite journal | last1 = Leibowitz | first1 = M. A. | title = Queues | doi = 10.1038/scientificamerican0868-96 | journal = Scientific American| volume = 219 | issue = 2 | pages = 96–103 | year = 1968 | pmid = | pmc = }} 6. ^{{Cite book | last1 = Takagi | first1 = H. | chapter = Analysis and Application of Polling Models | doi = 10.1007/3-540-46506-5_18 | title = Performance Evaluation: Origins and Directions | series = LNCS| volume = 1769 | pages = 423–442 | year = 2000 | isbn = 978-3-540-67193-0 | pmid = | pmc = }} 7. ^{{cite journal | last1 = Mack | first1 = C. | last2 =Murphy | first2 = T. | first3 = N. L. | last3 = Webb | year = 1957 | title = The Efficiency of N Machines Uni-Directionally Patrolled by One Operative when Walking Time and Repair Times are Constants | journal = Journal of the Royal Statistical Society. Series B (Methodological) | volume = 19 | issue = 1 | pages = 166–172 | jstor = 2984003| doi = 10.1111/j.2517-6161.1957.tb00253.x }} 8. ^{{Cite journal | last1 = Resing | first1 = J. A. C. | title = Polling systems and multitype branching processes | doi = 10.1007/BF01149263 | journal = Queueing Systems| volume = 13 | issue = 4 | pages = 409–426 | year = 1993 | pmid = | pmc = }} 9. ^{{Cite journal | last1 = Borst | first1 = S. C. | title = Polling systems with multiple coupled servers | doi = 10.1007/BF01245325 | journal = Queueing Systems| volume = 20 | issue = 3–4 | pages = 369–393 | year = 1995 | url = http://oai.cwi.nl/oai/asset/2228/2228A.pdf| pmid = | pmc = }} 10. ^{{Cite journal | last1 = Wierman | first1 = A. | authorlink1 = Adam Wierman| last2 = Winands | first2 = E. M. M. | last3 = Boxma | first3 = O. J. | authorlink3 = Onno Boxma| doi = 10.1016/j.peva.2007.06.015 | title = Scheduling in polling systems | journal = Performance Evaluation| volume = 64 | issue = 9–12 | pages = 1009 | year = 2007 | url = http://users.cms.caltech.edu/~adamw/papers/pollingsched.pdf| pmid = | pmc = | citeseerx = 10.1.1.486.2326 }} 11. ^{{Cite journal | last1 = Czerniak | first1 = O. | last2 = Yechiali | first2 = U. | doi = 10.1007/s11134-009-9129-6 | title = Fluid polling systems | journal = Queueing Systems| volume = 63 | issue = 1–4 | pages = 401–435 | year = 2009 | url = http://www.tau.ac.il/~uriy/Papers/article-questa-090311.pdf| pmid = | pmc = }} 12. ^1 {{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 | pmid = | pmc = }} 13. ^{{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 | pmid = | pmc = }} 14. ^{{cite book | title = Analysis of Queues: Methods and Applications | first = Natarajan | last = Gautam | year = 2012 | publisher = CRC Press | isbn = 9781439806586}} 15. ^{{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 | pmid = | pmc = }} 16. ^{{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 | pmid = | pmc = }} 17. ^{{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 | pmid = | jstor = 2632232| pmc = }} 18. ^{{Cite journal | last1 = Coffman | first1 = E. G. | authorlink1 = 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| pmid = | pmc = }} 19. ^{{Cite journal | last1 = Coffman | first1 = E. G. | authorlink1 = 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 | year = 1998 | pmid = | url = ftp://netlib.bell-labs.com/who/marty/mypub/POLLINGbessel.pdf| jstor = 3690512| pmc = | citeseerx = 10.1.1.27.6730 }} 20. ^{{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 | pmid = | pmc = }} 1 : Queueing theory |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。