American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Delay characteristics in place-reservation queues with class-dependent service times
  • JIMO Home
  • This Issue
  • Next Article
    Performance evaluation and optimization of cognitive radio networks with adjustable access control for multiple secondary users
January  2019, 15(1): 15-35. doi: 10.3934/jimo.2018030

Multiserver retrial queue with setup time and its application to data centers

Tuan Phung-Duc 1,, and  Ken'ichi Kawanishi 2,

1. 

Division of Policy and Planning Sciences, Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan
2. 

Division of Electronics and Informatics, Gunma University, 1-5-1 Tenjin-cho, Kiryu, Gunma 376-8515, Japan

* Corresponding author

Received  February 2017 Revised  July 2017 Published  February 2018

Fund Project: The reviewing process of this paper was handled by Yutaka Takahashi and Wuyi Yue.

This paper considers a multiserver retrial queue with setup time which is motivated from application in data centers with the ON-OFF policy, where an idle server is immediately turned off. The ON-OFF policy is designed to save energy consumption of idle servers because an idle server still consumes about 60% of its peak consumption processing jobs. Upon arrival, a job is allocated to one of available off-servers and that server is started up. Otherwise, if all the servers are not available upon arrival, the job is blocked and retries in a random time. A server needs some setup time during which the server cannot process a job but consumes energy. We formulate this model using a three-dimensional continuous-time Markov chain obtaining the stability condition via Foster-Lyapunov criteria. Interestingly, the stability condition is different from that of the corresponding non-retrial queue. Furthermore, exploiting the special structure of the Markov chain together with a heuristic technique, we develop an efficient algorithm for computing the stationary distribution. Numerical results reveal that under the ON-OFF policy, allowing retrials is more power-saving than buffering jobs. Furthermore, we obtain a new insight that if the setup time is relatively long, setting an appropriate retrial time could reduce both power consumption and the mean response time of jobs.

Keywords: Data center, power consumption, delay, trade-off, retrials.
Mathematics Subject Classification: 60K25, 68M20, 90B22.
Citation: Tuan Phung-Duc, Ken'ichi Kawanishi. Multiserver retrial queue with setup time and its application to data centers. Journal of Industrial & Management Optimization, 2019, 15 (1) : 15-35. doi: 10.3934/jimo.2018030
References:
[1]

J. R. Artalejo and T. Phung-Duc, Markovian retrial queues with two way communication, Journal of Industrial and Management Optimization, 8 (2012), 781-806.  doi: 10.3934/jimo.2012.8.781.  Google Scholar

[2]

L. A. Barroso and U. Hölzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37.  doi: 10.1109/MC.2007.443.  Google Scholar

[3]

L. Bright and P. G. Taylor, Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, Stochastic Models, 11 (1995), 497-525.  doi: 10.1080/15326349508807357.  Google Scholar

[4]

J. Chang and J. Wang, Unreliable M/M/1/1 retrial queues with set-up time, Quality Technology & Quantitative Management, (2017), 1-13.  doi: 10.1080/16843703.2017.1320459.  Google Scholar

[5]

J. E. Diamond and A. S. Alfa, The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177.  doi: 10.1080/15326349808807518.  Google Scholar

[6]

J. E. Diamond and A. S. Alfa, Matrix analytic methods for a multiserver retrial queue with buffer, Top, 7 (1999), 249-266.  doi: 10.1007/BF02564725.  Google Scholar

[7]

G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997. Google Scholar

[8]

A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138.   Google Scholar

[9]

A. Gandhi, S. Doroudi and M. Harchol-Balter, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Queueing Systems, 77 (2014), 177-209.  doi: 10.1007/s11134-014-9409-7.  Google Scholar

[10]

Q.-M. He, H. Li and Y. Q. Zhao, Ergodicity of the BMAP/PH/s/s + K retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347.  doi: 10.1023/A:1019110631467.  Google Scholar

[11]

G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death process, Journal of Applied Probability, 30 (1993), 650-674.  doi: 10.1017/S0021900200044387.  Google Scholar

[12]

G. Latouche and V. Ramaswami, Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999.  Google Scholar

[13]

E. Morozov, A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168.  doi: 10.1007/s11134-007-9024-y.  Google Scholar

[14]

E. Morozov and T. Phung-Duc, Stability analysis of a multiclass retrial system with classical retrial policy, Performance Evaluation, 112 (2017), 15-26.  doi: 10.1016/j.peva.2017.03.003.  Google Scholar

