Analysis of a discrete-time queue with general service demands and phase-type service capacities

Michiel De Muynck; Herwig Bruneel; Sabine Wittevrongel

doi:10.3934/jimo.2017024

Article Contents

2017, Volume 13, Issue 4: 1901-1926. Doi: 10.3934/jimo.2017024

This issue Previous Article A new analytical model for optimized cognitive radio networks based on stochastic geometry Next Article Single server retrial queues with speed scaling: Analysis and performance evaluation

Analysis of a discrete-time queue with general service demands and phase-type service capacities

SMACS Research Group, Department of Telecommunications and Information Processing, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium

* Corresponding author: Michiel De Muynck.
* Corresponding author: Michiel De Muynck.

Received: October 2015

Published: November 2017

Abstract / Introduction Full Text(HTML) Figure(4) Related Papers Cited by

Abstract

In this paper, we analyze a non-classical discrete-time queueing model where customers demand variable amounts of work from a server that is able to perform this work at a varying rate. The service demands of the customers are integer numbers of work units. They are assumed to be independent and identically distributed (i.i.d.) random variables. The service capacities, i.e., the numbers of work units that the server can process in the consecutive slots, are also assumed to be i.i.d. and their common probability generating function (pgf) is assumed to be rational. New customers arrive in the queueing system according to a general independent arrival process. For this queueing model we present an analysis method, which is based on complex contour integration. Expressions are obtained for the pgfs, the mean values and the tail probabilities of the customer delay and the system content in steady state. The analysis is illustrated by means of some numerical examples.

Keywords:

Mathematics Subject Classification: Primary: 60K25, 90B22; Secondary: 68M20.

Citation:

Full Text(HTML)

Figure 3. Mean system content versus the mean service demand $\tau$ for Poisson arrivals with $\lambda=0.9$, shifted geometric service demands and various service-capacity distributions (as indicated), with mean $\mu = \tau$.

Download: Full-size image PowerPoint slide

Figure 1. Mean customer delay versus the load $\rho$, for Poisson arrivals with varying $\lambda$, deterministic service demands with $\tau=11$ and various service-capacity distributions (as indicated), all with mean $\mu=10$.

Download: Full-size image PowerPoint slide

Figure 2. Variance of the customer delay versus the load $\rho$, for Poisson arrivals with varying $\lambda$, deterministic service demands with $\tau=11$ and various service-capacity distributions (as indicated), all with mean $\mu=10$.

Download: Full-size image PowerPoint slide

