Article Contents
Article Contents

# An approximate mean queue length formula for queueing systems with varying service rate

• * Corresponding author: Jian Zhang
• In this paper, we analyze the delay performance of queueing systems in which the service rate varies with time and the number of service states may be infinite. Except in some simple special cases, in general, the queueing model with varying service rate is mathematically intractable. Motivated by the P-K formula for M/G/1 queue, we developed a limiting analysis approach based on the connection between the fluctuation of service rate and the mean queue length. Considering the two extreme service rates, we provide a lower bound and upper bound of mean queue length. Furthermore, an approximate mean queue length formula is derived from the convex combination of these two bounds. The accuracy of our approximation has been confirmed by extensive simulation studies with different system parameters. We also verified that all limiting cases of the system behavior are consistent with the predictions made by our formula.

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

 Citation:

• Figure 1.  The continuous time Markov chain of the server process

Figure 2.  The continuous-time Markov chain of the queueing model

Figure 3.  The fluctuation of service rate $\mu$ over the time with parameter $\frac{\mu_c}{\mu_s} = 10$, $\lambda_s = 10$

Figure 4.  The first and second moments of service time increase with the variance of the service rate

Figure 5.  Service rate becomes a constant when system reaches equilibrium

Figure 6.  The two-state extreme scenario

Figure 7.  The transition diagram of the two service states

Figure 8.  Mean queue length $L$ is bounded by $L_1$ and $L_2$

Figure 10.  Overload probability $a$ vs. parameter $\alpha$

Figure 11.  Mean queue length in overload region $L_{overload}$ and overload probability $a$

Figure 12.  Simulation and approximation results of mean queue lengths

•  [1] D. P. Anderson, BOINC: A system for public-resource computing and storage, In Proceedings of the Workshop on Grid Computing, (2004). doi: 10.1109/GRID.2004.14. [2] D. P. Anderson, J. Cobb, E. Korpela, M. Lebofsky, and D. Werthimer, SETI@home: An experiment in public resource computing, Communications of the ACM, 45 (2002), 56-61. doi: 10.1145/581571.581573. [3] M. Eisen and M. Tainiter, Stochastic variations in queuing processes, Operations Res., 11 (1963), 922–927. doi: 10.1287/opre.11.6.922. [4] T. Estrada, M. Taufer and D. P. Anderson, Performance prediction and analysis of BOINC projects: An empirical study with EmBOINC, Journal of Grid Computing, 7 (2009), 537–554. doi: 10.1007/s10723-009-9126-3. [5] B. Fan, D. Chiu and J. Lui, The Delicate Tradeoffs in BitTorrent-like File Sharing Protocol Design, In Proceedings of the 2006 IEEE International Conference on Network Protocols, (2006), 239–248. doi: 10.1109/ICNP.2006.320217. [6] N. Gunaseelan, L. Liu, J. F. Chamberland and G. H. Huff, Performance analysis of wireless Hybrid-ARQ systems with delay-sensitive traffic, IEEE Transactions on Communications, 58 (2010), 1262–1272. doi: 10.1109/TCOMM.2010.04.090104. [7] L. Huang and T. T. Lee, Generalized Pollaczek-Khinchin formula for Markov channels, IEEE Transactions on Communications, 61 (2013), 3530–3540. doi: 10.1109/TCOMM.2013.061913.120712. [8] F. P. Kelly,  Reversibility and stochastic networks, Cambridge University Press, 2011. [9] L. Kleinrock, Queueing Systems, Volume 1, Theory, John Wiley & Sons, New York, 1975. [10] R. Kumar, Y. Liu and K. Ross, Stochastic Fluid Theory for P2P Streaming Systems, In IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, (2007), 919–927. doi: 10.1109/INFCOM.2007.112. [11] H. Li and T. Yang, Queues with a variable number of servers, European J. Oper. Res., 124 (2000), 615–628. doi: 10.1016/S0377-2217(99)00175-7. [12] S. R. Mahabhashyam and N. Gautam, On queues with Markov modulated service rates, Queueing Syst., 51 (2005), 89–113. doi: 10.1007/s11134-005-2158-x. [13] M. F. Neuts,  Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, John Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1981. [14] T. Phung-Duc, W. Rogiest and S. Wittevrongel, Single server retrial queues with speed scaling: Analysis and performance evaluation, J. Ind. Manag. Optim., 13 (2017), 1927–1943. doi: 10.3934/jimo.2017025. [15] B. A. Salihu, P. Li, L. Sang, Z. Li, Y. Gao and D. Yang, Network calculus delay bounds in multi-server queueing networks with stochastic arrivals and stochastic services, In Global Communications Conference (GLOBECOM), IEEE (2015), 1–7. doi: 10.1109/GLOCOM.2014.7417645. [16] M. Yajima, and T. Phung-Duc, Batch arrival single server queue with variable service speed and setup time, Queueing Syst., 86 (2017), 241–260. doi: 10.1007/s11134-017-9533-2. [17] M. Yajima and T. Phung-Duc, A central limit theorem for a Markov-modulated infinite-server queue with batch Poisson arrivals and binomial catastrophes, Performance Evaluation, 129 (2019), 2–14. doi: 10.1016/j.peva.2018.10.002. [18] J. Zhang, Z. Zhou, T. T. Lee and T. Ye, Delay analysis of three-state Markov channels, in Lecture Notes of Computer Science, 10591 (2017), 101-117.  doi: 10.1007/978-3-319-68520-5_7. [19] J. Zheng, C. Luo and L. Yu, Performance analysis of stochastic multi server systems, In Communications and Networking in China (ChinaCom), 2015 10th International Conference on, IEEE (2015), 562–566. [20] BOINCstats, Available from: http://boincstats.com.

Figures(12)