[15]

M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994.  Google Scholar

[16]

T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A simple algorithm for the rate matrices of level-dependent QBD processes, Proceedings of the 5th International Conference on Queueing Theory and Network Applications, (2010), 46-52.  doi: 10.1145/1837856.1837864.  Google Scholar

[17]

T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A matrix continued fraction approach to multiserver retrial queues, Annals of Operations Research, 202 (2013), 161-183.  doi: 10.1007/s10479-011-0840-4.  Google Scholar

[18]

T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth symposium on Information and Communication Technology (SoICT 2014), (2014), 240-247.  doi: 10.1145/2676585.2676613.  Google Scholar

[19]

T. Phung-Duc and K. Kawanishi, An efficient method for performance analysis of blended call centers with redial, Asia-Pacific Journal of Operational Research, 31 (2014), 1440008 (33 pages).  Google Scholar

[20]

T. Phung-Duc, M/M/1/1 retrial queues with setup time, Proceedings of the 10th International Conference on Queueing Theory and Network Applications, (2015), 93-104.   Google Scholar

[21]

T. Phung-Duc and K. Kawanishi, Impacts of retrials on power-saving policy in data centers in Proceedings of the 11th International Conference on Queueing Theory and Network Applications, ACM, (2016), Article No. 22. doi: 10.1145/3016032.3016047.  Google Scholar

[22]

T. Phung-Duc, Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324.  doi: 10.1007/s11235-016-0177-z.  Google Scholar

[23]

T. Phung-Duc, Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345.   Google Scholar

[24]

Y. W. Shin, Stability of $MAP/PH/c/K$ queue with customer retrials and server vacations, Bulletin of the Korean Mathematical Society, 53 (2016), 985-1004.  doi: 10.4134/BKMS.b150337.  Google Scholar

[25]

R. L. Tweedie, Sufficient conditions for regularity, recurrence and ergodicity and Markov processes, Mathematical Proceedings of the Cambridge Philosophical Society, 78 (1975), 125-136.  doi: 10.1017/S0305004100051562.  Google Scholar

show all references

References:
[1]

J. R. Artalejo and T. Phung-Duc, Markovian retrial queues with two way communication, Journal of Industrial and Management Optimization, 8 (2012), 781-806.  doi: 10.3934/jimo.2012.8.781.  Google Scholar

[2]

L. A. Barroso and U. Hölzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37.  doi: 10.1109/MC.2007.443.  Google Scholar

[3]

L. Bright and P. G. Taylor, Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, Stochastic Models, 11 (1995), 497-525.  doi: 10.1080/15326349508807357.  Google Scholar

[4]

J. Chang and J. Wang, Unreliable M/M/1/1 retrial queues with set-up time, Quality Technology & Quantitative Management, (2017), 1-13.  doi: 10.1080/16843703.2017.1320459.  Google Scholar

[5]

J. E. Diamond and A. S. Alfa, The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177.  doi: 10.1080/15326349808807518.  Google Scholar

[6]

J. E. Diamond and A. S. Alfa, Matrix analytic methods for a multiserver retrial queue with buffer, Top, 7 (1999), 249-266.  doi: 10.1007/BF02564725.  Google Scholar

[7]

G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997. Google Scholar

[8]

A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138.   Google Scholar

[9]

A. Gandhi, S. Doroudi and M. Harchol-Balter, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Queueing Systems, 77 (2014), 177-209.  doi: 10.1007/s11134-014-9409-7.  Google Scholar

[10]

Q.-M. He, H. Li and Y. Q. Zhao, Ergodicity of the BMAP/PH/s/s + K retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347.  doi: 10.1023/A:1019110631467.  Google Scholar

[11]

G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death process, Journal of Applied Probability, 30 (1993), 650-674.  doi: 10.1017/S0021900200044387.  Google Scholar

[12]

G. Latouche and V. Ramaswami, Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999.  Google Scholar

[13]

E. Morozov, A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168.  doi: 10.1007/s11134-007-9024-y.  Google Scholar

[14]

E. Morozov and T. Phung-Duc, Stability analysis of a multiclass retrial system with classical retrial policy, Performance Evaluation, 112 (2017), 15-26.  doi: 10.1016/j.peva.2017.03.003.  Google Scholar

[15]

M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994.  Google Scholar

[16]

