Abstract
This study is devoted to a queueing analysis of polling systems with a probabilistic server routing mechanism. A single server serves a number of queues, switching between the queues according to a discrete time parameter Markov chain. The switchover times between queues are nonneghgible. It is observed that the total amount of work in this Markovian polling system can be decomposed into two independent parts, viz., (i) the total amount of work in the corresponding system without switchover times and (ii) the amount of work in the system at some epoch covered by a switching interval. This work decomposition leads to a pseudoconservation law for mean waiting times, i.e., an exact expression for a weighted sum of the mean waiting times at all queues. The results generalize known results for polling systems with strictly cyclic service.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boxma, O.J. (1989). Workloads and waiting times in single-server systems with multiple customer classes. To appear in Queueing Systems.
Boxma, O. J., Groenendijk, W.P. (1987). Pseudo-conservation laws in cyclic-service systems. J. Appl. Prob. 24, 949–964.
Boxma, O.J., Groenendijk, W.P., Weststrate, J.A. (1988). A pseudoconservation law for service systems with a polling table. Report Centre for Mathematics and Computer Science, Amsterdam; to appear in IEEE Trans. Commun.
Boxma, O.J., Meister, B. (1987). Waiting-time approximations for cyclic-service systems with switchover times, Performance Evaluation 7, 299–308.
Chung, K.L. (1967). Markov Chains with Stationary Transition Probabilities (Springer, Berlin; 2nd ed.).
Cinlar, E. (1975). Introduction to Stochastic Processes (Prentice Hall, Englewood Cliffs, NJ).
Cohen, J.W. (1982). The Single Server Queue (North-Holland, Amsterdam; 2nd ed.).
Groenendijk, W.P. (1988). Waiting-time approximations for cyclic-service systems with mixed service strategies, in: M. Bonatti (ed.), Proceedings ITC-12 (North-Holland, Amsterdam).
Keilson, J., Servi, L.D. (1986). Oscillating random walk models for GI/G/1 vacation systems with Bernoulli schedules. J. Appl. Prob. 23, 790–802.
Kelly, F.P. (1979). Reversibility and Stochastic Networks (Wiley, New York).
Kleinrock, L., Levy, H. (1988). The analysis of random polling systems. Oper. Res. 36, 716–732.
Levy, H. (1984). Non-Uniform Structures and Synchronization Patterns in Shared-Channel Communication Networks. CSD-840049, Computer Science Department, University of California, Los Angeles, Ph.D. Dissertation.
Levy, H., Sidi, M. (1988). Correlated arrivals in polling systems. Report Department of Computer Science, Tel Aviv University.
Mitrani, L, Adams, J.L., Falconer, R.M. (1986). A modelling study of the Orwell ring protocol. In: Teletraffic Analysis and Computer Performance Evaluation, eds. O.J. Boxma, J.W. Cohen and H.C. Tijms (North-Holland, Amsterdam), pp. 429–438.
E. Seneta (1981). Non-negative Matrices and Markov Chains (Springer, New York; 2nd ed.).
Takagi, H. (1986). Analysis of Polling Systems (The MIT Press, Cambridge, MA).
Takagi, H. (1988). Queuing analysis of polling models. ACM Comput. Surveys 20, 5–28.
Tedijanto (1988). Exact results for the cyclic-service queue with a Bernoulli schedule. Report Electrical Engineering Department and Systems Research Center, University of Maryland.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boxma, O.J., Weststrate, J.A. (1989). Waiting Times in Polling Systems with Markovian Server Routing. In: Stiege, G., Lie, J.S. (eds) Messung, Modellierung und Bewertung von Rechensystemen und Netzen. Informatik-Fachberichte, vol 218. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-75079-3_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-75079-3_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51713-9
Online ISBN: 978-3-642-75079-3
eBook Packages: Springer Book Archive