# American Institute of Mathematical Sciences

• 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

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

Citation: Tuan Phung-Duc, Ken'ichi Kawanishi. Multiserver retrial queue with setup time and its application to data centers. Journal of Industrial and 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. [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. [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. [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. [5] J. E. Diamond and A. S. Alfa, The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177.  doi: 10.1080/15326349808807518. [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. [7] G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997. [8] A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138. [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. [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. [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. [12] G. Latouche and V. Ramaswami, Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999. [13] E. Morozov, A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168.  doi: 10.1007/s11134-007-9024-y. [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. [15] M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994. [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. [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. [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. [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). [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. [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. [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. [23] T. Phung-Duc, Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345. [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. [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.

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. [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. [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. [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. [5] J. E. Diamond and A. S. Alfa, The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177.  doi: 10.1080/15326349808807518. [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. [7] G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997. [8] A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138. [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. [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. [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. [12] G. Latouche and V. Ramaswami, Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999. [13] E. Morozov, A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168.  doi: 10.1007/s11134-007-9024-y. [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. [15] M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994. [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. [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. [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. [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). [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. [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. [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. [23] T. Phung-Duc, Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345. [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. [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.
The power consumption versus retrial rate for $c = 50$
The power consumption versus setup rate for $c = 30, 50$
The ratio $\mathrm{E}[P]/c$ versus retrial rate for $\alpha = 1/100$
Mean response time versus retrial rate for $c = 30, 50$
Mean response time versus retrial rate for $c = 30, 50$
The power consumption versus traffic intensity for $\mu = 1$ and $\alpha = 1/10$
The power consumption versus retrial rate for $c = 50$ and $\alpha = 1/10$
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$ 1203 150 59 $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $1.0060\times 10^{-11}$ $1.6243\times 10^{-10}$ $2.2090\times 10^{-15}$
 $c=30$ $\alpha = 1/100$ $\alpha = 1/10$ $\alpha = 1$ $N$ 1203 150 59 $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $1.0060\times 10^{-11}$ $1.6243\times 10^{-10}$ $2.2090\times 10^{-15}$
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$ 1203 149 58 $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $4.6265\times 10^{-11}$ $2.4851\times 10^{-10}$ $1.1490\times 10^{-16}$
 $c=50$ $\alpha = 1/100$ $\alpha = 1/10$ $\alpha = 1$ $N$ 1203 149 58 $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $4.6265\times 10^{-11}$ $2.4851\times 10^{-10}$ $1.1490\times 10^{-16}$
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.1 39 $2.3871 \times 10^{-19}$ 39 $1.3689 \times 10^{-25}$ 0.2 66 $3.3924 \times 10^{-15}$ 66 $1.0369 \times 10^{-17}$ 0.3 92 $3.7031 \times 10^{-13}$ 92 $3.1474 \times 10^{-14}$ 0.4 118 $9.5226 \times 10^{-12}$ 118 $4.7215 \times 10^{-12}$ 0.5 144 $1.4487 \times 10^{-10}$ 144 $2.1293 \times 10^{-10}$ 0.6 170 $1.7715 \times 10^{-09}$ 170 $5.4344 \times 10^{-09}$ 0.7 197 $1.7430 \times 10^{-08}$ 196 $1.0141 \times 10^{-07}$ 0.8 228 $1.0765 \times 10^{-07}$ 227 $1.0942 \times 10^{-06}$ 0.9 349 $1.5416 \times 10^{-06}$ 321 $7.4458 \times 10^{-07}$
 $c=50$ $c=100$ $\rho$ $N$ $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ $N$ $\widehat{\mathit{\boldsymbol{\pi}}}^{(N)} \mathit{\boldsymbol{e}}$ 0.1 39 $2.3871 \times 10^{-19}$ 39 $1.3689 \times 10^{-25}$ 0.2 66 $3.3924 \times 10^{-15}$ 66 $1.0369 \times 10^{-17}$ 0.3 92 $3.7031 \times 10^{-13}$ 92 $3.1474 \times 10^{-14}$ 0.4 118 $9.5226 \times 10^{-12}$ 118 $4.7215 \times 10^{-12}$ 0.5 144 $1.4487 \times 10^{-10}$ 144 $2.1293 \times 10^{-10}$ 0.6 170 $1.7715 \times 10^{-09}$ 170 $5.4344 \times 10^{-09}$ 0.7 197 $1.7430 \times 10^{-08}$ 196 $1.0141 \times 10^{-07}$ 0.8 228 $1.0765 \times 10^{-07}$ 227 $1.0942 \times 10^{-06}$ 0.9 349 $1.5416 \times 10^{-06}$ 321 $7.4458 \times 10^{-07}$
 [1] Yanqin Bai, Yudan Wei, Qian Li. An optimal trade-off model for portfolio selection with sensitivity of parameters. Journal of Industrial and Management Optimization, 2017, 13 (2) : 947-965. doi: 10.3934/jimo.2016055 [2] Lihui Zhang, Xin Zou, Jianxun Qi. A trade-off between time and cost in scheduling repetitive construction projects. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1423-1434. doi: 10.3934/jimo.2015.11.1423 [3] Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial and Management Optimization, 2022, 18 (1) : 375-396. doi: 10.3934/jimo.2020158 [4] Masataka Kato, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Effect of energy-saving server scheduling on power consumption for large-scale data centers. Journal of Industrial and Management Optimization, 2016, 12 (2) : 667-685. doi: 10.3934/jimo.2016.12.667 [5] Daniel Mckenzie, Steven Damelin. Power weighted shortest paths for clustering Euclidean data. Foundations of Data Science, 2019, 1 (3) : 307-327. doi: 10.3934/fods.2019014 [6] C. Burgos, J.-C. Cortés, L. Shaikhet, R.-J. Villanueva. A delayed nonlinear stochastic model for cocaine consumption: Stability analysis and simulation using real data. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1233-1244. doi: 10.3934/dcdss.2020356 [7] Haoyue Song, Fanwei Meng. Some generalizations of delay integral inequalities of Gronwall-Bellman type with power and their applications. Mathematical Foundations of Computing, 2022, 5 (1) : 45-55. doi: 10.3934/mfc.2021022 [8] Zuo Quan Xu, Fahuai Yi. An optimal consumption-investment model with constraint on consumption. Mathematical Control and Related Fields, 2016, 6 (3) : 517-534. doi: 10.3934/mcrf.2016014 [9] Rafael Diaz, Laura Gomez. Indirect influences in international trade. Networks and Heterogeneous Media, 2015, 10 (1) : 149-165. doi: 10.3934/nhm.2015.10.149 [10] Michael Helmers, Barbara Niethammer, Xiaofeng Ren. Evolution in off-critical diblock copolymer melts. Networks and Heterogeneous Media, 2008, 3 (3) : 615-632. doi: 10.3934/nhm.2008.3.615 [11] Vitali Kapovitch, Anton Petrunin, Wilderich Tuschmann. On the torsion in the center conjecture. Electronic Research Announcements, 2018, 25: 27-35. doi: 10.3934/era.2018.25.004 [12] Camillo De Lellis, Emanuele Spadaro. Center manifold: A case study. Discrete and Continuous Dynamical Systems, 2011, 31 (4) : 1249-1272. doi: 10.3934/dcds.2011.31.1249 [13] Keith Burns, Amie Wilkinson. Dynamical coherence and center bunching. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 89-100. doi: 10.3934/dcds.2008.22.89 [14] Jingzhen Liu, Ka-Fai Cedric Yiu, Kok Lay Teo. Optimal investment-consumption problem with constraint. Journal of Industrial and Management Optimization, 2013, 9 (4) : 743-768. doi: 10.3934/jimo.2013.9.743 [15] Lei Sun, Lihong Zhang. Optimal consumption and investment under irrational beliefs. Journal of Industrial and Management Optimization, 2011, 7 (1) : 139-156. doi: 10.3934/jimo.2011.7.139 [16] Filipe Martins, Alberto A. Pinto, Jorge Passamani Zubelli. Nash and social welfare impact in an international trade model. Journal of Dynamics and Games, 2017, 4 (2) : 149-173. doi: 10.3934/jdg.2017009 [17] Pau Erola, Albert Díaz-Guilera, Sergio Gómez, Alex Arenas. Modeling international crisis synchronization in the world trade web. Networks and Heterogeneous Media, 2012, 7 (3) : 385-397. doi: 10.3934/nhm.2012.7.385 [18] Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Further results on multiple coverings of the farthest-off points. Advances in Mathematics of Communications, 2016, 10 (3) : 613-632. doi: 10.3934/amc.2016030 [19] Peter E. Kloeden, Thomas Lorenz, Meihua Yang. Reaction-diffusion equations with a switched--off reaction zone. Communications on Pure and Applied Analysis, 2014, 13 (5) : 1907-1933. doi: 10.3934/cpaa.2014.13.1907 [20] Masakatsu Suzuki, Hideaki Matsunaga. Stability criteria for a class of linear differential equations with off-diagonal delays. Discrete and Continuous Dynamical Systems, 2009, 24 (4) : 1381-1391. doi: 10.3934/dcds.2009.24.1381

2021 Impact Factor: 1.411