T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A simple algorithm for the rate matrices of level-dependent QBD processes, Proceedings of the 5th International Conference on Queueing Theory and Network Applications, (2010), 46-52.  doi: 10.1145/1837856.1837864.  Google Scholar

[17]

T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, A matrix continued fraction approach to multiserver retrial queues, Annals of Operations Research, 202 (2013), 161-183.  doi: 10.1007/s10479-011-0840-4.  Google Scholar

[18]

T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth symposium on Information and Communication Technology (SoICT 2014), (2014), 240-247.  doi: 10.1145/2676585.2676613.  Google Scholar

[19]

T. Phung-Duc and K. Kawanishi, An efficient method for performance analysis of blended call centers with redial, Asia-Pacific Journal of Operational Research, 31 (2014), 1440008 (33 pages).  Google Scholar

[20]

T. Phung-Duc, M/M/1/1 retrial queues with setup time, Proceedings of the 10th International Conference on Queueing Theory and Network Applications, (2015), 93-104.   Google Scholar

[21]

T. Phung-Duc and K. Kawanishi, Impacts of retrials on power-saving policy in data centers in Proceedings of the 11th International Conference on Queueing Theory and Network Applications, ACM, (2016), Article No. 22. doi: 10.1145/3016032.3016047.  Google Scholar

[22]

T. Phung-Duc, Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324.  doi: 10.1007/s11235-016-0177-z.  Google Scholar

[23]

T. Phung-Duc, Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345.   Google Scholar

[24]

Y. W. Shin, Stability of $MAP/PH/c/K$ queue with customer retrials and server vacations, Bulletin of the Korean Mathematical Society, 53 (2016), 985-1004.  doi: 10.4134/BKMS.b150337.  Google Scholar

[25]

R. L. Tweedie, Sufficient conditions for regularity, recurrence and ergodicity and Markov processes, Mathematical Proceedings of the Cambridge Philosophical Society, 78 (1975), 125-136.  doi: 10.1017/S0305004100051562.  Google Scholar

Figure 1.  The power consumption versus retrial rate for $c = 50$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The power consumption versus setup rate for $c = 30, 50$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The ratio $\mathrm{E}[P]/c$ versus retrial rate for $\alpha = 1/100$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Mean response time versus retrial rate for $c = 30, 50$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Mean response time versus retrial rate for $c = 30, 50$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The power consumption versus traffic intensity for $\mu = 1$ and $\alpha = 1/10$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  The power consumption versus retrial rate for $c = 50$ and $\alpha = 1/10$
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Truncation point $N$ and $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ for $c = 30$ and $\mu = 1/10$
$c=30$
$\alpha = 1/100$ $\alpha = 1/10$ $\alpha = 1$
$N$120315059
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $1.0060\times 10^{-11}$ $1.6243\times 10^{-10}$ $2.2090\times 10^{-15}$
Table Options

Download as excel

$c=30$
$\alpha = 1/100$ $\alpha = 1/10$ $\alpha = 1$
$N$120315059
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $1.0060\times 10^{-11}$ $1.6243\times 10^{-10}$ $2.2090\times 10^{-15}$
Table 2.  Truncation point $N$ and $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ for $c = 50$ and $\mu = 1/10$
$c=50$
$\alpha = 1/100$ $\alpha = 1/10$ $\alpha = 1$
$N$120314958
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $4.6265\times 10^{-11}$ $2.4851\times 10^{-10}$ $1.1490\times 10^{-16}$
Table Options

Download as excel

$c=50$
$\alpha = 1/100$ $\alpha = 1/10$ $\alpha = 1$
$N$120314958
$\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $4.6265\times 10^{-11}$ $2.4851\times 10^{-10}$ $1.1490\times 10^{-16}$
Table 3.  Truncation point $N$ and $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$
$c=50$$c=100$
$\rho$ $N$ $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $N$ $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$
0.139 $2.3871 \times 10^{-19}$39 $1.3689 \times 10^{-25}$
0.266 $3.3924 \times 10^{-15}$66 $1.0369 \times 10^{-17}$
0.392 $3.7031 \times 10^{-13}$92 $3.1474 \times 10^{-14}$
0.4118 $9.5226 \times 10^{-12}$118 $4.7215 \times 10^{-12}$
0.5144 $1.4487 \times 10^{-10}$144 $2.1293 \times 10^{-10}$
0.6170 $1.7715 \times 10^{-09}$170 $5.4344 \times 10^{-09}$
0.7197 $1.7430 \times 10^{-08}$196 $1.0141 \times 10^{-07}$
0.8228 $1.0765 \times 10^{-07}$227 $1.0942 \times 10^{-06}$
0.9349 $1.5416 \times 10^{-06}$321 $7.4458 \times 10^{-07}$
Table Options

