Two queues with random time-limited polling

• Autorzy: Saxena M. , Boxma O. , Kapodistria S. , Núñez-Queija R.

Identyfikatory

DOI

10.19195/0208-4147.37.2.4

• Języki publikacji: EN

Abstrakty

EN

In this paper, we analyse a single server polling model with two queues. Customers arrive at the two queues according to two independent Poisson processes. There is a single server that serves both queues with generally distributed service times. The server spends an exponentially distributed amount of time in each queue. After the completion of this residing time, the server instantaneously switches to the other queue, i.e., there is no switch-over time. For this polling model we derive the steady-state marginal workload distribution, as well as heavy traffic and heavy tail asymptotic results. Furthermore, we also calculate the joint queue length distribution for the special case of exponentially distributed service times using singular perturbation analysis.

Słowa kluczowe

EN

polling model; workload decomposition; heavy traffic; heavy tail asymptotics; singular perturbation analysis; time-scale separation; geometric ergodicity

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2017
• Tom: Vol. 37, Fasc. 2
• Strony: 257--289
• Opis fizyczny: Bibliogr. 49 poz.

Twórcy

autor

Saxena M.

• Dept. of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

autor

Boxma O.

• Dept. of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

autor

Kapodistria S.

• Dept. of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

autor

Núñez-Queija R.

• Korteweg-de Vries Institute for Mathematics, University of Amsterdam, Amsterdam, The Netherlands

Bibliografia

• [1] A. Al Hanbali, R. de Haan, R. J. Boucherie, and J. C. W. van Ommeren, Time-limited polling systems with batch arrivals and phase-type service times, Ann. Oper. Res. 198 (1) (2012), pp. 57-82.
• [2] E. Altman, Analysing timed-token ring protocols using the power-series algorithm, in: The Fundamental Role of Teletraffic in the Evolution of Telecommunications Networks, J. Labetoulle and J. W. Roberts (Eds.), Elsevier, Amsterdam 1994, pp. 961-971.
• [3] E. Altman, K. E. Avrachenkov, and R. Núñez-Queija, Perturbation analysis for denumerable Markov chains with application to queueing models, Adv. in Appl. Probab. 36 (3) (2004), pp. 839-853.
• [4] E. Altman, P. Konstantopoulos, and Z. Liu, Stability, monotonicity and invariant quantities in general polling systems, Queueing Syst. 11 (1) (1992), pp. 35-57.
• [5] B. Avi-Itzhak and P. Naor, Some queuing problems with the service station subject to breakdown, Oper. Res. 11 (3) (1963), pp. 303-320.
• [6] F. Baccelli and A. M. Makowski, Stability and bounds for single server queues in random environment, Stoch. Models 2 (2) (1986), pp. 281-291.
• [7] N. H. Bingham, C. M. Goldie, and J. L. Teugels, Regular Variation, Cambridge University Press, Cambridge 1989.
• [8] M. A. A. Boon, R. D. van der Mei, and E. M. M. Winands, Applications of polling systems, Surv. Oper. Res. Manag. Sci. 16 (2011), pp. 67-82.
• [9] M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, Contemp. Math. 520 (2010), pp. 1-40.
• [10] O. J. Boxma, Workloads and waiting times in single-server systems with multiple customer classes, Queueing Syst. 5 (1-3) (1989), pp. 185-214.
• [11] O. J. Boxma and J. W. Cohen, Heavy-traffic analysis for the GI/G/1 queue with heavy-tailed distributions, Queueing Syst. 33 (1-3) (1999), pp. 177-204.
• [12] O. J. Boxma, Q. Deng, and J. A. C. Resing, Polling systems with regularly varying service and/or switchover times, Adv. Perf. Anal. 3 (2) (2000), pp. 71-107.
• [13] O. J. Boxma and G. J. van Houtum, The compensation approach applied to a 2 × 2 switch, Probab. Engrg. Inform. Sci. 7 (1993), pp. 471-493.
• [14] O. J. Boxma and I. A. Kurkova, The M/G/1 queue with two service speeds, Adv. in Appl. Probab. 33 (2001), pp. 520-540.
• [15] J. Cao and W. Xie, Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines, Queueing Syst. 85 (1-2) (2017), pp. 117-147.
• [16] E. G. Coffman Jr., G. Fayolle, and I. Mitrani, Two queues with alternating service periods, in: Performance ’87, P. J. Courtois and G. Latouche (Eds.), North-Holland, Amsterdam 1988, pp. 227-239.
• [17] J. W. Cohen, Some results on regular variation for distributions in queueing and fluctuation theory, J. Appl. Probab. 10 (1973), pp. 343-353.
• [18] J. W. Cohen, The Single Server Queue, Elsevier, Amsterdam 2012.
• [19] J. W. Cohen and O. J. Boxma, Boundary Value Problems in Queueing System Analysis, Elsevier, Amsterdam 2000.
• [20] P. J. Courtois, Decomposability: Queueing and Computer System Applications, Academic Press, 2014.
• [21] R. de Haan, R. J. Boucherie, and J. C. W. van Ommeren, A polling model with an autonomous server, Queueing Syst. 62 (3) (2009), pp. 279-308.
• [22] F. Delebecque, A reduction process for perturbed Markov chains, SIAM J. Appl. Math. 43 (2) (1983), pp. 325-350.
• [23] I. Eliazar and U. Yechiali, Polling under the randomly timed gated regime, Stoch. Models 14 (1-2) (1998), pp. 79-93.
• [24] G. Fayolle, R. Iasnogorodski, and V. Malyshev, RandomWalks in the Quarter Plane: Algebraic Methods, Boundary Value Problems and Applications, Springer, Berlin 1999.
• [25] A. Federgruen and L. Green, Queueing systems with service interruptions, Oper. Res. 34 (5) (1986), pp. 752-768.
• [26] D. Fiems, T. Maertens, and H. Bruneel, Queueing systems with different types of server interruptions, European J. Oper. Res. 188 (3) (2008), pp. 838-845.
• [27] S. W. Fuhrmann and R. B. Cooper, Stochastic decompositions in the M/G/1 queue with generalized vacations, Oper. Res. 33 (5) (1985), pp. 1117-1129.
• [28] D. P. Gaver, A waiting line with interrupted service, including priorities, J. Roy. Statist. Soc. Ser. B 24 (1) (1962), pp. 73-90.
• [29] E. J. Jance van Rensburg, T. Prellberg, and A. Rechnitzer, Partially directed paths in a wedge, J. Combin. Theory Ser. A 115 (4) (2008), pp. 623-650.
• [30] T. Katayama, Waiting time analysis for a queueing system with time-limited service and exponential timer, Naval Res. Logist. 48 (7) (2001), pp. 638-651.
• [31] G. Kramer, B. Mukherjee, and G. Pesavento, IPACT a dynamic protocol for an Ethernet PON (EPON), IEEE Commun. Mag. 40 (2) (2002), pp. 74-80.
• [32] A. Krishnamoorthy, P. Pramod, and S. Chakravarthy, Queues with interruptions: A survey, TOP 22 (1) (2014), pp. 290-320.
• [33] H. Levy and M. Sidi, Polling systems: applications, modelling and optimization, IEEE Trans. Commun. 38 (10) (1990), pp. 1750-1760.
• [34] S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, Springer, London 1993.
• [35] L. W. Miller, Alternating Priorities in Multi-Class Queues, Ph.D. thesis, Cornell University, Ithaca, NY, 1964.
• [36] A. A. Pervozvanskii and V. G. Gaitsgori, Theory of Suboptimal Decisions: Decomposition and Aggregation, Springer Science & Business Media, 2013.
• [37] J. A. C. Resing, Polling systems and multitype branching processes, Queueing Syst. 13 (4) (1993), pp. 409-426.
• [38] K. Sigman, Appendix: A primer on heavy-tailed distributions, Queueing Syst. 33 (1-3) (1999), pp. 261-275.
• [39] F. M. Spieksma, Geometrically Ergodic Markov Chains and the Optimal Control of Queues, Ph.D. thesis, Leiden University, 1990.
• [40] H. Takagi, Queuing analysis of polling models, ACM Comput. Surv. 20 (1) (1988), pp. 5-28.
• [41] H. Takagi, Application of polling models to computer networks, Comput. Netw. ISDN Syst. 22 (3) (1991), pp. 193-211.
• [42] H. Takagi, Queueing Analysis. Volume 1: Vacation and Priority Systems, North-Holland, Amsterdam 1991.
• [43] H. Takagi, Analysis and application of polling models, in: Performance Evaluation: Origins and Directions, G. Haring, C. Lindemann, and M. Reiser (Eds.), Springer, Berlin-Heidelberg 2000, pp. 423-442.
• [44] T. Takine and B. Sengupta, A single server queue with service interruptions, Queueing Syst. 26 (3) (1997), pp. 285-300.
• [45] K. Thiruvengadam, Queuing with breakdowns, Oper. Res. 11 (1) (1963), pp. 62-71.
• [46] V. M. Vishnevskii and O. V. Semenova, Mathematical methods to study the polling systems, Autom. Remote Control 67 (2) (2006), pp. 173-220.
• [47] H. White and L. S. Christie, Queuing with preemptive priorities or with breakdown, Oper. Res. 6 (1) (1958), pp. 79-95.
• [48] J. Xie, M. J. Fischer, and C. M. Harris, Workload and waiting time in a fixed-time loop system, Comput. Oper. Res. 24 (8) (1997), pp. 789-803.
• [49] A. P. Zwart, Queueing Systems with Heavy Tails, Ph.D. thesis, Eindhoven University of Technology, 2001.

Uwagi

This paper is dedicated to Tomasz Rolski, in friendship, respect and admiration. His love of applied probability and never-ending curiosity are a blessing for our field.

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).