Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-20T01:18:34.363Z Has data issue: false hasContentIssue false
  • English
  • Français

Continuous Polling on Graphs

Published online by Cambridge University Press:  27 July 2009

E. G. Coffman Jr  and
Aleksandr Stolyar
E. G. Coffman Jr
Affiliation:
AT & T Bell Laboratories, Murray Hill, New Jersey 07974
Aleksandr Stolyar
Affiliation:
Institute of Control Sciences, Profsoyuznaya ul. 65, GSP-312 Moscow, Russia
Get access Rights & Permissions [Opens in a new window]

Abstract

Past research on polling systems has been quite restricted in the form of the paths followed by the server. This paper formulates a general, continuous model of such paths that includes closed walks on graphs. Customers arrive by a Poisson process and have general service times. The distribution of arrivals over the path is governed by an absolutely continuous, but otherwise arbitrary, distribution. The main results include a characterization of the stationary state distribution and explicit formulas for expected waiting times. The formulas reveal an interesting decomposition of the system into two components: a fluid limit and an M/G/1 queue.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 7 , Issue 2 , April 1993 , pp. 209 - 226
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Coffman, E.G. Jr. & Gilbert, E.N. (1986). A continuous polling system with constant service times. IEEE Transactions on Information Theory IT-32: 584–591.CrossRefGoogle Scholar
2.Coffman, E.G. Jr. & Gilbert, E.N. (1987). Polling and greedy servers on the line. Queueing Systems 2: 115–145.CrossRefGoogle Scholar
3.Fuhrmann, S.W. & Cooper, R.B. (1985). Application of the decomposition principle in M/G/1 vacation models to two continuum cyclic queueing models—Especially token-ring LANs. AT&T Technology Journal 64: 1091–1098.Google Scholar
4.Fuhrmann, S.W. & Cooper, R.B. (1985). Stochastic decompositions in the M/G/1 queue with generalized vacations. Operations Research 33: 1117–1129.CrossRefGoogle Scholar
5.Konheim, A.C. & Levy, H. (1992). Descendant set: An efficient approach for the analysis of polling systems. Preprint. Department of Computer Science, Tel Aviv University, Israel.Google Scholar
6.Kroese, D.P. & Schmidt, V. (1992). A continuous polling system with general service times. Annals of Applied Probability 2: 906–927.CrossRefGoogle Scholar