• Previous Article
    A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size
  • JIMO Home
  • This Issue
  • Next Article
    Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods
January  2021, 17(1): 185-204. doi: 10.3934/jimo.2019106

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

1. 

Shanghai Jiao Tong University, 800 Dongchuan Rd, Shanghai, China

2. 

The Chinese University of Hong Kong(Shenzhen), Shanghai Jiao Tong University, Zhejiang University of Technology

* Corresponding author: Jian Zhang

Received  October 2018 Revised  May 2019 Published  September 2019

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.

Citation: Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
References:
[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.  Google Scholar

[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.  Google Scholar

[3]

M. Eisen and M. Tainiter, Stochastic variations in queuing processes, Operations Res., 11 (1963), 922–927. doi: 10.1287/opre.11.6.922.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8] F. P. Kelly, Reversibility and stochastic networks, Cambridge University Press, 2011.   Google Scholar
[9]

L. Kleinrock, Queueing Systems, Volume 1, Theory, John Wiley & Sons, New York, 1975.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

J. ZhangZ. ZhouT. 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.  Google Scholar

[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. Google Scholar

[20]

BOINCstats, Available from: http://boincstats.com. Google Scholar

show all references

References:
[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.  Google Scholar

[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.  Google Scholar

[3]

M. Eisen and M. Tainiter, Stochastic variations in queuing processes, Operations Res., 11 (1963), 922–927. doi: 10.1287/opre.11.6.922.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8] F. P. Kelly, Reversibility and stochastic networks, Cambridge University Press, 2011.   Google Scholar
[9]

L. Kleinrock, Queueing Systems, Volume 1, Theory, John Wiley & Sons, New York, 1975.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

J. ZhangZ. ZhouT. 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.  Google Scholar

[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. Google Scholar

[20]

BOINCstats, Available from: http://boincstats.com. Google Scholar

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 9.  Overload and underload regions
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]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210

[2]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169

[3]

Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1

[4]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907

[5]

Liqin Qian, Xiwang Cao. Character sums over a non-chain ring and their applications. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020134

[6]

Min Li, Jiahua Zhang, Yifan Xu, Wei Wang. Effects of disruption risk on a supply chain with a risk-averse retailer. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021024

[7]

Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199

[8]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379

[9]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[10]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075

[11]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[12]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493

[13]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189

[14]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258

[15]

Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195

[16]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269

[17]

Benrong Zheng, Xianpei Hong. Effects of take-back legislation on pricing and coordination in a closed-loop supply chain. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021035

[18]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[19]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045

[20]

Ravi Anand, Dibyendu Roy, Santanu Sarkar. Some results on lightweight stream ciphers Fountain v1 & Lizard. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020128

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (246)
  • HTML views (497)
  • Cited by (0)

Other articles
by authors

[Back to Top]