
-
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
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 |
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.
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. |
[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. 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. |
[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. Google Scholar |
[20] |
BOINCstats, Available from: http://boincstats.com. Google Scholar |









[1] |
Chandra Shekhar, Amit Kumar, Shreekant Varshney, Sherif Ibrahim Ammar. $ \bf{M/G/1} $ fault-tolerant machining system with imperfection. Journal of Industrial & Management Optimization, 2021, 17 (1) : 1-28. doi: 10.3934/jimo.2019096 |
[2] |
Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170 |
[3] |
Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020167 |
[4] |
Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123 |
[5] |
Theresa Lange, Wilhelm Stannat. Mean field limit of ensemble square root filters - discrete and continuous time. Foundations of Data Science, 2021 doi: 10.3934/fods.2021003 |
[6] |
Editorial Office. Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, Stock price fluctuation prediction method based on time series analysis. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 915-915. doi: 10.3934/dcdss.2019061 |
[7] |
Guangjun Shen, Xueying Wu, Xiuwei Yin. Stabilization of stochastic differential equations driven by G-Lévy process with discrete-time feedback control. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 755-774. doi: 10.3934/dcdsb.2020133 |
[8] |
Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032 |
[9] |
Mokhtari Yacine. Boundary controllability and boundary time-varying feedback stabilization of the 1D wave equation in non-cylindrical domains. Evolution Equations & Control Theory, 2021 doi: 10.3934/eect.2021004 |
[10] |
Beom-Seok Han, Kyeong-Hun Kim, Daehan Park. A weighted Sobolev space theory for the diffusion-wave equations with time-fractional derivatives on $ C^{1} $ domains. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021002 |
[11] |
Riccarda Rossi, Ulisse Stefanelli, Marita Thomas. Rate-independent evolution of sets. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 89-119. doi: 10.3934/dcdss.2020304 |
[12] |
Editorial Office. Retraction: Wei Gao and Juan L. G. Guirao, Preface. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : ⅰ-ⅰ. doi: 10.3934/dcdss.201904i |
[13] |
Zsolt Saffer, Miklós Telek, Gábor Horváth. Analysis of Markov-modulated fluid polling systems with gated discipline. Journal of Industrial & Management Optimization, 2021, 17 (2) : 575-599. doi: 10.3934/jimo.2019124 |
[14] |
Wen Huang, Jianya Liu, Ke Wang. Möbius disjointness for skew products on a circle and a nilmanifold. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021006 |
[15] |
Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002 |
[16] |
Honglin Yang, Jiawu Peng. Coordinating a supply chain with demand information updating. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020181 |
[17] |
Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020117 |
[18] |
Patrick Martinez, Judith Vancostenoble. Lipschitz stability for the growth rate coefficients in a nonlinear Fisher-KPP equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 695-721. doi: 10.3934/dcdss.2020362 |
[19] |
Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020127 |
[20] |
Xin Zhao, Tao Feng, Liang Wang, Zhipeng Qiu. Threshold dynamics and sensitivity analysis of a stochastic semi-Markov switched SIRS epidemic model with nonlinear incidence and vaccination. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2021010 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]