American Institute of Mathematical Sciences

Advanced
  • 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

Jian Zhang 1,, , Tony T. Lee 2, , Tong Ye 2, and  Liang Huang 2,

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  January 2021 Early access  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.

Keywords: Continuous time Markov chain, M/G/1 queue, service rate fluctuation.
Mathematics Subject Classification: Primary: 60K20, 60K25; Secondary: 68M20.
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. 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.  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. 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.  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 Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

Figure 6.  The two-state extreme scenario
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  The transition diagram of the two service states
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

Figure 9.  Overload and underload regions
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

Figure 12.  Simulation and approximation results of mean queue lengths
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Sheng Zhu, Jinting Wang. Strategic behavior and optimal strategies in an M/G/1 queue with Bernoulli vacations. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1297-1322. doi: 10.3934/jimo.2018008
[2]

Achyutha Krishnamoorthy, Anu Nuthan Joshua. A $ {BMAP/BMSP/1} $ queue with Markov dependent arrival and Markov dependent service batches. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2925-2941. doi: 10.3934/jimo.2020101
[3]

Biao Xu, Xiuli Xu, Zhong Yao. Equilibrium and optimal balking strategies for low-priority customers in the M/G/1 queue with two classes of customers and preemptive priority. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1599-1615. doi: 10.3934/jimo.2018113
[4]

Gábor Horváth, Zsolt Saffer, Miklós Telek. Queue length analysis of a Markov-modulated vacation queue with dependent arrival and service processes and exhaustive service policy. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1365-1381. doi: 10.3934/jimo.2016077
[5]

Shan Gao, Jinting Wang. On a discrete-time GI$^X$/Geo/1/N-G queue with randomized working vacations and at most $J$ vacations. Journal of Industrial & Management Optimization, 2015, 11 (3) : 779-806. doi: 10.3934/jimo.2015.11.779
[6]

Dequan Yue, Wuyi Yue, Gang Xu. Analysis of customers' impatience in an M/M/1 queue with working vacations. Journal of Industrial & Management Optimization, 2012, 8 (4) : 895-908. doi: 10.3934/jimo.2012.8.895
[7]

Hideaki Takagi. Times until service completion and abandonment in an M/M/$ m$ preemptive-resume LCFS queue with impatient customers. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1701-1726. doi: 10.3934/jimo.2018028
[8]

Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[9]

Hideaki Takagi. Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026
[10]

Shaojun Lan, Yinghui Tang, Miaomiao Yu. System capacity optimization design and optimal threshold $N^{*}$ for a $GEO/G/1$ discrete-time queue with single server vacation and under the control of Min($N, V$)-policy. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1435-1464. doi: 10.3934/jimo.2016.12.1435
[11]

Shaojun Lan, Yinghui Tang. Performance analysis of a discrete-time $ Geo/G/1$ retrial queue with non-preemptive priority, working vacations and vacation interruption. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102
[12]

Michiel De Muynck, Herwig Bruneel, Sabine Wittevrongel. Analysis of a discrete-time queue with general service demands and phase-type service capacities. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1901-1926. doi: 10.3934/jimo.2017024
[13]

Ahmed M. K. Tarabia. Transient and steady state analysis of an M/M/1 queue with balking, catastrophes, server failures and repairs. Journal of Industrial & Management Optimization, 2011, 7 (4) : 811-823. doi: 10.3934/jimo.2011.7.811
[14]

Dequan Yue, Wuyi Yue, Guoxi Zhao. Analysis of an M/M/1 queue with vacations and impatience timers which depend on the server's states. Journal of Industrial & Management Optimization, 2016, 12 (2) : 653-666. doi: 10.3934/jimo.2016.12.653
[15]

Yutaka Sakuma, Atsushi Inoie, Ken’ichi Kawanishi, Masakiyo Miyazawa. Tail asymptotics for waiting time distribution of an M/M/s queue with general impatient time. Journal of Industrial & Management Optimization, 2011, 7 (3) : 593-606. doi: 10.3934/jimo.2011.7.593
[16]

Gopinath Panda, Veena Goswami. Effect of information on the strategic behavior of customers in a discrete-time bulk service queue. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1369-1388. doi: 10.3934/jimo.2019007
[17]

Bart Feyaerts, Stijn De Vuyst, Herwig Bruneel, Sabine Wittevrongel. The impact of the $NT$-policy on the behaviour of a discrete-time queue with general service times. Journal of Industrial & Management Optimization, 2014, 10 (1) : 131-149. doi: 10.3934/jimo.2014.10.131
[18]

Tatsuaki Kimura, Hiroyuki Masuyama, Yutaka Takahashi. Light-tailed asymptotics of GI/G/1-type Markov chains. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2093-2146. doi: 10.3934/jimo.2017033
[19]

Jerim Kim, Bara Kim, Hwa-Sung Kim. G/M/1 type structure of a risk model with general claim sizes in a Markovian environment. Journal of Industrial & Management Optimization, 2012, 8 (4) : 909-924. doi: 10.3934/jimo.2012.8.909
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (505)
  • HTML views (679)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy