Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-20T17:42:58.495Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Fluid Limit of an Overloaded Polling Model

Part of: Limit theorems Special processes Operations research and management science

Published online by Cambridge University Press:  22 February 2016

Maria Remerova ,
Sergey Foss  and
Bert Zwart
Maria Remerova*
Affiliation:
CWI
Sergey Foss*
Affiliation:
Heriot-Watt University and Sobolev Institute of Mathematics
Bert Zwart*
Affiliation:
CWI, EURANDOM, VU University Amsterdam and Georgia Institute of Technology
*
∗ Current address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands. Email address: [email protected]
∗∗ Postal address: Department of Actuarial Mathematics and Statistics, Heriot-Watt University, Edinburgh EH14 4AS, UK.
∗ Current address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In the present paper, we study the evolution of an overloaded cyclic polling model that starts empty. Exploiting a connection with multitype branching processes, we derive fluid asymptotics for the joint queue length process. Under passage to the fluid dynamics, the server switches between the queues infinitely many times in any finite time interval causing frequent oscillatory behavior of the fluid limit in the neighborhood of zero. Moreover, the fluid limit is random. In addition, we suggest a method that establishes finiteness of moments of the busy period in an M/G/1 queue.

Keywords

Cyclic pollingoverloadrandom fluid limitbranching processmulti-stage gated disciplinebusy period moment

MSC classification

Primary: 60K25: Queueing theory 60F17: Functional limit theorems; invariance principles
Secondary: 90B15: Network models, stochastic 90B22: Queues and service
Type
Research Article
Information
Advances in Applied Probability , Volume 46 , Issue 1 , March 2014 , pp. 76 - 101
Copyright
© Applied Probability Trust 

References

Altman, E. and Kushner, H. J. (2002). Control of polling in presence of vacations in heavy traffic with applications to satellite and mobile radio systems. SIAM J. Control Optimization 41, 217–252.CrossRefGoogle Scholar
Borst, S. C. (1996). Polling Systems. CWI, Amsterdam.Google Scholar
Boxma, O. J. (1991). Analysis and optimization of polling systems. In Queueing, Performance and Control in ATM, eds Cohen, J. W. and C. D. Pack. North-Holland, Amsterdam, pp. 173–183.Google Scholar
Coffman, E. G. Jr., Puhalskii, A. A. and Reiman, M. I. (1995). Polling systems with zero switchover times: a heavy-traffic averaging principle. Ann. Appl. Prob. 5, 681–719.Google Scholar
Coffman, E. G. Jr., Puhalskii, A. A. and Reiman, M. I. (1998). Polling systems in heavy traffic: a Bessel process limit. Math. Operat. Res. 23, 257–304.Google Scholar
Foss, S. (1984). Queues with customers of several types. In Advances in Probability Theory: Limit Theorems and Related Problems, ed. Borovkov, A. A.. Springer, New York, pp. 348–377.Google Scholar
Foss, S. and Kovalevskii, A. (1999). A stability criterion via fluid limits and its application to a polling model. Queueing Systems Theory Appl. 32, 131–168.Google Scholar
Harris, T. E. (1963). The Theory of Branching Processes. Springer, Berlin.CrossRefGoogle Scholar
Kesten, H. and Stigum, B. P. (1966). A limit theorem for multidimensional Galton–Watson processes. Ann. Math. Statist. 37, 1211–1223.Google Scholar
Kovalevskiı˘, A. P., Topchii, V. A. and Foss, S. G. (2005). On the stability of a queueing system with continually branching fluid limits. Problems Inf. Trans. 41, 254–279.Google Scholar
Kroese, D. P. (1997). Heavy traffic analysis for continuous polling models. J. Appl. Prob. 34, 720–732.CrossRefGoogle Scholar
Kurtz, T., Lyons, R., Pemantle, R. and Peres, Y. (1997). A conceptual proof of the Kesten–Stigum theorem for multi-type branching processes. In Classical and Modern Branching Processes (IMA Vol. Math. Appl. 84), Springer, New York, pp. 181–185.Google Scholar
Mack, C., Murphy, T. and Webb, N. L. (1957). The efficiency of N machines uni-directionally patrolled by one operative when walking time and repair times are constants. J. R. Statist. Soc. B 19, 166–172.Google Scholar
MacPhee, I., Menshikov, M., Petritis, D. and Popov, S. (2007). A Markov chain model of a polling system with parameter regeneration. Ann. Appl. Prob. 17, 1447–1473.Google Scholar
MacPhee, I., Menshikov, M., Petritis, D. and Popov, S. (2008). Polling systems with parameter regeneration, the general case. Ann. Appl. Prob. 18, 2131–2155.Google Scholar
Resing, J. A. C. (1993). Polling systems and multitype branching processes. Queueing Systems Theory Appl. 13, 409–426.Google Scholar
Takagi, H. (1986). Analysis of Polling Systems. MIT Press, Cambridge, MA.Google Scholar
Takagi, H. (1990). Queueing analysis of polling systems: an update. In Stochastic Analysis of Computer and Communication Systems, ed. Takagi, H., North-Holland, Amsterdam, pp. 267–318.Google Scholar
Takagi, H. (1997). Queueing analysis of polling models: progress in 1990–1994. In Frontiers in Queueing, CRC, Boca Raton, FL, pp. 119–146.Google Scholar
Vatutin, V. A. and Dyakonova, E. E. (2002). Multitype branching processes and some queueing systems. J. Math. Sci. (New York) 111, 3901–3911.CrossRefGoogle Scholar
Van der Mei, R. D. (2007). Towards a unifying theory on branching-type polling systems in heavy traffic. Queueing Systems 57, 29–46.Google Scholar
Van der Mei, R. D. and Resing, J. A. C. (2007). Polling models with two-stage gated service: fairness versus efficiency. In Managing Traffic Performance in Converged Networks (Lecture Notes Comput. Sci. 4516), Springer, Berlin, pp. 544–555.Google Scholar
Van der Mei, R. D. and Roubos, A. (2012). Polling models with multi-phase gated service. Ann. Operat. Res. 198, 25–56.Google Scholar
Van Wijk, A. C. C., Adan, I. J. B. F., Boxma, O. J. and Wierman, A. (2012). Fairness and efficiency for polling models with the κ-gated service discipline. Performance Evaluation 69, 274–288.Google Scholar
Yechiali, U. (1993). Analysis and control of polling systems. In Performance Evaluation of Computer and Communication Systems (Lecture Notes Comput. Sci. 729), Springer, Berlin, pp. 630–650.Google Scholar