Figure 4. Dominant-pole approximation of the tail probabilities of the system content, for Poisson arrivals with $\lambda=3$, uniformly distributed service demands from 1 to 10 work units, and negative binomial service capacities with $\mu=10$ and various values of the parameter $m$, as well as deterministic service capacities.

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	J. Abate and W. Whitt, Numerical inversion of probability generating functions, Oper. Res. Letters, 12 (1992), 245-251. doi: 10.1016/0167-6377(92)90050-D.
[2]	I. J. B. F. Adan and V. G. Kulkarni, Single-server queue with Markov-dependent inter-arrival and service times, Queueing Systems, 45 (2003), 113-134. doi: 10.1023/A:1026093622185.
[3]	I. J. B. F. Adan, J. S. H. van Leeuwaarden and E. M. M. Winands, On the application of Rouché's theorem in queueing theory, Oper. Res. Letters, 34 (2006), 355-360. doi: 10.1016/j.orl.2005.05.012.
[4]	S. Ayed, D. Sofiene and R. Nidhal, Joint optimisation of maintenance and production policies considering random demand and variable production rate, International Journal Of Production Research, 50 (2011), 6870-6885. doi: 10.1080/00207543.2011.631601.
[5]	J. W. Bosman, R. D. van der Mei and R. Nunez-Queija, A fluid model analysis of streaming media in the presence of time-varying bandwidth, Proc. ITC 24, 2012, 177-184.
[6]	O. J. Boxma and I. A. Kurkova, The M/G/1 queue with two service speeds, Advances in Applied Probability, 33 (2001), 520-540. doi: 10.1239/aap/999188327.
[7]	H. Bruneel and B. G. Kim, Discrete-time Models for Communication Systems Including ATM, Kluwer Academic, Boston, USA, 1993. doi: 10.1007/978-1-4615-3130-2.
[8]	H. Bruneel, S. Wittevrongel, D. Claeys and J. Walraevens, Discrete-time queues with variable service capacity: A basic model and its analysis, Annals of Operations Research, 239 (2016), 359-380. doi: 10.1007/s10479-013-1428-y.
[9]	H. Bruneel, W. Rogiest, J. Walraevens and S. Wittevrongel, On queues with general service demands and constant service capacity, LNCS, 8657 (2014), 210-225. doi: 10.1007/978-3-319-10696-0_17.
[10]	M. Chen, X. Jin, Y. Wang, X. Q. Cheng and G. Min, Modelling priority queuing systems with varying service capacity, Frontiers of Computer Science, 7 (2013), 571-582. doi: 10.1007/s11704-013-2365-2.
[11]	M. De Muynck, S. Wittevrongel and H. Bruneel, Analysis of discrete-time queues with general service demands and finite-support service capacities, Annals of Operations Research, accepted for publication, (2015), 1-26. doi: 10.1007/s10479-015-2060-9.
[12]	M. De Muynck, H. Bruneel and S. Wittevrongel, Delay analysis of a queue with general service demands and phase-type service capacities, AISC, 383 (2015), 29-39. doi: 10.1007/978-3-319-22267-7_3.
[13]	B. Feyaerts, S. De Vuyst, H. Bruneel and S. Wittevrongel, Performance analysis of buffers with train arrivals and correlated output interruptions, Journal of Industrial and Management Optimization, 11 (2015), 829-848. doi: 10.3934/jimo.2015.11.829.
[14]	S. Gao and J. Wang, On a discrete-time GI^X/Geo/1/N-G queue with randomized working vacations and at most J vacations, Journal of Industrial and Management Optimization, 11 (2015), 779-806. doi: 10.3934/jimo.2015.11.779.
[15]	B. Giri, W. Yun and T. Dohi, Optimal design of unreliable production-inventory systems with variable production rate, European Journal of Operational Research, 162 (2005), 372-386. doi: 10.1016/j.ejor.2003.10.015.
[16]	M. O. González, Classical Complex Analysis, Marcel Dekker, New York, 1992.
[17]	U. C. Gupta and V. Goswami, Performance analysis of finite buffer discrete-time queue with bulk service, Computers & Operations Research, 29 (2002), 1331-1341. doi: 10.1016/S0305-0548(01)00034-X.
[18]	S. Halfin, Steady-state distribution for the buffer content of an M/G/1 queue with varying service rate, SIAM Journal on Applied Mathematics, 23 (1972), 356-363. doi: 10.1137/0123037.
[19]	X. Jin, G. Min, S. Velentzas and J. Jiang, Quality-of-service analysis of queuing systems with long-range-dependent network traffic and variable service capacity, IEEE Transactions on Wireless Communications, 11 (2012), 562-570. doi: 10.1109/TWC.2011.120511.100867.
[20]	E. Kafetzakis, K. Kontovasilis and I. Stavrakakis, Effective-capacity-based stochastic delay guarantees for systems with time-varying servers, with an application to IEEE 802.11 WLANs, Performance Evaluation, 68 (2011), 614-628. doi: 10.1016/j.peva.2011.03.010.
[21]	B. Kim and J. Kim, A single server queue with Markov modulated service rates and impatient customers, Performance Evaluation, 83/84 (2015), 1-15. doi: 10.1016/j.peva.2014.11.002.
[22]	L. Kleinrock, Queueing Systems, Volume I: Theory, Wiley, New York, 1976. doi: 10.1002/net.3230060210.
[23]	G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, Society for Industrial and Applied Mathematics, 1987. doi: 10.1137/1.9780898719734.
[24]	S. R. Mahabhashyam and N. Gautam, On queues with Markov modulated service rates, Queueing Systems, 51 (2005), 89-113. doi: 10.1007/s11134-005-2158-x.
[25]	I. Mitrani, Modelling of Computer and Communication Systems, Cambridge University Press, Cambridge, 1987.
[26]	Z. Saffer and M. Telek, Analysis of BMAP vacation queue and its application to IEEE 802.16e sleep mode, Journal of Industrial and Management Optimization, 6 (2010), 661-690. doi: 10.3934/jimo.2010.6.661.
[27]	Z. Saffer and W. Yue, M/M/c multiple synchronous vacation model with gated discipline, Journal of Industrial and Management Optimization, 8 (2012), 939-968. doi: 10.3934/jimo.2012.8.939.
[28]	T. Takine, Single-server queues with Markov-modulated arrivals and service speed, Queueing Systems, 49 (2005), 7-22. doi: 10.1007/s11134-004-5553-9.
[29]	B. Vinck and H. Bruneel, Analyzing the discrete-time G^(G)/Geo/1 queue using complex contour integration, Queueing Systems, 18 (1994), 47-67. doi: 10.1007/BF01158774.
[30]	M. Vlasiou, I. J. B. F. Adan and O. J. Boxma, A two-station queue with dependent preparation and service times, European Journal of Operational Research, 195 (2009), 104-116. doi: 10.1016/j.ejor.2008.01.027.
[31]	J. Walraevens, H. Bruneel, D. Claeys and S. Wittevrongel, The discrete-time queue with geometrically distributed service capacities revisited, LNCS, 7984 (2013), 443-456. doi: 10.1007/978-3-642-39408-9_31.
[32]	Y. Yao and D. Wei-Chung Miao, Sample-path analysis of general arrival queueing systems with constant amount of work for all customers, Queueing Systems, 76 (2014), 283-308. doi: 10.1007/s11134-013-9361-y.