Download as excel

$c=50$$c=100$
$\rho$ $N$ $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $N$ $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$
0.139 $2.3871 \times 10^{-19}$39 $1.3689 \times 10^{-25}$
0.266 $3.3924 \times 10^{-15}$66 $1.0369 \times 10^{-17}$
0.392 $3.7031 \times 10^{-13}$92 $3.1474 \times 10^{-14}$
0.4118 $9.5226 \times 10^{-12}$118 $4.7215 \times 10^{-12}$
0.5144 $1.4487 \times 10^{-10}$144 $2.1293 \times 10^{-10}$
0.6170 $1.7715 \times 10^{-09}$170 $5.4344 \times 10^{-09}$
0.7197 $1.7430 \times 10^{-08}$196 $1.0141 \times 10^{-07}$
0.8228 $1.0765 \times 10^{-07}$227 $1.0942 \times 10^{-06}$
0.9349 $1.5416 \times 10^{-06}$321 $7.4458 \times 10^{-07}$
[1]

Takeshi Saito, Kazuyuki Yagasaki. Chebyshev spectral methods for computing center manifolds. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021008
[2]

Lei Lei, Wenli Ren, Cuiling Fan. The differential spectrum of a class of power functions over finite fields. Advances in Mathematics of Communications, 2021, 15 (3) : 525-537. doi: 10.3934/amc.2020080
[3]

Yohei Yamazaki. Center stable manifolds around line solitary waves of the Zakharov–Kuznetsov equation with critical speed. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3579-3614. doi: 10.3934/dcds.2021008
[4]

Yusra Bibi Ruhomally, Muhammad Zaid Dauhoo, Laurent Dumas. A graph cellular automaton with relation-based neighbourhood describing the impact of peer influence on the consumption of marijuana among college-aged youths. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021011
[5]

Qiang Lin, Yang Xiao, Jingju Zheng. Selecting the supply chain financing mode under price-sensitive demand: Confirmed warehouse financing vs. trade credit. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2031-2049. doi: 10.3934/jimo.2020057
[6]

Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021, 3 (1) : 1-26. doi: 10.3934/fods.2021002
[7]

Zhang Chen, Xiliang Li, Bixiang Wang. Invariant measures of stochastic delay lattice systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3235-3269. doi: 10.3934/dcdsb.2020226
[8]

Imene Aicha Djebour, Takéo Takahashi, Julie Valein. Feedback stabilization of parabolic systems with input delay. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021027
[9]

Mirelson M. Freitas, Anderson J. A. Ramos, Manoel J. Dos Santos, Jamille L.L. Almeida. Dynamics of piezoelectric beams with magnetic effects and delay term. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021015
[10]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389
[11]

Cheng-Kai Hu, Fung-Bao Liu, Hong-Ming Chen, Cheng-Feng Hu. Network data envelopment analysis with fuzzy non-discretionary factors. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1795-1807. doi: 10.3934/jimo.2020046
[12]

Woocheol Choi, Youngwoo Koh. On the splitting method for the nonlinear Schrödinger equation with initial data in $ H^1 $. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3837-3867. doi: 10.3934/dcds.2021019
[13]

Xianbang Chen, Yang Liu, Bin Li. Adjustable robust optimization in enabling optimal day-ahead economic dispatch of CCHP-MG considering uncertainties of wind-solar power and electric vehicle. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1639-1661. doi: 10.3934/jimo.2020038
[14]

Mikhail Gilman, Semyon Tsynkov. Statistical characterization of scattering delay in synthetic aperture radar imaging. Inverse Problems & Imaging, 2020, 14 (3) : 511-533. doi: 10.3934/ipi.2020024
[15]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[16]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931
[17]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 307-320. doi: 10.3934/naco.2020027
[18]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206
[19]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022
[20]

Wenjing Liu, Rong Yang, Xin-Guang Yang. Dynamics of a 3D Brinkman-Forchheimer equation with infinite delay. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021052

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (302)
  • HTML views (1278)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences