PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Two queues with random time-limited polling

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Rocznik
Strony
257--289
Opis fizyczny
Bibliogr. 49 poz.
Twórcy
autor
  • Dept. of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
autor
  • Dept. of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
  • Dept. of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-f14e08c5-53ad-45a5-9cb3-0e29d4831348
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.