Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2025-01-01T03:03:11.088Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Stability of Greedy Polling Systems with General Service Policies

Published online by Cambridge University Press:  27 July 2009

Serguei Foss  and
Günter Last
Serguei Foss
Affiliation:
Novosibirsk State University and Technical University of BraunschweigPF 3329, 38023 Braunschweig, Germany
Günter Last
Affiliation:
Novosibirsk State University and Technical University of BraunschweigPF 3329, 38023 Braunschweig, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a polling system with a finite number of stations fed by compound Poisson arrival streams of customers asking for service. A server travels through the system. Upon arrival at a nonempty station i, say, with x > 0 waiting customers, the server tries to serve there a random number B of customers if the queue length has not reached a random level C < x before the server has completed the B services. The random variable B may also take the value ∞ so that the server has to provide service as long as the queue length has reached size C. The distribution Hi, x of the air (B, C) may depend on i and x while the service time distribution is allowed to depend on i. The station to be visited next is chosen among some neighbors according to a greedy policy. That is to say that the server always tries to walk to the fullest station in his well-defined neighborhood. Under appropriate independence assumptions two conditions are established that are sufficient for stability and sufficient for instability. Some examples will illustrate the relevance of our results.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 12 , Issue 1 , January 1998 , pp. 49 - 68
Copyright
Copyright © Cambridge University Press 1998

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.Fayolle, G. (1989). On random walks arising in queueing systems: Ergodicity and transience via quadratic forms as Lyapunov functions—Part I. Queueing Systems 5: 167–184.CrossRefGoogle Scholar
2.Fayolle, G. & Lasgouttes, J. (1994). A state-dependent polling model with Markovian routing. INRIA Report 2279.Google Scholar
3.Foss, S. (1991). Ergodicity of queueing networks. Siberian Mathematic Journal 32: 184–203.Google Scholar
4.Foss, S. & Last, G. (1996). Stability of polling systems with exhaustive service policies and state dependent routing. Annals of Applied Probability 6: 116–137.CrossRefGoogle Scholar
5.Fricker, C. & Jaibi, M.R. (1994). Monotonicity and stability of periodic polling systems. Queueing Systems 15: 211–238.CrossRefGoogle Scholar
6.Lamperti, J. (1960). Criteria for the recurrence or transience of stochastic processes. International Journal of Mathematic Anal. Appl. 1: 314–330.CrossRefGoogle Scholar
7.Malyshev, V.A. & Men'shikov, M.V. (1982). Ergodicity, continuity and analyticity of countable Markov chains. Trans. Moscow Math. Soc. 1: 1–48.Google Scholar
8.Meyn, S.P. & Tweedy, R.L. (1993). Markov chains and stochastic stability. London: Springer-Verlag.CrossRefGoogle Scholar
9.Schassberger, R. (1995). Stability of polling networks with state-dependent server routing. Probability in the Engineering and Informational Sciences 9: 539–550.CrossRefGoogle Scholar
10.Tagaki, H. (1990). Queueing analysis of polling systems. In Takagi, H. (ed.), Stochastic analysis of computer and communication systems. Amsterdam: North-Holland, pp. 267–318.Google Scholar